Решить, является ли грамматика LR(0) или нет

Я новичок в предмете компиляции и только что начал упражнение для анализа Bottom -up.

Я застрял на следующей проблеме.

построить таблицу анализа LR(0) для следующей грамматики:

1) E –> E + T
2) E –> T
3) T –> (E)
4) T –> id


I0 :

   E' –> .E
   E –> .E + T
   E –> .T
   T –> .(E)
   T –> .id

на E следующее состояние в DFA будет:

 I1:

    E' -> E.
    E  -> E. + T

из того, что я узнал до сих пор, не является ли это конфликтом эсеров? потому что синтаксический анализатор не будет знать, нужно ли уменьшать или сдвигать, так как он не имеет переменной упреждения? так что это не должно быть LR(0) грамматика?

но PDF, который я читаю, создал таблицу LR(0). Так есть ли ошибка в PDF или я ошибся в понимании концепции?

Источник

2 ответа

Решение

Это действительно конфликт сдвига / уменьшения. Эта грамматика не является LR(0). Вы также можете видеть это, потому что это не без префикса; грамматика содержит несколько строк, которые являются префиксами друг друга, поэтому она не может быть LR(0).

Тем не менее, вы все равно можете построить все конфигурационные множества LR (0) и сделать автомат LR(0). Это просто не будет детерминированным из-за конфликта сдвига / уменьшения. Поэтому возможно, что вы правы, а раздаточный материал прав.

Надеюсь это поможет!

Источник

Вы дополнили грамматику E' -> E, Как правило, вы увеличиваете с производством, как E' -> E $ где $ является (терминальным) символом, который иначе не встречается в грамматике и обозначает конец ввода.

Так что I1 будет на самом деле


E' -> E. $
E  -> E. + T

и нет конфликта. (И я считаю, что грамматика LR(0).)

Источник
Другие вопросы по тегам