LL-Parser

In a compiler LL parser is a top-down parser, which processes the input from left to right to charge a leftmost derivation of the input.

An LL parser is called LL (k ) parser, if he can look ahead during parsing k tokens, and in contrast to the LF- parser uses the stack contents. k is referred to as lookahead. This Parsertyp are the LL (k ) grammars as a basis.

Although the LL (k ) grammars are relatively limited, LL (k ) parsers are often used. The decision is expanded according to which rule may be made only by analysis of the lookahead. A simple way to implement this Parsertechnik provides the method of recursive descent.

Operation

The starting point is a grammar. The parser uses a set of states, where a state is composed as follows:

  • Is the current content of a term basement that is used to store the current symbols. may include both terminal and non- terminal symbols.
  • Is the part of the input, which has not been read.
  • Is the output of a sequence of natural numbers, including the number of the rules of the leftmost derivation.

The non-deterministic automaton for the LL (k ) analysis is then:

  • ( Initial state)
  • ( Final state )

This is the start symbol of the underlying grammar and the analysis of the input links.

The transitions consist of the following:

  • ( Shift or shifting step )
  • (Expansion or exhaust step ), the rule in the rule set needs to be contained and the number of the rule.

LL (1) parser

This Parsertyp uses a lookahead of one character. Due to this restriction can simply be a deterministic parser can be created.

The above non-deterministic steps are thereby determined by the lookahead.

526324
de