CES-41 COMPILADORES
Aulas Práticas - 2013
Capítulo I
A Ferramenta Flex
Flex é um gerador de analisadores léxicos:

Tem como entrada expressões regulares e implementa um
autômato finito reconhecedor e classificador dos átomos dos
programas a serem compilados

Flex é uma versão, para o sistema DOS, do mais conhecido
gerador de analisadores léxicos: o Lex do sistema Unix

O analisador gerado é um programa escrito em C

Flex, Yacc, compilador Gcc e outros softwares estão
reunidos numa pasta denominada MingW, a ser usada nas
aulas práticas de CES-41
Programa 1.1: Saída de dados

Num editor de texto (Bloco de Notas, Borland C++, ou
outros), criar o seguinte arquivo extensão .l (saida.l, por
exemplo):
%%
%%
main () {
printf ("hello friends!");
}

Guardar esse arquivo no diretório
e:\alunos\ces-41\mingw\bin

No prompt do DOS, entrar no diretório
e:\alunos\ces-41\mingw\bin

Executar os seguintes comandos:
flex saida.l
gcc lex.yy.c -lfl
a

Executar:

Abrir o arquivo ttt (No DOS: more ttt)
a > ttt

Por curiosidade, abrir o arquivo lex.yy.c e procurar no final a
função main que aparece no arquivo saida.l

Flex gera uma função fundamental chamada yylex, mas não é
chamada pela main neste programa
Programa 1.2: Entrada de dados

Criar em e:\alunos\ces-41\mingw\bin o arquivo entra.l
com o seguinte programa:
%%
%%
main () {
int i, n;
printf ("Digite o numero de repeticoes: ");
scanf ("%d", &n);
for (i = 1; i <= n; i++)
printf ("\nhello friends!");
}

Executar os seguintes comandos:
flex entra.l
gcc lex.yy.c -lfl
a

Criar um arquivo entra.dat, colocando nele o número 10

Executar os comandos:
a < entra.dat
a < entra.dat > ttt

Abrir o arquivo ttt
(No DOS: more ttt)

Procurar novamente a função main no arquivo lex.yy.c

Novamente main não chama yylex
Esquema de produção de um programa executável
usando Flex:
Programa 1.3: Reconhecimento de while

