5.6 – Complementos de Yacc
5.6.1 – Usando Yacc com gramáticas ambíguas

Gramáticas ambíguas causam conflitos durante a
construção de um analisador sintático pelo Yacc

Os tipos de conflitos são:

Deslocamento-redução: o analisador tanto pode
deslocar um átomo para a pilha, como pode reduzir o
topo da pilha por uma produção

Redução-redução: o analisador pode usar mais de
uma produção para reduzir o topo da pilha

Há regras para a solução de ambiguidades

Yacc gera analisadores mais eficientes para gramáticas
ambíguas do que para gramáticas não ambíguas

Exemplo 5.34: Programa para análise da seguinte gramática
ambígua para cálculo de expressões:
EE+E | E-E | E*E | E/E | (E) | -E
| num
Com a seguinte precedência de operadores:
‘*’ e ‘/’ tem precedência sobre ‘+’ e ‘-’
 Menos-unário tem precedência sobre ‘*’ e ‘/’

O programa deve calcular expressões de valor real
EE+E | E-E | E*E | E/E | (E) | -E
| num

A gramática é ambígua pois para a sentença 5 + 8 * 3 tem
duas árvores sintáticas
E
E
5
E
+
E
E
8
*
E
E
E
3
5
+
*
E
8
E
3
Programa com regras para eliminação de ambiguidades e
comandos de escrita para mostrar as reduções feitas:
%{
#include
#include
#define
%}
%token
%left
%left
%right
%%
<stdio.h>
<ctype.h>
YYSTYPE double
NUM
'+' '-'
'*' '/'
MENUN
Declarações para
solução de
ambiguidades
line
:
;
expr :
|
|
expr '$'
{printf ( "Valor: %g\n", $1);
return 0;}
expr '+' expr
{$$ = $1 + $3;
printf ("Regra1: %g = %g + %g\n", $$, $1, $3);}
expr '-' expr
{$$ = $1 - $3;
printf ("Regra2: %g = %g - %g\n", $$, $1, $3);}
expr '*' expr
{$$ = $1 * $3;
printf ("Regra3: %g = %g * %g\n", $$, $1, $3);}
|
|
|
|
;
%%
expr '/' expr
{$$ = $1 / $3;
printf ("Regra4: %g = %g / %g\n", $$, $1, $3);}
Dispositivo para solução
'(' expr ')'
de ambiguidades
{$$ = $2;
printf ("Regra5: %g = ( %g )\n", $$, $2);}
'-' expr
%prec MENUN
{$$ = -$2;
printf ("Regra6: %g = - %g \n", $$, $2);}
NUM
{$$ = $1; printf ("Regra7: %g = %g\n", $$, $1);}
yylex () {
int c;
do
c = getchar ();
while (c == ' ');
if (c == '.' || isdigit (c)) {
ungetc (c, stdin);
scanf ("%lf", &yylval) ;
return (NUM);
}
return c;
}

A seguir, são descritas regras e dispositivos de programação
do Yacc para solucionar ambiguidades

Por default, o conflito redução-redução é resolvido em
favor da produção que aparece primeiro na lista de
produções

Por default, o conflito deslocamento-redução é resolvido
em favor do deslocamento

No exemplo anterior, não fosse pelas regras de precedência
a serem comentadas logo a seguir, a forma sentencial:
Pilha
expr ‘*’ expr
Entrada
‘+’ 3
provocaria o deslocamento do ‘+’ para o topo da pilha

A soma seria realizada antes da multiplicação

Nas declarações do programa Yacc, pode-se atribuir
precedências e associatividades aos terminais da gramática;
sejam as declarações:
%left
%left
%right
'+' '-'
'*' '/'
'~' (menos unário)
Diferentes

'+' e '-' têm mesma precedência
'*' e '/' têm mesma precedência
A precedência cresce de cima para baixo

No programa aparece:


%right
MENUN

Cada produção em Yacc também tem associada a si uma
precedência e uma associatividade:

Por default, é a precedência e associatividade de seu
terminal mais a direita

Exemplo: a precedência e associatividade da produção
A  a B c D e F G será a de ‘e’

Na decisão (deslocar ‘a’) ou (reduzir por A) haverá
deslocamento se ‘a’ tiver maior precedência que A, e
vice-versa

Na forma sentencial:
Pilha
expr ‘*’ expr
Entrada
‘+’ 3
haverá redução, pois a produção
expr ‘*’ expr tem a precedência de ‘*’
que é maior que a de ‘+’

Na declaração %left ‘-’, o operador ‘-’ é associativo à
esquerda; a seguinte forma sentencial causa redução:
Pilha
expr ‘-’ expr
Entrada
‘-’ 3

A expressão 5-3-1 = 2-1 = 1

Se fosse %right ‘-’, causaria deslocamento

O cálculo de 5-3-1 seria 5-3-1 = 5-2 = 3

Pode-se também forçar uma produção a ter uma
determinada precedência

O programa visto apresenta:
%left
'+' '-'
%left
'*' '/'
%right
MENUN
-------expr | '-' expr %prec MENUN

