14/08/2000 DIN - UEM 1

Ferramentas para a Construção de Compiladores: Lex & Yacc

Disciplina: Compiladores

Professor: Marcelo Morandini

Monitor: Alysson Neves BessaniAdaptação: Claudio Cesar de Sá

claudio@joinville.udesc.br

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 scanners(yylex()); Yacc: gerador de parsers(yyparse()); Trabalham juntos na construção de

parsers.

5

Relação Lex, Yacc, Sistema

lex

yacc

yylex()

yyparse()

“Backend”do

Compilador

Sistema de I/O

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 deve-se 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 (‘a’|’b’) /* AB é uma abreviação de a|b */

9

Lex: Regras

Formato básico:

Expressões Regulares:– Definições regulares;– Exemplos:

• [abcD]+ (a|b|c|D) (a|b|c|D)*

• .\+ ?+

<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 Regulares(cont):

– 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 yyleng:tamanho do texto;

11

Lex: Subrotinas auxiliares

Qualquer função definida em C; Normalmente utiliza-se 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 <stdio.h>#include ‘y.tab.h’ /* header que define os tokens */

int numc = 0, idc = 0, tok = 0;%}

NUM [0-9]ID [a-zA-Z_$] [a-zA-Z0-9_$]*

%%{NUM} {numc++;

tok = TNUM; return get_number();}

/* continua */

13

Lex: Pequeno Exemplo (cont)/* continuação */{ID} {idc++;

tok = TID; return do_table();}

\+ {return tok = TADD;}- {return tok = TSUB;}

%%

int get_number(){return atoi(yytext);

}

int do_table(){/* 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 associa-se 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> := <alt1>|<alt2>|...|<altN>

/* transforma-se 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 <stdio.h>%}

%start init%token TNUM TID TADD TSUB

%%

init : expr ‘\n’ {printf(‘r: %d’,$1);} ;/* 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:– yacc -d <arquivo.y>

• 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 y.output, que descreve o autômato de pilha gerado.

23

Lex & Yacc: Como Utilizar (cont) Utilizando Lex:

– lex <arquivo.l> Compilando e gerando o parser:

– cc -o <programa alvo> lex.yy.c y.tab.c -ly -ll

• Obs: lex.yy.c é o scanner gerado pelo lex;• Obs: y.tab.c é 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).