[bison] reduce/reduce конфликты

a10063

помогите разобраться, почему в следующей грамматике возникает конфликт и можно ли его решить:

 

%%

input:    /* empty */

        | input line

;

line:     '\n'

        | stmt '\n'

;

stmt:     var '=' exp

;

var:      id '(' int ',' int ',' int ')'

;

exp:      int

        | func

        | var

;

func:     id '(' exp ')'

        | id '(' exp ',' exp ')'

;

int: FLEX_INTEGER;

id:       FLEX_ID;

%%

sevast82

Есть подозрение, что в первом нетерминале нужно избавиться от левой рекурсии, изменив местами input и line во втором правиле.

bobby

Any kind of sequence can be defined using either left recursion or right recursion, but you should always use left recursion, because it can parse a sequence of any number of elements with bounded stack space. Right recursion uses up space on the Bison stack in proportion to the number of elements in the sequence, because all the elements must be shifted onto the stack before the rule can be applied even once. See The Bison Parser Algorithm, for further explanation of this.

sevast82

Я лучше подожду ответа от автора треда.

bobby

Ну, ок, подожди, но имей ввиду, что Бизон LALR(1 а не LL.

sevast82

Думаю, вот в такой грамматике конфликтов не будет:
input: /* empty */
| lines
;
lines: line
| line lines
;
line: '\n'
| stmt '\n';

bobby

Будет, и более того - есть

Правда, не в той части грамматики, что ты привел.

bobby

Конфликт вот в чем.
Смотри, пусть парсер читает строчку

FLEX_ID ( FLEX_INTEGER , FLEX_INTEGER , FLEX_INTEGER ) = FLEX_ID ( FLEX_INTEGER ,

Когда парсер будет читать конец строки, он сильно задумается над тем, сворачивать ли последний FLEX_INTEGER (который на самом деле уже свернут в int) в exp или же смещаться дальше (соотв. для правил func и var).
Если в правиле var заменить все int на exp, то конфликт будет устранен, но придется делать доп. проверки после сворачивания правила var (являются ли разобранные exp'ы внутри правила var int'ами).

bobby

Кстати, конфликт shift/reduce, а не reduce/reduce.

$ bison test2.y

test2.y: conflicts: 1 shift/reduce

a10063

2Lifelike:

Есть подозрение, что в первом нетерминале нужно избавиться от левой рекурсии, изменив местами input и line во втором правиле.

согласен с 'ом
bison - LR(1) парсер и рекурсии записывать нужно именно так
тут конфликт сопряжен с var
2:

Конфликт вот в чем.
Смотри, пусть парсер читает строчку
code:FLEX_ID ( FLEX_INTEGER , FLEX_INTEGER , FLEX_INTEGER ) = FLEX_ID ( FLEX_INTEGER ,
Когда парсер будет читать конец строки, он сильно задумается над тем, сворачивать ли последний FLEX_INTEGER (который на самом деле уже свернут в int) в exp или же смещаться дальше (соотв. для правил func и var).
Если в правиле var заменить все int на exp, то конфликт будет устранен, но придется делать доп. проверки после сворачивания правила var (являются ли разобранные exp'ы внутри правила var int'ами).

спасибо, кажется я понял
получается, от конфликта можно избавиться только описанным способом и перегруппировкой/разбиением правил тут не решить?

Кстати, конфликт shift/reduce, а не reduce/reduce.

точно. это я reduce/reduce разворачивал (упрощал правила) и пришел к этому, не заметил

Оставить комментарий