Является ли эта грамматика LR(1)?

Немного смущен тем, является ли эта грамматика неоднозначной или нет

C' -> C
C -> d C u C
C -> d C
C -> ε

Я попытался создать DFA для этого, но я получаю это в одном из состояний:

C -> d C DOT u C, $
C -> d C DOT, $

Разве это не конфликт сдвига-уменьшения, так что, конечно, это означает, что грамматика не LR (1)? Или он уменьшается независимо от того, поскольку $ и u оба находятся в следующем наборе C?


parsing compiler-construction grammar lr context-free-grammar
person Adam Hasan    schedule 28.03.2015    source источник
comment
Этот вопрос относится к cs.stackexchange.com   -  person titaniumdecoy    schedule 28.03.2015
comment
Если вы пишете компиляторы, это отличный вопрос для программирования.   -  person Gene    schedule 28.03.2015
comment
Я согласен с Геной. Аналогичный вопрос по программированию: я изучил свой код. Я вижу место, которое выглядит подозрительно. Могу ли я получить там ошибку нижнего индекса или есть правило, которое я должен знать, которое предотвращает это?   -  person Ira Baxter    schedule 28.03.2015

Ответы (1)


arrow_upward
3
arrow_downward

У него есть конфликт сдвига-уменьшения. Вот конечный автомат, созданный выбором смены. Конфликт находится в состоянии 4. state machine

Я должен отметить, что ваш вопрос немного не в порядке. Грамматика может быть однозначной и все же не LR(1).

Но это оказывается доказуемо двусмысленным. Рассмотрим строку ddudu. Два крайних левых вывода

C'->C->dCuC->ddCuCuC->dduCuC->ddudCuC->dduduC->ddudu
C'->C->dCuC->ddCuC->dduC->ddudCuC->dduduC->ddudu

Их существование говорит о том, что грамматика неоднозначна.

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

person Gene    schedule 28.03.2015
comment
Из любопытства, что вы использовали для построения графика? - person Martin Törnwall; 28.03.2015
comment
bison для создания vcg-файла и yComp для его рисования. - person Gene; 28.03.2015