bison (конфликт сдвига/вывода) - C/C++. Прикладные вопросы

Подскажите как подправить грамматику
bison 2.4.1 конфликты: 1 сдвига/вывода

%start na
%%
na : nb
   | na nb
   ;
nb : 'a' na '#' 'b' 
   | 'c' nc
   | 'd'
   ;
nc :
   | '#' 'e'
   ; 
%%

20.06.10 20:41: Перенесено модератором из 'C/C++' — Кодт

Здравствуйте, andrey_egeg, Вы писали:

_>na : nb
_>   | na nb
_>   ;

Конечно, бизон мог бы и догадаться, что уравнение
na = na | na nb
na = (|na) nb
na = (nb*) nb
na = nb+

Но наивный парсер здесь получает зацикливание.
Скажем, у нас попытка сопоставить na = "x#"

na = "xxx" ?
  nb = "xxx" ?
    "a" ... = "xxx" - нет
    "c" ... = "xxx" - нет
    "d" ... = "xxx" - нет
    - нет
  na nb = "xxx" ?
    nb ... = "xxx" ?
      сказка про белого бычка

Здравствуйте, andrey_egeg, Вы писали:

Да, а поправить нужно так:
_>

_>na : nb
_>   | nb na
_>   ;
_>

Здравствуйте, Кодт, Вы писали:

К>Да, а поправить нужно так:

na : nb
   | nb na
   ;

Только и всего? Не смешно.

Мог бы придумать что нить пооригинальней.

Здравствуйте, andrey_egeg, Вы писали:

_>Только и всего? Не смешно.

_>Мог бы придумать что нить пооригинальней.

Он придумает, например перенесет в другой форум, на место.

Здравствуйте, andrey_egeg, Вы писали:

_>Только и всего? Не смешно.

_>Мог бы придумать что нить пооригинальней.

Согласен, нагнал.

Ниже нетерминалы с большой буквы.

Видно, что проблема сосредоточена здесь:
A = B | BA
B = aA#b | cC | d
C = | #e

подставляя C в B, и забивая на A, получим
B = aB#b | c | c#e | d

И вот здесь-то и ругается бизон.

Здравствуйте, andrey_egeg, Вы писали:

_>Подскажите как подправить грамматику
_>bison 2.4.1 конфликты: 1 сдвига/вывода

Что, если просто задавить эту ошибку?

%start na

%expect 1

%%
.....

Здравствуйте, Кодт, Вы писали:

_>>Подскажите как подправить грамматику
_>>bison 2.4.1 конфликты: 1 сдвига/вывода

К>Что, если просто задавить эту ошибку?

И что он сделает встретив, например ac#b? Встретив после 'c' знак '#', парсер сделает сдвиг и будет очень удивлен, встретив 'b' вместо 'e'.

Здравствуйте, andrey_egeg, Вы писали:

_>Здравствуйте, Кодт, Вы писали:

К>>Да, а поправить нужно так:
_>

_>na : nb
_>   | nb na
_>   ;
_>

_>Только и всего? Не смешно. :shuffle:
_>Мог бы придумать что нить пооригинальней.

Дело не в том, оригинальней или нет, а в том, что это действительно важная замена для таких простых парсеров, как bison. Левосторонняя рекурсия без оснований ему плохо удаётся.

А хорошую подсказку здесь дал Xeor: пример ac#b разбирается двумя возможными путями. Это в общем-то значит, что исходная грамматика некорректна, и пытаться выкрутить это задавливанием конфликтов бессмысленно — в лучшем случае получите reduce/reduce conflict и он откажет собираться. Исправь на корректную.

P.S. А твоя реплика про "Мог бы придумать что нить пооригинальней" слишком многими может быть воспринята как неконструктивный наезд.

Здравствуйте, netch80, Вы писали:

N>А хорошую подсказку здесь дал Xeor: пример ac#b разбирается двумя возможными путями. Это в общем-то значит, что исходная грамматика некорректна, и пытаться выкрутить это задавливанием конфликтов бессмысленно — в лучшем случае получите reduce/reduce conflict и он откажет собираться. Исправь на корректную.

Поскольку контекста из одного символа недостаточно для спуска туда или сюда — это не LL(1)-грамматика (да?)

Если мы сделаем фокус, и склеим токены #b и #e на стадии лексера, то всё будет хорошо.

Может быть, ещё какие-то фокусы возможны — как, например, разруливается if-then/if-then-else.
Может быть, нужно ввести приоритеты...

Здравствуйте, andrey_egeg, Вы писали:

Ха! Я победил бизона!

%start series

%%

// нетерминал xxx_ эквивалентен xxx '#'

series  : elem  | elem series  ;
series_ : elem_ | elem series_ ;

elem  : alfa  | charlie  | delta  ;
elem_ : alfa_ | charlie_ | delta_ ;

alfa  : 'a' series_ 'b'  ;
alfa_ : alfa '#' ;

charlie  : 'c'     | 'c' '#' 'e' ;
charlie_ : 'c' '#' | 'c' '#' 'e' '#' ;

delta  : 'd' ;
delta_ : delta '#' ;

