Análise Léxica
Prof. Alexandre Monteiro
Baseado em material cedido pelo Prof. Euclides Arcoverde
Recife
‹#›
Contatos

Prof. Guilherme Alexandre Monteiro Reinaldo

Apelido: Alexandre Cordel

E-mail/gtalk: [email protected]
[email protected]

Site: http://www.alexandrecordel.com.br/fbv

Celular: (81) 9801-1878
Agenda

Definição de Compilador

Etapas da Compilação

Introdução à Análise Léxica

Implementação Manual de um Lexer
3
Definição de Compilador
Compilador

Definição geral:
• É um programa que traduz um texto escrito em uma
linguagem computacional (fonte) para um texto
equivalente em outra linguagem computacional
(alvo)
- Entrada: código fonte (na ling. fonte)
- Saída: código alvo (na ling. alvo)

Dependendo do propósito, podem ter nomes
específicos
5
Tipos de Compiladores

Assembler ou Montador
• Tipo simples de compilador
• A linguagem fonte é uma linguagem assembly (ou
linguagem de montagem)
- Correspondência direta com a linguagem de máquina
• A linguagem alvo é uma linguagem de máquina
6
Tipos de Compiladores

Compilador tradicional
• Traduz de uma linguagem de alto nível para uma de
baixo nível
• Em muitos casos, o compilador gera código objeto,
que é um código de máquina incompleto
- Precisa passar por um linker para virar executável
- Exemplo: gcc
• Em outros casos, o compilador gera um código em
linguagem de montagem
7
Etapas da Compilação
Etapas da Compilação


Tradicionalmente, os compiladores se dividem em um
conjunto de etapas
Mostraremos as cinco etapas básicas a seguir
•Podem existir também outras etapas
intermediárias de otimização de código,
omitidas na figura
9
Etapas da Compilação
Análise Léxica
Análise Sintática
Analise Semântica
Geração de Código
Intermediário
Geração de Código
Final
10
Fases da Compilação

Fase de Análise
•Subdivide o programa em partes
constituintes
•Cria uma estrutura abstrata do programa

Fase de Síntese
•Constrói o programa na linguagem alvo
•Gera código final
11
Etapas da Compilação
Análise Léxica
Análise Sintática
Front-End
(Análise)
Analise Semântica
Geração de Código
Intermediário
Geração de Código
Final
Back-End
(Síntese)
12
Etapas da Compilação

Mas por que essa divisão em etapas?
• Modularidade – deixa o compilador mais legível e
mais fácil de manter
• Eficiência – permite tratar mais a fundo cada etapa
com técnicas especializadas
• Portabilidade – facilita adaptar um compilador para
- Receber outro código fonte (muda o front-end)
- Gerar código para outra máquina (muda o back-end)
13
Etapas da Compilação
Análise Léxica
Análise Sintática
Front-End
(Análise)
Analise Semântica
Geração de Código
Intermediário
Geração de Código
Final
Back-End
(Síntese)
14
Introdução à Análise Léxica
Análise Léxica

Objetivo
•Ler os caracteres do código fonte
agrupando-os de maneira significativa (em
lexemas) e classificando esses agrupamentos
(em tokens)

Em outras palavras
•Entrada: sequência de caracteres
•Saída: sequência de tokens
16
Relembrando...


Lexema: sequência de caracteres com significado
interligado
Token: classificação dada ao lexema
•Geralmente retornado junto com o próprio
lexema ou outro atributo, como um ponteiro
ou um valor numérico associado
17
Relembrando...

Tokens especificados como expressões regulares:
ABRE_PAR
→(
FECHA_PAR
→)
ATRIB
→=
ADD
→+
MULT
→*
DEF
→ def
ID
→ [_a-z][_a-z0-9]*
NUM_INT
→ [0-9][0-9]*
PT_VG
→;
WHITESPACE
→ [ \t\n\r]+
18
Análise Léxica

O módulo de software responsável por essa
etapa pode ser chamado de:
• Analisador Léxico, Lexer ou Scanner

Além de retornar os tokens, ele pode:
• Remover espaços em branco
• Contar linhas e colunas, para identificar a
localização de erros
• Expandir macros
19
Análise Léxica


Existem várias técnicas para construção de um lexer,
inclusive técnicas de construção (semi) automática
Porém, iniciaremos vendo como fazer um lexer simples
manualmente
20
Implementação Manual de um Lexer
Implementação Manual

