代码之家 › 专栏 › 技术社区 › Stephen Cross

简单语法的Bison移位/减少冲突

shift-reduce-conflict bison parsing

Stephen Cross · 技术社区 · 14 年前

%token TYPENAME
%token VARNAME
%token THIS

%%

start:
    Expression
    ;

Expression:
    THIS
    | THIS '.' VARNAME
    | Expression '.' TYPENAME
    ;
%%

表达式的第一条规则允许用户将“this”作为值传递(例如,从方法返回它或传递给方法调用)。第二个是访问“this”上的数据。第三条规则是调用方法,但是我去掉了括号和参数,因为它们与问题无关。最初的语法显然比这个大得多,但是这是产生相同错误的最小部分(1个Shift/Reduce冲突)-我将它隔离到自己的解析器文件中并验证了这一点,因此错误与任何其他符号无关。

Expression '.' VARNAME

没有冲突。在任何情况下,我可能需要有人来说明为什么会发生这种冲突,以及如何解决它。

2 回复 | 直到 14 年前

Jonathan Leffler 7 年前

问题是语法只能向前看。所以当你看到 THIS 然后是 . ,你在2号线吗( Expression: THIS '.' VARNAME Expression: Expression '.' TYPENAME ,通过第1行的缩减)。

语法可以减少 THIS. 到 Expression. 然后找一个 TYPENAME 或者把它移到找一个 VARNAME ,但它必须决定何时到达 .

user34537 user34537 14 年前

我尽量避免y输出,但有时确实有用。我看了看它制作的文件,看到了。

state 1

    2 Expression: THIS.  [$end, '.']
    3           | THIS . '.' VARNAME

    '.'  shift, and go to state 4

    '.'       [reduce using rule 2 (Expression)]
    $default  reduce using rule 2 (Expression)

基本上是说它看到了“.”,可以减少,也可以改变。减少有时使我心神不定,因为他们很难罚款。这个转变是规则3,而且很明显(但是输出没有提到规则#)。在本例中,它看到的“.”处的reduce是行

| Expression '.' TYPENAME

当它转到表达式时,它会查看下一个字母(“.”)并进入。现在它看到了 THIS | 因此,当它到达该语句的结尾时,它期望“.”离开或出现错误。但是,它看到这个“.”,而它介于这个和“.”(因此out文件中的点)之间,并且它可以减少规则,因此存在路径冲突。我相信你可以用 %glr-parser

我强烈推荐 this book 在尝试使用野牛之前。

我想不出一个'伟大'的解决方案,但这没有冲突

start:
    ExpressionLoop
    ;

ExpressionLoop:
      Expression
    | ExpressionLoop ';' Expression
    ;
Expression:
      rval 
    | rval '.' TYPENAME
    | THIS //trick is moving this AWAY so it doesnt reduce
rval:

    THIS '.' VARNAME

或者,您可以稍后通过向规则中添加更多内容使其不会立即减少,或者通过在之后或之前添加令牌来明确要选择哪条路径或失败(请记住,在减少任何路径之前,它必须知道)

start:
    ExpressionLoop
    ;

ExpressionLoop:
      Expression
    | ExpressionLoop ';' Expression
    ;
Expression:
      rval 
    | rval '.' TYPENAME
rval:
      THIS '@'
    | THIS '.' VARNAME
%%

func param 和 type varname 我不能,因为根据lexer func,type是一个Var(即a-Za-z09)和type。param和varname都是var,所以这会导致reduce/reduce冲突。你不能把这写成他们的样子,只能写他们的样子。所以写作时要记住这一点。您必须编写一个标记来区分这两个,或者将其作为其中一个来编写,但要在代码(规则右侧{}中的部分)中编写附加逻辑,以检查它是funcname还是type,并处理这两种情况。