bug-bison
[Top][All Lists]

## Re: Controlling the effects of precedence

 From: Hans Aberg Subject: Re: Controlling the effects of precedence Date: Tue, 13 May 2003 23:19:32 +0200

```At 02:50 +0200 2003/05/13, Frank Heckenbach wrote:
>> In the generalized precedence scheme that I devised is as follows: For
>> every production
>>     A -> B_1 ... B_k
>> if B_i is a variable, one is admitted to impose restrictions, which of the
>> productions of the form
>>     B_i -> ...
>> that can be used in a derviation (i.e., when constructing the parse tree).
>
>So effectively, you ...

Here is a more complicated example:

Take the grammar
left +
left *
1.  E -> E + E
2.  E -> E * E
3.  E -> I
i.e., * has higher precedence than +.

I expressed the precedences as a series of limitations on the parse tree.
In the example, the second RHS E of production 1 can only be expanded using
rule 2. The first RHS E of production 2 cannot be expanded using production
1, and the second RHS E can only be expanded using production 3. This is
one gets if one translates the precedence conditions into the picture I
gave.

Then give new names to all LHS and RHS variables affected involved in the
restrictions, getting
E_1 -> E_11 + E_12
E_2 -> E_21 * E_22
E_3 -> I
After that, add all productions according to the restrictions:
E -> E_1 | E_2 | E_3
E_11 -> E_1 | E_2 | E_3
E_12 -> E_2 | E_3
E_21 -> E_2 | E_3
E_22 -> E_3

This seems to work. -- I haven't thought throw completely this grammar
translation scheme. But it is interesting to see that it can be done,
because it then means that the parsing only depends on a grammar, and thus
will be independent of parsing algorithms.

E -> E + T
E -> T
T -> T * F
T -> F
F -> I
It would perhaps be interesting to see how to extract this more compact
form as well.

Hans Aberg

```