Lex e Yacc Ferramentas para Construcao de Compiladores

1 Ferramentas para a Construção de Compiladores Lex Yacc Disciplina Compiladores Professor Stéfano Schwenck Adaptação Claudio Cesar de Sá UdescSC 2 Construção de Compiladores Analisadores Léxico scanners Sintático parsers e Semântico Tabela de Símbolos e Gerador de Código Grande volume de código Codificação complexa e repetitiva Altamente propensa a erros Desejável a utilização de ferramentas 3 Tipos de Ferramentas Geradores de analisadores léxicos Ex lex flex javacc Geradores de analisadores semânticos Ex yacc bison javacc Geradores de geradores de código Transformam uma LI linguagem intermediária em código assembly da máquina alvo 4 Lex Yacc Ferramentas largamente utilizadas no mundo UNIX Lex gerador de scannersyylex Yacc gerador de parsersyyparse Trabalham juntos na construção de parsers 5 Relação Lex Yacc Sistema lex yacc yylex yyparse Backend do Compilador Sistema de IO 1 n n 6 Lex Gerador de scanners Pode ser utilizado para reconhecimento de qualquer tipo de expressão regular Expressões regulares são transformadas em autômatos Para cada expressão regular especificada devese definir uma ação código em C 7 Formato do Arquivo Lex declarações regras subrotinas de apoio 8 Lex Declarações Códigos em C Abreviações coloque qualquer código em C define FOO 1 como defines ou macros int tokval 0 ou variáveis globais AB ab AB é uma abreviação de ab 9 Lex Regras Formato básico Expressões Regulares Definições regulares Exemplos abcD abcD abcD expressão regular 1 ação 1 expressão regular 2 ação 2 expressão regular n ação n 10 Lex Regras cont Expressões Regularescont Exemplos cont AB abreviação AB Ações Código em C Variáveis Importantes char yytext texto reconhecido pela ER associada a ação unsigned int yylengtamanho do texto 11 Lex Subrotinas auxiliares Qualquer função definida em C Normalmente utilizase esta seção para construção de funções de apoio nas ações Este trecho não é alterado no scanner gerado 12 Lex Pequeno Exemplo include stdioh include ytabh header que define os tokens int numc 0 idc 0 tok 0 NUM 09 ID azAZ azAZ09 NUM numc tok TNUM return getnumber continua 13 Lex Pequeno Exemplo cont continuação ID idc tok TID return dotable return tok TADD return tok TSUB int getnumber return atoiyytext int dotable instala o ID na tabela de símbolos ou retorna seu valor corrente 14 Yacc Yet Another Compiler Compiler Gerador de parsers Transforma uma gramática que define uma linguagem em um autômato de pilha que reconhece esta linguagem implementado em C Para cada produção da gramática existe uma ação semântica 15 Formato do Arquivo Yacc declarações regras de tradução subrotinas de apoio 16 Yacc Declarações Códigos em C de maneira semelhante ao Lex entre Definição de tokens token T1 T2 T3 TN Definição de regras auxiliares para solução de ambigüidades Exemplos right start S 17 Yacc Regras de Tradução Semelhantes a definições gramaticais Cada símbolo terminal ou não tem associado a ele uma pseudo variável O símbolo do lado esquerdo tem associado a ele o A cada símbolo i associase um i i contém o valor do token retornado por yylex se o símbolo i for terminal caso contrário contém o do não terminal 18 Yacc Regras de Tradução cont uma gramática definida assim lado esquerdo alt1alt2altN transformase na seguinte especificação yacc lado esquerdo alt1 ação semântica 1 alt2 ação semântica 2 alt3 ação semântica N As regras são da forma 19 Yacc Subrotinas auxiliares Funções em C que são copiadas para o parser gerado Funciona de maneira semelhante as subrotinas auxiliares do Lex Se o Lex não for usado para especificação do analisador léxico a função yylex deve ser implementada aqui 20 Yacc Pequeno Exemplo define stdioh start init token TNUM TID TADD TSUB init expr printfr d1 continua 21 Yacc Pequeno Exemplo cont continuação expr expr TADD expr 1 3 expr TSUB expr 1 3 expr 2 TNUM subrotinas em C se necessário 22 Lex Yacc Como Utilizar Arquivos Lex são por convenção terminados com l e os do Yacc são terminados em y Utilizando o Yacc bison d arquivoy Obs A opção d faz com que se crie o arquivo h com a definição dos tokens Obs Use a opção v para gerar o arquivo youtput que descreve o autômato de pilha gerado 23 Lex Yacc Como Utilizar cont Utilizando Lex lex arquivol Compilando e gerando o parser gcc o programa alvo lexyyc ytabc ly ll Obs lexyyc é o scanner gerado pelo lex Obs ytabc é o parser gerado pelo yacc Obs y é a biblioteca do yacc e ela deve ser colocada antes da biblioteca do lex l 24 Bibliografia Aho Alfred V et all Compiladores Princípios Técnicas e Ferramentas Livros Técnicos e Científicos tradução 1986 EUA Sun Microsystems Solaris Programing Utilities Guide 1994 USA UNIX Man Pages lex 1 e yacc 1