3

%prec または %left を使用せずに Bison で優先順位と結合性をどのように設定できますか? 必要のない文法を書く方法はありますか?

4

2 に答える 2

8

%prec、%left、およびを使用したくない場合は、%right優先順位を確立するために複数の非終端記号を使用する必要があります。

たとえば、次の文法を考えてみましょう。

%token NUMBER
%left '+'
%left '*'
%right '^'

%%

expression
    : NUMBER
    | expression '+' expression
    | expression '*' expression
    | expression '^' expression
    | '(' expression ')'
    ;

%%

式 とどのように一致するか見てみましょう1 + 2 * 3。上記の文法から優先順位ディレクティブを削除すると、文法はこの式に 2 つの方法で一致する可能性があります。1 つの方法を次に示します。

expression(+)
    |
    +-- expression(NUMBER 1)
    |
    +-- expression(*)
            |
            +-- expression(NUMBER 2)
            |
            +-- expression(NUMBER 3)

別の方法は次のとおりです。

expression(*)
    |
    +-- expression(+)
    |       |
    |       +-- expression(NUMBER 1)
    |       |
    |       +-- expression(NUMBER 2)
    |
    +-- expression(NUMBER 3)

最初の方法のようにのみ一致する文法を書きたいと思い*ます+。expression次のように、新しい非終端記号を作成し、非終端記号の生成を新しい非終端記号に分割する必要があります。

%token NUMBER

%%

primaryExpression
    : NUMBER
    | '(' expression ')'
    ;

exponentiationExpression
    : primaryExpression
    // Right-recursion makes this right-associative.
    | primaryExpression '^' exponentiationExpression
    ;

multiplicationExpression
    : exponentiationExpression
    // Left recursion makes this left-associative.
    | multiplicationExpression '*' exponentiationExpression
    ;

additionExpression
    : multiplicationExpression
    | additionExpression '+' multiplicationExpression
    ;

expression
    : additionExpression
    ;

この文法が式 とどのように一致するかを見てみましょう1 + 2 * 3。次の方法でのみ一致できます。

expression
    |
    +-- additionExpression
            |
            +-- additionExpression
            |       |
            |       +-- multiplicationExpression
            |               |
            |               +-- exponentiationExpression
            |                   |
            |                   +-- primaryExpression(NUMBER 1)
            |
            +-- multiplicationExpression
                    |
                    +-- multiplicationExpression
                    |       |
                    |       +-- exponentiationExpression
                    |               |
                    |               +-- primaryExpression(NUMBER 2)
                    |
                    +-- exponentiationExpression
                            |
                            +-- primaryExpression(NUMBER 3)

現在、解析ツリーにはより多くのレベルがありますが、望ましいバインディングの優先順位に一致しています。

このように文法を記述したい場合、LALR パーサーは通常、左再帰を処理するときよりも右再帰を処理するときにより多くのメモリを使用することに注意してください。そのため、( で使用されている) 右再帰を左再帰として書き直しexponentiationExpression、結合性をコードで修正するのが一般的です。

于 2012-09-14T03:35:01.663 に答える
1

はい -- さまざまなレベルの優先順位に個別のルールを使用し、左と右の再帰を介して結合性を制御できます。たとえば、 and よりも優先順位の低い and を取得するには、一方+が左連想で、もう一方が右1であり、次のようにすることができます。-*/

number: literal | variable;

mul_expr: number
        | mul_expr MUL_OP number
        ;

add_expr: mul_expr
        | mul_expr ADD_OP add_expr
        ;

はい、これは本当に yacc のような疑似コードです。yacc、byacc、Bison などはそのまま拒否するはずです。

1はい、通常はすべて左結合ですが、必要に応じて右結合にする方法を示すためにこれを行っているだけです。

于 2012-09-14T03:26:22.203 に答える