CES-41
COMPILADORES
Capítulo VI
Análise Semântica
Capítulo VI – Análise Semântica
6.1 – Classificação dos testes semânticos
6.2 – Montagem de uma tabela de símbolos
6.3 – Testes semânticos no Yacc
6.4 – Testes semânticos em análise preditora
6.5 – Formalização de análise semântica
6.1 – Classificação dos Testes
Semânticos
6.1.1 – O papel da análise semântica

A análise semântica verifica se as construções sintáticas
fazem sentido

GLC’s não são suficientemente poderosas para descrever
várias construções de linguagens de programação

É conveniente que aspectos dependentes de contexto
nessas linguagens sejam tratados durante a análise semântica

Exemplo: seja a linguagem já vista no Capítulo II:
L = {w c w | w  (a | b)*}
onde ∑ = {a, b, c}

Sentença típica: aababcaabab

A linguagem é uma simplificação daquelas que exigem a
declaração de todo identificador usado nos comandos
executáveis.

Tais linguagens não podem ser geradas por gramáticas livres
de contexto (GLC’s)

Os testes semânticos são de caráter estático, em
contraposição aos testes dinâmicos feitos em tempo de
execução

Exemplo 6.2: Um teste dinâmico:
Sejam a declaração e os comandos em C:
int
A[100], i, x;

scanf (“%d”, &i);
x = A[i];
Evitar i > 99, só é possível em tempo de execução

Os testes semânticos podem ser grupados em quatro classes:

Declaração e uso de identificadores e constantes

Compatibilidade de tipos

Fluxo de dados

Fluxo de controle
6.1.2 – Declarações e uso de identificadores e
constantes
a) Todos os identificadores usados devem ser declarados:

A verificação não é tão simples em linguagens organizadas
por blocos ou linguagens que admitem aninhamento de
sub-programas
Exemplo: em C:
int x ( ) {
int a;
----}
A variável a está
na TabSimb

int y ( ) {
----...=...+a+...
}
Mas seu uso em y
está incorreto
É exigida informação sobre o escopo de validade de um
identificador na TabSimb
Exemplo: em C:
//
Declaracoes globais
Declaração de
---------a no Bloco 1
void main ( ) {
----Uso
{ //Bloco 1
correto
int a;
----{//Bloco 2
----{//Bloco 3
.....= .....+a+.....;
}//Bloco 3 - fim
Uso
}//Bloco 2 - fim
incorreto
}//Bloco 1 – fim
{//Bloco 4
.....=.....+a+.....;
}//Bloco 4 - fim
}//
main - fim

Nessas linguagens, a tabela de símbolos deve ter
informações sobre o escopo de validade de um
identificador

Fortran dispensa a declaração dos identificadores usados
b) Dupla declaração de identificadores:

Isso é proibido para variáveis, funções e tipos globais ou
locais de um mesmo bloco

A Linguagem C permite que o nome de uma função seja
usado também como nome de variável local a essa função

É que a função é definida no escopo global

No entanto, uma função não pode ter o mesmo nome de
uma variável global
Exemplo: em C:
Declarações
#include <stdio.h>
legais de
a
int a = 7;
int b ( ) { int b = 3; return a+b; }
Declarações
legais de
float x ( ) { float a = 8.7; return a; }
void main ( ) {
char a = '$'; int c; float d;
c = b( ); d = x( );
printf ("a = %c, c = %d, d = %g", a, c, d);
}
b
Exemplo: em C:
#include <stdio.h>
Duas declarações de
no escopo global
a: ambas
A segunda declaração é ilegal
int a = 7;
int a ( ) { int b = 3; return a+b; }
float x ( ) { float a = 8.7; return a; }
void main ( ) {
char a = '$'; int c; float d;
c = b( ); d = x( );
printf ("a = %c, c = %d, d = %g", a, c, d);
}
c) Dimensionamento de variáveis indexadas:

Cada linguagem tem sua forma de dimensionar

Pascal:
ID : array [CTE1 .. CTE2] of TipoPrimitivo ;
É obrigatório que CTE1  CTE2

Linguagem C:
Tipo Variável [ CTE ] ;
É obrigatório que CTE > 0
d) Uso de subscritos:

Variáveis escalares não podem ter subscritos

Expressões e lados esquerdos de comandos de atribuição
em C:

O número de subscritos de variáveis indexadas e de
campos indexados de estruturas deve ser igual ao
número de suas dimensões
Exemplo: código em C:
Referências
legais à
variável A
int i, j, k, A[10][20][5];
- - - - A[i+1][2-j][3*k] = ..... ;
..... = ..... + A[7][15][2] + ..... ;
- - - - A[i-3] = ..... ;
..... = ..... + A[7][15] + ..... ;
A = ..... ;
Referências
ilegais à
variável A

Comandos de leitura em C:


O número de subscritos de variáveis indexadas do tipo
char e de campos indexados desse tipo nas estruturas
deve ser igual ou uma unidade menor que o número
de suas dimensões
Exemplo: código legal em C:
char A[15], B[5][10];
scanf (“%s%s%c%c”, A, B[4], A[12], B[2][3]);

Comandos de escrita em C:


Pode-se escrever um vetor de elementos de uma
variável indexada do tipo char ou do campo indexado
desse tipo de uma estrutura
Exemplo: código legal em C:
char A[15], B[5][10];
- - - - printf (“A = %s; B[4] = %s”, A, B[4]);
e) Campos de estruturas e de union’s:

Estão usados corretamente, isto é, correspondem a um
campo declarado da estrutura na qual está sendo usado?

Exemplo:
typedef struct st st;
struct st {int a; float x;};
st s;
- - - - s.a
=
..... ;
x = ..... ;
correto
incorreto

Pascal não admite que, num mesmo escopo, o identificador
de um campo de uma estrutura seja usado como campo de
outra estrutura ou como nome de variável
Em Pascal:
type
st1 = record
a: integer; b: real;
end;
st2 = record
a: real; c: char;
end;
Em C:
struct st1 {
int a; float b;
};
struct st2 {
float a; char c;
};
int a;
var
a: integer;
Declarações ilegais
Declarações legais
f) Unicidade dos rótulos de um comando de seleção

Exemplo: comando switch-case em C:
switch (expr) {
case 1: - - - - - ; break;
case 2: - - - - - ; break;
case 1: - - - - - ; break;
}
Erro: rótulo repetido
g) Declaração de um único módulo principal
6.1.3 – Compatibilidade de tipos
a) Já vistos em aulas de laboratório:

Compatibilidade entre operadores e operandos de expressões

Compatibilidade entre os dois lados de um comando de
atribuição

Compatibilidade da expressão de controle dos comandos
condicionais, repetitivos e da expressão em subscritos de
variáveis indexadas
b) Compatibilidade entre argumentos de chamada e
parâmetros de um sub-programa:

Essa compatibilidade deve ser em número, tipo e modo de
passagem de parâmetros

Em passagem por valor, o argumento deve ser uma
expressão; em passagem por referência, deve ser uma
variável
c) Compatibilidade entre o valor retornado e o tipo de uma
função
d) Compatibilidade entre o protótipo e a definição de um
subprograma
6.1.4 – Fluxo de dados
a) Inicialização e referência a variáveis

Já vistos em aulas de laboratório
b) Alteração na variável de controle de laços:

Em algumas linguagens como Pascal, Algol, Fortran, etc., os
laços for vêm com uma variável de controle explícita

Em algumas delas, é proibido alterar seu valor no escopo do
laço
Exemplo: em Pascal:
for
end
i := 1 to n do begin
- - - - i := ..... ;
- - - - read (i);
- - - - -
proibidos
c) Utilidade de valores atribuídos às variáveis

Não raro, programas atribuem valores inúteis a algumas de
suas variáveis, ou seja, valores que não serão usados em
nenhum momento em qualquer execução do programa

A detecção desse fato normalmente ocorre na fase de
otimização do código intermediário, por meio de uma
análise de fluxo de dados do programa
6.1.5 – Fluxo de controle
a) Detecção de sub-programas recursivos
b) Detecção de chamadas recursivas infinitas
c) Um escape de comando composto está dentro de um
comando composto?
d) Um comando será executado em alguma circunstância?

Exigem análise do fluxo de controle, normalmente aplicada
ao programa na fase de otimização do código intermediário
6.2 – Montagem de uma Tabela de
Símbolos
6.2.1 – Abordagem progressiva:

Linguagens sem subprogramas (visto em aulas de
laboratório)

Linguagens com subprogramas desaninhados e sem
estruturas de blocos

Linguagens com aninhamentos de subprogramas e/ou
estruturas de blocos
6.2.2 – Linguagens sem subprogramas

Estrutura de dados em hashing aberto

Função para o hashing:
Onde:
– NCLASSHASH é o número de classes.
– n é o número de caracteres de x (sem o ‘\0’)
Esquema da tabela de símbolos:
Declarações:
typedef struct celsimb celsimb;
typedef celsimb *simbolo;
struct celsimb {
char *cadeia;
int tid, tvar, ndims, dims[MAXDIMS+1];
char inic, ref, array; simbolo prox; };
int A[10][20][5];
simbolo tabsimb[NCLASSHASH];
dims
cadeia
tid
tvar
inic
ref
array
ndims
A
IDVAR
INTEIRO
0
0
1
3
10 20
0
1
2
5
3
..........
10
Funções:
int InicTabSimb ( )
simbolo ProcuraSimb
(char *cadeia)
simbolo InsereSimb
(char *cadeia, int tid, int tvar)
int hash (char *cadeia)
dims
cadeia
tid
tvar
inic
ref
array
ndims
A
IDVAR
INTEIRO
0
0
1
3
10 20
0
1
2
5
3
..........
10
6.2.3 – Linguagens com subprogramas
desaninhados e sem estruturas de blocos

