LL(*): the foundation of the ANTLR parser generator

摘要

Despite the power of Parser Expression Grammars (PEGs) and GLR, parsing is not a solved problem. Adding nonde- terminism (parser speculation) to traditional LL and LR parsers can lead to unexpected parse-time behavior and in- troduces practical issues with error handling, single-step de- bugging, and side-e ecting embedded grammar actions. This paper introduces the LL(*) parsing strategy and an asso- ciated grammar analysis algorithm that constructs LL(*) parsing decisions from ANTLR grammars. At parse-time, decisions gracefully throttle up from conventional xed k ≥1 lookahead to arbitrary lookahead and, nally, fail over to backtracking depending on the complexity of the parsing de- cision and the input symbols. LL(*) parsing strength reaches into the context-sensitive languages, in some cases beyond what GLR and PEGs can express. By statically removing as much speculation as possible, LL(*) provides the expressiv- ity of PEGs while retaining LL's good error handling and unrestricted grammar actions. Widespread use of ANTLR (over 70,000 downloads/year) shows that it is e ective for a wide variety of applications.