Analisador Léxico

Analisador Léxico

Fabiano Rodrigues Farley J. R. Oliveira 051.649-1 Michel Sato Vitor Lins Vieira 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 IDENT= ASSIGN_OP3 NUMBER+ ADD_OP2 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

• CODIGOConté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 Axel-Tobias 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 não reconhece diretamente.

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 pela flexibilidade, um ciclo de desenvolvimento mais curtos e mais funcionalidades.

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

LOLO

Analisador Léxico

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