impressao (3)

Prévia do material em texto

COMPILADORES 
AULA 4 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prof. Frank Coelho de Alcantara 
 
 
2 
CONVERSA INICIAL 
Já estudamos os analisadores léxico e sintático – um é responsável pela 
verificação dos lexemas e criação dos tokens e, outro, pela verificação da 
estrutura da linguagem. Caberá ao analisador semântico, tema desta aula, 
verificar o sentido de cada uma das instruções do seu código. 
Os analisadores sintáticos são intimamente ligados à gramática utilizada 
para a definição da linguagem. Da mesma forma, veremos que os analisadores 
semânticos precisam de uma gramática estendida para tirar sentido de cada 
declaração do seu código. Ao contrário da gramática utilizada pelos analisadores 
sintáticos, no caso da análise semântica, o contexto no qual cada lexema está 
inserido é importante para a definição dos sentidos envolvidos em cada uma das 
declarações do seu código-fonte. Novamente faremos alguns paralelos com o 
estudo das linguagens naturais, como o português, para a definição dessas 
gramáticas estendidas ou especiais. 
Veremos tais gramáticas especiais, gramáticas de atributos, e como o tipo 
de dado que está sendo trabalhado é importante não só para o processo de 
compilação como também para o momento em que seu programa será 
executado. 
Estamos chegando ao fim do processo de compilação. O seu código, 
depois de passar pelo analisador semântico, estará pronto para ser convertido 
em linguagem de máquina. Essa é a última oportunidade de corrigir eventuais 
erros antes que o código seja executado. Caberá ao analisador semântico tentar 
corrigir todos os erros que forem possíveis e, quando não for possível, parar o 
processo e produzir os relatórios de erros que permitirão a correção do 
programa. 
Finalmente, estudaremos o tempo de execução. O conhecimento do que 
acontecerá com seu programa durante a execução é importante durante o 
processo de geração de código, passo final do processo de compilação. Da 
mesma forma, acaba definindo decisões que deverão ser tomadas pelo 
compilador durante a análise semântica. 
TEMA 1 – ANALISADORES SEMÂNTICOS 
O analisador sintático simplesmente verifica se a string composta de 
tokens criada pelo analisador léxico tem validade segundo as regras de produção 
 
 
3 
da gramática. Ele adota e monta uma árvore sintática. O analisador léxico 
simplesmente classifica os lexemas e cria os tokens. Assim, um número inteiro 
poder ser classificado na classe integer e ter como valor o próprio número, 
dependendo apenas da estrutura de classes escolhida pelos criadores da 
linguagem. Já o analisador sintático observa as regras de produção 
determinadas pela gramática escolhida e monta a árvore sintática de acordo com 
essas regras, validando apenas a estrutura do código-fonte. Nos dois casos, 
trabalhamos sem prestar atenção ao contexto. 
No analisador semântico, as duas estruturas de dados criadas pelos 
módulos anteriores, a tabela de símbolos e a árvore sintática, serão analisadas 
em profundidade em busca do sentido de cada string no seu código, na tentativa 
de descobrir se cada um dos comandos, definições e operações fazem sentido 
no conjunto de instruções da linguagem de programação. Para isso, 
precisaremos levar em consideração o contexto de cada comando. 
Vamos fazer um paralelo com a linguagem natural. Ainda que uma frase 
tenha o substantivo e o verbo colocados em uma estrutura correta, sem erros de 
concordância, com a conjugação correta, com o uso correto dos pronomes e 
adjetivos, pode não fazer nenhum sentido. Caberá ao analisador semântico fazer 
de forma automática a análise de cada string do seu código-fonte. 
Para que o seu código-fonte seja semanticamente válido, todas as 
variáveis, constantes, funções, classes etc. devem ser corretamente definidas e 
dispostas de acordo com o sistema de tipos usados na linguagem. 
Na estrutura clássica dos compiladores a análise semântica é a penúltima 
fase do processo de compilação. Imediatamente anterior à geração de código. 
Trata-se da última oportunidade de encontrar erros, corrigi-los ou reportá-los. O 
analisador semântico deve garantir que não há erros no seu código-fonte para 
que seu programa funcione corretamente, como pode ser visto na Figura 1. 
 
 
 
4 
Figura 1 – Diagrama em blocos de um compilador genérico sem destacar a 
tabela de símbolos 
 
