Re: Controlling the effects of precedence

[Frank Heckenbach]

Hans Aberg wrote:

> 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.
> 
> The traditional translated grammar is
>     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.

If you identify the equivalent symbols (E and E_11, E_12 and E_21,
E_3 and E_22) and further substitute E_12 for `E_2 | E_3' in the E
rule, you get:

     E_1 -> E + E_12
     E_2 -> E_12 * E_3
     E_3 -> I
     E -> E_1 | E_12
     E_12 -> E_2 | E_3

Now substitute E_1 into the E rule (where it's used exclusively),
likewise E_2 into the E_12 rule

     E -> E + E_12 | E_12
     E_12 -> E_12 * E_3 | E_3
     E_3 -> I

And the result is just the traditional grammar (up to symbol
renamings).

I'm not sure if every precedences can be expressed as a series of
limitations on the parse tree -- at least bison defines them as
relations between rules and look-ahead tokens -- but if you can do
this, this method should work.

Frank

-- 
Frank Heckenbach, address@hidden
http://fjf.gnu.de/
GnuPG and PGP keys: http://fjf.gnu.de/plan (7977168E)