Slides de Aula I

Prévia do material em texto

Profa. Dra. Miryam de Moraes
UNIDADE I
Compiladores e
Computabilidade
 Compiladores são softwares que “desempenham como tarefa principal a conversão 
automática de programas-fonte (fornecidos como textos escritos em uma determinada 
linguagem de programação) em um texto equivalente cuja notação possa ser executada
no computador”.
 O objetivo desta disciplina é apresentar as técnicas empregadas na implementação dos 
compiladores das linguagens de programação, incluindo a análise léxica, a análise sintática, 
a tradução dirigida por sintaxe, tipos e verificação de tipos, a otimização de programa, a 
geração de código e os ambientes de execução.
Compiladores e computabilidade
 “Os modelos, a teoria e os algoritmos associados a um compilador podem ser aplicados a 
uma grande grama de problemas no projeto e desenvolvimento de software” (Aho, 2008).
 O estudante do curso de Ciência da Computação, ao se familiarizar com os princípios e 
técnicas de projeto de compiladores, prepara-se melhor para a tarefa de programar e 
aumenta sua capacidade de aprender novas linguagens de programação (Stanford online).
Por que estudar compiladores?
 Um interpretador é um programa que recebe como entrada um programa escrito em uma 
linguagem de programação e os dados fornecidos pelo usuário que devem ser processados 
segundo as operações especificadas no programa-fonte.
Interpretadores x compiladores
Fonte: Adaptados de: 
Aho et al. (2008, p. 2).
Interpretador
programa fonte
entrada
saída
Compilador
programa fonte
FIGURA 1.1 Um compilador.
programa objeto
Programa Objetoentrada saída
FIGURA 1.2 Executando o programa objeto.
 Compiladores são softwares que 
“desempenham como tarefa principal a 
conversão automática de programas-fonte 
(fornecidos como textos escritos em uma 
determinada linguagem de programação) em 
um texto equivalente cuja notação possa ser 
executada no computador” (José Neto, 2016).
Compiladores
Analisador Léxico
fluxo de caracteres
código da máquina alvo
fluxo de tokens
Analisador Sintático
árvore de sintaxe
Analisador Semântico
árvore de sintaxe
Gerador de Código Intermediário
representação intermediária
Otimizador de Código
Dependente da Máquina
representação intermediária
Gerador de Código
código da máquina alvo
Otimizador de Código
Independente de Máquina
Tabela de Símbolos
A análise léxica tem como principal funcionalidade ler o fluxo de caracteres que compõem o 
programa-fonte e os agrupa em sequências significativas, chamadas lexemas. Define-se 
lexema (Aho et al., 2007) como o par:
 O analisador léxico também deve reportar erros léxicos, tais como identificar o tamanho dos 
identificadores, detectar símbolos não pertinentes ao conjunto dos terminais da linguagem, 
detectar fim de arquivo inesperado etc.
Análise léxica
 Y é um lexema que corresponde ao token: . id significa identificador e o caractere 1 diz 
respeito à posição da tabela de símbolos que armazena os atributos deste identificador. 
Observe que a figura 2 exibe a tabela de símbolos. No caso dos identificadores, ela 
armazena o nome do identificador e seu tipo.
 = é um lexema ao qual corresponderá o token , simbolizando a atribuição. Este lexema 
não necessita de atributos.
 X é um lexema que corresponde ao token: . id significa identificador e o caractere 2 diz 
respeito à posição da tabela de símbolos que armazena os atributos deste identificador X.
 + é um lexema mapeado para o token .
 10 é um lexema mapeado para o token .
 ; é um lexema mapeado para o token 
Análise léxica
 O analisador sintático do compilador recebe como entrada os tokens e cria uma 
representação intermediária da sequência de tokens a partir de um conjunto de regras das 
estruturas sintáticas da linguagem, disponíveis no compilador. 
 Uma representação intermediária típica elaborada pelos compiladores é a árvore de sintaxe, 
que exibe a estrutura dos comandos em análise.
 O analisador também tem a função de identificar erros sintáticos, ou seja, informar se as 
estruturas sintáticas apresentam erros. 
 São estruturas sintáticas comandos (atribuição, condicionais, laços), declaração de variáveis, 
classes, funções, métodos etc.
 São exemplos de erros sintáticos como discordância na 
abertura e fechamento de delimitadores a saber: parênteses, 
colchetes e chaves, ausência de palavras-chave em um 
comando ou sua substituição por um identificador aceito na 
análise léxica etc.
Análise sintática
 Na análise semântica são realizadas verificações a fim de assegurar que os componentes do 
programa estejam agrupados corretamente, de acordo com a semântica da linguagem. 
 A análise semântica realiza tarefas como a verificação de concordância entre a declaração 
