While I was studying left recursion, I realized that it becomes complex and
unpredictable very fast. Allowing left recursion in peg parser is almost
like a permission for making it extremely complicated. Suddenly right
recursion starts affecting what ends up actually parsed and it's neither
nice that the solution is some wrap-around papered over the simple ways to
parse with parsing expression grammars.
I noticed another property that isn't emphasized a lot about pegs. If you
scan from right to left instead of left to right, the same grammar may
match a different language. Regular expressions have same behavior though.
It all gave me a reason to question the sanity in parsing expression
grammars. The idea to construct parser from recognition rules sounds
intuitive though. Perhaps there's a way to construct recognition based
parsing that doesn't depend on direction of evaluation as much.
Human parses the text by looking at some small area at once. Perhaps it
would make sense imitating that. Here's some observations:
Even if PEG parsing doesn't force that, it seems preferable to mark some
words, such as 'if', 'for' and 'else', as keywords. "term = identifier"
seems to be less specific than "statement = if ... else ..." or
"statement = for ... in" .
Infix expressions alone are unambiguous, and if human doesn't know their
precedence then only then they become ambiguous. For example: "4 + 5*3" is
easy to understand because precedence is very much standardized at that
point. The "4 + 3 << 2" is more ambiguous.
If some pattern is lacking, the pieces that formed parts of that pattern
are garbage. For example superfluous '(' and ')' parentheses. Some such
garbage patterns cause ambiguous situations as well.
I don't know whether I explore this idea further. It feels more promising
because there's chance for better error reporting there. It could also work
in noisy settings. Haven't studied whether there's something similar
existing already.
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
