Deterministic context-free language

A deterministic context -free language is a language that is accepted by a deterministic pushdown automaton. Sometimes the abbreviated term is used deterministic language. The definition goes back to Seymour Ginsburg and Sheila Greibach.

In terms of grammars there is also the name of LR ( k ) language: Any LR ( k ) grammar describes a deterministic context -free language. Conversely, there is one for each language deterministic context -free, so that an LR ( k ) language (ie, a LR ( k ) grammar has ). In fact, is not sufficient for it in any case, however. However, it can also be any deterministic context-free language which is not LR ( 0), transfer by introducing a unique label for the word end in an LR ( 0) language.

Properties

Deterministic context-free languages ​​have very useful for practical property that for them LR parsers exist, can be used with which decided in linear time when reading from left to right, if the input is a word of the language. Many formal languages ​​used in practice, in particular programming languages ​​, belong to this class of languages ​​.

Furthermore, the deterministic context -free languages ​​are closed under:

  • Averaging with regular amounts
  • Complement
  • Application of inverse homomorphisms

They are not closed under:

  • Reflection
  • Union
  • Average
  • Concatenation
  • - free homomorphisms

Relation to other language classes

Since the construction of an LR parser of an LR ( 1 ) grammar often leads to a deterministic context -free language to very large parse tables, light restrictions are made in practice, leading to lesser thickness. The two limitations of this type LALR and SLR parser.

Another subclass of the LR ( k) are the languages ​​LL (k ) languages ​​. These are sometimes preferred for certain applications, because this parser can be directly programmed easily without a parser from a grammar (see Recursive descent ). Continues during parsing information on the exact position in the parse tree available. This is especially useful because it allows inherited attributes in the definition of semantics in a simple way.

In LR parsers, the possible tree constellation above the handle is processed, however, a regular language. Common parser generators such as yacc therefore limited to the possibility of S- Attribution, which allows only synthesized attributes. Meanwhile, however, exists with zyacc also a parser generator that allows LR- attribution, ie inherited attributes in the cases where they can be clearly evaluated to right parsing left.

The deterministic context -free languages ​​are a proper subclass of context-free languages. They are incomparable with the linear languages ​​, but a real upper class of deterministic linear languages. Furthermore, they are a proper subclass of the deterministic growing context-sensitive languages ​​that are consistent with the Church - Rosser languages.

Vereinigung Donald Knuth
223711
de