CES-41 COMPILADORES
Aulas Práticas - 2015
Capítulo II
A Ferramenta Yacc
Yacc é um gerador de analisadores sintáticos:

Têm como entrada a gramática livre de contexto da
linguagem-fonte do compilador e implementa uma função de
nome yyparse, que responde se o programa analisado tem ou
não erros sintáticos

Yacc (Yet Another Compiler-Compiler) do sistema UNIX
também possui diversas versões para o sistema DOS (o Yacc
do Mingw é uma delas)

O analisador gerado é um programa em Linguagem C
Programa 2.1: Saída de dados

Criar na pasta MinGW/bin um arquivo extensão .y (saida.y,
por exemplo) com o seguinte programa:
%%
prod:{printf ("hello friends!\n");}
;
%%
Colocar pelo menos uma produção
yylex () {
Não pode haver função main
return 0;
Tem de haver função yylex
}

Executar os seguintes comandos:
yacc saida.y
gcc y.tab.c main.c yyerror.c -o saida -lfl
saida
%%
prod:{printf ("hello friends!\n");}
;
%%
yylex () {
return 0;
}

Executar: saida > ppp

Abrir o arquivo ppp (No DOS: more ppp)

Abrir o arquivo main.c (só executa yyparse e retorna)

yyparse é o analisador sintático produzido pelo Yacc

Abrir o arquivo y.tab.c e localizar yylex, prod e o printf
acima
Estrutura de um programa em Yacc:

Tal como em Lex, um programa em Yacc é dividido em três
partes, a saber:
Declarações
%%
Produções da gramática
%%
Rotinas auxiliares
Produções da gramática:

É a parte principal de um programa em Yacc

O programa deve conter pelo menos uma produção

As produções podem vir acompanhadas de ações escritas na
Linguagem C, inseridas em qualquer posição de seu lado
direito
Produções da gramática:

Exemplo: Sejam as produções:
Expr  Expr OPAD Termo | Termo
Termo  ID | CTE

Em Yacc, com ações opcionais:
expr :
|
;
termo:
|
;
expr OPAD {comandos em C} termo
{comandos em C} termo
ID {comandos em C}
CTE {comandos em C}
Produções da gramática:

Ações podem aparecer no lado direito de uma produção
vazia

Exemplo:
yyy
:
|
;
{comandos em C}
xxx {comandos em C} zzz
A primeira produção
de yyy é vazia
Declarações:
Nelas estão inclusas:

Em C, delimitadas por %{ e %}:
Declarações de variáveis, tipos, protótipos, etc.
- Definições de constantes e macros (define’s)
- Inclusão de arquivos sem definição de funções
-

Declarações do Yacc (fora de %{ e %}) usadas para definir
terminais, não-terminais, precedência de operadores, tipos dos
atributos, etc.
Declarações:

Exemplo: para as produções anteriores
expr :
|
;
termo:
|
;
expr OPAD {comandos em C} termo
{comandos em C} termo
ID {comandos em C}
CTE {comandos em C}
os átomos são assim declarados:
%token OPAD
%token ID
%token CTE
Rotinas auxiliares:

São definições de funções em C, referenciadas nas ações
das produções da gramática

Podem trazer a inclusão de arquivos com extensão .c; por
exemplo, o arquivo lex.yy.c, do Flex

Não devem conter a função main, pois essa já vem inclusa no
ambiente da ferramenta

Devem incluir a função yylex; quando usado com Flex, essa
função já vem contida no arquivo lex.yy.c
%%
prod : {printf ("hello friends!\n");}
friends!\n"); return;}
;
%%
yylex () {
0;
return 50;
}

Fazer yylex retornar algo diferente de zero

Colocar um return dentro da ação depois do printf
Retomando o
programa saida.y
%%
prod : {printf ("hello friends!\n");}
;
%%
yylex () {
Explicando os fatos
return 0;
}

O analisador gerado pelo Yacc é bottom-up

Vai detectando lados direitos de produções e reduzindo-os
para seus lados esquerdos

Tudo acaba bem quando se consegue chegar ao símbolo
inicial
%%
prod : {printf ("hello friends!\n");}
;
%%
yylex () {
Explicando os fatos
return 0;
}

A única produção desta gramática (prod) é vazia

Antes de yyparse pedir um átomo para yylex, ele casa a falta
de átomo em suas mãos com seu lado direito

yyparse faz a redução para o lado esquerdo e executa a ação
no final da produção

Chegou ao símbolo inicial
%%
prod : {printf ("hello friends!\n");}
;
%%
yylex () {
Explicando os fatos
return 0;
}

Em seguida, chama yylex que lhe retorna zero