de tipos das variáveis, e o uso delas, bem como da concordância entre o número de 
parâmetros na declaração de um método de uma classe e o número de argumentos no uso 
do método por um objeto etc.
Análise semântica
 Conforme o próprio nome, são criados códigos em sua representação intermediária, a saber: 
códigos de três endereços, pilhas.
 Exemplo: Seja a expressão: id1 = id2 + id3 * inttofloat(60)
 Obtém-se o código de 3 endereços: t1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3
Geração de código intermediário
 A otimização de código é a fase em que são realizadas transformações sobre o código 
intermediário obtido, a fim de se produzir um programa-objeto melhor, caso tais 
transformações não tivessem sido efetuadas.
O código de 3 endereços citado anteriormente pode ser otimizado como se segue:
t2 = id3 * 60.0
id1 = id2 + t2
Otimização de código
 Uma vez que o código intermediário tenha sido otimizado, o código-objeto pode ser gerado. 
id1 = id2 + id3 * inttofloat(60)
LDF R2, id3
MULF R2, R2, #60.0
LDF R1, i
ADDF R1, R1, R2
STF id1, R1
Geração de código objeto
 Análise léxica: diz respeito à componente regular da Linguagem de Programação.
 Na análise léxica há que se especificar os tokens, o que se faz mediante o uso de 
expressões regulares. Na construção do analisador léxico são empregados os diagramas 
de transição (Aho et al., 2007).
 A análise sintática diz respeito à componente livre de contexto da Linguagem
de Programação.
 Como explica Sebesta (2003), para descrever a sintaxe das 
linguagens de programação empregam-se mecanismos 
frequentemente denominados gramáticas, mais precisamente 
gramáticas livres de contexto. Usam-se também dispositivos 
de reconhecimento que executam procedimentos de aceitação
pelos quais é testado se uma dada cadeia de símbolos a ele 
submetida está ou não em conformidade com a
linguagem formalizada. 
 Análise semântica diz respeito à componente dependente de 
contexto da Linguagem de Programação. Faz uso da 
Gramática de Atributos.
A formalização das linguagens de programação
Assinale a alternativa incorreta:
a) Compiladores são softwares que desempenham como tarefa principal a conversão 
automática de programas-fonte (fornecidos como textos escritos em uma determinada 
linguagem de programação) em um texto equivalente cuja notação possa ser executada
no computador.
b) Para descrever a sintaxe das linguagens de programação empregam-se mecanismos 
denominados gramáticas livres de contexto.
c) Análise semântica diz respeito à componente dependente de contexto da linguagem de 
programação. Faz uso da gramática dependente de contexto.
d) A otimização de código é a fase em que são realizadas 
transformações sobre o código intermediário obtido, a fim 
de se produzir um programa-objeto melhor.
e) A componente regular da linguagem de programação diz 
respeito ao léxico.
Interatividade
Assinale a alternativa incorreta:
a) Compiladores são softwares que desempenham como tarefa principal a conversão 
automática de programas-fonte (fornecidos como textos escritos em uma determinada 
linguagemde programação) em um texto equivalente cuja notação possa ser executada
no computador.
b) Para descrever a sintaxe das linguagens de programação empregam-se mecanismos 
denominados gramáticas livres de contexto.
c) Análise semântica diz respeito à componente dependente de contexto da linguagem de 
programação. Faz uso da gramática dependente de contexto.
d) A otimização de código é a fase em que são realizadas 
transformações sobre o código intermediário obtido, a fim 
de se produzir um programa-objeto melhor.
e) A componente regular da linguagem de programação diz 
respeito ao léxico.
Resposta
 O analisador léxico, também denominado scanner, tem como tarefa extrair do texto-fonte 
sequências de caracteres e classificá-las em tokens, a saber: números, palavras reservadas, 
constantes, identificadores, operadores, símbolos especiais etc. 
 Para ele, o programa-fonte é uma sequência de palavras de uma linguagem regular.
 O analisador léxico executa atividades que não são de análise, tais como: rejeitar sequências 
de brancos, separadores e comentários. 
 Ainda, são executadas funções como: conversão numérica, criação e manutenção da tabela 
de símbolos.
Formalismos de uma Linguagem Regular:
 Gramática Regular.
 Autômatos Finitos.
 Expressões Regulares.
Analise léxica
 Seja G = (V, , P, S) uma gramática e sejam A e B símbolos não terminais e  uma cadeia 
de *. 
G é uma gramática linear à direita, se todas as produções são da forma:
A  B ou A  .
G é uma gramática linear à esquerda, se todas as produções são da forma:
A  B ou A  .
Gramática regular: dispositivo gerador da linguagem regular
 Exemplo: considere-se a gramática G3 linear à direita.
G3 = (V, , P, S), em que: V = {S, X, Y, F}  = {a, b} S é o símbolo inicial.
P = { S  aX
X  bF
F  aY |
Y  bF}
É fácil constatar que esta gramática gera a seguinte linguagem:
 L(G3) = {ab, abab, ababab,abababab,...}
