Abstract

The LL(finite) parsing strategy for parsing of LL(k) grammars where k needsnot to be known is presented. The strategy parses input in linear time, usesarbitrary but always minimal lookahead necessary to disambiguate betweenalternatives of nonterminals, and it is optimal in the number of lookaheadterminal scans performed. Modifications to the algorithm are shown that allowfor resolution of grammar ambiguities by precedence -- effectively interpretingthe input as a parsing expression grammar -- as well as for the use ofpredicates, and a proof of concept, the open-source parser generator Astir,employs the LL(finite) strategy in the output it generates.

 

Quick Read (beta)