Recebendo zero, ele aceita e retorna

main então se encerra
%%
prod : {printf ("hello friends!\n");}
friends!\n"); return;}
;
%%
yylex () {
Explicando os fatos
return 50;
}

Depois de chegar ao símbolo inicial, yyparse só aceita o
átomo zero

Se yylex lhe retornar algo diferente de zero, ele rejeitará

Com o return dentro da ação, yyparse retorna para main
antes de chamar yylex
Programa 2.2: Entrada de dados

Criar um arquivo extensão .y (entra.y, por exemplo) com o
seguinte programa:
%%
ppp: {int i, n;
printf ("Digite o numero de repeticoes: ");
scanf ("%d", &n);
for (i = 1; i <= n; i++)
printf ("\nhello friends!");
}
;
%%
yylex () {return 0;}

Executar os seguintes comandos:
yacc entra.y
gcc y.tab.c yyerror.c main.c -o entra -lfl
entra

Criar um arquivo entra.dat, colocando nele o número 10

Executar os comandos:
entra < entra.dat
entra < entra.dat > ppp

Abrir o arquivo ppp
Esquema de produção de um programa executável usando
Yacc, sem auxilio do Flex:
Programa 2.3: Reconhecimento de frase

Rodar yacc e gcc para um arquivo recfrase.y com o seguinte
programa:
%%
prod :
;
'C' 'O' 'M' 'P' ' ' '1' '6'
{printf ("Reconheco!\n"); return;}
%%
yylex () {
return getchar ();
}
Executar recfrase com:
COMP
COMP
COMP
COMP
15
16
17
163
O lado direito das produções
tem apenas terminais (tokens)
Um caractere entre apóstrofos é
considerado um token
Programa 2.3: Reconhecimento de frase

Rodar yacc e gcc para um arquivo recfrase.y com o seguinte
programa:
%%
prod :
;
'C' 'O' 'M' 'P' ' ' '1' '6'
{printf ("Reconheco!\n"); return;}
%%
yylex () {
return getchar ();
}
Executar recfrase com:
COMP
COMP
COMP
COMP
15
16
17
163
Executar com arquivo de dados
(recfrase.dat, por exemplo): uma
frase de cada vez
Executar:
recfrase < recfrase.dat > ppp
Programa 2.4: Gramática S → ε | a S b
%token a
Experimente
Tokens
são convertidos
tirar o return;
em
%token b
sem e com
defines
peloarquivo
Yacc de dados
%token dolar
%token erro
%%
SS :
S dolar
{printf ("Fim da analise\n"); return;}
;
S :
yylex () {
| aSb
char x;
;
x = getchar ();
%%
while (x == ' ' || x == '\n' || x == '\t' || x == '\r')
x = getchar ();
printf ("Caractere lido: %c\n", x);
if (x == 'a') return a; if (x == 'b') return b;
if (x == '$') return dolar; return erro;
}
Rodar com
para arquivo
várias cadeias,
de dados
uma
contendo:
por vez:
aabb$ $ aaabbb$ a$ b$ aaabb$ aabbb$ aba$ ba$
Programa 2.4: Gramática S → ε | a S b
%token a
Experimente tirar o return;
%token b
sem e com arquivo de dados
%token dolar
%token erro
%%
SS :
S dolar
{printf ("Fim da analise\n"); return;}
;
S :
yylex () {
Chegando ao símbolo inicial, yyparse
| aSb
char x;
sempre chama yylex, esperando zero
;
x = getchar ();
%%
while (x == ' ' || x == '\n' || x == '\t' || x == '\r')
x = getchar ();
printf ("Caractere lido: %c\n", x);
if (x == 'a') return a; if (x == 'b') return b;
if (x == '$') return dolar; return erro;
}
yylex só retorna quando um caractere é digitado e nunca retorna zero
Com fim de arquivo, yylex retorna erro
Exercício 2.1: Escrever em Yacc, um analisador sintático para a
seguinte gramática geradora da linguagem L abaixo:
L = { (a b)n cn (d d)* | n  1 }
Gramática:
SabAcD
AabAc | ε
DddD |ε
Exercício 2.2: Escrever em Yacc, um analisador sintático para a
seguinte gramática geradora da linguagem L abaixo:
L = { ai bj | j  i  0 }
Gramática:
SAB
AaAb |ε
BbB |ε
Exercício 2.3: Escrever em Yacc, um analisador sintático para a
seguinte gramática geradora de expressões contendo só pares
de parêntesis balanceados e nenhum outro caractere
Exemplos: ( ), ( ( ) ), ( ) ( ), ( ) ( ( ) ( ( ) ) ) ( ( ) )
Gramática:
S  (A) | S(A)
A ε| S
Programa 2.5: Yacc auxiliado por Lex