Há vários tipos de subprogramas:

Cada nome de subprograma deve ter informação sobre o
tipo de subprograma

Em Pascal, por exemplo, tid = IDFUNC ou IDPROC

Escopos para linguagens sem aninhamento de
subprogramas
Escopo global
 Escopo de cada subprograma


O escopo global abrange os dos subprogramas

Escopo do programa principal:
Em C, tem tratamento de subprograma
 Em Pascal, tem tratamento de escopo global


Informação sobre escopo de um identificador:

Ponteiro para a célula da tabela que contém o nome do
identificador que define o escopo
Exemplo:
em C
int ff ( ) {
int a;
----}
ff
IDFUNC
a
IDVAR
escopo

Há escopos que não correspondem a nenhum identificador
Exemplo: escopo global em C
 Pode-se usar na tabela um identificador artificial:
##global, por exemplo
 Tipo de id: IDGLOB


Novas informações para identificadores de variáveis:
Se são parâmetros ou não
 Tipo de passagem de parâmetros


Novas informações para identificadores de subprogramas ou
do escopo global:
Lista de variáveis locais
 Lista de parâmetros
 Lista de funções (para o escopo global)


Exemplo: a seguir, tabela de símbolos para o código
----int d, e, f;
int ff (int m, int n) {
int q, p; - - - - }-----
int d, e, f;
int ff (int m, int n) {
int q, p; - - }

Sugestões para declarações relativas à tabela de símbolos
/* Definicao dos tipos de identificadores */
#define IDGLOB
#define IDVAR
#define IDFUNC
#define IDPROC
#define IDPROG
1
2
3
4
5
/* Definicao dos tipos de
passagem de parametros */
#define PARAMVAL
#define PARAMREF
1
2
1
2
/* Listas de simbolos */
typedef struct elemlistsimb elemlistsimb;
typedef elemlistsimb *pontelemlistsimb;
typedef elemlistsimb *listsimb;
struct elemlistsimb {
simbolo simb;
pontelemlistsimb prox;
}
/* Tabela de simbolos */
typedef struct celsimb celsimb;
typedef celsimb *simbolo;
struct celsimb {
char *cadeia;
int tid, tvar, tparam , ndims,
dims[MAXDIMS+1];
char inic, ref, array, parametro ;
listsimb listvar, listparam,
listfunc;
simbolo escopo , prox;
};
simbolo tabsimb[NCLASSHASH];
6.2.4 – Linguagens com aninhamentos de
subprogramas e/ou estruturas de blocos

Blocos são comandos compostos com declarações no
início

Numa gramática, um bloco pode ser implementado pela
seguinte produção:
Bloco  { ListDeclarações ListComandos }

Numa gramática, subprogramas aninhados podem ser
implementados pelas seguintes produções:
Programa  CabeçalhoProg Declarações
SubProgramas CmdComposto
SubProgramas  ε | SubProgramas
DefSubProg
DefSubProg  CabeçalhoSubProg Declarações
SubProgramas CmdComposto

Pascal trabalha com blocos e os subprogramas podem ser
aninhados

A Linguagem C trabalha com blocos, mas os subprogramas
são desaninhados
Em linguagens com essa estrutura, os escopos formam uma
árvore hierárquica:

O escopo global é a raiz da árvore

Os subprogramas do escopo global são seus filhos na
árvore

Os subprogramas e os blocos internos a um outro
subprograma são filhos desse último

Os campos de uma estrutura e de uma union são filhos
dessas construções

Os escopos dos blocos podem ser representados na tabela
de símbolos por identificadores artificiais (por exemplo,
##bloco01, ##bloco02, etc.)

Cada identificador de escopo pode ter uma lista de
escopos filhos, tal como o caso do escopo global, no passo
anterior desta abordagem progressiva

Dois identificadores na tabela de símbolos podem ter o
mesmo nome, desde que pertencentes a escopos diferentes

Assim sendo, uma procura na tabela de símbolos deve
informar qual o identificador procurado e em qual escopo
ela é feita
Exemplo: blocos em C:
listescfilhos
##global
escopo
void main ( ) {
{bloco 1} {bloco 2}
listescfilhos
}
main
escopo
int f1 ( ) {
{bloco 3} {bloco 4}
}
##bloco 1
##bloco 2
float f2 ( ) {
escopo
escopo
struct st {
listescfilhos
int c1; float c2}
f1
escopo
}
f2
escopo
st
##bloco 3
##bloco 4
escopo
escopo
listtipos
c1
f2
c2
escopo
escopo
escopo
st
6.3 – Testes Semânticos no Yacc
6.3.1 – Linguagem ilustrativa
A linguagem para ilustrar este tópico tem as seguintes
características, no tocante a subprogramas e blocos:

Os subprogramas são do tipo função, podendo ser eles do
tipo void (que não retornam valor) ou de algum tipo
(retornando valor escalar)

Não há aninhamento de funções

Internamente às funções, pode haver aninhamentos de
blocos
Produções da gramática, para subprogramação:
Prog
DeclGlobs
ListDecls
---------Funções
ListFunc
Função
Cabeçalho
Tipo
ListParam
----------
:
:
:
Átomos em
negrito
DeclGlobs Funções
ε | globais : ListDecls
- - - - - - - - - - (conhecidas de outras gramáticas)
: funcoes : ListFunc
: Função | ListFunc Função
: Cabeçalho Bloco
: Tipo ID ( ListParam )
: int | - - - - - - - - - - | void
: - - - - - - - - - - (conhecidas de outras gramáticas)
Bloco
DeclLocs
Comandos
ListCmds
Comando
:
:
:
:
:
|
CmdComposto:

{{ DeclLocs Comandos }}
ε | locais : ListDecls
comandos : ListCmds
Comando | ListCmds Comando
CmdAtrib | CmdSe | - - - - - - - - |
CmdComposto
{ ListCmds }
Exemplo: um programa típico:
globais:
int a, b; real c, d;
funcoes:
Bloco
Delimitadores de
blocos (ABBLOC
e FBLOC)
int ff (int x, y;) {{
locais:
Delimitadores de
logic m, n;
blocos (ABBLOC
comandos:
e FBLOC)
a = b + 1;
{
c = d + 1; if ( - - - - - ) - - - - - ; m = !n;
}
{{ locais: int k, l; comandos: - - - - - }}
}}
void main ( ) {{
locais: - - - - comandos: - - - - }}
6.3.2 – Declaração e uso de identificadores

É necessário verificar se o identificador usado está na tabela
de símbolos, no escopo de seu uso ou em algum ancestral
desse escopo na árvore de escopos

A função ProcuraSimb deve ter como parâmetro, além da
cadeia procurada, o escopo onde ela deve ser procurada

Essa procura deve ser feita na produção
Variável : ID Subscritos
Exemplo:
/* Declaracoes globais */
----void main ( ) {{
{{ /*bl 1*/ - - - - - }}
{{ /*bl 2*/
----{{ /*bl 3*/ - - - - ...= a + ...
átomo em
}}
análise
{{ /*bl 4*/ - - - - - }}
}}
escopo
Escopo do
}}
uso de a
int ff ( ) {{
{{ /*bl 5 */ - - - - - }}
}}
Usar uma variável global escopo para
indicar o escopo do átomo em análise
##global
escopo
main
escopo
##bl 1
escopo
##bl 2
escopo
##bl 3
escopo
##bl 4
escopo
ff
escopo
##bl 5
escopo
/* Declaracoes globais */
ponto da
----análise
##global
void main ( ) {{
escopo
{{ /*bl 1*/ - - - - - }}
{{ /*bl 2*/
escopo
----{{ /*bl 3*/ - - - - ...= a + ...
}}
{{ /*bl 4*/ - - - - - }}
}}
}}
int ff ( ) {{
No início, insere-se o identificador
{{ /*bl */ - - - - - }}
##global na TabSimb, que passa a ser
}}
o escopo corrente
/* Declaracoes globais */
ponto da
----análise
##global
void main ( ) {{
escopo
{{ /*bl 1*/ - - - - - }}
main
escopo
{{ /*bl 2*/
escopo
----{{ /*bl 3*/ - - - - ...= a + ...
}}
{{ /*bl 4*/ - - - - - }}
}}
}}
int ff ( ) {{
O identificador main é inserido na
{{ /*bl */ - - - - - }}
TabSimb, no escopo de ##global
}}
/* Declaracoes globais */
ponto da
----análise
##global
void main ( ) {{
escopo
{{ /*bl 1*/ - - - - - }}
main
escopo
{{ /*bl 2*/
escopo
----{{ /*bl 3*/ - - - - ...= a + ...
}}
{{ /*bl 4*/ - - - - - }}
}}
}}
int ff ( ) {{
O escopo corrente passa a ser o de
{{ /*bl */ - - - - - }}
main
}}
/* Declaracoes globais */
ponto da
----análise
##global
void main ( ) {{
escopo
{{ /*bl 1*/ - - - - - }}
main
escopo
{{ /*bl 2*/
escopo
##bl1
----escopo
{{ /*bl 3*/ - - - - ...= a + ...
}}
{{ /*bl 4*/ - - - - - }}
}}
}}
int ff ( ) {{
O identificador ##bl1 é inserido na
{{ /*bl */ - - - - - }}
TabSimb, no escopo de main
}}
/* Declaracoes globais */
ponto da
----análise
##global
void main ( ) {{
escopo
{{ /*bl 1*/ - - - - - }}
main
escopo
{{ /*bl 2*/
escopo
##bl1
----escopo
{{ /*bl 3*/ - - - - ...= a + ...
}}
{{ /*bl 4*/ - - - - - }}
}}
}}
int ff ( ) {{
O escopo corrente passa a ser o de
{{ /*bl */ - - - - - }}
##bl1
}}
/* Declaracoes globais */
ponto da
----análise
##global
void main ( ) {{
escopo
{{ /*bl 1*/ - - - - - }}
main
escopo
{{ /*bl 2*/
escopo
##bl1
----escopo
{{ /*bl 3*/ - - - - ...= a + ...
}}
{{ /*bl 4*/ - - - - - }}
}}
}}
int ff ( ) {{
O escopo corrente volta a ser o de
{{ /*bl */ - - - - - }}
main
}}
/* Declaracoes globais */
ponto da
----análise
##global
void main ( ) {{
escopo
{{ /*bl 1*/ - - - - - }}
main
escopo
{{ /*bl 2*/
escopo
##bl1
----escopo
{{ /*bl 3*/ - - - - ##bl2
...= a + ...
escopo
}}
{{ /*bl 4*/ - - - - - }}
}}
}}
int ff ( ) {{
O identificador ##bl2 é inserido na
{{ /*bl */ - - - - - }}
TabSimb, no escopo de main
}}
/* Declaracoes globais */
ponto da
----análise
##global
void main ( ) {{
escopo
{{ /*bl 1*/ - - - - - }}
main
escopo
{{ /*bl 2*/
escopo
##bl1
----escopo
{{ /*bl 3*/ - - - - ##bl2
...= a + ...
escopo
}}
{{ /*bl 4*/ - - - - - }}
}}
}}
int ff ( ) {{
O escopo corrente passa a ser o de
{{ /*bl */ - - - - - }}
##bl2
}}
/* Declaracoes globais */
ponto da
----análise
##global
void main ( ) {{
escopo
{{ /*bl 1*/ - - - - - }}
main
escopo
{{ /*bl 2*/
escopo
##bl1
----escopo
{{ /*bl 3*/ - - - - ##bl2
...= a + ...
escopo
}}
##bl3
{{ /*bl 4*/ - - - - - }}
escopo
}}
}}
int ff ( ) {{
O identificador ##bl3 é inserido na
{{ /*bl */ - - - - - }}
TabSimb, no escopo de ##bl2
}}
/* Declaracoes globais */
ponto da
----análise
##global
void main ( ) {{
escopo
{{ /*bl 1*/ - - - - - }}
main
escopo
{{ /*bl 2*/
escopo
##bl1
----escopo
{{ /*bl 3*/ - - - - ##bl2
...= a + ...
escopo
}}
##bl3
{{ /*bl 4*/ - - - - - }}
escopo
}}
}}
int ff ( ) {{
O escopo corrente passa a ser o de
{{ /*bl */ - - - - - }}
##bl3
}}
/* Declaracoes globais */
ponto da
----análise
##global
void main ( ) {{
escopo
{{ /*bl 1*/ - - - - - }}
main
escopo
{{ /*bl 2*/
escopo
##bl1
----escopo
{{ /*bl 3*/ - - - - ##bl2
...= a + ...
escopo
}}
##bl3
{{ /*bl 4*/ - - - - - }}
escopo
}}
•O escopo corrente é o de ##bl3
}}
•O identificador a é procurado
int ff ( ) {{
primeiramente no escopo de ##bl3
{{ /*bl */ - - - - - }} •Depois no de ##bl2, de main e de
##global
}}
•Não sendo achado, não está declarado
Programação em Yacc:
1) Inserindo o identificador ##global:
Prog : {escopo = InsereSimb (“##global”, IDGLOB, NAOVAR,
NULL);} DeclGlobs Funções

