Recursive grammar

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.[1]

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).[2][3] All types of grammars in the Chomsky hierarchy can be recursive and it is recursion that allows the production of infinite sets of words.[1]

Properties

A non-recursive grammar can produce only a finite language; and each finite language can be produced by a non-recursive grammar.[1] For example, a straight-line grammar produces just a single word.

A recursive context-free grammar that contains no useless rules necessarily produces an infinite language. This property forms the basis for an algorithm that can test efficiently whether a context-free grammar produces a finite or infinite language.[4]

gollark: Yes.
gollark: Did you know? Bees approximate your location with increasing accuracy.
gollark: How fun.
gollark: Excitingly, minoteaur crashes when closing the database if migrating it if and only if it is not run under valgrind.
gollark: I can't point to a particular build/project tooling system which *utterly* doesn't fail for me. makefiles fail unfathomably sometimes, cmake fails unfathomably lots of the time, cargo sometimes runs into bizarre dependency errors, nimble works fine actually but I don't ever install stuff from it, luarocks is no, python has an awful mess, etc.

References
  1. Nederhof, Mark-Jan; Satta, Giorgio (2002), "Parsing Non-recursive Context-free Grammars", Proceedings of the 40th Annual Meeting on Association for Computational Linguistics (ACL '02), Stroudsburg, PA, USA: Association for Computational Linguistics, pp. 112–119, doi:10.3115/1073083.1073104.
  2. Notes on Formal Language Theory and Parsing, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.
  3. Moore, Robert C. (2000), "Removing Left Recursion from Context-free Grammars", Proceedings of the 1st North American Chapter of the Association for Computational Linguistics Conference (NAACL 2000), Stroudsburg, PA, USA: Association for Computational Linguistics, pp. 249–255.
  4. Fleck, Arthur Charles (2001), Formal Models of Computation: The Ultimate Limits of Computing, AMAST series in computing, 7, World Scientific, Theorem 6.3.1, p. 309, ISBN 9789810245009.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.