Just announcing a paper submitted for publication.
Abstract:
Parsing Expression Grammar (PEG) encodes a recursive-descent parser with
limited backtracking.
Its properties are useful in many applications.
In its appearance, PEG is almost identical to a grammar in the Extended
Backus-Naur Form (EBNF), but may define a different language.
Moreover, PEG has a feature that is useful but alien to EBNF, namely
syntactic predicate.
Recent research found the condition under which PEG without predicates
defines the same language as its EBNF look-alike.
The condition is that the limited backtracking of PEG is efficient as
replacement for full backtracking.
No EBNF equivalence can be defined for PEG with predicates, but we
conjecture that satisfying the same condition makes the grammar
well-behaved.
There is, in general, no mechanical way to check the condition, but it
can be often checked by inspection.
The paper outlines an experimental tool to facilitate such inspection.
http://www.romanredz.se/pubs.htm
Roman Redziejowski
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
