A construction method for non-left-recursive parsing expression grammars

摘要

Parsing expression grammars (PEGs) have recently been used to describe the syntax of artificial languages such as programming languages. Although PEGs look similar to context-free grammars (CFGs), all PEGs have linear-time parsers, and cannot express ambiguous grammars unlike CFGs. From a theoretical point of view, it is undecidable whether a PEG is left-recursive or not. But it has been an open problem whether there is an equivalent non-left-recursive PEG for every PEG. We propose a method which constructs an equivalent non-left-recursive PEG G' from an arbitrary PEG G. And we prove that this method is valid. The PEG G' detects left-recursion by memorizing the history of applied rules in G in nonterminals.