Vamos começar implementando tokens em uma linguagem
simples, chamada XPR-0
•Linguagem para especificar expressões
•Tokens de 1 caractere apenas
•Sem tratamento de espaços em branco
22
Exemplo de Implementação

Tokens de XPR-0
NUMERO
→ [0-9]
PT_VIRG
→;
ADD
→+
MULT
→*
ABRE_PAR
→(
FECHA_PAR
→)
23
Exemplo de Implementação

Passos para implementar o lexer de XPR-0
•Implementar os tipos dos tokens
•Implementar uma classe para o token
•Implementar o lexer
24
Exemplo de Implementação

Como implementar os tipos de tokens
• Java: criar uma classe separada TokenType
- Sugestão: usar “enum” de Java >= 5
• C: usar vários defines, com valores diferentes
• Definir um token especial para indicar fim de
arquivo

Exemplo em IDE (Eclipse ou Netbeans)
25
Exemplo de Implementação

Como implementar os tokens
• Criar classe Token
• Precisa guardar pelo menos o tipo
• Pode ter outras informações
-

O lexema
Uma subclassificação
O valor inteiro do token
Etc.
Exemplo em IDE (Eclipse ou Netbeans)
26
Exemplo de Implementação

Como implementar o lexer
• Criar classe Lexer
• Método “nextToken()”
- Lê o próximo caractere, classifica-o e retorna o token

Exemplo em IDE (Eclipse ou Netbeans)
27
Implementação Manual


O exemplo anterior foi bem simples, apenas
para dar uma noção de construção de um lexer
Complicações adicionais que podem surgir
• Tratamento de espaço em branco
• Tokens de vários caracteres
• Tokens com prefixos comuns
• Diferenciar identificadores de palavras-chave
28
Melhorando o Lexer Manual
Melhorando o Lexer

Espaço em branco
•Fazer um laço para ler todo caractere
considerado como espaço em branco
•Analisar antes de qualquer outro token
30
Melhorando o Lexer

Espaços em branco
// ignora os espaços em branco e quebras de linha
while (nextChar == ' ' || nextChar == '\t'
|| nextChar == '\r' || nextChar == '\n') {
nextChar = this.readByte();
}
// testar fim de arquivo
...
// testar outros tokens
...
31
Melhorando o Lexer

Tokens de vários caracteres
• Faz uma decisão externa com base no primeiro
símbolo
- Usar switch (mais eficiente) ou if-else’s encadeados
• Dentro, faz um laço do-while (ou while)
• Cada símbolo válido deve ser concatenado ao
lexema
32
Melhorando o Lexer

Tokens de vários caracteres
- Assuma que “lexema” é um objeto StringBuilder
...
else if (Character.isDigit(nextChar)) {
do {
lexema.append((char) nextChar);
nextChar = this.readByte();
} while (Character.isDigit(nextChar));
tipo = TokenType.NUMERO;
}
...
33
Melhorando o Lexer

Prefixos comuns
•Se tokens de múltiplos caracteres tiverem
parte em comum
•Adiar a decisão sobre o tipo e deixa para
fazer a decisão num nível mais interno
•Continuar lendo os caracteres e
armazenando no lexema até poder decidir
34
Melhorando o Lexer

Prefixos comuns
- Exemplo: tokens dos operadores “>=“ e “>”
...
else if (nextChar == '>') {
nextChar = this.readByte();
if (nextChar == '=') {
tipo = TokenType.GREATER_EQ;
nextChar = this.readByte();
} else {
tipo = TokenType.GREATER;
//não precisa ler o próximo char
}
}
...
35
Melhorando o Lexer

Diferenciando identificadores de palavraschave
• Ler todo o lexema, como se fosse um identificador
• Depois, compara o lexema inteiro com a lista de
palavras-chave
- Pode usar uma tabela hash (Hashtable, em Java)
- Adicionar as palavras-chave com seus tipos de token
- Após ler o lexema, é só consultar a tabela
• Se não existir palavra-chave para aquele lexema,
então é um identificador
36
Hashtable


Estrutura de dados que mapeia chaves (keys) a
valores (values)
Classe Hashtable (Java)
• Método “put” recebe o par (chave,valor)
• Método “get” recebe a chave e retorna o valor
• Exemplo: associar “String” com “Integer”
Hashtable numbers = new Hashtable();
numbers.put("one", new Integer(1));
numbers.put("two", new Integer(2));
Integer v = (Integer) numbers.get("one");
37
Melhorando o Lexer

