Re: Controlling the effects of precedence

[Hans Aberg]

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.

  Hans Aberg