II – Análise léxica
• Papel do analisador léxico.
• Diagnóstico e recuperação de erros léxicos
• Extensão de expressões regulares e
definições regulares
• Reconhecimento de tokens
• Bibliografia aconselhada:
– Aho, Sethi e Ullman – secções 3.1 e 3.3
– Appel – secções 2.1, 2.2 e 2.3
Jorge Morais
LFA 1999/2000 - 1
Papel do analisador léxico
Jorge Morais
LFA 1999/2000 - 2
Tokens, padrões e lexemas
• Token: representa um conjunto de
sequências de caracteres com significado
comum (número, identificador, etc...)
• Padrão: conjunto de sequências que
resultam num mesmo token
• Lexema: sequência de caracteres que
obedece a um padrão dum token
Jorge Morais
LFA 1999/2000 - 3
Exemplo
• O token identificador tem como padrão uma
sequência que começa numa letra seguida
de letras e números.
• Alguns lexemas possíveis:
– var, x1, LFA9900.
• Palavras reservadas
– if, else, while, switch, int, long, etc...
Jorge Morais
LFA 1999/2000 - 4
Atributos dos tokens
• Alguns tokens, como as palavras chave, só
têm um lexema possível
• Quando existe mais do que um lexema
possível é preciso guardar alguma
informação suplementar:
– um apontador para a tabela de símbolos, no
caso dum identificador
– o valor numérico, no caso dum número
Jorge Morais
LFA 1999/2000 - 5
Erros léxicos
• Um erro léxico ocorre quando o analisador
léxico não pode prosseguir porque nenhum
dos padrões foi encontrado
• Muitas vezes é impossível na fase de análise
léxica identificar alguns erros, porque o
padrão encontrado e o pretendido são
diferentes: a2 (identificador) / 2a (número
seguido de identificador)
Jorge Morais
LFA 1999/2000 - 6
Recuperação de erros léxicos
• Modo de pânico: apagar caracteres da
entrada até conseguir um token válido
• Apagar um carácter estranho
• Inserir um carácter em falta
• Substituir um carácter incorrecto por um
correcto
• Transposição de dois caracteres adjacentes
Jorge Morais
LFA 1999/2000 - 7
Extensão de expressões regulares
• Vamos estender as definições anteriores:
–
–
–
–
–
a|ba+b
a+  aa*
[abc]  a + b + c  a | b | c
[a-z]  a + b + ... + z  a | b | ... | z
a?  a +   a | 
Jorge Morais
LFA 1999/2000 - 8
Definições regulares
• Por conveniência podemos definir nomes
para algumas expressões regulares. Por
exemplo: [0-9] representa um dígito.
• Uma definição regular tem a forma
def  er onde def é a definição e er a
expressão regular, podendo esta usar
símbolos do alfabeto ou definições
anteriores
Jorge Morais
LFA 1999/2000 - 9
Exemplo
• Definição dum identificador
– letra  [A-Za-z]
– dígito  [0-9]
– identificador  letra (letra | digito)*
• Definição dum número
–
–
–
–
–
dígito  [0-9]
dígitos  dígito+
parte_fraccionária  (. dígitos)?
expoente  (E [+-]? dígitos)?
num  dígitos parte_fraccionária expoente
Jorge Morais
LFA 1999/2000 - 10
Reconhecimento de tokens
• Espaços em branco – caracteres que não são
considerados para a formação de tokens
• O carácter ' ' é desprezado quando se tenta
determinar um token, mas é tido em conta
quando se trata duma string
• Caracteres como os de tabulação e nova
linha podem ser considerados espaços em
branco
Jorge Morais
LFA 1999/2000 - 11
Tokens e autómatos finitos
• Os autómatos finitos, como reconhecem
linguagens regulares, são uma boa forma de
reconhecer tokens
• Existem algoritmos que permitem
transformar uma expressão regular num
autómato finito determinístico
Jorge Morais
LFA 1999/2000 - 12
Exemplo dum analisador léxico
• Vamos considerar um pequeno analisador
léxico com:
–
–
–
–
espaços em branco: ' ', tabulação e nova linha
operadores relacionais: <, <=, >, >=, ==, !=
identificadores: letra (letra | dígito)*
números: dígito+ (. dígito+)? (E [+-]? dígito+)?
Jorge Morais
LFA 1999/2000 - 13
Operadores relacionais
Jorge Morais
LFA 1999/2000 - 14
Identificadores
Jorge Morais
LFA 1999/2000 - 15
Números
Jorge Morais
LFA 1999/2000 - 16
Implementação em C
• Código fonte:
– ex1.c
• Comando:
– ex1 – lê a partir do standard input
– ex1 < fich
Jorge Morais
LFA 1999/2000 - 17