Почему эти конфликты появляются в следующей грамматике yacc для XML - PullRequest
Новая
       44

Почему эти конфликты появляются в следующей грамматике yacc для XML

2 голосов
/ 11 марта 2012

У меня есть следующая грамматика 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_s |

, нопри этом я получаю следующие конфликты 

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

Я понятия не имею, почему, любая помощь будет оценена.

1 Ответ

2 голосов
/ 11 марта 2012

Запуск 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 конфликта сдвига / уменьшения. Я опишу 1-й конфликт сдвига / уменьшения: когда конечный автомат находится в состоянии 27, а на входе - ID, машина может выполнять два действия: 

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

1-е действие было сгенерировано правилом 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
...