Compiladores - Lista de Exercícios 3 - Resolução

Prévia do material em texto

Lista de Exercícios 3: Compiladores 
Prof André Luiz Teixeira Vinci 
 
 
1. Elimine a recursividade à esquerda, quando existir, para cada as 
seguintes regras gramaticais: 
comando : comando ';' listaComandos 
comando : comando ';' 'if' '(' expr ')' 'then' comando 
expr : expr '+' termo | expr '-' termo | termo 
termo : termo '*' fator | termo '/' fator | fator 
fator : fator '.' VAR | VAR 
comando : 'while' '(' expr ')' comando 'endwhile' 
listacomandos : '{' comando '}' 
Resolução: 
comando : 'while' '(' expr ')' comando 'endwhile' comando2 
comando2 : ';' listaComandos comando2 | ';' 'if' '(' expr ')' 'then' 
comando | <<vazio>> 
expr : termo expr2 
expr2 : '+' termo expr2 | '-' termo expr2 | <<vazio>> 
termo : fator termo2 
termo2 : '*' fator termo2 | '/' fator termo2 | <<vazio>> 
fator : VAR fator2 
fator2: '.' VAR fator2 | <<vazio>> 
listacomandos : '{' comando '}' 
 
2. Realize a fatoração à esquerda, se necessário, para o seguinte conjunto 
de regras gramaticais abaixo: 
comandoCondicao : 
'SE' expressaoRelacional 'ENTAO' comando 'FIMSE' | 
'SE' expressaoRelacional 'ENTAO' comando 'SENAO' comando 'FIMSE'; 
Resolução: 
comandoCondicao : 'SE' expressaoRelacional 'ENTAO' comando 
comandoSenao 'FIMSE' 
comandoSenao : 'SENAO' comando | <<vazio>> 
 
3. Remova a recursividade à esquerda modificando as regras gramaticais 
abaixo de forma a empregar EBNF. 
lexp : atomo | lista 
atomo : numero | identificador 
lista : '(' lexpseq ')' 
lexpseq : lexpseq lexp | lexp 
Resolução: 
lexp : atomo | lista 
atomo : numero | identificador 
lista : '(' lexp+ ')' 
 
4. Considere a seguinte gramática e elimine a recursividade à esquerda. 
S : ( L ) | a 
L : L,S | S 
Resolução: 
S : '(' L ')' | 'a' 
L : S L2 
L2 : ',' S L2 | <<vazio>> 
 
5. Considere a gramática do Exercício 3 e responda: 
a. A gramática é LL(1)? 
b. Se não, aplique as transformações necessárias para convertê-la 
em LL(1). 
Resolução: 
Não é LL(1), pois, há recursividade à esquerda. Removendo: 
lexp : atomo | lista 
atomo : numero | identificador 
lista : ( lexpseq ) 
lexpseq : lexp lexpseq2 
lexpseq2 : lexp lexpseq2 | ε 
 
6. Considerando a gramática é possível afirmar que ela é LL(K)? Justifique 
sua resposta. 
declaracao : nomeQualificado ‘:’ ID ‘;’ 
| nomeQualificado ‘:’ ID ‘=’ expressao; 
nomeQualificado : ID | ID ‘.’ nomeQualificado; 
Resolução: Não, pois não há nenhum valor mínimo de k tal que garantidamente seja 
possível determinar qual das duas produções da regra “declaração” utilizar. Isso porque 
a regra nomeQualificado tem recursividade, e portanto pode gerar nomes 
infinitamente grandes. 
 
7. Apresente as ações do analisador preditivo não recursivo correspondente 
para cada uma das cadeias de entrada abaixo. Utilize a tabela LL(1) 
fornecida e considere x, y e z como identificador e 2 como número. 
a. (x (y (2)) (z)) 
b. (x y 2)) (z)) 
c. (x y 2 
 numero identificador ( ) $ 
 
lexp lexp → atomo lexp → atomo lexp → lista 
 
atomo atomo → numero atomo → 
 identificador 
 
lista lista → ( 
 lexpseq ) 
 
lexpseq lexpseq → lexp lexpseq → lexp lexpseq → lexp 
 lexpseq2 lexpseq2 lexpseq2 
 
lexpseq2 lexpseq2 → lexp lexpseq2 → lexp lexpseq2 → lexp 
lexpseq2 
→ ε 
 lexpseq2 lexpseq2 lexpseq2 
 
 
Resolução: 
a. (x (y (2)) (z)) 
 
b. (x y 2)) (z)) 
 
 
c. (x y 2 
 
 
8. Realize a análise sintática LR para cada cadeia abaixo, apresentando 
uma tabela para cada passo dos valores da pilha, símbolos, cadeia e 
ação. Considere a gramática e tabela SLR fornecidas na sequência. 
a. ((id)) 
b. (id * id (id)) 
c. (id * ) id) 
d. id + id + id 
Gramática Enumerada Tabela SLR 
(1) E → E + T 
(2) E → T 
(3) T → T * F 
(4) T → F 
(5) F → (E) 
(6) F → id 
 
 
 
 
 
 
 
Estados Ações Transições 
id + * ( ) $ E T F 
0 s5 
 
s4 
 
1 2 3 
1 
 
s6 
 
OK 
 
2 
 
r2 s7 
 
r2 r2 
 
3 
 
r4 r4 
 
r4 r4 
 
4 s5 
 
s4 
 
8 2 3 
5 
 
r6 r6 
 
r6 r6 
 
6 s5 
 
s4 
 
9 3 
7 s5 
 
s4 
 
10 
8 
 
s6 
 
s11 
 
9 
 
r1 s7 
 
r1 r1 
 
10 
 
r3 r3 
 
r3 r3 
 
11 
 
r5 r5 
 
r5 r5 
 
Resolução: 
a. ((id)) 
 
b. (id * id (id)) 
 
c. (id * ) id) 
 
 
 
 
d. id + id + id