Neste ponto, o escopo corrente é o de ##global

As variáveis globais e as funções serão inseridas nesse
escopo
2) Entrada e saída do escopo de uma função:
Cabeçalho
: Tipo ID {escopo = InsereSimb ($2, IDFUNC,
tipocorrente, escopo);} ABPAR Listparam FPAR ;

Neste ponto, o escopo corrente é o do nome da função

Os parâmetros serão inseridos nesse escopo
Função
Bloco

:
Cabeçalho
{proxblocoehfuncao = VERDADE}
;
Para indicar, que o bloco a seguir é de função
3) Entrada e saída do escopo de um bloco:

Criação do tid = IDBLOC
#define IDGLOB
#define IDVAR
#define IDFUNC
#define IDPROC
#define IDPROG
#define IDBLOC

1
2
3
4
5
6
Função para gerar o nome de um novo bloco: NovoBloco

Retorna um ponteiro para uma cadeia de caracteres

Chamadas do não-terminal Bloco
Comando: CmdAtrib | CmdSe | - - - - - - - - |
Bloco | CmdComposto
Função :
Cabeçalho Bloco
Bloco :
ABBLOC {
if (! proxblocoehfuncao)
escopo = InsereSimb (NovoBloco (), IDBLOC,
NAOVAR, escopo);
} DeclLocs {proxblocoehfuncao = FALSO;}
Comandos FBLOC {escopo = escopo->escopo;}
;

Só cria nome para bloco e entra em seu escopo, se o bloco
não for o corpo de uma função

Prepara para receber blocos embutidos no bloco corrente

Saindo de um bloco, o escopo corrente é o do pai
4) Teste de declaração de identificadores usados
Variável
: ID {
escaux = escopo;
##global
simb = ProcuraSimb ($1, escaux);
while (escaux && !simb) {
main
escaux = escaux->escopo
if (escaux)
##bl1
simb = ProcuraSimb ($1, escaux);
}
##bl2
if (! simb) NaoDeclarado ($1);
else if (simb->tid != IDVAR)
##bl3
TipoInadequado ($1);
} Subscritos
escopo
;
escopo
escopo
escopo
escopo
escopo
5) Teste de dupla declaração de identificadores

Basta verificar se o identificador recém-declarado já está na
tabela de símbolos, no escopo corrente
ElemDecl :
ID
{
if (ProcuraSimb ($1, escopo))
DuplaDeclaracao ($1);
}
;
6.3.3 – Variável de controle de comandos for:

Produção:
CmdFor:
for ABPAR Variavel ATRIB Expressao
PVIRG Expressao
PVIRG Variavel ATRIB Expressao
FPAR Comando

O tipo da primeira Variavel e da primeira e terceira
Expressao deve ser escalar inteiro ou caractere

O tipo da segunda Expressão deve ser lógico

A segunda Variavel deve ser igual à primeira

Produções simplificadas para o comando for em Pascal:
CmdFor
CmdAtrib
: for CmdAtrib to Expressao do Comando
: ID = Expressao
Funcionamento desse
comando em termos de
comandos while
A variável i é chamada de
variável de controle do
for
CmdFor
CmdAtrib
: for CmdAtrib to Expressao do Comando
: ID = Expressao
Testes semânticos cabíveis:
1. A variável de controle deve ser escalar do tipo inteiro ou
caractere (testes semelhantes já foram apresentados)
2. As expressões dessas produções devem ser do tipo inteiro ou
caractere (testes semelhantes já foram apresentados)
3. A variável de controle não pode ser global (verificar escopo)
4. A variável de controle não pode ser alterada no escopo
desse comando (ver programa a seguir)
Exemplo de programa com variável de controle global:
/* Declaracoes globais */
int i;
funcoes:
void main ( ) {{
int n;
for i := 1 to n do
call ff ();
----}}
int ff ( ) {{
i := - - - - -;
----}}
A chamada de ff dentro do
comando for altera o valor de i
(variável de controle - global)
Deve-se verificar qual o escopo
de i, por ela ser a variável de
controle do comando for

Seja a seguinte gramática simplificada:
Prog
:
CmdComposto:
ListCmds
:
Comando
:
CmdFor
:
CmdAtrib
:
Expressao
:
CmdComposto
{ ListCmds }
Comando | ListCmds Comando
CmdComposto | CmdFor | CmdAtrib
for CmdAtrib to Expressao do Comando
ID = Expressao
Termo | Termo + Termo
Termo
ID
:
| CTINT

O programa a seguir implementa o teste semântico das
alterações da variável de controle do for em seu escopo

