EstudodeCaso_TeoriadaComputacao

Prévia do material em texto

LINGUAGENS 
FORMAIS E 
AUTÔMATOS
OBJETIVOS DE APRENDIZAGEM
 > Conceituar as fases de análise léxica e sintática em processadores de lin-
guagens.
 > Apresentar as ferramentas Lex e Yacc.
 > Demonstrar a construção de um processador de linguagem utilizando Lex e Yacc.
Introdução
Uma aplicação da teoria de linguagens formais é o reconhecimento de linguagens, 
o que envolve os processos de análise léxica e análise sintática. Nesse âmbito, 
duas ferramentas são bastante usadas, Flex e Bison, que são versões atualizadas 
de duas ferramentas clássicas, Lex e Yacc, aplicadas respectivamente para gerar 
analisadores léxicos e sintáticos. 
Neste capítulo, você vai compreender os conceitos de análise léxica e análise 
sintática e seu importante papel no processo de reconhecimento e processa-
mento de linguagens. Você estudará ferramentas dedicadas a essas análises e 
acompanhará um exemplo de sua aplicação para construir um interpretador para 
uma linguagem de programação simplificada.
Processos de análise léxica e sintática 
No contexto de linguagens de programação, um tradutor é um sistema, se-
gundo Price e Toscani (2001), que aceita como entrada um programa escrito 
em certa linguagem de programação (linguagem-fonte) e que produz como 
resultado um programa equivalente em outra linguagem (linguagem-objeto). 
A esse programa damos o nome de compilador.
Estudo de caso
Rafael Leal Martins
O processo de tradução feito por um compilador é composto de várias 
fases, conforme ilustrado na Figura 1. 
Figura 1. As fases de um compilador.
Fonte: Aho et al. (2007, p. 4). 
Segundo (AHO et al., 2007, p. 3): 
A parte de análise subdivide o programa-fonte em partes constituintes e impõe 
uma estrutura gramatical sobre elas. Depois, usa essa estrutura para criar uma 
representação intermediária do programa-fonte. Se a parte de análise detectar que 
o programa-fonte está sintaticamente mal formado ou semanticamente incorreto, 
então ele precisa oferecer mensagens esclarecedoras, de modo que o usuário 
possa tomar a ação corretiva. A parte de análise também coleta informações sobre 
o programa-fonte e as armazena em uma estrutura de dados chamada tabela de 
símbolos, que é passada adiante junto com a representação intermediária para a 
parte de síntese. A parte de síntese constrói o programa-objeto desejado a partir 
da representação intermediária e das informações na tabela de símbolos.
Estudo de caso2
O processo de reconhecimento de uma linguagem é chamado de aná-
lise. A análise divide a entrada em símbolos básicos (tokens) e impõe uma 
estrutura gramatical sobre eles (AHO et al., 2007). Como a primeira fase de 
um reconhecedor de linguagem, a principal tarefa da análise léxica é ler os 
caracteres de entrada do programa de origem, agrupá-los em lexemas e 
produzir como saída uma sequência de tokens para cada lexema na entrada. 
O fluxo de tokens é enviado para análise sintática. 
As análises léxica e sintática são complementares, o que muitas vezes 
nos permite simplificar pelo menos uma dessas tarefas. Numa linguagem 
de programação, por exemplo, comentários são irrelevantes na análise do 
código-fonte. O analisador léxico pode lidar com comentários e outras en-
tradas irrelevantes removendo-as, simplificando o trabalho realizado pelo 
analisador sintático. Quando estamos projetando uma nova linguagem, se-
parar preocupações léxicas e sintáticas pode levar a um design de linguagem 
geral mais limpo.
Análise léxica
Essa primeira fase de um compilador, a análise léxica, também é chamada de 
scanning. O analisador léxico (ou scanner) faz a leitura do fluxo de caracteres 
que compõem o programa-fonte e os agrupa de acordo com seu significado 
dentro do programa. As sequências de caracteres reconhecidos pelo ana-
lisador léxico são chamadas de lexemas. Para cada lexema reconhecido, o 
analisador léxico produz como saída um token no formato , que é passado para a próxima fase, a análise sintática. O 
nome-token é um símbolo abstrato que identifica o tipo de símbolo dentro 
do programa, e será usado posteriormente durante a análise sintática. O 
segundo componente, valor-atributo, aponta para uma entrada em uma 
tabela de símbolos referente a esse token. A informação da entrada da tabela 
de símbolos é necessária para a fase de análise semântica e posteriormente 
para a geração de código. 
Exemplo
Considere uma típica operação de atribuição em uma linguagem de 
programação:
X = X + valor * 50
Um analisador léxico tipicamente poderia fazer os seguintes 
reconhecimentos:
Estudo de caso 3
1. X seria reconhecido como um identificador (nome de variável ou 
função) e seria mapeado para o token , em que ID repre-
sentaria o tipo do símbolo encontrado (ID: identificador) e 1 
seria a posição desse token na tabela de símbolos. O identificador é 
armazenado na tabela de símbolos, pois representa uma variável, uma 
posição de memória específica que provavelmente será referenciada 
novamente no código.
2. O operador = seria reconhecido como um token , para indicar 
que esse caractere representa uma operação de atribuição a ser feita. 
Esse token não precisaria de um atributo, pois não são necessárias 
mais informações além da operação a ser realizada em si.
3. Novamente, o lexema X seria reconhecido como um identificador, 
mas como ele já estaria armazenado na tabela de símbolos, o token 
retornado seria novamente , pois está referenciando a mesma 
variável.
4. O caractere + seria reconhecido como um token .
5. A palavra valor seria mapeada para , pois trata-se de uma 
nova variável reconhecida. Logo, ela deve ser armazenada como uma 
nova entrada na tabela de símbolos. 
6. O caractere * seria reconhecido como .
7. A sequência 50 seria mapeada para um token , ou mesmo para um 
token ,a fim de representar uma constante numérica 
nessa expressão.
Os espaços entre os elementos da sentença seriam descartados pelo 
analisador léxico.
Análise sintática
A segunda fase do compilador é a análise sintática. O analisador sintático, ou 
parser, utiliza os tokens reconhecidos pelo analisador léxico para criar uma 
representação tipo árvore, que mostra a estrutura gramatical da sequência 
de tokens. Nessa árvore, cada nó interior representa uma operação, e os filhos 
do nó representam os argumentos da operação. A essa árvore damos o nome 
de árvore sintática. A árvore sintática é construída a partir de uma gramática 
que define a ordem dos tokens na formação das sentenças da linguagem. Se 
for possível criar a árvore sintática com a sequência de tokens reconhecidos 
pelo analisador léxico, a entrada é aceita, ou seja, o programa-fonte está de 
acordo com a estrutura da linguagem.
Estudo de caso4
Exemplo
Considere a seguinte gramática:
CMD → EXPRESSAO
EXPRESSAO → EXPRESSAO TERMO
EXPRESSAO → TERMO
TERMO → TERMO FATOR
TERMO → FATOR
FATOR → | 
Para a sentença X = X + valor * 50, o analisador léxico reconheceria a 
sequência de tokens: , , , , , 
e . O trabalho do analisador sintático é tentar criar uma árvore sintática 
para essa sequência de tokens. 
De acordo com a gramática recém-apresentada, o analisador sintático poderia 
montar a árvore sintática mostrada na Figura 2. Isso significa que a sequência 
de tokens é aceita pela análise sintática, ou seja, X = X + valor * 50 é uma 
instrução válida.
Figura 2. Árvore sintática para a instrução X = X + valor * 50.
Vejamos agora a sentença X + 10 = Y. Embora o analisador léxico conse-
guisse reconhecer os tokens , , , e , 
essa sequência não é capaz de produzir uma árvore sintática a partir da 
gramática proposta, o que torna essa instrução inválida de acordo com a 
sintaxe da linguagem. 
Estudo de caso 5
E as outras fases do compilador? O analisador semântico usa a árvore 
sintática e as informações na tabela de símbolos para verificar a 
consistênciado programa-fonte com a definição da linguagem. Uma parte 
importante da análise semântica é a verificação de tipos de dados, em que o 
compilador verifica se cada operador possui operandos compatíveis. Como 
muitas linguagens de programação exigem que um índice de um array seja um 
número inteiro, o compilador precisa informar um erro de tipo se um número 
de ponto flutuante for usado para indexar um array. Outra verificação seria, 
numa divisão, verificar se o denominador tem valor igual a zero e alertar o 
programador, a fim de evitar um erro de execução. 
Depois da análise do programa-fonte, muitos compiladores geram uma 
representação intermediária que pode ser facilmente produzida e traduzida 
para a máquina-alvo. A fase de otimização aplica certas transformações no 
código intermediário, visando a produção de um melhor código-objeto. Nesse 
caso, segundo Aho et al. (2007), melhor normalmente significa mais rápido, 
menor ou que consume menos energia. Na fase de geração de código, os códigos 
intermediários são traduzidos em sequências de instruções de máquina que 
realizam a mesma tarefa proposta nas instruções da linguagem-fonte.
Flex e Yacc: ferramentas para gerar 
analisadores léxicos e sintáticos
Na década de 1950, os primeiros compiladores usavam técnicas totalmente 
ad hoc para analisar a sintaxe do código-fonte dos programas que estavam 
compilando. Durante a década de 1960, o campo recebeu muita atenção 
acadêmica, e no início da década de 1970 a análise sintática era um campo 
bem estudado (LEVINE, 2009).
Um dos principais conceitos foi dividir o trabalho em duas partes: análise 
léxica (lexing ou scanning) e análise sintática (parsing). Relembrando: a aná-
lise léxica divide a entrada em pedaços significativos, chamados tokens, e a 
análise sintática verifica como os tokens se relacionam entre si.
Os analisadores léxicos geralmente funcionam procurando padrões de 
caracteres na entrada. Em linguagens de programação típicas, por exemplo, 
uma constante de inteiro é uma sequência de um ou mais dígitos, um iden-
tificador é uma letra seguida por zero ou mais letras ou dígitos e os vários 
operadores são caracteres únicos ou pares de caracteres. Uma maneira 
simples de descrever esses padrões são expressões regulares.
Estudo de caso6
O trabalho do analisador sintático é descobrir a relação entre os tokens 
de entrada. Como já vimos, uma maneira comum de exibir tais relações é 
uma árvore sintática. Para escrever um analisador sintático, precisamos de 
uma maneira de descrever as regras que o analisador usa para transformar 
uma sequência de tokens em uma árvore sintática. Para isso, recorremos a 
uma gramática livre de contexto. Uma forma de descrever uma gramática é 
a forma de Backus-Naur.
Flex e Bison são ferramentas para construir programas que lidam com 
entradas estruturadas. O nome Flex vem da expressão Flexible Lexical Gene-
rator (Gerador Léxico Flexível). Já o nome Bison vem de uma brincadeira com 
o nome da ferramenta Yacc (Yet Another Compiler Compiler, ou Mais Outro 
Compilador de Compilador). Ocorre que o nome Yacc lembra o termo em 
inglês yak (iaque), um parente do bisão (bison, em inglês). Flex e Bison eram 
originalmente ferramentas para construir compiladores, mas se revelaram 
úteis em muitas outras áreas. 
Flex é um gerador de analisadores léxicos e Bison é um gerador de ana-
lisadores sintáticos. Ambos geram código na linguagem de programação C a 
partir de arquivos (ou programas) escritos em certos formatos.
Flex e Bison são substitutos modernos para as ferramentas clássicas 
Lex e Yacc, que foram desenvolvidas na Bell Laboratories na década 
de 1970. O Yacc foi o primeiro dos dois, desenvolvido por Stephen C. Johnson. Já 
o Lex foi projetado por Mike Lesk e Eric Schmidt para trabalhar com o Yacc. Tanto 
Lex quanto Yacc têm sido utilitários Unix padrão desde a sétima edição Unix, 
na década de 1970. O Flex pode ser obtido em https://github.com/westes/flex/
releases, enquanto o Bison está disponível em http://www.gnu.org/software/
bison/. Ambos são ferramentas UNIX/Linux clássicas e também podem ser 
instaladas por meio de repositórios de pacotes de várias distribuições Linux.
Usuários Windows podem usar máquinas virtuais Linux. Também pode-se 
optar por instalar o ambiente Cygwin e compilar os códigos-fonte do Flex e do 
Bison diretamente no Windows. Especificamente para usuários do Windows 10, 
ainda há uma alternativa mais fácil: instalar uma distribuição Linux no Subsistema 
Windows para Linux, que é um módulo do sistema operacional Windows 10 que 
visa disponibilizar um ambiente Linux compatível no sistema da Microsoft sem a 
necessidade de emuladores ou do uso de máquinas virtuais. Na distribuição Linux 
Ubuntu, por exemplo, para instalar o Flex e o Bison basta digitar os seguintes 
comandos no terminal (é necessário confirmar a instalação dos pacotes):
sudo apt update
sudo apt install flex bison
Estudo de caso 7
Um arquivo Bison consiste em um arquivo de texto contendo uma definição 
de uma gramática livre de contexto na forma Backus-Naur. Os tokens são os 
símbolos terminais dessa gramática e são definidos também no arquivo Bison. 
Além de reconhecer os símbolos pelas produções gramaticais, é possível 
definir ações a serem realizadas quando uma produção gramatical é reconhe-
cida com sucesso. Uma ação pode ser usada para gerar código equivalente à 
instrução na linguagem-alvo ou pode ser usada para executar instruções na 
linguagem C relativas à sentença reconhecida pela gramática. Esse processo 
se chama tradução dirigida pela sintaxe, e é muito usado na construção de 
compiladores e interpretadores. No nosso exemplo, a ação será usada para 
realizar a operação aritmética relativa à expressão reconhecida. A ferramenta 
Bison lê o arquivo contendo o arquivo Bison (recomenda-se utilizar a extensão 
.y para arquivos Bison) e gera o código em C para um analisador (e tradutor) 
sintático para a gramática definida. Ele também pode gerar um arquivo-fonte 
com extensão .tab.c, além do arquivo de cabeçalho com extensão .tab.h para 
integração com o analisador léxico gerado pelo Flex posteriormente.
Um arquivo Bison consiste em três seções, separadas por linhas contendo 
apenas %%:
 � a primeira seção contém declarações;
 � a segunda seção é uma lista de padrões e ações;
 � a terceira seção é o código C que é copiado para o analisador léxico 
