[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## 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.
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

**Re: Controlling the effects of precedence**,
*Hans Aberg* **<=**