语法冲突:可能采取多种行动

Question

我试图用jison（http://zaa.ch/jison/docs/）编写简单的解析器，卡在描述文本中。

%lex
%%
[snt]+                   return 'TK_SPACE';
[0-9]+("."[0-9]+)?b        return 'TK_NUMBER';
[a-zA-Z]+([a-zA-Z0-9]+)?b  return 'TK_WORD';
<<EOF>>                     return 'EOF';
/lex
%start document
%%
document
  : nodes EOF
    { console.log($1); }
  | EOF
  ;
nodes
  : nodes node
    { $1.push($2); $$ = $1; }
  | node
    { $$ = [$1]; }
  ;
node
  : text
  ;
text
  : text text_element
    { $$ = $1 + $2; }
  | text_element
  ;
text_element
  : TK_NUMBER
  | TK_WORD
  | TK_SPACE
  ;

此语法编译有警告。

Conflict in grammar: multiple actions possible when lookahead token is TK_SPACE in state 5
- reduce by rule: node -> text
- shift token (then go to state 9)
Conflict in grammar: multiple actions possible when lookahead token is TK_WORD in state 5
- reduce by rule: node -> text
- shift token (then go to state 8)
Conflict in grammar: multiple actions possible when lookahead token is TK_NUMBER in state 5
- reduce by rule: node -> text
- shift token (then go to state 7)
States with conflicts:
State 5
  node -> text . #lookaheads= TK_SPACE TK_WORD TK_NUMBER EOF
  text -> text .text_element #lookaheads= EOF TK_NUMBER TK_WORD TK_SPACE
  text_element -> .TK_NUMBER
  text_element -> .TK_WORD
  text_element -> .TK_SPACE

但是如果我尝试解析文本，它可以正常工作。这不是代码的完整版本，只是带有文本的版本。我想在功能node附加节点。

Answer 1

问题是你的语法不明确——nodes由一个序列或模式node组成，没有分隔符。 node是一个text，它由一个或多个没有分隔符的text_element组成。 因此，无法判断一个node何时结束，下一个何时开始。

例如，如果您的输入中有 3 个text_elements序列，则可能是包含所有 3 个node，也可能是 3 个node每个 1。

Bison将通过始终更喜欢shift而不是reduce来"解决"这种冲突，后者总是喜欢制作更大的text对象，因此规则nodes: nodes node永远不会减少，并且可能只是从语法中删除。 由于这是一个纯粹的歧义（不是前瞻性问题），因此生成的语法与相同的语言匹配，因此这可能不是问题。 我假设 jison（或您实际使用的任何解析器生成器）是相同的。

但是，一般来说，

冲突是一个问题，因为这意味着生成的解析器解析的语法不是您指定的语法。 弄清楚生成的解析器实际解析的语法并非易事，需要仔细了解 shoft-reduce 解析的工作原理以及解析器生成器实际生成的状态。 信息都在.output文件中（由 bison 用 -v 生成 - 其他生成器可能不同），但您需要阅读和理解它。