Lex e Yacc
Compiladores
Giovani Rubert Librelotto
[email protected]
Adaptação: Claudio Cesar de Sá
[email protected]
Roteiro

.... Há muita teoria... Até chegar neste
ponto...
Definição


Lex e Yacc são ferramentas que ajudam a criar
rotinas C para analisar e interpretar um arquivo de
entrada, na construção de um compilador
Eles podem ser usados para ajudar a escrever
compiladores e interpretadores, ou qualquer
outro programa cuja entrada pertence a uma
estrutura bem definida, e que deseja
transformar em outra.
Lex



Lê um arquivo contendo expressões regulares para
“pattern matching”
e gera rotinas C que
executam a análise léxica.
Essa rotina lê a entrada e identifica “tokens”.
Os “tokens” são definidos a partir de expressões
regulares (gramática regular, etc).
Yacc
Lê um arquivo que codifica a gramática de
uma linguagem e gera uma rotina de
“parsing”.
 Essa rotina agrupa os “tokens” em uma
seqüência significativa (de interesse), e
invocar rotinas para agir (realizar ações)
sobre elas.

Compiladores


Um compilador pega a descrição de um programa
e converte para um conjunto de instruções que
pode ser executadas por um computador.
A execução de um compilador tem 3 estágios:



Análise léxica - LEX
Análise sintática e semântica - YACC
Geração de Código.
Diagrama de um Compilador
Text File
usuário
Compiler
Progama
Executável
Etapas de um compilador
Cada estágio prepara a entrada para o
próximo estágio;
 Desse modo, o sistema operacional provém
um arquivo em bytes, a análise léxica
provém um agrupamento de tokens, o parser
provém um agrupamento de tokens em
instruções dentro da linguagem, e as ações
provém interpretação para os valores dos
tokens.

Modelo básico de processamento
para compiladores
input
Analisador
Léxico
Analisador
Sintático
(Parser)
Ações
Características Gerais






Lex gera código C para análise léxica.
Yacc gera código C para um parser.
Ambas especificações são menores que um
programa e mais fáceis de ler e entender.
Por definição, o sufixo de um arquivo Lex é .l e de
um arquivo Yacc é .y
Lex cria uma rotina chamada yylex em um
arquivo lex.yy.c
Yacc cria uma rotina chamada yyparse em um
arquivo chamado y.tab.c
Especif.
LEX
*.l
lex
Especif.
YACC
yacc
lex.yy.c
yylex( )
*.y
*.c
y.tab.c
yyparse( )
cc
program
Rotinas
C
Bibliot.
UNIX
libl.a
liby.a
Exemplo de Análise Léxica

Um programa que classifica uma entrada
em diversos tipos de tokens:
números;
 comandos;
 strings;
 comentários.

Programa em C (pags. 5 e 6)
 Especificação Lex (pag 7)

Expressões Regulares
Elas provém flexibilidade em muitas
situações.
 Ex.:



([0-9]*\.)*[0-9]+
Essa expressão permite reconhecer os
seguintes números:
100
 6.8
 45.92

Modelo de um autômato finito
[0 - 9]
[0 - 9]
1
0
. (ponto decimal)
. (ponto decimal)
2
[0 - 9]
[0 - 9]
3
Ações



A função básica de uma rotina léxica é retornar
tokens ao parser.
As ações, em uma especificação Lex, consiste em
expressões da linguagem C que retornam o token.
Para retornar o token em uma ação, usa-se a
expressão return.

[0-9]+
{
}
yylval = atoi(yytext);
return NUMBER
Um Parser




Um analisador léxico gera uma entrada para um
parser interpretar.
O parser organiza os tokens de acordo com as
regras de uma gramática.
A gramática, para uma linguagem de
programação, descreve a estrutura de entrada de
um programa.
Quando o parser tem uma seqüência de tokens,
que corresponde a uma regra, a ação associada é
executada.
Sumário de Rotinas Léxicas e
Sintáticas