gerado (geralmente funções relacionadas ao código nas ações). 
Na primeira seção, a seção de declaração, o código pode ser inserido dentro 
de um bloco iniciando com %{ e finalizando com %}. Esse código é inserido 
início do arquivo fonte C gerado. Nessa seção, também definimos quais são 
os tokens usados pela linguagem, bem como sua ordem de precedência e 
associatividade (muito importante no caso de operadores aritméticos).
Na segunda seção, inserimos as produções gramaticais que representam 
a sintaxe da linguagem a ser analisada. Essas produções são escritas em uma 
variação da forma Backus-Naur e têm o seguinte formato:
 : { ação (opcional)} 
onde é uma sequência de um ou mais caracteres que representa um 
símbolo não terminal da gramática da linguagem. é uma sequ-
ência de símbolos, tokens ou não terminais, que são derivados a partir no 
símbolo proposto. A definição da ação é opcional, mas permite definir 
um bloco de instruções em C para realizar a tradução desejada para aquela 
produção gramatical. 
Estudo de caso8
Cada símbolo numa produção gramatical de Bison tem um valor. Assim, 
o valor do símbolo de destino (à esquerda dos dois pontos) é chamado de 
$$ no código de ação, e os valores à direita são numerados $1, $2, e assim 
por diante, até o número de símbolos contidos na produção. Os valores dos 
tokens são o que estava em yylval quando o scanner retorna o token; os 
valores de outros símbolos são definidos em regras no analisador sintático. 
Para uma produção no formato X : Y, o Bison irá automaticamente realizar 
a ação $$ = $1, ou seja, ovalor do símbolo Y ($1) será copiado para o 
símbolo não terminal X ($$). 
A terceira seção do arquivo Bison permite definir uma função principal 
(main) para chamar o analisador sintático por meio de uma chamada à função 
yyparse()gerada pelo Bison. Também podemos definir ações para outras 
funções, como a função yyerror(char *s), que é chamada quando um erro 
sintático é detectado. 
Um programa Flex consiste basicamente em uma lista de expressões 
regulares com instruções sobre o que fazer quando a entrada corresponde a 
qualquer uma delas (LEVINE, 2009). O Flex gera como saída um arquivo-fonte 
escrito na linguagem C contendo o código para um analisador léxico que 
reconhece os tokens para os padrões de lexemas que você definir por meio de 
expressões regulares. Um analisador léxico gerado pelo Flex lê os caracteres de 
entrada (do console ou de um arquivo), tentando estabelecer correspondência 
entre as sequências de caracteres lidos com essas expressões regulares e 
fazendo a ação apropriada quando um padrão for correspondido. 
Grande parte dos programas com analisadores léxicos gerados pelo Flex 
recorre a esse analisador para retornar um fluxo de tokens que são manu-
seados por um analisador sintático (que em grande parte das vezes é gerado 
pelo Bison, mas não necessariamente). Cada vez que o programa precisa de 
um token, ele chama a função yylex(), que lê uma sequência de caracteres 
da entrada e retorna o token. Quando o analisador sintático precisa de outro 
token, ele chama yylex() novamente. O analisador léxico age como uma 
função (ou corrotina), ou seja, cada vez que retorna um token, ele recorda de 
onde estava na leitura da entrada, e na próxima chamada retoma do ponto 
onde parou.
Dentro do analisador léxico, quando o código de ação tem um token pronto, 
ele apenas o devolve como o valor de yylex(). Da próxima vez que o programa 
chamar yylex(), ele retoma a varredura com os próximos caracteres de 
entrada. Por isso, neste nosso exemplo, analisaremos primeiro o programa 
em Bison para depois analisarmos o programa em Flex, mas isso é apenas 
para facilitar a compreensão. Você pode escrevê-los em qualquer ordem.
Estudo de caso 9
Um programa Flex consiste em três seções, separadas por linhas %%:
 � a primeira seção contém declarações e configurações de opções;
 � a segunda seção é uma lista de padrões e ações;
 � a terceira seção é o código C que é copiado para o analisador léxico 
