关于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 解析器（自上而下），上述语法将导致 和 上的左递归。
要解决此问题，您应该对 LL 解析器使用以下语法：

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