语法冲突：可能有多个动作

Question

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

%lex

%%
[\s\n\t]+                   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(); }
  | EOF
  ;

nodes
  : nodes node
    { .push(); $$ = ; }
  | node
    { $$ = []; }
  ;

node
  : text
  ;

text
  : text text_element
    { $$ =  + ; }
  | 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 的单个 node，也可能是每个包含 3 个 node有一个。

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

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

语法冲突：可能有多个动作

Conflict in grammar: multiple actions possible

parsing

bison

lalr

jison