Programa em Flex no arquivo expr01.l
delim
ws
digit
num
%%
{ws}
{num}
"+"
"-"
"*"
"/"
"("
")"
"$"
.
%%
[ \t\n\r]
{delim}+
[0-9]
{digit}+
{ ;}
{return
{return
{return
{return
{return
{return
{return
{return
{return
CTE;}
OPAD;}
OPAD;}
OPMULT;}
OPMULT;}
ABPAR;}
FPAR;}
DOLAR;}
INVAL;}
yylex retorna tokens
declarados no
programa em Yacc

Programa em Yacc no arquivo expr01.y
%{
#include
#include
%}
%token
%token
%token
%token
%token
%token
%token
%%
<stdio.h>
<stdlib.h>
DOLAR
CTE
OPAD
OPMULT
ABPAR
FPAR
INVAL
Tokens a serem
retornados por
yylex
line :
expr DOLAR
{printf("Fim da analise\n"); return;}
;
expr :
expr OPAD term
|
term
;
term :
term OPMULT fat
|
fat
;
fat :
CTE
|
ABPAR expr FPAR
;
%%
#include "lex.yy.c"
Tokens aparecem
do lado direito das
produções
yylex está em lex.yy.c

Executar os seguintes comandos:
flex expr01.l
yacc expr01.y
gcc y.tab.c main.c yyerror.c -o expr01 -lfl
expr01
(digitar uma expressão correta terminada por ‘$’)
expr01
(digitar uma expressão incorreta terminada por ‘$’)

Usando arquivo de dados de entrada, yylex retorna zero ao
ler fim de arquivo, quando criado pelo Flex

Então, dispensa-se o return da produção line
Esquema de produção de um programa executável usando
Yacc, com auxilio do Flex:
Programa 2.6: Uso de atributos (calculadora simples)

Programa em Flex no arquivo calc01.l
delim
ws
digit
num
%%
{ws}
{num}
"+"
"-"
"*"
"/"
"("
")"
"$"
.
%%
[ \t\n\r]
{delim}+
[0-9]
{digit}+
{ ;}
{yylval
{yylval
{yylval
{yylval
{yylval
{return
{return
{return
{yylval
yylval guarda o atributo de um
token
yylval é declarado pelo Yacc
= atoi(yytext); return CTE;}
= MAIS; return OPAD;}
= MENOS; return OPAD;}
= VEZES; return OPMULT;}
= DIV; return OPMULT;}
ABPAR;}
FPAR;}
DOLAR;}
= yytext[0]; return INVAL;}

Programa em Yacc no arquivo calc01.y
%{
#include
#include
#define
#define
#define
#define
%}
%token
%token
%token
%token
%token
%token
%token
%%
<stdio.h>
<stdlib.h>
MAIS
1
MENOS
2
VEZES
3
DIV
4
DOLAR
CTE
OPAD
OPMULT
ABPAR
FPAR
INVAL
Atributos para os
tokens OPAD e
OPMULT
Por default,
yylval é inteiro
line :
;
expr :
{
expr DOLAR{
printf("valor: %d\n", $1);
}
expr OPAD term
Não-terminais também
têm atributos
switch ($2)
{
case MAIS : $$ = $1 + $3; break;
case MENOS : $$ = $1 - $3; break;
}
}
|
;
term
Numa produção qualquer:
$$ é o atributo do não-terminal do lado
esquerdo
$1, $2, $3 ... são atributos dos 1o, 2o, 3o ...
símbolos do lado direito
term :
{
fat
}
|
;
:
|
;
term OPMULT fat
Rodar o executável para um
arquivo com a expressão
switch ($2)
10 * (5 + 3)$
{
case VEZES: $$ = $1 * $3; break;
case DIV: $$ = $1 / $3; break;
}
O atributo de um terminal é
fornecido por yylex, em yylval
fat
Os atributos dos não-terminais
devem ser calculados nas ações
CTE
ABPAR expr FPAR {$$ = $2;}
%%
#include "lex.yy.c"
Por default, a ação tomada
no final de uma produção é:
$$ = $1;

No Yacc, a análise é bottom-up (por deslocamento e
redução)

Os átomos são obtidos e deslocados para uma pilha
(deslocamento)

Quando no topo da pilha se formar o lado-direito de uma
produção, tem-se uma ocasião para reduzir

O analisador verifica se a redução é válida

Isso será estudado no tópico sobre Análise Bottom-Up
do capítulo sobre Análise Sintática

Em caso positivo, substitui, na pilha, o lado-direito pelo
lado-esquerdo da produção (redução)

