recursive grammar

{{Short description|Computer science and linguistics concept relating to non-terminal production}}

In computer science, a grammar is informally called a recursive grammar if it contains production rules that are recursive, meaning that expanding a non-terminal according to these rules can eventually lead to a string that includes the same non-terminal again. Otherwise it is called a non-recursive grammar.{{citation

| last1 = Nederhof | first1 = Mark-Jan

| last2 = Satta | first2 = Giorgio

| contribution = Parsing Non-recursive Context-free Grammars

| doi = 10.3115/1073083.1073104

| location = Stroudsburg, PA, USA

| pages = 112–119

| publisher = Association for Computational Linguistics

| title = Proceedings of the 40th Annual Meeting on Association for Computational Linguistics (ACL '02)

| year = 2002| doi-access = free

}}.

For example, a grammar for a context-free language is left recursive if there exists a non-terminal symbol A that can be put through the production rules to produce a string with A (as the leftmost symbol).[http://www.cs.may.ie/~jpower/Courses/parsing/parsing.pdf#search='indirect%20left%20recursion' Notes on Formal Language Theory and Parsing], James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.{{citation

| last = Moore | first = Robert C.

| contribution = Removing Left Recursion from Context-free Grammars

| location = Stroudsburg, PA, USA

| pages = 249–255

| publisher = Association for Computational Linguistics

| title = Proceedings of the 1st North American Chapter of the Association for Computational Linguistics Conference (NAACL 2000)

| url = http://dl.acm.org/citation.cfm?id=974305.974338

| year = 2000}}.

All types of grammars in the Chomsky hierarchy can be recursive and it is recursion that allows the production of infinite sets of words.