Como é esta gramática LL (1)?

12

Esta é uma pergunta do Dragon Book. Esta é a gramática:

SAaAbBbBa
Aε
Bε

A pergunta pergunta como mostrar que é LL (1), mas não SLR (1).

Para provar que é LL (1), tentei construir sua tabela de análise, mas estou obtendo várias produções em uma célula, o que é contradição.

Por favor, diga como é este LL (1) e como provar isso?

Vinayak Garg
fonte
6
Não conheço muito as gramáticas, mas parece que a linguagem dessa gramática é finita. L={ab,ba}
Nejc
@ Nejc: Sim, parece que sim!
Vinayak Garg

Respostas:

11

Primeiro, vamos dar um número às suas produções.

1 2 S B b B a 3 A ε 4 B εSAaAb
SBbBa
Aε
Bε

Vamos calcular o primeiro e seguir os conjuntos primeiro. Para pequenos exemplos como esses, usar a intuição sobre esses conjuntos é suficiente.

FIRST(S)={a,b}FIRST(A)={}FIRST(B)={}FOLLOW(A)={a,b}FOLLOW(B)={a,b}

Agora vamos calcular a tabela . Por definição, se não temos conflitos, a gramática é L L ( 1 ) .LL(1)LL(1)

    a | b |
-----------
S | 1 | 2 |
A | 3 | 3 |
B | 4 | 4 |

Como não há conflitos, a gramática é .LL(1)

Agora, para a tabela . Em primeiro lugar, o G R ( 0 ) autómato.SLR(1)LR(0)

state 0SAaAbSBbBaABA1B5
state 1SAaAba2
state 2SAaAbAA3
state 3SAaAbb4
state 4SAaAbb
state 5SBbBab6
state 6SBbBaBB7
state 7SBbBaa8
state 8SBbBa

E então a tabela (presumo que S possa ser seguido por qualquer coisa).SLR(1)S

    a     | b     | A | B |
---------------------------
0 | R3/R4 | R3/R4 | 1 | 5 |
1 | S2    |       |   |   |
2 | R3    | R3    | 3 |   |
3 |       | S4    |   |   |
4 | R1    | R1    |   |   |
5 |       | S4    |   |   |
6 | R4    | R4    |   | 7 |
7 | S8    |       |   |   |
8 | R2    | R2    |   |   |

Existem conflitos no estado 0, então a gramática não é . Note-se que se L A L R ( 1 ) foi utilizado em vez disso, em seguida, ambos os conflitos seria resolvido correctamente: no estado 0 em antecipação um G Um G R ( 1 ) levaria R3 e em antecipação b levaria R4.SLR(1)LALR(1)a LALR(1)b

Isso suscita a questão interessante de saber se existe uma gramática mas não L A L R ( 1 ) , que é o caso, mas não é fácil encontrar um exemplo.LL(1)LALR(1)

Alex ten Brink
fonte
Obrigado! Eu havia construído o First & Follow corretamente, mas cometi um erro ao construir a tabela.
Vinayak Garg
10

Se você não for solicitado, não precisará construir a tabela LL (1) para provar que é uma gramática LL (1). Você apenas calcula os conjuntos PRIMEIRO / SEGUINTE como Alex fez:

FIRST(S)=a,bFIRST(A)=εFIRST(B)=εFOLLOW(A)=a,bFOLLOW(B)=a,b

E então, por definição, uma gramática LL (1) deve:

  1. Se e A b são duas regras diferentes da gramática, então deve ser que PRIMEIRO ( a ) PRIMEIRO ( b ) = . Portanto, os dois conjuntos não têm nenhum elemento comum.AaAbFIRST(a)FIRST(b)=
  2. Se por qualquer símbolo não-terminal você tem alfa * ε , então ele deve ser que PRIMEIRO ( A ) FOLLOW ( A ) = . Portanto, se houver uma produção zero para um símbolo não terminal, os conjuntos PRIMEIRO e SEGUINTE não poderão ter nenhum elemento comum.AΑεFIRST(A)FOLLOW(A)=

Então, para a gramática dada:

  1. Temos desde PRIMEIRO ( A a A b ) = { a } enquanto PRIMEIRO ( B b B a ) = { b } e eles não têm nenhum elementos comuns.FIRST(AaAb)FIRST(BbBa)=FIRST(AaAb)={a}FIRST(BbBa)={b}
  2. desde PRIMEIRO ( A ) = { a , b } enquanto SEGUIR ( A ) = , e agora PRIMEIRO ( B ) SEGUIR ( B ) = desde PRIMEIRO ( B ) = { ε } enquanto SEGUIR ( B ) = {FIRST(A)FOLLOWA)=FIRST(A)={a,b}FOLLOW(A)=FIRST(B)FOLLOW(B)=FIRST(B)={ε} .FOLLOW(B)={a,b}

Quanto à análise SLR (1), acho que é perfeita!

Ethan
fonte
Bem-vinda! Para melhorar essa resposta, por que você não aplica o que afirma à gramática em questão?
Raphael
Feliz por estar aqui!! Respondeu ao seu pedido e acho que dei uma explicação completa!
Ethan
Obrigado! Observe que podemos usar o LaTeX aqui, como eu editei na sua matemática.
Raphael
Uau, obrigado! Esta é uma ótima explicação. Mas acho que há algum erro na aplicação. Não é o primeiro (A) = {epsilon}? Eu acho que você trocou o PRIMEIRO e SEGUIR.
Vinayak Garg
PRIMEIRO (A) é realmente epsilon, mas como você deseja calcular o PRIMEIRO conjunto do membro certo, A -> ε mostra que temos uma produção vazia e o primeiro símbolo de terminal que você vê (e, portanto, o PRIMEIRO conjunto) é símbolo do terminal a. Espero que isso tenha ajudado!
Ethan
0

Procure uma condição suficiente que faça uma gramática LL (1) (dica: veja os PRIMEIROS conjuntos).

Procure uma condição necessária que todas as gramáticas SLR (1) devem atender (dica: veja os conjuntos de SEGUINTES).

AProgrammer
fonte