Compiladores

_________________________________________
Professor Álvaro Antônio Fonseca de Souza
Aula de hoje
_____________________________________________________________________________________________________________

Estrutura de um compilador
 Fundamentos da linguagem de programação
● Estático e Dinâmico
● Estático: política de linguagem que permite ao compilador decidir a respeito da
questão.
○ Decisão em tempo de compilação

● Dinâmico: política só permite que a decisão seja tomada quando o programa está
em execução.
○ Decisão em tempo de execução.

3
 Fundamentos da linguagem de programação
● Estático e Dinâmico
● O termo static aplicado aos dados em uma declaração de classe Java.
○ uma variável é um nome que designa uma localização de memória

● Nesse contexto, static refere-se à capacidade de o compilador definir o local na

memória onde a variável declarada se encontrará.
● Uma declaração como
○ public static int x;

● Torna x uma variável de classe e diz que existe apenas uma única cópia de x.
● O compilador determina a localização na memória onde x será mantido.
● Do contrário, cada objeto teria sua própria localização de x.
4
 Fundamentos da linguagem de programação
● Escopo
● Escopo de uma declaração de x: é a região do programa em que os usos de x se
referem a essa declaração.
● Escopo estático: Também conhecido como escopo léxico, determina o escopo
de uma declaração examinando-se apenas o programa.
● A maioria das linguagens utilizam escopo estático.
● Escopo dinâmico: o escopo é definido enquanto o programa é executado.
○ O mesmo uso de x poderia se referir a qualquer uma das declarações diferentes de x.

5
 Fundamentos da linguagem de programação
● As regras de escopo para C são baseadas na estrutura do programa.
● O escopo de uma declaração é determinado implicitamente pelo local onde a
declaração aparece no programa.
● Linguagens modernas, como C++, Java e C#, tem controle explícito sobre
escopos, através de palavras-chave como public, private e protected.
● Escopo estático para uma linguagem com blocos,
● Um bloco é um agrupamento de declarações e comandos.
● C utiliza chaves { e } para delimitar um bloco;
● Escopo teve origem na linguagem Algol usando begin e end para esta finalidade.

6
Aula de hoje
_____________________________________________________________________________________________________________

Análise léxica
 Introdução

● Análise léxica é a primeira fase de um compilador.

● A tarefa principal do analisador léxico é:
○ ler os caracteres da entrada do programa fonte;
○ agrupá-los em lexemas;
○ produzir uma sequência de tokens para cada lexema no programa
fonte.
● O fluxo de tokens é enviado ao analisador sintático para que
a análise seja efetuada.
8
 Introdução

● Um analisador léxico lê caracteres e os agrupa em “objetos do tipo token”.

● Trata as construções de múltiplos caracteres como identificadores.
● Os identificadores são sequências de caracteres.
● Os identificadores são tratados como unidades chamadas tokens durante a
análise sintática.
● Por exemplo, na expressão

count + 1,

● o identificador count é tratado como uma unidade.

9
 Tokens, padrões e lexemas
● Um token é um par consistindo em um nome e um valor de atributo
opcional.
● O nome do token é um símbolo abstrato que representa um tipo de
unidade léxica
○ uma palavra-chave em particular, ou uma sequência de caracteres da entrada
denotando um identificador.

● Um padrão é uma descrição da forma que os lexemas podem assumir.

○ uma sequência de caracteres que formam uma palavra-chave.

● Um lexema é uma sequência de caracteres no programa fonte que casa

com o padrão para um token 10
 Lexema e token
● O analisador léxico Iê os caracteres do programa fonte e produz como
saída tokens que representam os lexemas.
● Lexema: agrupamento de caracteres em unidades lexicamente
significativas que define um token.
● Um token é um terminal com informações adicionais.
● Um token possui a seguinte estrutura de dois componentes:
● <nome-token, valor-atributo>
○ um nome de token
○ um valor de atributo.
11
 Lexema e token

● Os nomes de token são símbolos abstratos

○ usados pelo analisador para fazer o reconhecimento sintático.

● Os nomes de token são conhecidos como terminais.

● Os tokens aparecem como símbolos terminais na gramática para uma linguagem
de programação.
● Exemplos de nome de tokens são: números, identificador, constante.

12
 Lexema e token

● O valor do atributo, se houver, é um apontador para a tabela de símbolos que

contém informações adicionais sobre o token.
● Exemplo de valor do atributo: número que referencia o token na tabela.
● Essas informações adicionais não fazem parte da gramática.
● Corriqueiramente nos referimos aos tokens e aos terminais como sinônimos.

13
 Lexema e token

● Os tokens podem ser divididos em dois grupos:

