Lista 1 Analise Lexica - Prof Daniel Lucrédio

Construção de Compiladores 1 - 2015.1 - Prof. Daniel Lucrédio

Lista 01 – Conceitos

1. O que é um compilador?

R: "um programa que recebe como entrada um programa em uma linguagem de programação

- a linguagem fonte - e o traduz para um programa equivalente em outra linguagem - a

linguagem objeto"

2. Quais as diferenças entre um compilador e um interpretador? Cite vantagens e desvantagens de

cada um.

R: Um compilador traduz o programa fonte em um programa objeto, e o programa objeto é

quem executa as ações semânticas. Um interpretador traduz um programa fonte diretamente

em ações semânticas, isto é, é ele mesmo quem executa as ações.

- Um compilador é mais eficiente, pois o código produzido executa de forma independente.

- Um interpretador é menos eficiente, pois ele precisa executar o código ao mesmo tempo em

que o traduz.

- Um compilador tem maior dificuldade em oferecer diagnóstico de erros, pois na compilação

parte da informação é perdida. O programa objeto não tem acesso direto ao programa fonte.

- Um interpretador tem mais facilidade em oferecer diagnóstico de erros, pois ele tem o

programa fonte acessível no momento da execução.

- Um compilador é menos flexível quanto a mudanças, pois é sempre necessário recompilar

antes de re-executar um programa.

- Um interpretador é mais flexível quanto a mudanças, pois, alterando-se o programa fonte,

basta executar o interpretador uma vez, e ele já irá considerar as mudanças.

3. O que é compilação JIT?

R: É uma forma de aumentar a eficiência em um processo de interpretação ou compilação

híbrida (compilação + interpretação). Um compilador JIT (Just-In Time) é inserido dentro de

um interpretador, e é responsável por compilar o programa um pouco antes da interpretação,

automaticamente. Enquanto um interpretador puro analisa o programa ao longo da

execução, um interpretador com JIT faz uma pré-compilação e executa o código compilado,

melhorando assim seu desempenho. Exceto o desempenho, para o usuário não há diferença

entre um interpretador puro e um interpretador com JIT.

4. Por que uma gramática livre de contexto não é suficiente para a maioria das linguagens de

programação?

R: Porque a maioria das linguagens de programação faz uso de nomes (de variáveis, métodos,

classes, procedimentos, funções, pacotes, etc.). Um nome serve como uma referência para

algo que já foi "declarado" anteriormente no programa. Para reconhecer nomes, é necessário

um formalismo capaz de lembrar múltiplas sequências de caracteres aparecendo

repetidamente em um programa. Trata-se de uma extensão da linguagem {ww | w pertence a

um alfabeto {0,1}*}, a qual não é livre de contexto, conforme pode ser demonstrado pelo

lema do bombeamento para linguagens livres de contexto.

5. Como é possível utilizar uma gramática livre de contexto em um compilador (ao invés de uma

gramática com menos restrições) e usufruir da simplicidade e praticidade de um PDA?

R: Eliminando os nomes da linguagem, em um primeiro momento, para tornar a análise

sintática possível por meio de um PDA (Push-Down Automata ou Autômato com pilha). Os

nomes podem ser considerados posteriormente, por meio das ações realizadas durante a

análise semântica / síntese.

6. Que fase do compilador utiliza um autômato de pilha?

R: Análise sintática, dentro da etapa de análise, ou front-end do compilador.

7. Qual a diferença entre sintaxe e semântica, no contexto de um compilador?

R: Sintaxe é tudo que aparece na gramática livre de contexto. O resto é semântica.

8. Qual a diferença entre análise e síntese em um compilador?

R: A análise busca entender um programa fonte, sua sintaxe e significado, enquanto a síntese

busca produzir um programa objeto que reflete o mesmo significado que o programa fonte,

ainda que com sintaxe diferente.

9. Qual a diferença entre o front-end e o back-end de um compilador?

R: Front-end é o mesmo que análise, e back-end é o mesmo que síntese, portanto a resposta é

a mesma da pergunta anterior.

10. Descreva todas as fases de um compilador, incluindo, para cada uma delas:

a) Entrada

b) Saída

c) Descrição

d) Se faz parte do front-end ou back-end

R:

1. Analisador léxico

a) Entrada = fluxo de caracteres

b) Saída = fluxo de tokens

c) Descrição = O analisador léxico é responsável por identificar, no programa fonte, as

unidades léxicas que fazem parte da linguagem. Ele busca identificar as "palavras" que fazem

parte do "vocabulário" da linguagem. Para cada unidade léxica, ele produz um token, que é

uma estrutura de dados que representa as informações da unidade léxica necessárias para a

fase seguinte. Também detecta erros léxicos, na forma de unidades léxicas mal formadas

("palavras" que não existem no "vocabulário" da linguagem)

d) Front-end.

2. Analisador sintático

a) Entrada = fluxo de tokens

b) Saída = árvore de análise sintática

c) Descrição = O analisador sintático busca determinar a FORMA com que as unidades

léxicas se compõem. Se o léxico cuida das "palavras"/"vocabulário", o sintático cuida das

"frases"/"gramática" da linguagem. Ele apenas considera o TIPO das unidades léxicas. Nomes

são descartados, de forma que é possível fazer uso de um formalismo baseado em um PDA.

Ele produz como resultado uma árvore de análise sintática, que é uma estrutura de dados que

representa as construções sintáticas do programa em uma hierarquia que obedece às regras

da linguagem. Também detecta erros sintáticos, na forma de combinações inválidas de

unidades léxicas ("frases" inválidas conforme a gramática da linguagem)