Compiladores

Os exercícios desta seção são complementares àqueles que estão na apostila.

1.

Em uma certa linguagem, as constantes binárias inteiras são representadas pelos dígitos 0 e 1 seguidos ao final pelos símbolos ``b'' ou ``B''. Derive a regexp que reconhece tais constantes.

2.

Construa o AF determinístico otimizado (com número mínimo de estados) para a regexp do exercício anterior.

3.

Repita os dois exercícios anteriores para constantes binárias fracionárias.

4.

Realize a minimização de estados do seguinte autômato finito determinístico: clique aqui para obter o autômato.

5.

Modifique a regra gramatical abaixo para incluir operação de divisão e subtração.

E -> E + T
E -> T
T -> T x F
T -> F
F -> (E)
F -> id

6.

Utilizando esta nova regra, obtenha a derivação canônica de (id*id)/(id+id) e sua arvore gramatical:

a)usando derivação mais à esquerda

b)usando derivação mais à direita

7.

Crie um arquivo de especificações Lex que reconheça registros do seguinte formato:

- Nome da faculdade (em letras maiúsculas)

- RA (somente números)

- Nome (primeira letra maiúscula, as demais minúsculas)

- Disciplinas (apenas 2 letras maiúsculas e 3 algarismos)

Exemplo:

FEEC 031795 Jose da Silva EA876 MC505 MC102

8.

Descreva detalhadamente as tarefas que precisam ser executadas por um compilador de linguagem de alto nível.

9.

O que é uma árvore sintática? Exemplifique, construindo uma árvores sintáticas para a sentença 0110 gerada pela gramática G = ( {0,1} , {S} , P , S ), onde P={S $\rightarrow$0S1 , S $\rightarrow \epsilon$} .

10.

De que forma a ferramenta lex (ou flex) pode ser útil ao processo de compilação de um código de programa em linguagem de alto nível?

11.

E a ferramenta yacc (ou bison)?

12.

Explique em detalhes como se pode gerar um compilador completo usando as ferramentas lex e yacc.

13.

Explique como se dá a interação entre o código gerado pelas ferramentas lex e yacc.

14.

Existem várias maneiras de se otimizar um código, seja em linguagem de alto nível ou de baixo nível. Crie e explique exemplos que ilustrem pelo menos 5 destas maneiras.

15.

Por que é importante distingüir entre otimizações dependentes e independentes de máquina?

16.

Escreva expressões regulares para os seguintes padrões:
(a) o conjunto de palavras tendo a, e, i, o, u aparecendo nesta ordem, embora não necessariamente consecutivos;
(b) comentários em PL/I ou C, ou seja, cadeias iniciadas por /* e encerradas com */ .

17.

Usando a linguagem de especificação lex, escreva uma gramática que reconheça uma declaração de variáveis em C composta de qualquer combinação legal das palavras-chave int, char, log, float, double, signed, unsigned, short e um nome de variável. Assim, sentenças como

       long unsigned int x;
       short y;

devem ser aceitas, enquanto que

                                                        
        signed unsigned int x;

não deve ser aceita. Observe que a palavra-chave int pode ser omitida em uma declaração quando combinada com outras palavras-chave.

• Outros exercícios extras sobre compiladores