programming-languages - 关于BNF的问题

Question

我有这个用 BNF 写的语法。如何将其转换为 + 优先于 * 并强制 + 正确关联？

<assign> -> id = <expr>
<id>     -> A | B | C
<expr>   -> <expr> + term | <term>
<term>   -> <term> * <factor> | <factor>
<factor> -> ( <expr> ) | <id>

这是我的解决方案：

<assign> -> id = <expr>
<id>     -> A | B | C
<expr>   -> <expr> * term | <term>
<term>   -> <term> + <factor> | <factor>
<factor> -> ( <expr> ) | <id>

如何检查给定语法的正确性？任何的想法？
谢谢，

Answer 1

看起来很奇怪，您想恢复乘法的优先级而不是加法，但无论如何，如果您需要这种语法，那么正确的 BNF 将是（您在第三个产生式上打错了字）

<assign> -> id = <expr>
<id>     -> A | B | C
<expr>   -> <expr> * <term> | <term>
<term>   -> <term> + <factor> | <factor>
<factor> -> ( <expr> ) | <id>

这适用于 LR 解析器（自下而上）。

对于 LL 解析器（自上而下），上述文法将导致<expr>和上的左递归<term>。要解决此问题，您应该为 LL 解析器使用此语法：

<assign> -> id = <expr>
<id>     -> A | B | C
<expr>   -> <term> * <expr> | <term>
<term>   -> <factor> + <term> | <factor>
<factor> -> ( <expr> ) | <id>