Abstract
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 (I), whereas LL(k) is stronger than LL (I), appears to give LR techniques the additional benefit of not requiring k-token lookahead and its associated ovehead. 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 lwkahead. We denote such "optimized" LL(k) parsers LLm(n)|mSnSk
Date of this Version
July 1992