Tema 4 Análise Semântica

Prévia do material em texto

DESCRIÇÃO
Apresentação da tabela de símbolos, das árvores de sintaxe e do analisador semântico.
PROPÓSITO
Apresentar as características da tabela de símbolos, os tipos de árvores de sintaxe de demais
representações intermediárias gráficas e o funcionamento do analisador semântico.
PREPARAÇÃO
Não há necessidade de preparação prévia.
OBJETIVOS
MÓDULO 1
Descrever a organização e o funcionamento da tabela de símbolos
MÓDULO 2
Identificar as características das árvores de sintaxe e demais representações gráficas
intermediárias
MÓDULO 3
Analisar as principais técnicas utilizadas na análise semântica
INTRODUÇÃO
O terceiro passo da etapa de análise na compilação é a análise semântica, no qual será
verificado o contexto do programa escrito. Para tal, a partir da árvore de sintaxe gerada pelo
parser, serão validados os tipos, parâmetros de procedimentos, escopo de variáveis etc.
Para que isso seja possível, o analisador semântico irá manipular as informações da tabela de
símbolos, decorar a árvore de derivação, gerar e analisar o grafo de dependência e realizar a
tradução dirigida pela sintaxe.
Neste tema, veremos ainda que a análise semântica é, normalmente, executada de forma
concomitante com a análise sintática.
MÓDULO 1
 Descrever a organização e o funcionamento da tabela de símbolos
TABELA DE SÍMBOLOS (TS)
O compilador, em suas diversas etapas, utiliza um conjunto de tabelas auxiliares para seu
funcionamento. Algumas delas dependem apenas da linguagem do programa-fonte, como a
tabela de palavras reservadas ou a de delimitadores, que são muito importantes,
particularmente para as análises léxica e sintática.
Entretanto, existe uma tabela de extrema importância que é montada e consultada ao longo de
todas as fases da análise: A tabela de símbolos (Figura 1).
Fonte: EnsineMe
 Figura 1. Tabela de símbolos e a etapa de análise.
Fonte: EnsineMe
A TS (Tabela de Símbolos) é uma estrutura de dados que armazena informações sobre vários
aspectos da análise do programa-fonte, como:
Declarações de variáveis.
Declarações dos procedimentos ou sub-rotinas.
Parâmetros de sub-rotinas.
Ela também permite associar atributos aos identificadores, como:
Tipo e escopo para variáveis.
Parâmetros de subprogramas.
Limites de vetores.
A ideia básica de seu funcionamento é:
Durante a análise léxica, quando um identificador é encontrado, é verificado se ele já existe na
TS. Caso não exista, ele é inserido, mesmo que ainda não possam ser associados atributos a
ele.

Toda vez que um identificador for reconhecido no programa-fonte, em qualquer etapa da
análise, a tabela é consultada e as informações que ali existem são comparadas com as
informações obtidas na análise, e qualquer nova informação é inserida na tabela.
As informações armazenadas na tabela dependem da categoria do símbolo:
VARIÁVEIS
Classe (var), tipo, endereço no texto, precisão, tamanho.
PARÂMETROS FORMAIS
Classe (par), tipo, mecanismo de passagem.
PROCEDIMENTOS/SUB-ROTINAS
Classe (proc), número de parâmetros.
Outro aspecto muito importante que a tabela de símbolos controla é o escopo, ou seja, em que
parte do programa uma determinada variável é acessível.
Algumas linguagens de programação suportam o uso do mesmo identificador em diferentes
blocos do programa, por exemplo, em uma sub-rotina podemos ter uma variável Total, e este
mesmo nome ser usado como um parâmetro em outra sub-rotina. Então, o compilador, durante
a análise semântica, terá que delimitar exatamente a qual Total um comando está se referindo.
Para isso, ele lançará na tabela de símbolos as informações de escopo do símbolo.
 ATENÇÃO
Note que as linguagens que admitem esse tipo de uso implicam que na TS podem existir várias
entradas para o mesmo nome em blocos distintos do programa, cada uma com a sua
“interpretação semântica” específica. Isso mostra que mesmo na última etapa da análise a TS
é lida e atualizada.
Dessa forma, a definição da categoria do símbolo é utilizada pelo analisador semântico para:
Diferenciar o nome de uma variável do nome de uma sub-rotina a ser chamada.
Evitar que o nome de um procedimento apareça sem a lista de seus argumentos ou à
esquerda de uma atribuição.
Evitar que um numeral seja o destino de uma atribuição.
Evitar, nas linguagens que assim o exigirem, a atribuição de uma letra a uma variável
numérica.
Atribuir a todas as constantes idênticas o mesmo endereço de memória.
Outro aspecto importante a se observar é que linguagens que aceitam novos tipos de dados
criados pelo usuário, como Pascal e C, requerem que o compilador armazene o nome do tipo
criado na TS e seus componentes. Dessa forma, o analisador semântico pode validar a
declaração das variáveis do tipo criado pelo usuário.
Para manipular esses tipos, o analisador sintático, ao reconhecer um símbolo, passa ao
analisador semântico, que verifica se ele já existe na TS. Se não existir, o insere; caso contrário,
ele procura verificar a compatibilidade entre os atributos armazenados e a forma como está
sendo usado no momento.
Portanto, a consulta e a manipulação da tabela de símbolos são pesadas, e a sua forma de
organização vai afetar diretamente o desempenho do compilador.
ORGANIZAÇÃO DA TABELA DE SÍMBOLOS
A tabela de símbolos pode ser acessada e organizada de várias formas diferentes. Segundo
Cooper e Torczon (2014), as formas mais comuns de implementação são:
LISTA LINEAR
BUSCA BINÁRIA
TABELA HASH
LISTA LINEAR
Uma lista linear pode se expandir até um tamanho arbitrário. O algoritmo de busca é um laço
único, pequeno e estreito. Infelizmente, o algoritmo de busca exige O(n) sondagens por
pesquisa, na média, onde n é o número de símbolos na tabela.
Essa única desvantagem quase sempre supera a simplicidade da implementação e da
expansão. Para justificar o uso de uma lista linear, o construtor de compiladores precisa de
evidências fortes de que os procedimentos que estão sendo compilados têm muitos poucos
nomes, como poderia ocorrer para uma linguagem orientada a objeto.
BUSCA BINÁRIA
Para reter a facilidade de expansão da lista linear enquanto se melhora o tempo de busca, o
construtor de compiladores poderia usar uma árvore binária balanceada. No caso ideal, uma
árvore balanceada deve permitir a pesquisa em O(log2 n) sondagens por pesquisa; essa é uma
melhoria considerável em relação à lista linear. Muitos algoritmos têm sido publicados para o
balanceamento de árvores de busca (efeitos semelhantes podem ser alcançados usando a
busca binária em uma tabela ordenada, mas a tabela torna a inserção e a expansão mais
difíceis).
TABELA HASH
Uma tabela hash pode minimizar os custos de acesso. A implementação calcula um índice de
tabela diretamente a partir do nome. Desde que a computação produza uma boa distribuição
de índices, o custo médio de acesso deverá ser O(1). Porém, o pior caso pode recair na busca
linear. O construtor de compiladores pode tomar medidas para diminuir a probabilidade de que
isso aconteça, mas casos patológicos ainda podem ocorrer. Muitas implementações de tabela
hash possuem esquemas pouco dispendiosos para expansão.
Agora que já conhecemos um pouco sobre a Tabela de Símbolos, responda:
CADA ENTRADA NA TS ESTÁ RELACIONADA À
DECLARAÇÃO DE UM NOME. NO ENTANTO, AS ENTRADAS
POSSUEM TAMANHO UNIFORME?
SIM
NÃO
As entradas não possuem tamanho uniforme e esse fato deve ser levado em conta em sua
organização. Como vimos, o preenchimento da tabela é iniciado pelo scanner durante a análise
léxica, onde as entradas são basicamente compostas pelo token e pelo lexema associado.
Outros atributos do token somente são definidos durante as análises sintática e semântica, que
irão acrescentar atributos às entradas ou até mesmo novas entradas.
Como cada uma das diversas categorias de entradas (variáveis, constantes, subprogramas
etc.) possui atributos diferentes, a entrada de cada tipo de categoria possuirá uma estrutura
diferente, ou seja, o tamanho de cada uma será diferente. EXEMPLO
Entradas referentes a terminais como “int” são normalmente compostas apenas do token
e do lexema.
Entradas de variáveis possuem mais atributos com ID, lexema, tipo e valor.
Entradas de variáveis do tipo vetor exigem ainda os atributos de limites superior e inferior.
Entradas referentes a subprogramas devem possuir informações a respeito de seus
parâmetros (quantidade, forma de passagem etc.).
Como lidar com essa situação, então? Temos duas abordagens possíveis:
Armazenar esses atributos com o nome em uma mesma tabela – o que acarreta
desperdício de espaço.
Armazenar a parte comum a todos em uma tabela e as informações adicionais em outras
estruturas de armazenamento ligadas à entrada por ponteiros – que tem como
desvantagem a recuperação da informação de forma mais lenta.
Além dos aspectos referentes à diferença de tamanho, temos que lembrar que uma TS de um
programa, mesmo que ele seja relativamente pequeno, acarreta as seguintes situações:
O número de entradas da tabela atinge a casa de vários milhares.

