context-free-grammar - 文脈自由文法では順序は重要ですか？

Question

次の文法があるとしましょう：

expr = expr + term | term    
term = term +  number | number    
number = (just any integers..)

私の質問は、expr = expr +term|です。exprと同じ項= term + expr | 用語？

文法を拡張しましたが、問題ないようです。私は正しいですか？

score 1 · Accepted Answer

いいえ、それらは同じではありません。順序が重要です。例については、http://en.wikipedia.org/wiki/Context-free_grammar#Exampleをご覧ください。

score 0 · Accepted Answer

もちろん、答えは文法に依存するということです。

あなたの場合、あるルールを別のルールに置き換えても、文法によって生成された言語の文字列のセットは変更されません。文法は異なりますが、言語は同じです。唯一の違いは、1 つ目は右から文字列を構築し、2 つ目は左から文字列を構築することです。

これがうまくいかない文法を考え出すのは難しくありません。時には、プロダクションで記号の順序を変更すると、言語が変わることがあります。

2 に答える 2