为什么这些冲突出现在下yacc语法的XML [英] Why are these conflicts appearing in the following yacc grammar for XML

问题描述

我有下面的XML语法的正常工作：

I have the following XML grammar which works fine:

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
    |

I don't like the additional statement for empty node_list so I added an empty rule to node_s |

但这样做我得到以下冲突

but by doing so i get the following conflicts

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

我不知道为什么，任何帮助将是AP preciated。

I have no idea why, any help would be appreciated.

推荐答案

运行<​​code>野牛--verbose AY 打印信息写入文件 a.output 。该文件包含的信息，如：

Running bison --verbose a.y prints information into file a.output. The file contains information such as:

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 ，机器可以做两个动作：

Here we can see that in state 27 there are 2 shift/reduce conflicts. I will describe the 1st shift/reduce conflict: when the state machine is in state 27, and the input is ID, the machine can do two actions:

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

是由第7条所产生的第一个行动 node_s：ID ，由第8条生成的第2个动作node_s：/ *空* / 。这是不明确的，选择哪个动作。

The 1st action was generated by rule 7 node_s:ID, the 2nd action was generated by rule 8 node_s:/*empty*/. It is ambiguous which action to choose.

node_list 是 node_s 的名单。在状态27，输入 ID 可以解析为

node_list is list of node_s. In state 27, the input ID can be parsed as

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

或

ID               node_list = node_s:ID

在换句话说，不可能决定节点列表是否应该以一个空节点开始

In other words, it is impossible to decide whether the node list should begin with an empty node.

要解决此问题，语法应修改如下：

To fix this problem, the grammar should be modified like this:

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

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

现在，解析时node_list'＆LT;''/'ID'＆GT; ，输入将​​明确地确定是否节点列表为空或非空：

Now, when parsing node_list '<''/'ID'>', the input will unambiguously determine whether the node list is empty or non-empty:

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

这篇关于为什么这些冲突出现在下yacc语法的XML的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！