gerado (geralmente funções relacionadas ao código nas ações). 
Na primeira seção, a seção de declaração, o código pode ser inserido 
dentro de um bloco iniciando com %{ e finalizando com %}. Esse código é 
inserido no início do arquivo-fonte C gerado.
Na segunda seção, cada padrão definido deve ser escrito no início de uma 
linha, seguido do código em C para executar uma ação quando o padrão for 
correspondido. O código C pode ser apenas uma instrução ou um bloco de 
instruções entre chaves, { }. Cada padrão deve começar no início de uma 
linha no arquivo, uma vez que o Flex considera qualquer linha que comece 
com espaço branco a ser codificada no código C gerado pelo Flex.
Construção de uma calculadora simples 
usando Bison e Flex
O primeiro programa que escreveremos usando Flex e Bison é uma calculadora 
simples. Primeiro escreveremos um analisador sintático com Bison, depois 
escreveremos um analisador léxico usando Flex e por fim combinaremos os 
dois.
Para simplificar, começaremos reconhecendo apenas inteiros e os quatro 
operadores aritméticos básicos. Para a calculadora proposta, podemos usar 
o seguinte arquivo Bison (chamado calculadora.y):
/* calculadora de expressoes */
%{
#include 
%}
/* declarar tokens */
%token NUMERO
%left SOMA SUB 
Estudo de caso10
%left MUL DIV 
%token EOL
%%
calclist: calclist expressao EOL { printf("= %d\n", $2); } 
| /*Quando nada e definido, assume-se epsilon*/ 
;
expressao: NUMERO /* default $$ = $1 */
| expressao SOMA expressao { $$ = $1 + $3; }
| expressao SUB expressao { $$ = $1 - $3; }
| expressao MUL expressao { $$ = $1 * $3; }
| expressao DIV expressao { $$ = $1 / $3; }
;
%%
main(int argc, char **argv)
{
yyparse();
}
yyerror(char *s)
{
fprintf(stderr, "Erro: %s\n", s);
}
A linha 01 contém um comentário. Tudo que for escrito entre /* e */ 
influenciará a execução do analisador sintático gerado. 
Na linha 02, inicia-se o bloco %{. Dentro dele, quaisquer declarações 
necessárias para o programa final devem ser inseridas, como inclusão de 
bibliotecas e declarações de variáveis globais. O código C digitado aqui será 
transcrito para o código gerado pelo Bison.
Estudo de caso 11
Na linha 03, incluímos a biblioteca C stdio.h para podermos usar a função 
de impressão em tela printf mais à frente. Note que essa linha está contida 
dentro do bloco %{ e }%, que é fechado na linha 04. 
Na linha 06, a declaração %token NUMERO define um token NUMERO para 
representar os valores numéricos inteiros avaliados nas expressões. Repare 
que ainda não estamos definindo quais caracteres formam um token NUMERO. 
Isso é função do analisador léxico, que será construindo posteriormente.
As linhas 07 e 08 definem os tokens dos operadores aritméticos, mas 
observando uma ordem de associatividade e procedência. Na linha 07, a 
declaração %left SOMA SUB define esses dois tokens para representar as 
instruções de soma e subtração, respectivamente, e os define como associa-
tividade à esquerda (left). Logo, uma expressão 5 + 6 – 7 será interpretada 
como ((5+6)+7). Algo similar é feito na linha 08, só que para operadores de 
multiplicação e divisão (tokens MUL e DIV, respectivamente). A precedência 
dos operadores é definida por ordem de declaração: tokens definidos primeiro 
têm menos precedência que tokens definidos em linhas seguintes. Nesse 
caso específico, MUL e DIV têm mais precedência que SOMA e SUB, pois foram 
declarados depois destes. 
Na linha 09, um token EOL é definido para representar o final de uma 
linha digitada. A calculadora proposta permitirá avaliar várias expressões 
aritméticas, uma por linha.
A linha 10 (%%) marca a separação da primeira e da segunda seção do 
arquivo Bison.
Na linha 11, temos a primeira produção gramatical: 
calclist: calclist expressao EOL { printf("= %d\n", $2); } 
Os símbolos não terminais não precisam ser declarados, bastando que 
haja uma produção em que esses símbolos apareçam antes dos dois pontos. 
Em seguida, temos a sequência de símbolos que pode ser derivada a partir 
do não terminal. Nesse caso, calclist pode derivar calclist expressao 
EOL. Numa gramática livre de contexto, um não terminal pode produzir uma 
sequência contendo quaisquer outros símbolos não terminais ou terminais 
(tokens). Também é possível uma derivação vazia (ε — épsilon). Nessa produção 
específica, calclist gera outro calclist, o que permite que a sentença 
derive outra sequência em um comportamento de repetição (loop). Isso foi 
feito aqui para permitir que várias expressões sejam avaliadas, uma a cada 
linha (o fim da linha é marcado pelo token EOL). 
Depois dos símbolos da produção, temos o bloco de código. Essa é a ação 
a ser executada após a avaliação com sucesso dessa produção gramatical. 
Estudo de caso12
Dentro das chaves, você pode inserir código C para realizar alguma operação 
específica. Aqui, após o final de uma linha (token EOL), deseja-se imprimir o 
valor da expressão por meio do comando printf. Note que o valor impresso 
foi a variável $2, que contém o valor armazenado no segundo símbolo dessa 
produção gramatical, no caso o símbolo seria expressao. 
Na linha 12, temos uma segunda produção para calclist. O símbolo | 
(pipe) no início da linha é usado como um “ou” lógico para outras produções. 
Observe que a produção aqui consiste apenas nesse símbolo, isto é, significa 
uma produção ε, usada para finalizar o loop criado pela primeira produção 
de calclist.
Na linha 13, há apenas um ponto e vírgula (;), que marca o fim das produ-
ções para um símbolo não terminal.Nas linhas de 14 a 19, temos as produções gramaticais para o não terminal 
expressão, que pode ser gerado pelo não terminal calclist definido 
anteriormente. 
Não é permitido no Bison mencionar um símbolo não terminal em 
uma produção gramatical sem definir produções para esse símbolo. 
Tampouco é permitido mencionar um token (terminal) sem declará-lo na seção 
anterior. 
A primeira produção expressao: NUMERO define que uma expressão 
pode ser formada por apenas um número. A ação associada é copiar o valor 
do número ($1) para o não terminal expressao que o gerou ($$). Como 
essa é a ação-padrão numa produção assim, nenhum bloco de comandos é 
necessário (automaticamente $$ = $1). 
As demais produções (das linhas de 15 a 18) permitem a construção de 
expressões contendo um número indeterminado de termos com os operado-
res SOMA, SUB, MUL e DIV. Para cada operação aritmética avaliada, tem-se a 
ação de realizar a operação associada em C com os valores armazenados no 
primeiro e segundo operando ($1 e $3, respectivamente, pois $2 refere-se ao 
token do operador, cujo valor específico não é relevante aqui), armazenando 
o resultado no símbolo gerador da produção ($$). A linha 19 marca o fim das 
produções para expressao.
A linha 20 (%%) marca o início da terceira seção, onde define-se a função main 
em C (linha 21) para que ela chame o analisador sintático por meio da chamada 
yyparse() (linha 23). Isso permite que o compilador gere um executável e 
possamos executar a calculadora a partir do próprio console, por exemplo. 
Estudo de caso 13
Uma última definição é feita para a função yyerror(), nas linhas de 
25 a 28. Aqui definimos que, caso haja algum erro sintático, ele deve ser 
impresso na saída-padrão.
Agora que já temos o analisador sintático definido, criaremos um arquivo 
Flex, que chamaremos de calculadora.l (.l é a extensão recomendada para 
arquivos Flex) para gerar o analisador léxico para a calculadora proposta:
/* calculadora.l : reconhece os tokens para a calculadora*/
%{
#include "calculadora.tab.h" /*O nome do arquivo .tab.h deve 
ser o mesmo gerado pelo Bison (calculadora.y)*/
%}
%%
"+" { return SOMA; }
"-" { return SUB; }
"*" { return MUL; }
"/" { return DIV; }
[0-9]+ { yylval = atoi(yytext); return NUMERO; }
\n { return EOL; }
[ \t] { /* ignore whitespace */ }
. { printf("Caractere desconhecido %c\n", *yytext); }
%%
A estrutura de um arquivo Flex é muito similar à de um arquivo Bison. 
Na linha 01, também temos um comentário escrito que funciona da mesma 
forma que em um arquivo Bison. 
Na linha 02, inicia-se o bloco %{. Dentro dele, quaisquer declarações ne-
cessárias para o programa final devem ser inseridas, como a inclusão de 
bibliotecas e declarações de variáveis globais. 
Na linha 3, incluímos um arquivo de cabeçalho .h que o Bison criará para 
nós, que inclui ambas as definições dos tokens e para implementação de uma 
tabela para armazenamento dos tokens reconhecidos pelo analisador léxico da 
calculadora. O bloco de declarações é fechado na linha 4 com os símbolos }%.
Estudo de caso14
A linha 5 marca o início da segunda seção, onde serão feitas as definições 
dos lexemas a serem reconhecidos pela calculadora. A linha 6 reconhece o 
lexema + e reconhece (retorna) um token do tipo SOMA. Para reconhecer 
apenas um caractere ou mesmo uma sequência específica de caracteres, 
como palavras-chave da linguagem (palavras como imprima, leia, início, fim, 
etc.), deve-se colocar o lexema desejado entre aspas duplas. 
Nas linhas de 07, 08 e 09, são definidos os lexemas para os demais ope-
radores, retornando os respectivos tokens.
Os tokens retornados pelo analisador léxico devem ser idênticos 
aos declarados na primeira seção do arquivo Bison. Se o token não 
for definido, um erro ocorrerá e o Flex não conseguirá gerar o código para o 
analisador léxico.
Na linha 10, temos a definição dos lexemas para números inteiros. A ex-
pressão [0-9]+ significa ocorrência de um ou mais dígitos de 0 até 9. A ação 
executada converterá a sequência de caracteres armazenada em yytext 
em um valor inteiro (usando a função em C atoi) e armazenará esse valor na 
variável yylval. Isso permite armazenar o valor do número lido na entrada 
para sua avaliação nas regras do analisador sintático gerado pelo Bison.
A linha 11 reconhece uma quebra de linha (“\n”) retornando um token EOL.
A linha 12 faz o analisador léxico ignorar (descartar) espaços em branco 
e tabulações (“\t”). Note o espaço em branco após [ nessa linha e o bloco 
vazio (apenas com comentário) ao final.
Finalmente, na linha 13 temos a expressão . (ponto), que representa 
qualquer outro caractere não definido nas regras anteriores. Por não fazer 
parte das expressões propostas, a ação será apenas relatar o aparecimento 
de algum caractere desconhecido.
Testando a calculadora
Com os arquivos calculadora.y e calculadora.l prontos, podemos finalmente 
gerar os códigos dos analisadores sintático e léxico, compilá-los usando um 
compilador C e executar a calculadora.
Primeiro precisamos gerar o código do analisador sintático usando o 
comando:
bison -d calculadora.y
Isso gerará dois arquivos: calculadora.tab.h e calculadora.tab.c.
Estudo de caso 15
Em seguida, geraremos o código para o analisador léxico por meio do 
comando:
flex calculadora.l
Isso gerará o arquivo lex.yy.c
Finalmente, compilaremos o código usando o compilador (neste exemplo 
usamos o gcc):
gcc calculadora.tab.c lex.yy.c -lfl
É normal que algumas warnings possam aparecer, sem problemas. 
Por padrão, o gcc gerará o arquivo a.out contendo o executável do código, 
que pode ser executado gerando a saída mostrada na Figura 3. Podemos 
avaliar quantas expressões quisermos, uma em cada linha. Quando quisermos 
finalizar a entrada, digitamos CTRL-D.
Figura 3. Executando a calculadora feita com Flex e Bison.
Neste capítulo, você aprendeu sobre as análises léxica e sintática e sua 
importância para o reconhecimento e tradução de linguagens. É recomendável 
que você estude a documentação completa do Flex e do Bison para poder 
usar recursos ainda mais poderosos dessas ferramentas. 
Referências
AHO, A. V. et al. Compiladores: princípios, técnicas e ferramentas. 2. ed. São Paulo: 
Pearson, 2007. 
LEVINE, J. Flex & Bison. Sebastopol: O’Reilly Media, 2009.
PRICE, A. M. de A.; TOSCANI, S. S. Implementação de linguagens de programação: 
compiladores. 2. ed. Porto Alegre: Sagra Luzzatto, 2001.
Estudo de caso16
Leituras recomendadas
COOPER, K.; TORCZON, L. Construindo compiladores. 2. ed. Rio de Janeiro: Elsevier, 2014.
GRUNE, D. et al. Projeto moderno de compiladores. Rio de Janeiro: Campus, 2001.
LEVINE, J. R.; MASON, T.; BROWN, D. Lex & Yacc: Unix programming tools. Sebastopol: 
O´Reilly, 1995.
MENEZES, P. B. Linguagens formais e autômatos. 3. ed. Porto Alegre: Sagra-Luzzato; 
Instituto de Informática da UFRGS, 2000. (Série Livros Didáticos).
Os links para sites da web fornecidos neste capítulo foram todos 
testados, e seu funcionamento foi comprovado no momento da 
publicação do material. No entanto, a rede é extremamente dinâmica; suas 
páginas estão constantemente mudando de local e conteúdo. Assim, os editores 
declaram não ter qualquer responsabilidade sobre qualidade, precisão ou 
integralidade das informações referidas em tais links.
Estudo de caso 17