Frage

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.

War es hilfreich?

Lösung

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

e+ := e e*

Andere Tipps

[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
    
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top