У меня есть следующие грамматики, которые я сказал в LR (1), но не SLR (1):Как это грамматика LR (1), но не SLR (1)?
S :: = а A | b A c | d c | б г а
:: = d
Я не понимаю, почему это происходит. Как бы вы это доказали?
Один из способов понять это - попытаться построить парсер LR (1) и SLR (1) для грамматики. Если мы найдем любые сдвиги/сокращения или сокращения/сокращения конфликтов при этом, мы можем показать, что грамматика не должна принадлежать одному из этих классов языков.
Начнем с анализатора SLR (1). Во-первых, нам нужно вычислить LR (0) конфигурационные множества для грамматики. Они рассматриваются здесь:
(1)
S -> .aA
S -> .bAc
S -> .dc
S -> .bda
(2)
S -> a.A
A -> .d
(3)
S -> aA.
(4)
A -> d.
(5)
S -> b.Ac
S -> b.da
A -> .d
(6)
S -> bA.c
(7)
S -> bAc.
(8)
S -> bd.a
A -> d.
(9)
S -> bda.
(10)
S -> d.c
(11)
S -> dc.
Далее, мы должны получить наборы Следования всех нетерминалов. Это показано здесь:
FOLLOW(S) = { $ }
FOLLOW(A) = { $, c }
Учитывая это, мы можем вернуться назад и обновить LR (0) конфигурированием наборов в SLR (1) конфигурированием наборов:
(1)
S -> .aA [ $ ]
S -> .bAc [ $ ]
S -> .dc [ $ ]
S -> .bda [ $ ]
(2)
S -> a.A [ $ ]
A -> .d [ $, c ]
(3)
S -> aA. [ $ ]
(4)
A -> d. [ $, c ]
(5)
S -> b.Ac [ $ ]
S -> b.da [ $ ]
A -> .d [ $, c ]
(6)
S -> bA.c [ $ ]
(7)
S -> bAc. [ $ ]
(8)
S -> bd.a [ $ ]
A -> d. [ $, c ]
(9)
S -> bda. [ $ ]
(10)
S -> d.c [ $ ]
(11)
S -> dc. [ $ ]
Интересно, что нет никаких конфликтов Вот! Единственный возможный конфликт смены/сокращения находится в состоянии (8), но здесь нет конфликта, потому что действие сдвига находится на a, а уменьшение - на $. Следовательно, эта грамматика фактически - SLR (1). Поскольку любая грамматика SLR (1) также является LR (1), это означает, что грамматика является как SLR (1), так и LR (1).
Надеюсь, это поможет!
Просто отметьте, что каждая грамматика SLR (1) является грамматикой LR (1), но не все LR (1) является SLR (1) –
Если вы ищете пример, вы можете использовать эту грамматику: '1) S -> XX 2) X -> аХ 3) X -> b' –
@templatetypedef, что, если это был бы АРП. [$] в состоянии 8. Будет ли сокращение сокращения конфликтов? Потому что у нас есть только один следующий символ, который является общим. – Zephyr
не хватает кармы прокомментировать выше ответ, и я немного опоздал на этот вопрос, но ...
Я видел эту грамматику в качестве примера в другом месте и О.П. фактически сделал опечатку. Это должно быть:
S :: = A a | b A c | d c | б г а
:: = д
т.е. самый первый раздел S является ' а', а не 'а '.
В это случае НИЖЕСЛЕДУЮЩЕМ набор для А {$, а, с} и есть зеркальная конфликт в состоянии 8.
Если вы собираетесь сделать карьеру в компьютерном бизнесе, вам нужно научиться читать, когда вы ничего не знаете. Внимательно прочитайте Википедию на языках LR и продумайте это.Если потребуется некоторое время, чтобы смотреть на него и понимать, пусть будет так; это типично. http://en.wikipedia.org/wiki/LR_parser –
Спасибо, вы были очень полезны! –
В ужасном виде, да: -} –