Do ponto de vista de recursos e tempo, a maior parte do trabalho realizado 
pelos analisadores semânticos está na observação de construtores, como 
variáveis, funções, declaração de tipos e verificação de tipos. Sempre que uma 
nova declaração de variável, ou função, ou struct etc. é encontrada, o analisador 
semântico toma nota do tipo atribuído a esse identificador. Assim, irá, ao longo 
de toda a análise semântica, certificar-se de que não existem conflitos entre o 
tipo do identificador declarado e seu uso, verificando, por exemplo, se os tipos 
dos dois lados de uma declaração de atribuição são compatíveis. 
Cabe ao analisador semântico verificar se os argumentos utilizados na 
chamada de uma função coincidem em número e tipo com os parâmetros 
utilizados para a definição dessa mesma função. Na linguagem de programação 
C, cabe ainda verificar se o tipo retornado pela chamada da função coincide com 
o tipo do construtor que irá armazenar esse valor. Uma linguagem específica 
pode também requerer que os identificadores sejam únicos, consequentemente 
proibindo a declaração de dois identificadores com o mesmo nome, no mesmo 
escopo do código-fonte. Além disso, em muitas linguagens é importante verificar 
o tipo resultante de operações aritméticas para, quando possível, fazer sua 
correção automática. 
 
 
5 
Em alguns casos, a análise semântica pode ser realizada durante o 
processo de parser para a criação da árvore sintática. Nesse caso, quando uma 
estrutura particular é identificada, digamos, uma divisão aritmética, o analisador 
semântico pode observar os tipos dos dois operandos e verificar a 
compatibilidade entre eles. No caso de alguma diferença, pode ser possível 
corrigir esses tipos ou emitir um erro. 
Essa abordagem foi utilizada nos primeiros compiladores. Contudo, 
graças à necessidade de flexibilidade e da criação de uma estrutura modular, 
ambas impostas pelo mercado, a estrutura de compilação modular, como a que 
estamos estudando, acabou se tornando predominante. Mesmo sob a pressão 
do mercado que exige sistemas modulares e flexíveis, existem alguns 
compiladores, classificados como de “uma passagem”, que podem utilizar a 
análise semântica durante o parser, e que conseguem grande eficiência e 
velocidade. 
Até o momento, preocupamo-nos com a formação e com a estrutura do 
código e optamos por gramáticas livres de contexto para definir nossa linguagem 
a fim de facilitar o reconhecimento de padrões. Até vimos que, em alguns casos, 
o melhor par parser/gramática é aquele no qual a gramática é livre de contexto 
e restrita. Agora, precisamos identificar o contexto. Tomemos como exemplo 
apenas uma linha de código utilizando a linguagem de programação C: 
 
Essa linha será corretamente avaliada tanto pelo analisador léxico quanto 
pelo analisador sintático. Contudo, o analisador semântico irá gerar um erro, já 
que, em C, não é possível atribuir uma string a uma variável do tipo int. Além 
desse, a maior parte dos analisadores semânticos emite um conjunto de erros 
que inclui: 
 erros de tipos; 
 variáveis não declaradas; 
 uso incorreto de palavras-chaves; 
 declarações múltiplas em um mesmo escopo; 
 acesso a variáveis fora de escopo; 
 erros em parâmetros de funções. 
 
 
 
6 
Para que seja possível esse tipo de verificação, utilizamos uma gramática 
especial chamada de Gramática de Atribuição. 
Em gramáticas de atribuição, as informações extras, os atributos, são 
acrescentados aos símbolos não terminais da gramática livre de contexto. Esses 
atributossão parametrizados e servem para representar a estrutura sintática da 
linguagem, identificando as características semânticas de cada um. Nesse caso, 
uma das características mais importantes é o tipo. 
TEMA 2 – TIPOS DE DADOS 
Tipos ou, mais precisamente, tipos de dados são estruturas desenvolvidas 
para permitir um determinado nível de abstração sintática em programas. Os 
tipos permitem, por exemplo, que o computador saiba como processar uma 
operação aritmética de ponto flutuante, ou como verificar o espaço necessário 
para armazenar uma string. 
Interessa-nos entender como identificar esses tipos e retirar conteúdo 
semântico dessa informação. Desta forma, vamos nos referir à Linguagem C 
que, além de tipada, de ter tipos primitivos, complexos e compostos, ainda 
permite que o programador crie tipos novos. Vamos, portanto, começar com 
algumas definições importantes: 
 Tipos básicos ou primitivos: estão nessa classe os tipos 𝑖𝑛𝑡, 𝑓𝑙𝑜𝑎𝑡, 
𝑑𝑜𝑢𝑏𝑙𝑒, 𝑐ℎ𝑎𝑟, 𝑏𝑜𝑜𝑙 etc. Esses consistem nos tipos primitivos definidos pela 
linguagem de programação que são relacionados ao hardware da 
máquina. Esse conjunto varia de linguagem para linguagem e, em 
algumas linguagens, como o C, por exemplo, é possível definir algumas 
variantes desses tipos básicos, como os 𝑒𝑛𝑢𝑚𝑠. 
 Tipos compostos: são tipos que podem ser construídos em uma dada 
linguagem de programação utilizando a agregação dos tipos primitivos e, 
em alguns casos, outros tipos compostos. Estão nessa classe, entre 
outros: 𝑎𝑟𝑟𝑎𝑦𝑠, 𝑝𝑜𝑖𝑛𝑡𝑒𝑟𝑠, 𝑟𝑒𝑐𝑜𝑟𝑑𝑠, 𝑠𝑡𝑟𝑢𝑐𝑡𝑠, 𝑢𝑛𝑖𝑜𝑛𝑠, 𝑐𝑙𝑎𝑠𝑠𝑒𝑠. 
 Tipos complexos: são tipos de dados abstratos e algumas linguagens, 
como o C, por exemplo, que não têm suporte para esse nível de 
abstração. Estão nessa classe: 𝑙𝑖𝑠𝑡𝑠, 𝑠𝑡𝑎𝑐𝑘𝑠, 𝑞𝑢𝑒𝑢𝑒𝑠, 𝑡𝑟𝑒𝑒𝑠, ℎ𝑒𝑎𝑝𝑠, 𝑡𝑎𝑏𝑙𝑒𝑠 
etc. 
 
 
 