A quantidade de consultas e operações de inclusão, exclusão e atualização será enorme.
Face às características citadas, a forma mais eficiente, normalmente, de implementar a TS é
utilizando uma tabela hash, pois se constitui em um método de busca extremamente eficiente,
principalmente pela característica de o tempo de acesso para qualquer entrada ser constante.
TABELA DE SÍMBOLOS COMO TABELA HASH
Para implementar a TS através do uso do hashing, é necessário que sejam definidos dois
aspectos:
A FUNÇÃO DE HASHING
javascript:void(0)
Responsável por transformar a chave de busca em um código que determina a sua posição na
tabela. Deve ser de fácil implementação e rápida execução.
O TRATAMENTO DE COLISÕES
Que define como proceder se dois símbolos gerarem a mesma entrada na tabela.
FUNCIONAMENTO DA FÓRMULA HASH
Como um compilador realiza muito acesso à TS, a eficiência é fundamental em sua
implementação. O método hash fornece uma forma elegante e muito eficiente de mapear
nomes e números inteiros pequenos. Observe a Figura 2, que mostra a implementação de uma
TS simples de 10 slots, construída a partir de hash, como um vetor de registros onde cada slot
mantém a descrição gerada pelo compilador de um único nome.
Fonte: COOPER e TORCZON, 2014
 Figura 2 − Tabela hash.
Fonte: COOPER e TORCZON, 2014
Para realizar o mapeamento, a função de hash h realiza um cálculo a partir do nome da entrada
e determina um número inteiro que corresponderá ao índice de entrada e um vetor (ou tabela).
javascript:void(0)
Na figura 2, podemos observar que os nomes a, b e c já foram inseridos, e o nome d está sendo
inserido na posição 2, já que h(d) = 2.
Para acessar o registro “n”, é necessário calcular h(n) e indexar na tabela em h(n). Se h mapear
dois ou mais símbolos para o mesmo inteiro pequeno, ocorre uma “colisão”.
TRATAMENTO DE COLISÕES
Na situação da Figura 2, se h(d) = 3, ocorreria uma colisão, pois na posição 3 já temos “a”. A
escolha da fórmula de hash é extremamente importante para minimizar as colisões, porém,
não existe fórmula perfeita e as colisões sempre irão ocorrer. Como tratá-las, então?
HASHING ABERTO
Esse método, também chamado de hashing de balde, assume que a função de hash h irá
produzir muitas colisões. Ele conta que h irá espalhar o conjunto de chaves de entrada em uma
quantidade fixa de baldes (buckets). Cada balde é organizado como uma lista linear de
registros, sendo um registro por nome.
O lookup (Função de pesquisa) , ao procurar uma entrada n", percorre a lista linear
armazenada no balde indexado pelo resultado de h(n).
Dessa forma, lookup(n) exige o cálculo do hash de n (h(n)) e a busca em uma lista linear.
Normalmente, o cálculo de h(n) é rápido, mas a busca na lista será mais lenta quanto maior ela
for. Para uma tabela com tamanho S e N nomes, o custo da pesquisa será de O(N/S). Se h
realizar a distribuição dos nomes de modo uniforme e a razão entre nomes e baldes for
pequena, esse custo irá se aproximar do que se procura como objetivo, ou seja, O(1).
Fonte: COOPER e TORCZON, 2014
 Figura 3 − Tabela de hashing aberto.
Fonte: COOPER e TORCZON, 2014
A Figura 3 mostra o funcionamento desse esquema. Nela podemos ver uma pequena tabela de
hash onde h(a) = h(d) = 3, ocorrendo, portanto, uma colisão. Portanto, a e d apontam para o
mesmo slot na tabela. Este, por sua vez, possui um ponteiro para a lista encadeada das chaves
que colidem naquele slot.
A inserção de novas entradas sempre ocorre no início da lista, para serem mais rápidas. A lista
d está antes de a, o que significa que foi incluído depois de a. Segundo Cooper e Torczon
(2014), essa forma de tratamento possui as seguintes vantagens:
Como cria um nó em uma das listas interligadas para cada nome inserido, ele pode tratar
um número arbitrariamente grande de nomes sem esgotar o espaço.
Um número excessivo de entradas em um balde não afeta o custo de acesso em outros
baldes.
Como a representação concreta para o conjunto de baldes normalmente é um array de
ponteiros, o overhead para aumentar S é pequeno — um ponteiro para cada balde
acrescentado (isso torna menos dispendioso manter N/S pequeno. O custo por nome é
constante).
A escolha de S como uma potência de dois reduz o custo da inevitável operação mod
exigida para implementar h.
Quanto às desvantagens, os autores afirmam que:
O hashing aberto pode fazer uso intenso de alocação. Cada inserção aloca um novo registro.
Isso pode ser observado quando implementado em um sistema com alocação de memória
pesada.
Se qualquer conjunto em particular se tornar grande, lookup se degrada até a busca linear. Com
uma função hash com comportamento razoável, isso ocorre somente quando N é muito maior
que S.
ENDEREÇAMENTO ABERTO
No endereçamento aberto, o tratamento de colisões é realizado calculando um índice
alternativo usando outra função de hashing g(n), para os nomes cujo slot normal calculado por
h(n)está ocupado. Por isso, essa técnica também é chamada de rehashing.
A pesquisa pela função de busca lookup(n) inicia com o cálculo de h(n) e o exame do slot
indexado. A partir desse ponto, se o slot:
Estiver vazio, retorna um erro informando que a entrada não existe na tabela de símbolos.
Contiver n, recupera as informações do nome.
Se o slot contiver outro valor:
Calcula g(n), que corresponde a um incremento de busca.
Examina o slot indexado por (h(n) + g(n)) mod S.
Se o slot possui o símbolo, recupera as informações.
Se o slot não contiver o símbolo:
Examina o slot indexado por (h(n) + 2 * g(n)) mod S.
Examina o slot indexado por (h(n) + 3 * g(n)) mod S.
Segue esse ciclo até encontrar o nome.
Se chegar a um slot vazio ou voltar para h(n) uma segunda vez, significa que o nome não
está na tabela e retornará um erro.
A figura 4 mostra uma pequena tabela de hash com esse esquema, usando os mesmos dados
apresentados na Figura 3. Quando ocorreu a inserção de d, o cálculo de h(n) produziu uma
colisão com a. A função g(d) produziu o incremento 2 de maneira que a inserção que ocorreu
na slot 5 g(d) produziu 2, de modo que Insert colocou d no índice 5 da tabela.
Fonte: COOPER e TORCZON, 2014
 Figura 4 − Tabela de endereçamento aberto.
Fonte: COOPER e TORCZON, 2014
A principal diferença entre esse método e o hashing aberto é que:
Hashing aberto
Todos os nomes que geram o mesmo valor em h(n) ficam no mesmo slot e são acessados em
uma lista encadeada.

Endereçamento aberto
Todos os nomes que geram o mesmo valor em h(n) ficam armazenados diretamente na tabela
e um único local na tabela serve de partida para várias cadeias que geram um valor diferente de
g(n). Esse tipo de tratamento busca um compromisso entre espaço e velocidade. Como cada
chave fica armazenada na tabela S, deve ser maior que N.
SE AS FUNÇÕES DE HASHING H() E G() FOREM BEM
ESCOLHIDAS, OCORRERÃO POUCAS COLISÕES E
AS CADEIAS GERADAS PELO REHASHING SERÃO
CURTAS E A VELOCIDADE DE RECUPERAÇÃO ALTA.
Dentreas vantagens dessa solução, temos que:
Esse esquema não precisa armazenar ponteiros para indexar a cadeia de rehashing, já
que o cálculo de g(n) é rápido.
Como não se consume espaço da tabela com ponteiros, ela será maior, o que diminui a
possibilidade de colisão.
Quanto mais curtas as cadeias de hashing, maior a velocidade de consulta.
Como desvantagens, podemos citar:
Como a cadeia de rehashing é encadeada na própria tabela, o tratamento da colisão do
slot 3 h(a) = h(d), como foi exemplificado, colocou d no slot 5. Isso pode gerar uma nova
colisão com, por exemplo, e, se h(e) = 5.
Como S deve ser do mesmo tamanho de N, a tabela deve ser expandida se N for muito
grande.
Para simplificar a implementação, alguns compiladores utilizam uma função constante
para g, porém isso cria uma única cadeia de hashing para cada valor de h, o que mescla
cadeias diferentes.
ARMAZENAMENTO DE REGISTROS DE
SÍMBOLOS
As duas formas de tratamento de colisões não resolvem a questão de como alocar espaço
para a informação associada a cada entrada da tabela de hash. Uma solução para isso seria a
implementação representada na figura 5.
Utilizando a solução de hashing aberto para o tratamento das colisões, as próprias listas de
cadeia podem ser implementadas na pilha, o que reduz o custo de alocação de registros
individuais, particularmente se a inserção for uma operação pesada.
Já com endereçamento aberto, as cadeias de rehashing ainda são implícitas no conjunto de
índices, preservando a economia de espaço que motivou a ideia.
Fonte: COOPER e TORCZON, 2014
 Figura 5 − Alocação de pilha para registros.
