如何将某些表达式抽象为 BNF？

Question

例如：

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抽象对我来说不是那么直观。（我不太明白它们是如何制作的）

规范化此类表达式时有什么步骤要遵循吗？

Answer 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 的推导现在必须如何进行：

          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 插入符号是右关联的”。