Re: Help needed with grammar problem

kgw-news@stiscan.com
14 Mar 2003 11:21:49 -0500

          From comp.compilers

Related articles
Help needed with grammar problem ymishory@study.haifa.ac.il (2003-03-09)
Re: Help needed with grammar problem kgw-news@stiscan.com (2003-03-14)
| List of all articles for this month |

From: kgw-news@stiscan.com
Newsgroups: comp.compilers
Date: 14 Mar 2003 11:21:49 -0500
Organization: Solution Technology
References: 03-03-029
Keywords: parse
Posted-Date: 14 Mar 2003 11:21:49 EST

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.


Post a followup to this message

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