0

我正在寻找一种没有多余括号的算术表达式的明确语法。例如，括号在 中是多余的id+(id*id)，但在 中不是(id+id)*id。

4

2 回答 2

4

你可以很容易地做到这一点。唯一需要括号的时候是当有一个求和表达式作为乘法表达式的一部分，或者某个表达式作为除法表达式的第二部分时。在任何一种情况下，您都可以通过强制括号内的材料至少有一个裸运算符（不被更多括号包围）来确保括号不是多余的。

我想我可能会帮助你回答入学考试或家庭作业的问题，我不太喜欢，但每个人都说这是不可能的或暗示这可能是不可能的都是错误的，我想把它们弄清楚。

您想这样解析表达式：

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 )，这是不可能的，因为只有 produnits 和 units 有括号，并且如果括号存在，它们需要一些算术运算符出现在括号内。( value ) 不能从任何表达式派生，并且 ( (anything) ) 是不可能的，因为只有 produnit 和 unit 派生括号。仔细观察，如果派生括号，produnit 需要出现 * 或 / ，或者将其解析为单位或不带括号的值。unit 需要一个 + 或一个 - 出现，或者没有括号。

( ( 5 + 6 ) ) 失败，因为 ( 5 + 6 ) 只能解析为一个单元，这可以使它成为一个产品单元，但是没有办法在一个单独的产品单元周围加上括号 - 没有链可以转动一个单元或一个produnit 放在一个单独的 produnit 周围的括号中。

我将为您分解我的选择： 5*(6*7) 不解析-您会认为这是一个术语乘以一个单位，但是 (6*7) 不是一个单位，因为单位必须是值或带有至少一个总和的表达式周围的括号。一旦出现至少一个总和，括号就不是微不足道的。另一方面，5/(6*7) 与 5/6*7 完全不同——第一个类似于 5/6/7，第二个类似于 5*7/6。但是，5/(6) 与 5/6 是一样的——单个值不能出现在括号内。同样，5/(6/7) 与 5/6/7 不同，因为第一个与 5*7/6 相同，第二个与 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 回答