● Tokens simples: são tokens que não têm valor associado, pois a classe do token
já a descreve.
● Exemplo: palavras reservadas, operadores, delimitadores: <if,>, <else>, <+,>.
● Tokens com argumento: são tokens que têm valor associado e corresponde a
elementos da linguagem definidos pelo programador.
● Exemplo: identificadores, constantes numéricas - <id, 3>, <numero, 10>, <literal,
Olá Mundo>.

14
 Lexema e token

● Os tokens podem ser divididos em dois grupos:

● Tokens simples: são tokens que não têm valor associado, pois a classe do token
já a descreve.
● Exemplo: palavras reservadas, operadores, delimitadores: <if,>, <else>, <+,>.
● Tokens com argumento: são tokens que têm valor associado e corresponde a
elementos da linguagem definidos pelo programador.
● Exemplo: identificadores, constantes numéricas - <id, 3>, <numero, 10>, <literal,
Olá Mundo>.

15
 Símbolos léxicos
● identificadores: palavras para nomear entidades do programa
○ variáveis, funções, métodos, classes, módulos, etc.

● literais: sequência de caracteres que representa uma constante

○ um número inteiro, um número em ponto flutuante, um caracter, uma string, um valor verdade
(verdadeiro ou falso), etc.

● palavras-chave: palavras usadas para expressar estruturas da linguagem,

○ comandos condicionais, comandos de repetição, etc.
○ São geralmente reservadas, não podendo ser utilizadas como identificadores.

● sinais de pontuação: sequências de caracteres que auxiliam na construção das

estruturas do programa
○ separador de expressões em uma lista de expressões.

16
 Símbolos léxicos
● identificadores: palavras para nomear entidades do programa
○ variáveis, funções, métodos, classes, módulos, etc.

● literais: sequência de caracteres que representa uma constante

○ um número inteiro, um número em ponto flutuante, um caracter, uma string, um valor verdade
(verdadeiro ou falso), etc.

● palavras-chave: palavras usadas para expressar estruturas da linguagem,

○ comandos condicionais, comandos de repetição, etc.
○ São geralmente reservadas, não podendo ser utilizadas como identificadores.

● sinais de pontuação: sequências de caracteres que auxiliam na construção das

estruturas do programa
○ separador de expressões em uma lista de expressões.

17
 Símbolos léxicos
● identificadores: palavras para nomear entidades do programa
○ variáveis, funções, métodos, classes, módulos, etc.

● literais: sequência de caracteres que representa uma constante

○ um número inteiro, um número em ponto flutuante, um caracter, uma string, um valor verdade
(verdadeiro ou falso), etc.

● palavras-chave: palavras usadas para expressar estruturas da linguagem,

○ comandos condicionais, comandos de repetição, etc.
○ São geralmente reservadas, não podendo ser utilizadas como identificadores.

● sinais de pontuação: sequências de caracteres que auxiliam na construção das

estruturas do programa
○ separador de expressões em uma lista de expressões.

18
 Símbolos léxicos
● identificadores: palavras para nomear entidades do programa
○ variáveis, funções, métodos, classes, módulos, etc.

● literais: sequência de caracteres que representa uma constante

○ um número inteiro, um número em ponto flutuante, um caracter, uma string, um valor verdade
(verdadeiro ou falso), etc.

● palavras-chave: palavras usadas para expressar estruturas da linguagem,

○ comandos condicionais, comandos de repetição, etc.
○ São geralmente reservadas, não podendo ser utilizadas como identificadores.

● sinais de pontuação: sequências de caracteres que auxiliam na construção das

estruturas do programa
○ separador de expressões em uma lista de expressões.

19
 Símbolos léxicos
