Deterministic Context Free Language

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

In relation to grammars there is also the designation LR ( k ) language : Every LR (k) grammar describes a deterministic context-free language. Conversely, for any deterministically context-free language, there is one such that is an LR ( k ) language (i.e., has an LR ( k ) grammar). In fact, that's enough in any case , but not . However, any deterministic context-free language that is not LR (0) can also be converted into an LR (0) language by introducing a clear marking for the end of the word. ${\ displaystyle L}$ ${\ displaystyle k}$ ${\ displaystyle L}$ ${\ displaystyle k = 1}$ ${\ displaystyle k = 0}$

properties

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

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

Intersection with regular languages
complement
Application of inverse homomorphisms

They are not completed under:

Mirroring, that is, reversing the order of the characters in each word
Union
average
Concatenation
${\ displaystyle \ varepsilon}$ -free homomorphisms

Relationship to other language classes

Since the construction of an LR parser from an LR (1) grammar for a deterministic context-free language often leads to very large parse tables, slight restrictions are made in practice that lead to less power. The two limitations of this kind are LALR and SLR parsers .

Another subclass of the LR (k) languages are the LL (k) languages . These are sometimes preferred for certain applications, as parsers can easily be programmed directly from a grammar without a parser generator (see recursive descent ). Information about the exact position in the parse tree is also available during parsing. This is particularly useful because it easily allows inherited attributes when defining the semantics.

With LR parsers, however, the possible tree constellation above the processed handle is a regular language. Common parser generators such as yacc are therefore limited to the option of S-attribution , which only allows synthesized attributes. In the meantime, however, there is also a parser generator, zyacc, which allows LR attribution , i.e. H. inherited attributes in those cases where they can be uniquely evaluated when parsing from left to right.

The deterministic context-free languages are a real sub-class of the context-free languages . They are incomparable to the linear languages , but a real upper class of the deterministic linear languages . Furthermore, they are a real sub-class of the deterministic, increasingly context-sensitive languages , which correspond to the Church-Rosser languages .

literature

Seymour Ginsburg , Sheila A. Greibach : Deterministic context-free languages . In: Information and Control 9, 1966, ISSN 0019-9958 , pp. 620-648.
Donald E. Knuth : On the Translation of Languages from Left to Right . In: Information and Control 8, 1965, ISSN 0019-9958 , pp. 607-639, (Reprint of an extended version in: Donald E. Knuth: Selected Papers on Computer Languages . Center for the Study of Language and Information, Stanford CA 2003 , ISBN 1-575-86381-2 , ( CSLI lecture notes 139), chapter 15).

Web links

DCFL . In: Complexity Zoo. (English)