Lex e Yacc

.... Há muita teoria... Até chegar neste ponto...
Definição


Lex e Yacc são ferramentas que ajudam a criar
programas C para analisar e interpretar um
arquivo de entrada.
Eles podem ser usados para ajudar a escrever
montadores, compiladores e interpretadores, ou
qualquer outro programa cuja entrada
pertence a uma estrutura bem definida, e que
se deseja transformar em outra.
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.
Essa rotina lê a entrada e identifica “tokens”.
Os “tokens” são definidos a partir de expressões
regulares (especificação léxica).
Yacc


Lê um arquivo que codifica a gramática de uma
linguagem e produz uma rotina em C que irá
executar a análise sintática, ou parsing, desta
gramática.
Essa rotina agrupa os “tokens” em uma sequência
de interesse e invoca rotinas para realizar ações
sobre elas.
Montadores


Um montador recebe como entrada um programa
em linguagem de montagem (que pode ser lido
por humanos) e gera como saída um programa
em linguagem de máquina (bits: adequado para
máquinas).
O funcionamento de um montador pode ser
decomposto em três etapas:



Análise léxica - LEX
Análise sintática e semântica - YACC
Geração de Código.
Diagrama de um Montador
Arquivo
texto
usuário
Montador
Programa
Executável
Etapas de um montador

Cada estágio prepara a entrada para o próximo
estágio.



O usuário disponibiliza um arquivo texto (bytes)
O analisador léxico detecta e disponibiliza tokens para
o parser
O parser detecta agrupamentos de tokens segundo os
comandos da linguagem de montagem e gera o código
(realiza Ações) associado aos comandos.
Modelo básico de processamento
para montadores
input
Analisador
Léxico
Analisador
Sintático
(Parser)
Ações
Características Gerais




A análise léxica pode ser vista como a primeira fase de um
processo de tradução (compilação).
Sua principal tarefa é ler uma seqüência de caracteres de
entrada, geralmente associados a um código-fonte, 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.
Os itens léxicos são geralmente denominados tokens e
correspondem a palavras-chave, operadores, símbolos
especiais, símbolos de pontuação, identificadores
(variáveis) e literais (constantes) partes de uma
linguagem.
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( )
gcc
programa
Rotinas
C
Bibliot.
UNIX
libl.a
liby.a
Análise Léxica

Processo (programa) que classifica partes do
arquivo texto de entrada em diversos tipos de
tokens:





números;
comandos;
strings;
comentários.
Pode ser especificada por meio de expressões
regulares, passíveis de representação na forma
de autômatos finitos.
Expressões Regulares


Forma compacta de descrever uma sequência de
caracteres.
Ex.:


([0-9]*\.)*[0-9]+
Essa expressão permite reconhecer os seguintes
números:



100
6.8
45.92
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;
Parser




Um analisador léxico gera uma entrada para um parser
interpretar.
O parser tenta organizar os tokens de acordo com as
regras de uma gramática.
A gramática, para uma linguagem de programação,
descreve a estrutura de um programa.
Quando o parser encontra uma seqüência de tokens que
corresponde a um comando da linguagem, a ação
associada é executada.
Sumário de Rotinas Léxicas e
Sintáticas de um Tradutor




A rotina main do tradutor invoca (chama) yyparse para
avaliar se a entrada é válida.
yyparse invoca a rotina yylex cada vez que precisa de
um token.
A rotina léxica lê a 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 (entre outras).
Fluxo de controle de um tradutor
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
LEX
Lex


É um gerador de programas (módulo) destinados
ao processamento léxico de textos.
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 uso em conjunto com módulos
de reconhecimento sintático.
Usando o LEX

Etapas:




Escrever um arquivo texto com uma especificação Lex.
Esse arquivo, por convenção, tem o sufixo .l.
Executar o lex usando como entrada o arquivo .l. Esse
passo gera um arquivo chamado lex.yy.c.
Compilar lex.yy.c com o gcc, juntamente com quaisquer
outros arquivos fonte ou bibliotecas eventualmente
necessárias.
Usar o executável gerado para análise léxica.





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
aquelas presentes na biblioteca standard do
UNIX, a libl.a.
Estrutura de um texto LEX (.l)
<definições gerais> /* opcional */
“%%”
<regras de tradução>
“%%”
<rotinas C do usuário > /* opcional */
Estrutura de um texto LEX (.l)

A seção de definições pode possuir:

1. A definição de macros como:




digito [01]+ /* substituir {digito} por [01]+ ao processar as
regras */
frac .[0-9]+ /* substituir {frac} por .[0-9]+ ao processar regras */
nl \n /* substituir {nl} por \n ao processar as regras */
2. A inclusão das linhas de comando em C, que devem
ser delimitadas por <%{> e <%}>, como:
%{
#include <y.tab.h>
extern int yylval;
%}
Estrutura de um texto LEX (.l)



A seção de regras define a funcionalidade do
analisador léxico.
Cada regra compreende uma seqüência válida de
caracteres (descrita utilizando literais e
expressões regulares) e as ações semânticas
associadas a ela.
As regras têm a seguinte estrutura:
<EspRegular> “{“ <AçãoC> “}”
Estrutura de um texto LEX (.l)




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; é usada
para incluir rotinas em C desenvolvidas pelos
usuários.
Estrutura de um texto LEX (.l)

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;
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.
Um exemplo simples
%%
zippy
%%



printf(“Eu reconheci zippy”);
Este texto lex especifica um filtro para substituir as
ocorrências de “zippy” por “Eu reconheci zippy”.
Todo o texto que não se “encaixe” em nenhum pattern é
simplesmente copiado para a saída.
Neste exemplo, tanto as definições gerais, como as
“rotinas C auxiliares” são inexistentes.
Utilização

cat sample.l
%%
zippy
%%


printf(“Eu reconheci zippy”);
lex sample.l
ls
lex.yy.c sample.l


gcc -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

cat sample2.l
%%
zip
zippy
zippy$
%%



printf(“ZIP”);
printf(“Eu reconheci zippy”);
printf(“Achei zippy no final da linha”);
lex sample2.l
gcc -o sample2 lex.yy.c -ll
cat test | ./sample2
Achei zippy na final da linha
harry
Eu reconheci zippy and ZIP
Exemplo 3
cat sample3.l
%%
[A-Z]+[ \t\n]
printf(“%s”, yytext);
.
;
%%

lex sample3.l

gcc -o caps lex.yy.c -ll

cat test.caps

Xview é uma API executando sob o X Window que suporta o {pula linha}
OPEN LOOK GUI.

./caps < test.caps
API X
OPEN LOOK
Trabalho 1 (enviar para
[email protected])

Faça um arquivo .l que detecte:







O mnemônico “add” e retorne o token ADD.
Números inteiros em decimal e retorne o token NUMBER e, na
variável yylval, o valor do número.
Números inteiros em hexadecimal e retorne o token NUMBER e, na
variável yylval, o valor do número.
Labels e retorne em yytext a string com o label e o token LABEL.
A especificação de um registrador ($1, por exemplo) e retorne o
token REGISTER e, na variável yylval, o número do registrador
Os caracteres: “,” (COMMA), “(” (OPEN_PARENTHESIS), “)”
(CLOSE_PARENTHESIS)
O fim de uma linha e retorne END_OF_LINE