Есть ли что-то неправильное в этом определении CFG Bison?

У меня есть следующая грамматика в файле Bison:

lst: ID COMMA lst
   | ID
   | /*empty*/

plst: lst SEMICOLON lst
    | SEMICOLON lst
    | lst

ГДЕ первое правило фактически пытается отобразить список идентификаторов, таких как id1,id2,id3...

А второй хочет отобразить возможную пару списков, разделенных точкой с запятой. Допустимые варианты: id11,id12,id13...;id21,id22,id23..., id1,id2,id3... или ;id1,id2,id3....

Мне было интересно, правильный ли это набор правил, поскольку Bison возвращает много конфликтов. Я подумал, что одной из возможных проблем могут быть неправильно сформированные правила. Итак, мой вопрос: вышеупомянутый набор правил хорош или он подвержен конфликтам? Спасибо.


grammar context-free-grammar formal-languages bison
person Andry    schedule 24.09.2013    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Проблема в том, что вы позволяете lst быть пустым. Таким образом, невозможно различить:

lst ';' lst

и

';' lst

Другими словами, lst пусто или отсутствует? Грамматика неоднозначна.

Я бы убрал пустое производство для lst, но есть и другие решения.

person rici    schedule 24.09.2013