printf("Total = %d\n”, score);

● printf e score são lexemas casando com o padrão para o token id

● “Total = %d\n” é um lexema casando com literal.
● () lexemas que auxiliam na identificação de uma função.

20
Símbolos léxicos

21
Símbolos léxicos

22
 Exemplos

const PI = 3.1416

Onde:

● const casa com o padrão const que é um lexema

● PI é um lexema que casa com o padrão id (identificador)
● = é um lexema que cada com o padrão do token atribuição
● 3.1416 é um lexema que casa com o padrão token numero

23
 Tokens

Em muitas linguagens de programação, as classes a seguir abrangem a maioria ou

todos os tokens:

1. Um token para cada palavra-chave. O padrão para uma palavra-chave é o

mesmo que a própria palavra-chave.
2. Tokens para os operadores, seja individualmente ou em classes, como o token
comparison
3. Um token representando todos os identificadores
4. Um ou mais tokens representando constantes, como números e cadeias literais.
5. Tokens para cada símbolo de pontuação, como parênteses esquerdo e direito,
vírgula e ponto-e-vírgula.
24
 Atributos de tokens
● Mais de um lexema pode casar com um padrão.
● O analisador léxico deve oferecer às fases subsequentes do compilador
informações adicionais sobre qual foi o lexema em particular casado.
● Por exemplo, o padrão para o token number casa com 0 e 1,
● É extremamente importante para o gerador de código saber qual lexema foi
encontrado no programa fonte.

25
 Atributos de tokens
● O analisador léxico retorna ao analisador sintático um valor de atributo,
além do nome de token;
● O valor do atributo descreve o lexema representado pelo token
● O nome do token influencia as decisões durante a análise sintática,
● O valor do atributo influencia a tradução dos tokens após o
reconhecimento sintático.

26
 Atributos de tokens
● Os tokens possuem no máximo um atributo associado
● Esse atributo pode ter uma estrutura que combine com várias peças
da informação.
● O token id é um exemplo em que é necessário associar muitas
informações ao token.
● As informações do token, como lexema, tipo, e localização são
mantidas na tabela de símbolos.
● O valor de atributo apropriado para um identificador é um apontador
para sua entrada na tabela de símbolos. 27
 Remoção de espaços em branco
● Um analisador léxico pode realizar outras tarefas além da
identificação de lexemas.
● Uma dessas tarefas é remover:
○ comentários
○ espaço em branco (espaço);
○ quebra de linha;
○ tabulação;
○ outros caracteres usados para separar os tokens na entrada.
28
 Remoção de espaços em branco
● Espaços em branco podem causar erro.
● Devem ser ignorados assim como os comentários.
● Se os espaço em branco for eliminado, o analisador sintático não precisa
considerá-lo.
● Incorporar o espaço em branco na análise sintática é uma tarefa difícil.

Os números de linha e o contexto são úteis dentro das mensagens de erro para auxiliar a localizar os
erros; 29
 Lendo adiante
● Um analisador léxico talvez precise ler alguns caracteres adiante antes de
poder decidir sobre o token a ser retornado.
● Por exemplo:
● Um analisador léxico para C precisa ler adiante após ver o caractere >.
● Se o caractere seguinte for =,
● então > pertence à sequência de caracteres >=;
○ o lexema do token para o operador “maior ou igual a”,

● Senão, o próprio > forma o operador “maior que”,

● O analisador léxico terá lido um caractere a mais.

30
 Lendo adiante
● Manter um buffer de entrada no qual o analisador
léxico pode ler e colocar caracteres de volta.
● Um apontador registra a parte da entrada que está
sendo analisada.
● Para voltar um caractere, move-se o apontador para
trás.

31
 Lendo adiante
● A leitura de um caractere adiante normalmente é suficiente,
● Uma solução é usar uma variável para tratar o próximo
caractere da entrada.
● O analisador léxico lê um caractere adiante enquanto coleta
dígitos para formar os identificadores;
● por exemplo, após 1 ele lê mais um caractere para distinguir
entre 1 e 10, e após t ele lê mais um caractere para distinguir
entre t e true.
32
 Lendo adiante
● O analisador léxico lê adiante apenas quando necessário.
● Um operador como * pode ser identificado sem leitura adiante.
● A variável de leitura é definida como um espaço em branco
○ será ignorado quando o analisador léxico for chamado para encontrar o
próximo token.

● A variável de leitura contém :

○ O caractere além do lexema para o token corrente
○ Um espaço em branco.

33
 Reconhecendo palavras-chave e identificadores
● As palavras-chave geralmente satisfazem as regras para formar
identificadores.
● Necessário um mecanismo para decidir quando um lexema forma
uma palavra-chave e quando ele forma um identificador.
● O problema é mais fácil de resolver se as palavras-chave forem
reservadas;
○ Se não puderem ser usadas como identificadores.
● Uma sequência de caracteres forma um identificador apenas se não
for uma palavra-chave.
34
 Reconhecendo palavras-chave e identificadores
● Representação única.
● Uma tabela com sequências de caracteres pode isolar o
resto do compilador da representação das sequências de
caracteres.
● As fases do compilador podem trabalhar com referências ou
apontadores para a sequência de caracteres na tabela.
● As referências também podem ser manipuladas com mais
eficiência do que as próprias sequências de caracteres. 35
 Reconhecendo palavras-chave e identificadores
● Palavras reservadas.
● As palavras reservadas podem ser implementadas inicializando a tabela
de sequências de caracteres com as sequências de caracteres
reservadas e seus tokens.
● Quando o analisador léxico lê uma sequências de caracteres ou lexema
que possa formar um identificador, ele primeiro verifica se o lexema está
na tabela de sequências de caracteres.
● Se estiver, retorna o token da tabela; caso contrário, retorna um token
cujo primeiro componente é o terminal id.
36
 Reconhecendo palavras-chave e identificadores
● Uma tabela de sequências de caracteres pode ser implementada como
uma tabela hash.
● A declaração

Hashtable words = new Hashtable();

● Configura words como uma tabela hash padrão,

● Faz o mapeamento entre chaves e valores.

37
 Qual é a sequência de tokens?

Qual é a sequência de tokens?

38
 Qual é a sequência de tokens?

Qual é a sequência de tokens?

39
 Um analisador léxico
1. Token scan()
2. ignora os espaços em branco
3. trata os números
4. trata as palavras reservadas e identificadores
5. /* se chegamos aqui, trata o caractere lido adiante como
token */
6. Token 1 = new Token(peek);
7. peek = espaço /* inicialização
8. return t
9. }
40
Exemplo

41
Exemplo

42
Exemplo

43
 Tabelas de símbolos
● Tabelas de símbolos são estruturas de dados que contém informações sobre as
construções do programa fonte.
● As informações são coletadas de modo incremental pelas fases de análise de um
compilador.
● As entradas na tabela de símbolos são criadas e usadas durante a fase de
análise pelo analisador léxico, pelo analisador sintático e pelo analisador
semântico.
● As informações são usadas pelas fases de síntese para gerar o código objeto.
● As entradas na tabela de símbolos contêm informações sobre um identificador,
como nome ou lexema, tipo, endereço na memória e outras informações
relevante.
44
 O papel do analisador léxico
Quando o analisador léxico descobre que um lexema é um identificador, precisa inserir esse
lexema na tabela de símbolos.

Em alguns casos, as informações referentes ao identificador devem ser lidas da tabela de

símbolos pelo analisador léxico para determinar o token apropriado que ele precisa passar ao
analisador sintático.

45
 Erros léxicos
● É difícil para um analisador léxico saber que existe um erro no código
fonte.
● Por exemplo, se a cadeia de caracteres fi for encontrada pela primeira
vez em um programa C no contexto:

fi (a = f(x)) …

● fi pode ser
● A palavra-chave if escrita errada
● Um identificador de função não declarada.
46
 Erros léxicos
● fi é um lexema válido para o token id
● O analisador léxico precisa retomar o token id
● Deixa que alguma outra fase do compilador trate do erro
devido à transposição das letras.
● Provavelmente o analisador sintático, neste caso.
● O compilador deve continuar o processo de compilação para
encontrar o maior número de erros possível.

47
 Abordagens de implementação

Existem duas abordagens para se construir uma analisador léxico:

● Escrever uma descrição formal dos padrões de símbolos da linguagem

utilizando uma linguagem de descrição relacionada com expressões
regulares e usar um software para gerar automaticamente o analisador.
Exemplo: lex;
● Construir autômatos finitos para descrever os padrões de símbolos da
linguagem e escrever um programa para implementar e utilizar os
autômatos.
○ Tabelas de transição ou diretamente em código. 48
 Exercício
Divida o seguinte programa em C++:

float limitedsquare(float x){

/* retorna x ao quadrado, mas nunca mais do que 100 */

return (x<=-10.0||x>=10.0)? 10.0:x*x;

em lexemas apropriados.

Quais lexemas devem ter valores léxicos associados?

Quais deverão ser esses valores?

49
 Bibliografia
Bibliografia Básica:

● AHO, A. V. ET AL. Compiladores: princípios,

técnicas e ferramentas. 2. ed. São Paulo: Pearson
Addison Wesley, 2008. 634 p. Acervo: 005.453 C736
● LOUDEN, K.C. Compiladores: princípios e práticas.
São Paulo: Cengage Learning, 2004. 569 p. Acervo:
005.453 L886c
● HOPCROFT, JOHN E.; ULLMAN, JEFFREY D.;
MOTWANI, RAJEEV. Introdução à teoria de
autômatos, linguagens e computação. Rio de
Janeiro: Elsevier, 2003. 560 p. Acervo: 005.131 H791i
2003
50
 Bibliografia
Bibliografia Complementar:

● DELAMARO, M. E.. Como Construir um Compilador: Utilizando Ferramentas

Java. São Paulo: Novatec, 2004.
● ROSA, JOÃO LUIS GARCIA.. Linguagens formais e autômatos. Rio de Janeiro:
LTC, 2010. Acervo: 005.131 R788l
● MENEZES, P. B.. Linguagens formais e autômatos. 6. ed. Porto Alegre:
Bookman, 2011. Acervo: 005.131 M543l 2011
● RAMOS, M. V. M.; JOSÉ NETO, J.; VEGA, I. S. Linguagens Formais: Teoria,
Modelagem e Implementação. São Paulo: Bookman, 2009. 656 p. Acervo:
● RICARTE I. L. M.. Introdução à Compilação. Rio de Janeiro: Elsevier, 2008. 280
p. Acervo:
51