7 
Na maior parte das linguagens de programação, o programador começa 
escrevendo o tipo de um construtor qualquer, como uma variável ou função. Esse 
mecanismo caracteriza a declaração do tipo desse construtor e será, como vimos 
antes, anotada na árvore sintática. A declaração básica é constituída apenas de 
tipo e nome. Contudo, algumas linguagens de programação podem incluir 
modificadores para controlar a visibilidade da variável e seu uso, como o static, 
em C, e o private, em Java. Além disso, linguagens como o C, o Java e o C++ 
permitem que a variável seja inicializada durante a declaração. 
A declaração de funções, ou prototipagem, serve em relação ao mesmo 
objetivo para as funções. Os identificadores de funções e métodos também 
possuem um tipo e um identificador que o analisador semântico poderá utilizar 
para verificar se a definição e a chamada da função estão corretas, examinando 
o tipo de retorno, além do número, o tipo e a posição dos argumentos da função 
ou método. 
O local da declaração, tanto para variáveis quanto para funções, 
determina a visibilidade do construtor. Variáveis e funções podem ser globais ou 
locais, podem estar aninhadas em outras funções ou podem estar relacionadas 
a alguma classe. A Figura 2 mostra algumas declarações em C comentadas. 
Figura 2 – Exemplo de declarações em C 
 
Existem linguagens que permitem a criação de novos tipos. Na linguagem 
de programação C, isso é feito com a palavra-chave typedef. Ao encontrar tal 
tipo de declaração, o analisador semântico deverá acrescentar o novo tipo na 
tabela de símbolos e tratá-lo exatamente como qualquer outro tipo da linguagem. 
 
 
8 
Mas não acabou: as linguagens de programação ainda podem ser estática ou 
dinamicamente tipadas. 
Em uma linguagem estaticamente tipada, as variáveis terão seu tipo 
definido no código, ou em tempo de compilação, e durante a execução do 
programa só poderão receber valores que sejam do tipo definido. As informações 
necessárias para a verificação dos tipos são fornecidas durante a redação do 
código e anotadas na Tabela de Símbolos. As violações das regras de tipos são 
descobertas ainda em tempo de compilação e chamadas de type error. Contudo 
há um custo intrínseco ao processo de redação de código-fonte, já que os tipos 
das variáveis devem ser decididos antes do seu uso. São exemplos de 
linguagens estaticamente tipadas: C, C++, Java, C#, Haskell. 
Infelizmente, não é possível descobrir todos os erros de tipos durante o 
tempo de compilação. Tomemos por exemplo duas variáveis perfeitamente 
definidas: int a; int b;. Se tentarmos atribuir um valor real para essas variáveis, 
teremos um type error. Contudo, nada impede que, durante a execução, um valor 
inteiro, muito grande, seja computado e atribuído a essas variáveis. Nesse caso, 
teremos um erro chamado de Buffer Overflow – quando escrevemos um dado 
maior que o espaço de memória reservado para ele. De fato, um erro parecido 
com esse explodiu o foguete Arianne 5, na data de 4 de julho de 1996, em pleno 
ar. 
Figura 3 – Foguete Arianne 5 explodindo graças a um erro de tipos 
 
Fonte: Arnold, 2000. 
 Em linguagens dinamicamente tipadas, só os valores possuem tipos 
