Может ли грамматика быть проанализирована с помощью LL(1), но не с помощью LR(1)?

В качестве домашнего задания мне дали следующую грамматику:

S: D
D: AbBb | BaAb
A: ε 
B: ε

Я вычислил это с помощью LL (1) просто отлично. Первые наборы были:

S: a, b
D: a,b
A: ε 
B: ε

Были следующие наборы:

S: $
D: $
A: b
B: a,b

Когда я сделал свою таблицу синтаксического анализа, пример строки «ab» был проанализирован просто отлично. Однако, когда я попытался разобрать точно такую ​​же грамматику с помощью LR(1), я столкнулся с ошибками.

Для набора элементов 0 я получил следующее: (разделяет терминалы просмотра вперед)

Item set 0:

S: .D, $
D: .AbBb, $ 
D: .BaAb, $
A: ., b
B: ., a,b

Если вы сделаете таблицу, вы ясно увидите, что существует конфликт уменьшения-уменьшения между A и B в наборе элементов 0. Если меня попросят проанализировать строку «ab», синтаксический анализатор не будет знать, следует ли уменьшить мой пустой до A или уменьшить до B. Что я делаю не так? Мне всегда говорили, что LR(1) на самом деле может анализировать больше грамматик, чем LL(1), так в чем тут дело? Я был бы признателен, если бы кто-нибудь мог мне помочь, потому что это сводит меня с ума. Спасибо


compiler-construction computability automata lr1
person Ryan Foster    schedule 04.11.2019    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Они заявляют, что вы сгенерировали код, похожий на парсер SLR(1).

Если вы используете LR(1) или даже LALR(1), вы обнаружите, что конфликтов нет. Вот, например, состояние 0 машины LALR(1), сгенерированное Bison:

Состояние 0

0 $accept: . S $end
1 S: . D
2 D: . A 'b' B 'b'
3  | . B 'a' A 'b'
4 A: . %empty  ['b']
5 B: . %empty  ['a']

'a'       reduce using rule 5 (B)
$default  reduce using rule 4 (A)

S  go to state 1
D  go to state 2
A  go to state 3
B  go to state 4

Хотя LL(1) ⊂ LR(1), безусловно, верно, между LL(1) и SLR(1) или LALR(1) нет простой связи. (Здесь я говорю о грамматиках. Для наборов языков отношения проще.) Ваша грамматика является достаточно простым примером LL(1) грамматики, которая не является SLR(1); пример грамматики LL(1), которая не является LALR(1), см. этот ответ.

person rici    schedule 04.11.2019
comment
Я в замешательстве, вы говорите, что состояния просмотра вперед для A и B - это ['a'] и ['b']? Кроме того, я узнал, что SLR(1) — это первый и последующие наборы грамматики. В то время как в LR(1) вы создаете первый и последующие наборы только для тех нетерминалов, которые вам нужны в процессе работы. Разве это не то, что я сделал во втором примере? - person Ryan Foster; 05.11.2019
comment
@ryan: это упреждающие наборы в этом состоянии, да. В конструкции LR(1) вы не используете наборы FOLLOW нетерминалов, вычисляемые для синтаксического анализа сверху вниз. Упреждающие наборы исходят из контекста, в котором нетерминал появляется в этом состоянии. - person rici; 05.11.2019
comment
@ryan: Вот хороший ответ с полностью проработанным упреждающим вычислением. - person rici; 05.11.2019
comment
Извините, позвольте мне перефразировать то, что я сказал. Я понимаю, что состояния просмотра вперед - это первые наборы нетерминала, на которые вы сейчас смотрите, а НЕ ПОСЛЕДУЮЩИЕ наборы. Однако я смущен тем, как прогнозы для нетерминала B - это просто «a», а не «a», «b». При взгляде на D -> .AbBb первым из B в этом случае будет «b». Если смотреть на D -> .BaAb, первым из B будет «a». Следовательно, не должны ли состояния просмотра вперед быть ОБА "a" и "b". Я в замешательстве. Благодарю. - person Ryan Foster; 05.11.2019
comment
@ryan: прогнозы - это не первые наборы нетерминалов, на которые вы смотрите. Это ПЕРВЫЕ наборы части правой части, следующей за нетерминалом (дополненные, при необходимости, опережением для элемента). В этом случае опережающим просмотром для A: . %empty является FIRST(bBb), который, очевидно, не содержит a. Это должно быть легко понять: опережающий набор для сокращения содержит терминалы, которые могут следовать за сокращением, и совершенно ясно, что сокращение A в этом состоянии может произойти только в том случае, если следующим терминалом будет b. - person rici; 05.11.2019
comment
@ryan: честно говоря, я думаю, что @templatetypedef объясняет это более ясно в ответе, который я дал выше. - person rici; 05.11.2019
comment
Думаю, теперь я понимаю. Что я делал, так это просматривал каждое появление нетерминала и вычислял его первые наборы. Например, для B я понял, что упреждающим является First(aAb), который есть a, но я также посмотрел на B в операторе над ним и вычислил First(b). Вот откуда у меня а, б. - person Ryan Foster; 05.11.2019
comment
@torek: ой, исправлено. - person rici; 07.11.2019