Fonte: COOPER e TORCZON, 2014
Quando armazenamos os registros reais em uma pilha, eles se constituem em uma tabela
densa que é muito melhor para E/S externa e torna mais eficiente percorrer os símbolos −
operação na qual o compilador realiza para várias tarefas, por exemplo, atribuir locais de
armazenamento.
Uma última vantagem é a simplificação na tarefa de expandir o conjunto de índices, já que
basta descartar o antigo, alocar um conjunto maior e depois reinserir os registros na nova
tabela percorrendo a pilha de baixo para cima.
O percurso na tabela densa é menos custoso, pois isso evita percorrer slots vazios, como pode
acontecer quando o endereçamento aberto expande os índices para manter as cadeias de
rehashing curtas ou, ainda, no caso do hashing aberto ficar cassando os ponteiros para
percorrer os nós das listas lineares.
CONSTRUÇÃO DE UMA TABELA DE SÍMBOLOS
Para construir a tabela de símbolos, três funções básicas são necessárias:
LOOKUP(NOME)
Pesquisa a tabela em busca do símbolo correspondente ao nome. Se o símbolo existir na
célula h(nome) da tabela, retorna o registro; caso contrário, deve retornar um erro informando
que este não foi encontrado.
INSERT(NOME, R)
Armazena a informação existente em r no slot indexado por h(nome), sendo que essa função
pode expandir a tabela, se necessário, para acomodar o registro.
REMOVE(NOME)
Apaga uma entrada na tabela de símbolos.
Muitas vezes, a própria função lookup pode ser implementada com um parâmetro que
especifica se o nome, se não encontrado, deve ser inserido na TS. Isso evita o erro de não
encontrar o símbolo e a eventual violação da regra “declarar antes de usar” nos esquemas de
tradução dirigida pela sintaxe ou para lidar com o aninhamento de escopos léxicos. Essa
solução simples de três funções serve perfeitamente para os esquemas de tradução dirigida
pela sintaxe.
javascript:void(0)
javascript:void(0)
javascript:void(0)
 EXEMPLO
No processamento da declaração de uma variável, o scanner cria uma entrada para o token na
tabela de símbolos usando insert. A seguir, o parser − ao reconhecer uma produção que declara
uma variável − usa lookup para encontrar o token. Se existir, apaga a entrada anterior utilizando
remove(nome) e reinclui a entrada com os novos atributos. Se não existir, usa insert para incluir
o símbolo e seus atributos.
OUTRAS FUNÇÕES PODEM SER ACRESCIDAS PARA
INICIALIZAR A TABELA, FINALIZÁ-LA, ARMAZENÁ-
LA OU RECUPERÁ-LA A PARTIR DE MÍDIAS
EXTERNAS. MAS, DE FORMA GERAL, AS FUNÇÕES
AQUI APRESENTADAS SÃO SUFICIENTES PARA
UMA LINGUAGEM DE PROGRAMAÇÃO SIMPLES.
CONSTRUÇÃO DE UMA TABELA DE SÍMBOLOS
Assista ao vídeo para saber mais sobre a Construção de uma tabela de símbolos.
VERIFICANDO O APRENDIZADO
1. A TABELA DE SÍMBOLOS ARMAZENA INFORMAÇÕES SOBRE VÁRIOS
ASPECTOS DA ANÁLISE DO PROGRAMA FONTE, COMO: DECLARAÇÕES DE
VARIÁVEIS, PARÂMETROS DE SUBPROGRAMAS, DECLARAÇÃO DE
PROCEDIMENTOS ETC.
PARA QUE POSSA FUNCIONAR ADEQUADAMENTE, ELA NECESSITA SER
ORGANIZADA DE FORMA EFICIENTE. QUANDO A TABELA É ORGANIZADA
COMO UMA ÁRVORE DE PESQUISA BALANCEADA, ESTÁ SENDO UTILIZADA A
TÉCNICA DE ORGANIZAÇÃO DENOMINADA:
A) Lista linear
B) Tabela hash
C) Árvore binária
D) Busca binária
E) Vetor
2. UMA DAS FORMAS DE ORGANIZAR A TABELA DE SÍMBOLOS É UTILIZAR
UMA TABELA HASH. NESSE TIPO DE ORGANIZAÇÃO, É UTILIZADA UMA
FÓRMULA QUE DETERMINA O ÍNDICE DA TABELA ONDE O SÍMBOLO SERÁ
ARMAZENADO.
CONSIDERE QUE A FÓRMULA DE HASHING SEJA O RESTO DA DIVISÃO
INTEIRA POR 11 (MOD 11) E QUE DOIS SÍMBOLOS A E B CORRESPONDENTES,
RESPECTIVAMENTE, AOS VALORES 33 E 48, DEVEM SER ALOCADOS.
SABENDO-SE QUE A TS POSSUI 11 SLOTS NUMERADOS DE 0 A 10, EM QUAIS
SLOTS SERIAM OS SÍMBOLOS ARMAZENADOS?
A) A e B slot 0
B) A e B slot 4
C) A slot 0 e B slot 4
D) A slot 4 e B slot 0
E) A slot 0 e B slot 10
GABARITO
1. A tabela de símbolos armazena informações sobre vários aspectos da análise do programa
fonte, como: Declarações de variáveis, parâmetros de subprogramas, declaração de
procedimentos etc.
Para que possa funcionar adequadamente, ela necessita ser organizada de forma eficiente.
Quando a tabela é organizada como uma árvore de pesquisa balanceada, está sendo utilizada
a técnica de organização denominada:
A alternativa "D " está correta.
A lista linear implica em organizar a tabela como uma lista de registro que deve ser percorrida
sequencialmente durante a busca. A tabela hash utiliza uma função para determinar o índice da
tabela onde o símbolo deve ser acessado. A árvore binária é a estrutura de dados que permite
realizar a busca binária na tabela de símbolos. Portanto, a resposta correta é a letra D.
2. Uma das formas de organizar a tabela de símbolos é utilizar uma tabela hash. Nesse tipo de
organização, é utilizada uma fórmula que determina o índice da tabela onde o símbolo será
armazenado.
Considere que a fórmula de hashing seja o resto da divisão inteira por 11 (mod 11) e que dois
símbolos A e B correspondentes, respectivamente, aos valores 33 e 48, devem ser alocados.
Sabendo-se que a TS possui 11 slots numerados de 0 a 10, em quais slots seriam os símbolos
armazenados?
A alternativa "C " está correta.
Para determinar o slot, devemos calcular o resto da divisão do valor do símbolo por 11.
No caso de A, temos 33 mod 11 cujo resultado é 0.
No caso de B, temos 48 mod 11 cujo resultado é 4.
Portanto, a alocação seria A – slot 0 e B slot 4.
MÓDULO 2
 Identificar as características das árvores de sintaxe e demais representações gráficas
intermediárias
ÁRVORE DE SINTAXE NO PROCESSO DE
COMPILAÇÃO
O processo de compilação é organizado como uma série de passos e, em cada um deles, é
derivado conhecimento a respeito do código-fonte. Cada passo precisa repassar o
conhecimento adquirido para o seguinte, necessitando, portanto, possuir uma representação
para esse conhecimento.
 EXEMPLO
A análise léxica gera a lista de tokens que é repassada para a análise sintática, que gera como
produto, normalmente, uma árvore sintática. Esta, por sua vez, é repassada para a análise
semântica, que produzirá algum tipo de representação do código visto que possa ser utilizada
pela etapa de síntese para gerar o código a ser executado.
A Figura 6 mostra exatamente esse ambiente:
Fonte: EnsineMe
 Figura 6 − Etapa de análise.
