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

Question

Я новичок в теме компиляции и только что начал упражнение по восходящему анализу.

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

создайте таблицу синтаксического анализа 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-файле или я где-то ошибся в понимании концепции?

Answer 1

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

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

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

Answer 2

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

Так что я на самом деле был бы

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

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