%%

Идея была в следующем: поскольку неоднозначность возникает между c·#b и c·#e — т.е. непонятно, то ли сворачивать прямо сейчас, то ли чуть погодя...
А не сделать ли нам так, чтобы # всегда сдвигался?!
Тогда момент выбора переместится на один шаг вперёд: c#·b или c#·e# — а уж отличить b от e мы сумеем

Написать

charlie  : 'c' | 'c' '#' 'e' ;
charlie_ : 'c' '#' ;

нельзя, поскольку мы здесь опять получим shift/reduce: то ли идти по второй ветке charlie, то ли немедленно сворачивать его.

Единственно, что отягощает — количество дублёров_.

А кстати, это грамматика реальной задачи, или учебно-тренировочной?

Здравствуйте, andrey_egeg, Вы писали:

_>Подскажите как подправить грамматику
_>bison 2.4.1 конфликты: 1 сдвига/вывода

А вот похоже штатное средство от таких проблем. Эта грамматика как раз LALR(2) получается.

http://www.gnu.org/software/bison/manual/html_node/Simple-GLR-Parsers.html

Здравствуйте, Xeor, Вы писали:

X>А вот похоже штатное средство от таких проблем. Эта грамматика как раз LALR(2) получается.

X>http://www.gnu.org/software/bison/manual/html_node/Simple-GLR-Parsers.html

Что-то у меня получилось. Ну, добавил %glr-parser, а он как был LALR(1), так и остался.
Можешь показать работающий код?

Здравствуйте, Кодт, Вы писали:

К>Что-то у меня получилось. Ну, добавил %glr-parser, а он как был LALR(1), так и остался.
К>Можешь показать работающий код?

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

Здравствуйте, Xeor, Вы писали:

X>Я вживую его не использовал. Парсер-то и останется LALR(1), только в случае неоднозначности ветвится в оба пути, а потом откидывает неудачный вариант.

А, понятно, это у меня в ходе экспериментов закралась опечатка... сейчас заново набил код — всё заработало.

Здравствуйте, netch80, Вы писали:

N>Дело не в том, оригинальней или нет..
N>Исправь на корректную.
N>P.S. А твоя реплика про "Мог бы придумать что нить пооригинальней" слишком многими может быть воспринята как неконструктивный наезд.

Смысл упомянутой "реплики про" — это просьба изменить грамматику таким образом, дабы исключить вышеупомянутый конфликт. И, поясни, что "конструктивного" в твоем предложении самому "исправить на корректную", которое с последним — "..наезд." по-сути воспринимается как бестолковый треп.
p.s. решение — пара переставленных строк + оператор %prec и %left(естественно без директивы glr-parser и %expect)

Здравствуйте, andrey_egeg, Вы писали:

_>p.s. решение — пара переставленных строк + оператор %prec и %left(естественно без директивы glr-parser и %expect)

Покажи, пожалуйста, решение.

Здравствуйте, Кодт, Вы писали:
К>Покажи, пожалуйста, решение.

%right '#'
%start na
%%
nc     : 'c' %prec '#'
    | 'c' '#' 'e'
    | nb
    ; 
na    : nc 
    | na nc
    ;
nb    : 'a' na '#' 'b' 
    | 'd'
    ;
%%

Не у кого не завалялись корректные (примерно как Е.Зуева в книге А.Ахо "Компиляторы.." ) bison`и грамматики С++ и HTML? В идеале — интересуют исходники программы SourceMonitor, в которой (по слухам) присутствует первая (C++).

Здравствуйте, Аноним, Вы писали:

А>Не у кого не завалялись корректные (примерно как Е.Зуева в книге А.Ахо "Компиляторы.." ) bison`и грамматики С++ и HTML? В идеале — интересуют исходники программы SourceMonitor, в которой (по слухам) присутствует первая (C++).

В GCC присутствует грамматика C++.... а в каком смысле корректные? понятные для человека или корректные для bison?

Здравствуйте, GhostCoders, Вы писали:

А>>bison`и грамматики С++ и HTML?
GC>В GCC присутствует грамматика C++.... а в каком смысле корректные? понятные для человека или корректные для bison?
Та что в gcc-g++-3.3.1-3-src (и т.п.) требует серьезной доработки в связке flex и bison, а этой возни хотелось бы избежать.

	От:	andrey_egeg
	Дата:	20.06.10 14:04
	Оценка:

	От:	Кодт
	Дата:	20.06.10 16:40
	Оценка:

	От:	Кодт
	Дата:	20.06.10 16:41
	Оценка:

	От:	andrey_egeg
	Дата:	20.06.10 17:25
	Оценка:

	От:	Ops
	Дата:	20.06.10 18:11
	Оценка:

От:	netch80	http://netch80.dreamwidth.org/
Дата:	21.06.10 05:33
Оценка:

	От:	Аноним
	Дата:	25.06.10 13:01
	Оценка:

	От:	GhostCoders
	Дата:	25.06.10 13:03
	Оценка:

	От:	Аноним
	Дата:	25.06.10 13:29
	Оценка: