语法规范解决Shift/Reduce冲突

Question

我正在使用Jison(Bison)来创建一个简单的标记语言.我显然对此很陌生,但略有不同的变化非常好.我只是不明白S/R冲突的根源.

"文本"由两个词法分析器操作(具有不同的"开始条件")返回似乎并不重要,我喜欢这样,因为它似乎允许语法具有更少的规则,并且因为给用户的错误消息是一致的.我已经尝试将"文本"规则放在一起,不管上下文如何,我也尝试给每个标记一个不同的名称,但它似乎对S/R冲突没有任何影响.

解析器是SUPPOSED用于创建具有纯文本,子数组和各种特殊节点的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 ']'

原因是在看到a sentence和a [并查看下一个令牌之后Text,解析器不知道是否移位Text,匹配第一个规则,或者将其Text视为开始sentenceList匹配第二个规则.

现在,如果你有一个使用2令牌前瞻的解析器生成器,这不会有问题,但是野牛是LALR(1)(1是一个令牌前瞻).

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

• 在词法分析器中做额外的预测以区分Text-follow-by-]和Text-not-follow-by-]作为两个不同的标记,然后重写规则以使用这两个标记.

• 使用bison的%glr-parser功能来使用GLR解析器.这将以两种方式解析句子,然后丢弃不匹配的句子

• 重构语法,不需要2令牌前瞻.

在你的情况下有效的一个重构是重写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

所以现在a sentenceList是用逗号分隔的一个或多个句子(而不是两个或更多),并且在sentence '[' sentenceList ']'规则的动作中,你要检查sentenceList它是否是两个或更多的句子并采取适当的行动.