A rotina main invoca (chama) yyparse para avaliar
se a entrada é válida.
yyparse invoca a rotina invoca a rotina yylex cada
vez que precisa de um token.
A rotina léxica lê da entrada, e a cada token
encontrado, retorna o número do token para o parser.
A rotina léxica pode também passar o valor do token
usando a variável externa yylval.
Fluxo de controle em rotinas léxicas
e sintáticas
main
Entrada
avaliada
Retorna 0 se
entrada é valida
1 se não
yyparse( )
Valor da
ação do
processo
yylval
Requerer
próximo token
Retornar o token
ou 0 se EOF
Ler chars
da entrada
yylex( )
Valor passado
do token
input
Os Mecanismos de Lex e Yacc
A partir de agora, o objetivo é ajudar a
entender como esses programas funcionam.
 E o que os programas geram.
 Veremos alguns programas simples.
 Será o básico do Lex e do Yacc.

LEX
1.1 Genericamente


É um gerador de programas (módulos) destinados
a processamento léxico de testos.
O módulo gerado pode funcionar como:





Filtro para processamento léxico;
“Pattern Matching” (expressões regulares);
Reconhecedor de linguagens regulares simples;
Pré-processador simples;
Analisador léxico para ligação de módulos de
reconhecimento sintático.
Usando o LEX

São três (quatro) etapas:
Escrever uma especificação Lex que contém
seqüências de caracteres em uma entrada. Esse
arquivo, por convenção, tem o sufixo .l.
 Executar a especificação Lex. Esse passo gera
um arquivo chamado lex.yy.c.
 Compilar lex.yy.c e qualquer arquivo fonte.






lex.yy.c não contém um programa completo.
Ele contém uma rotina léxica chamada yylex.
Você pode integrar o analisador léxico com um
parser gerado no Yacc.
Um programa léxico também assume a existência
de outras rotinas de suporte.
Você pode fornecer essas rotinas, ou usar as
bibliotecas standart do UNIX, a libl.a.
1.2 Funcionamento



Com base num texto “lex”, é gerado um módulo C
que contém um reconhecedor baseado em
autômatos determinísticos.
Este vai permitir encontrar patterns num texto de
entrada e sobre eles executar uma ação semântica
correspondente.
O módulo C é automaticamente escrito em um
arquivo “lex.yy.c” que inclui numa função
“yylex()”, a qual executa o algoritmo que se
apresenta:
FUNCAO yylex( ) : int
REPETIR
| yytext <- “ ”
| c <- input( )
| ENQUANTO (c cabe numa ExpRegular)
|
| yytext <- concatenar (yytext, c)
|
| c <- input( )
|
| executar a acãoC correspondente a ExpRegular
ATE chegar ao fim do input
yywrap( )
Escrevendo uma especificação
Lex




A principal seção de uma especificação léxica
contém um conjunto de regras.
A especificação mínima segue o formato:
%%
rules
%% indica o início da seção de regras.
Cada regra consiste em uma expressão regular.
1.3 Estrutura de um texto LEX

<definições gerais>
“%%”
<regras de tradução>
“%%”
<rotinas C auxiliares>
Cada regra vai ter a seguinte estrutura:
<EspRegular> “{“ <AçãoC> “}”
1.4 Um exemplo simples
%%
zippy
%%



printf(“Eu reconheci zippy”)
Este texto lex especifica um filtro para substituir
as ocorrências de “zippy” por “Eu reconheci ...”.
Todo o texto que não se “encaixe” em nenhum
pattern é simplesmente copiada pra saída.
Neste exemplo, tanto as definições gerais, como as
“rotinas C auxiliares” são inexistentes.
1.5 Utilização

cat sample.l
%%
zippy
%%


printf(“Eu reconheci zippy”)
lex sample.l
ls
lex.yy.c sample.l


cc -o sample lex.yy.c -ll
ls
lex.yy.c sample* sample.l

cat test
zippy
harry
zippy and zip

cat test | sample
Eu reconheci zippy
harry
Eu reconheci zippy and zip
Exemplo 2
%%
zip
printf(“ZIP”);
zippy
printf(“Eu reconheci zippy”);
zippy$
printf(“Achei zippy na final da linha”);
 Depois de refazer todas as etapas anteriores:
