Parsing Expression Grammars with Unordered Choices

Parsing expression grammars (PEGs) were formalized by Ford in 2004, and have several pragmatic operators (such as ordered choice and unlimited lookahead) for better expressing modern programming language syntax. In addition, PEGs can be parsed in a linear time by using recursive-descent parsing and memoization. In this way, PEGs have a lot of positive aspects. On the other hand, it is known that ordered choices defy intuition. They may cause bugs. This is due to a priority of an ordered choice. To avoid this, unordered choices are required. In this paper, we define a parsing expression grammar with unordered choices (PEGwUC), an extension of a PEG with unordered choices. By the extension, it is expected that a PEGwUC includes both a PEG and a context-free grammar (CFG), and this allows us to write a grammar more intuitively. Furthermore, we show an algorithm for parsing a PEGwUC. The algorithm runs in a linear time when a PEGwUC does not include unordered choice and in a cubic time in worst-case running time.