Analisador Léxico
Analisador Léxico
Fabiano Rodrigues
Farley J. R. Oliveira
Michel Sato
Vitor Lins Vieira
051.649-1
052.696-7
Analisador Léxico
• A análise léxica é a primeira fase do
compilador. A função do analisador léxico,
também denominado scanner, é ler o código
fonte, caracter a caracter, buscando a
separação e identificação dos elementos
componentes do programa fonte,
denominados símbolos léxicos ou tokens.
Analisador Léxico
• É também de responsabilidade desta fase a
eliminação de elementos "decorativos" do
programa, tais como espaços em branco,
marcas de formatação de texto e comentários.
Tokens
• A criação dos símbolos (tokens) é importante,
pois torna a próxima etapa de um compilador
(análise sintática, ou parsing) mais simples.
Etapas
• Na análise léxica podemos destacar três
etapas:
– Extração e classificação dos tokens
– Eliminação de delimitadores e comentários
– Recuperação de erros
Tokens
• O objetivo principal da análise léxica é
identificar sequências de caracteres que
constituem unidades léxicas ("tokens"). O
analisador léxico lê, caractere a caractere, o
texto fonte, verificando se os caracteres lidos
pertencem ao alfabeto da linguagem,
identificando tokens, e desprezando
comentários e brancos desnecessários.
Tokens
• Tokens são símbolos tais como palavras
reservadas, delimitadores, identificadores, etc.
• Os tokens (símbolos léxicos) são unidades
básicas de texto do programa. Eles são
representados internamente por três
informações: classe do token, valor do token e
posição do token.
Recuperação de Erros
• Ações possíveis:
• Remoção de sucessivos caracteres até o
reconhecimento de um token válido
(modalidade Pânico).
• Inserção de um caractere ausente.
• Substituição de um caractere incorreto por
outro correto.
• Transposição de caracteres adjacentes.
Exemplo
Exemplo: sum=3+2;
token type
sum
=
3
+
2
;
IDENT
ASSIGN_OP
NUMBER
ADD_OP
NUMBER
SEMICOLON
Exemplo de comando
•Comando em Java:
if (i== j)
z = 0; /* No work needed */
else
z= 1;
•Como o analisador léxico vê os comandos:
\tif(i== j)\n\t\tz = 0; /* No work needed */\n\telse\n\t\tz= 1;
Formação de Tokens & Expressões
Regulares
• Analisador efetua sucessivas verificações de caracteres até
encontrar um caracter de “estado morto”, como espaço,
parênteses, ponto-e-vírgula
• Retorna à ultima análise válida para extrair um lexeme
• Um lexeme classificado se torna um token
• O reconhecimento de um token é feito através de expressões
regulares
Scanner
• Após a definição dos tokens, o scanner, uma função do
analisador léxico, converte isto:
\tif(i== j)\n\t\tz = 0; /* No work needed */\n\telse\n\t\tz= 1;
• Nisto:
IF, LPAR, ID("i"), EQUALS, ID("j"), RPAR, ID("z"), ASSIGN,
INTLIT(""), SEMI, ELSE, ID("z"), ASSIGN, INTLIT(""), SEMI
que é a “expressão” a ser enviada ao analisador sintático
Classe de Scanner
• Exemplo de classe para um scanner em Java
class Token {
enum SyntacticCategory {
IF, LPAR, ID, EQUALS, RPAR, ASSIGN, ...
};
SyntacticCategory syntax;
Object value;
Location sourcePosition;
...
}
Classe de Scanner
• Exemplo de classe para um scanner em Java
class Token {
enum SyntacticCategory {
IF, LPAR, ID, EQUALS, RPAR, ASSIGN, ...
};
SyntacticCategory syntax;
Object value;
Location sourcePosition;
...
}
Geradores de Analisadores Lèxicos
• FLEX
• OOLEX
LEX / FLEX
• LEX é uma ferramenta para a geração
automática de analisadores léxicos
• Versão Free: FLEX (Fast LEX)
• Desenvolvido em 1975 em conjunto com o
YACC (Yet another compiler-compiler), por
Mike Lesk & Eric Schmidt. No Bell Laboratories
LEX / FLEX
• Free Software Foundation – GNU – FLEX:
Implementação mais rápida do FLEX (e
gratuita!!)
• O gcc (GNU C Compiler) foi desenvolvido com
LEX & YACC.
• LEX: dividir as entradas em unidades
coerentes (tokens)
• YACC: descobrir o relacionamento entre os
tokens. (análise sintática)
LEX / FLEX
• Objetivos: desenvolvida para programadores
de compiladores e interpretadores; porém
podem ser usadas também em detecção de
padrões em arquivos de dados, linguagem de
comandos, etc..
• Vantagem: Rápido desenvolvimento de
protótipos e manutenção simples do software.
LEX / FLEX
• Papel do LEX: toma um conjunto de descrições
de possíveis tokens e produz uma rotina em C
que irá identificar estes tokens
• Papel do Yacc: toma uma descrição concisa de
uma gramática e produz uma rotina em C que
irá executar a análise sintática ou parsing.
• NOTA: um analisador léxico desenvolvido
usando Lex é quase sempre mais rápido do
que um analisador léxico escrito diretamente
em C.
LEX / FLEX
LEX / FLEX
• Encontra-se em qualquer sistema Unix e pode
ser chamada usando os comandos lex ou flex;
• Transforma um arquivo contendo expressões
regulares em um programa C que reconhece
os padrões descritos no arquivo
• O Flex lê os arquivos de entrada (arquivo de
definição), obtendo assim a descrição do
scanner a ser gerado. Esse arquivo é definido
usando a linguagem lex
LEX / FLEX
LEX / FLEX
• Um arquivo de descrição Flex é dividido em três seções
separadas por %% :
• DEFINICOES
%%: Contém declarações de variáveis, constantes e definições
regulares;
• REGRAS
%%: Contém definições de rotinas em C que são chamadas
quando uma expressão é reconhecida
• CODIGO
Contém o main (início de procedure em C) e descreve como o
analisador léxico deve ser utilizado
LEX / FLEX
• SEÇÃO DE DEFINIÇÕES:
•
É opcional (pode ser vazia)
•
Contém definições léxicas, e a declaração e inicialização de variáveis
globais
•
Uma definição léxica possui a forma NOME DEFINIÇÃO
•
As definições são expressões regulares que reconhecem tokens do texto
fonte.
•
Seu conteúdo será copiado no início do arquivo C gerado na saída.
LEX / FLEX
• SEÇÃO DE DEFINIÇÕES:
• LEX define por padrão as variaveis globais:
yytext (lexema corrente) e yyleng (tamanho do lexema)
• Definições de macros:
digito [01]+ /* substituir {digito} por [01]+ ao processar as regras */
frac .[0-9]+ /* substituir {frac} por .[0-9]+ ao processar as reg
nl \n
/* substituir {nl} por \n ao processar as regras */ras */
• A inclusão das linhas de comando em C devem ser delimitadas por <%{> e
<%}>, como:
%{
#include <y.tab.h>
extern int yylval;
%}
LEX / FLEX
• SEÇÃO DE REGRAS:
• Define a funcionalidade do analisador léxico. Cada regra compreende uma
seqüência valida de caracteres (literais/expressões regulares) .
• Definido da seguinte forma:
token {AÇÃO}
• A ação pode ser nula ‘{ }’ ou conter um ou mais comandos em linguagem
C.
LEX / FLEX
• SEÇÃO DE REGRAS:
• Ao chamar a função yylex(), passando o token e seu tamanho, o
analisador executará a AÇÃO associada àquela token;
• Retornará o próprio token caso seja reconhecido pelo analisador léxico;
• Retornará brancos caso nenhuma ação seja tomada, ou caso seja
encontrados espaços em branco;
• ‘{ printf(“é isso ai\n”);} é a “ação” que consiste em imprimir uma
mensagem na tela.
LEX / FLEX
• SEÇÃO DE CODIGOS / PROCEDIMENTOS ADICIONAIS:
• Opcional (pode ser vazia)
• Possui o código C definido pelo programador (função main() , que deve
chamar a função yylex()
• Qualquer código C nessa seção será copiado diretamente no arquivo
produzido pelo Lex.
• Pode definir código para as ações complexas usadas na seção anterior.
LEX / FLEX
• UTILIZAÇÃO DO COMPONENTE GERADO
• O LEX é acoplado ao YACC, que efetua a analise sintática. É uma
ferramenta similar e complementar ao LEX.
• O LEX gera a função yylex() , que retorna o identificador de um item léxico
reconhecido.
• O YACC funciona de forma a chamar o yylex() do LEX;
• O YACC gera a função yyparse() , que analisa os itens léxicos e decide se
ele formam ou não uma sentença válida.
Analisador Léxico
OOLEX
OOLEX
• OOLEX (object-oriented lexer) é estritamente
baseada no paradigma de orientação a
objetos.
• Tese de doutorado de Bernd Kühl and AxelTobias Schreiner em Ciências da Computação
na Universidade de Osnabrück, Alemanha
OOLEX
• OOLEX pode ser estendido sem acesso para o
código fonte: símbolo recognizer pode ser
obtido por herança e um scanner de execução
pode ser reconfigurado para diferentes
contextos.
• OOLEX não precisa ser baseado em um
autômato finito e, portanto, ele pode
reconhecer símbolos que sistemas como o flex
OOLEX
• OOLEX é usado para prototipagem rápida: a
maioria dos identificadores existentes podem
ser representados como expressões regulares
para o JLex baseados em Java.
• OOLEX oferece muitas vantagens sobre
Scanners de Expressões Regulares scanners
• OOLEX tem um desempenho pior justificado
OOLEX
• OOLEX pode compilar uma expressão regular
em uma árvore de objetos recognizers
• OOLEX é muito mais fácil de usar, porque já
existe uma biblioteca de recognizers para os
símbolos mais comuns
• OOLEX em sua própria classe quando se trata
de análise léxica
Analisador Léxico
LOLO
LOLO
• LOLO (language-oriented lexer objects) é
estritamente baseada no paradigma de
orientação a objetos.
• Continuação da tese de doutorado de Bernd
Kühl and Axel-Tobias Schreiner em Ciências da
Computação na Universidade de Osnabrück,
Alemanha
LOLO
• Não necessita de autômato finito
– Modelagem de estados, transições e ações
• Reconhece diretamente símbolos que
sistemas como FLEX não
LOLO
• Não necessita de autômato finito
– Modelagem de estados, transições e ações
• Reconhece símbolos que sistemas como flex
não conseguiriam diretamente
LOLO
• Baseia-se na competição de objetos
• Que buscam reconhecer um único símbolo
LOLO
• Um input entra numa "sala" repleta de
objetos
• Caractere a caractere é verificado por cada
objeto, que caso não reconheça é retirado da
sala
• O último objeto a sair é o ganhador
– Reconheceu a maior sequência de caracteres
LOLO
• Principal desvantagem é a performance
• Cerca de 3 vezes mais lento em comparação
ao Flex
Analisador Léxico
FIM