冗長括弧のない算術式の明確な文法

Question

括弧が不要な算術式の明確な文法を探しています。たとえば、括弧はid+(id*id)では冗長ですが、(id+id)*idでは冗長ではありません。

Answer 1

「括弧が不要な算術式」の意味によります。これは、冗長括弧で式を受け付けますが、また、任意にネストされた括弧を受け入れる：

expr ::= factor 
expr ::= factor mul_div factor 

mul_div ::= '*' | '/' 

factor ::= term 
factor ::= term add_sub term 

add_sub ::= '+' | '-' 

term ::= NUMBER 
term ::= '(' expr ')' 

私はその数が署名した番号を認識するために管理してと仮定していますので、何の単項プラスまたはマイナスがそこにはありません。必要であれば、それをどう扱うかを考え出すことができます。必要に応じて変数などを追加することもできます。

不要なかっこを含む式を拒否する文法を意味する場合は、文脈自由文法ではないものを検索していると思います。

Answer 2

これは簡単に実行できます。括弧が必要になる唯一の時間は、乗算式の1つとしての合計式、または分割式の1つの第2ピースとしての式です。いずれの場合でも、括弧内のマテリアルに少なくとも1つの裸の演算子（括弧で囲まれていない）を強制することによって、括弧が冗長でないことを保証することができます。

私はあなたが入試や宿題の質問に答えるのを助けているかもしれないと思いますが、私はそれほど好きではありませんが、これを不可能と呼んだり、不可能かもしれないと言っている人は間違っていて、 。

次のような式を解析したい：

expr  ::= expr addsub term 
expr  ::= prodterm 
expr  ::= value 

sum  ::= expr addsub term 

addsub ::= '+' | '-' 

term  ::= prodterm 
term  ::= unit 

prodterm ::= term '*' unit 
prodterm ::= term '/' produnit 

unit  ::= '(' sum ')' 
unit  ::= value 

produnit ::= unit 
produnit ::= '(' prodterm ')' 

value  ::= '0-9'* 

唯一の価値は、それを囲む括弧を持つことはできません。単位は、乗算式の部分式です。 produnitsはあなたの部門表現にかっこの尾を許します。 （5）は（値）になります。これは不可能です。プロダユニットとユニットだけがカッコを持ち、カッコ内に算術演算子が必要です。 （値）は任意の式から派生することはできません。（（何か））は不可能です。なぜなら、produnitとunitだけが括弧を派生しているからです。密接に見ると、produnitは、かっこが派生した場合や、単位として解析する場合や括弧のない場合には、*やa /が必要です。ユニットには、+または - が必要です。またはカッコはありません。

（5 + 6）は（5 + 6）がユニットとしてしか解析できないため、失敗する可能性がありますが、孤独なプロードユニットの周りにかっこを入れる方法はありません。孤独なプロダユニットの周りの括弧内のユニットまたはプロユニット。私はあなたのために自分の選択を打ち破ります：5 *（6 * 7）は解析しません - 単位時間という意味ですが、（6 * 7）は単位ではありません少なくとも1つの合計を持つ式のまわりの値またはかっこでなければなりません。少なくとも1つの合計が発生すると、かっこは自明ではありません。一方、5 /（6 * 7）は5/6 * 7と全く同じではありません。最初は5/6/7、2番目は5 * 7/6です。しかし、5 /（6）は5/6と同じです - 単一の値はカッコ内では出現できません。同様に、5 /（6/7）は5/6/7と同じではなく、5/7/6と同じで、2/5は6/7と同じであるためです。言い換えれば、中に裸の演算子がある場合、分母の周りのかっこは決して無関係ではありません。

（5 + 6）+7も不可能です。なぜなら、合計の左辺（および右辺）は、厳密な値、合計の周りの括弧なしの和、または製品の周りの括弧のない製品です。

あなたは、これらが保持されていることを納得させることができ、それが明確であることを自分で確認することができます。指数演算子を含むように拡張したり、より高い優先順位の演算子またはより低い優先順位演算子（例えば、==または<）に一般化することによって、それを拡張して保持することを自分自身に示すことができます。

こちらがお役に立てば幸いです。