Achei zippy na final da linha
harry
Eu reconheci zippy and ZIP
Exemplo 3
%%
[A-Z]+ [ \t\n]
.
 cat test.caps
printf(“%s”, yytext);
;
Xview é uma API executando sob o X Window que suporta o
OPEN LOOK GUI.

caps < test.caps
API X
OPEN LOOK
Usando a especificação completa
<definições gerais>
“%%”
<regras de tradução>
“%%”
<rotinas C auxiliares>
Exemplo 4 - cutter.l
%%
int field_count = 1;
extern int field_cut;
\t
++field_count;
\n
{ECHO; field_count = 1; }
[^\t\n]+ {if(field_count == field_cut)
;
else
printf(“%s”, yytext); }
%%
int field_cut;
main(argc, argv)
int argc;
char *argv[ ];
{
if (argc > 1)
field_cut = atoi(argv[1]);
else
field_cut = 1;
yylex( );
}
lex cutter.l
 cutter 3 < test.cuts
 cc -o cutter lex.yy.c - abc def jkl
mno pqr
ll
wxy z
 cat test.cuts
 cutter < test.cuts
abc def ghi jkl

mno pqr stu
wxy z
def ghi jkl
pqr stu
z
1.5.1 Opções do comando LEX

-r 
ações em Fortran (RATFOR)

-t 
o arquivo lex.yy.c é enviado para
saída padrão

-v 
fornece estatísticas do autômato
gerado
1.6 Funcionamento como préprocessador

Para desenvolver um pré-processador, podese usar o módulo gerado através da função
correspondente ao seguinte algoritmo:
enquanto não fim input
yytext <- getSimbolo()
efetuar ação correspondente ao tipo de
símbolo encontrado
1.7 Funcionamento como
Analisador Léxico

Para funcionar como uma analisador léxico de um
compilador a ser invocado por um Parser, cada vez
que um símbolo é reconhecido, guarda-se o seu
valor (numa variável global) e retorna inteiro; para
tal, as regras terão o seguinte aspecto:
ExpReg
{ yylval <-- [guardar o valor do
símbolo];
return(código); }
YACC
Introdução
YACC é um comando UNIX.
 Seu significado é – Yet Another Compiler
Compiler
 O YACC recebe um texto com a descrição
de uma gramática com ações semânticas,
isto é, ações em C que indicam o que é que
se deve fazer cada vez que reconheceu uma
produção.





Ele gera um reconhecedor sintático do tipo
SLR(1) correspondente.
YACC é, portanto, um gerador de programas.
O texto de entrada pode incluir procedimentos
e/ou funções auxiliares.
O texto do reconhecedor gerado (código C) pode
ser unido a outros módulos e transportado para
outros ambientes.
Usando Yacc

São 4 passos para criar um parser:
Escrever uma especificação de uma gramática.
O arquivo terá a extensão .y.
 Escrever um analisador léxico que pode
produzir tokens, o yylex.
 Executar yacc na especificação para gerar o
código do parser, o y.tab.c.
 Compilar e linkar os códigos fontes para o
parser e o analisador léxico e rotinas auxiliares.






A saída y.tab.c contém uma rotina yyparse que
chama a rotina léxica yylex, para cada novo token.
Como Lex, Yacc não gera programas completos.
yyparse deve ser chamado de uma rotina main.
Um programa completo também requer uma rotina
de erro chamada yyerror chamada pelo yyparse.
Ambas, main e yyerror, podem ser supridas pelo
programador, através da biblioteca liby.a, que
pode ser linkada com a opção -ly, na compilação.
Escrevendo uma Especificação
Yacc

Uma especificação Yacc descreve uma gramática
livre do contexto que pode ser usada para gerar um
parser. Ela tem 4 classe de elementos:




Tokens, que é o conjunto de símbolos terminais;
Elementos sintáticos, que são os símbolos não terminais.
Regras de produção, que definem símbolos não terminais,
em termos de seqüência de terminais e não terminais;
Uma regra start, que reduz todos os elementos da
gramática para uma regra simples.
Foco de uma especificação Yacc



