Hi Peter:
I like the idea of a well defined implicit parse tree.
The three simple cases (left tree, right tree, and flat list) work very
well:
sum = sum '+' int | int
Left recursion is left-associative: 1+2+3+4 => (((1+2)+3)+4)
sum = int '+' sum | int
Right recursion is right-associative: 1+2+3+4 => (1+(2+(3+4)))
sum = int ('+' int)*
Repeat generates a simple flat list : 1+2+3+4 => (1+2+3+4)
But I can't find a simple way to define:
sum = sum '+' sum | int
Perhaps it should be a balance, so that 1+2+3+4 => ((1+2)+(3+4))
But what about 1+2+3? Should that be (1+(2+3)) or ((1+2)+3) or (1+2+3)?
So your question is in my "too hard" basket!
I hope someone else has a better answer....
Cheers,
Peter Cashin
On Fri, Jan 7, 2011 at 6:28 AM, Peter Goodman <peter.good...@gmail.com>wrote:
> Hello PEG list,
>
> Suppose I have the following PEG:
>
> S -> S S / a.
>
> For the string "aaaa", Warth et al.'s LR support method would yield
> the following tree: (a(a(a(aa)))). However, it has been suggested that
> the natural/expected tree for this string is really ((((aa)a)a)a).
> What does everyone think the parse tree should be for the following
> PEG:
>
> S -> S B / a
> B -> S
>
> I ask because supporting ((((aa)a)a)a) is, in effect, making a special
> case for left recursion in the presence of non-left recursion. But, if
> one were to think in terms of the language of B, then the parse of the
> above grammar should probably be (a(a(a(aa)))). If this is acceptable,
> then it means getting right-leaning trees with left recursion is no
> more complicated then adding an intermediary variable. The other side
> of things is that (roots of) left recursion should be prioritized over
> all else as a means of getting similar trees to what one might expect
> from a left-to-right bottom-up parser. What are people's thoughts on
> this?
>
> Best Regards,
>
> Peter Goodman,
> http://ioreader.com
> 70 Winston Circle,
> Montreal, Quebec
> H9S 4X6
>
> _______________________________________________
> PEG mailing list
> PEG@lists.csail.mit.edu
> https://lists.csail.mit.edu/mailman/listinfo/peg
>
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
