1. Descreva as tarefas efetuadas pelos seguintes programas, e explique como eles se assemelham ou se relacionam a compiladores:
2. Explique qual a relação e para que servem expressões regulares, autômatos finitos, tokens e lexemas.
3. Construa um autômato finito para aceitar as palavras reservadas case, char, const e continue.
4. Considere os tokens:
Escreva regras usando expressões regulares e desenhe um autômato finito para reconhecer os tokens acima.
5. Numerais hexadecimais são usados em muitas linguagens de programação, e são escritos com o prefixo 0x ou 0X seguido de dígitos hexadecimais, 0-9 e a-f ou A-F. Ex: 0x80, 0xDEADBEEF, 0X42acB, 0xF.
6. Qual o problema causado por aninhamento de comentários em um analisador léxico gerado a partir de expressões regulares?
7. O seguinte trecho de código Java é responsável por ler e ignorar comentários em um analisador léxico de Pascal escrito à mão:
Como você reescreveria esse trecho para permitir comentários aninhados? Você pode definir métodos auxiliares. Dica: pense em um analisador sintático recursivo.
8. Escreva uma gramática sem ambiguidades que gere o conjunto de cadeias de caracteres {s;, s;s;, s;s;s;, …}.
9. Dada a gramática (o caractere | separa as regras do mesmo não-terminal): |
Descreva a linguagem que ela gera, e mostre que ela é ambígua.
10. Dada a gramática:
Escreva derivações e árvores sintáticas para as expressões a seguir (assuma que os numerais são instâncias do terminal num):
11. Escreva uma gramática para expressões boolenas contendo as constantes true e false e os operadores &&, || e !, além de parênteses. O operador || tem precedência menor que &&, e este menor que !. A gramática não pode ser ambígua.
12. Desafio! Mostre que a seguinte tentativa de resolução da ambiguidade do else ainda é ambígua:
13. Sinais de subtração unários podem ser acrescentados de diferentes maneiras a uma gramática de expressões aritméticas. Modifique a gramática da questão 10 de acordo com cada uma das especificações abaixo:
14. Na gramática a seguir os não-terminais estão em maiúsculas e os terminais em minúsculas, todos separados por espaços (estilo BNF):
Mostre a árvore sintática para o programa a seguir (pode abreviar os não-terminais assim: P, L, C, E, T):
15. A gramática a seguir descreve um subconjunto das expressões regulares (o
|
do lado direito da primeira regra é o token do operador |):
(ab|b)*
.Reescreva essa gramática para não ser mais ambígua, corrigindo as precedências dos operadores. Lembre-se que a concatenação tem precedência sobre o | , e a repetição (*) tem precedência sobre esses dois. Faça a operação de concatenação ser associativa à direita. |
16. Dada a gramática A -> (A)A | *vazio*
, escreva pseudocódigo para
analisá-la de forma recursiva com retrocesso local e sem retrocesso (LL(1)).
17. Uma gramática LL(1) pode ser ambígua? Justifique.
18. Uma gramática não ambígua precisa ser LL(1)? Justifique.
19. Dadas as duas gramáticas a seguir:
Remova a recursão esquerda, caso seja necessário, e escreva pseudo-código para um analisador recursivo para elas.
20. Dada a gramática:
21. Da a gramática A -> aAa | *vazio*
, demostre que essa gramática
não é LL(1), e mostre que o código a seguir não implementa corretamente
um analisador recursivo para essa gramática:
22. Considere a gramática a seguir, para um fragmento de Pascal:
Reescreva essa gramática para eliminar recursão à esquerda e prefixos comuns.
Última Atualização: 2016-05-18 10:58