Gramática regular: dispositivo gerador da linguagem regular
 De fato, tem-se que, com: G3 = (V, , P, S), em que V = {S, X, Y, F}  = {a, b }
 P = { S  aX; X  bF; F  aY | ; Y  bF} , S símbolo inicial da gramática,
Tem-se:
 S  aX  abF  ab = ab
 S  aX  abF  abaY  ababF  abab = abab
 S  aX  abF  abaY  ababF  ababaY  abababF  ababab = ababab
 Uma vez que G3 é regular, a linguagem L(G3) é regular.
Gramática regular: dispositivo gerador da linguagem regular
 Os autômatos finitos são formalismos de aceitação das sentenças das linguagens regulares, 
ou seja, aceitam toda e qualquer cadeia pertencente à linguagem para a qual foram 
projetados e rejeitam todas as cadeias não pertencentes a ela. Eles podem ser 
determinísticos ou não determinísticos.
 Um autômato finito determinístico (AFD) ou simplesmente um autômato finito (AF) M é uma 
quíntupla: M = (Q, , g, q0, F), onde: Q é um conjunto finito de estados.
  é um alfabeto (finito e não vazio) de entrada;
 g é uma função de transição, g: Q    Q;
 q0 é o estado inicial, q0  Q;
 F é um conjunto de estados finais, F  Q pertencente à 
linguagem para a qual foram projetados e rejeitam todas as 
cadeias não pertencentes a ela.
Autômatos finitos
 Exemplo: sejam  = {x, y} e L uma linguagem definida sobre o alfabeto , tal que 
L = {  |  apresenta a subcadeia xyxy}
A representação algébrica para o autômato finito é:
 Q = {q0, q1, q2, q3, q4}  = {x, y} q0 é o estado inicial.
 g = {((q0,x), q1), {((q0,y), q0), ((q0,x), q1), ((q1,x), q1), ((q1,y), q2), ((q2,x), q3), ((q2,y), q0), 
((q3,x), q1), ((q3,y), q4), ((q4,x), q4), ((q4,y), q4)}
F = {q4}
Autômatos finitos: exemplo
q3q0 q2q1 q4
x y x y
y
x
y
x
y
x
Autômatos finitos: exemplo
x y x y x x y x y x
 
q0  q1
x y x y x x y x y x
 
q2 q3
x y x y x x y x y x
 
q4 q4
q3q0 q2q1 q4
x y x y
y
x
y
x
y
x
 A cadeia é processada até o último símbolo e o autômato assume um estado final. Trata-se 
da configuração de aceitação.
 Após o processamento do último símbolo da fita, o autômato finito assume um estado não 
final. O autômato para e a cadeia de entrada é rejeitada.
 A função de transição é indefinida para um símbolo da cadeia de entrada. O autômato para e 
a cadeia de entrada é rejeitada.
Autômatos finitos
 O conjunto vazio , que é uma linguagem vazia, é uma expressão regular.
 A cadeia vazia  é uma expressão regular e, portanto, a linguagem L = {} é regular.
 Qualquer símbolo x é uma expressão regular e, portanto, a linguagem L = {x} é regular.
Se r e s são expressões regulares e, consequentemente, as linguagens R e S são
regulares, então:
 (r | s) é uma expressão regular e a linguagem R  S é regular;
 (rs) é uma expressão regular e a linguagem RS = {xy | x  R e y  S} é regular;
 (r*) é uma expressão regular.
Exemplo: A expressão regular (ab)+ representa a linguagem: 
 L7 = {ab, abab, ababab,...}
Expressões regulares: uma alternativa para representar
linguagens regulares
Para especificar padrões regulares de busca ou de geração, surgiram variantes, tais como:
 s? indica que s é opcional. s? pode ser escrito como (s| ).
 s+ indica que s é repetido uma ou mais vezes. s+ pode ser escrito como ss*.
 [a-z] indica qualquer caractere nesse intervalo. [a-z] pode ser escrito como (a|b|...|z).
 [^x] indica qualquer caractere, exceto um. [^x] pode ser escrito como Σ – x.
Expressões regulares
 Diz-se que tokens são as unidades básicas do texto do programa ou ainda correspondem 
a símbolos abstratos que representam um tipo de unidade léxica, por exemplo, um 
identificador, um número, uma palavra reservada, um operador etc. Por outro lado, um 
lexema é uma sequência de caracteres no programa-fonte segundo um padrão de token 
ou, em outras palavras, um lexema é uma instância de token. 
 As classes de tokens, na maioria das linguagens, são: palavras reservadas, identificadores, 
constantes numéricas, cadeias de caracteres, operadores e separadores.
 Às classes dos tokens são atribuídos valor e local de sua 
ocorrência no texto. É válido observarmos que há tokens que 
não têm valor associado, por exemplo, palavras reservadas, 
operadores e delimitadores. Eles exibem padrões que podem 
ser especificados por expressões regulares que se 
apresentam nas definições regulares.
Tokens
 digito  [0-9]
 digitos  digit+
 numero  digitos(.digitos)?(E[+-+)dígitos)?
 Letra  [A-Za-z]
 id  letra(letra|digito)*
 if  if
 then  then
 else  else
 relop  | = | = | 
 Essa especificação define como tokens as palavras 
reservadas if, then, else, numero, relop, id. Os lexemas são as 
palavras if, then, else e aquelas sequências de caracteres que 
combinam com os padrões de numero, relop e id.
Definições regulares
relop  | = | = | 
Diagramas de transição para operadores relacionais
início 
*
=
5 return ( relop, EQ )
7 return ( relop, GE )
8 return ( relop, GT )
*
=>
other
6
FIGURA 3.13 Diagrama de transição para relop.
other
Diagramas de transição 
Diagrama de transição para 
identificadores e palavras-chave
Diagrama de transição 
para números sem sinal
Diagrama de transição para 
espaços em branco
início letter other
9 10 11 return (getToken), install) ())
*
letter or digit
Fonte: Adaptado de: Aho et al. (2008, p. 84).
Fonte: Adaptado de: Aho et al. (2008, p. 85).
Fonte: Adaptado de: Aho et al. (2008, p. 85).
início delim other
22 23 24
*
delim
início digit
12 13
digit
. digit E
14 15 16
digit
+ or – digit other
17 18 19
*
digit
2120
E
* *
digit
otherother
 A sequência de tokens identificados é então passada para a próxima fase do processo de 
