BNF 文法中运算符的优先级 [英] Precedence of operators in BNF grammar

问题描述

我正在做一个家庭作业，其中我给出了一些 BNF 语法:

I'm doing a homework assignment where I am give some BNF grammar:

<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."

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

A classmate suggested we simply switch the + and * operators and then + will have precedence and gain right association, however I don't think this is correct since the question is recursive.

我的问题是，+ 运算符是否通过简单地将其与 * 运算符切换来获得优先级和正确关联?我的两个想法是去掉递归，按照同学的建议去做，或者把+运算符放在必须用(和)<包围的条件下/code> 工作.

My question is, does the + operator gain precedence and right association by simply switching it with the * operator? My two thoughts are to remove the recursion and do what my classmate suggests, or put the + operator in a condition where is must be surrounded by ( and ) to work.

也许我想多了?

推荐答案

在语法中交换 + 和 * 显然会交换优先级，但使它们右结合是一个单独的步骤，所以很容易.

Swapping + and * in the grammar will clearly swap the precedence, but making them right-associative is a separate step, so that's easy.

但是，对于右与左关联性，我无法理解您的建议，但它们似乎都是错误的.

However, for Right-vs-Left associativity, I'm having trouble understanding your suggestions, but both of them seem wrong.

如果我们采用样本输入 A = A + B + C，那么你的语法会像这样解析它:

If we take the sample input A = A + B + C, then your grammar parses it like this:

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

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

Or, if you prefer the same thing in a parenthetical format:

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

请注意，最里面并因此首先计算的 + 是距离 左侧 最远的那个.因此，您的语法具有左结合性.您需要更改 expr 和 term 以便评估的第一个是距离 right 最远的那个，以使语法具有右结合性.括号提供了一种否决"语法所具有的任何结合性的方法，但除此之外与结合性并没有真正相关.

Notice that the innermost and thus first evaluated + is the one farthest to the left. Thus, your grammar has Left associativity. You need to change expr and term so that the first one evaluated is the one farthest to the right for the grammar to have right associativity. Parenthesis provide a way to "overrule" of whatever the associativity the grammar has, but otherwise aren't really related to the associativity.

这篇关于BNF 文法中运算符的优先级的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！