Конфликт в грамматике: возможно несколько действий

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($1); } 
    | EOF 
    ; 

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

node 
    : text 
    ; 

text 
    : text text_element 
    { $$ = $1 + $2; } 
    | 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 без разделителей. A node - это text, который состоит из одного или более text_element, без разделителей. Таким образом, нельзя сказать, когда заканчивается один node, и начинается следующее.

В качестве примера, если у вас есть последовательность из 3 text_elements, вы можете указать один node со всеми 3, или это может быть 3 node каждый с одним.

Bison будет «разрешать» этот конфликт, всегда предпочитая смещение по сокращению, которое всегда будет предпочитать создание более крупных объектов text, поэтому правило nodes: nodes node никогда не будет уменьшено и может быть просто удалено из грамматики. Поскольку это чистая двусмысленность (не проблема), результирующая грамматика соответствует одному и тому же языку, так что это может быть не проблема. Я предполагаю, что jison (или любой генератор синтаксического анализатора, который вы фактически используете) тот же.

В общем случае конфликты являются проблемой, потому что это означает, что грамматика, анализируемая сгенерированным парсером, не является указанной вами грамматикой. Выяснение того, какая грамматика фактически анализируется полученным парсером, нетривиальна и требует тщательного понимания того, как работает синтаксический анализ shoft и состояния, которые в действительности генерируются генератором синтаксического анализатора. Вся информация содержится в файле .output (изготовлена ​​бизоном с -v - другие генераторы могут быть разными), но вам нужно их прочитать и понять.