Re: Why LL(1) Parsers do not support left recursion?

On 25 Jul 2006 00:40:16 -0400, Hans-Peter Diettrich wrote:


> SM Ryan schrieb:
>
>> If the semantics of a subtract production are the value of the right
>> subtree is subtracted from the value of left subtree, then
>> 3 - 2 - 1
>> with left recursion is
>> = (3 - 2) - 1 = 1 - 1 = 0
>> with right recursion is
>> = 3 - (2 - 1) = 3 - 1 = 2
>
> This is a property of the asymmetric subtraction operation, which
> doesn't apply to the symmetric addition or multiplication operations. Of
> course it's a good idea to enforce a unique sequence of *numerical*
> operations in program code, whereas in mathematical formulas such
> additional restrictions should *not* be built into a grammar.


Do you mean that association should be handled after parsing? That would be
a strange language. However, if you merely argue that 3 - 2 - 1 should be
parsed as:


" -"
  /|\
3 2 1


or (maybe better) as


        "+"
      / | \
    / "-""-"
  / | \
3 2 1


then I would certainly agree with you. But this is also "built in grammar"
to me.


--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Return to the comp.compilers page.
Search the comp.compilers archives again.