Então, a ação no final da produção é executada

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
10*(5+3)$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
10*(5+3)$#
Operação
d
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#C10
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
*(5+3)$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#C10
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
*(5+3)$#
Operação
r: F → C
Ação
$$ = $1

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#F10
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
*(5+3)$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#F10
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
*(5+3)$#
Operação
r: T → F
Ação
$$ = $1

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
*(5+3)$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
*(5+3)$#
Operação
ddd
Por que não reduz segundo E → T ?
A resposta virá no estudo de Análise
Bottom-Up
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(C5
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
+3)$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(C5
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
+3)$#
Operação
r: F → C
Ação
$$ = $1

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(F5
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
+3)$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(F5
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
+3)$#
Operação
r: T → F
Ação
$$ = $1

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(T5
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
+3)$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(T5
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
+3)$#
Operação
r: E → T
Ação
$$ = $1

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(E5
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
+3)$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(E5
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
+3)$#
Operação
dd
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(E5+C3
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
)$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(E5+C3
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
)$#
Operação
r: F → C
Ação
$$ = $1

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(E5+F3
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
)$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(E5+F3
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
)$#
Operação
r: T → F
Ação
$$ = $1

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(E5+T3
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
)$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(E5+T3
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
)$#
Operação
r: E → E+T
Ação
$$ = $1+$3

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(E8
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
)$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(E8
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
)$#
Operação
d
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(E8)
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*(E8)
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
$#
Operação
r: F → (E)
Ação
$$ = $2

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*F8
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T10*F8
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
$#
Operação
r: T → T*F
Ação
$$ = $1*$3

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T80
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#T80
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
$#
Operação
r: E → T
Ação
$$ = $1

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#E80
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
$#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#E80
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
$#
Operação
d
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#E80$
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
#
Operação
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#E80$
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
#
Operação
r: L → E$
Ação
Imprimir $1

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#L
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
Operação
#
Escrito no vídeo: valor 80
Ação

Análise e cálculo da expressão 10 * (5 + 3)$
line :
expr :
term :
fat :
Pilha
#L
expr DOLAR
expr OPAD term | term
term OPMULT fat | fat
CTE | ABPAR expr FPAR
Entrada
#
Operação
aceitar
Escrito no vídeo: valor 80
Ação
Árvore
sintática de
10*(5+3)$
com
atributos:
Programa 2.7: Alteração no tipo dos atributos

Programa em Flex no arquivo calc02.l:
delim
ws
digit
cte
%%
{ws}
{cte}
"+"
"*"
"("
")"
"$"
%%
[ \t\n]
{delim}+
[0-9]
{digit}+(\.{digit}*)?
{ ;}
{yylval
{return
{return
{return
{return
{return
= atof(yytext); return CTE;}
MAIS;}
VEZES;}
Para simplificar:
ABPAR;}
Expressões somente com
FPAR;}
somas e multiplicações
DOLAR;}

Programa em Yacc no arquivo calc02.y
%{
#include
#include
#define
%}
%token
%token
%token
%token
%token
%token
%%
<stdio.h>
<stdlib.h>
YYSTYPE float
DOLAR
CTE
MAIS
VEZES
ABPAR
FPAR
Alteração no tipo
de yylval e dos
atributos dos nãoterminais
line :
expr DOLAR {
printf("valor: %g\n",$1);
return 0;}
;
expr :
expr MAIS term {$$ = $1 + $3;}
|
term
;
term :
term VEZES fat {$$ = $1 * $3;}
|
fat
;
fat :
CTE
|
ABPAR expr FPAR {$$ = $2;}
;
Rodar o executável para um arquivo
%%
com uma expressão tal como
#include "lex.yy.c"
10.5 * (5.2 + 3.3)$
Programa 2.8: Atributos de tipos alternativos

Programa em Flex no arquivo calc03.l
delim
ws
digit
ctint
ctfloat
%%
[ \t\n]
{delim}+
[0-9]
{digit}+
{digit}+\.{digit}*
Programa com
constantes
inteiras e reais
{ws}
{ctint}
{ ;}
{yylval.valint = atoi(yytext);
return CTINT;}
{ctfloat} {yylval.valfloat = atof(yytext);
return CTFLOAT;}
"+"
{yylval.atr = MAIS; return OPAD;}
"-"
{yylval.atr = MENOS; return OPAD;}
"*"
{yylval.atr = VEZES; return OPMULT;}
"/"
{yylval.atr = DIV; return OPMULT;}
"("
{return ABPAR;}
")"
{return FPAR;}
"$"
{return DOLAR;} yylval não é mais declarado
no programa Flex
%%
Deve ser uma union com os
Agora yylval está sendo usado
campos:
como apresentado no capítulo
sobre Flex
valint, valfloat e atr

