Lex e Yacc - Ferramentas para Analise Lexica e Sintatica - Guia Introdutorio

Prof Von Zuben DCAFEECUnicamp EA877 1S99 Lex Yacc¹ objetivo genérico ferramentas de auxílio na escrita de programas que promovem transformações sobre entradas estruturadas objetivo específico ferramentas desenvolvidas para programadores de compiladores e interpretadores objetivos específicos secundários ferramentas válidas também para outras aplicações como detecção de padrões em arquivos de dados linguagens de comandos etc vantagens sobre ferramentas alternativas permitem um rápido desenvolvimento de protótipos e uma manutenção simples do software tanto o Lex como o Yacc foram desenvolvidos nos Bell Laboratories ¹ Este material está baseado em Levine Mason Brown lex yacc OReilly Associates Inc 1995 1 Prof Von Zuben DCAFEECUnicamp EA877 1S99 3 papel do Lex toma um conjunto de descrições de possíveis tokens e produz uma rotina em C que irá identificar estes tokens analisador léxico descrições de possíveis tokens expressões regulares especificação léxica 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 nota1 um analisador léxico desenvolvido usando Lex é quase sempre mais rápido do que um analisador léxico escrito diretamente em C nota2 um analisador sintático desenvolvido utilizando Yacc é geralmente mais lento do que um analisador sintático escrito diretamente em C Mas o ganho no desenvolvimento e manutenção do programa é enorme Prof Von Zuben DCAFEECUnicamp EA877 1S99 4 1 Geradores de Analisadores Léxicos a análise léxica pode ser vista como a primeira fase do processo de compilação sua principal tarefa é ler uma seqüência de caracteres de entrada geralmente associados a um códigofonte e produzir como saída uma seqüência de itens léxicos por outro lado a análise sintática tem por objetivo agrupar os itens léxicos em blocos de comandos válidos procurando reconstruir uma árvore sintática conforme ilustrado na figura 1 os itens léxicos são geralmente denominados tokens e correspondem a palavraschave operadores símbolos especiais símbolos de pontuação identificadores variáveis e literais constantes presentes em uma linguagem Prof Von Zuben DCAFEECUnicamp EA877 1S99 Yacc Yet another compilercompiler Stephen C Johnson 1975 Lex Mike Lesk Eric Schmidt desenvolvido posteriormente para trabalhar junto com o Yacc Free Software Foundation Projeto GNU flex bison bison Robert Corbett Richard Stallman versão padronizada POSIX 10032 existem versões também para arquiteturas padrão IBMPC gcc GNU C compiler foi desenvolvido com Lex Yacc etapas Análise léxica dividir as entradas em unidades coerentes tokens Análise sintática descobrir o relacionamento entre os tokens toda tarefa que envolve ambas ou uma das etapas acima é candidata a ser resolvida via Lex eou Yacc 2 Prof Von Zuben DCAFEECUnicamp EA877 1S99 5 o analisador léxico pode executar também algumas tarefas secundárias de interface com o usuário como reconhecer comentários no códigofonte eliminar caracteres de separação espaço tabulação e fim de linha associar mensagens de erro provenientes de outras etapas do processo de compilação com as linhas correspondentes no códigofonte realizar préprocessamento etc Analisador léxico Analisador sintático Tabela de símbolos token Solicitação do próximo token Entrada de caracteres código fonte Árvore sintática Figura 1 Interação entre análise léxica e sintática Prof Von Zuben DCAFEECUnicamp EA877 1S99 6 11 Lex a ferramenta de automatização da análise léxica a ser estudada utiliza o comando lex disponível no UNIX ou seu correspondente flex da GNU O programa Lex produz automaticamente um analisador léxico a partir de especificações de expressões regulares passíveis de representação na forma de autômatos finitos o programa Lex é geralmente utilizado conforme ilustrado na figura 2 O formato geral para a especificação de uma gramática regular em Lex é definições opcional regras rotinas do usuário opcional Prof Von Zuben DCAFEECUnicamp EA877 1S99 7 Compilador Lex programafonte do Lex lexl lexyyc Compilador C aout lexyyc aout Seqüência de entrada Seqüência de tokens Figura 2 Criando um analisador léxico com Lex Prof Von Zuben DCAFEECUnicamp EA877 1S99 8 a seção de definições inclui 1 a definição de macros como digito 01 substituir digito por 01 ao processar as regras frac 09 substituir frac por 09 ao processar as regras nl substituir nl por ao processar as regras 2 a inclusão das linhas de comando em C que devem ser delimitadas por e como include ytabh extern int yylval a redefinição dos tamanhos das tabelas utilizadas pelo gerador tais como número de nós da árvore sintática número de transições e número de estados Prof Von Zuben DCAFEECUnicamp EA877 1S99 9 a seção de regras define a funcionalidade do analisador léxico Cada regra compreende uma seqüência válida de caracteres utilizando literais e expressões regulares e as ações semânticas associadas a ela Lex armazena temporariamente a subseqüência de caracteres identificada na variável yytext do tipo char Podemos então usar a função sscanf da biblioteca de C para convertêla em outros tipos de dados A variável reservada pelo Lex para armazenar o resultado da conversão é yylval A seção de rotinas do usuário é opcional e ela é usada para incluir rotinas em C desenvolvidas pelos usuários como o programa yylex que chama o analisador léxico gerado pelo Lex quando uma seqüência de caracteres de entrada casa com mais de uma regra Lex adota uma das seguintes estratégias para resolver ambigüidades escolher a regra que consegue casar a maior seqüência de caracteres possível Prof Von Zuben DCAFEECUnicamp EA877 1S99 10 quando há mais de uma regra que case com a maior seqüência de caracteres escolher aquela que aparece primeiro na seção de regras embora o Lex seja relativamente simples de entender ele é freqüentemente associado ao Yacc já não tão simples em aplicações no domínio dos compiladores No entanto o Lex pode e deve ser utilizado também como uma ferramenta única 2 Geradores de Analisadores Sintáticos Ferramentas similares e complementares aos geradores de analisadores léxicos Ferramenta mais comum yacc yet another compilercompiler lex gera a função yylex que retorna o identificador de um item léxico reconhecido Prof Von Zuben DCAFEECUnicamp EA877 1S99 11 yacc gera a função yyparse que analisa os itens léxicos e decide se eles formam ou não uma sentença válida 21 Passos para gerar analisador sintático Escrever programa analisador léxico ou usar ferramenta lex para tal Escrever gramática da linguagem em arquivo com extensão y Escrever programa analisador sintático ou usar a ferramenta yacc para tal Compilar e ligar os programasfonte Para yylex e yyparse trabalharem em conjunto é preciso garantir que os tokens e seus valores sejam comuns às duas funções Prof Von Zuben DCAFEECUnicamp EA877 1S99 12 22 Formato geral da gramática de Yacc Similar ao da gramática de lex três seções no arquivo y definições declaração de nomes e tipos de tokens de variáveis etc regras contém as produções da gramática em BNF símbolo derivações ações semânticas rotinas do usuário contém a função principal main e outras rotinas do usuário Prof Von Zuben DCAFEECUnicamp EA877 1S99 13 3 Cooperação entre LEX e YACC para obter um analisador sintático com o uso de Lex e Yacc é necessário veja figura 3 1 especificar a gramática de definição dos itens léxicos em linguagem de especificação de Lex num arquivo por convenção com extensão l e gerar o analisador léxico em C yylex através do seguinte comando flex filenamel O arquivo que contém yylex é denominado lexyyc 2 especificar a estrutura sintática da linguagem através da linguagem de especificação de Yacc num arquivo por convenção com extensão y e gerar o analisador sintático em C yyparse através do seguinte comando yacc d filenamey A chave d indica que um arquivo de definição de itens léxicos e tipo de dados da variável global yylval Prof Von Zuben DCAFEECUnicamp EA877 1S99 14 filenametabh deve ser gerado Este arquivo estabelece a dependência simbólica entre o analisador léxico e o sintático Yacc inclui automaticamente as chamadas a yylex para obter os itens léxicos e os seus valores O arquivo que contém yyparse é chamado filenametabc 3 compilar e ligar os programasfonte com outros programas adicionais através do seguinte comando cc o filename filenametabc lexyyc ly ll para gerar o código executável por exemplo filename Os indicadores y e l correspondem à inclusão de rotinas das bibliotecas em C libya e libla respectivamente Prof Von Zuben DCAFEECUnicamp EA877 1S99 15 Gramática especificada no formato LEX num arquivo com extensão l Gramática especificada no formato YACC num arquivo com extensão y Analisador léxico yylex no arquivo lexyyc Analisador sintático yyparse no arquivo filenametabc Outros programas em C cc Programa Rotinas das bibliotecas libla e libya lex ou flex yacc ou bison Figura 3 Esquema do uso de Lex e Yacc Prof Von Zuben DCAFEECUnicamp EA877 1S99 16 Exemplos Os programas a seguir devem ser compilados com o comando flex pl seguido do comando gcc lexyyc ll o p p1l AZ printfc yytext0aA ECHO Execute o seguinte comando p1 p1l p2l int nlin0 Qqchar NovaLinha QqcharNovaLinha nlinnlin1printf4d s nlin yytext Execute o seguinte comando p2 p2l Prof Von Zuben DCAFEECUnicamp EA877 1S99 17 p3l Dia 0011 Tarde 1217 Noite 1823 Dia printf Bom Dia Tarde printf Boa Tarde Noite printf Boa Noite Execute o seguinte comando date p3 p4l int count0 count main yylex printf d palavras contadas count Prof Von Zuben DCAFEECUnicamp EA877 1S99 18 p5l then var printf printf mod printf or printf and printf begin printf end printf program printfmain printf printf printf integer ShuffleInt ECHO ShuffleInt int i printfint fori0 yytexti i printfc yytexti printf Prof Von Zuben DCAFEECUnicamp EA877 1S99 19 p6l 1909 printfDecimal 007 printfOctal 0xX09AFaf printf Hexadecimal printfNao numerico Calculadora lex include ytabh integer 09 nl integer sscanfyytextdyylvalintegerreturn INTEGER nl extern int lineno lineno return return yytext0 Prof Von Zuben DCAFEECUnicamp EA877 1S99 20 Calculadora yacc include stdioh union double real int integer token integer INTEGER type integer expr left left nonassoc UMINUS lines nothing lines line line expr printfd 1 error yyerror Prof Von Zuben DCAFEECUnicamp EA877 1S99 21 expr INTEGER expr expr 1 3 expr expr 1 3 expr expr 1 3 expr expr if3 1 3 else yyerrordivide by zero expr 2 expr prec UMINUS 2 int lineno 0 main yyparse yyerrors char s printfcalc s s printfline d lineno Prof Von Zuben DCAFEECUnicamp EA877 1S99 22 Calculadora científica lex include ytabh integer 09 real 0909 nl integer sscanfyytext d yylvalinteger return INTEGER real sscanfyytext lf yylvalreal return REAL nl extern int lineno lineno return sin return SIN cos return COS tan return TAN return yytext0 Prof Von Zuben DCAFEECUnicamp EA877 1S99 23 Calculadora científica yacc include stdioh include mathh union double real int integer token integer INTEGER token real REAL token SIN COS TAN type integer expri type real expr left left nonassoc UMINUS lines nothing lines line Prof Von Zuben DCAFEECUnicamp EA877 1S99 24 line expr printflf 1 error yyerror expri INTEGER expr REAL expri 1 SIN expr sin3 COS expr cos3 TAN expr tan3 expr expr 1 3 expr expr 1 3 expr expr 1 3 expr expr if3 1 3 else yyerrordivide by zero expr 2 expr prec UMINUS 2 Prof Von Zuben DCAFEECUnicamp EA877 1S99 25 int lineno 0 main yyparse yyerrors char s printfcalc s s printfline d lineno 4 Autômatos finitos Definição Um autômato finito M é uma quíntupla ordenada M S s0 F A g 1 S é um conjunto finito de estados 2 s0 S é o estado inicial 3 F S é um conjunto de estados finais 4 A é um alfabeto de entrada 5 g S A S é um conjunto finito de aplicações de transição Prof Von Zuben DCAFEECUnicamp EA877 1S99 26 5 Expressões regulares Uma expressão regular é um objeto matemático específico que permite a escrita concisa de uma seqüência válida de caracteres Para tanto são utilizados operadores na forma de metacaracteres sendo que os mais comuns são apresentados na tabela 1 Mesmo sabendo ser possível descrever a sintaxe léxica de uma linguagem utilizando gramáticas livres de contexto esta descrição geralmente é feita por meio de expressões regulares pelas seguintes razões 1 as regras léxicas de uma linguagem são geralmente muito simples não necessitando uma descrição gramatical recurso demasiadamente poderoso para tal fim 2 expressões regulares geralmente fornecem uma notação mais concisa e fácil de entender do que a correspondente representação gramatical 3 analisadores léxicos automáticos construídos a partir de expressões regulares são mais eficientes que aqueles construídos a partir de gramáticas arbitrárias Prof Von Zuben DCAFEECUnicamp EA877 1S99 27 Tabela 1 Metacaracteres utilizados em expressões regulares Operador Significado Exemplo a expressão anterior é opcional 541 541 ou 51 qualquer repetição inclusive vazio a aaa qualquer repetição exclusive vazio a aaa alternativa entre duas expressões ab a ou b agrupamento de expressões qualquer caracter exceto linefeed casa com o início de uma linha exceto quando está entre quando significa complemento fim de uma linha qualquer caracter especificado abc abc dentro de qualquer caracter entre os extremos 09 0123456789 indica o número de repetições permitido ou substitui uma definição macro a12 aaa digito 01 permite interpretar o próximo caracter como caracter comum É também utilizado para representar caracteres nãoimprimíveis tabulação b blank linefeed especifica um conjunto de seqüências seguida de uma expressão 012Y aceita qualquer seqüência composta de 0 1 e 2 seguida de Y Prof Von Zuben DCAFEECUnicamp EA877 1S99 28 Exercícios 1 Apresente a expressão regular mais compacta que seja capaz de descrever qualquer número decimal positivo e somente eles com a parte inteira sendo separada da parte fracionária por ponto quando for o caso Por exemplo são seqüências válidas 089 12 40 32748 3452 2 Como uma alternativa à expressão regular obtida acima apresente o autômato finito que permite validar ou não qualquer número decimal positivo Resolva a questão com base nas seguintes hipóteses existem dois tipos de símbolos terminais ou eventos 09 e utilize dois estados finais lembrando que a seqüência de caracteres só é válida se for atingido um estado final e não houver mais caracteres a processar para qualquer estado deve haver uma lei de transição de estados a partir de cada um dos eventos existentes