compilação, a análise sintática, em que a estrutura gramatical do programa é verificada. Em 
geral, o analisador léxico é implementado como uma sub-rotina invocada pelo
analisador sintático.
Tokens
Analisador
Léxicoprograma
fonte
para análise
semântica
token
Analisador
Sintático
Tabela de
Símbolos
getNextToken
Assinale a alternativa que não diz respeito à análise léxica:
a) Expressões regulares.
b) Autômatos finitos.
c) Diagramas de transição. 
d) Gramáticas regulares.
e) Árvore de sintaxe.
Interatividade
Assinale a alternativa que não diz respeito à análise léxica:
a) Expressões regulares.
b) Autômatos finitos.
c) Diagramas de transição.
d) Gramáticas regulares.
e) Árvore de sintaxe.
Resposta
 A análise sintática examina a sequência com que os lexemas do texto-fonte estão 
organizados segundo sua forma e estrutura. Assim, o analisador sintático, a partir dos 
lexemas obtidos na análise léxica, verifica a ordem em que se encontram e identifica o tipo 
da construção sintática.
 A especificação das estruturas sintáticas de uma linguagem de programação se efetua a 
partir de uma gramática livre de contexto.
 O analisador sintático efetua a derivação do código-fonte e, 
ao longo do processo de tradução, cria uma representação 
intermediária denominada árvore de sintaxe, que é uma forma 
condensada da árvore de derivação.
Análise sintática
Seja G = (V, , P, S). Diz-se que G é uma gramática livre de contexto (GLC) se as produções 
apresentarem o seguinte padrão:
A  , em que: A V e  (V  T) *.
Exemplo: é conhecido o duplo balanceamento dos símbolos “(“ e ”)” nas expressões lógico-
aritméticas das linguagens de programação, bem como o duplo balanceamento dos símbolos 
“{“ e ”}” na estruturação de blocos de comandos. Considere a seguinte linguagem L com duplo 
balanceamento definida a partir do alfabeto :
 = {a, b} e L = { |  =an bn, n ≥ 0}
Gramática livre de contexto
  = {a, b} e L = { |  = an bn, n ≥ 0}
A gramática G, geradora, é:
 G = (V, , P, S) = ({S}, {a,b}, P, S)
 P = {S  aSb | }
 S  
 S  aSb  ab = ab
 S  aSb  aaSbb  = aabb = aabb
 S  aSb  aaSbb  aaaSbbb  aaabbb = aaabbb
Gramática livre de contexto
Exemplo: seja a gramática G = ({S, B}, {a, b}, P, S), onde:
 P = {S  aB | aSB; B b}.
A derivação para a cadeia aabb é:
 S aSBaaBB aabBaabb
Árvore de derivação 
S
S
Ba
S
S
Ba
Ba
S
S
Ba
Ba
bb
 Segundo Aho et al. (2008), existem três estratégias gerais de análise sintática para o 
processamento de gramáticas: universal, descendente e ascendente.
 Os métodos de análise universal podem analisar qualquer gramática, no entanto, são muito 
ineficientes. São exemplos desses algoritmos o algoritmo de Cocke-Younger-Kasami e o 
algoritmo de Earley.
 Os compiladores em geral empregam, em vez dos métodos universais, aqueles conhecidos 
