Bison shift 减少逗号冲突
Bison shift reduce conflict on comma
无论我更改什么，我都会收到奇怪的 shift-reduce 警告。简化语法：
expr : NUMBER
| NUMBER ',' expr
| expr ',' NUMBER ',' NUMBER
Bison 报告第 2 条带逗号的规则减少。我尝试设置优先级：
%nonassoc num_p
%nonassoc exp_p
expr : NUMBER %prec num_p
| NUMBER ',' expr %prec exp_p
| expr ',' NUMBER ',' NUMBER
但警告保持不变。有人可以解释一下我在这里错过了什么吗？
有时将左递归重写为右递归会有所帮助，如下所示：
expr : NUMBER
| expr ',' NUMBER
;
那里可以找到理论依据：https://cs.stackexchange.com/questions/9963/why-is-left-recursion-bad
很明显下面是有歧义的：
expr : NUMBER %prec num_p
| NUMBER ',' expr %prec exp_p
| expr ',' NUMBER ',' NUMBER
因为任何包含三个或更多数字的列表都可以通过多种方式进行解析。粗略地说，我们可以从列表的开头删除单个数字，或者从列表的末尾删除一对数字，直到我们在中间的某个地方相遇；但是，没有定义中间点的位置。
例如，考虑可以产生 1, 2, 3, 4, 5 的各种解析树。这里只有两个（数字表示哪个产品用于扩展 expr）：
expr(2) expr(3)
/ \ / | \
/ \ / | |
| expr(2) / | |
| / \ / | |
| / \ expr(3) | |
| / expr(3) / | \ | |
| | / | \ / | \ | |
| |expr(1)| \ expr(1)| | | |
| | | | | | | | | |
1 , 2 , 3 , 4 , 5 1 , 2 , 3 , 4 , 5
从某种意义上说，以上两棵树都是最大的。左边的那个使用产生式 2 获取尽可能多的单个 NUMBER，直到只剩下两个 NUMBER 用于产生式 3。右边的一个尽可能多地应用产生式 3。 （如果数字列表的长度是偶数，则需要一次应用产生式 2。）
为了解决歧义，我们需要一个明确的意图声明。但在我看来，它不太可能通过优先声明来解决。请记住，优先级关系始终在 可能的缩减 （在解析器堆栈的顶部）和 前瞻符号 之间。他们从不比较两个前瞻符号或两个产品。如果先行符号获胜，则将其移入堆栈；如果减少获胜，则减少堆栈。没有比这更复杂的了。
因此，如果优先级有帮助，相关标记必须是 ','，而不是 NUMBER。 NUMBER 必须始终移入解析堆栈。由于没有生产以 ',' 结束，所以当 NUMBER 是先行符号时，永远不可能减少堆栈。相比之下，当 ',' 是先行符号时，通常可以减少解析器堆栈的顶部或移动 ',' 以准备不同的减少。
唯一可能做出此决定的地方是在我们已经看到 NUMBER 并且正在查看 ',' 的情况下，因此我们必须决定是否应用产生式 1，在准备生产 3，或转移 ','，留下生产 2 作为唯一的选择。这两个决定都不会成功：如果我们选择减少，那么生产 3 可能会变得不可能，因为列表中的数量不够；如果我们选择转移，那么生产 3 将永远不会被使用。
在从左到右的解析中，生成上述右手解析的算法是不可能的，因为在到达末尾之前我们无法知道列表的长度是偶数还是奇数，此时追溯减少前两个数字已经太晚了。另一方面，左手解析需要向前看四个标记，而不是一个标记，以便决定在哪一点停止使用产生式 2。这使得构建 LR(1) 文法成为可能，因为有一种将任何 LR(k) 文法重写为 LR(1) 文法的方法，但生成的文法通常很复杂。
我怀疑这些都不是你的本意。为了推荐一项决议，有必要知道确切的意图是什么。
一种可能性（由评论引起）是 expr 还包括一些既不是数字也不是数字列表的东西：
expr: NUMBER
| complex_expression
在那种情况下，语法可能打算捕获两种可能性：
包含 NUMBER 的列表，末尾可能有 complex_expression；
包含偶数个 NUMBER 的列表，开头可能有 complex_expression。
在上面的公式中留下歧义的是一个仅由 NUMBER 组成的列表，因为第一个或最后一个数字都可以解析为 expr。这里只有几个合理的可能解决方案：
NUMBER 的列表总是被解析为第一个选项（expr 在末尾）
当且仅当列表中的元素数量为奇数时，NUMBER 的列表才被解析为第二个选项（expr 开头）。
第一个解决方案比较容易，所以我们可以从它开始。在这种情况下，列表中的第一个元素基本上决定了列表将如何被解析，因此不可能将 first NUMBER 减少到 expr。我们可以通过分隔不同类型的 expr:
来表示
expr: list_starting_expr | list_ending_expr
list_starting_expr: complex_expression ',' NUMBER ',' NUMBER
| list_start_expr ',' NUMBER ',' NUMBER
list_ending_expr : complex_expression
| NUMBER ',' list_ending_expr
| NUMBER
上例中的最后一个产生式允许将完全包含 NUMBER 的列表解析为 list_ending_expr。
它还允许将仅包含单个 complex_expression 的列表解析为 list_ending_expr，而 list_starting_expr 需要至少包含三个元素。否则，仅由 complex_expression 组成的列表将是不明确的。在问题的示例语法中，隐式禁止仅包含 complex_expression 的列表；可以通过将 list_ending_expr 的基础生产从 list_ending_expr: complex_expression 更改为 list_ending_expr: NUMBER ',' complex_expression.
来重现
但是如果我们想要第二个分辨率怎么办？我们仍然可以识别该语言，但构建正确的解析树可能需要一些手术。我们可以从分离列表仅包含 NUMBERs.
的情况开始
expr: list_starting_expr | list_ending_expr | ambiguous_list
list_starting_expr: complex_expression ',' NUMBER ',' NUMBER
| list_starting_expr ',' NUMBER ',' NUMBER
list_ending_expr : NUMBER ',' complex_expression
| NUMBER ',' list_ending_expr
ambiguous_list : NUMBER
| NUMBER ',' ambiguous_list
尽管经常重复声称在自底向上文法中应避免右递归，但这里 ambiguous_list 和 list_ending_expr 必须是右递归的，因为我们无法区分两种可能性，直到我们到达列表的末尾。
现在我们可以使用语义操作来简单地计算列表中元素的数量。该操作需要与 ambiguous_list 减少到 expr:
相关联
expr: list_starting_expr | list_ending_expr
| ambiguous_list {
if (count_elements() % 2 == 1) {
$$ = make_list_starting_expr();
}
else {
$$ = make_list_starting_expr();
}
}
但我们实际上可以在语法上区分这两种情况，正是因为正确的递归：
expr: list_starting_expr
| list_ending_expr
| even_list_of_numbers
| odd_list_of_numbers
list_starting_expr : complex_expression ',' NUMBER ',' NUMBER
| list_starting_expr ',' NUMBER ',' NUMBER
list_ending_expr : NUMBER ',' complex_expression
| NUMBER ',' list_ending_expr
odd_list_of_numbers : NUMBER
| NUMBER ',' NUMBER ',' odd_list_of_numbers
even_list_of_numbers: NUMBER ',' NUMBER
| NUMBER ',' NUMBER ',' even_list_of_numbers
这样写可能更有意义：
expr: expr_type_one | expr_type_two
expr_type_one: list_starting_expr | even_list_of_numbers
expr_type_two: list_ending_expr | odd_list_of_numbers
/* Remainder as above */
注： 上面的文法和原题中的文法一样，不允许expr只包含的 complex_expression。如果只希望处理单个 complex_expression 的情况，那么可以将该语法直接添加到 expr 的产生式（或 expr_type_one 或 [=64= 中的任何一个） ] 是合适的。
无论我更改什么，我都会收到奇怪的 shift-reduce 警告。简化语法：
expr : NUMBER
| NUMBER ',' expr
| expr ',' NUMBER ',' NUMBER
Bison 报告第 2 条带逗号的规则减少。我尝试设置优先级：
%nonassoc num_p
%nonassoc exp_p
expr : NUMBER %prec num_p
| NUMBER ',' expr %prec exp_p
| expr ',' NUMBER ',' NUMBER
但警告保持不变。有人可以解释一下我在这里错过了什么吗？
有时将左递归重写为右递归会有所帮助，如下所示：
expr : NUMBER
| expr ',' NUMBER
;
那里可以找到理论依据：https://cs.stackexchange.com/questions/9963/why-is-left-recursion-bad
很明显下面是有歧义的：
expr : NUMBER %prec num_p
| NUMBER ',' expr %prec exp_p
| expr ',' NUMBER ',' NUMBER
因为任何包含三个或更多数字的列表都可以通过多种方式进行解析。粗略地说，我们可以从列表的开头删除单个数字，或者从列表的末尾删除一对数字，直到我们在中间的某个地方相遇；但是，没有定义中间点的位置。
例如，考虑可以产生 1, 2, 3, 4, 5 的各种解析树。这里只有两个（数字表示哪个产品用于扩展 expr）：
expr(2) expr(3)
/ \ / | \
/ \ / | |
| expr(2) / | |
| / \ / | |
| / \ expr(3) | |
| / expr(3) / | \ | |
| | / | \ / | \ | |
| |expr(1)| \ expr(1)| | | |
| | | | | | | | | |
1 , 2 , 3 , 4 , 5 1 , 2 , 3 , 4 , 5
从某种意义上说，以上两棵树都是最大的。左边的那个使用产生式 2 获取尽可能多的单个 NUMBER，直到只剩下两个 NUMBER 用于产生式 3。右边的一个尽可能多地应用产生式 3。 （如果数字列表的长度是偶数，则需要一次应用产生式 2。）
为了解决歧义，我们需要一个明确的意图声明。但在我看来，它不太可能通过优先声明来解决。请记住，优先级关系始终在 可能的缩减 （在解析器堆栈的顶部）和 前瞻符号 之间。他们从不比较两个前瞻符号或两个产品。如果先行符号获胜，则将其移入堆栈；如果减少获胜，则减少堆栈。没有比这更复杂的了。
因此，如果优先级有帮助，相关标记必须是 ','，而不是 NUMBER。 NUMBER 必须始终移入解析堆栈。由于没有生产以 ',' 结束，所以当 NUMBER 是先行符号时，永远不可能减少堆栈。相比之下，当 ',' 是先行符号时，通常可以减少解析器堆栈的顶部或移动 ',' 以准备不同的减少。
唯一可能做出此决定的地方是在我们已经看到 NUMBER 并且正在查看 ',' 的情况下，因此我们必须决定是否应用产生式 1，在准备生产 3，或转移 ','，留下生产 2 作为唯一的选择。这两个决定都不会成功：如果我们选择减少，那么生产 3 可能会变得不可能，因为列表中的数量不够；如果我们选择转移，那么生产 3 将永远不会被使用。
在从左到右的解析中，生成上述右手解析的算法是不可能的，因为在到达末尾之前我们无法知道列表的长度是偶数还是奇数，此时追溯减少前两个数字已经太晚了。另一方面，左手解析需要向前看四个标记，而不是一个标记，以便决定在哪一点停止使用产生式 2。这使得构建 LR(1) 文法成为可能，因为有一种将任何 LR(k) 文法重写为 LR(1) 文法的方法，但生成的文法通常很复杂。
我怀疑这些都不是你的本意。为了推荐一项决议，有必要知道确切的意图是什么。
一种可能性（由评论引起）是 expr 还包括一些既不是数字也不是数字列表的东西：
expr: NUMBER
| complex_expression
在那种情况下，语法可能打算捕获两种可能性：
包含
NUMBER的列表，末尾可能有complex_expression；包含偶数个
NUMBER的列表，开头可能有complex_expression。
在上面的公式中留下歧义的是一个仅由 NUMBER 组成的列表，因为第一个或最后一个数字都可以解析为 expr。这里只有几个合理的可能解决方案：
NUMBER的列表总是被解析为第一个选项（expr在末尾）当且仅当列表中的元素数量为奇数时，
NUMBER的列表才被解析为第二个选项（expr开头）。
第一个解决方案比较容易，所以我们可以从它开始。在这种情况下，列表中的第一个元素基本上决定了列表将如何被解析，因此不可能将 first NUMBER 减少到 expr。我们可以通过分隔不同类型的 expr:
expr: list_starting_expr | list_ending_expr
list_starting_expr: complex_expression ',' NUMBER ',' NUMBER
| list_start_expr ',' NUMBER ',' NUMBER
list_ending_expr : complex_expression
| NUMBER ',' list_ending_expr
| NUMBER
上例中的最后一个产生式允许将完全包含 NUMBER 的列表解析为 list_ending_expr。
它还允许将仅包含单个 complex_expression 的列表解析为 list_ending_expr，而 list_starting_expr 需要至少包含三个元素。否则，仅由 complex_expression 组成的列表将是不明确的。在问题的示例语法中，隐式禁止仅包含 complex_expression 的列表；可以通过将 list_ending_expr 的基础生产从 list_ending_expr: complex_expression 更改为 list_ending_expr: NUMBER ',' complex_expression.
但是如果我们想要第二个分辨率怎么办？我们仍然可以识别该语言，但构建正确的解析树可能需要一些手术。我们可以从分离列表仅包含 NUMBERs.
expr: list_starting_expr | list_ending_expr | ambiguous_list
list_starting_expr: complex_expression ',' NUMBER ',' NUMBER
| list_starting_expr ',' NUMBER ',' NUMBER
list_ending_expr : NUMBER ',' complex_expression
| NUMBER ',' list_ending_expr
ambiguous_list : NUMBER
| NUMBER ',' ambiguous_list
尽管经常重复声称在自底向上文法中应避免右递归，但这里 ambiguous_list 和 list_ending_expr 必须是右递归的，因为我们无法区分两种可能性，直到我们到达列表的末尾。
现在我们可以使用语义操作来简单地计算列表中元素的数量。该操作需要与 ambiguous_list 减少到 expr:
expr: list_starting_expr | list_ending_expr
| ambiguous_list {
if (count_elements() % 2 == 1) {
$$ = make_list_starting_expr();
}
else {
$$ = make_list_starting_expr();
}
}
但我们实际上可以在语法上区分这两种情况，正是因为正确的递归：
expr: list_starting_expr
| list_ending_expr
| even_list_of_numbers
| odd_list_of_numbers
list_starting_expr : complex_expression ',' NUMBER ',' NUMBER
| list_starting_expr ',' NUMBER ',' NUMBER
list_ending_expr : NUMBER ',' complex_expression
| NUMBER ',' list_ending_expr
odd_list_of_numbers : NUMBER
| NUMBER ',' NUMBER ',' odd_list_of_numbers
even_list_of_numbers: NUMBER ',' NUMBER
| NUMBER ',' NUMBER ',' even_list_of_numbers
这样写可能更有意义：
expr: expr_type_one | expr_type_two
expr_type_one: list_starting_expr | even_list_of_numbers
expr_type_two: list_ending_expr | odd_list_of_numbers
/* Remainder as above */
注： 上面的文法和原题中的文法一样，不允许expr只包含的 complex_expression。如果只希望处理单个 complex_expression 的情况，那么可以将该语法直接添加到 expr 的产生式（或 expr_type_one 或 [=64= 中的任何一个） ] 是合适的。