Criar um arquivo (while.l) com o seguinte programa:
%{
yytext é uma
#define
WHILE
1
variável string,
%}
Agora main
%%
global, do arquivo
while
{return WHILE;} chama yylex
lex.yy.c
%%
main () {
int i;
while (i = yylex ())
printf ("\nstring: %6s; tipo: %d; \n", yytext, i);
}
Criar um arquivo de dados (while.dat)
com o seguinte conteúdo:
fabio 111 while else
whil whiles if BHwhile22
Executar:
flex while.l
gcc lex.yy.c –lfl
a < while.dat
%{
#define
WHILE
1
%}
%%
while
{return WHILE;}
%%
main () {
int i;
while (i = yylex ())
printf ("\nstring: %6s;
}
Arquivo de dados:
fabio 111 while
whil whiles if
BHwhile22
else
tipo: %d; \n", yytext, i);
Funcionamento do yylex:
Resultados:
a < while.dat
fabio 111
string: while; tipo: 1;
else whil
string: while; tipo: 1;
s if BH
string: while; tipo: 1;
22
yylex lê caractere por caractere da
entrada e o coloca em yytext
Quando não reconhece uma
sequência guardada em yytext, ele
escreve seu conteúdo e a esvazia
Escreve tudo o que não é
reconhecido, inclusive espaços em
branco
%{
#define
WHILE
1
%}
%%
while
{return WHILE;}
%%
main () {
int i;
while (i = yylex ())
printf ("\nstring: %6s;
}
Arquivo de dados:
fabio 111 while
whil whiles if
BHwhile22
else
tipo: %d; \n", yytext, i);
Funcionamento do yylex:
Resultados:
a < while.dat
fabio 111
string: while; tipo: 1;
else whil
string: while; tipo: 1;
s if BH
string: while; tipo: 1;
22
Continua percorrendo a entrada,
tentando reconhecer algo
Neste programa, só while é
reconhecido
Ao reconhecer algo, executa a ação
em frente
{return WHILE;}
%{
#define
WHILE
1
%}
%%
while
{return WHILE;}
%%
main () {
int i;
while (i = yylex ())
printf ("\nstring: %6s;
}
Arquivo de dados:
fabio 111 while
whil whiles if
BHwhile22
else
tipo: %d; \n", yytext, i);
Funcionamento do yylex:
Resultados:
a < while.dat
fabio 111
string: while; tipo: 1;
else whil
string: while; tipo: 1;
s if BH
string: while; tipo: 1;
22
Retorna zero ao encontrar fim de
arquivo
Tenta reconhecer a maior string
possível
Sempre esvazia yytext no início de sua
execução
Estrutura de um programa em Flex:

Um programa em Flex é dividido em três partes:
Declarações
%%
Regras de tradução
%%
Rotinas auxiliares

As strings “%%” são os separadores dessas partes

Seu uso é obrigatório, mesmo que o programa não tenha
alguma(s) dessa(s) parte(s)
Regras de tradução:

Constituem-se na parte principal de um programa em Flex

São comandos da forma:
p1
{ação1}
p2
{ação2}


pn
{açãon}

Cada pi é uma expressão regular e cada açãoi é um
fragmento de programa em C

Caso um conjunto máximo de caracteres da entrada se
enquadre em uma expressão regular pi, a açãoi é executada
Declarações:
Nelas estão inclusas:

Declarações de variáveis, tipos e diretivas de préprocessamento (define’s, include’s, etc), tudo escrito em C,
delimitado por %{ e %}

Definições regulares componentes das expressões
regulares que aparecem nas regras de tradução


Essas definições ficam fora dos %{ e %}
Os arquivos incluídos devem conter somente declarações
Rotinas auxiliares:

São as definições das funções em C, referenciadas nas ações
das regras de tradução

Podem trazer inclusão de arquivos com extensão .c

A função main pode aí aparecer
Programa 1.4: Reconhecimento de várias palavras
Resultados:
Criar um arquivo com o seguinte programa:
Executar
a < reserv.dat
fabio 111
%{
string: while; tipo: 1;
#define
WHILE
1
#define
IF
2
string:
else; tipo: 5;
#define
IF11
3
wh whi whil
#define
FOR
4
string: while; tipo: 1;
s then
#define
ELSE
5
string:
if; tipo: 2;
%}
%%
string:
for; tipo: 4;
while
{return WHILE;}
BH
if
{return IF;}
string:
if; tipo: 2;
if11
{return IF11;}
for
{return FOR;}
string:
else; tipo: 5;
22
else
{return ELSE;}
string:
if; tipo: 2;
%%
1
main () {
string:
if11; tipo: 3;
int i;
while (i = yylex ())
printf ("\nstring: %6s; tipo: %d; \n", yytext, i);
}
Arquivo de dados: fabio 111 while else wh whi whil
whiles then if
for BHifelse22 if1 if11
Programa 1.4: Reconhecimento de várias palavras
Resultados:
a < reserv.dat
string:
if; tipo: 2;
%{
#define
WHILE
1
string:
if; tipo: 2;
#define
IF
2
1
#define
IF11
3
string:
if11; tipo: 3;
#define
FOR
4
string:
if; tipo: 2;
#define
ELSE
5
%}
12
%%
while
{return WHILE;}
Para if1 e if12, yylex lê 1{branco} e 12
if
{return IF;}
if11
{return IF11;}
Como if1{branco} e if12 não são
for
{return FOR;}
reconhecidos, ele devolve 1{branco} e 12
else
{return ELSE;}
%%
para o buffer de entrada
main () {
Reconhece o if e retorna
int i;
while (i = yylex ())
printf ("\nstring: %6s; tipo: %d; \n", yytext, i);
}
Arquivo de dados: if
if1
if11
if12
Programa 1.5: Tratamento de espaços em branco
Expressão regular reconhecedora
de espaço de um ou mais brancos,
tabulações, new-lines ou carriagereturns
%{
#define
WHILE
1
#define
IF
2
#define
IF11
3
#define
FOR
4
#define
ELSE
5
%}
[abc] significa: um caractere que
%%
pode ser a, b ou c
[ \t\n\r]+ {printf ("\n");}
while
{return WHILE;}
[abc]+ significa: um ou mais
if
{return IF;}
if11
{return IF11;}
caracteres a, b ou c
for
{return FOR;}
else
{return ELSE;}
[abc]* significa: zero ou mais
%%
caracteres a, b ou c
main () {
int i;
while (i = yylex ())
printf ("\nstring: %6s; tipo: %d; \n", yytext, i);
}
Arquivo de dados: fabio 111 while else wh whi
whil whiles then if
for BHifelse22 if1 if11
Resultados:
fabio
111
Arquivo de dados:
fabio 111 while else wh
whi whil whiles then if
for BHifelse22 if1 if11
Reconhecimento da regra
[ \t\n\r]+
{printf ("\n");}
Imprime new-line e não retorna
Esvazia yytext ao iniciar novo
processo de reconhecimento
string:
while; tipo: 1;
string:
else; tipo: 5;
wh
whi
whil
string:
s
then
while; tipo: 1;
string:
if; tipo: 2;
string:
for; tipo: 4;
BH
string:
if; tipo: 2;
string:
22
else; tipo: 5;
string:
1
if; tipo: 2;
string:
if11; tipo: 3;
Programa 1.6: Identificadores, números e operadores
%{
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
%}
delim
ws
digito
letra
num
id
%%
DOLAR
LT
LE
EQ
NE
GT
GE
IF
THEN
ELSE
ID
NUM
0
1
2
3
4
5
6
7
8
9
10
11
O conteúdo do que está
entre os colchetes [ e ]
representa um só caractere
Entre as chaves { e }
coloca-se o nome de uma
definição regular
Entre os parêntesis ( e )
coloca-se uma subexpressão regular
[ \t\n\r]
{delim}+
[0-9]
[A-Za-z]
{digito}+
{letra}({letra}|{digito})*
Definições
regulares
{ws}
{ ;}
if
{return IF;}
then
{return THEN;}
else
{return ELSE;}
{id}
{return ID;}
{num}
{return NUM;}
"<"
{return LT;}
"<="
{return LE;}
"="
{return EQ;}
"<>"
{return NE;}
">"
{return GT;}
">="
{return GE;}
"$"
{return DOLAR;}
%%
main () {
int i;
while (i = yylex ())
printf ("\nstring: %6s;
}
É preciso usar chaves:
{id}, {num} e {ws}
Por que?
A função main é igual à dos
programas anteriores, exceto
por um ‘\n’
tipo: %d;", yytext, i);
Executar com o seguinte arquivo
de entrada:
{ws}
{ ;}
then if xxx 123 < <>
if
{return IF;}
<= >= > = else $
then
{return THEN;}
else
{return ELSE;}
Resultados:
{id}
{return ID;}
{num}
{return NUM;}
string:
then;
tipo:
8;
Por
curiosidade,
colocar
a
regra
"<"
{return LT;}
string:
if; tipo: 7;
do
{id}
antes
da
regra
do if
"<="
{return LE;}
string:
xxx; tipo: 10;
string:
123; tipo: 11;
"="
{return EQ;}
string:
<; tipo: 1;
"<>"
{return NE;}
Caso
uma
string
seja
string:
<>; tipo: 4;
">"
{return GT;}
reconhecida
por 2<=;
regras,
a regra
string:
tipo:
2;
">="
{return GE;}
escolhida
aparece
string:é a que>=;
tipo: 6;
"$"
{return DOLAR;}
primeiro
na lista de>;regras
string:
tipo: 5;
%%
string:
=; tipo: 3;
main () {
string:
else; tipo: 9;
int i;
while (i = yylex ())
printf ("\nstring: %6s; tipo: %d;", yytext, i);
}
then if xxx 123
<= >= > = else
<
$
<>
{ws}
{ ;}
Resultados:
if
{return IF;}
then
{return THEN;}
string:
then; tipo: 8;
else
{return ELSE;}
string:
if; tipo: 7;
{id}
{return ID;}
string:
xxx; tipo: 10;
{num}
{return NUM;}
string:
123; tipo: 11;
"<"
{return LT;}
string:
<; tipo: 1;
string:
<>; tipo: 4;
"<="
{return LE;}
string:
<=; tipo: 2;
"="
{return EQ;}
string:
>=; tipo: 6;
"<>"
{return NE;}
string:
>; tipo: 5;
">"
{return GT;}
string:
=; tipo: 3;
">="
{return GE;}
string:
else; tipo: 9;
"$"
{return DOLAR;}
%%
Este é um exemplo de formação de
main () {
átomos de uma mini-linguagem
int i;
yylex retorna o tipo do átomo
while (i = yylex ())
printf ("\nstring: %6s; tipo: %d;", yytext, i);
}
Programa 1.7: Autômato
Reconhecimento de strings de
%{
#define
ACEITA
1
0’s e 1’s contendo um número
#define
OUTRA
2
ímpar de 1’s
%}
delim
[ \t\n\r]
ws
{delim}+
[^abc] : um caractere diferente de a,
aceita
0*1(0*10*1)*0*
string
[^ \t\n\r]+
bec
%%
{ws}
{ ;}
{aceita}
{return ACEITA;} Executar com o seguinte arquivo de
{string}
{return OUTRA;} entrada:
%%
main () {
111 001 00101 11 00
int i;
100100 100100001 21
while (i = yylex ())
000001 00110001 01110001100
switch (i) {
case ACEITA:
printf ("%-20s: Aceita\n", yytext);
break;
case OUTRA:
printf ("%-20s: Rejeitada\n", yytext);
break;
}
}

Exercício 1.1: Escrever um programa em Flex reconhecedor
de strings sobre o alfabeto {0, 1} que possuam pelo menos
dois dígitos 0’s seguidos

Exercício 1.2: Escrever um programa em Flex reconhecedor
de strings sobre o alfabeto {0, 1, 2}, nas quais cada dígito 2 é
imediatamente seguido por dois 0’s e cada dígito 1 é
imediatamente seguido por um dígito 0 ou pelo par de dígitos
20

Exercício 1.3: Escrever um programa em Flex reconhecedor
de strings sobre o alfabeto {0, 1}, nas quais o número de
dígitos 0 é par ou o número de dígitos 1 é ímpar

Exercício 1.4: Escrever um programa em Flex reconhecedor
de strings sobre o alfabeto {0, 1}, nas quais a string 101 não é
uma sub-string

Exercício 1.5: Escrever um programa em Flex reconhecedor
de strings sobre o alfabeto {0, 1}, nas quais o número de
dígitos 0 é par e o número de dígitos 1 é ímpar
Programa 1.8: Atributos para os átomos além do tipo
Sejam os seguintes define’s para tipos de átomos:
%{
#define
#define
#define
#define
#define
#define
%}
ELSE
IF
WHILE
ID
CTINT
OPREL
1
2
3
4
5
6
O tipo dos átomos ELSE, IF e
WHILE já os define completamente
Os átomos de tipos ID, CTINT e
OPREL necessitam de mais
informações para ficarem
completamente definidos:
ID: sua string
CTINT: seu valor numérico
OPREL: qual o operador relacional
Solução: atributos para os átomos
%{
#include
<string.h>
#define
ELSE
#define
IF
#define
WHILE
#define
ID
#define
CTINT
#define
OPREL
#define
LT
#define
LE
#define
GT
#define
GE
#define
EQ
#define
NE
union {
char string[50];
int atr, valor;
char carac;
} yylval;
%}
Atributos:
1
2
3
4
5
6
1
2
3
4
5
6
ID: string
CTINT: valor numérico
OPREL: operador
Define’s para os
atributos dos átomos
de tipo OPREL
yylval: variável global com vários
campos:
Um campo para cada tipo de
átomo
delim
ws
digito
letra
ctint
id
%%
{ws}
else
if
while
{id}
{ctint}
"<"
"<="
">"
">="
"=="
"!="
%%
[ \t\n\r]
{delim}+
[0-9]
[A-Za-z]
{digito}+
{letra}({letra}|{digito})*
{ ;}
{return ELSE;}
{return IF;}
{return WHILE;}
{strcpy (yylval.string, yytext); return ID;}
{yylval.valor = atoi(yytext); return CTINT;}
{yylval.atr = LT; return OPREL;}
{yylval.atr = LE; return OPREL;}
{yylval.atr = GT; return OPREL;}
{yylval.atr = GE; return OPREL;}
{yylval.atr = EQ; return OPREL;}
{yylval.atr = NE; return OPREL;}
Alguns átomos formados por yylex são compostos pelo
valor retornado e pelo valor de algum campo de yylval
main () {
int i;
printf ("\n
texto |
tipo
| atributo \n");
printf ("--------------------------------\n");
while (i = yylex ()) {
printf ("%10s|%10d|", yytext, i);
switch (i) {
case ID:
printf ("%10s", yylval.string); break;
case CTINT:
printf ("%10d", yylval.valor); break;
case OPREL:
printf ("%10d", yylval.atr); break;
}
printf ("\n");
}
}
Executar com o seguinte arquivo de
Acrescentar pelo meio
entrada:
da entrada:
while
<
<=
if
>
else
xxx
123
>=
==
!=
(&%
Programa 1.9: Tratamento de caracteres estranhos

.

Acrescentar a seguinte regra no final das regras de tradução:
{yylval.carac = yytext[0]; return INVAL;}
Acrescentar no meio dos define’s a declaração:
#define INVAL 7

Acrescentar na função main ( ):
Alterações no
Programa 1.8
case INVAL: printf ("%10c", yylval.carac); break;
O ponto ‘.’ é um meta-símbolo que significa
qualquer caractere, exceto o new-line
Exercício 1.6: Acrescentar ao programa anterior regras para
reconhecimento de constantes reais, caracteres e strings

Constante real: um ou mais dígitos seguidos de um ponto
decimal, seguido de zero ou mais dígitos

A constante pode ainda estar na notação exponencial:


Acrescenta-se opcionalmente o seguinte: a letra E
maiúscula ou minúscula, seguida opcionalmente de + ou -,
seguidos de um ou mais dígitos
Exemplos: 12.
3.57
0.23
3.2E19
7.5e-45
Exercício 1.6: Acrescentar ao programa anterior regras para
reconhecimento de constantes reais, caracteres e strings

Caractere: qualquer caractere entre apóstrofos; cuidado com
os caracteres iniciados pela barra ‘\’; cuidado quando o
caractere for o apóstrofo


Exemplos: ‘w’
‘\n’
‘\‘’
Strings: conjunto de caracteres entre aspas; mesmos cuidados;
cuidado quando o caractere for aspas

Exemplo: “w\n123\g\“”
Executar o programa com o seguinte arquivo:
while if else xxx 123 12.53 13. 31.5E-12 1.5e11
19.E+27 ';' '\'' '\n' 's' "ab \\ \" \n'z"
'"'
"'"
Dicas:

Definir novos tipos de átomos:


Constante real, constante caractere e constante string
Novo campo para yylval:
union {
char string[50];
int atr, valor;
float valreal;
char carac;
} yylval;

Caractere e string podem usar o campo string do yylval

Criar definições regulares para constante real, constante
caractere e constante string

Constante caractere:
carac1
ctcarac

Constante string:
carac2
string

\\.|[^\\']
'{carac1}'
\\.|[^\\\"]
\"{carac2}*\"
Qualquer caractere precedido pela
‘\’ ou qualquer caractere que não
seja ‘\’ ou apóstrofo isolados
Qualquer caractere precedido pela
‘\’ ou qualquer caractere que não
seja ‘\’ ou aspas isolados
Criar novas regras de tradução para constante real, ctcarac
e string
Solução: no arquivo
RealCharString.l

Aumentar o switch da função main
Página do Professor
Exercício 1.7: Acrescentar ao programa anterior regras para
reconhecimento e descarte de comentários

Comentários: tudo entre /* e */;

Não é para criar um átomo do tipo comentário

Eles devem ser lidos e descartados, antes do retorno da
função yylex
Exercício 1.7: Acrescentar ao programa anterior regras para
reconhecimento e descarte de comentários

Acrescentar uma linha com o protótipo
void comentario (void);
entre os delimitadores %{ e %}

Acrescentar a seguinte regra de tradução:
"/*"

{comentario ();}
Acrescentar e programar a seguinte rotina auxiliar:
void comentario () { ----- }
Idéia: usar o seguinte autômato depois de detectado o par /*:
Executar o programa com o seguinte arquivo:
while
if
*/1.5e11/*
/* else
19.E+27*/
xxx */ 123
/*12.53
13. 31.5E-12
';' '\'' '\n' 's' "ab \\ \" \n'z"
void comentario () {
char c; int estado;
estado = 1;
while (estado != 3) {
switch (estado) {
case 1:
c = input ();
if (c == EOF) estado = 3;
else if (c == '*') estado = 2;
break;
case 2:
- - - - }
}
}