definidos. Uma variável pode ser associada a qualquer tipo desde que lhe seja 
atribuído um valor. Alguns compiladores são capazes de determinar que certas 
variáveis só podem ser associadas a um certo tipo de valor. Contudo, essa não 
é a regra. As violações de tipos são descobertas, via de regra, apenas em tempo 
de execução, quando o programa está rodando. Essa opção fornece um grau 
maior de liberdade ao programador, já que ele pode usar as variáveis da forma 
 
 
9 
que desejar. São exemplos de linguagens dinamicamente tipadas: Python, Ruby, 
Javascript, Lisp, Clojure. 
As linguagens de programação ainda podem ser rigidamente tipadas ou 
fracamente tipadas – em inglês, strong typed e weak typed. Esses, 
provavelmente, são os dois tipos de sistemas de tipos menos compreendidos. 
Podemos começar esclarecendo que não existe uma relação entre rígido e 
estático nem entre fraco e dinâmico. De fato, uma linguagem pode ser 
dinamicamente e rigidamente tipada como o Python e fraca e estaticamente 
tipada como o C. 
Tal classificação – rígido e fraco – refere-se à tendência de conversão de 
tipos de acordo com seu uso. Podemos classificar as linguagens Python, 
Common Lisp, Java e Ruby como sendo rigidamente tipadas, e as linguagens 
Javascript, PHP, Perl, C como fracamente tipadas. Tome como exemplo a 
seguinte expressão: "10" − 5. Em linguagens rigidamente tipadas, essa 
operação irá gerar um erro em tempo de compilação. A esse erro damos o nome 
de type error (erro de tipo). Já em linguagens fracamente tipadas a tendência de 
comportamento mais proeminente é que o "10" seja implicitamente convertido 
para o tipo inteiro, graças à existência do operador de subtração, além de não 
existir a geração de qualquer tipo de erro, e a expressão seja corretamente 
avaliada em tempo de execução. Há uma regra nunca escrita que pode facilitar 
a identificação da linguagem: se uma linguagem tem um operador lógico triplo 
(===, ! ==), então será uma linguagem fracamente tipada. Esse é o caso do 
Javascript. 
Em Javascript, os operadores === e !== existem apenas para garantir 
que a comparação lógica seja verdadeira se só e somente só ambos os lados do 
operador sejam do mesmo tipo. Por outro lado, existem os operadores == e ! =. 
Nesse caso, mesmo que os operandos sejam de tipos diferentes, será possível 
obter o resultado da comparação lógica, já que o analisador semântico tentará 
fazer a conversão implícita e automática dos tipos antes de comparar. Por 
problemas de eficiência durante a redação do código, e de segurança durante a 
execução do programa, as linguagens mais modernas estão tendendo ao 
sistema de tipos rígido. 
Finalmente é preciso ressaltar que muitos dos compiladores modernos 
possuem algum mecanismo para a correção dos erros de tipos mais simples. 
Chamamos esse processo decorreção implícita ou coerção. Em C, por exemplo, 
 
 
10 
isso acontece quando somamos um valor inteiro com um valor de ponto 
flutuante. Nesse caso, o compilador promove o número inteiro e resolve a 
operação corretamente. Todas as vezes que um erro de tipo é detectado no seu 
código, o compilador C irá tentar corrigir implicitamente esses tipos. Nem sempre 
isso é uma coisa boa. Em C++, por exemplo, devido à complexidade da 
linguagem, essa tentativa de correção pode aumentar muito o tempo da 
compilação. 
TEMA 3 – GRAMÁTICAS DE ATRIBUTOS 
A identificação dos atributos necessários à análise semântica requer o uso 
de uma variação das gramáticas livres de contexto: as gramáticas de atributos. 
Em alguns textos, as gramáticas de atributo são chamadas de gramáticas 
de atribuição. Trata-se de uma forma especial das gramáticas livre de contexto, 
em que algumas informações adicionais, os atributos, são anexadas a um ou 
mais símbolos não terminais. Essa atribuição tem o objetivo de fornecer 
informação que seja sensível ao contexto, e cada atributo deve ser bem definido, 
estando em um domínio de valores. Em resumo, podemos definir uma gramática 
de atributos como sendo uma gramática livre de contexto expandida com 
atributos, regras semânticas e condições. 
Essas gramáticas são uma forma de prover sentido semântico às 
gramáticas livres de contexto e ajudam a especificar a linguagem de 
programação, facilitando o processo de compilação. Veja, por exemplo, a 
seguinte regra de produção: 
𝑆 → 𝑆 + 𝑇 {𝑆. 𝑣𝑎𝑙𝑢𝑒 = 𝑆. 𝑣𝑎𝑙𝑢𝑒 + 𝑇. 𝑣𝑎𝑙𝑢𝑒} 
A parte da direita dessa regra de produção contém as regras semânticas 
que especificam como a gramática deverá ser interpretada. Aqui, os valores não 
terminais serão adicionados, e o resultado será atribuído ao não terminal 𝑆. Ou 
podemos observar o próximo exemplo, que já considera a definição de tipos, 
ainda que de forma simplificada. 
𝐷𝑒𝑐𝑙 → 𝑇𝑦𝑝𝑒 𝑉𝑎𝑟𝐿𝑖𝑠𝑡 {𝑉𝑎𝑟𝐿𝑖𝑠𝑡. 𝑡𝑦𝑝𝑒 ∶= 𝑇𝑦𝑝𝑒. 𝑡𝑦𝑝𝑒} 
𝑇𝑦𝑝𝑒 → 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 {Type. type ∶= int} 
𝑇𝑦𝑝𝑒 → 𝑓𝑙𝑜𝑎𝑡 {Type. type ∶= float} 
𝑉𝑎𝑟𝐿𝑖𝑠𝑡 → 𝑖𝑑|𝑉𝑎𝑟𝐿𝑖𝑠𝑡1 {VarList1. type ∶= VarList. type; id. type ∶= VarList. type} 
𝑉𝑎𝑟𝐿𝑖𝑠𝑡 → 𝑖𝑑 {id. type ∶= VarList. type} 
 
 
11 
 
Podemos classificar os atributos de acordo com a forma como seus 
valores são alocados: atributos sintetizados e atributos herdados. 
3.1 Atributos sintetizados 
São atributos cujos valores são atribuídos de acordo com os valores dos 
atributos dos seus filhos. Considere a regra de produção que usamos 
anteriormente: 
𝑆 → 𝑆 + 𝑇 {𝑆. 𝑣𝑎𝑙𝑢𝑒 = 𝑆. 𝑣𝑎𝑙𝑢𝑒 + 𝑇. 𝑣𝑎𝑙𝑢𝑒} 
O valor do nó 𝑆, pai, recebe seu valor devido aos valores dos seus filhos 
𝑆 𝑒 𝑇. Então dizemos que o atributo do símbolo não terminal, representado pelo 
nó 𝑆, é dito sintetizado. Os atributos sintetizados jamais obtêm seus valores de 
nós pais ou irmãos. A Figura 4 esquematiza essa classe de atributos para o nó 
verde, com os nós envolvidos destacados em vermelho: 
Figura 4 – Esquema de árvore destacando o esquema dos atributos sintetizados 
 
3.2 Atributos herdados 
Ao contrário dos atributos sintetizados, os atributos desta classe podem 
obter seus valores dos atributos dos nós pais e dos nós irmãos. Considere a 
seguinte regra de produção: 
𝑆 → 𝐴𝐵𝐶 
Nesse caso, 𝐴 poderá receber seus valores de 𝑆, 𝐵 e 𝐶. Da mesma forma, 
𝐵 pode receber valores de 𝐴, 𝑆 e 𝐶, e pode receber valores de 𝑆, 𝐴 e 𝐵. Sendo 
todos eles classificados como atributos herdados. A Figura 5 apresenta esse 
 
 
12 
esquema de atribuição para o nó verde – nós envolvidos destacados em 
vermelho: 
Figura 5 – Esquema de atributos herdados para o nó verde 
 
