gpt4 book ai didi

Bison 减少/减少

转载 作者:行者123 更新时间:2023-12-02 18:21:49 27 4
gpt4 key购买 nike

我是 Bison 解析的新手,我无法理解它是如何工作的。我有以下语法,其中我保留了最低限度的语法来突出问题。

%left '~'
%left '+'
%token T_VARIABLE
%%
start: expr;
expr: composite_expr | variable_expr;
variable_expr: T_VARIABLE;
composite_expr:
expr '+' expr
| '~' variable_expr { do_something_1(); }
| '~' composite_expr { do_something_2(); }
;

%%

如您所见,我想根据后面的表达式类型对 '~' 运算符应用不同的函数。然而,这会产生 2 个归约/归约冲突。

当然,如果我像这样重写composite_expr规则......

composite_expr:   
expr '+' expr
| '~' expr { /* ??? */ }
;

...那么就没有冲突了,但现在我无法调用 do_something_1()do_something_2() 因为我无法再判断 expr variable_exprcomposite_expr

还有其他方法可以做到这一点吗?谁能解释一下为什么首先要减少/减少冲突?

请记住,这是一个精简版本,实际上,规则 composite_expr 非常长。所以复制它是不可能的。

最佳答案

基本问题是你的语法不明确,并且你(试图)使用优先规则来解决歧义,但它失败了,因为歧义表现为归约/归约冲突,而优先规则在那种情况。您可以使用 bison 的 -v 更好地了解正在发生的情况。选项来获取它构建的状态机的列表,这样您就可以准确地看到冲突在哪里以及如何体现。

在这种情况下,您会看到类似以下内容:

state 8

3 expr: variable_expr .
6 composite_expr: '~' variable_expr .

$end reduce using rule 6 (composite_expr)
'+' reduce using rule 3 (expr)
'+' [reduce using rule 6 (composite_expr)]
$default reduce using rule 3 (expr)

这告诉您它不知道在 + 的前瞻中减少哪个规则。现在显然从你的优先规则中你想要规则6(因为 ~ 的优先级高于 + ),但是 bison 中的优先级消歧规则有点麻烦,无法处理这个问题 - 它无法理解减少规则 3 将导致 + 发生变化在减少将消耗 ~ 的规则之前.

那么你能对此做些什么呢?您可以接受冲突的存在并制定规则,以便正确的事情发生。在这种情况下,您需要移动 expr: composite_expr | variable_expr规则到最后(至少到 composite_expr 规则之后)。这有点丑陋,难以理解,更难维护。

或者,您可以对事物进行分解以摆脱单个规则(具有单个非终结符且右侧没有其他内容的规则 - 这些是往往会触发归约/归约问题的规则。),例如:

composite_expr:   
composite_expr '+' composite_expr
| composite_expr '+' variable_expr
| variable_expr '+' composite_expr
| variable_expr '+' variable_expr
| '~' variable_expr { do_something_1(); }
| '~' composite_expr { do_something_2(); }
;

如果有很多composite_expr,这不太可能实用。正如您所描述的规则。

最好的选择可能是根本不在语法中这样做,而是根据您的语义规则进行选择。像这样的东西:

expr:   
expr '+' expr { $$.isComposite = true; }
| '~' expr { if ($2.isComposite)
do_something_2();
else
do_something_1();
$$.isComposite = true; }
| T_VARIABLE { $$.isComposite = false; }
;

然后您设置 %type对于 expr成为一个带有额外 bool isComposite 的结构字段以及您使用它的任何其他内容。

关于 Bison 减少/减少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6718917/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com