BNF 文法中运算符的优先级

Question

我正在做家庭作业，我要讲一些 BNF 语法：

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

问题是：

"Rewrite this grammar so that the + operator is right associative and takes precedence over the * operator."

一位同学建议我们简单地切换 + 和 * 运算符，然后 + 将具有优先权并获得正确的关联，但是我认为这是不正确的，因为问题是递归的。

我的问题是，+ 运算符是否通过简单地与 * 运算符切换来获得优先级和正确的关联？我的两个想法是删除递归并按照我同学的建议进行操作，或者将 + 运算符置于必须被 ( 和 ) 包围的条件下才能工作。

也许我想多了？

Answer 1

在语法中交换 + 和 * 将清楚地交换优先级，但使它们右结合是一个单独的步骤，所以这很容易。

但是，对于左右结合性，我无法理解你的建议，但它们似乎都是错误的。

如果我们采用示例输入 A = A + B + C，那么您的语法会像这样解析它：

assign: <id> = <expr>
    id: A
    expr: <expr> + <term>
        expr: <expr> + <term>
            expr: <expr> + <term>
                expr: <term>
                term: <factor>
                    factor: <id>
                         id: A
            term: <factor>
                factor: <id>
                    id: B
        term: <factor>
            factor: <id>
                id: C

或者，如果您更喜欢括号格式的相同内容：

(A) = ((((A))+(B))+(C))

请注意，最里面的第一个求值 + 是距离左边最远的那个。因此，您的语法具有左结合性。您需要更改 expr 和 term 以便第一个评估的是最远的 right 语法具有正确的关联性。括号提供了一种 "overrule" 语法具有的任何关联性的方法，但除此之外与关联性并不真正相关。

BNF 文法中运算符的优先级

Precedence of operators in BNF grammar

syntax

bnf

operator-precedence