Pode haver aninhamentos de for’s o que torna o teste mais
complexo
%{
#include <string.h>
typedef struct noh noh;
typedef noh *pilha;
struct noh {
char elem[30]; noh *prox;
};
pilha PFor;
void Empilhar (char *, pilha *);
void Desempilhar (pilha *);
char *Topo (pilha);
void InicPilha (pilha *);
char Vazia (pilha);
noh *Procurar (char *, pilha);
%}
Será usada uma pilha
para guardar as variáveis
de controle de um
aninhamento de
comandos for
%union {
char cadeia[50]; int valint; char carac;
}
%type
<cadeia>
CmdAtrib
%token
<cadeia>
ID
%token
<valint>
CTINT
%token
ABCHAV
%token
FCHAV
CmdAtrib terá o mesmo
%token
ATRIB
atributo de sua variável
%token
MAIS
do lado esquerdo
%token
FOR
%token
TO
%token
DO
%token
<atr>
INVAL
%%
Prog
: {InicPilha (&PFor);} CmdComposto
;
CmdComposto: ABCHAV {printf ("{\n");} ListCmds
FCHAV {printf ("}\n");}
;
ListCmds
: Comando
| ListCmds Comando
;
No começo, a pilha é
Comando
: CmdComposto
inicializada vazia
| CmdFor
| CmdAtrib {printf ("\n");}
;
Processado CmdAtrib,
seu atributo, ou seja, a
variável de controle é
empilhada
CmdFor:
FOR {printf ("for ");}
CmdAtrib {Empilhar ($3, &PFor);}
TO {printf ("to ");} Expressao DO
{printf ("do\n");}
Comando {Desempilhar (&PFor);}
;
Encerrado o processamento de
CmdFor, a variável de controle é
desempilhada
A variável do lado
esquerdo de CmdAtrib
é procurada na pilha
Caso seja encontrada:
CmdAtrib
: ID {
erro
printf ("%s ", $1);
if (Procurar ($1, PFor))
printf (
"** Alteracao em variavel de controle de for: %s ** ", $1);
} ATRIB {printf ("= ");} Expressao {strcpy ($$, $1);}
;
O atributo de ID é copiado
no atributo de CmdAtrib
Expressao
Termo
:
|
:
|
;
Termo
Termo MAIS {printf ("+ ");} Termo
ID {printf ("%s ", $1);}
CTINT {printf ("%d ", $1);}
%%
#include "lex.yy.c"
Definições das funções
para manipular a pilha de
variáveis de controle
Exemplo: seja um arquivo de entrada com o seguinte
programa:
{
i=1
for j = 2 to 10 do {
k = 2 + 3 b = e+ww
for i = d+f to h+22 do
j=5
v=3
for k = 32+i to n+2 do {
i = 3 i = 4+b
for k = 3 to 20 do {
j = 3 k = i+w
}
}
}
}
{
i = 1
Saída
for j = 2 to 10 do
{
k = 2 + 3
b = e + ww
for i = d + f to h + 22 do
j ** Alteracao em variavel de controle de for: j ** = 5
v = 3
for k = 32 + i to n + 2 do
{
i = 3
i = 4 + b
for k ** Alteracao em variavel de controle de for: k ** = 3 to 20 do
{
j ** Alteracao em variavel de controle de for: j ** = 3
k ** Alteracao em variavel de controle de for: k ** = i + w
}
}
}
}
Observações:

As variáveis de um comando read também devem ser
procuradas na pilha de variáveis de controle

Linguagens com aninhamentos de blocos e/ou de funções
podem tornar o teste mais complexo (o corpo do for pode ser
um bloco)

A pilha do for pode exigir o escopo da declaração da
variável de controle
6.3.4 – Unicidade dos rótulos de um comando de
seleção

Exemplo de um comando de seleção (Pascal-like):
case ( expr ) {
ct1, ct2, ct3: Cmd1
ct4, ct5: Cmd2
ct6, ct7, ct8: Cmd3
ct9: Cmd4
default: Cmd5
}
Entre as constantes
inteiras ct1, ct2, ct3, ct4,
ct5, ct6, ct7, ct8 e ct9 não
deve haver repetições
Possíveis produções para um comando de seleção:
CmdCase  CASE ABPAR ExprArit FPAR ABCHAV ListCase FCHAV
ListCase  ListCaseSimpl AlterDefault
ListCaseSimpl  ListAlterCase DPONTS Comando
| ListCaseSimpl ListAlterCase DPONTS Comando
ListAlterCase  AlterCase
| ListAlterCase VIRG AlterCase
AlterCase  CTINT | CTCHAR
AlterDefault   | DEFAULT DPONTS Comando
case ( expr ) {
ct1, ct2, ct3: Cmd1
ct4, ct5: Cmd2
ct6, ct7, ct8: Cmd3
ct9: Cmd4
default: Cmd5
}
Idéia: usar listas de rótulos
como atributos de alguns
desses não-terminais
Exemplo:
case (Expressao) {
1, 2, 3: Comando
4, 5: Comando
6: Comando
}
Em algumas
reduções,
concatena-se listas
de rótulos
Em outras,
inaugura-se uma
lista dessas

Acrescenta-se o atributo listrotcase na %union

Acrescenta-se a seguinte declaração %type:
%type

Nas produções do não-terminal AlterCase:
AlterCase:
|
;

<listrotcase> ListCase ListCaseSimpl
ListAlterCase AlterCase
CTINT { $$ = InicListCase ($1)}
CTCHAR { $$ = InicListCase ($1)}
O não terminal AlterCase terá sempre uma lista contendo um
rótulo

Nas produções do não-terminal ListAlterCase:
ListAlterCase
:
AlterCase
|
ListAlterCase VIRG AlterCase
{$$ = ConcatListCase ($1, $3);}
;

Na primeira produção, a ação default é {$$ = $1}; a lista do
não-terminal AlterCase será passada para o não-terminal da
esquerda

Na segunda produção, as listas dos não-terminais
ListAlterCase e AlterCase serão concatenadas e passadas
para o não terminal da esquerda

Nas produções do não-terminal ListCaseSimpl :
ListCaseSimpl : ListAlterCase DPONTS Comando
| ListCaseSimpl ListAlterCase DPONTS
Comando {$$ = ConcatListCase ($1, $2);}
;

Na primeira produção, a ação default é {$$ = $1}; a lista do
não-terminal ListAlterCase será passada para o não-terminal
da esquerda.

Na segunda produção, as listas dos não-terminais
ListCaseSimpl e ListAlterCase serão concatenadas e
passadas para o não-terminal da esquerda

Na produção do não terminal ListCase:
ListCase
:
ListCaseSimpl
AlterDefault

A ação default é {$$ = $1}; a lista do não-terminal
ListCaseSimpl será passada para o não-terminal da
esquerda

Na produção do não-terminal CmdCase:
CmdCase: CASE ABPAR ExprArit FPAR ABCHAV
ListCase FCHAV { ChecUnicRotCase ($6); }
;

A lista do não-terminal ListCase será examinada para
verificar se possui algum rótulo repetido
6.3.5 – Testes semânticos relacionados com
ponteiros
1) Produção para a declaração de ponteiros:
ElemDecl :
ID
Dimens
| @
ID

O caractere ‘@’ declara que ID é um ponteiro

Aqui usa-se @ ID no lugar de * ID para evitar duplicidade de
uso do caractere ‘*’
2) Produções para referências a ponteiros:
Fator : Variavel | CTINT | CTREAL | CTCHAR
| TRUE | FALSE
| ~ Fator
| ( Expressao )
CallFunc
|
|
# Variavel
# Variavel significa “local
apontado por Varíavel”
CmdAtrib
: LadoEsquerdo := Expressao ;
| LadoEsquerdo :=
& Variavel
;
& Variavel significa
“endereço de Variavel”
LadoEsquerdo:
Variavel | # Variavel
3) Novos tokens
%token
DECLPTR
/* ‘@’ – declaração de ponteiro
%token
LOCAPONT
/* ‘#’ – local apontado por
%token
ENDER
/* ‘&’ – endereço de variável */
*/
*/
4) Definições de novos tipos de expressões e variáveis
#define NAOVAR
#define INTEIRO
#define LOGICO
#define REAL
#define CARACTERE
0
1
2
3
4
#define PTRINT
#define PTRLOG
#define PTRREAL
#define PTRCARAC
5
6
7
8
5) Novo campo na tabela de símbolos:

O flag ehpont que sinaliza se uma variável é ou não um
ponteiro
6) Tabela de compatibilidade para os operadores de
ponteiros:
Operador
#
&
Operandos admitidos
Variável ponteiro
Qualquer variável
7) Declaração de variáveis ponteiros:
ElemDecl
: DECLPTR ID {
if (ProcuraSimb ($2) != NULL)
DeclaracaoRepetida ($2);
else {
switch (tipocorrente) {
case INTEIRO: tipoprt = PTRINT;
case REAL: tipoprt = PTRREAL;
case LOGICO: tipoprt = PTRLOG;
case CARACTERE: tipoprt = PTRCARAC;
}
InsereSimb ($2, IDVAR, tipoptr);
}
}
;
8) Compatibilidade em expressões:
Fator : LOCAPONT Variavel {
if ($2)
if (!$2->ehpont)
Esperado ("Variavel ponteiro");
else switch ($2->tvar) {
case PTRINT: $$ = INTEIRO; break;
case PTRLOG: $$ = LOGICO; break;
case PTRREAL: $$ = REAL; break;
case PTRCARAC: $$ = CARACTERE; break;
}
}
;
9) Compatibilidade em comandos de atribuição:

Tabela de compatibilidade:
Tipo do lado
esquerdo
Inteiro
Real
Caractere
Lógico
Ponteiro
Tipo admitido do lado direito
Inteiro ou Caractere
Inteiro, Real ou Caractere
Inteiro ou Caractere
Lógico
Ponteiro de mesmo tipo

Teste de compatibilidade: nas produções:
CmdAtrib :
LadoEsquerdo
:=
Expressao
|
LadoEsquerdo
:=
&
LadoEsquerdo:

Variavel
|
Variavel
Atributo do não-terminal LadoEsquerdo:
%type <tipoexpr>

#
Variavel
LadoEsquerdo
A seguir a programação em Yacc
;
;
LadoEsquerdo :
Variavel
{ if ($1) $$ = $1->tvar; }
Cálculo do atributo
de LadoEsquerdo
| LOCAPONT Variavel {
if ($2)
if (!$2->ehpont)
Esperado ("Variavel ponteiro");
else switch ($2->tvar) {
case PTRINT: $$ = INTEIRO; break;
case PTRLOG: $$ = LOGICO; break;
case PTRREAL: $$ = REAL; break;
case PTRCARAC: $$ = CARACTERE; break;
}
}
;
CmdAtrib : LadoEsquerdo ATRIB Expressao PVIRG
{
switch ($1) {
case INTEIRO: case CARACTERE:
if ($3 != INTEIRO && $3 != CARACTERE)
Incompatibilidade
("Tipos incompativeis numa atribuicao");
break;
case REAL:
if ($3 != INTEIRO && $3 != CARACTERE && $3 != REAL)
Incompatibilidade
("Tipos incompativeis numa atribuicao");
break;
case LOGICO:
if ($3 != LOGICO)
Incompatibilidade
("Tipos incompativeis numa atribuicao");
break;
default:
if ($1 != $3)
Incompatibilidade
("Tipos incompativeis numa atribuicao");
}
}
;
CmdAtrib : LadoEsquerdo ATRIB ENDER Variavel PVIRG
{
switch ($1) {
case INTEIRO: case CARACTERE:
case REAL: case LOGICO :
Incompatibilidade
("Tipos incompativeis numa atribuicao"); break;
default:
if ($1 == PTRINT && $4->tvar != INTEIRO ||
$1 == PTRREAL && $4->tvar != REAL ||
$1 == PTRLOGIC && $4->tvar != LOGICO ||
$1 == PTRCARAC && $4->tvar != CARACTERE)
Incompatibilidade
("Tipos incompativeis numa atribuicao");
}
}
;
6.3.6 – Comentários sobre o poder dos atributos

Como já foi visto, Yacc possibilita que os terminais e os nãoterminais da gramática carreguem consigo atributos
compostos

Isso dá um poder muito grande aos seus programas

Na redução de uma produção, os campos do atributo no
não-terminal à esquerda podem ser calculados em função
daqueles dos símbolos da direita

Esses atributos calculados são usados para o cálculo de
outros atributos, em outras reduções

É um cálculo bottom-up dos atributos dos elementos da
árvore sintática do programa analisado

Como escolher quais campos terá o atributo de um nãoterminal?

Depende do papel desse não-terminal no processo de
compilação

Por exemplo, um não-terminal envolvido na formação de
expressões é usado:

Em testes de compatibilidade de tipos entre
operadores e operandos

Para determinar os operandos das quádruplas com
operadores aritméticos, relacionais e lógicos, na geração
do código intermediário

Para guardar valores intermediários no cálculo de
expressões

Portanto é útil que seu atributo tenha campos para guardar:

O tipo do operando que ele representa numa
operação aritmética ou lógica (inteiro, real, caractere,
lógico, etc.)

O tipo do operando ou resultado (variável, constante,
etc.) da quádrupla gerada para a tradução da operação
aritmética ou lógica em que está envolvido

Mais informações sobre os operandos das
quádruplas (nome de variável, valor de constante, etc.);

Valores intermediários usados no cálculo de uma
expressão aritmética ou lógica, etc.


Outros não terminais podem ter campos dos mais variados
tipos e complexidade:

Lista de rótulos de comandos case

Lista de tipos dos argumentos de chamada de funções

Número de argumentos, número de índices de
elementos de variáveis indexadas, etc.
Esses campos vão aparecendo no projeto do compilador,
conforme sua necessidade:
Ao implementar determinados testes semânticos
 Ao implementar a geração de quádruplas, etc.


Atributos podem ser dados às ações no meio das produções

Foi visto que em Yacc, ações no meio das produções geram
produções vazias de não terminais fictícios, que passam a
ter tais ações no final

Com esses atributos de ações, consegue-se transmitir
informações de uma ação para outra, numa mesma
produção
6.3.7 – Testes relativos à sub-programação
a) Abrangência da abordagem

Aqui serão vistos testes de compatibilidade entre:

Argumentos de chamadas das funções e seus
respectivos parâmetros

Tipo das expressões retornadas por uma função e tipo
declarado da própria função

Para ilustrar esta Seção 6.3.7 adotar-se-á o modelo da
Linguagem C, no tocante à passagem de parâmetros

Então só será abordada a passagem de parâmetros por valor

A passagem por referência será simulada pelo uso de
ponteiros e pelo operador & que manipula o endereço de
variáveis

Para evitar ambiguidades, o operador AND será representado
por “&&”

Para simplificar, supõe-se que a linguagem não trabalhe com
blocos

Os testes aqui estudados, relacionados com a
compatibilidade entre os argumentos de chamada e os
parâmetros de uma função, são os seguintes:

O número de argumentos de chamada deve ser igual
ao número de parâmetros

Os tipos dos argumentos de chamada devem ser
compatíveis com os tipos dos parâmetros

Tabela de compatibilidade adotada nesta abordagem:
** Se o parâmetro for um vetor, o argumento pode ser uma
linha de uma matriz bi-dimensional, desde que seus
elementos sejam de mesmo tipo e em mesmo número dos
elementos do parâmetro
b) Preparo da tabela de símbolos

É útil cada identificador de função conter em sua célula na
tabela de símbolos:

Um campo com o número de seus parâmetros; seja
nparam o nome desse campo

