Re: Help needed with grammar problem

On Sun, 9 Mar 2003 22:29:40 UTC, ymishory@study.haifa.ac.il (Yuval Mishory) wrote:


> hello everyone,
> I'm facing a problem:
>
> Among other rules, I have a syntax rule that goes E -> E R E , which
> is of course a left recursion. now, this syntax rule is supposed to be
> interpreted into a syntax subtree that is supposed to be binary and
> created preorder, meaning I'd like the lefthand side E to become a
> node of type R, which has two 'sons' of type E (each of which may
> become another R itself and so on).
>
> Simple left recursion elimination algorithms can't help me here,
> because eventually it still comes down to inorder processing, which
> gives me a non-binary tree (E may become a single node, three nodes,
> five nodes and so on).


Ambiguous to start with! E R E R E R E has multiple parses. Never
mind trying to eliminate left recursion. That will not make the
ambiguity go away. Either you need precedence-associativity or
another level of non-terminal in the language. What are the other
productions for E? Try substitution of Es to see if you can make
sense of it. Or examine a FSM that accepts the input to give you some
insight on the needed productions.

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