yacc中优先级和关联的概念是否可以分开
is it possible to separate the concept of precedence and association in yacc
我想在 yacc 中有一个关于优先级和结合性的清晰示例，但我发现自己在区分这两个概念时遇到了麻烦。
也许这是因为我将这两个概念与数学和数学运算相关联。这是我构建的两个旧示例：
Associativity (*) 用于指定要应用的关联类型（左、右、非关联....）
事实上
%left '+' '*'
指示plus和multiplication是左结合的。到目前为止，一切都很好。 （不完全是，但它服务于示例的目的）
优先级 (**) 用于让一个运算符优先于另一个运算符。
%left '+'
%left '*'
乘法的优先级高于加运算。
所以我们得到了 E+E*E
想要的解析操作
E+(E*E) in case of (**)
(E+E)*E in case of only (*) --> this is clearly wrong - but it's fine for the example
那么问题来了，我能不使用结合律的概念，把结合律和优先级清楚地分开吗？
即使是非关联性也意味着关联性知识......所以..如果可能的话，我怎么能单独谈论它们？
这一切都很混乱。
Associativity ... Is used to give precedence to one operator over another
没有。绝对不。关联性用于确定同一运算符的两个相邻实例的计算顺序。(E+E)+E 或 E+(E+E)。除指数运算外的所有算术运算符在数学中都是左结合的。
%left '+' '*'
这表示+和*都是左结合的并且具有相同的优先级，因为它们都在同一行。因此这是错误的。
can I separate clearly associativity from precedence without using the concept of associativity
对不起，这毫无意义。
没有。在解析器定义中，关联性只是优先算法中的一个小细节。
要理解这一点，重要的是要理解优先级在解析术语中的实际含义。
从左到右 shift-reduce parser 有一个 堆栈 和一个 输入流 。最初，堆栈是空的，输入流包含要解析的输入。 SR 解析器重复执行以下两个操作之一，直到堆栈仅包含起始符号且输入流为空（在这种情况下解析成功），或者两种操作都不可能（在这种情况下解析失败） :
- 减少右侧在堆栈顶部的产生式，方法是将右侧弹出堆栈并将左侧非 -终端；
- shift一个输入符号从输入入栈
只有当产生式的右侧位于堆栈顶部时才能进行归约，这是该框架的一个重要特征。
除非输入流耗尽，否则始终可以执行移位操作，但只有当堆栈顶部与某些产生式的右侧精确匹配时，才能执行缩减操作。
构建 SR 解析器的不同方法将涉及不同的机制来决定在任何给定的堆栈配置中采取哪种操作。一种这样的机制是优先算法。一些非常简单的语言只能通过优先算法进行SR解析。在其他情况下，它可以用作辅助决策算法，以解决歧义的语法规范；这是 yacc 派生的解析器生成器中优先级的用例。
为了使优先级起作用，在任何堆栈配置中最多只能执行一个归约操作，这意味着不能有两个产生式具有相同的右侧。 [注1]
鉴于最多有一种可能的缩减动作和最多一种可能的移位动作（因为给出了下一个输入符号，如果有的话），唯一的问题是决定是移位还是减少。优先算法涉及一个优先函数PREC(A→α,a) ⇒ { SHIFT, REDUCE }, 其参数是产生式 A→α和一个终端符号 a，映射到 SHIFT 或 REDUCE.
虽然优先级关系通常写成比较，但它不是普通的比较运算符，因为两个参数来自不同的域。它总是涉及生产和终端。
然而，在简单的情况下，可以使用数字比较来实现 PREC。为此，我们定义了两个函数，分别将产生式和终端映射到整数：f(A→α) 和 g(a)。我们用它们来计算 PREC:
PREC(A→α,a) ≡
减少 if f(A→α) > g(a)
SHIFT if f(A→α) < g(a)
[注2]
无论如何，给定堆栈配置的优先算法是：
识别产生P(=A→α)可能的减少操作，如果有的话。
如果只能进行移位或减少，那就去做吧。否则，如果减少和转移都是可能的，计算 PREC(P, input) 和reduce 使用 P 如果结果是 REDUCE；否则，shift input.
现在这可能看起来令人困惑，因为大多数对优先关系的描述都将它们描述为好像它们比较终端，而不是带有终端的产生式。那是因为 "name" 每个作品使用作品中的最后一个终端是正常的。通常，这是明确的，因为对生产右侧的限制：由于两个右侧必须不同，所以很可能所有生产右侧都有不同的终端符号。 [注3]
尽管该简写允许我们说，例如，“* 的优先级高于 +”，而不是有点麻烦 "the production E→E*E has precedence over the terminal +"，重要的是要记住后一种说法才是我们真正的意思。
优先级也适用于单个运算符。对于大多数运算符，我们更喜欢从左到右分组，因此 E-E-E 应该被解析为就好像它已写成 (E-E)-E。然而，一些运算符喜欢右边的幂组，这意味着 E**E**E 应该被解析为 E**(E**E)。使用 PREC 函数很容易定义；对于左分组运算符 ⊕，我们将有：
PREC(E→E⊕E, ⊕) ≡ 减少
而右分组运算符 ⊗ 会
PREC(E→E⊗E, ⊗) ≡ SHIFT
当我们使用 PREC 的实际参数时，这一点很清楚，但当我们使用 shorthand 符号时，它会变得混乱，这让我们试图说 ⊕ 有优先级高于 ⊕，而 ⊗ 的优先级低于 ⊗。为了避免歧义并让我们继续使用 shorthand，我们将 ⊕ 描述为 "left-associative" (%left)，将 ⊗ 描述为 "right-associative" (%right)。但实现只是普通优先算法的应用。
例如，考虑简单的表达式语言：
E → E + E
E → E * E
E → E ** E
E → id
这里我们期望 * 比 + 绑定更紧密，而 ** 绑定最紧;前两组在左边，而指数组在右边。为此，我们可以分配 f 和 g 函数，如下所示：
Production f(Production) Terminal g(Terminal)
E → E + E 2 + 1
E → E * E 4 * 3
E → E ** E 5 ** 6
E → id 8 id 7
Yacc 生成的文法不使用优先级来决定何时减少 E→id 的产生，但是上面的方法会起作用，因为仅使用优先级算法就可以完全解析文法。
可以轻松添加括号；我会把它留作练习。
注释
可能有一些其他机制来决定缩减操作，因此对于只使用优先级的解析器来说，限制只是绝对的。可能还有一些其他机制来限制可能的换挡动作。例如，为了使移位可行，堆栈顶部的标记最终需要减少，这意味着堆栈的某些后缀必须是某些产生式右侧的前缀。类似地，只有在 post-reduce，堆栈的某些后缀是某些产生式右侧的前缀时，减少才是可行的。
您会看到使用 < 和 ≥（或 ≤ 和 >）的公式，但为了避免混淆，我假设 f 的范围和 g 是不同的整数集。由于函数是任意的，因此不限制通用性。
情况并非总是如此。例如，允许 - 是一元运算符或二元运算符的语言将具有右侧的产生式 <b>-</b> E和E<b>-</b>E。 Yacc 派生的解析器生成器使用 %prec TERMINAL 声明将产生式与默认终端以外的终端相关联。
我想在 yacc 中有一个关于优先级和结合性的清晰示例，但我发现自己在区分这两个概念时遇到了麻烦。 也许这是因为我将这两个概念与数学和数学运算相关联。这是我构建的两个旧示例：
Associativity (*) 用于指定要应用的关联类型（左、右、非关联....） 事实上
%left '+' '*'
指示plus和multiplication是左结合的。到目前为止，一切都很好。 （不完全是，但它服务于示例的目的）
优先级 (**) 用于让一个运算符优先于另一个运算符。
%left '+'
%left '*'
乘法的优先级高于加运算。
所以我们得到了 E+E*E
E+(E*E) in case of (**)
(E+E)*E in case of only (*) --> this is clearly wrong - but it's fine for the example
那么问题来了，我能不使用结合律的概念，把结合律和优先级清楚地分开吗？ 即使是非关联性也意味着关联性知识......所以..如果可能的话，我怎么能单独谈论它们？
这一切都很混乱。
Associativity ... Is used to give precedence to one operator over another
没有。绝对不。关联性用于确定同一运算符的两个相邻实例的计算顺序。(E+E)+E 或 E+(E+E)。除指数运算外的所有算术运算符在数学中都是左结合的。
%left '+' '*'
这表示+和*都是左结合的并且具有相同的优先级，因为它们都在同一行。因此这是错误的。
can I separate clearly associativity from precedence without using the concept of associativity
对不起，这毫无意义。
没有。在解析器定义中，关联性只是优先算法中的一个小细节。
要理解这一点，重要的是要理解优先级在解析术语中的实际含义。
从左到右 shift-reduce parser 有一个 堆栈 和一个 输入流 。最初，堆栈是空的，输入流包含要解析的输入。 SR 解析器重复执行以下两个操作之一，直到堆栈仅包含起始符号且输入流为空（在这种情况下解析成功），或者两种操作都不可能（在这种情况下解析失败） :
- 减少右侧在堆栈顶部的产生式，方法是将右侧弹出堆栈并将左侧非 -终端；
- shift一个输入符号从输入入栈
只有当产生式的右侧位于堆栈顶部时才能进行归约，这是该框架的一个重要特征。
除非输入流耗尽，否则始终可以执行移位操作，但只有当堆栈顶部与某些产生式的右侧精确匹配时，才能执行缩减操作。
构建 SR 解析器的不同方法将涉及不同的机制来决定在任何给定的堆栈配置中采取哪种操作。一种这样的机制是优先算法。一些非常简单的语言只能通过优先算法进行SR解析。在其他情况下，它可以用作辅助决策算法，以解决歧义的语法规范；这是 yacc 派生的解析器生成器中优先级的用例。
为了使优先级起作用，在任何堆栈配置中最多只能执行一个归约操作，这意味着不能有两个产生式具有相同的右侧。 [注1]
鉴于最多有一种可能的缩减动作和最多一种可能的移位动作（因为给出了下一个输入符号，如果有的话），唯一的问题是决定是移位还是减少。优先算法涉及一个优先函数PREC(A→α,a) ⇒ { SHIFT, REDUCE }, 其参数是产生式 A→α和一个终端符号 a，映射到 SHIFT 或 REDUCE.
虽然优先级关系通常写成比较，但它不是普通的比较运算符，因为两个参数来自不同的域。它总是涉及生产和终端。
然而，在简单的情况下，可以使用数字比较来实现 PREC。为此，我们定义了两个函数，分别将产生式和终端映射到整数：f(A→α) 和 g(a)。我们用它们来计算 PREC:
PREC(A→α,a) ≡
减少 if f(A→α) > g(a)
SHIFT if f(A→α) < g(a)
[注2]
无论如何，给定堆栈配置的优先算法是：
识别产生P(=A→α)可能的减少操作，如果有的话。
如果只能进行移位或减少，那就去做吧。否则，如果减少和转移都是可能的，计算 PREC(P, input) 和reduce 使用 P 如果结果是 REDUCE；否则，shift input.
现在这可能看起来令人困惑，因为大多数对优先关系的描述都将它们描述为好像它们比较终端，而不是带有终端的产生式。那是因为 "name" 每个作品使用作品中的最后一个终端是正常的。通常，这是明确的，因为对生产右侧的限制：由于两个右侧必须不同，所以很可能所有生产右侧都有不同的终端符号。 [注3]
尽管该简写允许我们说，例如，“* 的优先级高于 +”，而不是有点麻烦 "the production E→E*E has precedence over the terminal +"，重要的是要记住后一种说法才是我们真正的意思。
优先级也适用于单个运算符。对于大多数运算符，我们更喜欢从左到右分组，因此 E-E-E 应该被解析为就好像它已写成 (E-E)-E。然而，一些运算符喜欢右边的幂组，这意味着 E**E**E 应该被解析为 E**(E**E)。使用 PREC 函数很容易定义；对于左分组运算符 ⊕，我们将有：
PREC(E→E⊕E, ⊕) ≡ 减少
而右分组运算符 ⊗ 会
PREC(E→E⊗E, ⊗) ≡ SHIFT
当我们使用 PREC 的实际参数时，这一点很清楚，但当我们使用 shorthand 符号时，它会变得混乱，这让我们试图说 ⊕ 有优先级高于 ⊕，而 ⊗ 的优先级低于 ⊗。为了避免歧义并让我们继续使用 shorthand，我们将 ⊕ 描述为 "left-associative" (%left)，将 ⊗ 描述为 "right-associative" (%right)。但实现只是普通优先算法的应用。
例如，考虑简单的表达式语言：
E → E + E
E → E * E
E → E ** E
E → id
这里我们期望 * 比 + 绑定更紧密，而 ** 绑定最紧;前两组在左边，而指数组在右边。为此，我们可以分配 f 和 g 函数，如下所示：
Production f(Production) Terminal g(Terminal)
E → E + E 2 + 1
E → E * E 4 * 3
E → E ** E 5 ** 6
E → id 8 id 7
Yacc 生成的文法不使用优先级来决定何时减少 E→id 的产生，但是上面的方法会起作用，因为仅使用优先级算法就可以完全解析文法。
可以轻松添加括号；我会把它留作练习。
注释
可能有一些其他机制来决定缩减操作，因此对于只使用优先级的解析器来说，限制只是绝对的。可能还有一些其他机制来限制可能的换挡动作。例如，为了使移位可行，堆栈顶部的标记最终需要减少，这意味着堆栈的某些后缀必须是某些产生式右侧的前缀。类似地，只有在 post-reduce，堆栈的某些后缀是某些产生式右侧的前缀时，减少才是可行的。
您会看到使用 < 和 ≥（或 ≤ 和 >）的公式，但为了避免混淆，我假设 f 的范围和 g 是不同的整数集。由于函数是任意的，因此不限制通用性。
情况并非总是如此。例如，允许 - 是一元运算符或二元运算符的语言将具有右侧的产生式
<b>-</b> E和E<b>-</b>E。 Yacc 派生的解析器生成器使用%prec TERMINAL声明将产生式与默认终端以外的终端相关联。