Question

The Wikipedia article for PEG parsers defines the following combinators:

2.Given any existing parsing expressions e, e1, and e2, 
a new parsing expression can be constructed using the following operators: 

Sequence: e1 e2
Ordered choice: e1 / e2
Zero-or-more: e*
One-or-more: e+
Optional: e?
And-predicate: &e
Not-predicate: !e

Are all these combinators truly necessary? It seems to me that Optional and One-Or-More can easily be implemented as

e+ = e* & e
e? = e / ""

Am I right in saying this, or is there something fundamental that requires those two forms be separate atoms? I'm building my own PEG parser, and skipping those two (or defining them in terms of other combinators) would be convenient, but I want to make sure I'm not missing anything important.

Was it helpful?

Solution

You are correct, except that e+ is written as a sequence without the &.

e+ := e e*

OTHER TIPS

[Expanding on what you and 280Z28 said...]

  • + can be defined in terms of sequence and * and possibly & (though the latter expansion is not commonly used):

    x+ == x x*
    x+ == &x x*
    
  • ? can be defined in terms of choice:

    x? == x / (empty)
    
  • & can be defined in terms of !:

    &x = !!x
    
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top