bison - 解决Shift/Reduce冲突的语法规范

Question

我正在使用Jison(Bison)创建一种简单的标记语言。我显然是新来的，但是稍有变化的效果很好。我只是不了解S/R冲突的根源。

由两个词法分析器操作(具有不同的开始条件)返回“文本”似乎并不重要，我喜欢这一点，因为它似乎允许语法具有更少的规则，并且发给用户的错误消息是一致的。我尝试过不管上下文如何都通用“文本”规则，并且还尝试为每个 token 赋予不同的名称，但是当它们在一起时，似乎对S/R冲突没有任何影响。

该解析器可以创建一个具有纯文本，子数组和各种特殊节点的json对象。

规范:

/* lexical grammar */
%lex

%s bracketed

%%

<bracketed>(\\.|[^\\\,\[\]])+       { yytext = yytext.replace(/\\(.)/g, '$1'); return 'Text'; }
<INITIAL>(\\.|[^\\\[])+             { yytext = yytext.replace(/\\(.)/g, '$1'); return 'Text'; }
"["                                 { this.begin('bracketed'); return '['; }
"]"                                 { this.popState(); return ']'; }
","                                 return ','
<<EOF>>                             return 'END'

/lex

%start template

%%    

template
    : sentence END
    ;

sentence
    : /* empty */
    | sentence Text
    | sentence '[' ']'
    | sentence '[' dynamic ']'
    ;

dynamic
    : sentence
    /*| dynamic ',' sentence*/
    ;

警告:

Conflict in grammar: multiple actions possible when lookahead token is ] in state 5
- reduce by rule: sentence ->
- shift token (then go to state 6)

States with conflicts:
State 5
  sentence -> sentence [ .] #lookaheads= END Text [ ]
  sentence -> sentence [ .dynamic ] #lookaheads= END Text [ ]
  dynamic -> .sentence #lookaheads= ]
  sentence -> . #lookaheads= ] Text [
  sentence -> .sentence Text
  sentence -> .sentence [ ]
  sentence -> .sentence [ dynamic ]

不同的生成器算法或多或少有麻烦，但是它们似乎都有麻烦。

谢谢!

Answer 1

冲突从根本上来自以下两个规则:

sentence: sentence '[' Text ']'
        | sentence '[' sentenceList ']'

原因是，在看到 sentence和 [并查看了下一个标记为 Text之后，解析器不知道是否要移动 Text，匹配第一个规则，还是将那个 Text视为朝向的 sentenceList的开始符合第二条规则。

现在，如果您有一个使用2 token 先行的解析器生成器，这将不成问题，但是bison是LALR(1)(1是一个 token 先行)。

您可以尝试以下几种方法:

在词法分析器中进行了额外的前瞻，以将Text-followed-by-和Text-not-followed-]区别为两个不同的标记，然后重写规则以使用这两个标记。

使用野牛的％glr-parser功能使用GLR解析器。这将双向解析该句子，然后丢弃与

不匹配的句子

重构语法，无需提前2个 token 。

在您的情况下，一种有效的重构方法是重写 sentence规则，使它们全部向右递归，而不是向左递归:

sentence: /* empty */
        | Text sentence 
        | '[' ']' sentence
        | '[' Text ']' sentence
        | '[' sentenceList ']' sentence
        ;

这样可以避免 sentence(或其他以 sentence开头的规则，例如 sentenceList)以 sentence: /*empty*/规则的空值开头。因此，在有问题的情况下，解析器可以自由地移动 Text，从而将缩减推迟到看到下一个标记之前。但是，它确实涉及内存使用问题，因为它会导致解析器，该解析器实际上会将整个输入移至解析器堆栈，然后一次将其减少一个句子。

您可以做的另一种重构是将 [Text]和 []构造包含在 [sentenceList]中:

sentence: /* empty */
        | sentence Text 
        | sentence '[' sentenceList ']'
        ;

sentenceList: sentence
            | sentenceList ',' sentence

因此，现在 sentenceList是由逗号分隔的一个或多个句子(而不是两个或多个)，在 sentence '[' sentenceList ']'规则的操作中，您将检查 sentenceList是否为两个或多个句子并采取适当的措施。