Em ordem cronológica reversa.
PR são bem-vindos para popular esta página.
- Sim,
a*|bc. - Não foi, sendo a principal razão o fato que o estado 4 une
diretamente os reconhecedores de
ced. Deveríamos ter uma transição vazia entre o atual estado 4 e um novo estado que inicia o reconhecimento doc. Podemos também mencionar a ausência da marcação de um estado final, ainda que o estado14possa ser considerado como final. - Fech-ε(0) = {0, 1, 2, 3, 6, 7, 8, 9, 10, 12, 13, 14} = A;
- Considerando que devemos aplicar o Fech-ε após um movimento, podemos entender que a resposta é Fech-ε(Mov(A, a)) = {11, 12, 13, 14, 8, 9, 10};
- Podemos empregar ellerre para obter a resposta.
echo'S => A B ;A => a | b | c C a | C ;B => a | b | ;C => b | c | d | ;'> gramatica.ee ./firstfollow < gramatica.ee
Grammar with 12 rules and 8 symbols (4 non-terminals): S ⇒ A B A ⇒ a A ⇒ b A ⇒ c C a A ⇒ C B ⇒ a B ⇒ b B ⇒ ε C ⇒ b C ⇒ c C ⇒ d C ⇒ ε First sets: S -- ε b d a c A -- ε b d a c B -- ε b a C -- ε b d c Follow sets: S -- $ A -- $ b a B -- $ C -- $ b a
- Analisando a gramática fornecida, podemos concluir que a gramática
não é LL(1) pois (a) o conjunto Pri(cCa) tem intersecção com o
conjunto Pri(C), com o token
c; (b) o conjunto Seq(C) tem intersecção com o conjunto Pri(b). - A tabela criada
a b c d $ S AB AB AB AB AB A a b cCa C C C C C C B a b ε C b c d ε ε ε - Os passos são os seguintes (o
%marca final da pilha e entrada)/ <r> <r> <l> Pilha Entrada Ação S % % S -> AB AB % % A -> C CB % % C -> ε B % % B -> ε % % aceita - Os passos são os seguintes (idem com o
%)/ <r> <r> <l> Pilha Entrada Ação S % acda % S -> AB AB % acda % conflito entre A -> C e A -> a
- Vamos empregar ellerre para obter a resposta.
echo'S => a [ L ] | a ;L => S - L | S ;'> gramatica.ee ./lr0 < gramatica.ee > /dev/null ./firstfollow < gramatica.ee dot -Tpng LR0.dot -o resp_2023_1-E3-LR0.png
Grammar with 4 rules and 6 symbols (2 non-terminals): S ⇒ a [ L ] S ⇒ a L ⇒ S - L L ⇒ S First sets: S -- a L -- a Follow sets: S -- $ ] - L -- ]
Considere que na resposta poderíamos ter apenas os estados do 0 ao 3.
- A gramática não é LR(0) pois nos estados 2 e 4 temos itens completos junto com itens de empilhamento. Em LR(0) isso não é possível pois acaba por causar um conflito empilha-reduz.
- No caso do estado 2, a heurística de usar o conjunto sequência do
símbolo para o qual iremos reduzir resolve o conflito pois Seq(S)
contém apenas
a, e não temos transição comaa partir do estado 2. A mesma justificativa pode ser usado no estado 4 ao observar o Seq(L).
- A gramática não é LR(0) pois no esado 4 temos um conflito empilha-reduz ao observar um item completo juntamente com um item que implica em empilhamento.
- Para responder se a gramática é SLR(1), precisamos do conjunto
sequência dos NTs. Vamos empregar ellerre para obter a resposta.
echo'F => [ a ] | [ a ] - F ;'> gramatica.ee ./firstfollow < gramatica.ee
Grammar with 2 rules and 5 symbols (1 non-terminals): F ⇒ [ a ] F ⇒ [ a ] - F First sets: F -- [ Follow sets: F -- $
Observamos que no conjunto Seq(F) temos apenas o $, portanto a gramática é SLR(1) uma vez que o conflito empilha-reduz do estado 4 desaparece visto que a redução para F só ocorrerá com
$na entrada. - A tabela SLR(1), usando a heurística do conjunto sequência na redução
/ < > [ a ] - $ F 0 2 1 1 aceita 2 3 3 4 4 5 R 5 2 6 6 R - A análise LR usando a tabela SLR(1) acima. Novamente o
%marca o final da pilha e da entrada./ <l> <r> Pilha Entrada Ação % 0 [a]-[a] % 2 % 0 2 a]-[a] % 3 % 0 2 3 ]-[a] % 4 % 0 2 3 4 -[a] % 5 % 0 2 3 4 5 [a] % 2 % 0 2 3 4 5 2 a] % 3 % 0 2 3 4 5 2 3 ] % 4 % 0 2 3 4 5 2 3 4 % R por F -> [a] % 0 2 3 4 5 % desempilha três estados (pois são três símbolos no corpo) % 0 2 3 4 5 % Como voltamos para o estado 5 e acabamos de reduzir para F, 6 % 0 2 3 4 5 6 % R por F -> [a]-F % 0 % desempilha cinco estado (pois são cinco símbolos no corpo) % 0 % Como voltamos para o estado 0 e acabamos de reduzir para F, 1 % 0 1 % aceita
- A gramática não é LR(1) pois no estado 4 temos um conflito
empilha-reduz com
a, uma vez que temos um item completo indicando redução comaao mesmo que temos que temos uma transição coma.
- Sim, os estados que reconhecem os caracteres ‘a’, ‘b’ e ‘c’ estão devidamente isolados com produções vazias, possuindo um alternância entre ‘ab’ e ‘c’ e então um laço de repetição
Fech-\epsilon (1) = {1, 2, 3, 7} = |A|
Mov(A, a) = {4, 5} = |B|
Mov(A, b) = {}
Mov(A, c) = {8, 9, >10<, 1, 2, 3, 7} = |C|
Mov(B, a) = {}
Mov(B, b) = {6, 9, >10<, 1, 2, 3, 7} = |D|
Mov(B, c) = {}
Mov(C, a) = {4, 5} = |B|
Mov(C, b) = {}
Mov(C, c) = {8, 9, >10<, 1, 2, 3, 7} = |C|
Mov(D, a) = {4, 5} = |B|
Mov(D, b) = {}
Mov(D, c) = {8, 9, >10<, 1, 2, 3, 7} = |C|
Gerando o automato:
Recursão à esquerda:
S->Sa A->Ac
O estado A teria 2 produções com o ‘d’ pois ‘d’ é parte de Primeiro(A)
A->Ac A->d
2.
A->bAX X->aX X->ε A->dB B->cB B->ε
Tabela LL(1):
| a | b | c | d | $ | |
|---|---|---|---|---|---|
| S | bAX | ||||
| X | aX | ε | |||
| A | dB | ||||
| B | ε | b | cB | ε |
Passos Análise LL(1):
| / | <r> | <r> | <l> |
| Pilha | Entrada | Ação | |
|---|---|---|---|
| S% | bdcaa% | S -> bAX | |
| bAX% | bdcaa% | casa | |
| AX% | dcaa% | A -> dB | |
| dBX% | dcaa% | casa | |
| BX% | caa% | B -> cB | |
| cBX% | caa% | casa | |
| BX% | aa% | B -> ε | |
| X% | aa% | X -> aX | |
| aX% | aa% | casa | |
| X% | a% | X -> aX | |
| aX% | a% | casa | |
| X% | % | X -> ε | |
| % | % | aceita |
LR(0):
LR(1):
- Não é LR(0) devido a conflito empilha-reduz no estado 6 (possui um item finalizado e este não está isolado)
- Não é SLR(1), pois ‘f’ pertence à Sequência(C) (por causa da produção A->bCf) e há presença de um empilhamento de ‘f’ que vai para o estado 8, logo no estado 6 há conflito empilha-reduz
- É LR(1), pois todos os itens finais estão em estados:
- ou que tem eles isolados (estados 1, 4, 5, 8)
- ou cujos empilhamentos não estão no token de look-ahead (estado 6)
- ou possuem tokens de look-ahead diferentes de outros estados finais (estado 7)
| Primeiro | Sequência | |
|---|---|---|
| S | u | $ |
| B | v,ε | y,x,z |
| D | x,y,ε | z |
| E | y,ε | x,z |
| F | x,ε | z |