Nesse ponto talvez seja necessária uma pequena explicação sobre essa 
estrutura de dados árvore que estamos usando tão frequentemente. Uma árvore 
é uma estrutura de dados não linear e bidimensional com propriedades espaciais 
que admite operações como consulta, inserção, remoção etc. De modo geral, 
uma árvore terá as seguintes características: 
 Ao contrário das árvores naturais, a raiz está em cima, é o nó no topo da 
árvore. Esse é o primeiro nó da árvore e, dele descendem todos os outros. 
ATENÇÃO: na regra 𝑆 → 𝐴𝐵𝐶, o 𝑆 está recebendo seu valor dos seus 
filhos, sendo, consequentemente, um atributo sintetizado 
 Todos os nós no interior da árvore são chamados simplesmente de nó. 
Eles podem ter descendentes ou não. Se um nó interior não tiver 
descendentes, chamamos este nó de folha. Uma folha é um nó terminal 
da árvore. 
 Se um nó tem descendentes, dizemos que é um nó pai. Se um nó tem pai, 
então é um nó filho. Nós que estão no mesmo nível na árvore são nós 
irmãos. 
Além dessas características, as estruturas de dados árvores têm outras 
que não são relevantes para nosso estudo. Antes de prosseguirmos ainda são 
necessárias duas definições: 
 Expansão: processo que ocorre quando um símbolo não terminal é 
expandido em símbolos terminais graças a uma regra gramatical. 
 
 
13 
 Redução: processo que ocorre quando um símbolo terminal é reduzido 
ao seu símbolo não terminal correspondente graças a uma regra 
gramatical. 
As árvores sintáticas são varridas da esquerda para a direita e de cima 
para baixo. Sempre que uma redução ocorrer, devem ser aplicadas as regras 
semânticas da linguagem. Ao processo de aplicação dessas regras damos o 
nome de Ação. Para uma determinada regra de produção 𝑆 → 𝑋𝑌, as ações 
podem ter a forma: 
𝑆. 𝑣𝑎𝑙𝑢𝑒 → 𝑓(𝑋. 𝑣𝑎𝑙𝑢𝑒, 𝑌. 𝑣𝑎𝑙𝑢𝑒) para atributos sintetizados; 
𝑆. 𝑣𝑎𝑙𝑢𝑒 → 𝑓(𝑌. 𝑣𝑎𝑙𝑢𝑒, 𝑋. 𝑣𝑎𝑙𝑢𝑒) para atributos herdados. 
O resultado do processo de análise semântica é uma árvore sintática com 
todos os atributos necessários à geração de código. Não se esqueçam: o 
próximo módulo já é a geração de código. 
ATENÇÃO: saindo um pouco da formalidade, podemos armazenar os atributos 
na Tabela de Símbolos por meio de uma dupla simples. 
As operações de expansão e redução são realizadas por um método 
chamado de Translação Sintática Direta (TSD). Trata-se de um método para 
traduzir uma string em uma sequência de ações associando uma ação a cada 
uma das regras de produção da gramática que determina essa string. 
Se a translação direta, TSD, utiliza apenas atributos sintetizados, nós a 
chamaremos de STSD. Nesse caso, os atributos são avaliados utilizando um 
algoritmo de parser da classe Bottom-Up. O valor atribuído ao nó pai dependerá 
dos valores dos nós filhos. 
Um algoritmo de atribuição mais interessante é o LTSD. Nesse caso, o 
processo de atribuição utiliza tanto atributos sintetizados quanto atributos 
herdados, mas com a restrição de não utilizar atributos de nós irmãos que 
estejam à direita. No LTSD, um símbolo não terminal terá seus valores 
determinados a partir do seu pai, filhos e irmãos à esquerda (de onde vem o L 
na abreviação do nome do algoritmo – left, esquerda em inglês). Vamos voltar a 
uma regra de produção que vimos anteriormente: 
𝑆 → 𝐴𝐵𝐶 
 
 
14 
O símbolo 𝑆 poderá ter seus valores determinados por 𝐴, 𝐵 𝑒 𝐶. Nesse 
caso, teremos um atributo sintetizado. O símbolo 𝐴 só poderá ter valores 
relacionados ao valor de S. O símbolo 𝐵, apenas de 𝑆 e 𝐴 e, por fim, o símbolo 
𝐶 poderá ter valores oriundos de 𝑆, 𝐴 e 𝐵. Talvez a árvore torne as coisas mais 
claras. Veja a Figura 6. 
Figura 6 – Árvore para destacar a LTSD 
 
Nenhum símbolo não terminal pode receber valores dos irmãos à direita. 
Nesse caso, LTSD, os atributos são avaliados de baixo para cima e da esquerda 
para a direita. 
TEMA 4 – ERROS E RECUPERAÇÃO 
O analisador semântico é a última instância para detecção e geração de 
erros no processo de compilação. Cada um dos módulos anteriores teve sua 
oportunidade de verificar o código-fonte de ângulos diferentes, detectar e gerar 
erros. Por exemplo: o analisadorléxico pode gerar erros indicando que 
determinado identificador não atende às regras da linguagem, enquanto o 
analisador sintático é capaz de indicar o uso incorreto de uma palavra reservada, 
e o analisador semântico pode informar que determinado identificador está 
definido duas vezes no mesmo escopo. Esses erros dependem da linguagem, 
da estrutura léxica, da gramática e da atribuição de valores. Mas, depois do 
analisador semântico, teremos linguagem de máquina, e os erros encontrados 
serão em tempo de execução. Podemos encontrar os seguintes tipos de erro 
durante o processo de compilação: 
 léxicos: algum identificador cujo nome atribuído viola as regras da 