Programa em Yacc no arquivo calc03.y
%{
#include <stdio.h>
#include <stdlib.h>
Os campos da
union podem ser
#define MAIS
1
struct’s ou até
#define MENOS 2
outras union’s
#define VEZES 3
#define DIV
4
%}
%union {
int valint, atr; Declaração da estrutura e dos campos
de yylval e de outras variáveis de
float valfloat;
mesmo tipo, usadas na função yyparse
}
%type
%token
%token
%token
%token
%token
%token
%token
%%
<valfloat>
<valint>
<valfloat>
<atr>
<atr>
expr term
DOLAR
CTINT
CTFLOAT
OPAD
OPMULT
ABPAR
FPAR
fat
%type: para os não-terminais
%token: para os terminais
Especificação
dos atributos dos
tokens e dos nãoterminais
line :
;
expr :
{
Aqui, $1 corresponde ao campo
valfloat de alguma variável de yyparse
expr DOLAR {
printf("valor: %g\n",$1);
}
expr OPAD term
Mudança no tipo do valor
a ser escrito
switch ($2) {
case MAIS : $$ = $1 + $3; break;
case MENOS : $$ = $1 - $3; break;
}
}
|
;
Aqui:
term
$1, $3 e $$ correspondem ao campo
valfloat
$2 corresponde ao campo atr
term :
{
term OPMULT fat
switch ($2) {
case VEZES: $$ = $1 * $3; break;
case DIV: $$ = $1 / $3; break;
}
fat
}
|
;
:
|
|
;
fat
Fator de conversão
CTINT
{$$ = (float)$1;}
CTFLOAT
ABPAR expr FPAR {$$ = $2;}
%%
#include "lex.yy.c"
Rodar o executável para um arquivo
com uma expressão tal como
10.5 * (5 + 3.3)$
Programa 2.9: Ações no início e meio das produções
%{
Arquivo acaomeio.y
#include <stdio.h>
#include <stdlib.h>
int v, w, x, y, z;
%}
%%
Caracteres entre
A :
{w = 10; $$ = 5*w;} B
apóstrofos são
{$$ = 1; v = $1; y = $2;} C
tokens
{
x = $3; z = $4;
printf ("v = %d; w = %d; x = %d; y = %c; z = %c;",
v, w, x, y, z);
return 0;
yylex () {
}
char x;
;
x = getchar ();
B :
'b'
while (x != 'b' && x != 'c')
;
x = getchar ();
C :
'c'
yylval = x;
O tipo e o atributo
;
return x;
são iguais
%%
}
A :
;
B :
;
C :
;
{w = 10; $$ = 5*w;} B
{$$ = 1; v = $1; y = $2;} C
{
x = $3; z = $4;
printf ("- - -", v, w, x, y, z);
return 0;
}
'b'
Ação no início ou meio de uma produção:
'c'
Yacc cria uma produção vazia para um não-terminal
fictício
A ação fica no final dessa produção vazia
Tal não-terminal fica no lugar da ação, na produção
original
A
A
Produção:
:
{w = 10; $$ = 5*w;} B
{$$ = 1; v = $1; y = $2;} C
{x = $3; z = $4;
printf
("... ", v, w, x, y, z);
return 0;}
;
Torna-se:
$$1
$$2
A
:
:
:
;
{w = 10; $$ = 5*w;} ;
{$$ = 1; v = $1; y = $2;} ;
$$1 B $$2 C {
x = $3; z = $4;
printf ("…", v, w, x, y, z);
return 0;
}

Nas produções de $$1 e $$2, $$ é o atributo do lado esquerdo

Na produção de $$2, $1 é o atributo de $$1 e $2 é o de B, da
produção de A

Na produção de A, $3 é o atributo de $$2 e $4 é o de C

Cuidado com a numeração dos atributos da produção original
$$1
$$2
A
:
:
:
;
{w = 10; $$ = 5*w;} ;
{$$ = 1; v = $1; y = $2;} ;
$$1 B $$2 C {
x = $3; z = $4;
printf ("…", v, w, x, y, z);
return 0;
}
Para entrada bc:
$$1
$$2
A
:
:
:
B
C
;
:
:
{w = 10; $$ = 5*w;} ;
{$$ = 1; v = $1; y = $2;} ;
$$1 B $$2 C {
x = $3; z = $4;
printf ("…", v, w, x, y, z); return 0;
}
Resultado no vídeo:
v = 50; w = 10; x = 1; y = b; z = c;
'b';
'c';
Programa 2.10: Pretty-Printer
Dada uma entrada
desorganizada do tipo:
{ i = 1;
i + 1; i
{j = 0;{
= j + 1;
- (x-3)
+ c; } i
1; } }
i =
= 0;
j
a = b
Obter uma saída
organizada do tipo:
{
i = 1 ;
i = i + 1 ;
i = 0 ;
{
j = 0 ;
{
j = j + 1 ;
a = b - ( x - 3 ) + c ;
}
i = i - 1 ;
}
= i -
}
É necessário mudar de linha e tabular oportunamente

