0

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

4

2 に答える 2

4

これは簡単にできます。括弧が必要になるのは、乗算式の一部として合計式がある場合、または除算式の 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) は ( value ) になりますが、これは不可能です。なぜなら、produnit と unit のみに括弧があり、それらが存在する場合は算術演算子を括弧内に配置する必要があるためです。( value ) はどの式からも導出できず、 ( ( anything ) ) は不可能です。これは、produnit と unit のみが括弧を導出するためです。よく見ると、produnit では、括弧が派生する場合、または単位として解析する場合、または括弧なしの値の場合に * または / が発生する必要があります。unit には + または - を付けるか、括弧を付けないでください。

( ( 5 + 6 ) ) は、 ( 5 + 6 ) がユニットとしてしか解析できないため失敗します。これは、それを製品ユニットにする可能性がありますが、単一の製品ユニットを括弧で囲む方法はありません。ユニットまたはprodunit を単独の produnit を括弧で囲みます。

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 も不可能です。これは、合計の左辺 (および右辺) が厳密な値、合計の周りに括弧のない合計、または積の周りの括弧のない積のいずれかであるためです。曲がるわけがない

これらが成り立つことを自分自身に納得させ、それが明白であることを自分自身で確認できます。指数演算子を含めるように拡張するか、== や < などの優先順位の高い演算子または優先順位の低い演算子に一般化することで、それが成り立つことを自分自身に示すことができます。

これが役立つことを願っています！

于 2013-02-20T17:03:19.510 に答える
2

それは、「冗長な括弧のない算術式の場合」の意味に正確に依存します。これは冗長な括弧のない式を受け入れますが、任意にネストされた括弧も受け入れます:

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

mul_div ::= '*' | '/'

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

add_sub ::= '+' | '-'

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

NUMBER は符号付きの数値を認識できると想定しているため、単項プラスまたはマイナスはありません。必要に応じて、それらの処理方法を検討できます。必要に応じて変数などを追加することもできます。

不要な括弧を含む表現を拒否する文法を意味する場合、文脈自由文法ではない何かを探していると思います。

于 2011-01-08T05:21:10.530 に答える