Fonte: EnsineMe
Embora na figura apareça apenas o produtoda análise semântica como sendo uma
representação intermediária (RI), tanto a lista de tokens como, principalmente, a árvore de
sintaxe correspondem à definição de RI.
Na realidade, um compilador possui uma série de RIs que ele utiliza no processo de tradução.
Todos os passos, com exceção do scanner − que acessa diretamente o programa-fonte −
trabalham a partir de algum tipo de representação intermediária gerada no anterior. Todos os
passos também geram algum tipo de RI, com a possível exceção do gerador de código ao final
da etapa de síntese.
As RIs necessitam de muita expressividade para registrar fatos importantes para a tradução e
que não aparecem no código-fonte, por exemplo: Endereços de variáveis, constantes etc. O uso
de tabelas, como a de símbolos, contribui para aumentar a expressividade das RIs.
DE MODO GERAL, AS REPRESENTAÇÕES
INTERMEDIÁRIAS PODEM SER DE DOIS TIPOS:
Gráficas
Codificam o conhecimento em um grafo ou em uma árvore, como uma árvore de sintaxe.

Lineares
Semelhantes a algum tipo de pseudocódigo para uma máquina abstrata. Por exemplo, o
Código ILOC que corresponde a uma linguagem de montagem para um processador abstrato.
A Figura 7 mostra esses dois tipos:
Fonte: COOPER e TORCZON, 2014
 Figura 7 − Representação gráfica e linear.
Fonte: COOPER e TORCZON, 2014
ÁRVORES DE SINTAXE
Esse é o tipo de representação gráfica mais comum de se observar. Elas podem ser de vários
subtipos, cada uma utilizada com finalidades diferentes, como as que podemos observar na
Figura 8, que correspondem à expressão int + int:
Fonte: EnsineMe
 Figura 8 − Árvores de derivação e sintática.
Fonte: EnsineMe
ÁRVORES DE DERIVAÇÃO
Nesse tipo de árvore de sintaxe, para uma gramática livre de contexto (GLC), cada nó é rotulado
por um símbolo da gramática, sendo que os símbolos terminais aparecem nas folhas e os não
terminais, nas raízes das subárvores. A sentença da gramática será obtida a partir dos
símbolos existentes nas folhas, lidos da esquerda para a direita.
Considere a seguinte gramática:
O símbolo inicial da gramática é E e as produções são:
E → E + T|T
T → T / F | F
F → int
A árvore de derivação para a sentença int + int / int seria a da Figura 9:
Fonte: EnsineMe
 Figura 9 − Árvore de derivação.
Fonte: EnsineMe
Observe que:
A raiz da árvore é o símbolo inicial da gramática.
Os filhos de um nó correspondem sempre a uma produção da gramática, por exemplo: Os
filhos da raiz E são E + T é uma das produções possíveis para o não terminal E.
Esse tipo de árvore é utilizado como RI durante a análise sintática e, também, nos sistemas de
gramática de atributos.
ÁRVORE SINTÁTICA
Também conhecida como árvore sintática abstrata ou AST (na sigla em inglês), ela se origina
de transformações realizadas na árvore de derivação, visando a fazer a sua simplificação,
retendo apenas os nós essenciais aos próximos passos da compilação. Esse tipo de árvore
combina muito bem com a tradução orientada a sintaxe, a principal técnica de análise
semântica.
Para a produção da árvore, seguimos duas regras básicas:
Para um operador, criar um nó com um filho para cada operando. Assim, 2 + 3 cria um nó
binário para + com os nós para 2 e 3 como filhos.
Para uma produção inútil, como Termo → Fator, reutiliza o resultado da ação Fator como
seu próprio resultado.
Considerando a árvore da Figura 9, a árvore sintática obtida por essas regras seria a da Figura
10:
Fonte: EnsineMe
 Figura 10 − Árvore sintática.
Fonte: EnsineMe
Podemos observar, então, que a ideia básica é eliminar todos os nós com símbolos não
terminais, mantendo apenas os nós com símbolos terminais.
ÁRVORE DE DERIVAÇÃO ANOTADA
Corresponde a uma árvore de derivação a qual são acrescentados atributos aos seus nós, de
forma a facilitar a análise semântica utilizando a gramática de atributos.
Por exemplo, considere a seguinte gramática de atributos, que realiza a soma de números e
apresenta o seu resultado:
S : =result
E : = E + E | T
T : = numero
Para a expressão 10 + 24, a árvore de derivação seria a da Figura 11:
Fonte: EnsineMe
 Figura 11 − Árvore de derivação.
Fonte: EnsineMe
A seguir, a associação das regras semânticas:
Regras
de
Regras
semânticas
Comentários
produção
S :=r
Resultado
(E.val)
r é um terminal que representa o resultado do cálculo
E := E + E
| T
E.val = E.val
+ E.val
E.val = T.val
Quando realizamos a soma de valores, há dependência
entre os termos, assim, a definição dirigida por sintaxe
associa um atributo a cada termo. Nesse caso, val
indica o tipo e está associado aos símbolos não
terminais
T := n T = n.lexval
n é um símbolo terminal e está associado a um atributo
sintetizado, pois, nesse caso, não há regra semântica
para o mesmo, já que o valor deverá ser fornecido pelo
léxico (lexval)
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Vamos lembrar alguns conceitos muito importantes:
LEXEMA
É o valor representado pelo padrão do token. Tomemos como exemplo “valor = 10”. Na análise
léxica desse comando, identificamos que:
“valor” é o lexema e o token é ID.
“10” é o lexema e o token é NUMERO.
ANALISADOR LÉXICO
Para integrar-se aos analisadores sintático e semântico, deverá, além de identificar o tipo do
token, adicionar na tabela de símbolos (TS) os atributos do token, por exemplo: Nome do token,
o lexema e o valor.
FUNÇÃO DO ANALISADOR LÉXICO
Fornecer o atributo sintetizado para os tokens, o qual será identificado pela notação lexval, e,
nesse exemplo, o símbolo terminal é o token NUMERO. lexval=10. e NUMERO.lexval = 24.
Para gerar a árvore anotada, percorremos a árvore de derivação e a cada nó aplicamos as
regras semânticas. Dessa forma, seria produzida a árvore anotada da Figura 12:
Fonte: EnsineMe
 Figura 12 − Árvore de derivação anotada.
Fonte: EnsineMe
PERCURSO EM ÁRVORE DE SINTAXE
Para se percorrer uma árvore de sintaxe, a estratégia mais comum é Depth First. Nessa
estratégia, o algoritmo básico é o seguinte:
Para cada filho m de n da esquerda para a direita, faça:
Como o algoritmo utiliza recursão, percorre-se primeiro todos os filhos de n, visitando-os, para
somente depois visitar n. Isso faz com que a raiz seja a última a ser visitada. Essa ordem de
percurso é particularmente importante na análise semântica, pois implica que as regras
semânticas serão aplicadas na ordem correta.
Depth_First (n: nodo)Depth_First (n: nodo)11
Depth_First(m);Depth_First(m); 
Visite(n);Visite(n);
11
22
Considerando a árvore da Figura 12, a ordem de visitação está estabelecida pelos números que
constam na Figura 13:
Fonte: EnsineMe
 Figura 13 − Árvore de derivação anotada.
Fonte: EnsineMe
PERCURSO EM ÁRVORE DE SINTAXE
Veja no vídeo o passo a passo de como ocorre o percurso em uma árvore sintática.
GRAFOS
Grafos são outro tipo de representação gráfica, normalmente operando a partir da alguma
árvore.
GRAFOS ACÍCLICOS DIRECIONADOS (DAG)
Fonte: EnsineMe
 Figura 14 − AST e DAG.
Fonte: EnsineMe
Embora a AST seja mais concisa do que uma árvore de derivação, ela ainda representa de
forma fidedigna o programa-fonte. Por exemplo, uma AST (figura 14A) para a expressão a * 2 +
a * 2 * b contém duas cópias da expressão a x 2. Um grafo acíclico direcionado realiza uma
diminuição da AST eliminando a expressão duplicada (figura 14B).
EM UMA DAG, UM NÓ PODE TER VÁRIOS PAIS E
OPERAÇÕES IGUAIS SÃO REUTILIZADAS.
Note que no exemplo da Figura 14 é compartilhada uma única cópia de a × 2. Ele codifica uma
dica explícita para avaliar a expressão. Se o valor de a não puder mudar entre os dois usos de a,
então o compilador deve gerar código para avaliar a * 2 uma vez e usar o resultado duas vezes.
Se o valor de a pode mudar, então o compilador não fará essa contração.
GRAFO DE DEPENDÊNCIA
Um grafo de dependência é construído a partir de uma árvore de derivação, e mostra a
dependência entre os atributos da árvore. Por exemplo, considere a seguinte gramática em
BNF:
<decl> ::= <tipo><listaVariaveis>
<tipo> ::= int | double
<listaVariaveis> ::= id , <listaVariaveis> | id
Vamos reescrever as produções utilizando a notação formal para deixar mais evidente a
definição dos atributos:
T → int | double
Onde a produção T nos leva aos símbolos terminais int ou double.
L → id , L | id
Onde “id” e “,” são símbolos terminais.
Vamos agora estabelecer as regras de atributos:
Regras de
produção
Regras
semânticas
Comentários
D → T L
L.tipo =
T.tipo
T → int
T.tipo =
inteiro Separamos em duas produções, pois cada tipo tem
um tratamento diferente.
T → double T.tipo = real
L → id , L
id.tipo =
L.tipo
O identificador (variável) deve ter o mesmo tipo da
lista de variáveis.
L → id
id.tipo =
L.tipo
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Finalmente, podemos ver na Figura 15 a árvore gerada para a expressão int a,b, e as setas em
azul mostram a dependência dos atributos.
 Figura 15 − Árvore de derivação anotada e grafo de dependência.
