[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Controlling the effects of precedence
From: |
Frank Heckenbach |
Subject: |
Re: Controlling the effects of precedence |
Date: |
Wed, 14 May 2003 00:48:08 +0200 |
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)