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

Question

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

Answer 1

В принципе, грамматика SLR (1) может разрешать конфликты сдвига, которые существуют в соответствующей грамматике LR (0). Возьмите пример грамматики на SLR parser странице Википедии (что объясняет это на более низком, более строгом уровне):

1. S → E
2. E → 1 E
3. E → 1

Когда парсер LR (0) анализирует E, а «1» является следующим входным символом, он может распознать E и уменьшить (правило 3) или он может сдвинуться для анализа следующего E (правило 2) , Поскольку он не может смотреть в будущее, LR (0) не может определить, что делать. Это становится все более очевидным, если мы посмотрим на items ЛР (0) может быть обработка, когда он сталкивается с «1» (символ конца из-строки было добавлено):

• E → 1 • E $
• E → 1 • $

Первый потребует сдвига, то вторая требует уменьшения.

С помощью вышеуказанной грамматики грамматика SLR (1) может смотреть вперед один символ и определять, какое действие нужно предпринять. E может следовать только $, поэтому действие уменьшения действительно только в конце строки. Это соответствует второму пункту, где вы можете увидеть следующий символ - «$».

Для другой пример грамматики, которая является зеркальной (1), а не LR (0), см. Fegaras 'notes for CSE 5317/4305 в Техасском университете.