Bison 无法解决 shift-reduce 和 reduce-reduce 的冲突
Bison can't solve conflicts shift-reduce and reduce-reduce
我正在使用 Bison 编写解析器，但似乎无法获得正确的语法。
有两个冲突：
以下是围绕冲突一使用的一些规则：
program : function END_OF_FILE {return 0;}
formal_parameters : OPEN_PAREN formal_parameter list_E_fparameter CLOSE_PAREN | OPEN_PAREN CLOSE_PAREN
formal_parameter : expression_parameter | function_parameter
function : return_options IDENTIFIER formal_parameters block
function_parameter : return_options IDENTIFIER formal_parameters
expression_parameter : VAR identifier_list IDENTIFIER | identifier_list IDENTIFIER
variable_creation : identifier_list COLON type SEMI_COLON
labels : LABELS identifier_list SEMI_COLON
list_E_identifiers : list_E_identifiers COMMA IDENTIFIER |
identifier_list : IDENTIFIER list_E_identifiers
return_options : VOID | IDENTIFIER
状态 12 冲突：1 reduce/reduce
state 12
56 identifier_list: IDENTIFIER . list_E_identifiers
60 return_options: IDENTIFIER .
102 list_E_identifiers: . list_E_identifiers COMMA IDENTIFIER
103 | .
COMMA reduce using rule 103 (list_E_identifiers)
IDENTIFIER reduce using rule 60 (return_options)
IDENTIFIER [reduce using rule 103 (list_E_identifiers)]
$default reduce using rule 60 (return_options)
list_E_identifiers go to state 23
状态 64 冲突：1 shift/reduce
state 64
8 body: OPEN_BRACE list_E_statement . CLOSE_BRACE
17 statement: . opt_declaration unlabeled_statement
18 | . compound
31 compound: . OPEN_BRACE list_NE_unlstatement CLOSE_BRACE
73 opt_declaration: . IDENTIFIER COLON
74 | .
94 list_E_statement: list_E_statement . statement
CLOSE_BRACE shift, and go to state 68
IDENTIFIER shift, and go to state 69
OPEN_BRACE shift, and go to state 70
IDENTIFIER [reduce using rule 74 (opt_declaration)]
$default reduce using rule 74 (opt_declaration)
statement go to state 71
compound go to state 72
opt_declaration go to state 73
谁能帮帮我？我看过 http://www.gnu.org/software/bison/manual/html_node/Understanding.html 但不明白这是什么意思。
如果有帮助，我可以post完整的语法。
谢谢！
第二个冲突是"optional"个元素的经典问题。像您所做的那样为可选标签编写规则是非常诱人的，但是 optional_label 无法产生任何结果这一事实迫使解析器在获得足够的信息之前尝试做出决定。
LR 解析器必须 "reduce"（识别）非终结符才能吸收任何进一步的标记。他们可以先行查看下一个 k 个标记（LR(1) 解析器的下一个标记，这是 bison 生成的），但他们不能暂时使用该标记然后再去回来做减少。
因此，当解析器处于下一个标记（标识符）应该开始语句的位置时，它可能正在查看以标识符开头的语句，或者它可能正在查看标签以标识符开头。它可以通过查看标识符后面的冒号（如果有的话）来区分，但它看不到那么远。
现在，如果不是因为需要减少空的 optional_declaration 或包含标签的标签，就不会有问题。如果你写过这样的东西：
statement: basic_statement | compound
basic_statement: unlabeled_statement | declaration unlabeled_statement
declaration: IDENTIFIER COLON
那么解析器在看到标识符时就不必做出决定。它只需要在生产结束时做出决定；当有两个可能的产品要完成时，它完全有能力向前推进。但是当你强制它识别一个optional标签时，它必须知道标签是否不存在以减少（识别）空生产。
对于第一个冲突，我们可以从输出中看到，在某些上下文中，先行符号是 IDENTIFIER，您可以使用 return_options 或 identifier_list .由于这两个产生式都可以产生一个 IDENTIFIER，解析器将不知道要减少哪个。
有了可用的实际语法，很容易找到 return_options IDENTIFIER 和 identifier_list IDENTIFIER 都可能的上下文：
formal_parameter : expression_parameter | function_parameter
expression_parameter: identifier_list IDENTIFIER
function_parameter : return_options IDENTIFIER …
那个语法没有歧义。如果 IDENTIFIER IDENTIFIER 是 function_parameter 的开始，那么它后面必须跟着一个 (；如果它是一个 expression_parameter，那么它后面必须跟着通过 、 或 )。但这是第二个下一个标记，这意味着您需要一个 LR(2) 解析器。
所以我会给出处理 LR(2) 语法的常用建议。可以将 LR(k) 文法重写为 LR(1) 文法，而不管 k 的值如何，但结果通常是臃肿和丑陋的。因此，如果您使用的是 bison，并且您愿意接受动作评估可能会稍微延迟的可能性，那么您最简单的解决方案是让 bison 生成一个 GLR 解析器。通常，只需将 %glr-parser 添加到选项部分就足够了。
值得注意的是，您的语法似乎是 C 和类 Pascal 语法之间的不稳定组合。在 C 中，参数中的第一个标记始终是类型；函数的 return 类型，或以下标识符的类型。在 Pascal 中，参数中的最后一个标记是类型。但在您的语法中，有时第一个标记是类型，有时是最后一个标记。从某种意义上说，正是这种不一致导致了语法上的尴尬。
（Pascal 有更多的标点符号：类型总是以冒号开头，函数参数之前是单词 function。不需要这些额外的标记来使语法正常工作，但它可以说它们使语法更容易被人类阅读。）
我正在使用 Bison 编写解析器，但似乎无法获得正确的语法。
有两个冲突：
以下是围绕冲突一使用的一些规则：
program : function END_OF_FILE {return 0;}
formal_parameters : OPEN_PAREN formal_parameter list_E_fparameter CLOSE_PAREN | OPEN_PAREN CLOSE_PAREN
formal_parameter : expression_parameter | function_parameter
function : return_options IDENTIFIER formal_parameters block
function_parameter : return_options IDENTIFIER formal_parameters
expression_parameter : VAR identifier_list IDENTIFIER | identifier_list IDENTIFIER
variable_creation : identifier_list COLON type SEMI_COLON
labels : LABELS identifier_list SEMI_COLON
list_E_identifiers : list_E_identifiers COMMA IDENTIFIER |
identifier_list : IDENTIFIER list_E_identifiers
return_options : VOID | IDENTIFIER
状态 12 冲突：1 reduce/reduce
state 12
56 identifier_list: IDENTIFIER . list_E_identifiers
60 return_options: IDENTIFIER .
102 list_E_identifiers: . list_E_identifiers COMMA IDENTIFIER
103 | .
COMMA reduce using rule 103 (list_E_identifiers)
IDENTIFIER reduce using rule 60 (return_options)
IDENTIFIER [reduce using rule 103 (list_E_identifiers)]
$default reduce using rule 60 (return_options)
list_E_identifiers go to state 23
状态 64 冲突：1 shift/reduce
state 64
8 body: OPEN_BRACE list_E_statement . CLOSE_BRACE
17 statement: . opt_declaration unlabeled_statement
18 | . compound
31 compound: . OPEN_BRACE list_NE_unlstatement CLOSE_BRACE
73 opt_declaration: . IDENTIFIER COLON
74 | .
94 list_E_statement: list_E_statement . statement
CLOSE_BRACE shift, and go to state 68
IDENTIFIER shift, and go to state 69
OPEN_BRACE shift, and go to state 70
IDENTIFIER [reduce using rule 74 (opt_declaration)]
$default reduce using rule 74 (opt_declaration)
statement go to state 71
compound go to state 72
opt_declaration go to state 73
谁能帮帮我？我看过 http://www.gnu.org/software/bison/manual/html_node/Understanding.html 但不明白这是什么意思。
如果有帮助，我可以post完整的语法。
谢谢！
第二个冲突是"optional"个元素的经典问题。像您所做的那样为可选标签编写规则是非常诱人的，但是 optional_label 无法产生任何结果这一事实迫使解析器在获得足够的信息之前尝试做出决定。
LR 解析器必须 "reduce"（识别）非终结符才能吸收任何进一步的标记。他们可以先行查看下一个 k 个标记（LR(1) 解析器的下一个标记，这是 bison 生成的），但他们不能暂时使用该标记然后再去回来做减少。
因此，当解析器处于下一个标记（标识符）应该开始语句的位置时，它可能正在查看以标识符开头的语句，或者它可能正在查看标签以标识符开头。它可以通过查看标识符后面的冒号（如果有的话）来区分，但它看不到那么远。
现在，如果不是因为需要减少空的 optional_declaration 或包含标签的标签，就不会有问题。如果你写过这样的东西：
statement: basic_statement | compound
basic_statement: unlabeled_statement | declaration unlabeled_statement
declaration: IDENTIFIER COLON
那么解析器在看到标识符时就不必做出决定。它只需要在生产结束时做出决定；当有两个可能的产品要完成时，它完全有能力向前推进。但是当你强制它识别一个optional标签时，它必须知道标签是否不存在以减少（识别）空生产。
对于第一个冲突，我们可以从输出中看到，在某些上下文中，先行符号是 IDENTIFIER，您可以使用 return_options 或 identifier_list .由于这两个产生式都可以产生一个 IDENTIFIER，解析器将不知道要减少哪个。
有了可用的实际语法，很容易找到 return_options IDENTIFIER 和 identifier_list IDENTIFIER 都可能的上下文：
formal_parameter : expression_parameter | function_parameter
expression_parameter: identifier_list IDENTIFIER
function_parameter : return_options IDENTIFIER …
那个语法没有歧义。如果 IDENTIFIER IDENTIFIER 是 function_parameter 的开始，那么它后面必须跟着一个 (；如果它是一个 expression_parameter，那么它后面必须跟着通过 、 或 )。但这是第二个下一个标记，这意味着您需要一个 LR(2) 解析器。
所以我会给出处理 LR(2) 语法的常用建议。可以将 LR(k) 文法重写为 LR(1) 文法，而不管 k 的值如何，但结果通常是臃肿和丑陋的。因此，如果您使用的是 bison，并且您愿意接受动作评估可能会稍微延迟的可能性，那么您最简单的解决方案是让 bison 生成一个 GLR 解析器。通常，只需将 %glr-parser 添加到选项部分就足够了。
值得注意的是，您的语法似乎是 C 和类 Pascal 语法之间的不稳定组合。在 C 中，参数中的第一个标记始终是类型；函数的 return 类型，或以下标识符的类型。在 Pascal 中，参数中的最后一个标记是类型。但在您的语法中，有时第一个标记是类型，有时是最后一个标记。从某种意义上说，正是这种不一致导致了语法上的尴尬。
（Pascal 有更多的标点符号：类型总是以冒号开头，函数参数之前是单词 function。不需要这些额外的标记来使语法正常工作，但它可以说它们使语法更容易被人类阅读。）