Fonte: EnsineMe
VERIFICANDO O APRENDIZADO
1. ÁRVORES DE DERIVAÇÃO SÃO UM DOS TIPOS DE REPRESENTAÇÃO
INTERMEDIÁRIA GRÁFICA. ELAS SE PRESTAM A AUXILIAR O ANALISADOR
SINTÁTICO EM SEU TRABALHO. A PARTIR DELAS, PODEM SER OBTIDAS
VÁRIAS OUTRAS REPRESENTAÇÕES GRÁFICAS, SEJA DIRETAMENTE OU A
PARTIR DE OUTRA ÁRVORE DELAS DERIVADAS. A REPRESENTAÇÃO GRÁFICA
QUE MOSTRA A RELAÇÃO ENTRE OS DIVERSOS ATRIBUTOS DOS SÍMBOLOS
DENOMINA-SE:
A) Árvore sintática
B) Árvore de derivação anotada
C) Grafo acíclico direcionado
D) Árvore léxica
E) Grafo de dependência
2. A ÁRVORE DE DERIVAÇÃO ANOTADA CORRESPONDE A UMA ÁRVORE DE
DERIVAÇÃO A CUJOS SÍMBOLOS FORAM ACRESCIDOS ATRIBUTOS QUE
FACILITAM A ANÁLISE SEMÂNTICA. ESSES ATRIBUTOS E SEUS VALORES
SÃO DETERMINADOS PELAS REGRAS SEMÂNTICAS ACRESCIDAS ÀS
GRAMÁTICAS DA LINGUAGEM-FONTE DO PROGRAMA. QUANTO ÀS REGRAS
SEMÂNTICAS E A DEFINIÇÃO DOS VALORES DOS ATRIBUTOS, PODEMOS
AFIRMAR QUE:
A) As regras semânticas determinam como serão computados os valores de todos os nós.
B) O valor dos símbolos das folhas da árvore é determinado pelo analisador léxico.
C) As regras sempre correspondem apenas aos símbolos terminais da gramática.
D) As regras são associadas ao lado esquerdo das produções.
E) As regras semânticas são computadas a partir do lado esquerdo das produções.
GABARITO
1. Árvores de derivação são um dos tipos de representação intermediária gráfica. Elas se
prestam a auxiliar o analisador sintático em seu trabalho. A partir delas, podem ser obtidas
várias outras representações gráficas, seja diretamente ou a partir de outra árvore delas
derivadas. A representação gráfica que mostra a relação entre os diversos atributos dos
símbolos denomina-se:
A alternativa "E " está correta.
O grafo de dependência deriva da árvore de derivação anotada e mostra a relação de
dependência entre os atributos dos diversos símbolos.
2. A árvore de derivação anotada corresponde a uma árvore de derivação a cujos símbolos
foram acrescidos atributos que facilitam a análise semântica. Esses atributos e seus valores
são determinados pelas regras semânticas acrescidas às gramáticas da linguagem-fonte do
programa. Quanto às regras semânticas e a definição dos valores dos atributos, podemos
afirmar que:
A alternativa "B " está correta.
As folhas de uma árvore de derivação anotada correspondem aos símbolos terminais da
gramática e representam a cadeia que está em análise. O único analisador que entra em
contato com o programa-fonte é o scanner, portanto somente ele pode determinar os valores
dos atributos dos símbolos terminais.
MÓDULO 3
 Analisar as principais técnicas utilizadas na análise semântica
ANÁLISE SEMÂNTICA
Um programa pode estar correto tanto do ponto de vista léxico quanto do sintático, mas,
mesmo assim, ainda possuir erros que impediriam o término da tradução.
Para poder detectar esse tipo de erro, o compilador realizará uma análise semântica que
envolve a verificação de cada comando em seu contexto de execução real, visando a verificar
os erros de tipo e de concordância.
 COMENTÁRIO
Apesar de academicamente a análise semântica ser vista como um passo de tradução
separada da análise sintática, normalmente elas são executadas de forma concomitante.
TRADUÇÃO DIRIGIDA POR SINTAXE
A TRADUÇÃO DIRIGIDA POR SINTAXE É UMA
TÉCNICA QUE PERMITE REALIZAR A ANÁLISE
SEMÂNTICA DE FORMA CONCOMITANTE COM A
ANÁLISE SINTÁTICA.
Para que isso ocorra, ações semânticas são associadas às produções da gramática, de forma
que, quando uma delas é utilizada − para derivação ou redução de uma forma sentencial −,
essas ações são executadas.
As ações semânticas podem gerar ou interpretar códigos, armazenar dados na tabela de
símbolos, emitir mensagens de erro, manipular as árvores de sintaxe, dentre outros. Durante
esse tipo de tradução é possível realizar a associação de variáveis aos símbolos da gramática,
sejam os terminais ou os não terminais, dotando-os, então, de atributos que podem armazenar
valores durante o processo de reconhecimento.
Quando uma regra de produção é usada, os símbolos gramaticais são alocados com os seus
atributos. Dessa forma, a árvore de derivação passa a ter em cada nó os atributos daquele
símbolo, caracterizando a árvore de derivação anotada, conforme visto no módulo anterior.
ESQUEMAS DE TRADUÇÃO
O esquema de tradução corresponde a uma extensão da gramática livre de contexto (GLC), que
realiza a associação de atributos aos símbolos gramaticais e ações semânticas às produções.
Eles se constituem em uma notação apropriada para especificar as operações semânticas que
o compilador deve executar de forma concomitante com a análise sintática.
 ATENÇÃO
Um atributo pode conter um valor número, uma string, um tipo de dado, um endereço de
memória, uma posição em um vetor etc. Já as ações semânticas podem envolver a avaliação
de um atributo, chamadas de subprogramas e outros.
Considere a seguinte gramática, por exemplo:
exp → exp + termo | exp - termo | termo
termo → termo * fator | termo div fator | fator
fator → ( exp ) | num
E as seguintes regras semânticas:
Produção Regra
exp→exp1+termo exp.val =exp1.val+termo.val
exp→exp2-termo exp.val =exp2.val-termo.val
exp→termo exp.val=termo.val
termo→termo1*fator termo.val=termo1.val*fator.val
termo→termo2 div fator termo.val=termo2.val/fator.val
termo→fator termo.val=fator.val
fator→(exp) fator.val=(exp.val)
fator→num fator.val=num.val
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Todos os símbolos possuem o atributo val, que corresponde ao valor do atributo, e quando
existem duas vezes o mesmo símbolo na regra de produção, é acrescentado um subscrito para
eliminar a ambiguidade. Além disso, as regras estabelecem como o valor de val deve ser
computado para cada símbolo não terminal, já que o valor dos símbolos terminais, que no caso
é apenas num, é definido pelo scanner durante a análise léxica.
Nem todo símbolo gramatical tem atributos.
Pode haver manipulação de mais de um atributo em uma mesma regra e para um mesmo
símbolo.
Pode não haver regras semânticas para uma regra sintática.
Os atributos são representados pela forma geral simbolo.atributo, para o símbolo x com
atributos valor e escopo, a representação seria x.valor e x.escopo.
As ações semânticas associadas às produções computam os valores dos atributos dos
símbolos. Por exemplo, para somar os atributos valores de duas variáveis e atribuí-las a x,
o que corresponde à expressão x:=a+b, a regra é x.valor :=a.valor + b.valor.
De forma mais detalhada:
A partir de uma sentença de entrada será construída a árvore de derivação.
As ações semânticas definirão os valores dos atributos dos símbolos não terminais, que se
encontram nos nós internos da árvore.
Todas as informações referentes à sentença de entrada estão contidas na lista de tokens que o
scanner gera e localizadas nas folhas da árvore de derivação. É por causa disso que os valores
dos símbolos terminaissão obtidos durante a análise léxica e armazenados na tabela de
símbolos.
 EXEMPLO
