LL(*)
Authors:
Open Access
- 4 June 2011
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 46 (6) , 425-436
Abstract
Despite the power of Parser Expression Grammars (PEGs) and GLR, parsing is not a solved problem. Adding nondeterminism (parser speculation) to traditional LL and LR parsers can lead to unexpected parse-time behavior and introduces practical issues with error handling, single-step debugging, and side-effecting embedded grammar actions. This paper introduces the LL(*) parsing strategy and an associated grammar analysis algorithm that constructs LL(*) parsing decisions from ANTLR grammars. At parse-time, decisions gracefully throttle up from conventional fixed k=1 lookahead to arbitrary lookahead and, finally, fail over to backtracking depending on the complexity of the parsing decision 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 expressivity 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 effective for a wide variety of applications.Keywords
This publication has 14 references indexed in Scilit:
- Parsing expression grammars2004
- Elkhound: A Fast, Practical GLR Parser Generator2004
- Practical Experiments with Regular Approximation of Context-Free LanguagesComputational Linguistics, 2000
- Practical arbitrary lookahead LR parsingJournal of Computer and System Sciences, 1990
- Compact recursive-descent parsing of expressionsSoftware: Practice and Experience, 1985
- On LL-regular grammarsJournal of Computer and System Sciences, 1979
- On the parsing of LL-regular grammarsLecture Notes in Computer Science, 1976
- LL-regular grammarsInformation Processing Letters, 1975
- Transition network grammars for natural language analysisCommunications of the ACM, 1970
- An efficient context-free parsing algorithmCommunications of the ACM, 1970