[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 <=