演算子結合性

Question

は、私は次のEBNF式の文法を持っている：

<expr> -> <term> { (+|-) <term> } 
<term> -> <factor> { (*|/|%) <factor> } 
<factor> -> <pow> { ** <pow> } 
<pow>  -> (<expr>) | <id> 
<id>  -> A | B | C 

私は文法がその事業者のための特定の結合性を強制する、またはそれは、パーサコードで実装する必要があるかどうかどうかを判断する必要があります。私が今までに読んだことから、それはそうではないように見えますが、私は連想の原因を理解するのに苦労しています。どんな助けでも大いに役立つでしょう！

Answer 1

が切り裂く標準的な変換では、式文法を、トップダウン（LL）文法で解析できる形式に変換すると、LL文法は左結合演算子に対応できないため、結合情報は既に削除されています。実際、解析木はLL文法によって誘発され、すべての双対演算子を右結合にする。しかし、セマンティックアクションではあまり問題にすることなく、一般的に演算子を再関連付けすることができます。

これは、乗算とべき乗演算子が類似の文法生成を持つように見えるためですが、通常は累乗は右結合で、他の二項演算子は左結合であると考えられます。

LR文法では、これは明らかであろう。

上記文法で

<expr> -> <term> | <expr> + <term> | <expr> - <term> 
<term> -> <factor> | <term> * <factor> | <term>/<factor> | <term> % <factor> 
<factor> -> <pow> | <pow> ** <factor> 
<pow> -> (<expr>) | <id> 
<id>  -> A | B | C 

、オペレータは左結合されている生産が左再帰的である場合（オペレータが唯一の一部として発生する可能性があるためオペレータの左側の非終端）。同様に、右の連想演算子は、同じ理由で右回帰規則を有する。