como determinísticos ascendentes e determinísticos descendentes.
Estratégias de análise sintática
 Nem todas as linguagens livres de contexto permitem a construção de analisadores 
determinísticos e entre as que o fazem nem todas podem ser tratadas por meio de
técnicas descendentes.
 O subconjunto das GLC que permite a construção de reconhecedores determinísticos 
descendentes é denominado LL(k). São assim nomeadas porque o código-fonte é analisado 
da esquerda para a direita (left-to-right) e as regras da produção ao longo da derivação são 
aplicadas de tal forma que o lado esquerdo da produção é substituído pelo lado direito da 
produção (leftmost derivation).
Exemplo: seja a gramática G7 = ({E, E’, T, T’, F}, {x, +, *}, P, E), 
em que:
 P = {E  TE’; E’  +TE’ | ; T  FT’; T’ *FT’ |  ; F x}
Análise sintática descendente
Exemplo: seja a gramática G7 = ({E, E’, T, T’, F}, {x, +, *}, P, E), em que:
P = {E  TE’; E’  +TE’ | ; T  FT’; T’ *FT’ |  ; F x}
G7 é LL(1), visto que pode ser analisada considerando apenas um não terminal e o próximo 
token no fluxo de entrada. Observe-se a derivação e a árvore de derivação da sentença
x + x * x:
E  TE’  FT’E’  xT’E’  xE’  xE’ x +TE’ x +FT’E’ x +xT’E’ 
x +x*FT’E’ x +x*xT’E’ x +x*xE’ x +x*xE’ 
x +x*x x +x*x
Os analisadores sintáticos preditivos tabulares fazem uso de uma pilha explícita para 
representar o conjunto de símbolos não terminais, bem como de uma tabela de análise, além 
de uma fita de entrada, conforme ilustra a figura a seguir:
Análise preditiva tabular
a+b$
Analisador Preditivo
Tabela de Análise
X
Y
...
$
Saída
Definição: conjuntos First seja  qualquer sequência de símbolos – terminais ou não terminais. 
First() é o conjunto de todos os símbolos terminais que começam qualquer sequência 
derivável de . Assim, First() é calculado a partir das seguintes regras: 
 se ⇒* a  então a ∈ First(), em que a é um símbolo terminal e  uma forma sentencial 
qualquer, podendo ser vazia.
se  ⇒* ε então ε ∈ First(). Tem-se que:
 Se a é terminal, então First(a) = {a}
 Se X é uma produção, então adicione ε a First(X)
 Se XY1Y2...Yk, é uma produção e, para algum i, todos 
Y1Y2...Yi-1 derivam ε, então First(Yi) está em First(X), 
juntamente como todos os símbolos não- de First(Y1), 
First(Y2),... First(Yi-1). O símbolo ε será adicionado a First(X) 
apenas se todo Yj (j=1, 2, ..., k) derivar .
Análise preditiva tabular
Exemplo: considere a gramática G = ({E, E’, T, T’, F}, {+, *, id},P, E), em que:
 P = {E  TE’ ; E’+TE’ | ; T  FT’; T’  *FT’|  ; F id}
Aplicando-se o algoritmo, tem-se:
 First(E) = First(T) = First(F) = {id}
 First(E’) = {+, } First(T’)= {*, }
Análise preditiva tabular
O algoritmo para calcular Follow(X) é aduzido seguidamente:
1. Se S é o símbolo inicial da gramática e $ é o marcador de fim de sentença, então $ está em 
Follow(S).
2. Se existe produção do tipo AX, então todos os símbolos de First(), exceto a palavra 
vazia , fazem parte de Follow(X).
3. Se existe produção do tipo A  X, ou AX, sendo que *, então todos os símbolos 
que estiverem em Follow(A) fazem parte de Follow(X).
Análise preditiva tabular
Para o cálculo da função Follow, tem-se:
 Follow(E)={$}, pela regra 1. Follow(T) First(E’), portanto, Follow(T) = {+} pela regra 2.
 Follow(F)  First(T’), portanto, Follow(F) = {*} pela regra 2.
 Deve-se prosseguir pela regra 3 para as produções da forma A  X.
 Follow(E’)  Follow(E), portanto, Follow(E’)= {$} pela regra 3.
 Follow(T’)  Follow(T), portanto, Follow(T’)= {+} pela regra 3.
 Deve-se prosseguir com a regra 3 para as produções AX, sendo que *
 Follow(T)  Follow(E’). Portanto, Follow(T) = {+,$}.
 Follow(T) foi alterado e, portanto, Follow(T’)={+,$}.
Análise preditiva tabular 
Ainda: Follow(F)  Follow(T’). Portanto, Follow(F)= {*,+,$}. Em resumo:
 Follow(E)={$} Follow(E’)= {$} Follow(T) = {+,$} Follow(T’) ={+,$}
 Follow(F)= {*,+, $}
