なぜ私は正常に動作し、次のXMLの文法を持つXML

Question

ため、以下のyacc文法に登場するこれらの競合です：

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で、マシンは二つの動作を行うことができます：私は競合を減らす/第一のシフトを説明

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

第一アクションがルール7 node_s:IDによって生成されました、 2番目のアクションはルール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