Esta produção é forçada a ter precedência maior que ‘+’, ‘-’,
‘*’, ‘/’

Exemplo: o programa visto produziu os seguintes resultados
experimentais:
1) Entrada: 5-2-2$
Regra7: 5 = 5
Regra7: 2 = 2
Regra2: 3 = 5 - 2
Regra7: 2 = 2
Regra2: 1 = 3 - 2
Valor: 1
2) Trocando %left '+' '-' por
%right '+' '-':
Entrada: 5-2-2$
Regra7: 5 = 5
Regra7: 2 = 2
Regra7: 2 = 2
Regra2: 0 = 2 - 2
Regra2: 5 = 5 - 0
Valor: 5

Exemplo: o programa visto produziu os seguintes resultados
experimentais:
3) Destrocando:
Entrada: 5*-(3+2)$
Regra7: 5 = 5
Regra7: 3 = 3
Regra7: 2 = 2
Regra1: 5 = 3 + 2
Regra5: 5 = ( 5 )
Regra6: -5 = - 5
Regra3: -25 = 5 * -5
Valor: -25
4) Entrada: -3+8$
Regra7: 3 = 3
Regra6: -3 = - 3
Regra7: 8 = 8
Regra1: 5 = -3 + 8
Valor: 5
5) Trocando %right MENUN
%left '+' '-'
%left '*' '/'
Entrada: -3+8$
Regra7: 3 = 3
Regra7: 8 = 8
Regra1: 11 = 3 + 8
Regra6: -11 = - 11
Valor: -11
5.6.2 – Notificação e tratamento de erros no Yacc

Em Yacc, o tratamento de erros pode ser feito usando
produções de erros entre as produções da gramática

Primeiramente deve-se decidir quais não-terminais da
gramática terão essas produções

Esses podem ser não-terminais que possuam átomos em
suas produções normais, para que mensagens notificando a
falta deles possam ser emitidas

Ou então outros estratégicos geradores de expressões,
comandos, sub-programas, etc.


Seja A um não-terminal escolhido; introduz-se, na gramática,
produções da forma A   error 
 e  são cadeias de terminais e ou não-terminais, vazias ou
não

error é uma palavra reservada do Yacc (um token especial)

Na montagem do analisador, as produções de erros são
tratadas como produções normais da gramática

No entanto, quando o analisador produzido encontra um
erro, a manipulação dos estados e da pilha é diferente do
normal
Encontrando um erro, desempilha-se símbolos e estados, até
encontrar um estado no topo da pilha, cujo conjunto de
itens contenha um item do tipo A  . error 
erro
Entrada
Estado com
item do tipo
A  . error 
Programa
analisador
LR
0
Pilha

Tabelas LR
Saída
Encontrando um erro, desempilha-se símbolos e estados, até
encontrar um estado no topo da pilha, cujo conjunto de
itens contenha um item do tipo A  . error 
erro
Entrada
Estado com
item do tipo
A  . error 
Programa
analisador
LR
0
Pilha

Tabelas LR
Saída
Desloca-se o átomo fictício error para o topo da pilha, como se
tivesse visto um erro na entrada
Estado com
item do tipo
A   error . 
Estado com
item do tipo
A  . error 
erro
Entrada
err
or
Programa
analisador
LR
0
Pilha

Tabelas LR
Saída
Se  for vazia, reduz-se imediatamente para A e uma eventual
ação semântica pode ocorrer (notificação e tratamento de
erros programado)
Estado com
item do tipo
A   error . 
Estado com
item do tipo
A  . error 
erro
Entrada
err
or
Programa
analisador
LR
0
Pilha

Tabelas LR
Saída
Se  for vazia, reduz-se imediatamente para A e uma eventual
ação semântica pode ocorrer (notificação e tratamento de
erros programado)
erro
Entrada
A
0
Pilha
Programa
analisador
LR
Tabelas LR
Saída
Se  não for vazia:
erro
Entrada
A
0
Pilha
Programa
analisador
LR
Tabelas LR
Saída
Se  não for vazia:
o analisador observa os próximos símbolos de entrada, até
encontrar uma sub-cadeia redutível para 
redutível
para 
Estado com
item do tipo
A   error . 
Estado com
item do tipo
A  . error 
erro
Entrada
err
or
Programa
analisador
LR
0
Pilha

Tabelas LR
Saída
Essa sub-cadeia é deslocada para a pilha provocando a redução
para A
redutível
para 

Estado com
item do tipo
A   error . 
Estado com
item do tipo
A  . error 
erro
Entrada
err
or
Programa
analisador
LR
0
Pilha

Tabelas LR
Saída
Essa sub-cadeia é deslocada para a pilha provocando a redução
para A
redutível
para 
O caso mais
comum é o de 
ser uma sequência
de terminais
erro
Entrada
A
0
Pilha
Programa
analisador
LR
Tabelas LR
Saída
Também uma eventual ação semântica pode ocorrer
(notificação e tratamento de erros programado)
redutível
para 
O caso mais
comum é o de 
ser uma sequência
de terminais
erro
Entrada
A
0
Pilha
Programa
analisador
LR
Tabelas LR
Saída