Um campo com a lista de células de seus parâmetros;
seja ListParam o nome dessa lista
Exemplo:
ListVar
Decl
tid
Seja o trecho
de programa:
##global
ListFunc
IDGLOB
escopo
----
#
// Escopo global
float x; . . .
int ff (int b, . . .) {
int a, . . .
ff
.....
}
x
----
#
tid
param
tvar
IDVAR
FALSO
REAL
escopo
ListVar
Decl
tid
List
Param
IDFUNC
tvar
nparam
INT
1+...
escopo
----
#
a
----
#
tid
param
tvar
IDVAR
FALSO
INT
escopo
b
tid
param
tvar
IDVAR
VERD
INT
escopo
Programação no não-terminal Prog:
Prog : {
InicTabSimb (); declparam = FALSO;
} DeclGlobais Funcoes
;
Indicando que parâmetros
não estão sendo declarados
Programação no não-terminal Prog:
Prog : {
InicTabSimb (); declparam = FALSO;
escopo = simb =
InsereSimb ("global##", IDGLOB, NAOVAR, NULL);
} DeclGlobais Funcoes
;
##global
escopo
tid
ListVar
Decl
ListFunc
IDGLOB
escopo
#
InsereSimb aloca o nó-líder
de ListVarDecl e ListFunc
#
simb
Programação no não-terminal Prog:
Prog : {
InicTabSimb (); declparam = FALSO;
escopo = simb =
InsereSimb ("global##", IDGLOB, NAOVAR, NULL);
pontvardecl = simb->listvardecl;
pontfunc = simb->listfunc;
} DeclGlobais Funcoes
ListVar
Decl
tid
ListFunc
;
##global IDGLOB
escopo
pontvardecl
escopo
#
Prepara para inserir a primeira
variável global e a primeira função
nas listas do escopo global
#
pontfunc
simb
Programação no não-terminal Cabecalho:
Cabeçalho
: Tipo ID {
escopo = simb =
InsereSimb ($2, IDFUNC, tipocorrente, escopo);
} ABPAR {declparam = VERDADE;} Listparam
FPAR
ListVar
Decl
tid
ListFunc
;
##global IDGLOB
escopo
escopo
pontvardecl
escopo
#
ListVar
Decl
tid
ff
IDFUNC
List
Param
#
tvar
nparam
pontfunc
INT
escopo
#
#
pontfunc
simb
simb
Programação no não-terminal Cabecalho:
Cabeçalho
: Tipo ID {
escopo = simb =
InsereSimb ($2, IDFUNC, tipocorrente, escopo);
Prepara para inserir a primeira
pontvardecl = simb->listvardecl;
variável local e o primeiro parâmetro
pontparam = simb->listparam;
nas listas do escopo da função
} ABPAR {declparam = VERDADE;} Listparam
FPAR
ListVar
Decl
tid
ListFunc
;
##global
escopo
pontvardecl
escopo
#
ListVar
Decl
tid
ff
IDFUNC
pontvardecl
IDGLOB
List
Param
#
tvar
nparam
simb
INT
escopo
#
#
pontfunc
pontparam
Programação no não-terminal Cabecalho:
Cabeçalho
: Tipo ID {
escopo = simb =
InsereSimb ($2, IDFUNC, tipocorrente, escopo);
pontvardecl = simb->listvardecl;
pontparam = simb->listparam;
} ABPAR {declparam = VERDADE;} Listparam
FPAR {declparam = FALSO;}
;
Indicando que parâmetros não
mais estão sendo declarados
Indicando que parâmetros
começam a ser declarados
Nova função InsereSimb:
simbolo InsereSimb (char *cadeia, int tid, int tvar,
simbolo escopo) {
int i; simbolo aux, s;
/*Codigo comum a todos os identificadores */
i = hash (cadeia); aux = tabsimb[i];
s = tabsimb[i] = malloc (sizeof (celsimb));
s->cadeia = malloc ((strlen(cadeia)+1)* sizeof(char));
strcpy (s->cadeia, cadeia);
s->prox = aux; s->tid = tid; s->tvar = tvar;
s->escopo = escopo;
/*Codigo para parametros e variáveis globais e locais */
if (declparam) {
s->inic = s->ref = s->param = VERDADE;
O identificador inserido é um parâmetro
}
Todo parâmetro é considerado referenciado e inicializado
else {
s->inic = s->ref = s->param = FALSO;
}
/*Codigo para parametros e variáveis globais e locais */
if (declparam) {
s->inic = s->ref = s->param = VERDADE;
if (s->tid == IDVAR)
InsereListSimb (s, &pontparam);
s->escopo->nparam++;
Insere o parâmetro na lista
}
de parâmetros de seu escopo
Acrescenta 1 ao número de
else { parâmetros de seu escopo
s->inic = s->ref = s->param = FALSO;
}
/*Codigo para parametros e variáveis globais e locais */
if (declparam) {
s->inic = s->ref = s->param = VERDADE;
if (s->tid == IDVAR)
InsereListSimb (s, &pontparam);
s->escopo->nparam++;
Insere uma variável na lista
}
de variáveis globais ou locais
de uma função
else {
s->inic = s->ref = s->param = FALSO;
if (s->tid == IDVAR)
InsereListSimb (s, &pontvardecl);
}
/*Codigo para identificador global ou nome de função */
if (tid == IDGLOB || tid == IDFUNC) {
s->listvardecl = (elemlistsimb *)
malloc (sizeof (elemlistsimb));
s->listvardecl->prox = NULL;
}
if (tid == IDGLOB) {
s->listfunc = (elemlistsimb *)
malloc (sizeof (elemlistsimb));
s->listfunc->prox = NULL;
}
Insere o nólíder da lista de
variáveis
globais ou
locais de uma
função
Insere o nó-líder da lista de
funções do escopo global
/*Codigo para nome de função e retorno de Inserir */
if (tid == IDFUNC) {
Insere o nós->listparam = (elemlistsimb *)
líder da lista
de parâmetros
malloc (sizeof (elemlistsimb));
do escopo de
s->listparam->prox = NULL;
uma função
s->nparam = 0;
InsereListSimb (s, &pontfunc);
}
Inicializa com zero o número
de parâmetros de uma função
return s;
}
Insere o nome da função na lista de
funções do escopo global
c) Teste de compatibilidade entre parâmetros e
argumentos escalares

Quando os parâmetros e os argumentos envolvidos são
escalares, os testes de compatibilidade são mais simples

É necessário calcular o número de argumentos de chamada
e formar uma lista com os tipos dos argumentos

Esses, em seguida, podem ser comparados com o número de
parâmetros e com a lista dos mesmos já organizada na
tabela de símbolos
Exemplo: seja o seguinte código
int ff1 (int a, float b, logic c)
{----------}
ff1
int ff2 ( - - - - - )
{
---------a = ff1 (expr1, expr2, expr3);
---------}
Na chamada de ff1:
•O número de expressões
deve ser 3
•Deve haver compatibilidade
entre (expr1, a), (expr2, b) e
(expr3, c)
tid
nparam
IDFUNC
3
ListParam
#
tid
a
tvar
IDVAR
INTEIRO
escopo
tid
b
tvar
IDVAR
REAL
escopo
tid
c
tvar
IDVAR
LOGICO
escopo
Produções envolvidas:
CallFunc
Argumentos
ListExpr

:
:
:
ID ( Argumentos )
ε | ListExpr
Expressao | ListExpr
,
Expressao
É conveniente que os não-terminais ListExpr e
Argumentos tenham como atributos:


Número de argumentos (expressões)
Lista de tipos dos argumentos (tipos das expressões)
typedef struct infolistexpr infolistexpr;
struct infolistexpr { pontexprtipo listtipo; int nargs; };

Acrescenta-se a seguinte declaração na %union:
infolistexpr infolexpr;

E a seguinte declaração de atributo de não-terminais:
%type

<infolexpr> ListExpr Argumentos
A seguir a programação nos três não-terminais envolvidos

Nos não-terminais ListExpr e Argumentos :
ListExpr
:
Expressao {
$$.nargs = 1; $$.listtipo = InicListTipo ($1.tipo);
}
| ListExpr VIRG Expressao {
$$.nargs = $1.nargs + 1;
$$.listtipo =
ConcatListTipo ($1.listtipo, InicListTipo ($3.tipo));
}
;
Argumentos : {$$.nargs = 0; $$.listtipo = NULL;}
| ListExpr /* default: $$ = $1; */

No não-terminal CallFunc :
Atributo de CallFunc:
CallFunc
: ID ABPAR {
Ponteiro para o nome da
função na TabSimb
simb = ProcuraSimb ($1, escopo->escopo);
if (! simb) NaoDeclarado ($1);
else if (simb->tid != IDFUNC)
Necessário:
TipoInadequado ($1);
%type <simb> CallFunc
$<simb>$ = simb;
} Argumentos FPAR {
Necessário para calcular o tipo
$$ = $<simb>3;
de Fator na produção
if ($$ && $$->tid == IDFUNC) {
Fator : CallFunc
if ($$->nparam != $4.nargs)
Incompatibilidade
("Numero de argumentos diferente do numero de parametros");
ChecArgumentos ($4.listtipo, $$->listparam);
}
}
;
A seguir a função ChecArgumentos
void ChecArgumentos (pontexprtipo Ltiparg, listsimb Lparam) {
pontexprtipo p; pontelemlistsimb q;
p = Ltiparg->prox; q = Lparam->prox;
Ltiparg
ff1
tid
nparam
IDFUNC
3
ListParam
########
#
p
Lparam
INTEIRO
q
tid
a
tvar
IDVAR
INTEIRO
INTEIRO
escopo
tid
b
tvar
IDVAR
LOGICO
REAL
escopo
tid
c
tvar
IDVAR
LOGICO
escopo
while (p != NULL && q != NULL) {
switch (q->simb->tvar) {
case INTEIRO: case CARACTERE:
if (p->tipo != INTEIRO && p->tipo != CARACTERE)
Incompatibilidade("....");
break;
case REAL:
if (p->tipo != INTEIRO && p->tipo != CARACTERE &&
p->tipo != REAL)
Incompatibilidade("....");
break;
case LOGICO:
if (p->tipo != LOGICO)
Incompatibilidade("....");
break;
default:
if (q->simb->tvar != p->tipo)
Incompatibilidade("....");
break;
}
p = p->prox; q = q->prox;
}
}
d) Teste de compatibilidade entre parâmetros e
argumentos do tipo variável indexada

Esse teste exige alterações na função ChecArgumentos,
bem como nas ações de algumas produções da gramática

Se um parâmetro for uma variável indexada, o argumento
correspondente deve ser uma variável de mesmo tipo e
dimensão

Se esse parâmetro for um vetor, o argumento pode ser um
vetor ou uma linha de uma matriz bi-dimensional de
mesma dimensão
Exemplo: seja o código
int ff (float A[ , ], int B[ ]) {
É necessário verificar se uma
----expressão tem um só elemento:
}
void main ( ) {
Mais informações nos
float X [... , ... , ...];
atributos de expressões
int Y [... , ... , ...];
----. . . = . . . . . . ff ( X[ ... ] , Y[ ... , ... ] ) . . . . . . ;
----}
Expressões contendo um só elemento
e) Teste de compatibilidade da expressão retornada por
uma função

Tabela de compatibilidade:

A programação para esse teste muito se assemelha com
aquela feita para comandos de atribuição

As produções envolvidas são:
CmdReturn : RETURN | RETURN Expressão

É necessário comparar o tipo da expressão com o tipo da
função que define o escopo do comando return

No caso da primeira produção, o tipo da função deve ser void
6.4 – Testes Semânticos em Análise Preditora

Seja o método apresentado na Seção 5.4.3 do capítulo
sobre análise sintática:
 Cada não-terminal tem seu procedimento (subprograma) particular

Nesse método, as ações para análise semântica e
para geração de código intermediário são recheios
no procedimento de cada não-terminal.

Resta apresentar a implementação de atributos para
não-terminais nesse método

A idéia é que os procedimentos se tornem funções e
os atributos sejam os valores retornados por essas
funções

Exemplo: seja a gramática para expressões:
Expressão  Termo Eaux
Eaux  OPAD Termo Eaux | ε
Termo  Fator Taux
Taux  OPMULT Fator Taux| ε
Fator  CTE | ( Expressão ) | OPNEG Fator