Análise preditiva tabular
id + * $
E E  TE’
E’ E’+TE’ E’ 
T T  FT’
T’ T’   T’  *FT’ T’  
F F id 
id+id*id$
Passos de um analisador preditivo tabular
Pilha Entrada Derivação
$E id+id*id$ ETE’
$E’T id+id*id$ TFT’
$E’T’F id+id*id Fid
$E’T’id id+id*id$
$E’T’ +id*id$ T’
$E’ +id*id$ E’+TE’
$E’T+ +id*id$
$E’T id*id$ TFT’
$T’F id*id$ Fid
$T’id Id*id$
$T’ *id$ T’*FT’
$T’F* *id$
$T’F id$ Fid
$T’id id$
$T’ $ T’
$ $ Aceitação da cadeia de entrada.
 As colunas referentes às ações são associadas aos símbolos terminais da gramática 
passíveis de serem encontrados na cadeia de entrada. Uma coluna adicional diz respeito ao 
símbolo indicador de fim de cadeia de entrada ($). Assim, para cada par (estado, símbolo 
terminal da cadeia de entrada), corresponde uma possível ação ora de empilhamento, ora de 
aplicação de regra. Portanto, o processo da análise se faz mediante o empilhamento dos 
símbolos da cadeia de entrada.
 A ação de empilhamento é indicada pelo símbolo ej, em que j é um número inteiro que indica 
qual estado deve ser empilhado com o símbolo da cadeia de entrada recém-lido. Pela ação 
de empilhamento, o símbolo terminal da entrada é inserido na pilha, sucedido pelo
estado indicado.
Análise ascendente
Algoritmo de Análise
X
Y
...$
Saída
a ... b ... c $
Ação Transição
Seja a gramática G = ({E, E’, T, T’, F}, {+, *, id},P, E), onde:
P = { E  TE’ ; E’  +TE’ | ; T  FT’; T’  *FT’|  ; F  id }. Assinale a alternativa correta:
a) Follow(E) = {$};
b) Follow(T) = {$};
c) Follow(T’) = {$};
d) Follow(F) = {$,*};
e) Follow(F) = {$};
Interatividade
Seja a gramática G = ({E, E’, T, T’, F}, {+, *, id},P, E), onde:
P = { E  TE’ ; E’  +TE’ | ; T  FT’; T’  *FT’|  ; F  id }. Assinale a alternativa correta:
a) Follow(E) = {$};
b) Follow(T) = {$};
c) Follow(T’) = {$};
d) Follow(F) = {$,*};
e) Follow(F) = {$};
Resposta
“A palavra semântica deveria referir-se ao exato significado com que o compilador deveria 
interpretar a sentença em análise no contexto em que ela foi encontrada no programa-fonte”. 
Assim sendo, a análise semântica diz respeito ao processamento de dependências de 
contexto. José Neto (1993) também elenca:
 delimitação de escopos para os identificadores, a fim de garantir que cada identificador seja 
utilizado estritamente em regiões do programa determinadas pelas regras de escopo 
impostas pela linguagem;
 possíveis múltiplas interpretações de um mesmo símbolo, que pode ser interpretado 
diferentemente conforme o ponto do programa em que for utilizado.
 Garantia de que identificadores previamente declarados sejam 
coerentemente utilizados. Assim, a associação de atributos 
aos identificadores na declaração dos identificadores exige 
que se verifique a coerência de sua utilização nos comandos 
que os referenciam.
Análise semântica
 A componente dependente de contexto de uma linguagem de programação exige que antes 
de sua substituição se realize um teste para verificar a aplicabilidade da regra de substituição 
em cada caso particular. Em outras palavras, as dependências de contexto não podem ser 
descritas por formalismos livres de contexto.
 Um formalismo capaz de efetuar associações entre objetos da linguagem e os seus atributos 
declarados é a gramática de atributos.
A semântica dirigida pela sintaxe feita com o uso de gramáticas de atributos diz quais ações 
serão realizadas considerando:
 comportamento semântico das operações;
 verificação de tipos;
 manipulação de erros;
 tradução do programa.
Análise semântica
Definição dirigida por sintaxe: é uma GLC acrescida de atributos e regras: os atributos são 
associados aos símbolos e as regras associadas às produções. Exemplo:
Tradução dirigida por sintaxe
Produção Regras semânticas 
1) E  T / E1 E.val = T.val - E1.val
2) E  T E.val = T.val 
3) T  digit T.val = digit.lexval
 Atributo sintetizado: para um não terminal A em um nó N da árvore de derivação, é definido 
por uma regra semântica associada à produção naquele nó. A produção precisa ter A como 
sua cabeça, ou seja, seu nó ancestral. Um nó sintetizado no nó N é apenas definido em 
termos dos valores dos atributos dos filhos de N e do próprio N.
 Atributo herdado: para um não terminal B é definido por uma regra semântica associada à 