gramática; 
 sintáticos: falta de um ponto e vírgula ou de um parêntese; 
 semântico: tipos incompatíveis; 
 lógicos: o programa entra em um laço infinito. 
 
 
15 
Os erros lógicos são os mais difíceis de identificação em tempo de 
compilação. Apesar disso, existe um conjunto de estratégias que pode ser 
utilizado durante o processo de parser, seja na construção da árvore sintática ou 
na atribuição de valores a essa árvore para lidar com os erros encontrados: 
4.1 Modo pânico 
Quando o parser encontra um erro em qualquer lugar da string, ele ignora 
o resto da string até um marcador de fim, como um ponto e vírgula. Essa é a 
forma mais simples de lidar com erros e impede que o parser seja pego em um 
laço infinito. Tal técnica pode ser implementada em todos os três módulos de 
análise, mas requer definições precisas, ou seja, não permite nenhum tipo de 
ambiguidade na gramática, nem em forma (sintaxe) nem em significado 
(semântica). Do ponto de vista do analisador semântico, erros desse tipo são 
gerados quando encontramos problemas na resolução de escopo (variáveis e 
funções duplamente declaradas); na verificação de tipos; e na verificação dos 
limites de um 𝑎𝑟𝑟𝑎𝑦. 
O tratamento de erro em modo pânico é simples e efetivo, mas consome 
tempo do programador durante o desenvolvimento do código. Alguns ambientes 
de desenvolvimento, como o Visual Studio, utilizam esse tipo de avaliação 
durante a escrita do código, e o programador tem dicas visuais de possíveis 
problemas, evitando que o código seja compilado com erros óbvios. Para isso, 
ele mantém um conjunto de analisadores léxico, sintático e semântico rodando 
em tempo real. 
Em geral, os erros produzidos pelo analisador semântico estarão em uma 
das seguintes classes: 
 Type mismatch (um erro de tipos); 
 Undeclared variable (uma variável não declarada); 
 Reserved identifier misuse (uma palavra-chave com erro de digitação); 
 Multiple declaration of variable in a scope (duplicidade na declaração de 
variáveis); 
 Accessing an out of scope variable (chamada de variável fora do escopo); 
 Actual and formal parameter mismatch (erro nos parâmetros de funções); 
 
 
16 
4.2 Modo declaração 
Quando o parser encontra um erro, ele tenta medidas automáticas de 
correção de forma que o seu processo de varredura e análise possa continuar. 
Um caso clássico seria a substituição de uma vírgula por um ponto e vírgula. 
Esse é um procedimento delicado: um erro na correção pode colocar o parser 
em um laço infinito e inviabilizar o processo de compilação. 
 Produção de Erros: durante o processo de digitação, alguns erros são 
comuns e ocorrem com frequência. Tais erros podem ser considerados e 
o designer do analisador semântico pode criar gramáticas aumentadas 
especificamente para permitir sua correção ou uma indicação melhor do 
problema para o programador. 
 Correção Global: no analisador semântico, durante o ciclo de atribuição 
de valor, o parser considera o programa de forma global, como uma única 
entidade, e tenta entender o que o programa pretende fazer, além de 
tentar criar a árvore sintática aumentada correta mais próxima possível 
dessa funcionalidade. Nesse caso, as pesquisas estão caminhando na 
área da inteligência artificial. 
Considerando os ambientes de desenvolvimento modernos e os 
compiladores por eles utilizados, assim como as pesquisas mais recentes, a 
estratégia Modo Pânico ainda é a mais eficiente para garantir o seu código. A 
estratégia de fornecer dicas visuais sobre erros adotada no Visual Studio parece 
promissora. A grande vantagem é que você pode, ainda em tempo de redação 
de código, simular correções e oferecer a opção para o programador. Dessa 
forma, a possibilidade de que o sistema automático corrija seu código de forma 
errada diminui. Afinal, tudo o que queremos é que nossos programas rodem sem 
erros e sem explodir foguetes de bilhões de euros. 
TEMA 5 – AMBIENTE DE EXECUÇÃO 
A finalidade principal do analisador semântico é a de garantir que o código 
em linguagem de máquina que será gerado pelo nosso compilador não terá 
erros. Queremos, em última análise, que nosso programa, em tempo de 
execução, não contenha erros. Mas o que exatamente isso quer dizer? O que 
significa rodar um programa? 
 
 
17 
Já nos referimos aos tempos de redação, quando você está escrevendo 
o seu código, ao tempo de compilação, quando o seu código está sendo 
compilado, e, finalmente, temos o tempo de execução, quando o código já foi 
transformado em programa e o programa está sendo executado. Os programas 
em tempo de execução estão rodando em um ambiente de execução. Trata-se 
de um conjunto de estados da máquina-alvo que permite a execução do seu 
programa. Esse ambiente pode incluir bibliotecas de função, variáveis de 
ambiente e dispositivos físicos que fornecerão serviços e funcionalidades aos 
seus programas. Em alguns ambientes de execução, como o Windows, por 
exemplo, alguns serviços são empacotados no seu programa para facilitar sua 
execução em qualquer máquina, enquanto outros devem estar disponíveis. 
Esses serviços empacotados cuidam, por exemplo, da alocação de memória, 
para que seu programa possa ser executado. 
Um programa, esteja em linguagem de máquina ou em linguagem de alto 
nível, é apenas uma sequência de comandos e dados combinados e executados 
em ordem sequencial. Uma função, como a função 𝑚𝑎𝑖𝑛() da linguagem C, deve 
ter um começo e um fim e, como função, indica um desvio na ordem sequencial 
dos programas. Saber onde ela começa e onde termina é indispensável para 
que o programa continue a ser executado. 
A função 𝑚𝑎𝑖𝑛() é um caso especial. O seu ponto de entrada é definido 
por padrão e o seu ponto de saída será determinado pelo tamanho do seu 
código, mas, nos dois casos, esses pontos só interessam ao sistema 
operacional, já que será ele o responsável por executar essa função. De forma 
mais geral, todas as funções são apenas procedimentos específicos, 
representados por um bloco de código. Para que seja possível executar o 
procedimento e retornar ao fluxo normal do programa, esse procedimento deverá 
ser registrado. 
Chamamos de ativação a execução de qualquer procedimento ou função 
em execução. Um registro de ativação deverá conter toda a informação 
necessária para chamar o procedimento em qualquer lugar do código e, 
dependendo da linguagem utilizada no código fonte, terá informações diferentes, 
como, por exemplo, no Quadro 1: 
 
 
 