Palavras-chave
- Criação da hash
class Lexer {
...
private Hashtable keywords;
Lexer() {
keywords.put(“if” , TokenType.IF);
keywords.put(“else”, TokenType.ELSE);
keywords.put(“int” , TokenType.INT);
...
}
38
Melhorando o Lexer

Palavras-chave
- Reconhecimento dos tokens, em nextToken()
if (Character.isLetter(nextChar)) {
do {
lexema.append((char)nextChar);
nextChar = this.readByte();
} while (Character.isLetter(nextChar));
if (keywords.containsKey(lexema.toString())) {
tipo = keywords.get(lexema.toString());
} else {
tipo = TokenType.IDENTIFICADOR;
}
}
39
Buffers de Leitura
Por que usar buffers?

Para tratar situações em que é preciso olhar
caracteres à frente
• Na leitura de um ID, por exemplo, é preciso chegar
num caractere inválido para parar
• Como devolver este último caractere?

Para melhorar a performance
• Ler um bloco de caracteres do disco é mais
eficiente do que ler caractere a caractere
41
Buffer Único

Lê um bloco de caracteres do arquivo para um array na
memória
•Geralmente, usa-se como tamanho do buffer
o tamanho do bloco de disco
•Exemplo: 4096 bytes (4 KB)
42
Buffer Único
t
e
lexemeBegin

m
p
=
a
forward
Variáveis para controlar o buffer
• lexemeBegin: início do lexema atual
• forward: próximo caractere a ser analisado pelo
lexer

O lexema final fica entre lexemeBegin e
forward
43
Buffer Único

Vantagens
• Leitura mais eficiente do arquivo (em blocos)
• Permite devolver um caractere, retornando o
apontador forward

Porém, o uso de buffer único ainda traz
problemas
• Lexemas podem ficar “quebrados” no fim do buffer
44
Buffers Duplos

Dois buffers de mesmo tamanho
•Exemplo: dois buffers de 4kB

t
Evita que um lexema fique incompleto, desde que tokens
não possam passar do tamanho de um buffer
e
lexemeBegin
m
p
=
a
u
x
*
1
0
forward
45
Buffers Duplos


Um buffer é carregado quando o outro já foi
completamente lido
A cada leitura de caractere (por meio da variável forward),
é preciso testar os limites
•Se chegou ao fim de um buffer, muda para o
próximo e recarrega

Esse teste ainda pode ser otimizado...
46
Sentinelas

São caracteres especiais usados para demarcar
o fim do buffer
• Não precisa testar o fim do buffer a cada passo,
basta testar quando achar esse caractere

t
Geralmente se usa o mesmo símbolo usado
para fim de arquivo – eof
e
m
p
=
a
eof
u
x
*
1
0
eof
código fonte
código fonte
sentinela
47
sentinela
Sentinelas

Como diferenciar um sentinela de um fim de
arquivo real?
• Basta consultar a posição do caractere
• Sentinelas ficam em posições fixas no fim do buffer
• Um fim de arquivo real aparece em qualquer outra
posição
t
e
m
p
=
a
eof
sentinela
u
x
eof
eof
fim de arquivo
sentinela
;
48
Sobre Buffers e Sentinelas

São técnicas para quem está muito preocupado com
eficiência na compilação
•Não é para quem faz um compilador em
Java, é para quem faz em C ou Assembly
49
Expressões Regulares
Expressões Regulares

Tokens: classificação de um lexema
• São vistos como unidades atômicas da linguagem

Para especificar quais lexemas são associados
a cada token, podem ser usadas expressões
regulares
• Cada token é associado a uma expressão regular
51
Expressões Regulares

Exemplo de especificação dos tokens
ABRE_PAR
→(
FECHA_PAR
→)
ATRIB
→=
ADD
→+
MULT
→*
DEF
→ def
ID
→ [_a-z][_a-z0-9]*
NUM_INT
→ [0-9][0-9]*
PT_VG
→;
WHITESPACE
→ [ \t\n\r]+
52
Lexer Manual

Fazer manualmente envolve diversas
dificuldades, como já vimos
• Tratar espaços em branco
• Tratar tokens de múltiplos caracteres
• Diferenciar identificadores de palavras reservadas
• Criação de buffer

Não seria possível criar o lexer
automaticamente a partir da especificação?
53
Lexer Automático

Cada expressão regular da especificação deve ser
transformada em um reconhecedor
•Recebe uma sequência de caracteres de
entrada
•Retorna se ela casa ou não com a expressão
palavra
(encontrada no
código fonte)
Reconhecedor
sim/não
54
Expressões Regulares

Vimos diversos tipos de expressões regulares
•a*, a+, a{3,5}, a?, (a|b), ab, ...

Todos eles podem ser reduzidos a um conjunto menor de
expressões regulares básicas e de operadores sobre elas
55
Expressões Regulares

Expressões básicas
• Para representar um caractere “x” qualquer: x
• Para representar a palavra vazia: ε

Operadores
• ab – concatenação: “a” seguido de “b”
• a|b – união: “a” ou “b”
• a* – zero ou mais ocorrências de “a”
56
Lexer Automático

É suficiente converter estas expressões básicas e
operadores para algum reconhecedor
•Todos os outros operadores poderão serão
convertidos a partir destes

Mas que reconhecedor é este? E como converter?
57
Autômatos Finitos
Autômatos Finitos

Formalismo reconhecedor de linguagens
• Linguagem: conjunto de palavras


Foram vistos em Teoria da Computação, junto
com expressões regulares
São equivalentes às expressões regulares, ou
seja, representam as mesmas linguagens
59
Autômatos Finitos

O primeiro tipo que veremos é o autômato finito nãodeterminístico (AFN ou NFA)
•Seguiremos a definição do livro texto para
AFN, porém usando a sigla em inglês NFA
60
NFA

Um estado inicial e vários estados de aceitação

Mudanças entre estados
• Pode ler o próximo símbolo da palavra
• Ou pode acontecer sem leitura de símbolo: ε

Se existir algum caminho que pare em um
estado de aceitação, a palavra é dita “aceita”
• Se não houver nenhum caminho, rejeita
61
NFA

Exemplos:
•id -> he | she | his | hers
0
h
1
e
2
i
s
•Exercício:
6
3
h
4
r
s
e
8
7
2
- comparacao -> < | > | <= | >= | = | <>
62
s
9
Expressão Regular → NFA


Como vimos em Teoria da Computação, é possível converter
de uma expressão regular para um NFA
Veremos
•Conversão de expressões básicas
•Conversão de cada operador
63
Expressão Regular → NFA

Conversão de cada expressão regular básica r
64
Expressão Regular → NFA

Operador de concatenação – r1r2
•Converter r1 para um autômato M1 e r2 para
M2
•Depois, criar o autômato:
65
Expressão Regular → NFA

Operador de união – r1|r2
•Converter r1 para M1 e r2 para M2
•Depois, criar o autômato:
66
Expressão Regular → NFA

Operador de concatenação sucessiva – r*
•Converter r para M1
•Depois, criar o autômato:
67
Expressão Regular → NFA

Exercício
•Criar NFA para a(b*|c*)
68
NFA

Autômatos não-determinísticos (NFA)
permitem múltiplos caminhos para leitura de
uma mesma palavra
• Pode ser usado, mas é computacionalmente
ineficiente, devido à necessidade de expandir todos
os caminhos

O ideal seria uma autômato sem ambiguidades
no processo de reconhecimento
69
DFA

Autômato finito determinístico (AFD ou DFA)
é um caso especial de NFA
• Sem transições vazias
• Com apenas uma opção de transição para cada
caractere/símbolo
• Para todo caractere possível, há uma transição
70
DFA

Exemplo
71
DFA

O caminho de reconhecimento para uma dada
palavra é único e bem-definido
• Mais simples de implementar o reconhecimento

As transições podem ser representadas
simplesmente como uma tabela
• Implementada como um array bidimensional
72
DFA

Exemplo
•Diagrama de estados
•Tabela
73
NFA → DFA

A partir do NFA pode ser feita uma conversão
para um DFA por um processo genérico
• Cada estado no DFA vai representar um conjuntos
de estados no NFA


O DFA resultante pode ficar com mais estados,
mas existe um processo genérico de
minimização de estados também
Não veremos esses dois procedimentos...
74
Autômatos


Assim, os autômatos são usados para criar
“reconhecedores” a partir de expressões regulares dadas
Mas como usar autômatos para criar um scanner? Como
fazer isso automaticamente?
75
Geradores Automáticos de Lexers
Gerador Automático de Lexers

Recebe uma especificação (na forma de regras léxicas)

Como saída, gera o código do lexer
Regras
Léxicas
Gerador de
Analisadores Léxicos
Scanner
77
Regras Léxicas


Servem para especificar as expressões regulares e os tokens
associados a elas
Na prática, associa a expressão regular com algum código
definido pelo usuário
"("
{ return new Token(A_PARENT); }
")"
{ return new Token(F_PARENT); }
[0-9]+ { return new Token(NUMERO, yytext()); }
* public String yytext(): returns the matched input text region
78
Lexer Gerado

Capaz de tratar automaticamente
ambiguidades
• Quando um trecho da entrada (lexema) pode casar
com duas ou mais expressões regulares

Duas regras são usadas no caso de
ambiguidades
• Casar com a expressão regular que reconhece o
maior lexema possível
• Se ainda houver mais de uma opção, casa com a
expressão regular que vem primeiro na lista
79
Gerador Automático de Lexer

Discutiremos a seguir dois tópicos relacionados à geração
automática de um analisador léxico
•Como gerar o lexer automaticamente
•Como funcionará o lexer gerado
80
Gerando um Lexer...


Converte cada expressão regular (associada a
cada token) para um NFA
Une todos os NFAs em um só, criando um
estado inicial e usando transições vazias
• Um só estado inicial, mas vários estados de
aceitação
• Cada estado de aceitação vai indicar o
reconhecimento de um token específico
81
Gerando um Lexer...

Em seguida, converte o NFA combinado para
um DFA
• Cria estados combinando os estados do NFA
• Se dois estados de aceitação do NFA forem
combinados em um estado do DFA, apenas o token
definido primeiro será retornado
- Trata a regra “primeiro na lista”

Depois, ainda pode minimizar os estados do
DFA por questões de eficiência
82
Exemplo


Seja a seguinte especificação de entrada para o gerador de
lexers
a
{ return TOKEN_X; }
abb
{ return TOKEN_Y; }
a*b+
{ return TOKEN_Z; }
Convertendo cada expressão para NFAs...
83
Exemplo

NFAs para cada expressão regular
84
Exemplo

NFA combinado
85
Exemplo

Conversão para DFA
86
Reconhecimento no Lexer...


Vimos como gerar o autômato para reconhecer as
expressões regulares associadas aos tokens
Mas como esse autômato é usado no lexer gerado
automaticamente?
87
Reconhecimento no Lexer...

Um DFA pode ser facilmente representado por
um array bidimensional
• Para cada par (estado, símbolo) indica o próximo
estado

Para simular o funcionamento do autômato é
preciso usar uma variável para guardar o
estado atual
88
Reconhecimento no Lexer...

A cada chamada da função nextToken(),
começa um novo processo de reconhecimento
• Reinicia o autômato – volta ao estado inicial
• Retoma a leitura de onde parou na última chamada

Lê o arquivo de entrada, fazendo as transições
no autômato para cada caractere
• Basta consultar a tabela de transição
89
Reconhecimento no Lexer...

O reconhecimento pára quando não houver mais nenhuma
transição possível
•Trata a regra “maior lexema”

O lexer, então, recupera o último estado de aceitação
atingido
•Retorna o token associado a esse estado
90
Exemplo

Reconhecimento de “abbba” no AFD anterior
• Primeira chamada a nextToken()
-
Início no estado q0
Lê a → q2q4q7
Lê b → q5q8
Lê b → q6q8
Lê b → q8
Lê a → erro, então volta a q8 e retorna TOKEN_Z
• Segunda chamada a nextToken()
- Início no estado q0
- Lê a → q2q4q7
- Fim da leitura, então retorna TOKEN_X
91
Reconhecimento no Lexer...

Atenção: Não confundam o gerador com o
lexer que ele cria
• O gerador lê as regras léxicas, cria um autômato e,
então, gera o código fonte do lexer baseado no
autômato
• O lexer, depois de compilado, é que vai operar
como descrito na última parte da aula
92
Exemplos de Geradores

Para C
•Lex e Flex

Para Java
•JLex e JFlex

Para C#
•C# Lex, C# Flex
93
Bibliografia

AHO, A., LAM, M. S., SETHI, R., ULLMAN, J. D.,
Compiladores: princípios, técnicas e ferramentas. Ed.
Addison Wesley. 2a Edição, 2008 (Capítulo 2)
94