produção no pai de N. A produção precisa ter B como um símbolo em seu corpo. Um atributo 
herdado no nó N é definido em termos dos valores dos atributos do pai de N, do próprio N e 
dos irmãos de N.
Atributos herdados e atributos sintetizados
 Esquemas S-atribuídos são aqueles em que há apenas 
atributos sintetizados.
Implementação de esquemas S-atribuídos
Produções Regras semânticas
E → E1 + T E.ptr:= cria_no (‘ +’, E1 .node, T.node)
E → E1 - T E.ptr = cria_no(‘’, E1 .ptr, T.ptr)
E → T E.ptr =T.ptr
T → (E) T.ptr:= E.ptr
T → id T.ptr cria_folha(id, id.entry)
T → num T.ptr:= cria_folha (num, num.val)
 A Árvore de Sintaxe Abstrata (AST) é uma estrutura de dados 
que representa a estrutura primária de um programa. Cada nó 
representa uma construção, tais como procedimentos, 
declarações, instruções, expressões, tipos e parâmetros. Os 
nós-filhos representam os componentes dessas construções.
Esquema S-atribuído
Produções Regras semânticas
E → E1 + T E.ptr:= cria_no (‘ +’, E1 .node, T.node)
E → E1 - T E.ptr = cria_no(‘’, E1 .ptr, T.ptr)
E → T E.ptr =T.ptr
T → (E) T.ptr:= E.ptr
T → id T.ptr cria_folha(id, id.entry)
T → num T.ptr:= cria_folha (num, num.val)
Árvore de sintaxe para a expressão a-7+b 
Árvore de Sintaxe
Estrutura de Dados
a 7
– b
+ +
– id b
num 7id a
 Os esquemas L-atribuídos
são aqueles em que há
atributos sintetizados
e herdados.
Esquema L-atribuído
Produções Regras Semânticas
E  TE’ E.ptr=E’.s
E’.h=T.ptr
E’ +TE’ E’1.h=cria_no(+, E’.h, T.ptr)
E’.s=E’1.s
E’  -TE’ E’1.h=cria_no(+, E’.h, T.ptr)
E’.s=E’1.s
E’  E’.s=E’1.h
T (E) T.ptr = E.ptr
T id T.ptr=cria_folha(id, id.entry)
T num T.ptr=cria_folha(num, num.val)
Esquema L-atribuído
Produções Regras Semânticas
E  TE’ E.ptr=E’.s
E’.h=T.ptr
E’ +TE’ E’1.h=cria_no(+, E’.h, T.ptr)
E’.s=E’1.s
E’  -TE’ E’1.h=cria_no(+, E’.h, T.ptr)
E’.s=E’1.s
E’  E’.s=E’1.h
T (E) T.ptr = E.ptr
T id T.ptr=cria_folha(id, id.entry)
T num T.ptr=cria_folha(num, num.val)
Grafo de dependência 
para a-7+b
E 13 ptr
T 2 ptr h 5 E’ 12 s
– T 4 ptr h 6 E’ 11 sid 1 entry
num 3 val + T 8 ptr h 9 E’ 10
id 7 entry ∈
 Em um compilador, a tabela de símbolos é construída na análise semântica e usada durante 
a geração de código. Durante a geração do código, a tabela de símbolos fornece as 
informações necessárias para traduzir as instruções de alto nível para código de máquina ou 
outro formato de saída, assegurando que o código final esteja correto e otimizado.
 A tabela de símbolos é uma estrutura de dados gerada pelo compilador com o objetivo de 
armazenar informações sobre os nomes (identificadores de variáveis, de parâmetros, de 
funções, de procedimentos, classes e métodos). Consequentemente, para as variáveis são 
armazenados atributos, como tipo e endereços, escopo. Aos identificadores de funções são 
associados atributos, como tipo dos argumentos e de seus resultados.
Tabela de símbolos
 É comum usar tabelas de símbolos separadas para diferentes espaços. Pode-se usar uma 
tabela para cada tipo de declaração, como constantes, variáveis, tipos, procedimentos e 
funções. Como exemplo, podemos citar os descritores das estruturas sintáticas. Classes das 
linguagens de programação orientadas a objetos estão associadas a duas tabelas de 
símbolos: para os atributos e para os métodos.
São operações essenciais da tabela de símbolos:
 criar uma tabela vazia;
 inserir uma nova entrada em uma tabela, a saber o identificador e a informação pertinente;
 procurar um determinado identificador e devolver a informação 
associada (caso exista) ou um sinal de falha;
 (remoção) exclui ou torna inacessíveis as informações sobre 
um elemento que não é mais necessário, como variáveis 
locais que deixam de existir após a saída de um procedimento.
Tabela de símbolos
 Diferentes abordagens podem ser realizadas para sua implementação, estática ou dinâmica. 