É um conjunto de regras de produções da forma:
símbolo:
definição
{ação}
;
Dois pontos (:) separam o lado esquerdo do lado
direito da regra, e o ponto-e-vírgula (;) finaliza a
regra.
Por convenção, a definição segue 2 “tabs” após os
dois pontos.
Símbolos




Cada regra em uma gramática é chamada por um
símbolo, um não terminal.
A definição consiste de zero ou mais terminais
(tokens ou caracteres literais) e outros não terminais.
Tokens são símbolos terminais reconhecidos pelo
analisador léxico, e só aparecem no lado direito da
regra.
Cada definição pode ter uma ação em C associada a
ela. Essa ação está entre chaves ( { } ).
Símbolos (continuação)





Os nomes de símbolos podem ter qualquer
tamanho, consistindo de letras, ponto, sublinhado
e números (exceto na primeira posição).
Caracteres maiúsculos e minúsculos são distintos.
Os nomes de não terminais são em minúsculos.
Tokens, em maiúsculos.
Uma especificação mínima Yacc consiste de uma
seção de regras precedidas por uma declaração dos
tokens usados na gramática.
Formato da especificação

O formato é similar ao formato do Lex.
declarações
%%
regras da gramática
%%
programas C
Exemplo 1 - print_int.y
%token INTEGER
%%
lines :
/* empty */
|
lines line
{
printf(“= %d\n”, $2); }
;
line :
INTEGER ‘\n’
{
$$ = $1; }
;
%%
#include “ lex.yy.c”
print_int




Especificação para gerar um programa que
imprime qualquer número recebido como entrada.
Na seção declaração, declaramos o token
INTEGER. Este símbolo é usado para a
comunicação entre o analisador léxico e o parser.
Na seção da gramática, especificamos lines e line.
A regra lines é definida para 0 ou mais linhas de
entrada.


A primeira alternativa é vazia.
A segunda alternativa é recursiva.
print_int.y - Ações das regras




Yacc provém pseudo-variáveis, que facilitam a as
ações de pegar o valor de um símbolo e setar o
valor retornado por uma ação.
O $ tem significado especial para o Yacc.
O valor de cada elemento pode ser obtido usando
a notação posicional: $1 para o 1º token, $2 para o
2º, e assim por diante.
O valor retornado pela ação é setado pela tarefa
para $$.
print_int.y - Ações das regras
line

:
{
Essa ação, “$1” retorna o token INTEGER. Há 2
elementos na definição, mas o ‘\n’ não retorna.
|
{

INTEGER ‘\n’
$$ = $1; }
lines line
printf(“= %d\n”, $2); }
Nessa ação, “$2” refere-se ao valor de line.
print_int.l - Analisador léxico
%%
[0-9]+
\n
[-+=]
quit
.
{
sscanf(yytext, “%d”, &yylval);
return(INTEGER);
}
return(‘\n’);
return yytext[0];
return 0;
;
print_int.y - #include



A terceira parte deste exemplo de especificação
Yacc contém a instrução #include.
Ela inclui o código para analisador léxico.
Para testar a especificação:
lex print_int.l
yacc print_int.y
cc -o print_int y.tab.c -ly -ll
print_int - Execução
$> print_int
3
=3
15
= 15
6
=6
zippy
sintax error
1.1 Gramática do YACC
textoYacc
->
<definições> “%%”
<produções> “%%”
<codigoCaux>
<definições>
->
<def>*
<produções>
->
<produção>+
1.1.1 Zona de Definições

Em <definições> são definidos os seguintes
elementos referentes a gramática:
Axioma da gramática;
 Conjunto dos terminais (T) e respectivo tipo de
valor, caso exista;
 Tipo de valor associados a cada não terminal
(NT), caso exista;


Ainda em <definições>, encontram-se
elementos referentes a resolução automática
de conflitos e ambigüidades:
Indicação de propriedades de operadores;
 Indicação de associatividade de operadores (à
esquerda, direita ou não associatividade).

