c - 为什么这些冲突出现在以下 XML 的 yacc 语法中

Question

我有以下 XML 语法，效果很好:

program 
    : '<' '?'ID attribute_list '?''>' 
      root
    ;
root
    : '<' ID attribute_list '>' node_list '<''/'ID'>'
    ;

node_list
    : node_s
    | node_list node_s
    ;
node_s
    : node
    | u_node
    | ID
    ;

node
    : '<' ID attribute_list '/''>'
    ;
u_node
    :'<' ID attribute_list '>' node_list '<''/'ID'>'
    |'<' ID attribute_list '>' '<''/'ID'>'
    ;

attribute_list
    : attributes
    |
    ;
attributes
    : attribute
    | attributes attribute   
    ;

attribute
    : ID ASSIGNOP '"' ID '"'
    | ID ASSIGNOP '"' NUM '"'
    | ID ASSIGNOP '"' NUM ID'"'
    | ID ASSIGNOP '"' WEB '"'
    ;

我不喜欢空node_list的附加语句，所以我向node_s添加了一个空规则 |

但是这样做我会遇到以下冲突

conflicts: 8 shift/reduce
prog1.y:40.10: warning: rule useless in parser due to conflicts: node_s: /* empty */

我不知道为什么，任何帮助将不胜感激。

Answer 1

正在运行bison --verbose a.y将信息打印到文件 a.output 。该文件包含以下信息:

State 27 conflicts: 2 shift/reduce

Grammar

    3 node_list: node_s
    4          | node_list node_s

    5 node_s: node
    6       | u_node
    7       | ID
    8       | /* empty */

...

state 27

    2 root: '<' ID attribute_list '>' . node_list '<' '/' ID '>'

    ID   shift, and go to state 28
    '<'  shift, and go to state 29

    ID   [reduce using rule 8 (node_s)]
    '<'  [reduce using rule 8 (node_s)]

    node_list  go to state 30
    node_s     go to state 31
    node       go to state 32
    u_node     go to state 33

state 28

    7 node_s: ID .

在这里我们可以看到，在状态 27 中有 2 个移位/归约冲突。我将描述第一个移位/归约冲突:当状态机处于状态 27 且输入为 ID 时，机器可以做两个 Action :

shift, and go to state 28
[reduce using rule 8 (node_s)]

第一个操作是由规则 7 node_s:ID 生成的，第二个操作是由规则 8 node_s:/*empty*/ 生成的。选择哪个操作是不明确的。

node_list是 node_s 的列表。在状态 27 下，输入 ID可以解析为

<nothing> ID     node_list = node_s:/*empty*/, node_s:ID

或作为

ID               node_list = node_s:ID

换句话说，无法决定节点列表是否应该以空节点开头。

要解决这个问题，语法应该修改如下:

node_list
    : /*empty*/
    | node_list node_s
    ;
node_s
    : node
    | u_node
    | ID
    ;

u_node
    :'<' ID attribute_list '>' node_list '<''/'ID'>'
    ;

现在，解析 node_list '<''/'ID'>' 时，输入将明确确定节点列表是否为空或非空:

INPUT   ACTION
< /     empty node list
< ID    non-empty node list
ID      non-empty node list