Skip to content
Parsing

Efficient LL(k)

In terms of recognition strength, LL techniques are widely held to be inferior to LR parsers. The fact that any LR(k) grammar can be rewritten to be LR(1), whereas LL(k) is stronger than LL(1), appears to give LR techniques the additional benefit of not requiring k-token lookahead and its associated overhead. In this paper, we suggest that LL(k) is actually superior to LR(1) when translation, rather than acceptance, is the goal. Further, a practical method of generating efficient LL(k) parsers is presented. This practical approach is based on the fact that most parsing decisions in a typical LL(k) grammar can be made without comparing k-tuples and often do not even require the full k tokens of look ahead. We denote such "optimized" LL(k) parsers

— Terence Parr, 1990 ↗

Implementations

  • ANTLR v1