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.

有帮助吗?

解决方案

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

e+ := e e*

其他提示

[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
    
许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top