No caso de uma constante numérica, o scanner irá definir o lexema como sendo uma
ocorrência do token constante e o seu valor.
Denominamos decorar a árvore o ato de, durante a fase de parser, realizar a associação dos
símbolos aos seus atributos na árvore de derivação, transformando-a na árvore de derivação
anotada.
Três passos normalmente são seguidos durante a tradução:
1ª PASSO
Análise da cadeia de tokens e construção da árvore de derivação.
2º PASSO
Construção do grafo de dependência.
3º PASSO
Percurso no grafo de dependência para avaliação das regras semânticas associadas aos nós
da árvore.
Esse esquema acadêmico, se implementado como descrito, teria um custo computacional alto.
Dessa forma, esquemas práticos normalmente fazem todo o trabalho em uma única passagem,
sem precisar construir a árvore de derivação nem o grafo de dependência.
GRAMÁTICA DE ATRIBUTOS
Quando um esquema de tradução não produz efeitos colaterais, como imprimir algo ou
atualizar o valor de uma variável global, ele é chamado de gramática de atributos. Esta consiste
em uma gramática livre de contexto (GLC) aumentada por um conjunto de regras que
especificam computações, ou seja, regras que definem um valor ou atributo a partir do valor de
outros atributos.
As regras associam os atributos a um símbolo específico da gramática, dessa forma cada
símbolo em uma árvore de derivação, ou árvore sintática, é associado a uma determinada
ocorrência do atributo.
Gramáticas de atributos são definidas por uma tripla A = (G, V, F), onde:
javascript:void(0)
javascript:void(0)
javascript:void(0)
O método de trabalho consiste em:
O processamento ocorre normalmente com a análise sintática.
A cada símbolo não terminal da GLC associamos zero, um ou vários atributos.
A cada produção associamos as asserções ou predicados que correspondem às ações
semânticas a serem realizadas.
A partir das definições realiza-se a análise semântica, validando os valores dos atributos
associados aos símbolos correspondentes a uma entrada.
Se as asserções se mantêm verdadeiras, então a entrada é considerada semanticamente
correta.
TIPOS DE ATRIBUTOS
Segundo Cooper e Torczon (2014), existem dois tipos de atributos:
SINTETIZADOS
Atributo definido totalmente em termos dos atributos do nó, seus filhos e constantes.
HERDADOS
Atributo definido totalmente em termos dos atributos próprios do nó e daqueles de seus irmãos
ou seu pai na árvore de derivação (além de constantes).
A seguir, um exemplo lidando com esses tipos de atributos (baseado no existente em Cooper e
Torczon (2014)).
Considere a seguinte gramática que gera todos os números binários com sinais:
G = (T,NT,S,P)
Onde:
T = {+, -, 0, 1}
NT = {Number, Sign, List. Bit}
S = {Number}
Produções:
Number → Sign List
Sign → + | -
List → List Bit | Bit
Bit → 0 | 1
Atributos:
Símbolos Atributos
Number value
Sign negative
List position,value
Bit position,value
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Nesse caso, somente símbolos não terminais possuem atributos, para os terminais eles não
são necessários nessa gramática.
A Figura 16 mostra as regras de atribuição:
Fonte: COOPER e TORCZON, 2014.
 Figura 16 − Gramática de atributo para números binários com sinal.
Fonte: COOPER e TORCZON, 2014
A partir do nome, as regras acrescentam atributos aos nós da árvore de derivação. O atributo
que aparece em uma regra deve ser invocado cada vez que ocorre um nó desse tipo.
Portanto, cada regra especifica como computar o valor do atributo. Por exemplo: Considerando
a string -101 como entrada, a gramática geraria a árvore de derivação anotada e o grafo de
dependência da Figura 17, onde os atributos value e position estão com os nomes truncados.
Fonte: COOPER e TORCZON, 2014
 Figura 17 − Árvore atribuída para o número binário com sinal –101.
Fonte: COOPER e TORCZON, 2014
Ao se percorrer os nós, em Depth-First são aplicadas as regras semânticas, o que gera uma
entrada correspondente a list e position para cada nó list na árvore, e termina por colocar na
raiz correspondente a number o valor -5 (decimal de -101), que corresponde à entrada.
Os atributos definem implicitamente as suas dependências e, quando observado a partir de
toda a árvore, temos o grafo de dependências que aparece na Figura 17(b).
Existe um fluxo bidirecional, já que list.value recebe o valor de bit.value e vice-versa. Essa
situação aparece no grafo, pois temos setas indo de bit para list e de list para bit. A distinção
entre os tipos de atributos pode ser observada a partir dessas setas.
Se o fluxo da informação é de baixo para cima, uma regra que define um atributo para o lado
esquerdo estabelece o valor de um atributo sintetizado.
Já se o fluxo é de cima para baixo ou lateralmente, ele é herdado, ou seja, a regra que define um
atributo para o lado direito da produção cria um atributo herdado.
No nosso exemplo, os atributos value e negative são sintetizados, enquanto position é herdado.
Podemos resumir, então, que:
O valor dos atributos é computado durante a realização das ações semânticas, exceto os
atributos dos símbolos terminais que são definidos pelo scanner.
O valor de um atributo do símbolo A é dito sintetizado se ele for definido exclusivamente a
partir do valor dos atributos dos filhos de A na árvore de derivação.
O valor de um atributo do símbolo A é dito herdado se ele for definido a partir dos valores dos
atributos dos irmãos ou do pai de A.
TIPOS DE ESQUEMA DE TRADUÇÃO
ESQUEMAS S-ATRIBUÍDOS
Esse esquema de tradução trabalha apenas como atributos sintetizados, sendo implementados
através de extensões de analisadores ascendentes (bottom-up ou redutivos). Eles apresentam
suas regras à direita das produções.
Os atributos sintetizados podem ser avaliados durante o reconhecimento da cadeia pelo parser.
Para isso, o analisador sintático mantém os atributos associados aos símbolos em sua própria
pilha. Quando ocorre a redução, o valor dos do lado esquerdo da produção é computado a
partir dos atributos da pilha. Por exemplo, veja o esquema de tradução:
PRODUÇÃO REGRA
A → X Y Z ( A.a := f (X.x, Y.y, Z.z) )
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Quando XYZ estiver na pilha, momento em que ocorrerá a redução para A, também estarão na
pilha X.x, Y.y, Z.z. Dessa forma, A.a poderá ser computado.
A tabela a seguir mostra a pilha com duas colunas, uma para o símbolo em análise e outra para
o valor do atributo:
Pilha
Análise Atributo
Z z
Y y
X x
$
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
A ordem dos símbolos na pilha corresponde à ordem do valor de seu atributo com Z e z no
topo, Y e y em seguida etc. Se um símbolo não possui atributo, a coluna do valor fica vazia
naquela posição, como é o caso do $.
Esse esquema de tradução possui como desvantagem não poder trabalhar com atributos
herdados, não permitindo, portanto, passar adiante informação de pai para filho ou de irmão
para irmão.
ESQUEMA COM ATRIBUTOS HERDADOS
Considere a gramática a seguir e suas respectivas regras semânticas correspondentes a
determinar o tipo de cada identificador:
Nr Produções Regras semânticas
1 D → TL L.t := T.tipo
2 T → int T.tipo := inteiro
3 T →real T.tipo := real
4 L → id, L1
Adtipo(id.indice, L.t);
L1.t := L.t
5 L → id Adtipo(id.indice, L.t)
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
As regras semânticas estabelecem que:
O não terminal T possui um atributo sintetizado “tipo” cujo valor é estabelecido pelas regras 2 e
3 (inteiro ou real).
O valor de T.tipo é repassado pela produção 1 ao atributo herdado t do não terminal L.
A aplicação das demais regras repassa esse tipo para os nós abaixo da árvore de derivação,
onde existe o símbolo L no atributo herdado t.
As regras das produções 4 e 5 chamam a rotina adtipo(), quefaz a inclusão do tipo do
identificador na tabela de símbolos.
O terminal id possui o atributo índice, que aponta a entrada da tabela de símbolos
correspondente ao identificador.
A Figura 18 mostra uma árvore anotada para a sentença real a, b.
 Figura 18 − Árvore de derivação anotada.
Fonte: EnsineMe
ESQUEMAS DE TRADUÇÃO L-ATRIBUÍDOS
Um esquema de tradução é dito L-atribuído se cada atributo herdado depende somente:
Dos atributos à esquerda dele na produção.; ou

Dos atributos herdados do não terminal da produção.
 EXEMPLO