Existem diferentes estruturas de dados concretos que podem ser utilizadas, tais como listas 
lineares, matrizes, árvores binárias ou AVL e tabelas hash.
 Uma tabela de símbolos apresenta de algumas centenas a milhares de entradas. 
Naturalmente, uma estratégia de implementação dinâmica é mais adequada, visto que o 
tamanho se ajusta conforme necessário. O escopo dos identificadores pode ser 
representado por múltiplas tabelas ou uma única tabela, que inclui a identificação do escopo 
como um atributo. Isso permite ao compilador gerenciar corretamente variáveis e funções 
com o mesmo nome em diferentes níveis de escopo (Olivete Júnior, [s.d.]).
 O escopo dos identificadores pode ser representado por 
múltiplas tabelas ou por uma única tabela que inclui a 
identificação do escopo como um atributo. Isso permite que o 
compilador gerencie corretamente variáveis e funções com o 
mesmo nome em diferentes níveis de escopo.
Tabela de símbolos 
 Para gerenciar escopos de forma eficiente, a tabela desímbolos pode incluir um campo 
adicional que indica o nível de escopo de cada variável. Durante a compilação, o nível é 
ajustado ao entrar e sair de procedimentos ou funções. Por exemplo, ao entrar em uma 
função, o nível é incrementado e, ao sair, é decrementado. Além disso, as variáveis locais a 
um procedimento podem ser associadas à entrada correspondente na tabela de símbolos, 
frequentemente por meio de listas encadeadas.
 Inserção, busca e remoção são incorporadas diretamente na análise sintática do compilador, 
garantindo que a tabela de símbolos seja constantemente atualizada.
 Essa integração permite que o compilador monitore e verifique 
de maneira eficaz todos os identificadores do programa, 
assegurando a correção e a consistência do código.
Tabela de símbolos
Considere as seguintes asserções:
I. Um atributo sintetizado no nó N é apenas definido em termos dos valores dos atributos 
dos filhos de N e do próprio N.
PORQUE
II. Um atributo herdado no nó N é definido em termos dos valores dos atributos do pai de N, 
do próprio N e dos irmãos de N. 
Assinale a alternativa correta:
a) I e II são asserções verdadeiras e II justifica I.
b) I e II são asserções verdadeiras, mas II não justifica I.
c) Apenas a asserção I é falsa.
d) Apenas a asserção II é falsa.
e) Ambas asserções são falsas.
Interatividade
Considere as seguintes asserções:
I. Um atributo sintetizado no nó N é apenas definido em termos dos valores dos atributos 
dos filhos de N e do próprio N.
PORQUE
II. Um atributo herdado no nó N é definido em termos dos valores dos atributos do pai de N, 
do próprio N e dos irmãos de N. 
Assinale a alternativa correta:
a) I e II são asserções verdadeiras e II justifica I.
b) I e II são asserções verdadeiras, mas II não justifica I.
c) Apenas a asserção I é falsa. 
d) Apenas a asserção II é falsa.
e) Ambas asserções são falsas.
Resposta
 AHO, A. V. et al. Compiladores princípios, técnicas e ferramentas. 2. ed. São Paulo: 
Pearson Addison Wesley, 2007. 
 NETO, J. J.; Ramos M. V. M. Considerações sobre o projeto de um compilador para uma 
Linguagem de Programação de Alto Nível. 1988, Anais EPUSP – vol. 1 – série B.1993. 306 f. 
Disponível em: Prof. Marcus Ramos – UNIVASF. Acesso em: 29 ago. 2024.
 NETO, J. J. Contribuições à metodologia de construção de compiladores. 1993. 306 f. Tese 
(Livre-Docência Engenharia de Computação e Sistemas Digitais) – Escola Politécnica, 
Universidade de São Paulo, São Paulo, 1993. Disponível em: 
http://lta.poli.usp.br/lta/publicacoes/teses-e-dissertacoes/1993/jose-neto-1993-contribuicoes-
a-metodologia-de-construcao-de-compiladores/view. Acesso em: 26 set. 2024.
 NETO J. J. Introdução à Compilação. 2. ed. rev. atual. e 
ampliada. Rio de Janeiro: Elsevier, 2016.
Referências
 OLIVETE JR. C. Compiladores. Faculdade de Ciências e Tecnologia/UNESP Disponível em: 
www2.fct.unesp.br/docentes/dmec/olivete/compiladores/compiladores_material_didatico.html 
Acesso em: 29 ago. de 2024.
 PRICE, A. M. A. ; TOSCANI, S. S. Implementação de Linguagens de Programação: 
Compiladores. Porto Alegre: Sagra-Luzzatto, 2000.
 ROCHA, R. L. A. Linguagens e Compiladores. Disponível em: www.usp.br. (Linguagens e 
Compiladores). Acesso em: 28 abr. de 2024.
Referências
ATÉ A PRÓXIMA!