Quoting David Mercer <[EMAIL PROTECTED]>:
Robert Grimm wrote:
I agree with Terence in that ambiguity vs. ordering is a trade-off.
With CFGs you may get unnecessary ambiguity and with PEGs you may get
subtle ordering errors.
Ah, so now you're persuading me the other way. At least with ambiguity, you
can discover the problem when the grammar is compiled, but subtle ordering
errors you may or may not discover...
Actually, I'm pretty much convinced (though I haven't demonstrated it
yet) that
pretty much the same grammar analysis techniques that LR/LALR-style parser
generators use to detect ambiguities and produce their parse tables could
easily be adapted to find unanticipated ordering dependencies in PEGs, with
precisely the same capabilities and limitations.
I think at one point (maybe in my MS thesis?) I proposed as future work adding
an "unordered choice" operator '|' to a PEG-based parser generator,
which would
more or less reduce to the standard ordered choice operator '/', but
only if the
parser generator can successfully verify (e.g., using LR-style analysis
techniques) that the different alternatives are indeed order-independent (or
perhaps have a single obviously correct order like 'X Y | X | <empty>').
Basically what LR parse table generation does is perform an abstract execution
of all possible paths of a parse, with a few simplifying assumptions thrown in
to make sure the analysis terminates. It should not be inherently any harder
to perform exactly the same kind of abstract execution of a PEG, with the same
simplifying assumptions, in order to determine whether certain alternation
operators definitely can or definitely cannot match the same input text. The
difference, though, would be that the PEG would not have to be "globally"
unambiguous in an LR-analyzable sense; only the particular alternator
operators
in the PEG that the user has explicitly declared "unordered" need to be
verified
umanbiguous in this way. The user could still use ordered choice constructs
whenever appropriate - e.g., when alternatives are well-known to be
"ambiguous"
but the language specification clearly specifies how such ambiguities
are to be
resolved.
I think that adapting an LR-style analysis to order dependency
detection in PEGs
would make a very nice, small, well-defined summer project for grad student -
anybody have a grad student in need of a project? :)
Cheers,
Bryan
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