O analisador deixa o estado de erro e volta ao normal,
através da execução de uma macro: yyerrok

O exemplo a seguir é experimental e relativamente simples:


Mostra os casos de  e  serem vazios e compostos de
um e dois terminais

Mostra também o uso da macro yyerrok
A literatura (livros, Internet, etc.) apresenta outros dispositivos
para recuperação de erros no Yacc

Exemplo: programa para a seguinte gramática:
Função : Cabeçalho Declarações
Cabeçalho : ID ( )
Declarações : { ListDecl }
ListDecl : ε | ListDecl Declaração
Declaração : Tipo ListElemDecl ;
Tipo : INT | FLOAT | CHAR | BOOL
ListElemDecl : ElemDecl
| ListElemDecl , ElemDecl
ElemDecl : ID
Analisador léxico:
delim
ws
letra
digito
id
%%
{ws}
bool
char
float
int
{id}
"("
")"
"{"
"}"
";"
","
.
%%
[ \t\n\r]
{delim}+
[A-Za-z]
[0-9]
{letra}({letra}|{digito})*
{ ;}
{return BOOL;}
{return CHAR;}
{return FLOAT;}
{return INT;}
{strcpy (yylval.cadeia, yytext); return ID;}
{return ABPAR;}
{return FPAR;}
{return ABCHAV;}
{return FCHAV;}
{return PVIRG;}
{return VIRG;}
{yylval.carac = yytext[0]; return INVAL;}
Analisador sintático:
%{
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
void Esperado (char *);
%}
%union {
char cadeia[50];
char carac;
}
%token
%token
%token
%token
%token
%token
%token
%token
%token
%token
%token
%token
%%
BOOL
CHAR
FLOAT
INT
<cadeia>
ABPAR
FPAR
ABCHAV
FCHAV
PVIRG
VIRG
<carac>
ID
INVAL
Funcao
: Cabecalho Declaracoes
;
Cabecalho : ID ABPAR {printf ("%s \( ", $1);} FPAR
{printf (")\n");}
| ID error {printf ("%s ", $1);
Esperado ("(");}
FPAR {yyerrok; printf (")\n");}
| ID error {printf ("%s\n", $1);
Esperado ("( )"); yyerrok;}
| error {Esperado ("Identificador");}
ABPAR FPAR {yyerrok; printf ("() ");}
| ID ABPAR error {printf ("%s (\n", $1);
Esperado (")"); yyerrok;}
;
Declaracoes :
ABCHAV {printf ("\{\n");} ListDecl
FCHAV {printf ("}\n");}
;
ListDecl
:
| ListDecl Declaracao
;
Declaracao : Tipo ListElemDecl PVIRG
{printf ("; \n");}
| Tipo ListElemDecl error PVIRG
{Esperado("';' "); yyerrok;}
;
Tipo
: INT
{printf ("int ");}
| FLOAT {printf ("float ");}
| CHAR {printf ("char ");}
| BOOL {printf ("bool ");}
;
ListElemDecl : ElemDecl
| ListElemDecl VIRG {printf (", ");}
ElemDecl
;
ElemDecl : ID {printf ("%s ", $1);}
| error ID
{Esperado("Identificador"); yyerrok;}
;
%%
#include "lex.yy.c"
void Esperado (char *s) {
printf ("\n***** Esperado: %s \n", s);
}

A seguir alguns testes e seus resultados
1) Programa para teste: (sem erros)
main ( )
{
int i, j, k, fat;
bool m, n;
float x;
char a;
}
Resultado:
main ( )
{
int i , j , k , fat ;
bool m , n ;
float x ;
char a ;
}
2) Programa para teste:
()
syntax error
{
int i, j, k, fat;
bool m, n;
float x;
char a;
}
Resultado:
***** Esperado: Identificador
() {
int i , j , k , fat ;
bool m , n ;
float x ;
char a ;
}
3) Programa para teste:
abc )
{
int i, j, k, fat;
bool m, n;
float x;
char a;
}
Resultado:
syntax error
abc
***** Esperado: (
)
{
int i , j , k , fat ;
bool m , n ;
float x ;
char a ;
}
4) Programa para teste:
abc (
{
int i, j, k, fat;
bool m, n;
float x;
char a;
}
Resultado:
syntax error
abc (
***** Esperado: )
{
int i , j , k , fat ;
bool m , n ;
float x ;
char a ;
}
5) Programa para teste:
abc
{
int i, j, k, fat;
bool m, n;
float x;
char a;
}
Resultado:
syntax error
abc
***** Esperado: ( )
{
int i , j , k , fat ;
bool m , n ;
float x ;
char a ;
}
6) Programa para teste:
abc ( )
{
int bool i, j, k, fat;
bool m, n
float x;
char a;
}
Resultado:
abc ( )
{
int syntax error
***** Esperado: Identificador
, j , k , fat ;
bool m , n syntax error
***** Esperado: ';'
char a ;
}