2020/10/15 by Peter Belcak, Belcak, Peter
Computer Science · #Algorithms and Data Compression #Computation and Language (cs.CL) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Natural Language Processing Techniques #Programming Languages (cs.PL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2010.07874
openalex publication_date 2020/10/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.