A seguir um analisador sintático preditor recursivo:
141

Programa principal:
void main () {
printf ("Digite a expressao:\n\n");
fflush (stdin); gets (expressao);
printf ("\n"); ptexpr = 0;
carac = NovoCarac (); NovoAtomo ();
Expressao ();
if (atom.tipo != ENDOFFILE)
Esperado (ENDOFFILE);
}
void Expressao () {Termo (); Eaux ();}
void Eaux () {
if (atom.tipo == OPAD) {
NovoAtomo (); Termo (); Eaux ();
}
}
void Termo () {Fator (); Taux ();}
void Taux () {
if (atom.tipo == OPMULT) {
NovoAtomo (); Fator (); Taux ();
}
Todas as funções são do tipo void
}
void Fator () {
switch (atom.tipo) {
case CTE: NovoAtomo (); break;
case ABPAR: NovoAtomo (); Expressao ();
if (atom.tipo != FPAR)
Esperado (FPAR);
NovoAtomo (); break;
case OPNEG: NovoAtomo (); Fator (); break;
default: NaoEsperado (atom.tipo);
NovoAtomo (); break;
}
}

Este programa pode ser usado como esqueleto para
implementar uma calculadora simples

No Yacc, usa-se atributos para valores intermediários
e finais

Nesta análise preditora, cada função passará a retornar
valores do tipo atribnonterm (equivalentes a
atributos no Yacc)
/* Estrutura dos atributos dos não-terminais */
typedef struct atribnonterm atribnonterm;
struct atribnonterm { float valor; int oper; };

Programa principal:
void main () {
atribnonterm x;
printf ("Digite a expressao:\n\n");
fflush (stdin); gets (expressao);
printf ("\n"); ptexpr = 0;
carac = NovoCarac (); NovoAtomo ();
x = Expressao ();
if (atom.tipo != ENDOFFILE)
Esperado (ENDOFFILE);
else
printf ("\nValor da expressao: %g",x.valor);
}
Se houver erros além deste, o valor estará errado
/* Funcao para Expressao */
atribnonterm Expressao () {
atribnonterm x, y;
x = Termo (); y = Eaux ();
if (y.oper == MAIS) x.valor += y.valor;
else x.valor -= y.valor;
return x;
}
As funções não são mais do tipo void
/* Funcao para Eaux */
atribnonterm Eaux () {
atribnonterm x, y; long oper;
x.valor = 0; x.oper = MAIS;
if (atom.tipo == OPAD) {
oper = atom.atrib.atr; NovoAtomo ();
x = Termo (); y = Eaux ();
if (oper == MENOS) y.valor *= -1;
if (y.oper == MAIS) x.valor += y.valor;
else x.valor -= y.valor;
x.oper = oper;
}
return x;
}
/* Funcao para Termo */
atribnonterm Termo () {
atribnonterm x, y;
x = Fator (); y = Taux ();
if (y.oper == VEZES) x.valor *= y.valor;
else x.valor /= y.valor;
return x;
}
/* Funcao para Taux */
atribnonterm Taux () {
atribnonterm x, y; long oper;
x.valor = 1; x.oper = VEZES;
if (atom.tipo == OPMULT) {
oper = atom.atrib.atr; NovoAtomo ();
x = Fator (); y = Taux ();
if (oper == DIV) y.valor = 1 / y.valor;
if (y.oper == VEZES) x.valor *= y.valor;
else x.valor /= y.valor;
x.oper = oper;
}
return x;
}
/* Funcao para Fator */
atribnonterm Fator () {
atribnonterm x;
switch (atom.tipo) {
case CTE: x.valor = atom.atrib.valor;
NovoAtomo (); break;
case ABPAR: NovoAtomo ();
x = Expressao ();
if (atom.tipo != FPAR) Esperado (FPAR);
NovoAtomo (); break;
case OPNEG: NovoAtomo ();
x = Fator (); x.valor *= -1;
break;
default: NaoEsperado (atom.tipo);
NovoAtomo (); break;
}
return x;
}

No exemplo visto, os atributos de todos os nãoterminais são do mesmo tipo e tem dois campos:
valor e oper.

Em gramáticas mais complexas, os tipos podem
variar de não-terminal para não-terminal.
6.5 – Formalização de Análise Semântica
6.5.1 – Esquemas de tradução

O processo de análise semântica apresentado até
aqui tem caráter um tanto informal; bem mais
informal que os processos de análise sintática vistos.

Por exemplo, as especificações semânticas das
linguagens foram feitas quase que desassociadas das
produções das gramáticas.

Para resolver os testes semânticos foram usadas
inúmeras variáveis globais, tais como pilhas, flags,
etc., que nada têm a ver com a gramática da
linguagem analisada.

Se o Yacc não usasse atributos associados aos
símbolos nas reduções, seriam necessárias muitas
outras pilhas e flags, para a análise semântica e
outros recheios da análise sintática.

A literatura sobre compiladores apresenta um certo
grau de formalização da análise semântica e desses
outros recheios.

O nome dado a essa formalização é esquema de
tradução e isso engloba a utilização de atributos dos
símbolos.
Esquema de tradução é uma generalização de
gramática livre de contexto na qual:

Cada ocorrência de símbolo em uma produção tem
associado um conjunto de atributos;

Esses atributos são definidos e computados através
de regras semânticas (ações) inseridas em
determinadas posições das produções da gramática
(no início, meio e fim).

Tal como já foi visto, esses atributos podem ser
valores de constantes numéricas ou não, ponteiros
para um símbolo da tabela de símbolos, listas de
símbolos ou tipos ou constantes, etc..

Também como já foi visto, na árvore sintática de
uma sentença ou programa, esses atributos ficam
localizados em seus nós.

Atributo não é propriedade de uma produção, mas
sim de uma instância de produção no processo de
análise
Exemplo 6.11: Seja o seguinte esquema de tradução para
expressões aritméticas:
L
E
E
T
T
F
F







E ‘\n’
E1 ‘+’ T
T
T1 ‘*’ F
F
‘(’ E ‘)’
num
{L.fict
{E.val
{E.val
{T.val
{T.val
{F.val
{F.val







Árvore sintática com
atributos para
25 * 4 + 10 \n
Imprimir (E.val)}
E1.val + T.val}
T.val}
Para ações sem atribuições,
T1.val * F.val}
cria-se atributos fictícios para
F.val}
serem lados-esquerdos
E.val}
num.lexval}
L
E
E
T
T
F
F







E ‘\n’
E1 ‘+’ T
T
T1 ‘*’ F
F
‘(’ E ‘)’
num
{L.fict
{E.val
{E.val
{T.val
{T.val
{F.val
{F.val







Imprimir (E.val)}
E1.val + T.val}
T.val}
T1.val * F.val}
F.val}
E.val}
num.lexval}
Uma ação só pode ser executada,
quando seus operandos estiverem
disponíveis
No início, os únicos atributos
disponíveis são os lexval’s
L
E
E
T
T
F
F







E ‘\n’
E1 ‘+’ T
T
T1 ‘*’ F
F
‘(’ E ‘)’
num
{L.fict
{E.val
{E.val
{T.val
{T.val
{F.val
{F.val







Imprimir (E.val)}
Agora, as ações que podem ser
E1.val + T.val}
executadas são as do tipo
T.val}
T1.val * F.val}
F.val  num.lexval
F.val}
E.val}
num.lexval}
L
E
E
T
T
F
F







E ‘\n’
E1 ‘+’ T
T
T1 ‘*’ F
F
‘(’ E ‘)’
num
{L.fict
{E.val
{E.val
{T.val
{T.val
{F.val
{F.val







Imprimir (E.val)}
Agora, as ações que podem ser
E1.val + T.val}
executadas são as do tipo
T.val}
T1.val * F.val}
T.val  F.val
F.val}
E.val}
num.lexval}
L
E
E
T
T
F
F







E ‘\n’
E1 ‘+’ T
T
T1 ‘*’ F
F
‘(’ E ‘)’
num
{L.fict
{E.val
{E.val
{T.val
{T.val
{F.val
{F.val







Imprimir (E.val)}
Agora, a ação a ser executada é
E1.val + T.val}
T.val}
T.val  T1.val * F.val
T1.val * F.val}
F.val}
E.val}
num.lexval}
L
E
E
T
T
F
F







E ‘\n’
E1 ‘+’ T
T
T1 ‘*’ F
F
‘(’ E ‘)’
num
{L.fict
{E.val
{E.val
{T.val
{T.val
{F.val
{F.val







Imprimir (E.val)}
Agora, a ação a ser executada é
E1.val + T.val}
T.val}
E.val  T.val
T1.val * F.val}
F.val}
E.val}
num.lexval}
L
E
E
T
T
F
F







E ‘\n’
E1 ‘+’ T
T
T1 ‘*’ F
F
‘(’ E ‘)’
num
{L.fict
{E.val
{E.val
{T.val
{T.val
{F.val
{F.val







Imprimir (E.val)}
Agora
E1.val + T.val}
T.val}
E.val  E1.val + T.val
T1.val * F.val}
F.val}
E.val}
num.lexval}
L
E
E
T
T
F
F







