yacc运算符关联性声明对只有几个标记的表达式的影响

Question

当你有这样的语法时：

B:  'a' A 'a'
|   'b' A 'b'
A:  'a' 'a'
|   'a'

%right"a"声明导致不接受aa.a，因为在"."处发生了移位而不是减少，%left'a'既不接受aa.aa也不接受ba.ab，因为解析总是在点处减少。

我不太清楚如何弄清楚在标记('a')没有直接用作运算符的情况下，关联性声明会产生什么影响。

Answer 1

为什么你认为LR(1)会更直观？语法不是LR(1)，所以任何LR(1"语法分析器生成器都应该报告移位/减少冲突，就像LALR(1)语法分析器生成器一样。

当然，yacc/bison并不是一个纯粹的LALR(1)解析器生成器。如果它使用优先级/关联性声明来解决移位/减少冲突，则会抑制警告。不过，这并不能使语法变得明确。使用优先级声明的(许多)问题之一是，您解析的语言不再清晰。静默地忽略shift/reduce并静态地解析它以支持一个或另一个操作将生成一个解析器，该解析器可以识别某些上下文无关的语言，但它不是语法所描述的语言。

不过，这些都与LALR算法无关。

---

要回答您的问题：bison/yacc用于解决偏移/减少冲突的算法非常简单。

1. 优先级声明中提到的每个终端都被分配了一个优先级值。同一声明中提及的所有端子具有相同的优先级，并且优先级高于前一声明中提到的任何端子。

2. 最后一个终端具有优先级值的每个产品都被分配相同的优先级值。(如果生产包含%prec TERMINAL修饰符，则使用该端子而不是生产中的最后一个端子。

3. 如果具有某个先行符号的生产存在移位-减少冲突，并且生产和先行符号都具有优先级值，则如果生产的优先级更高，或者优先级相等，并且优先级由%left声明指定，则应用减少。如果先行符号的优先级较高，或者优先级相等并且优先级由%right声明指定，则应用移位。

就是这样。注意，在上面的算法中，没有提到运算符，这实际上不是任何形式的LR解析中的概念。