Programa em Flex no arquivo pretty2015.l
delim
ws
digito
letra
intct
id
%%
{ws}
{id}
{intct}
"+"
"-"
"("
")"
"{"
"}"
";"
"="
.
%%
[ \t\n]
{delim}+
[0-9]
[A-Za-z]
{digito}+
{letra}({letra}|{digito})*
{ ;}
{strcpy (yylval.cadeia, yytext); return ID;}
{yylval.valint = atoi(yytext); return INTCT;}
{yylval.atr = MAIS; return ADOP;}
{yylval.atr = MENOS; return ADOP;}
{return OPPAR;}
{return CLPAR;}
{return OPBRACE;}
{return CLBRACE;}
{return SCOLON;}
{return ASSIGN;}
{yylval.carac = yytext[0]; return INVAL;}

Programa em Yacc no arquivo pretty2015.y
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define
MAIS
#define
MENOS
int tab = 0;
%}
%union {
char cadeia[50];
int atr, valint;
char carac;
}
7
8
tab: no de tabulações
a serem dadas por
uma função de nome
tabular
%token
%token
%token
%token
%token
%token
%token
%token
%token
%token
%%
<cadeia>
<valint>
<atr>
<carac>
ID
INTCT
ADOP
OPPAR
CLPAR
OPBRACE
CLBRACE
SCOLON
ASSIGN
INVAL
CompStat
:
OPBRACE
{tabular (); printf ("\{\n"); tab++;}
StatList CLBRACE
{tab--; tabular (); printf ("}\n");}
;
StatList
:
Statement
|
StatList Statement
;
Statement
:
AssignStat
|
CompStat
;
AssignStat
:
tabular: dá tantas
tabulações quanto
for o valor de tab
Depois de todo
token imprime seu
texto
ID {tabular (); printf ("%s ", $1);}
ASSIGN {printf ("= ");}
Expression SCOLON {printf(";\n");}
;
Para alguns tokens,
imprime ‘\n’
Expression
Term
:
|
;
:
|
|
Term
Expression ADOP {
if ($2 == MAIS) printf ("+ ");
else printf ("- ");
} Term
ID {printf ("%s ", $1);}
INTCT {printf ("%d ", $1);}
OPPAR {printf("\( ");}
Expression CLPAR {printf (") ");}
;
%%
#include "lex.yy.c"
tabular () {
int i;
for (i = 1; i <= tab; i++)
printf ("\t");
}
Rodar o executável para um
arquivo contendo o programa
desorganizado ilustrativo
Outra forma de apresentar a gramática (com abreviaturas):
Comp :
StatL :
Stat :
AsStat :
Expr :
Term :
|
‘{’ $$1 StatL ‘}’
{tab--; tabular (); write("}\n");} ;
Stat | StatL Stat
;
AsStat | Comp
;
ID $$2 “=” $$3 Expr ‘;’
{write(";\n");}
;
Term | Expr OPAD $$4 Term
;
ID {write($1);} | INTCT {write($1);}
‘(’ $$5 Expr ‘)’ {write (")");}
;
$$4: {if ($2 == MAIS) write (‘+’);
$$1: {tabular ();
else printf (‘-’);}
write ("{\n"); tab++;}
$$2: {tabular (); write ($1);} $$5: {write (‘(’);}
$$3: {write ("=");}

A análise bottom-up por deslocamento e redução, feita
pelo Yacc, simula o caminhamento em pós-ordem, na árvore
sintática de uma sentença correta

Isso é usado a seguir para ilustrar o resultado das ações do
pretty-printer para produzir o efeito desejado

Seja a seguinte sentença bem simples:
{ i = 1 ; j = 2 ; }

A seguir, sua árvore sintática
Seja a pós-ordem:
Comp
{
tab
$$1
StatL

StatL
}
AsStat
AsStat
$$2

Os elementos
dos retângulos
formam a pilha
Stat
Stat
ID(i)
01
ID(j)
=

Reduzir:
Deslocar Ação:
vazio
{ tabular (); write ("{\n");
tab++;}
$$3
Term
$$2
Expr
{_
_
INTCT(1)
=
;

$$3
Expr

;
Term
INTCT(2)
Tela do
vídeo
Seja a pós-ordem:
Comp
{
tab
$$1
StatL

StatL
}
Stat
Stat
AsStat
AsStat
ID(i)
$$2

1
ID(j)
=

Reduzir:
Deslocar Ação:
vazio
{tabular (); write ($1);}
$$3
Term
$$2
Expr
{
_
INTCT(1)
=
;
$$3

i_
Expr

;
Term
INTCT(2)
Seja a pós-ordem:
Comp
{
tab
$$1
StatL

StatL
}
Stat
Stat
AsStat
AsStat
ID(i)
$$2
1
ID(j)
=
$$3
$$2
Expr
=
;
$$3

Expr

;
Term
{


Term
Reduzir: Ação:
Deslocar vazio
{write (“=");}
INTCT(1)
ii_=_
INTCT(2)
Seja a pós-ordem:
Comp
{
tab
$$1
StatL

StatL
}
Stat
Stat
AsStat
AsStat
ID(i)
$$2
1
ID(j)
=
$$3
$$2
Expr
=
;
$$3

Expr

;
Term
{


Term
Reduzir: Ação:
Deslocar
{write
{$$
= $1);}
($1);}irrelevante
INTCT(1)
i=
=_1_
INTCT(2)
Seja a pós-ordem:
Comp
{
tab
$$1
StatL

StatL
}
Stat
Stat
AsStat
AsStat
ID(i)
$$2
1
ID(j)
=
$$3
$$2
Expr
=
;
$$3

Expr

;
Term
{


Term
i=1
1_;
_
Reduzir: Ação:
Deslocar
{write
{$$
= $1);}
(“;\n”);}
irrelevante
INTCT(1)
INTCT(2)
Seja a pós-ordem:
Comp
{
tab
$$1
StatL

StatL
}
Stat
Stat
AsStat
AsStat
ID(i)
1
ID(j)
$$2
=
$$3
$$2
Expr
=
;
$$3

Expr

;
Term
{


Term
_
Reduzir: Ação:
Deslocar vazio
{tabular(); write ($1);}
INTCT(1)
i=1;
j_
INTCT(2)
Seja a pós-ordem:
Comp
{
tab
$$1
StatL

StatL
}
Stat
Stat
AsStat
AsStat
ID(i)
$$2
1
ID(j)
=
$$3
$$2
Expr
=
;
$$3

Expr

;
Term
{


Term
Reduzir: Ação:
Deslocar vazio
{write (“=”);}
INTCT(1)
i=1;
jj_=_
INTCT(2)
Seja a pós-ordem:
Comp
{
tab
$$1
StatL

StatL
}
Stat
Stat
AsStat
AsStat
ID(i)
$$2
1
ID(j)
=
$$3
$$2
Expr
=
;
$$3

Expr

;
Term
{


Term
Reduzir: Ação:
Deslocar
{write
{$$
= $1);}
($1);}irrelevante
INTCT(1)
i=1;
j=
=_2_
INTCT(2)
Seja a pós-ordem:
Comp
{
tab
$$1
StatL

StatL
}
Stat
Stat
AsStat
AsStat
ID(i)
$$2
1
ID(j)
=
$$3
$$2
Expr
=
;
$$3

Expr

;
Term
{

Reduzir: Ação:
Deslocar
{write
{$$
= $1);}
(“;\n”);}
irrelevante

i=1;
j=2
2_;
Term
_
INTCT(1)
INTCT(2)
Seja a pós-ordem:
Comp
{
tab
$$1
StatL

StatL
}
Stat
Stat
AsStat
AsStat
ID(i)
$$2
01
ID(j)
=
$$3
$$2
Expr
=
;
$$3

Expr

;
Term
{


i=1;
j=2;
Term
Reduzir: Ação:
Deslocar
Aceitar
{tab--;
tabular(); write (“}\n”);}
}
_
_
INTCT(1)
INTCT(2)
Comp
{
As ações no prettyprinter produziram os
resultados desejados
$$1
StatL

StatL
}
Stat
Stat
AsStat
AsStat
ID(i)
$$2
ID(j)
=
$$3
$$2
Expr
=
;
$$3

Expr

;
Term
{

Processamento de um
não-terminal: é uma
redução para ele

i=1;
j=2;
Term
}
_
INTCT(1)
INTCT(2)
Resultado
Programa 2.11: Conflitos no Yacc
%token a
%token b
%token c
%token dolar
%token erro
%%
SS: S dolar {printf
;
S : X C | A Y ;
A : /* vazia */ |
X : /* vazia */ |
Y : /* vazia */ |
C : /* vazia */ |
%%
Arquivo conflito.y com uma
gramática geradora da linguagem
L = {aibjck | i=j ou j=k}
("Fim da analise\n"); return;}
A
a
b
C
a ;
X b ;
Y c ;
c ;
A gramática é ambígua:
Sentença aaabbbccc tem
mais de uma árvore
sintática
yylex () {
char x;
Arquivo conflito.y (continuação)
x = getchar ();
while (x == ' ' || x == '\n' ||
x == '\t' || x == '\r')
x = getchar ();
printf ("Caractere lido: %c\n", x);
if (x == 'a') return a;
O analisador gerado pelo
if (x == 'b') return b;
Yacc não consegue tratar
if (x == 'c') return c;
certas gramáticas
if (x == '$') return dolar;
return erro;
Solução: Método mais
}
geral

Executar: yacc conflito.y

Resultado:
yacc: 1 shift/reduce conflict, 1 reduce/reduce conflict.
yylex () {
char x;
Arquivo conflito.y (continuação)
x = getchar ();
while (x == ' ' || x == '\n' ||
x == '\t' || x == '\r')
x = getchar ();
printf ("Caractere lido: %c\n", x);
if (x == 'a') return a;
O analisador gerado pelo
if (x == 'b') return b;
Yacc não consegue tratar
if (x == 'c') return c;
certas gramáticas
if (x == '$') return dolar;
return erro;
Solução: Método mais
}
geral

Executar: yacc –v conflito.y

Abrir arquivo y.output
Arquivo y.output:

Contém um relatório da montagem do analisador

Conflito shift-reduce: indecisão entre deslocar o átomo para
a pilha ou fazer uma redução no topo da pilha

Conflito reduce-reduce: indecisão na escolha de uma
produção para reduzir no topo da pilha
Arquivo y.output - as produções são numeradas:
0
1
2
3
4
5
6
7
8
9
10
11
Produção arfificial do Yacc
$accept : SS $end
SS : S dolar
0: shift/reduce conflict (shift 1, reduce 4)
S : X C
on a
| A Y
No estado 0 (zero – início da análise),
A :
diante de um ‘a’ na entrada, ele não sabe se
| A a
o empilha e vai para o estado 1, ou se faz
X :
uma redução usando a produção 4
| a X b
Y :
0: reduce/reduce conflict (reduce 4, reduce
| b Y c
6) on dolar
C :
No estado 0 (zero – início da análise),
| C c
diante de um ‘$’ na entrada, ele não sabe se
faz uma redução usando a produção 4 ou 6

Há gramáticas ambíguas que têm equivalentes não ambíguas

Exemplo: gramática S  S S | ( S ) | ε
geradora expressões com pares de parêntesis balanceados, tais
como:
( ), ( ( ) ), ( ) ( ), ( ) ( ( ) ( ( ) ) ) ( ( ) )

Gramática equivalente: S  ε | S ( S )
Programa 2.12: Conflito por ações no início ou meio de
produções
%%
SS
: S '$' {printf ("Fim da analise\n");
return;} ;
S :
| S
;
'('
S
')'
Programa correto para
S ε| S(S)
%%
yylex () {
char x; x = getchar ();
while (x == ' ' || x == '\n' || x == '\t' ||
x == '\r')
x = getchar ();
printf ("Caractere lido: %c\n", x);
if (x == '\(' || x == ')' || x == '$')
return x;
return '#';
Rodar para: ( ) ( ( ) ( ) ) ( ( ) ) $
}
Inserindo uma ação:
%%
SS
: S '$' {printf ("Fim da analise\n");
return;} ;
S :
| {printf ("\nyyy");} S '(' S ')'
;
%%
yacc: 1 reduce/reduce conflict.
yylex () {
char x; x = getchar ();
while (x == ' ' || x == '\n' || x == '\t' ||
x == '\r')
x = getchar ();
printf ("Caractere lido: %c\n", x);
if (x == '\(' || x == ')' || x == '$')
return x;
return '#';
}
Arquivo y.output:
0
1
2
3
4
$accept : SS $end
SS : S '$'
S :
$$1 :
S : $$1 S '(' S ')'

O conflito é em usar a produção 2 ou 3 para reduzir diante
do ‘(’

$$1 é um não-terminal fictício

Cada caso tem sua solução particular

Aqui, pode-se colocar a ação depois do S
Observações finais:

Apesar do conflito, o Yacc gera o analisador

O problema é que os resultados produzidos podem não ser
corretos

No projeto da disciplina, as produções do comando
condicional irão gerar um conflito shift/reduce

O analisador gerado resolverá o conflito de forma a obedecer
à regra usual para o caso if-else