6 
E -> E+T | E-T | T
T -> T*F | T/F | F
F -> i | (E)

如何修改此语法以允许求幂运算^以便我可以编写i+i^i*i？既然我们知道操作顺序更高，^那么我所知道的就是我必须使它具有正确的关联性。

4

3 回答 3

7

在 EBNF（扩展巴科斯-瑙尔形式）中，这可能如下所示：

expr -> term [ ('+' | '-') term ]*
term -> factor [ ('*' | '/') factor ]*
factor -> base [ '^' exponent ]*
base -> '(' expr ')' | identifier | number
exponent -> '(' expr ')' | identifier | number

（取自这里）

翻译成您的符号（数字和标识符之间没有区别）：

E -> E+T | E-T | T
T -> T*F | T/F | F
F -> F^X | B
B -> i | (E)
X -> i | (E)

为了清楚起见，可以合并“B”和“X”。

于 2013-06-18T13:55:10.497 回答
6

这里提供的两个答案都是错误的。在这些答案中 ^ 关联到左侧，而实际上它应该关联到右侧。正确的修改语法应该是：

  E -> E+T | E-T | T
  T -> T*X | T/X | X
  X -> F^X | F //Note: it's F^X not X^F
  F -> i | (E)

通过这种方式，您的语法可以使用如下表达式按预期工作：

a+b^c^d^e*f

谢谢！

于 2015-04-05T21:05:05.623 回答
3

对称如下。 

E -> E + T | E - T | T
T -> T * F | T / F | X
X -> X ^ Y | Y
Y -> i | (E)

解释：
==========
注意这个语法是明确的。要生成由运算符^, *, /, +,组成的表达式-，首先我们需要开始编写步骤，在这些步骤中+，-可以在较高优先级运算符之前添加低优先级运算符，即*, /。然后^可以在末尾添加目标表达式。因此，在抽象语法树（解析树）中，运算符^ 将出现在底部（朝向叶子）。这样，如果我们根据树评估该表达式，^将首先执行。

注意：根据语法规则，在情感形式中X -> O ^ Y我们不能回去添加+，-..，但是如果您有任何情感形式，E+T | E-T | T那么我们可以进一步添加其他运算符。所以在这种语法形式中，我们可以控制任何有效表达式（字符串）的生成流程属于语法语言。（这是如何控制运算符优先级的明确性）。

例如要生成表达式i + i ^ i * i，我们不能像E --> T --> X ---> X ^ Y，因为一旦有了X ^ Y就不能添加+, -（没有括号(E)）。

生成表达式的可能选择i + i ^ i * i如下：

E --> E - T --> E + T - T --> E + X - T --> E + X ^ Y - T --*--> i+i^i*i

`--*-->` means more than one step

注意运算符^是在最后一步添加的（因此可以出现在树的底部，如下图所示）：

树将类似于：

                     E 
                   / | \ 
                  /  |  \
                 E   -   T    <--  - evaluates 3rd 
               / | \     '
              /  |  \    '
             E   +   T   i    <--  + evaluates 2nd 
             '       |    
             '       |
             i       X 
                   / | \
                  /  |  \ 
                 X   ^   Y     <--  ^ evaluates first 
                 '       '
                 '       '
                 i       i
    NOTE:

    in tree  '  means more than one steps 
             '
    ^ has higher precedence 

    because of Left to right associativity + evaluated before then -

当您开始评估这棵树时，^将首先评估。

请记住，高优先级运算符始终添加在底部，因此，语法应该使得运算符可以稍后添加（在句子合成中）。

（你应该明白为什么在你的语法+中-可以直接生成 viaE和 viaT你可以添加*，/。为什么其他明确的版本E -> E*T | E/T | T，T -> T+F | T-F | X是不正确的！因为这个语法生成的语言和你的语法是等价的。原因是你的语法生成正确从尊重的评估点看树）

此外，如果您正在使用 YACC 工具编写解析器。您可以使用具有较少生产规则的该语法的模棱两可版本，并在语法规则之外指定运算符优先级（这将大致了解首先评估哪个运算符，因此应该如何构建树）。这将比这种明确的形式更可取，因为更少的生产规则在高处构建更小的树（因此高效的编译器 - 解析时间更少）。

于 2013-06-18T13:55:25.687 回答