LF parser

from Wikipedia, the free encyclopedia

An LF parser ( English strong LL parser ) is a top-down parser that decides exclusively on the basis of the k next input tokens for which alternative a non-terminal symbol is to be replaced. It differs from an LL parser in that the decision sets used when looking ahead must be pairwise disjoint for each nonterminal symbol , that is, each tuple of metasymbol and k- lookahead token must clearly refer to an alternative at any point in time . Therefore this method only works for special context-free grammars , the LF (k) grammars . LF parsers are also known as strong LL parsers.

An LF parser is called an LF (k) parser if it can look ahead to k tokens during parsing . These tokens are also known as lookahead tokens .

The class of LF (1) grammars is the same as the class of LL (1) grammars. For , however, the classes differ, as can be seen from the following grammar, which is in LL (2), but not in LF (2):

S → a A | b B
A → C ab
B → C b
C → a | ε

This grammar may be a LF (2) parser not be implemented, because both are the next token from , both a ε-derivative could be necessary if of A was derived from as well as a derivative with respect to a , if of B from was derived. An LL grammar is available, since it is always possible to distinguish between two possible derivations with the same context using the lookaheads. Trivially, every LF grammar is an LL grammar. The example can be expanded to include anything, for example:

S → a A | b B
A → C aᵏ⁻¹ b
B → C aᵏ⁻² b
C → a | ε

LF parsers can be implemented much more easily, for example by means of recursive descent , but the term LL parser is used much more frequently because LL (1) / LF (1) parsers are the most common and there is no difference. Every LL (1) grammar is also an LF (1) grammar, because if the context were decisive for the selection of a derivation, this would at most be a token a in the lookahead, i.e. H. an ε-derivative or a derivative starting with a would be possible, but this would also be done taking the context into account.

literature

  • Derick Wood: The theory of left factored languages: part 1. Comp. Journal   12 : 4 (1969)
  • Derick Wood: The theory of left factored languages: part 2. Comp. Journal   13 : 1 (1970)
  • Derick Wood: A further note on top-down deterministic languages. Comp. Journal   14 : 4 (1971)