next up previous
Next: Turing machines and the Up: How to implement a Previous: How to implement the

Beyond LL(1) - use LR(1) generators

The restriction to LL(1) has a number of disadvantages: In many case a natural (and unambiguous) grammar like $ G$ has to be changed. There are some cases where this is actually impossible, i.e. although the language is deterministic there is no LL(1) grammar for this.

Luckily, there is a more powerful approach, called LR(1). LL(1) proceeds from top to bottom, when we are looking at the parse tree, hence this is called top-down parsing. In contrast LR(1) proceeds from bottom to top, i.e. it tries to construct the parse tree from the bottom upwards.

The disadvantage with LR(1) and the related approach LALR(1) (which is slightly less powerful but much more efficient) is that it is very hard to construct LR-parsers from hand. Hence there are automated tools which get the grammar as an input and which produce a parser as the output. One of the first of those parser generators was YACC for C. Nowadays one can find parser generators for many languages such as JAVA CUP for Java and Happy for Haskell.


next up previous
Next: Turing machines and the Up: How to implement a Previous: How to implement the
Thorsten Altenkirch 2001-05-08