2011/1/6 Peter Cashin <cashin.pe...@gmail.com>
> 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!
>
My intuition to that problem is that as long as left-recursion is present,
we should prefer a left tree. Yes, left-recursion comes handy when it comes
to clearly express the intent of a grammar, but it should not be a careless
choice. I assume that since one used left-recursion, his expectation is a
left-associative behaviour, no matter if the rule is also right-recursive or
not.
That's where the idea from Peter gets really nice : it can allow one aware
dude to use left recursion but to get a right associative behaviour by
adding an intermediate rule in it. Some fair hack.
Others have discussed the thing, see Laurence Tratt's "Direct
Left-Recursive Parsing Expression Grammars"
http://tratt.net/laurie/research/publications/html/tratt__direct_left_recursive_parsing_expression_grammars/
The author suggests we fix the behaviour of Wrath et al.'s left-recursion
handling algorithm to get it parse to "left trees" when a rule is both left
and right recursive.
Alex
> 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
>
>
_______________________________________________
PEG mailing list
PEG@lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/peg
