World Library  
Flag as Inappropriate
Email this Article

Deterministic context-free grammar

Article Id: WHEBN0010609024
Reproduction Date:

Title: Deterministic context-free grammar  
Author: World Heritage Encyclopedia
Language: English
Subject: Deterministic context-free language, Context-free grammar, Range concatenation grammars, Aperiodic finite state automaton, Embedded pushdown automaton
Publisher: World Heritage Encyclopedia

Deterministic context-free grammar

In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars. They are the subset of context-free grammars that can be derived from deterministic pushdown automata, and they generate the deterministic context-free languages. DCFGs are always unambiguous, and are an important subclass of unambiguous CFGs; there are non-deterministic unambiguous CFGs, however.

DCFGs are of great practical interest, as they can be parsed in linear time and in fact a parser can be automatically generated from the grammar by a parser generator. They are thus widely used throughout computer science. Various restricted forms of DCFGs can be parsed by simpler, less resource-intensive parsers, and thus are often used. These grammar classes are referred to by the type of parser that parses them, and important examples are LALR, SLR, and LL.


In the 1960s, theoretical research in computer science on regular expressions and finite automata led to the discovery that context-free grammars are equivalent to nondeterministic pushdown automata.[1][2][3] These grammars were thought to capture the syntax of computer programming languages. The first computer programming languages were under development at the time (see History of programming languages) and writing compilers was difficult. But using context-free grammars to help automate the parsing part of the compiler simplified the task. Deterministic context-free grammars were particularly useful because they could be parsed sequentially by a deterministic pushdown automaton, which was a requirement due to computer memory constraints.[4] In 1965, Donald Knuth invented the LR(k) parser and proved that there exists an LR(k) grammar for every deterministic context-free language.[5] This parser still required a lot of memory. In 1969 Frank DeRemer invented the LALR and Simple LR parsers, both based on the LR parser and having greatly reduced memory requirements at the cost of less language recognition power. The LALR parser was the stronger alternative.[6] These two parsers have since been widely used in compilers of many computer languages.

See also


  1. ^ Chomsky, Noam (1962). "Context Free Grammars and Pushdown Storage". Quarterly Progress Report, MIT Research Laboratory in Electronics 65: 187–194. 
  2. ^ Evey, R.J. (1963). "Application of Pushdown-Store Machines". 1963 AFIPS Proceedings of the Fall Joint Computer Conference: 215–227. 
  3. ^ Schützenberger, Marcel Paul (1963). "On Context-Free Languages and Push-Down Automata". Information and Control 6: 246–264. 
  4. ^  
  5. ^  
  6. ^ Franklin L. DeRemer (1969). "Practical Translators for LR(k) languages". MIT, PhD Dissertation. 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.