LINUX.ORG.RU

Конфликт сдвига/вывода

 


0

2

Доброго времени суток!

Может ли кто-нибудь объяснить, почему bison дает на этом файле конфликт сдвига/вывода? При комментировании 71 или 82 строчки конфликт исчезает. Но даже при наличии этого конфликта прога работает нормально. Не обращайте внимания на дурь при выводе - после того, как будет написана грамматика, эту часть можно будет отладить позднее при помощи деревьев. Или же этот конфликт не будет в итоге давать syntax error, но в правильном порядке составить аргументы не всегда получится? То есть, какова должна быть ситуация, чтобы этот конфликт проявился?

Прога должна уметь обрабатывать выражения вида:

abc
abc()
abc(def)
abc(45, 89.09, asd)
abc(45, 89.09, asd())
abc(45, 89.09, asd(hj))
abc(45, 89.09, asd(89).ui)
abc(45, 89.09, asd(89).ui).io
abc(45, 89.09, asd(89).ui).io(89)
...

Вот еще лексер, для полноты картины.

★★

Бизон позволяет сдампить кишки сгенерённого парсера:

$ bison --report=all --report-file=report grammar.y

В самом начале написано, какие конфликты в каких состояниях. Дальше идут общие статистики, а потом собственно состояния:

State 6 conflicts: 1 shift/reduce
...
state 6

    8 function: . WORD '(' func_args
    8         | WORD '(' . func_args
    9         | . WORD '(' ')'
    9         | WORD '(' . ')'
   10 func_args: .  [DOT, '\n', ')', ',']
   11          | . INT ',' func_args
   12          | . DOUBLE ',' func_args
   13          | . WORD ',' func_args
   14          | . INT ')'
   15          | . DOUBLE ')'
   16          | . WORD ')'
   17          | . function ',' func_args
   18          | . function ')'

    INT     shift, and go to state 11
    DOUBLE  shift, and go to state 12
    WORD    shift, and go to state 13
    ')'     shift, and go to state 14

    ')'       [reduce using rule 10 (func_args)]
    $default  reduce using rule 10 (func_args)
Точка обозначает текущую позицию, прямо за точкой --- символ предпросмотра. Бизон обрабатывает LALR(1) грамматики, поэтому парсер заглядывает вперёд на один символ. По этому одному символу парсер должен решить, что делать дальше: сдвигать символ и двигаться дальше или делать свёртку.

Как видно из дампа, выбор по предпросмотру ')' неоднозначен: можно сдвинуть символ как часть правила function -> WORD '(' . ')', а можно применить свёртку func_args -> . с тем чтоб впоследствии применить function -> WORD '(' func_args ')'.

Бизон всегда предпочитает сдвиг свёртке (по логике «зохавать как можно больше»), поэтому неоднозначность он решает в пользу function -> WORD '(' . ')'. Это объясняет то, что «парсится правильно»: если б бизон выбрал свёртку, то стало бы заметно, что правило func_args -> . кривое (там забыта закрывающая скобка).

В данном случае проблемную часть грамматики надо подправить примерно так:

function
    : WORD '(' ')'
    | WORD '(' func_args ')';

func_args
    : func_arg
    | func_args ',' func_arg;

func_arg
    : INT......
    | DOUBLE.
    | WORD...
    | function;

И тогда будет и красиво, и без конфликтов. :)

anonymous
()
Ответ на: комментарий от aido

Если хочешь разобраться в бизоне (и, возможно, в синтаксическом разборе в целом), то вот лучшая книжка, которую я знаю: http://www.dickgrune.com/Books/PTAPG_2nd_Edition/

Она даёт хорошее представление в целом (постановка задачи синтаксического разбора, разбиение на классы подзадач, обзор методов решения каждого класса) и в частности (объяснение принципа действия и ключевых моментов отдельных алгоритмов).

Её можно читать не всю сразу, а по мере надобности. Например, чтобы понимать бизон, можно идти от общего к частному: классификация Хомского -> контекстно-свободные грамматики -> разбор «снизу вверх» (bottom-up, в противовес разбору «сверху вниз», top down) -> LR: однозначные КС-грамматики -> LR(k) -> LR(1) -> LALR(1). Тогда станет ясно, что там с конфликтами (и многое другое).

Потом, если понадобится, можно вникать до посинения (там список литературы внушительный по любому из направлений).

А я https://github.com/skvadrik.

anonymous
()
Ответ на: комментарий от anonymous

А как использовать при парсинге «стрелочки» на клавиатуре. Например, они очень полезны для автодополнения и редактирования команды.

aido ★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.