Na produção S →ABC, C somente pode depender de A de B ou dos herdados de S. Todo
esquema S-atribuído é L-atribuído, pois essa regra se aplica apenas a atributos herdados.
Esses esquemas são mais flexíveis que os S-atribuídos, pois permitem usar atributos herdados
e sintetizados, além de permitir a avaliação destes de forma simultânea à construção da árvore
de derivação.
ORDENAÇÃO DE AÇÕES SEMÂNTICAS
A ordem de execução das ações semânticas é importante, já que devemos assegurar que os
valores dos atributos já tenham sido computados quando as ações a ele se referiram. Quando
são usados somente atributos sintetizados, isso é conseguido colocando-se as ações
semânticas após o lado direito da produção.
Quando se usa atributos herdados e sintetizados, o procedimento deve ser o seguinte:
O atributo herdado associado ao símbolo direito da produção deve ser computado em
ação semântica localizada à esquerda daquele símbolo.
Uma ação semântica somente pode se referir a atributo sintetizado de símbolo que
apareça à esquerda dessa ação.
Cabe observar que esquemas L-atribuídos sempre atendem a essas condições.
TRATAMENTO DE ESCOPO ANINHADO
Normalmente, as linguagens de programação trabalham com o escopo de nome, ou seja, uma
determinada variável ou parâmetro que pode existir em um subprograma com o mesmo nome
de uma variável ou parâmetro de outro subprograma.
A Figura 19 mostra os escopos definidos para as variáveis a e b ao longo de um programa:
Fonte: EnsineMe, 2020
 Figura 19 − Escopo das variáveis a e b.
Fonte: EnsineMe, 2020
Nos blocos 1, 2 e 4 o valor de a é 1, enquanto no bloco 3 é 3. Já B no bloco 1 tem o valor 1, nos
blocos 2 e 3, o valor 2, e no bloco 4, o valor 4. Mas como controlar isso na análise semântica? A
forma mais simples é utilizar uma tabela de símbolos com escopo.
Para que isso seja viável, o parser deve mudar ligeiramente sua técnica. Toda vez que entra em
um novo escopo, ele deve criar uma tabela de símbolos para este, o que acaba por gerar um
feixe de tabelas interligadas em uma ordem que corresponde aos níveis dos alinhamentos
léxicos.
Considerando o programa de exemplo (Figura 19), seriam criadas as tabelas para B1, B2, B3 e
B4, encadeadas da forma como pode ser visto na Figura 20:
Fonte: EnsineMe, 2020
 Figura 20 − Tabelas de símbolos por escopo.
Fonte: EnsineMe, 2020
SISTEMAS DE TIPO
As linguagens de programação associam uma coleção de propriedades a cada valor de dados.
Essa coleção de propriedades é o que chamamos de tipo, que pode ser:
Um conjunto de valores.
Um conjunto de operações sobre esses valores.
Predefinidos para uma linguagem.
Definidos pelos programadores utilizando os recursos da linguagem.
Os sistemas de tipo criam um segundo vocabulário para descrever o comportamento dos
programas válidos, estendendo o alcance da análise para além das possibilidades do scanner e
do parser e que é utilizado basicamente para:
SEGURANÇA
EXPRESSIVIDADE
EFICIÊNCIA DE EXECUÇÃO
SEGURANÇA
Buscando minimizar a possibilidade de erros de execução do programa.
EXPRESSIVIDADE
Permite que seja especificado com mais precisão o comportamento do programa, por exemplo,
o uso da sobrecarga de operadores.
EFICIÊNCIA DE EXECUÇÃO
Ao agregar mais informações, a análise permite que o compilador gere códigos mais eficientes.
VERIFICAÇÃO DE TIPO
Para diminuir o overhead em tempo de execução, os compiladores normalmente fazem a
verificação de tipo em tempo de compilação a partir da análise do programa e da atribuição do
tipo a cada nome e a cada expressão. Além disso, é necessário verificá-los para garantir que
sejam utilizados em contexto onde sejam válidos.
Uma linguagem é denominada fortemente tipada se a verificação é realizada em todas as
operações, o que ocorre com a maioria das linguagens. Uma notável exceção a esse enfoque é
o C, pois o sistema pode ser facilmente desligado, podendo-se manipular diretamente os bytes
na memória.
Um sistema de tipo, para uma linguagem moderna, abrange quatro componentes
fundamentais:
UM CONJUNTO DE TIPOS BÁSICOS OU EMBUTIDOS
Abrangendo normalmente números, caracteres e lógicos, são admitidos diretamente pela
maioria dos processadores.
REGRAS PARA CONSTRUIR NOVOS TIPOS A PARTIR DOS
EXISTENTES
Permitem a criação de tipos estruturados como vetores e registros.
UM MÉTODO PARA DETERMINAR SE DOIS TIPOS SÃO
EQUIVALENTES OU COMPATÍVEIS
Permitem verificar se duas declarações distintas são equivalentes ou não, dessa forma deve
prover uma regra não ambígua para responder a essa pergunta para qualquer um dos tipos da
linguagem.
REGRAS PARA INFERIR O TIPO DE CADA EXPRESSÃO DA
LINGUAGEM-FONTE
Especificam para um determinado operador e tipo de operando o tipo do resultado, por
exemplo, a soma de dois inteiros gera um resultado inteiro.
Muitas linguagens também incluem, ainda, regras para a conversão implícita de valores de um
tipo para outro com base no contexto.
VERIFICAÇÃO ESTÁTICA DE TIPO
É realizada em tempo de compilação e deve reportar um erro se um tipo de operador for
aplicado a um operando incompatível. Por exemplo, o seguinte trecho em C:
Ele deve retornar um erro, já que b é do tipo float e não pode ser operado com % que se aplica
apenas a inteiros.
A verificação estática também pode envolver outros aspectos do código, como:
VERIFICAÇÃO DO FLUXO DE CONTROLE
VERIFICAÇÃO DE UNICIDADE
int f1(int a, float b)int f1(int a, float b) 
{{ 
 return a % b; return a % b; 
}}
11
22
33
44
VERIFICAÇÃO DO FLUXO DE CONTROLE
Os comandos que quebram um loop precisam ter algum lugar para transferir o controle. Por
exemplo, em C o comando break tem que aparecer dentro de pelo menos um for, while ou
switch.
VERIFICAÇÃO DE UNICIDADE
Determinadas linguagens como o Pascal exigem que um objeto deve ser definido exatamente
uma vez, como a declaração de uma variável em um determinado nível.
O sistema de tipo é aplicado não somente às variáveis, mas também às expressões e aos
procedimentos.
TIPAGEM DE EXPRESSÕES
As expressões possuem tipos que correspondem ao valor do resultado. Por exemplo, as
expressões aritméticas possuem tipo inteiro se ambos os operandos forem inteiros; um
operando real faz com que elas tenham o tipo real.
O verificador de tipos pode inserir casts (conversões de tipo) explícitos nos pontos em que
precisa usar conversão, para facilitar o trabalho do gerador de código.
TIPAGEM DE PROCEDIMENTOS
Como os procedimentos estão em um espaço de nomes separado das variáveis, seu contexto
de tipagem também é diferente.
A ideia é representar o tipo de um procedimento como combinação dos tipos de seus
parâmetros e do seu tipo de retorno. A verificação da chamada checa o número de parâmetros,
e o tipo de cada um versus o tipo dos argumentos. A verificação do corpo do procedimento põe
o tipo de cada parâmetro e da variável de retorno no ambiente de tipos de variáveis.
PRODUTO DA ANÁLISE SEMÂNTICA
Conforme visto, o produto da análise semântica é a representação do programa-fonte em
algum tipo de representação intermediária. No módulo anterior, vimos que estas podem ser
gráficas ou lineares. Normalmente, a análise semântica produz o seu resultado em algum tipo
de representação linear.
REPRESENTAÇÕES INTERMEDIÁRIAS LINEARES
Esse tipo de RI normalmente é composto por uma sequência de instruções que são executadas
na ordem em que aparecem ou em uma ordem coerente com a da execução sequencial. Esta
última deve ser estabelecidade forma extremamente clara nesse tipo de RI. As instruções
podem ter uma ou várias operações, que, nesse último caso, são executadas em paralelo.
As RI lineares utilizadas pelos compiladores se assemelham muito ao código assembly de um
processador abstrato. O embasamento por detrás do uso desse formato é que o código-fonte,
que é entrada para o compilador, está em formato linear, assim como o código de montagem
que ele gera.
O fluxo de controle, em esquemas lineares, compreende desvios condicionais, saltos e
mecanismos de repetição, sendo que eles delimitam os blocos básicos dessa RI linear.
Segundo Cooper e Torczon (2014), existem vários tipos de RIs lineares:
CÓDIGOS DE UM ENDEREÇO
Modelam o comportamento das máquinas acumuladoras e de pilha. Estes expõem o uso de
nomes implícitos, de modo que o compilador pode ajustar o código a esse uso. O código
resultante é bastante compacto.
CÓDIGOS DE DOIS ENDEREÇOS
Modelam uma máquina que tem operações destrutivas. Esses códigos caíram em desuso
quando as restrições de memória se tornaram menos importantes.
CÓDIGOS DE TRÊS ENDEREÇOS
Modelam uma máquina na qual a maioria das operações utiliza dois operandos e produz um
resultado. O surgimento de arquiteturas RISC nas décadas de 1980 e 1990 tornou esses
códigos populares, pois são semelhantes a uma máquina RISC simples.
A seguir, os dois tipos que ainda são muito usados.
CÓDIGO DE MÁQUINA DE PILHA
Esse formato de código de um endereço assume que existe uma pilha para os operandos. A
maioria das operações, nesse caso, retira seus operandos da pilha e coloca os resultados da
operação de volta na estrutura.
Nesse esquema, uma operação de soma de números inteiros retiraria dois elementos do topo
da pilha − por exemplo, os valores 32 e 57 −, realizaria a operação e colocaria no topo da pilha o
valor 89, que é o resultado da soma.
O uso da pilha exige a presença de algumas operações específicas como swap, que troca os
dois primeiros elementos do topo da pilha. Por exemplo, para a expressão a – 2 * b a RI linear
seria:
push 2
push b
multiply
push a
subtract
O código fica muito compacto, já que não é necessário manipular muitos nomes intermediários
de variáveis etc. Como desvantagem, porém, temos que o uso da pilha faz com que todos os
resultados e argumentos não fiquem armazenados, sendo transitórios, a menos que o código
os salve explicitamente na memória.
Esse tipo de RI é utilizado pelo Java, já que o bytecode é uma implementação desse conceito, o
que permite que sejam executados em um interpretador ou traduzidos para o código da
máquina alvo na compilação Just-In-Time.
Como o código gerado é pequeno, a sua distribuição é facilitada e gera um esquema que
permite portar o mesmo programa para outra máquina, bastando para isso criar o interpretador
daquela arquitetura.
 VOCÊ SABIA
