6

我正在使用 Jison (Bison) 创建一个简单的标记语言。我显然对此很陌生，但细微的变化效果很好。我只是不明白 S/R 冲突的根源。

两个词法分析器操作（具有不同的开始条件）返回“文本”似乎并不重要，我喜欢这个，因为它似乎允许语法有更少的规则，而且给用户的错误消息是一致的。无论上下文如何，我都尝试使“文本”规则通用，并且我还尝试为每个标记赋予不同的名称，但是当它们一起出现时，它似乎对 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 ]

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

谢谢！

4

1 回答 1

17

冲突从根本上来自以下两条规则：

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

原因是在看到 asentence和 a[并查看下一个标记是Text之后，解析器不知道是移动Text，匹配第一条规则，还是将其Text视为sentenceList匹配第二条规则的开始。

现在，如果您有一个使用 2-token 前瞻的解析器生成器，这不会有问题，但 bison 是 LALR(1)（1 是一个 token 前瞻）。

您可以尝试以下几件事：

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

  • 使用 bison 的 %glr-parser 功能来使用 GLR 解析器。这将双向解析句子，然后丢弃不匹配的句子

  • 重构语法以不需要 2-token 前瞻。

适用于您的情况的一种重构是重写sentence规则以使它们全部右递归而不是左递归：

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

这避免了sentence（或任何其他以sentence诸如sentenceList开头的规则）以规则的空归约开始sentence: /*empty*/。因此，解析器可以Text在有问题的情况下自由移动 a ，将缩减推迟到它看到下一个标记。然而，它确实有内存使用的影响，因为它导致解析器本质上将整个输入转移到解析器堆栈，然后一次减少一个句子。

您可以做的另一个重构是将[Text]and[]构造包含到[sentenceList]：

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

sentenceList: sentence
            | sentenceList ',' sentence

所以现在 asentenceList是一个或多个用逗号分隔的句子（而不是两个或多个），并且在sentence '[' sentenceList ']'规则的操作中，您将检查sentenceList它是否是两个或多个句子并采取适当的行动。

于 2012-10-03T22:22:39.497 回答