The LL(finite) strategy for optimal LL(k) parsing
This addresses parsing efficiency and flexibility for compiler and language tool developers, though it appears incremental as an extension of LL(k) parsing methods.
The paper introduces the LL(finite) parsing strategy for LL(k) grammars without requiring a known k, achieving linear-time parsing with minimal lookahead and optimal terminal scans. It also presents modifications for handling grammar ambiguities and predicates, implemented in the open-source parser generator Astir.
The LL(finite) parsing strategy for parsing of LL(k) grammars where k needs not to be known is presented. The strategy parses input in linear time, uses arbitrary but always minimal lookahead necessary to disambiguate between alternatives of nonterminals, and it is optimal in the number of lookahead terminal scans performed. Modifications to the algorithm are shown that allow for resolution of grammar ambiguities by precedence -- effectively interpreting the input as a parsing expression grammar -- as well as for the use of predicates, and a proof of concept, the open-source parser generator Astir, employs the LL(finite) strategy in the output it generates.