O nome bytecode deriva do fato de os códigos de operação da linguagem possuírem o
tamanho de um byte ou menos.
CÓDIGO DE TRÊS ENDEREÇOS
Nas operações desse tipo de código, o formato básico é r ← x op y, onde temos um
operador(op), dois operandos (x e y) e um resultado (r). Alguns poucos comandos
necessitaram de menos argumentos, como realizar um salto ou um load. Por exemplo, o
código correspondente a x + y * 3 seria:
t1 ← y
t2 ← 3
t3 ← t1 * t2
t4 ← x
t5 ← t3 + t4
Esse tipo de código é muito interessante pelos seguintes motivos:
MOTIVO 1
É compacto − Como a maioria das operações é composta por três nomes e um operando,
estas normalmente correspondem a um ou dois bytes e os nomes normalmente exigem mais
um ou dois bytes, de forma que quatro bytes usualmente são suficientes para a representação
da instrução.
MOTIVO 2
Ao utilizar nomes diferentes para os operandos e o resultado, obtém-se liberdade na
reutilização desses mesmos nomes, sendo que nesse tipo de RI não existem operações
destrutivas.
MOTIVO 3
Como muitos processadores modernos implementam operações de três endereços, essa RI
modela bem as propriedades das linguagens de máquinas dessas CPUs.
Normalmente, a RI de três endereços possui operação de baixo nível como saltos, desvios e
operações de leitura e gravação na memória, bem como operações complexas que
encapsulam fluxo de controle. Ao representar diretamente essas operações complexas, torna
mais fácil analisar e otimizar o código gerado, já que as pode mover durante a otimização sem
se preocupar com o seu funcionamento interno.
CRIANDO UMA ÁRVORE DE DERIVAÇÃO
NOTADA
Assista ao vídeo para saber mais sobre a criação de uma árvore de derivação notada.
VERIFICANDO O APRENDIZADO
1. UM ESQUEMA DE TRADUÇÃO CORRESPONDE A UMA EXTENSÃO DA
GRAMÁTICA LIVRE DE CONTEXTO (GLC), QUE REALIZA A ASSOCIAÇÃO DE
ATRIBUTOS AOS SÍMBOLOS GRAMATICAIS E AÇÕES SEMÂNTICAS ÀS
PRODUÇÕES.
ESSES ESQUEMAS DISPONIBILIZAM UMA ANOTAÇÃO APROPRIADA PARA
ESPECIFICAR AS AÇÕES SEMÂNTICAS QUE O COMPILADOR DEVE EXECUTAR
DURANTE A ANÁLISE SINTÁTICA. O TIPO DE ESQUEMA DE TRADUÇÃO QUE
SOMENTE PODE TRABALHAR COM ATRIBUTOS SINTETIZADOS DENOMINA-
SE:
A) Gramática de atributos
B) Tradução dirigida por sintaxe
C) Esquemas L-atribuídos
D) Esquemas S-atribuídos
E) Esquemas S-atribuídos
2. EXISTEM DOIS TIPOS BÁSICOS DE RI: AS GRÁFICAS E AS LINEARES. O
ANALISADOR SEMÂNTICO POSSUI COMO PRODUTO UMA REPRESENTAÇÃO
INTERMEDIÁRIA LINEAR. VÁRIOS TIPOS DE REPRESENTAÇÃO PODEM SER
UTILIZADOS PARA ESSE PRODUTO, CADA UM POSSUINDO VANTAGENS E
DESVANTAGENS. DENTRE ESSAS REPRESENTAÇÕES, ALGUMAS POSSUEM
OPERAÇÕES DESTRUTIVAS. ANALISE AS OPÇÕES A SEGUIR E RESPONDA
QUAL DELAS SE ENQUADRA NA SITUAÇÃO DESCRITA ANTERIORMENTE:
A) Código de máquina de pilha
B) Código de um Endereço
C) Código de dois endereços
D) Código de três endereços
E) Tipagem de expressões
GABARITO
1. Um esquema de tradução corresponde a uma extensão da gramática livre de contexto
(GLC), que realiza a associação de atributos aos símbolos gramaticais e ações semânticas às
produções.
Esses esquemas disponibilizam uma anotação apropriada para especificar as ações
semânticas que o compilador deve executar durante a análise sintática. O tipo de esquema de
tradução que somente pode trabalhar com atributos sintetizados denomina-se:
A alternativa "D " está correta.
Esquemas S-atribuídos, por definição, somente permitem atributos sintetizados em seus
símbolos.
2. Existem dois tipos básicos de RI: As gráficas e as lineares. O analisador semântico possui
como produto uma representação intermediária linear. Vários tipos de representação podem
ser utilizados para esse produto, cada um possuindo vantagens e desvantagens. Dentre essas
representações, algumas possuem operações destrutivas. Analise as opções a seguir e
responda qual delas se enquadra na situação descrita anteriormente:
A alternativa "C " está correta.
Os códigos de pilha utilizam essa estrutura auxiliar para armazenar os operandos. Os códigos
de um endereço produzem um código compacto; os de dois endereços necessitam de ações
destrutivas para poder operar; e os de três endereços são similares ao funcionamento de uma
máquina RISC.
CONCLUSÃO
CONSIDERAÇÕES FINAIS
Neste tema, iniciamos os estudos pela tabela de símbolos, sua estrutura e como pode ser
manipulada.
A seguir, introduzimos o conceito de representações intermediárias, particularmente a árvore
de sintaxe em diversas de suas apresentações: Derivação, sintática e derivação anotada.
Vimos ainda os grafos que podem ser derivados das árvores de sintaxe, com particular
destaque para o grafo de dependência.
No último módulo, apresentamos as principais ferramentas da análise sintática, como a
tradução dirigida pela sintaxe e a gramática de atributos. Por fim, vimos como controlar o
escopo e apresentamos o sistema de tipos.
AVALIAÇÃO DO TEMA:
REFERÊNCIAS
AHO, A. et al. Compiladores: Princípios, técnicas e ferramentas. 2. ed. São Paulo: Pearson,
2008.
COOPER, K. D.; TORCZON, L. Construindo compiladores. 2. ed. Rio de Janeiro: Elsevier, 2014.
LOUDEN, K. C. Compiladores: Princípiose práticas. São Paulo: Cengage Learning, 2004.
SANTOS, P. R.; LANGLOIS, T. Compiladores: Da teoria à prática. Rio de Janeiro: LTC, 2018.
SEBESTA, R. W. Conceitos de linguagens de programação. 11. ed. Porto Alegre: Bookman,
2018.
TANENBAUM, A. S. Organização estruturada de computadores. 5. ed. São Paulo: Pearson,
2006.
EXPLORE+
Pra saber mais sobre os assuntos tratados neste tema, acesse:
A página do projeto GALS.
CONTEUDISTA
Sidney Nicolau Venturi Filho
 CURRÍCULO LATTES
javascript:void(0);