18 
Quadro 1 – Classes de dados armazenados no registro de ativação 
Tipo de 
armazenamento 
 
Valores temporários 
Para uso em rascunho ou cálculos temporários. 
Dados locais 
Para armazenar os dados que só terão uso no próprio 
procedimento. 
Estado da máquina 
Para armazenar os valores dos registradores, contador de 
programa etc. antes de chamar o procedimento. Este é o estado 
da máquina antes de que o procedimento seja executado. 
Parâmetros 
Para armazenar os parâmetros que serão utilizados pelo 
procedimento chamado. 
Valor de retorno 
Armazena o valor que será devolvido ao ponto onde o 
procedimento foi chamado. 
 
Sempre que um procedimento ou função é ativado, seu registro de 
ativação é armazenado em umaestrutura de dados do tipo pilha. Sempre que 
um procedimento é ativado, o fluxo principal é parado até que esse procedimento 
termine, mesmo que a ativação de um procedimento ocorra dentro de outro 
procedimento. Assim, a pilha que irá armazenar os registros de ativação deverá 
ser capaz de armazenar essa estrutura recursiva. Isso é necessário para que o 
fluxo de controle seja contínuo e para que, sempre que um procedimento seja 
ativado, o fluxo passe para o procedimento, mesmo que existam outros 
procedimentos aninhados, até que, finalmente, o fluxo retorne para o ponto onde 
ocorreu a primeira interrupção no fluxo principal. 
Para entender o conceito, veja o fragmento de código em C, apresentado 
na Figura 7. 
Figura 7 – Fragmento de código em C contendo chamadas de função 
 
 
 
 
19 
Trata-se de um código pequeno com quatro chamadas de funções, uma 
delas aninhada. A Figura 8 apresenta o fluxo de controle desse fragmento (fluxo 
principal do programa em azul, fluxo de ida para o procedimento em verde e fluxo 
de volta do procedimento em vermelho). Simplesmente com o objetivo de tornar 
a visualização mais clara, marcamos os pontos de desvio com um nó azul. 
Figura 8 – Ciclo de instruções mostrando o desvio das chamadas de função 
 
Para que essa estrutura de chamada seja eficiente, o ambiente de 
execução precisará gerenciar a memória de forma a atender os seguintes 
requerimentos: 
 Código: o código de máquina gerado durante a compilação ocupará um 
determinado espaço de memória. Esse espaço é determinado durante a 
compilação e, na maior parte dos sistemas operacionais, está gravado no 
cabeçalho do próprio arquivo executável; 
 Procedimentos: o código dos procedimentos ou funções é, na maior 
parte das vezes, estático, e foi definido em tempo de compilação. 
Contudo, as chamadas a esses procedimentos podem depender do uso 
do seu programa. O ambiente de execução deverá alocar espaço para 
uma pilha capaz de manter essa estrutura de chamada. 
 Variáveis: os tipos das variáveis são conhecidos em tempo de 
