Ответ 1
Чтобы проверить, является ли грамматика LL (1), одним из вариантов является создание таблицы разбора LL (1) и проверка любых конфликтов. Эти конфликты могут быть
- FIRST/FIRST конфликты, где должны быть предсказаны две разные постановки для пары с нетерминальной/конечной.
- FIRST/FOLLOW, где прогнозируются две разные постановки, одна из которых означает, что необходимо произвести некоторую продукцию и расширить ее до ненулевого числа символов, а один из них означает, что следует использовать производство, указывающее на то, что некоторые нетерминалы должны быть в конечном счете расширены в пустую строку.
- конфликты FOLLOW/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 →., мы не можем определить, следует ли уменьшить пустую строку до этих символов или сдвинуть какой-то другой символ. В более общем смысле, никакая грамматика с & epsilon -productions не является 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) был устранен, потому что мы уменьшаем только тогда, когда lookahead равен z, что не конфликтует ни с одним из других элементов. Точно так же конфликт в (6) ушел по той же причине.
Надеюсь, это поможет!