Чтобы проверить, является ли грамматика LL (1), одним из вариантов является создание таблицы синтаксического анализа LL (1) и проверка на наличие конфликтов.Эти конфликты могут быть
- ПЕРВОЕ / ПЕРВЫЕ конфликты, когда для нетерминальной / терминальной пары должно быть предсказано два разных производства.
- ПЕРВЫЙ / СЛЕДУЮЩИЙ конфликты, где два разных производствапредсказанный, один, представляющий, что некоторая продукция должна быть взята, и расширяется до ненулевого числа символов, а другой, представляющий, что продукция должна использоваться, указывая, что некоторая нетерминальная часть должна быть в конечном итоге расширена до пустой строки.
- СЛЕДОВАТЬ/ FOLLOW конфликтует, когда два произведения, указывающие на то, что нетерминал в конечном итоге должен быть расширен до пустой строки, конфликтуют друг с другом.
Давайте попробуем это на вашей грамматике, построив наборы FIRST и FOLLOW для каждого изнетерминалы.Здесь мы получаем, что
FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon}
У нас также есть следующие наборы FOLLOW:
FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}
Из этого мы можем построить следующую таблицу синтаксического анализа LL (1):
a b z $
X a Yz Yz
Y bZ eps
Z eps
Поскольку мы можем построить эту таблицу синтаксического анализа без конфликтов, грамматика будет LL (1).
Чтобы проверить, является ли грамматика LR (0) или SLR (1), мы начнем с построениявсе наборы конфигурации LR (0) для грамматики.В этом случае, предполагая, что X является вашим начальным символом, мы получаем следующее:
(1)
X' -> .X
X -> .Yz
X -> .a
Y -> .
Y -> .bZ
(2)
X' -> X.
(3)
X -> Y.z
(4)
X -> Yz.
(5)
X -> a.
(6)
Y -> b.Z
Z -> .
(7)
Y -> bZ.
Из этого мы можем видеть, что грамматика не является LR (0), потому что в состояниях есть конфликты сдвига / уменьшения(1) и (6).В частности, потому что у нас есть элементы сокращения Z →.и Y →., мы не можем сказать, уменьшать ли пустую строку до этих символов или сдвигать какой-либо другой символ.В более общем смысле, грамматика с ε-продукцией не является LR (0).
Однако эта грамматика может быть SLR (1).Чтобы увидеть это, мы дополняем каждое сокращение предустановкой для определенных нетерминалов.Это возвращает этот набор конфигурационных наборов SLR (1):
(1)
X' -> .X
X -> .Yz [$]
X -> .a [$]
Y -> . [z]
Y -> .bZ [z]
(2)
X' -> X.
(3)
X -> Y.z [$]
(4)
X -> Yz. [$]
(5)
X -> a. [$]
(6)
Y -> b.Z [z]
Z -> . [z]
(7)
Y -> bZ. [z]
Теперь у нас больше нет конфликтов смещением-уменьшением.Конфликт в состоянии (1) был устранен, потому что мы уменьшаем его только тогда, когда обращаемся к z, что не конфликтует ни с одним из других элементов.Точно так же конфликт в (6) исчез по той же причине.
Надеюсь, это поможет!