文法と優先順位の多くの説明では、演算子には優先順位があると言うショートカットを使用しているため、混乱しています。彼らはしません。優先されるのは文法のプロダクションであり、それらは他のプロダクションと比較して優先されます。文法があいまいな場合 (つまり、同じ入力に対して 2 つの異なる解析ツリーを生成できる場合)、および 1 つの生成の優先順位を他の生成よりも指定することによってあいまいさが解決される場合にのみ、2 つの生成が互いに対して優先順位を持つことは意味があります。 .
例を挙げて説明しましょう。
おもちゃの文法は次のとおりです。
expression =
| IDENTIFIER
| NUMBER
| expression '+' expression
| expression '*' expression
| expression '(' expression ')' // function call
| '(' expression ')' // grouping
| expression '[' expression ']' // array subscript
| '[' expression IDENTIFIER ':' expression ']' // message send
;
さて、1 + 2 * 3
この文法で構文解析することを考えてみましょう。2 つの有効な解析ツリーがあります。
+ *
/ \ / \
1 * + 3
/ \ / \
2 3 1 2
*
プロダクションがプロダクションよりも優先順位が高いことを指定することにより+
、パーサーは右のツリーではなく左のツリーを生成する必要があります。+
したがって、プロダクションとプロダクションの間の優先関係の考え方は*
理にかなっています。それは、パーサーの出力に影響を与えます。
同様に、1 + foo(3)
次の 2 つの解析ツリーがあります。
+ ()
/ \ / \
1 () + 3
/ \ / \
foo 3 1 foo
したがって、「+」生成と関数呼び出し生成の間の優先関係の考え方は理にかなっています。(関数呼び出し生成の代わりに添字生成を使用する)の場合1 + foo[3]
は類似しているため、「+」生成と添字生成の間の優先関係を指定することは理にかなっています。
を考えてみましょう1 + (2 * 3)
。文法は、可能な構文木を 1 つしか生成できません。
+
/ \
1 ( )
|
*
/ \
2 3
+
この入力を解析する方法は 1 つしかないため、プロダクションとグループ化プロダクションの間に優先関係は必要ありません。グループ化プロダクションがプロダクションよりも優先順位が高いと指定しても意味+
がありません。それによって作成できる構文木は他にないからです。
最後に、 を検討して1 + [2 add:3]
ください。これは、グループ化の例に似ています。考えられる構文木は 1 つだけです。
+
/ \
/ \
1 [ ]
/ | \
/ | \
2 add 3
他の解析ツリーはありえません。+
プロダクションとメッセージ送信プロダクションの優先関係を指定する必要はありません。それらの間の優先関係を指定しても効果はありません。これは、文法がこの入力を他の方法で解析することを許可していないためです。