Периодически проходит грамматика Bison, изредка терпит неудачу

Question

Я активно работаю с грамматиками Bison в первый раз. У меня установлена ​​моя грамматика и небольшой набор тестов для корреляции результатов.

Иногда набор тестов проходит:

Reducing stack by rule 101 (line 613): 
    $1 = nterm mathenv() 
-> $$ = nterm closedTerm() 
Stack now 0 5 3 
Entering state 120 
Reading a token: Next token is token ENDMATH() 
Reducing stack by rule 28 (line 517): 
    $1 = nterm closedTerm() 
-> $$ = nterm compoundTerm() 
Stack now 0 5 3 
Entering state 119 
Reducing stack by rule 12 (line 333): 
    $1 = nterm compoundTerm() 
-> $$ = nterm compoundTermList() 
Stack now 0 5 3 
Entering state 198 
Next token is token ENDMATH() 
Shifting token ENDMATH() 
Entering state 325 

... continues to completion ... 

Иногда он не делает:

Reducing stack by rule 101 (line 613): 
    $1 = nterm mathenv() 
-> $$ = nterm closedTerm() 
Stack now 0 5 3 
Entering state 120 
Reading a token: Next token is token MN() 
Reducing stack by rule 28 (line 517): 
    $1 = nterm closedTerm() 
-> $$ = nterm compoundTerm() 
Stack now 0 5 3 
Entering state 119 
Reducing stack by rule 12 (line 333): 
    $1 = nterm compoundTerm() 
-> $$ = nterm compoundTermList() 
Stack now 0 5 3 
Entering state 198 
Next token is token MN() 
Shifting token MN() 
Entering state 11 

... errors eventually ... 

Now at end of input. 
Line: 9 Error: syntax error at token 

ENDMATH правильный маркер для перехода к, но иногда, MN определяется. Я получаю несогласованные результаты, когда я запускаю свой тест. Является ли такая «случайная» двусмысленность нормальной? Что может быть причиной? Должен ли я определять некоторые правила %precedence?

В верхней части y.output, я вижу несколько конфликтов для государств, как

State 0 conflicts: 3 shift/reduce 
State 120 conflicts: 2 shift/reduce 
State 127 conflicts: 2 shift/reduce 
State 129 conflicts: 2 shift/reduce 
State 154 conflicts: 1 shift/reduce 
State 207 conflicts: 3 shift/reduce 
State 265 conflicts: 109 shift/reduce 
State 266 conflicts: 109 shift/reduce 
State 267 conflicts: 109 shift/reduce 
State 268 conflicts: 109 shift/reduce 
State 269 conflicts: 109 shift/reduce 
State 342 conflicts: 2 shift/reduce 
State 390 conflicts: 109 shift/reduce 
State 391 conflicts: 109 shift/reduce 
State 396 conflicts: 1 shift/reduce 
State 397 conflicts: 1 shift/reduce 

Целесообразно исключить все эти конфликты? Обратите внимание, что состояние 120 указано как имеющее конфликт и является правилом состояния перед этой случайной ошибкой.

Answer 1

Конфликты в вашей грамматике означают, что грамматика не LALR (1). Это может быть связано с неоднозначностью грамматики или, возможно, из-за грамматики, требующей более одного знака взгляда. Всякий раз, когда у вас есть конфликт, бизон разрешает его, выбирая одно из возможных действий (сдвиг или уменьшение) на основе указаний приоритета, которые у вас есть. В результате получается парсер, который распознает (анализирует) некоторое подмножество языка, описанного грамматикой.

Если конфликты происходят из-за двусмысленности, это может привести к простому устранению неоднозначных парсов и вообще не уменьшению языка. Для таких случаев использование правил приоритета для устранения двусмысленности является правильным способом решения проблемы, поскольку она дает вам грамматику, которая анализирует нужный язык.

Если конфликты вызваны необходимостью большего поиска, правила приоритета обычно не помогают. Вам необходимо решить проблему, переставив грамматику, чтобы не требовать просмотра или с помощью других методов (хаков), таких как добавление лексерных дополнительных синтетических токенов на основе дальнейшего поиска во входной или другой информации.

В вашем случае проблема возникает, как представляется, в лексере - в случае, если он возвращает токен ENDMATH, а в другом он возвращает MN. В грамматике могут также возникнуть неоднозначности или проблемы с рассмотрением конфликтов, которые вы видите в y.output, но такие проблемы на первый взгляд кажутся полностью независимыми от проблемы с лексером.