0

例如 ：

waldo:=fern+alpha/-beta^gamma;

上面的算术表达式可以被这个 BNF 抽象出来（可能与标准 BNF 有一些不同，但我们暂时忽略它）：

AEXP = AS $AS ;

AS = .ID ':=' EX1 ';' ;

EX1 = EX2 $( '+' EX2 / '-' EX2 ) ;

EX2 = EX3 $( '*' EX3 / '/' EX3 ) ;

EX3 = EX4 $( '^' EX3 ) ;

EX4 = '+' EX5 / '-' EX5 / EX5 ;

EX5 = .ID / .NUMBER / '(' EX1 ')' ;

.END

但是EX1~EX5抽象对我来说并不是那么直观。（我不太了解它们是如何制作的）

规范化此类表达式时是否有任何步骤可遵循？

4

1 回答 1

1

您可以直接将此表示法转换为 EBNF。

命名类别 EX1 到 EX5 并不是指定运算符优先级的常见方式。事实上，恕我直言，这是一个很好的选择，尤其是在某些具有 15 个或更多优先级的语言中，例如 C 和 C++。:)

您可以将它们重命名为表达式、术语、因子、主要等（或任何对您有意义的术语）。

附录

如果您需要将上述内容翻译成更传统的 EBNF，我会这样做：

AEXP => AS+
AS   => id ':=' EX1 ';'
EX1  => EX2 (('+' | '-') EX2)*
EX2  => EX3 (('*' | '/') EX3)*
EX3  => EX4 ('^' EX3)*
EX4  => ('+'|'-')? EX5
EX5  => id | number | '(' EX1 ')'

我用“*”表示零个或多个，“+”表示一个或多个，以及“？” 可选。我认为这里处理运算符优先级的方式非常酷。

附录 2：

请注意：EX3 的规则似乎是错误的。它现在的方式你可以得到这样的解析树

                  EX3
                   |
     +---+----+----+----+---------+
     |   |    |    |    |    |    |
    EX4  ^   EX3   ^   EX3   ^   EX3
            / | \               / | \
         EX4  ^  EX3         EX4  ^  EX3

所以写作a^b^c^d^e^f可能意味着a^(b^c)^d^(e^f)。但实际上还有其他方法可以制作这棵树。语法模棱两可。

语法的设计者似乎想让^运算符右结合。但要这样做，规则应该是

EX3 => EX4 ('^' EX3)?

现在语法不再模棱两可了。看看a^b^c^d^e^f现在 MUST 的推导如何进行：

          EX3
         / | \
      EX4  ^  EX3
             / | \
          EX4  ^  EX3
                 / | \
              EX4  ^  EX3
                     / | \
                  EX4  ^  EX3
                         / | \
                      EX4  ^  EX3

现在a^b^c^d^e^f只能解析为a^(b^(c^(d^(e^f))))

另一种方法是将规则重写为EX3 => EX4 ('^' EX4)*并有一条边规则说“OBTW 插入符号是右结合的”。

于 2011-07-24T05:53:57.697 回答