7

左結合演算子を使用した単純な算術式には、次のEBNF文法があります。

expression:
    term {+ term}
    
term:
    factor {* factor}
    
factor:
    number
    ( expression )

演算子の結合性を変更せずに、これをBNF文法に変換するにはどうすればよいですか? 次の BNF 文法は、演算子が右結合になっているため、うまくいきません。

expression:
    term
    term + expression
    
term:
    factor
    factor * term
    
factor:
    number
    ( expression )

ウィキペディアは次のように述べています。

いくつかの解決策は次のとおりです。

  1. 再帰的なままになるように文法を書き直すか、または
  2. 正しい優先順位/結合性を強制するために、より多くの非終端記号で文法を書き直すか、または
  3. YACC または Bison を使用している場合は、%left、%right、および %nonassoc という演算子宣言があり、パーサー ジェネレーターにどの結合性を強制するかを伝えます。

しかし、文法の書き直し方については書かれておらず、YACC や Bison などの解析ツールは一切使用せず、単純な再帰降下のみを使用しています。私が求めていることは可能ですか？

4

2 に答える 2

10 
expression
    : term 
    | expression + term;

それだけ簡単です。もちろん、左再帰文法を認識するために何らかの記述の LR パーサーが必要になります。または、再帰的降下の場合、そのような文法を認識することは可能ですが、右結合のものほど単純ではありません。そのようなものと一致させるには、小さな再帰的上昇パーサーをロールする必要があります。

Expression ParseExpr() {
    Expression term = ParseTerm();
    while(next_token_is_plus()) {
        consume_token();
        Term next = ParseTerm();
        term = PlusExpression(term, next);
    }
    return term;
}

この疑似コードは、そのスタイルの左再帰文法を認識する必要があります。

于 2012-07-11T14:14:25.097 に答える
1

パピーが提案することは、次の文法でも表現できます。

expression: term opt_add
opt_add: '+' term opt_add
       | /* empty */

term:  factor opt_mul
opt_mul: '*' factor opt_mul
       | /* emtpty */

factor: number
      | '(' expression ')
于 2016-12-08T16:12:35.870 に答える