1.1.1.1 Código C global
<def>
->
|
|
<defAxioma>
<defTipodeValor>
“%{“ <códigoCglobal> “%}”
|
<defTerminais>
|
<defAssociatividade>
|
<defTipodeValorT_NT>
<defAxioma> --> “%start” <unionDef>
<defTiposdeValor> -> “%union” <unionDef>
Definição de tipos de valores para T e NT.
 Esta definição será usada internamente para
a declaração de uma stack valor.
 <unionDef> é uma declaração de uma
union C;
 <unionDef> vai definir um conjunto de
identificadores de tipos que poderão ser
usados em <tipo>.

<defTerminais> -> “%token” <tipo> <T>*
Define os terminais da gramática podendo
ainda associar-lhes um tipo de valor.
 Essa definição pode ser feita em várias
linhas.

<tipo>
->
|
“<“ ID “>”
Tipo é opcional.
 Quando usado, ID é um identificador que
deve figurar na <unionDef> da
<defTipos_T_NT>

<defAssociatividade> -> “%left” <tipo> <T_NT>*
| “%rigth” <tipo> <T_NT>*
| “%noaccoc” <tipo> <T_NT>*



Indica se um operador é associativo ou não.
Esta informação é usada para tratamento de
conflitos. Nota-se, portanto, que podem ser
tratadas gramáticas ambíguas.
A cada símbolo S fica associada uma propriedade
de acordo com a ordem que ela aparece:


Os S declarados na mesma linha tem igual prioridade.
Os S declarados na linha i tem prioridade maior que os
da linha i-1.
<defTiposdeValorT_NT> -> “%type” <tipo> <NT>*

Permite associar um tipo de valor a um
terminal ou não terminal.
1.1.2 Produções
<produção> -> <NT> “:” <rhss>
Produção da gramática segundo a estrutura
sintática habitual.
 <NT> = não terminal
 rhs = rigth hand side – lado direito da produção

<rhss>

->
|
<rhs>
<rhs> “|” <rhss>
Lado direito possivelmente múltiplo, e
nesse caso, separa-se por “|”
<rhs>

->
|
<simb>*
<simb>* <prec>
Lado esquerdo é uma seqüência de
símbolos podendo opcionalmente incluir
<prec> para alternar propriedades de
operadores.
<simb>
->
|
|
<T>
<NT>
<simbSemântico>
T = símbolo terminal
 NT = símbolo não terminal
 simbSemantico = Símbolo semântico, para
colocar ações no parser.

<T> ->
|

ID_token
“ ’ ” char “ ‘ “
T – símbolo terminal é um identificador
declarado como token ou caracter entre
aspas.
<NT>

->
ID
O identificador ID deve figurar, em pelo
menos, um lado esquerdo de uma produção.
<simbSemantico> -> “{“ <codigoCcom$> “}”




<codigoCcom$> -> código C com possibilidade
de usar $$, $1, ...;
$$ permite a associação de um valor ao lado
esquerdo da produção ($$ = .. – atributo
sintetizado)
$i permite a utilização de um valor de um símbolo
do rhs (i – na ordem do símbolo)
Esse símbolo pode ser T, NT ou simbSemantico.
<prec>

->
“%prec” <T>
Permite associar a prioridade de um
símbolo terminal T a uma produção.
1.1.3 Código C
<codigoCaux> ->
|
<funcoes_C>
“%%” <funcoes_C>
/* vazio*/
-> código C puro;
Não esquecer a definição da
função de análise léxica
yylex()
Ex: #include “lex.yy.c”
Exemplo: Calculadora
Operações da Calculadora

Soma:


3+9
Subtração:

36.4 - 95
Análise

Léxica:
36.7 + 43.2
 REAL PLUS REAL


Sintática:
rexpr <-- REAL | rexpr ‘+’ rexpr
{$$ = $1 + $3;}
 line <-- ‘\n’ | rexpr ‘\n’

Expressões regulares para tokens

Para números inteiros:


Para números reais:


[0-9]+
[0-9]*\”.”[0-9]+
Para números reais com expoentes:

([0-9]*\”.”[0-9]+) | ([0-9]*\”.”[0-9]+ [eE] [+-]? [0-9]+)
Falta o exemplo da calculadora.
Está no texto em inglês, no
arquivo em PDF e no primeiro
link do site!