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

Question

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

Answer 1

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

1. S → E.
2. Е → 1 е
3. E → 1.

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

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

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

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

Для другого примера грамматики это SLR (1), а не LR (0), см. Фегарас Примечания для CSE 5317/4305 В Университете Техаса.