E ‘\n’
E1 ‘+’ T
T
T1 ‘*’ F
F
‘(’ E ‘)’
num
{L.fict
{E.val
{E.val
{T.val
{T.val
{F.val
{F.val







Imprimir (E.val)}
E finalmente
E1.val + T.val}
T.val}
L.fict  Imprimir (E.val)
T1.val * F.val}
F.val}
E.val}
num.lexval}
6.5.2 – Atributos sintetizados e hereditários

No exemplo anterior, os atributos em um nó da
árvore sintática são calculados em função dos
atributos dos filhos desse nó.

Atributos com essa característica recebem o nome de
atributos sintetizados.

Atributos sintetizados são transmitidos pela árvore
na direção bottom-up.

É concebível também uma outra modalidade de
atributos que são transmitidos pela árvore na direção
top-down.

Por exemplo, pode ser útil, para um não terminal,
informação sobre o escopo onde ele está sendo
processado.

Escopo é uma típica informação a ser transmitida na
direção top-down.

Atributos com essa característica recebem o nome de
atributos hereditários.

Numa árvore sintática, os atributos hereditários de
um nó são calculados em função dos atributos dos
pais e irmãos desse nó.
Exemplo: Esquema de tradução com atributos
hereditários (declaração de tipos de variáveis)

Recorda-se que, em Yacc, usou-se a variável
tipocorrente para armazenar o tipo de uma variável
na TabSimb

Tal variável nada tem a ver com as produções da
gramática

A seguir um esquema de tradução para esse
armazenamento:
168
D
T
T
L




T L
int
float
L1 , id
L  id

{L.her  T.tipo}
{T.tipo  INTEIRO}
{T.tipo  REAL}
{L1.her  L.her;
L.fict  IntrodTipo (id.entr, L.her)}
{L.fict  IntrodTipo (id.entr, L.her)}
Árvore sintática para a sentença float id1, id2, id3:
169
D
T
T
L




T L
int
float
L1 , id
L  id

{L.her  T.tipo}
O atributo her é
{T.tipo  INTEIRO}
hereditário
{T.tipo  REAL}
{L1.her  L.her;
L.fict  IntrodTipo (id.entr, L.her)}
{L.fict  IntrodTipo (id.entr, L.her)}
Árvore sintática para a sentença float id1, id2, id3:
Na produção
D  T L
her é função de tipo do
nó irmão
Na produção
L  L1 , id
L1.her é função de her do
nó pai
170
D
T
T
L




T L
int
float
L1 , id
L  id

{L.her  T.tipo}
O atributo her é
{T.tipo  INTEIRO}
hereditário
{T.tipo  REAL}
{L1.her  L.her;
L.fict  IntrodTipo (id.entr, L.her)}
{L.fict  IntrodTipo (id.entr, L.her)}
Árvore sintática para a sentença float id1, id2, id3:
O atributo entr de id é uma
referência à TabSimb
IntrodTipo coloca o valor
de her na célula que
guarda id na TabSimb
fict é um atributo fictício
para receber IntrodTipo,
que não retorna valor
171
D
T
T
L




T L
int
float
L1 , id
L  id

{L.her  T.tipo}
{T.tipo  INTEIRO}
{T.tipo  REAL}
{L1.her  L.her;
L.fict  IntrodTipo (id.entr, L.her)}
{L.fict  IntrodTipo (id.entr, L.her)}
Árvore sintática para a sentença float id1, id2, id3:
Atributos são associados
aos símbolos da
linguagem
Cada nó da árvore pode
possuir um ou mais
atributos
Cada atributo de um nó é
calculado por um
comando das ações do
esquema de tradução
172
D
T
T
L




T L
int
float
L1 , id
L  id
Inicialmente:
{L.her  T.tipo}
{T.tipo  INTEIRO}
T.tipo  REAL
{T.tipo  REAL}
{L1.her  L.her;
L.fict  IntrodTipo (id.entr, L.her)}
{L.fict  IntrodTipo (id.entr, L.her)}
173
D
T
T
L




T L
int
float
L1 , id
L  id
Em seguida:
{L.her  T.tipo}
{T.tipo  INTEIRO}
L.her  T.tipo
{T.tipo  REAL}
{L1.her  L.her;
L.fict  IntrodTipo (id.entr, L.her)}
{L.fict  IntrodTipo (id.entr, L.her)}
174
D
T
T
L




T L
int
float
L1 , id
L  id
Depois:
{L.her  T.tipo}
{T.tipo  INTEIRO}
L.fict  IntrodTipo (id.entr, L.her)
{T.tipo  REAL}
L1.her  L.her
{L1.her  L.her;
L.fict  IntrodTipo (id.entr, L.her)}
{L.fict  IntrodTipo (id.entr, L.her)}
175
D
T
T
L




T L
int
float
L1 , id
L  id
Ainda depois:
{L.her  T.tipo}
{T.tipo  INTEIRO}
L.fict  IntrodTipo (id.entr, L.her)
{T.tipo  REAL}
L1.her  L.her
{L1.her  L.her;
L.fict  IntrodTipo (id.entr, L.her)}
{L.fict  IntrodTipo (id.entr, L.her)}
176
D
T
T
L




T L
int
float
L1 , id
L  id
E finalmente:
{L.her  T.tipo}
{T.tipo  INTEIRO}
L.fict  IntrodTipo (id.entr, L.her)
{T.tipo  REAL}
{L1.her  L.her;
L.fict  IntrodTipo (id.entr, L.her)}
{L.fict  IntrodTipo (id.entr, L.her)}
177
D
T
T
L




T L
int
float
L1 , id
L  id
O atributo her é calculado na
{L.her  T.tipo}
{T.tipo  INTEIRO} direção top-down na árvore
{T.tipo  REAL}
{L1.her  L.her;
L.fict  IntrodTipo (id.entr, L.her)}
{L.fict  IntrodTipo (id.entr, L.her)}
178

Em Yacc, trabalha-se com atributos sintetizados;
atributos de um nó da árvore sintática podem influir
no cálculo dos atributos de seus ancestrais.

Além disso, numa produção, os atributos dos
símbolos dos dois lados podem ser calculados uns
em função dos outros, indistintamente.

Não é possível, em Yacc, que o atributo de um nó
influa no cálculo dos atributos de seus
descendentes na árvore, com a exceção daqueles de
seus filhos.
Exemplo 6.13: Programa em Yacc para a gramática
SabAcD
AabAc|ε
DddD|ε
179
%token a
%token b
yylex () {
char x;
%token c
%token d
x = getchar ();
%token dolar
%token erro
while (x == ' ' || x == '\n'
%%
|| x == '\t' || x == '\r')
SS
:
S dolar {
x = getchar ();
printf ("Fim da analise\n");
printf ("Caractere lido: %c\n", x);
return 0;}
if (x == 'a') return a;
if (x == 'b') return b;
;
if (x == 'c') return c;
S
:
a {$1 = 5;} b {$$ = 8;}
if (x == 'd') return d;
A {$5 = $1 + 2; $3 = $4 + $5;} c D {
if (x == '$') return dolar;
$$ = $1 + $3 + $5 + 10; $8 = 10 * $$;
return erro; Saída para abcdd$ :
printf ("$$ = %d; $8 = %d;\n", $$, $8); }
}
Caractere lido: a
;
Caractere lido: b
A
:
Caractere lido: c
Caractere lido: d
|
abAc
;
Caractere lido: d
D
:
Caractere lido: $
|
ddD
;
$$ = 37; $8 = 370;
%%
Fim da analise 180

Ainda em Yacc, numa mesma produção, não se pode
referenciar à esquerda de um símbolo o seu atributo.

Exemplo : Trocando no exemplo anterior as ações da
produção de S por:
S
:
a {$1 = 5;} b {$$ = 8;}
A {$5 = $1 + 2; $8 = $4 + $5;} c D
{
$$ = $1 + $3 + $5 + 10; $8 = 10 * $$;
printf ("$$ = %d; $8 = %d;\n", $$, $8);
}
;

Ou seja, referenciando $8, que é o atributo de D, à
esquerda de D, a execução do Yacc acusará erro.
181
Numa análise preditora recursiva procedimental:

Atributos hereditários podem ser passados como
parâmetros para os procedimentos dos não-terminais

Conforme já foi visto, atributos sintetizados podem
ser valores retornados desses procedimentos.
182
6.5.3 – Grafo de dependências dos atributos

O fato de atributos de alguns nós de uma árvore
sintática serem calculados em função daqueles de
outros nós concebe um grafo de dependências

Exemplo 6.15: Grafo de dependências da árvore
O grafo deve ser acíclico, senão está errado

Sendo esse grafo acíclico, a execução das ações do esquema
deve obedecer a uma ordenação topológica do grafo

Ordenação topológica:
tipo1  REAL
her3  tipo1
fict3  IntrodTipo (entr3, her3)
her2  her3
fict2  IntrodTipo (entr2, her2)
her1  her2
fict1  IntrodTipo (entr1, her1)

Muitos esquemas de tradução dispensam a
construção de árvores sintáticas
 Mas
o uso de atributos sintetizados e
hereditários fica bem determinado se essas
existirem.

Assim, conceitualmente falando, dado um esquema
de tradução e uma sentença a ser analisada, pode-se
realizar os seguintes passos: