Может ли грамматика когда-либо анализироваться LL (1), но не LR (1)? - PullRequest
Новая
       80

Может ли грамматика когда-либо анализироваться LL (1), но не LR (1)?

1 голос
/ 04 ноября 2019

Для домашней работы мне дали следующую грамматику: 

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», анализатор не будетзнаю, нужно ли уменьшить мою пустоту до А или уменьшить до Б. Что я делаю не так? Мне всегда говорили, что LR (1) может на самом деле анализировать больше грамматик, чем LL (1), так в чем же дело? Буду признателен, если кто-нибудь сможет мне помочь, потому что это сводит меня с ума. Спасибо

1 Ответ

2 голосов
/ 05 ноября 2019

Они утверждают, что вы сгенерировали его как парсер 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), см. в этом ответе .

...