Lista de exercicios 1a - Compiladores - 2018 - 2o sem

Prévia do material em texto

Graduação em Ciência da Computação
Disciplina: Compiladores
Professor: Walace de Almeida Rodrigues
Atividades: 1a Lista de Exercícios
Esses exercícios foram selecionados como apoio para revisão do conteúdo da disciplina.
Exercício 1. Construa uma GLC para cada uma das linguagens abaixo:
1. L1 = { aibjck | i = j ou j = k, com i, j, k > 0 }
2. L2 = { aiajbjci | i > 0 e j >= 0 }
3. L3 = { ai(b+ ca ∗ b+)jakcj | i = j ou j = k, com i, j, k > 0 }
Exercício 2. Mostre que a GLC abaixo é ambígua.
<comando>* ::= <simples> | <composto>
<simples> ::= <se> | <outro>
<se> ::= ’if ’ ’(’ <exp> ’)’ <comando>
| ’if ’ ’(’ <exp> ’)’ <comando> ’else’ <comando>
<exp> ::= ’true’ | ’false’
<outro> ::= ’com’ ’;’
<composto> ::= ’{’ <lista-comandos> ’}’
<lista-comandos> ::= <comando> <lista-comandos> | λ
Exercício 3. (Questão de prova em 2003) Construa uma GLC não ambígua para gerar
qualquer lista de identificadores seguindo o formato da linguagem LISP. Exemplos:
(a a a a) ( ) (a ( ) a a) ( ( ) ( ) ) (a (a a (a)) a) etc.
Exercício 4. (Questão de prova em 2004) Construa uma GLC não ambígua para gerar
expressões aritméticas infixadas envolvendo identificadores e números (ambos terminais). As
expressões geradas devem incluir os operadores +, -, *, /, mod, div, **. Inclua também
o uso dos parênteses e os operadores unários + e -. Considere que os operadores unários
têm a precedência mais alta, seguidos do operador de exponenciação, depois os operadores
de multiplicação e divisão (que incluem o mod e o div) e, por fim, os operadores de soma
e subtração (que têm a precedência mais baixa). Esses operadores são todos associativos
à esquerda, com exceção dos operadores unários e de exponenciação que são associativos à
direita.
Exercício 5. Considere a GLC G = (N,Σ, P, S) onde:
N = { Cad, Meio },
Σ = { a , b }
P = { Cad → a b, Cad → a Meio b, Meio → a Meio,
Meio → Meio b, Meio → a, Meio → b }
S = Cad
Qual a linguagem gerada por essa gramática? Ela é ambígüa ou não? Por que?
1
Exercício 6. Considere a GLC descrita pelas produções:
S ::= X Y
X ::= B
Y ::= λ
B ::= Y A
A ::= A A | C | D
C ::= ’0’
D ::= ’1’
E ::= X
Construa uma GLC equivalente simplificada e verifique se a gramática resultante é ambígüa.
Se for, encontre uma gramática não ambígüa equivalente.
Exercício 7. Construa uma expressão regular para reconhecer as cadeias especificadas abaixo:
(a) endereços de email (considere apenas endereços formados por identificadores de letras
separados por pontos). Exemplo: tux.roxo@terra.com.br
(b) números em Pascal. Exemplos: 12 ou 3.1416 ou -34.12378E+14
Exercício 8. (Questão de prova em 2005) Construa uma GLC para gerar todas as palavras
da língua Yan da tribo Nhan. Todos os lingüistas concordam que a língua yanica não é
complicada. Sabe-se que o alfabeto yanico é composto das vogais { a, u, o }mais as consoantes
{ d, g, h }. As palavras dessa língua são formadas por seqüências de sílabas. As sílabas
yanicas são constituídas por uma vogal, ou, alguma consoante seguida de uma vogal. Uma
pequena reforma ortográfica também introduziu nessa língua o uso de algumas sílabas especiais
formadas por uma consoante seguida de um ditongo yanico (um ditongo é formado por duas
vogais). As normas da gramática yanica, contudo, exigem que nenhuma palavra contenha
mais de um ditongo. Na língua yanica todos os ditongos são tônicos, e todas as as sílabas
formadas por uma única vogal são hiatos, portanto, duas sílabas de uma única vogal nunca
constituem um ditongo.
Exercício 9. (1o semestre de 2003) Construa uma GLC não ambígua para gerar expressões
infixadas de lógica ternária (que trabalha com os valores true, false, unknow) envolvendo
identificadores e números (ambos terminais), mais as expressões relacionais simples envolvendo
os operadores >, >=, <, <=, <>, = com seus dois operandos inteiros. As expressões lógicas
geradas devem incluir os operadores not, or, and, xor, equiv, or-else, and-then e também o
uso dos parênteses. Considere que o operador unário not tem a precedência mais alta, seguido
do operador equiv. Seguem os operadores or e and, depois o operador xor e, finalmente, os
operadores or-else e and-then (que têm a precedência mais baixa). Esses operadores são todos
associativos à esquerda, com exceção do operador not que é associativo à direita.
Exercício 10. (2o semestre de 2003) Seja G a seguinte gramática:
E ::= ’zip’ E E
| E E ’zoin’
| E ’zup’ E
| E ’zap’ E
| ’(’ E ’)’
| ’id’
Transforme as produções acima de modo a tornar a gramática G não ambígua ao expressar
a precedência e a associatividade dos operadores. Considere que os operadores zip e zup
são associativos à direita e os operadores zap e zoin são associativos à esquerda. Considere
também que a precedência dos operadores, por ordem crescente, é: zip, zup, zoin, zap.
2
Exercício 11. (2o semestre de 2003) Determine os conjuntos First(X) e Follow(X) para cada
não-teminal da gramática G com não-terminal de partida S apresentada a seguir:
S ::= A ’x’ A ’x’ A
A ::= ’y’ A ’y’ | ’w’ A ’w’ | B | λ
B ::= B A C | ’z’
C ::= ’k’ C ’k’ | A
Exercício 12. (2o semestre de 2004) Construa uma GLC, não ambígua, para gerar expressões
aritméticas envolvendo os dígitos (os tokens 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) e os quatro operadores
&, %, # e $. Considere que o operador $ é unário, posfixado, tem maior precedência e é
associativo à esquerda. Considere que o operador # é binário, posfixado, tem precedência
menor que o operador $, e também é associativo à esquerda. Considere que os operadores %
e & são binários, prefixados, de precedência menor que os operadores anteriores, associativo
à direita. Considere ainda o uso dos parênteses. Por fim, construa a árvore gramatical para
a expressão “8 ( % % 4 5 4 6 $ # ) #”.
Exercício 13. (2o semestre de 2004) Determine os conjuntos First(X) e Follow(X) para cada
não-teminal da gramática G com não-terminal de partida S apresentada a seguir:
S ::= A B C D A
A ::= ’x’ A ’x’ | ’y’ | λ
B ::= ’a’ B ’b’ | ’b’
C ::= ’c’ C A | ’d’
D ::= C B ’x’ | B A
Exercício 14. (2o semestre de 2004) Determine os conjuntos First(X) e Follow(X) para cada
não-teminal da gramática G com não-terminal de partida S apresentada a seguir:
S ::= A B B C C A
A ::= ’a’ A ’x’ | λ
B ::= ’a’ B | ’b’
C ::= ’c’ C | ’d’
Exercício 15. (2o semestre de 2004) Aplicações das tabelas de First e Follow: Considere
dados uma gramática G livre de contexto e a relação completa dos conjuntos First(X) e
Follow(X) para os não-terminais de G. É possível determinar, partindo destes dados, se a
gramática G pode ou não ser utilizada por um parser top-down preditivo? Como?
Bom Estudo
3