Packrat parsers can support left recursion
| Autor: | Todd Millstein, James R. Douglass, Alessandro Warth |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Parsing
Theoretical computer science Java Backtracking Computer science Programming language Left recursion Memoization computer.software_genre Top-down parsing TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Rule-based machine translation Parser combinator computer computer.programming_language |
| Zdroj: | PEPM |
| DOI: | 10.1145/1328408.1328424 |
| Popis: | Packrat parsing offers several advantages over other parsing techniques, such as the guarantee of linear parse times while supporting backtracking and unlimited look-ahead. Unfortunately, the limited support for left recursion in packrat parser implementations makes them difficult to use for a large class of grammars (Java's, for example). This paper presents a modification to the memoization mechanism used by packrat parser implementations that makes it possible for them to support (even indirectly or mutually) left-recursive rules. While it is possible for a packrat parser with our modification to yield super-linear parse times for some left-recursive grammars, our experimentsshow that this is not the case for typical uses of left recursion. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|