Abstract | ||
---|---|---|
Parsing Expression Grammars (PEGs) are a formalism that can describe all deterministic context-free languages through a set of rules that specify a top-down parser for some language. PEGs are easy to use, and there are efficient implementations of PEG libraries in several programming languages. A frequently missed feature of PEGs is left recursion, which is commonly used in Context-Free Grammars (CFGs) to encode left-associative operations. We present a simple conservative extension to the semantics of PEGs that gives useful meaning to direct and indirect left-recursive rules, and show that our extensions make it easy to express left-recursive idioms from CFGs in PEGs, with similar results. We prove the conservativeness of these extensions, and also prove that they work with any left-recursive PEG. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-33182-4_4 | Sci. Comput. Program. |
Keywords | DocType | Volume |
left recursion,parsing | Journal | 96 |
Issue | ISSN | Citations |
P2 | 0167-6423 | 2 |
PageRank | References | Authors |
0.42 | 19 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sérgio Medeiros | 1 | 28 | 3.31 |
Fabio Mascarenhas | 2 | 28 | 5.29 |
Roberto Ierusalimschy | 3 | 463 | 54.25 |