|Help needed with grammar problem email@example.com (2003-03-09)|
|Re: Help needed with grammar problem firstname.lastname@example.org (2003-03-14)|
|Date:||14 Mar 2003 11:21:49 -0500|
|Posted-Date:||14 Mar 2003 11:21:49 EST|
On Sun, 9 Mar 2003 22:29:40 UTC, email@example.com (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
Search the comp.compilers archives again.