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

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

$ 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)

Как видно из дампа, выбор по предпросмотру ')' неоднозначен: можно сдвинуть символ как часть правила 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;

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

Кто же ты, аноним, и откуда ты столько знаешь о бизоне? =)

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

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

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

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

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

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