compilação, mas os valores que elas deverão armazenar só serão 
conhecidos em tempo de execução. 
A própria alocação de memória requer estratégias diferentes para 
encontrar o máximo de eficiência. A alocação estática, por exemplo, garante que 
 
 
20 
o código em linguagem de máquina seja atrelado a uma posição fixa de memória, 
e que essa posição não seja alterada durante a execução do programa. Se os 
limites e endereços forem conhecidos com antecedência, o pacote de execução 
não precisará conter informações para o processo. A alocação de memória 
estática é típica de sistemas dedicados e embarcados. Em grandes máquinas 
genéricas, rodando sistemas operacionais como o Linux e o Windows, ela é rara 
e quase inútil. 
Outra técnica interessante é a alocação de memória em pilha – em inglês, 
stack allocation – para as chamadas às funções. Trata-se de uma estrutura em 
pilha, obedecendo à regra last-in-first-out, que armazena todos os dados de 
chamada dos procedimentos que existem no seu programa. A própria regra last-
in-first-out resolve o problema das chamadas recursivas, ou aninhadas, de 
procedimentos. 
Por fim, temos a Heap Allocation. Como heap em inglês também se traduz 
por pilha, vamos utilizar esse termo para diferenciar este algoritmo do algoritmo 
de pilha, usado para registrar as chamadas de procedimentos, métodos ou 
funções. 
No caso do heap, as variáveis locais de um determinado procedimento 
serão alocadas em memória durante o tempo de execução. Não há previsão de 
endereços para as variáveis locais em tempo de execução. Tipicamente 
utilizamos essa técnica para reservar a memória necessária à execução de um 
procedimento sempre que for necessária para a execução de uma determinada 
função, e devolvê-la ao sistema operacional quando o procedimento não for mais 
necessário. 
Esse conjunto de estratégias – alocação estática, alocação em pilha e 
heap – define todo o processo de gestão de memória na maior parte dos 
sistemas modernos. A parte estática é fixa; seu tamanho será definido em tempo 
de compilação; se colocarmos esta parte nos endereços de memória mais 
baixos, tudo que sobrar de espaço de memória poderá ser usado para a 
alocação dinâmica, pilha e heap. 
Na área de memória dinamicamente alocada podemos usar uma 
estratégia diferente. Como em tempo de compilação não é possível saber nem 
o tamanho da pilha nem o tamanho do heap, podemos alocar o heap nos 
endereços mais altos da memória, arrumando as variáveis de cima para baixo. 
Assim, sempre que um procedimento for chamado, suas variáveis locais usarão 
 
 
21 
a parte superior da memória e, sempre que o procedimento terminar, esse 
espaço ficará livre, deixando uma área entre os endereços finais da memória 
estática e o topo da memória para que a pilha possa utilizar. 
A área estática e o heap são alocados nos extremos da memória; o 
espaço destinado à pilha começa depois da área estática. Assim, a pilha cresce 
em direção ao topo, enquanto o heap cresce em direção à base. 
FINALIZANDO 
O analisador semântico finaliza o processo de criação da árvore sintática 
aumentada que será utilizada para gerar o código fonte do nosso programa. 
Trata-se do último módulo antes da geração do código. A última oportunidade de 
verificação e de correção de erros. 
Vimos todo o processo chamado de Back-End para a compilação – 
analisadores léxico, sintático e semântico. Em cada ponto desse processo vimos 
as técnicas utilizadas para validação e estruturação do código e, nesta aula, 
vimos as estratégias de geração de erro. Destacamos a estratégia chamada de 
Modo Pânico por ser a mais prática e eficiente, ainda que custe um pouco mais 
de tempo em modo de redação. Vimos também outras estratégias que tentam 
automatizar esses processos de correção de erros. Infelizmente, ainda hoje 
alguns erros são muito difíceis de identificar. Alguns, como erros de lógica, são 
quase impossíveis. 
O estudo do analisador semântico mostrou como o uso de gramáticas 
livres de contexto é importante para a definição de linguagens de programação. 
Importante, mas não suficiente. Vimos a necessidade de aumentar a informação 
contida nessas árvores para incluir o contexto que, no analisador sintático, 
tivemos tanto cuidado em separar. Precisamos incluir essas informações para 
poder encontrar, por exemplo, identificadores duplamente definidos em um 
mesmo escopo, ou para conseguir identificar erros de tipos. Estes últimos, os 
tipos, vimos com muito cuidado, já que são artefatos de codificação 
indispensáveis ao entendimento do significado do código e terão grande impacto 
na alocação de memória. 
Por fim, já nos preparando para a fase de geração de código, fizemos uma 
análise do ambiente de execução. Mas não pare por aqui. A análise semântica 
é indispensável em outras áreas de tecnologia, como entendimento de 
comandos de voz ou interpretação de textos. Todos os conceitos que estudamos 
 
 
22 
aqui, do ponto de vista da compilação, tem uso nessas novas áreas que estão 
surgindo todos os dias. 
 
 
 
23 
 
REFERÊNCIAS 
AHO, A. V. et al. Compiladores: princípios, técnicas e ferramentas. 2. ed. 
Boston, MA, USA: Pearson Education Inc., 2007. 
ARNOLD, D. N. The Explosion of the Ariane 5. Math User Home Pages, 2000. 
Disponível em: <http://www-
users.math.umn.edu/~arnold/disasters/ariane.html>. Acesso em: 24 nov. 2017. 
BERGMANN, S. D. Compiler Design: Theory, Tools, and Examples. [S.l.]: 
Rowan University, 2010. 
HOLUB, A. I. Compiler design in C. Englewood Cliffs, NJ, USA: Prentice Hall 
Software Series, 1990. 
MOGENSEN, T. Æ. Basics of Compiler Design. Copenhagen: Department of 
Computer Science University of Copenhagen, 2010. 
PITTS, A. M. Regular Languages and Finite Automata for Part IA of the 
Computer Science Tripos. Cambridge University Computer Laboratory. 
Cambridge, p.58, 2013. 
RANGEL, J. L. INF1626 Informática, PUC-Rio. PUC RIO, 2013. Disponível em: 
<www.inf.puc-rio.br/~inf1626>. Acesso em: 24 nov. 2017. 
ZANDER, C. Languages (Finite State Machines). CSS 448/548 - Introduction 
to Compilers Fall 2012, 2012. Disponível em: 
<http://courses.washington.edu/css448/zander/Notes/langFSM.pdf>. Acesso 
em: 24 nov. 2017.