Organização de computadores Aula 05

Prévia do material em texto

Organização e Arquitetura 
de Computadores 
Compiladores 
Prof. Wanderson Senra Michel 
wanderson.senra@udf.edu.br 
 Uma linguagem de programação é um conjunto de ferramentas, 
regras de sintaxe e símbolos ou códigos que nos permitem escrever 
programas de computador. 
 
 A primeira e mais primitiva linguagem de computador é a própria 
linguagem de máquina (0’s e 1’s). 
 
 Um programa era difícil, longo e principalmente caro de se 
construir. 
 
 Era também difícil de ser entendido por outros programadores. 
 
 Essa complexidade levou à necessidade de desenvolver novas 
técnicas e ferramentas. 
Programa em Linguagem de Máquina 
I. Execução de Programas 
• A resolução do problema passou pela criação de uma linguagem em 
que os códigos numéricos foram substituídos por mnemônicos. 
 
• O nome dessa linguagem é ASSEMBLY LANGUAGE. 
 
• Então será necessário um outro programa que leia o programa 
escrito nessa linguagem alternativa e o traduza para a linguagem 
nativa do computador!!! 
 
• O processo de tradução da linguagem de montagem para a linguagem 
de máquina é realizada por um programa chamado ASSEMBLER. 
 
 
Linguagem de Montagem 
I. Execução de Programas 
Linguagem Assembly 
I. Execução de Programas 
;****************************************************** 
;*** INTERFACE ROUTINES *** 
;****************************************************** 
; 
Read_Char PROC ;read char from input buffer 
; 
;Entry: CL = port number 
; 
;Exit: AL = char (z set if none) 
; 
 push cx ;preserve registers 
 push bx 
; 
 cmp cl,0 ;only port 0 allowed 
 jz rc_1 
; 
 _Int_Error 03301h ;invalid port number 
; 
rc_1: mov al,Rx_InPtr 
 sub al,Rx_OutPtr ;inptr - outptr = num. chars 
 jz rc_zex ;if zero exit 
• Foram desenvolvidas diversas linguagens de programação: 
• FORTRAN (1957) 
• ALGOL (1958) 
• COBOL (1959) 
• PASCAL (1963) 
• BASIC (1965) 
• ADA (1968) 
• DoD (1969) 
• C (1982) e mais tarde o C++ (1986) 
• Etc…. 
 
• Estas novas linguagens foram afastando cada vez mais o 
programador do nível de máquina. 
Linguagem de Programação 
I. Execução de Programas 
• Os programas em linguagem de alto nível também precisam ser 
traduzidos para linguagem de máquina. 
 
 
Tradução 
Código Fonte Código Objeto 
Tradução 
I. Execução de Programas 
• O processo de montagem traduz um programa 
escrito numa LP num programa equivalente em 
linguagem de máquina. 
Montagem 
Código Fonte 
Tradução 
Linguagem de Máquina 
Processo de Montagem 
I. Execução de Programas 
Mas com 
o quê ??? 
Todo o programa escrito numa 
linguagem de programação de alto 
nível precisa ser traduzido para a 
linguagem de máquina, 
para que o computador 
 possa executá-lo. 
Todo o programa escrito numa 
linguagem de programação de alto 
nível precisa ser traduzido para a 
linguagem de máquina, 
para que o computador 
 possa executá-lo. 
Com Compiladores ou 
Interpretadores 
• Um compilador tem a finalidade de converter uma 
linguagem – Linguagem Fonte – de fácil escrita e leitura 
para os programadores, numa linguagem – Linguagem alvo 
ou objeto – que possa ser executada pelas máquinas. 
 
• O código executável gerado pelo compilador é 
dependente do sistema operacional e da linguagem de 
máquina para o qual o código fonte foi traduzido. 
 
• A enorme variedade de compiladores existentes é bem 
vinda, visto que existem milhares de linguagens fonte, e 
as linguagens alvo são também muito variadas. 
II . Compiladores 
O que é um compilador 
• Os compiladores são por vezes classificados 
como uni-passo, multi-passo, otimizador, ou 
corretor de erros, dependendo da forma como 
foram construídos ou da funcionalidade para que 
são pretendidos. 
 
• Começaram a aparecer no início da década de 50. 
 
• Muito do trabalho inicial dos compiladores 
resumia-se a tradução de fórmulas aritméticas 
para código de máquina. 
II . Compiladores 
O que é um compilador 
• O primeiro compilador de FORTRAN, por exemplo, 
demorou 18 trabalhosos meses para ser implementado. 
 
• Boas linguagens de implementação, ambientes de 
programação e ferramentas de software estão sendo 
desenvolvidas a todo momento. 
 
• Com estes avanços, um bom compilador pode ser 
implementado por alunos num projeto de TCC de um curso 
de tecnologia. 
II . Compiladores 
O que é um compilador 
 Ilustração do funcionamento de um compilador: 
II . Compiladores www 
O que é um compilador 
• Podemos dividir o processo de compilação em duas fases: 
 
• Análise : parte o programa fonte em peças constituintes e cria 
uma representação intermediária do programa fonte. 
 
• Síntese : Constrói o programa alvo desejado (código de máquina) 
a partir da representação intermediária. 
 
• A parte da síntese é a que requer técnicas mais 
especializadas. 
II . Compiladores 
Modelo Análise- síntese da compilação 
II . Compiladores 
Modelo Análise- síntese da compilação 
Análise 
Análise 
Léxica 
Análise 
Sintática 
Análise 
Semântica 
II . Compiladores 
Modelo Análise- síntese da compilação 
Síntese 
Geração do 
Código 
Otimização 
do Código 
Muitos outros programas podem ser necessários para se 
criar um programa alvo executável. 
II . Compiladores 
Contexto de um compilador 
Biblioteca, arquivos de 
Objetos Realocados 
• Pré-processadores: produzem o input para os 
compiladores; 
• Montadores: Alguns compiladores produzem 
código Assembly que é passado para um 
montador para posterior processamento. 
• Alguns compiladores produzem o trabalho dos 
montadores; 
 
II . Compiladores 
Primos de um compilador 
• Montagens bi-passo: 
• Iº Passo - todos os identificadores que denotam localizações 
de armazenamento são encontrados e armazenados numa 
tabela de símbolos 
• IIº Passo - traduz cada código de operação para seqüência de 
bits representando essa operação na linguagem de máquina 
 
• Carregadores e editores de união (Linker): 
• Carregar consiste em tomar o restabelecimento do código 
máquina, alterando os endereços restabelecidos e colocando 
as instruções alteradas e dados na memória nas localizações 
convenientes. 
• O editor de união permite se fazer um único programa dos 
vários arquivos de código de máquina; 
II . Compiladores 
Primos de um compilador 
• Bibliotecas: 
 
• O desenvolvimento de um programa certamente utilizará 
diversas operações que são comuns a muitos outros programas. 
 
• Um programa de alto nível possivelmente conterá diversas 
chamadas de biblioteca. 
 
• Essas funções não devem ser confundidas com as instruções da 
linguagem – na realidade, são pequenos programas externos que 
são chamados através de instruções especiais chamado 
“biblioteca”. 
II . Compiladores 
Primos de um compilador 
• Na compilação a análise consiste em 3 
partes: 
 
• Análise Léxica ou Linear: 
• Em que a cadeia de caracteres que forma a estrutura 
do programa fonte é lido da esquerda para a direita e 
agrupado em tokens que são seqüências de 
caracteres tendo o sentido coletivo. 
 
• A sua função básica é o reconhecimento e a 
classificação das estruturas elementares ou classes 
sintáticas das linguagens. 
II . Compiladores 
Análise do programa fonte 
• Análise sintática ou hierárquica: 
• Na qual caracteres ou tokens são agrupados 
hierarquicamente em coleções aninhadas com sentido 
coletivo. 
 
• Verifica-se a estrutura geral do texto ou se o 
programa fonte está correto. 
II . CompiladoresAnálise do programa fonte 
• Análise semântica: 
• Na qual são executadas certas etapas para assegurar 
que os componentes de um programa são juntamente 
ajustados em sentido absoluto. 
 
• Verifica se o programa fonte tem erros semânticos e 
reúne a informação dos tipos para a fase de gerador 
de código subseqüente. 
 
• Um componente importante da análise semântica é a 
verificação do tipo. 
II . Compiladores 
Análise do programa fonte 
II . Compiladores 
Fases de um compilador 
II . Compiladores 
Fases de um compilador 
• Gerenciador da tabela de símbolos: 
• Uma função essencial de um compilador é registrar os 
identificadores usados no programa fonte e reunir 
informações sobre os vários atributos de cada 
identificador. 
 
• Uma tabela de símbolos é uma estrutura de dados 
contendo o registro de cada identificador, com 
campos para os atributos do identificador. 
II . Compiladores 
Fases de um compilador 
• Tabela de códigos: 
• É uma estrutura criada pela análise semântica de um 
compilador, que mantém registradas as linhas de 
código intermediário geradas por algum tempo. 
 
• Em geral as linhas de código geradas permanecem 
nesta tabela enquanto não estão totalmente 
preenchidas. 
 
 
II . Compiladores 
Fases de um compilador 
• Detecção de erros e aviso do erro: 
• Cada fase pode encontrar erros. Porém, depois de 
descobrir um erro, a fase tem que tratar de alguma 
maneira aquele erro, para que a compilação possa 
prosseguir. 
 
• As fases de análise sintática e semântica 
normalmente tratam de uma grande fração dos erros 
detectáveis pelo compilador. 
II . Compiladores 
Fases de um compilador 
 
• Geração de código intermediário: 
• Depois da análise sintática e semântica, alguns 
compiladores geram uma representação intermediária 
explícita do programa fonte. 
 
• Podemos pensar nesta representação intermediária 
como um programa para uma máquina abstrata. 
 
II . Compiladores 
Fases de um compilador 
• Otimização do código: 
• Esta fase tenta melhorar o código intermediário, de forma a que 
resulte num código de máquina mais rápido a ser executado. 
 
• Geração do código: 
• A fase final do compilador é a geração de código alvo, 
consistindo normalmente no restabelecimento no código máquina. 
• Neste ponto, após o programa fonte ter sido analisado e 
aprovado, segundo a sua sintaxe e livre de erros semânticos, o 
compilador tem condições de escrever um programa equivalente 
na linguagem alvo. 
II . Compiladores 
Fatores condicionantes da organização física dos compiladores 
• Dividir o processo de compilação em diversas fases "lógicas" 
permite um melhor entendimento do processo como um todo e leva a 
uma implementação mais estruturada. 
 
• A eficiência e os recursos disponíveis na máquina hospedeira do 
compilador influenciam de maneira decisiva. Um item 
importantíssimo na implementação de um compilador: o número de 
passos de compilação, para poder otimizar o tempo de compilação. 
 
 
 
 
III . Interpretadores 
Como funcionam os interpretadores 
• O funcionamento dos interpretadores é muito parecido ao 
dos compiladores. 
 
• O interpretador traduz o código linha a linha. 
 
• O código fonte não é totalmente traduzido antes de ser 
executado. 
 
• Não existem fases distintas nem se produz código 
intermediário. 
 
• Passa o tempo todo lendo e traduzindo código. 
III . Interpretadores 
Exemplos de interpretadores 
• Internet; 
 
• Excel, Word Basic, Access, ... ; 
 
• SmallTalk; 
 
• AutoLisp; 
 
• Lisp. 
IV . Comparação 
Vantagens Desvantagens 
 
Compiladores 
Execução mais rápida Várias etapas de tradução 
Permite estruturas de 
programação mais completas 
Programação final é maior, 
necessitando mais memória para a 
sua execução 
Permite a otimização do código 
fonte 
Processo de correção de erros e 
depuração é mais demorado 
 
Interpretadores 
Depuração do programa é mais 
simples 
Execução do programa é mais lenta 
Consome menos memória Estruturas de dados demasiado 
simples 
Resultado imediato do programa 
ou rotina desenvolvida 
Necessário fornecer o programa 
fonte ao utilizador 
V . Exemplos de Linguagens 
Compiladas e Interpretadas 
• Java; 
 
 
 
• Basic. 
Análise Léxica 
Prof. Wanderson Senra Michel 
wanderson.senra@udf.edu.br 
II – Análise léxica 
• Papel do analisador léxico. 
• Diagnóstico e recuperação de erros léxicos 
• Extensão de expressões regulares e definições 
regulares 
• Reconhecimento de tokens 
• Bibliografia aconselhada: 
– Aho, Sethi e Ullman – seções 3.1 e 3.3 
– Appel – seções 2.1, 2.2 e 2.3 
Papel do analisador léxico 
Tokens, padrões e lexemas 
• Token: representa um conjunto de sequências de 
caracteres com significado comum (número, 
identificador, etc...) 
• Padrão: conjunto de sequências que resultam 
num mesmo token 
• Lexema: sequência de caracteres que obedece a 
um padrão de token 
Exemplo 
• O token identificador tem como padrão uma 
sequência que começa numa letra seguida de 
letras e números. 
• Alguns lexemas possíveis: 
– var, x1, LFA9900. 
• Palavras reservadas 
– if, else, while, switch, int, long, etc... 
Atributos dos tokens 
• Alguns tokens, como as palavras chave, só têm 
um lexema possível 
• Quando existe mais do que um lexema possível é 
preciso guardar alguma informação suplementar: 
– um apontador para a tabela de símbolos, no caso de 
um identificador 
– o valor numérico, no caso de um número 
Erros léxicos 
• Um erro léxico ocorre quando o analisador léxico 
não pode prosseguir porque nenhum dos padrões 
foi encontrado 
• Muitas vezes é impossível na fase de análise 
léxica identificar alguns erros, porque o padrão 
encontrado e o pretendido são diferentes: a2 
(identificador) / 2a (número seguido de 
identificador) 
Recuperação de erros léxicos 
• Modo de pânico: apagar caracteres da entrada 
até conseguir um token válido 
• Apagar um caracter estranho 
• Inserir um caracter em falta 
• Substituir um caracter incorreto por um correto 
• Transposição de dois caracteres adjacentes 
Extensão de expressões regulares 
• Vamos estender as definições anteriores: 
– a | b  a + b 
– a+  aa* 
– [abc]  a + b + c  a | b | c 
– [a-z]  a + b + ... + z  a | b | ... | z 
– a?  a +   a |  
 
Definições regulares 
• Por conveniência podemos definir nomes para 
algumas expressões regulares. Por exemplo: [0-9] 
representa um dígito. 
• Uma definição regular tem a forma 
def  er onde def é a definição e er a expressão 
regular, podendo esta usar símbolos do alfabeto 
ou definições anteriores 
Exemplo 
• Definição de um identificador 
– letra  [A-Za-z] 
– dígito  [0-9] 
– identificador  letra (letra | digito)* 
• Definição de um número 
– dígito  [0-9] 
– dígitos  dígito+ 
– parte_fracionária  (. dígitos)? 
– expoente  (E [+-]? dígitos)? 
– num  dígitos parte_fracionária expoente 
Reconhecimento de tokens 
• Espaços em branco – caracteres que não são 
considerados para a formação de tokens 
• O caracter ' ' é desprezado quando se tenta 
determinar um token, mas é tido em conta 
quando se trata de uma string 
• Caracteres como os de tabulação e nova linha 
podem ser considerados espaços em branco 
Tokens e autómatos finitos 
• Os autómatos finitos, como reconhecem 
linguagens regulares, são uma boa forma de 
reconhecer tokens 
• Existem algoritmos que permitem transformar 
uma expressão regular num autómato finito 
determinístico 
Exemplode um analisador léxico 
• Crie um autômato finito determinístico que 
reconheça a seguinte linguagem: L=0 conjunto de 
todos os números binários {0,1} que tenham 01 
como subcadeia. 
Exemplo de um analisador léxico 
• Crie um autômato finito determinístico que 
reconheça a seguinte linguagem: L=0 conjunto de 
todos os números binários {0,1} que tenham 01 
como subcadeia. 
Exemplo de um analisador léxico 
• Vamos considerar um pequeno analisador léxico 
com: 
– espaços em branco: ' ', tabulação e nova linha 
– operadores relacionais: <, <=, >, >=, ==, != 
– identificadores: letra (letra | dígito)* 
– números: dígito+ (. dígito+)? (E [+-]? dígito+)? 
Operadores relacionais 
Identificadores 
Números 
II – Análise léxica 
• Conversão de expressões regulares em autómatos 
finitos determinísticos mínimos 
• Bibliografia aconselhada: 
– Aho, Sethi e Ullman – seções 3.6, 3.7 e 3.9 
– Crespo – subseções 3.1.2, 3.1.3 e 3.1.4 
– Appel – seção 2.4 
Expressão regular  autómato finito determinístico mínimo 
• Conversão expressão regular  autómato finito  
(Construção de Thompson) 
• Conversão autómato finito   autómato finito 
determinístico (construção de subconjuntos) 
• Conversão autómato finito determinístico com 
estados supérfluos  autómato finito 
determinístico mínimo 
ER  AF:  
ER  AF: a   
ER  AF: E1 + E2 
ER  AF: E1 E2 
ER  AF: E1
*
 
Propriedades do autómato final 
• O autómato criado tem no máximo duas vezes o 
número de símbolos da expressão regular 
• Existe um estado inicial e um final sem transições 
• Para cada estado, ou existe uma transição com 
um símbolo de  ou existem duas transições com 
 
Exemplo: (0+1)*(1+000) 
AF  AFD 
• fecha-(s): conjunto de estados alcançáveis a 
partir do estado s com transições de  
• fecha-(T): conjunto de estados alcançáveis a 
partir de estados s  T com transições de  
• mover(T,a): conjunto de estado para os quais 
existe uma transição a partir de estados s  T 
com o símbolo a   
Construção de subconjuntos 
• fecha-(i) é o primeiro estado não marcado 
 enquanto houver estados T não marcados 
– marcar T 
– para cada símbolo a   
• U = fecha-(mover(T,a)) 
• se U não pertence ao conjunto de estados 
– inserir U não marcado 
• adicionar transição (T,a,U) 
Exemplo: (0+1)*(1+000) 
• fecha-(0) = {0,1,2,4,7,8,10} = A 
• fecha-(mover(A,0)) = fecha-({3,11}) = 
{1,2,3,4,6,7,8,10,11} 
• fecha-(mover(A,1)) = fecha-({5,9}) = 
{1,2,4,5,6,7,8,9,10,14} = C 
• fecha-(mover(B,0)) = fecha-({3,11,12}) = 
{1,2,3,4,6,7,8,10,11,12} = D 
• fecha-(mover(B,1)) = fecha-({5,9}) = C 
Exemplo (cont.) 
• fecha-(mover(C,0)) = fecha-({3,11}) = B 
• fecha-(mover(C,1)) = fecha-({5,9}) = C 
• fecha-(mover(D,0))=fecha-({3,11,12,13}) = 
{1,2,3,4,6,7,8,10,11,12,13,14} = E 
• fecha-(mover(D,1)) = fecha-({5,9}) = C 
• fecha-(mover(E,0))=fecha-({3,11,12,13}) = E 
• fecha-(mover(E,1)) = fecha-({5,9}) = C 
Exemplo: AFD 
Minimizar número de estados 
• Partição inicial do conjunto de estados S em F e F\S 
• Em cada partição cria-se sucessivamente novas 
partições, mantendo juntos os estados que têm 
transições iguais entre partições 
• Os novos estados são: 
– estados iguais aos iniciais; 
– conjunto de estados com transições iguais entre partições. 
Exemplo: (0+1)*(1+000) 
• Partição inicial: (ABD)(CE) 
• Em (CE): o estado E tem a transição ((CE),0,(CE)), 
enquanto C tem a transição ((CE),0,(ABD))  (ABD)(C)(E) 
• Em (ABD): A e B têm a transição ((ABD),0,(ABD)), 
enquanto D tem a transição ((ABD),0,(E))  (AB)(C)(D)(E) 
• Em (AB): A tem a transição ((AB),0,(AB)), enquanto B tem 
a transição ((AB),0,(D))  (A)(B)(C)(D)(E) 
Exemplo: 0*(100*)*(1+ ) 
Exemplo: 0*(100*)*(1+ ) 
• fecha-(0) = {0,1,3,4,10,11,13,14,15} = A 
• fecha-(mover(A,0)) = fecha-({2}) = 
{1,2,3,4,10,11,13,14,15} = B 
• fecha-(mover(A,1)) = fecha-({5,12}) = {5,12,15} 
= C 
• fecha-(mover(B,0)) = fecha-({2}) = B 
• fecha-(mover(B,1)) = fecha-({5,12}) = C 
Exemplo: 0*(100*)*(1+ ) 
• fecha-(mover(C,0)) = fecha-({6}) = 
{4,6,7,9,10,11,13,14,15} = D 
• fecha-(mover(C,1)) = fecha-() =  
• fecha-(mover(D,0)) = fecha-({8}) = 
{4,7,8,9,10,11,13,14,15} = E 
• fecha-(mover(D,1)) = fecha-({5,12}) = C 
• fecha-(mover(E,0)) = fecha-({8}) = E 
• fecha-(mover(E,1)) = fecha-({5,12}) = C 
Exemplo: 0*(100*)*(1+ ) 
Exemplo: 0*(100*)*(1+ ) 
• Como todos os estados são finais, vamos ter 
inicialmente uma única partição (ABCDE) 
• Como C não tem transição com 1 para nenhum 
estado  (ABDE) (C) 
• Em (ABDE) todos os estados têm as mesmas 
transições: ((ABDE),0,(ABDE)) e ((ABDE),1,(C))  
não são feitas mais partições  (ABDE) (C) 
Exemplo: 0*(100*)*(1+ ) 
II – Análise léxica 
• lex: linguagem de especificação para analisadores 
léxicos 
• Implementação de simuladores de autómatos 
finitos 
• Bibliografia aconselhada: 
– lex & yacc 
– Aho, Sethi e Ullman – seção 3.5 e 3.8 
Linguagem lex 
• Linguagem de especificação de um analisador 
usando expressões regulares estendidas 
• As expressões regulares definem padrões para 
cada um dos tokens 
• As ações são especificadas para cada token em 
linguagem C 
Meta-símbolos 
• ‘-’ usado na definição de domínios (a-z) 
• ‘\’ caracter de escape usado como na linguagem C 
(\n, \t, etc...) e também para usar caracteres que 
são meta-símbolos (\- significa o caracter ‘-’) 
• “aspas” servem para delimitar caracteres 
• / operador de procura à frente (lookahead) 
Implementação do simulador AF 
• O lex usa um simulador de um autómato finito 
usando uma tabela de transições 
• Especificação em lex  compilador lex  tabela 
de transições 
• O simulador lê a entrada e, usando a tabela de 
transições, simula as transições dos autómatos 
executável 
Recapitulando 
Análise 
sintática 
Código fonte 
AST 
Análise 
semântica 
Geração de 
código 
AST decorada 
Análise 
léxica 
Tokens 
Análise Léxica - Definição 
• Fase da compilação responsável por extrair os tokens 
do código fonte de um programa. 
if (n == 0) { 
 return 1; 
} else { 
 ... 
} 
 
RPAR LCUR 
RCUR 
if LPAR 
return 
else 
 
"n" 
id 
"0" 
intLit 
assign 
"1" 
intLit ... comm 
Especificação 
• Os tokens de uma linguagem comumente são 
especificados através de Expressões Regulares 
 
– [a-z][a-z0-9]* identifier 
 
– [0-9]+ intLiteral 
 
Implementação 
• Autômatos finitos 
1 2 
a-z a-z 
0-9 
ID 
2 1 3 
i f 
IF 
Análise Sintática 
Prof. Wanderson Senra Michel 
wanderson.senra@udf.edu.br 
III – Análise sintática 
• Papel do analisador 
• Diagnóstico e recuperação de erros 
• Uso de gramáticas independentes de contexto 
• Bibliografia aconselhada: 
– Aho, Sethi e Ullman – seções 4.1 e 4.2 
– Appel – seção 3.1 
Papel do analisador 
Árvore 
Sintática 
Definição 
• Fase da compilação responsável por determinar se uma 
dada cadeia de entrada pertence ou não à linguagem 
definida por uma gramática 
 
• Tem como entrada os tokens processados pela análise 
léxica 
 
• Produz uma estrutura comumente denominada AST – 
abstract syntax tree 
 
Especificação 
• BNF - Backus-Naur form 
 
– S, A, B, C, D : não-terminais 
 
– a,b,d: terminais 
 
S ::= A | B 
A ::= C | D 
B ::= bba 
C ::= ab 
D ::= dab 
Produções 
Tipos de analisadores 
• Parsers universais: reconhecem todas as 
gramáticasindependentes de contexto mas são 
ineficientes 
• Parsers descendentes (Top-Down): 
reconhecimento feito da raíz para as folhas 
• Recursive-descent / LL(1) 
• Parsers ascendentes (Bottom-Up): 
reconhecimento feito das folhas para a raíz 
• LR, SLR, LALR, LR(k) 
 
Tipos de gramáticas 
• A maioria dos métodos trabalham apenas com 
subclasses de gramáticas, mas são suficientemente 
expressivas 
• Gramáticas LL(k) (Left-to-right parse, 
Leftmost-derivation, k-token lookahead): mais usado 
para parsers implementados diretamente 
• Gramáticas LR(k) (Left-to-right parse, 
Rightmost-derivation, k-token lookahead): mais usado 
com ferramentas automáticas 
Erros 
• A maioria dos erros no código fonte são erros S 
• Erros frequentes: 
– Tecla de shift 
– Carácter em falta ou em excesso 
– Erros resultantes de outros: variáveis mal declaradas 
não entram na tabela de símbolos 
Recursive descent 
• Algoritmo baseado em previsões 
 
• Funções mutuamente recursivas 
 
• Uma função para cada não-terminal 
 
• Uma cláusula para cada produção 
Recursive descent 
• Desenvolvendo um recursive descent parser 
 
– Cada não terminal 'X' dará origem a um 
método/função parseX(); 
 
– Produções do tipo 'A | B' darão origem a cláusulas 
cases 
Recursive descent 
A ::= aBcC 
 
B ::= CB | cC 
 
C ::= da 
parseA() { 
 accept(‘a’); 
 parseB(); 
 accept(‘c’); 
 parseC(); 
} 
parseB() { 
 case (d): 
 parseC(); 
 parseB(); 
 case (c): 
 accept(‘c’); 
 parseC(); 
} 
parseC() { 
 
 accept(‘d’); 
 accept(‘a’); 
} 
Recursive descent 
• Na prática constrói uma tabela de produções 
indexadas por não-terminais e terminais 
A ::= aBcC 
 
B ::= CB | cC 
 
C ::= da 
a c d 
A A::= 
aBcC 
B B::= cC B::= CB 
C C::= da 
Recursive descent 
A ::= aBcC 
 
B ::= CB | CA 
 
C ::= da 
parseA() { 
 accept(‘a’); 
 parseB(); 
 accept(‘c’); 
 parseC(); 
} 
parseB() { 
 case (d): 
 parseC(); 
 parseB(); 
 case (d): 
 parseC(); 
 parseA(); 
} 
parseC() { 
 
 accept(‘d’); 
 accept(‘a’); 
} 
Recursive descent 
• Na prática constrói uma tabela de produções 
indexadas por não-terminais e terminais 
A ::= aBcC 
 
B ::= CB | CA 
 
C ::= da 
a c d 
A A::= aBC 
B B::= CB 
B::= CA 
C C::= da 
Recursive descent 
• Vantagens 
– Fácil de implementar 
• Desvantagens 
– Performance 
– Gramática reconhecida possui restrições 
• Sem recursão à esquerda 
• Deve estar fatorada 
• ... 
 
Recursive descent 
A ::= aBC 
 
B ::= CB | CA 
 
C ::= da 
A ::= aBC 
 
B ::= CX 
 
X ::= B | A 
 
C ::= da 
a c d 
A A::= aBC 
B B::= CX 
C C::= da 
X X::=A X::=B 
Gramática 
LL(1) 
Gramáticas LL(1) 
Left-to-right parse Leftmost-derivation 1-symbol-lookahead 
LL(1) 
Algoritmos bottom-up 
• Algoritmos LL(k) precisam decidir que produção 
usar tendo visto apenas k tokens da entrada 
• Algoritmos bottom-up são baseados em técnicas 
LR(k) 
– Left-to-right parse, Right-most derivation, k-symbol-
lookahead 
Algoritmos bottom-up 
• Baseados no conceito de autômato a pilha 
– Pilha + lookahead 
– Duas tipos de ações 
• Shift: 
– Coloca o primeiro token da entrada no topo da pilha 
• Reduce: 
– Escolhe a regra X::= A B C 
– Retira C, B, A da pilha 
– Coloca X na pilha 
 
Gramáticas LR 
• LR(0) 
– Olham apenas para a pilha 
• SLR 
– Melhoramento sobre o LR(0) 
• LR(1) 
– Lookahead de 1 símbolo 
– Consegue descrever a maioria das linguagens de programação 
• LALR(1) 
– Melhoramento sobre o LR(1) 
• Diminuí o tamanho da tabela de parsing 
 
Gramáticas Ambíguas 
• Uma gramática é ambígua se a partir dela uma sentença 
pode dar origem a duas arvores de parsing 
 
• Problemáticas para a compilação 
 
• Eliminação de ambigüidade é quase sempre possível 
 
– Transformações na gramática 
Gramáticas Ambíguas 
• Caso clássico: gramática para expressões aritméticas 
E ::= intLiteral 
 | E '*' E 
 | E '/' E 
 | E '+' E 
 | E '-' E 
 |'(' E ')' 
 
 
Gramáticas Ambíguas 
1 + 2 * 3 
E 
E E 
E E 
* 
+ 3 
2 1 
E 
E E 
E E 
+ 
* 1 
2 3 
Gramáticas Ambíguas 
• Solução: 
– Transformar a gramática 
• * e / com maior precedência que + ou - 
• Operadores associativos a esquerda 
E ::= intLiteral 
 | E '*' E 
 | E '/' E 
 | E '+' E 
 | E '-' E 
 |'(' E ')' 
 
 
 
E ::= E '+' T 
 | E '–' T 
 | T 
T ::= T '*' F 
 | T '/' F 
 | F 
F ::= intLiteral 
 |'(' E ')' 
 
 
Parsing LR de Gramáticas Ambíguas 
• Gramáticas ambíguas ocasionam conflitos em 
parsers LR 
– Shift-reduce conflict 
• O parser não consegue decidir se empilha o próximo 
símbolo da entrada, ou se reduz para uma regra já 
disponível 
– Reduce-reduce conflict 
• O parser pode realizar uma redução para duas regras 
distintas 
Parsing LR de Gramáticas Ambíguas 
• Caso clássico: dangling-else 
 
S ::= 'if' E 'then' S 'else' S 
S ::= 'if' E 'then' S 
S ::= ... 
 
 
Parsing LR de Gramáticas Ambíguas 
if a then if b then s1 else s2 
if a then { if b then s1 else s2 } 
if a then { if b then s1 } else s2 
? 
Parsing LR de Gramáticas Ambíguas 
if a then if b then s1 else s2 Input: 
Stack: 
if a then if b then s1 
reduce St ? 
shift else ? 
St 
Optando pelo reduce... 
else s2 
Parsing LR de Gramáticas Ambíguas 
if a then if b then s1 else s2 Input: 
Stack: 
if a then if b then s1 
reduce St ? 
shift else ? 
else s2 
Optando pelo shift... 
St 
Parsing LR de Gramáticas Ambíguas 
• Solução: 
– Transformar a gramática 
• Introdução dos conceitos de matched e unmatched 
 
 
S ::= 'if' E 'then' S 'else' S 
S ::= 'if' E 'then' S 
S ::= ... 
 
 
S ::= M 
 | U 
 
M ::= 'if' E 'then' M 'else' M 
 | ... 
 
U ::= 'if' E 'then' S 
 | 'if' E 'then' M 'else' U 
LR(0) LL(0) 
SLR 
LALR(1) 
LL(k) 
LL(1) 
Gramáticas não-ambíguas Gramáticas 
ambíguas 
LR(1) 
LR(k) 
Sintaxe abstrata 
• Apenas reconhecer se uma sentença pertence ou não a 
linguagem especificada por uma gramática não é o 
suficiente 
 
• É necessário produzir uma estrutura que sirva de base 
para a próxima fase do processo de compilação 
– Parse trees nunca são montadas na prática 
 
AST – Abstract Syntax Tree 
• Capturam a essência da estrutura de uma gramática 
abstraindo não-terminais 
 
• Representação possível 
– Java: Classes que possam se relacionar a fim de montar uma 
árvore 
 
• Pode ser produzida através da inserção de ações 
semânticas no parser 
AST – Abstract Syntax Tree 
IfThenElse ::= 'if' expr 'then' comm1 'else' comm2 
return new IfThenElse(expr, comm1, comm2); 
Vantagem dos parsers LR 
• Reconhecem praticamente todas as construções 
de linguagens de programação expressas por 
gramáticas independentes de contexto 
• É o melhor método conhecido para parsers não 
recursivos com instruções shift-reduce, mantendo 
o grau de eficiência 
118 
Vantagem dos parsers LR (cont.) 
• A classe das gramáticas que podem ser derivadas 
com parsers LR contém a classe das gramáticas 
que podem ser derivadas usando parser 
preditivos 
• Pode detectar rapidamente erros, assim que seja 
possível numa pesquisa da entrada da esquerda 
para a direita 
119 
Yacc – gerador de parsers 
• YACC – Yet Another Compiler-Compiler 
• Tradução para um programaem C usando o 
método LALR 
• fich.y  compilador yacc  y.tab.c 
• y.tab.c  compilador C  a.out 
• entrada  a.out  saída 
120 
Programa em yacc 
 
 Declarações 
%% 
 Regras de tradução 
%% 
 Rotinas em C 
121 
Declarações 
• Declarações em C entre %{ e %} – tradução direta 
para C: 
enum{FALSE,TRUE}; 
• Declaração de tokens: 
%token INTEIRO REAL 
• Precedência e associatividade de operadores 
122 
Regras de tradução 
• X  Y1 | Y2 | ... | Yn 
• X : Y1 { Ação semântica 1 } 
 | Y2 { Ação semântica 2 } 
 ... 
 | Yn { Ação semântica n } 
 ; 
123 
Terminais e não terminais 
• Strings de letras e dígitos declarados como tokens 
são terminais 
• Caracteres na forma ‘c’ são terminais 
(correspondem a um token representado apenas 
pelo próprio carácter) 
• Todas as outras strings são não terminais 
124 
Valores de atributos 
• $$ – valor de atributo do lado esquerdo da regra 
• $i – valor de atributo do elemento de ordem i do 
lado direito 
• Exemplo: 
• Expr : expr ‘+’ term { $$ = $1 + $3 } 
 | term 
 ; 
125 
Interface com o analisador léxico 
• O yacc comunica com o analisador léxico 
chamando a função yylex 
• Os atributos são passados a partir da variável 
global yylval 
• Usando o lex/flex podemos gerar o analisador 
léxico, que poderá ser usado fazendo #include 
“lex.yy.c” 
• Compilação: gcc y.tab.c -ly -ll 
126 
Resolução de conflitos 
• Conflitos reduce/reduce – é usado o primeiro a 
ser listado na especificação do yacc 
• Conflitos shift/reduce – é resolvido escolhendo o 
shift 
 
127 
Associatividade e precedência 
• Associatividade: 
%left ‘+’ ‘-’ 
%right ‘^’ 
%noassoc ‘<‘ 
• Precedência: 
%prec terminal 
128 
Análise Semântica 
Prof. Wanderson Senra Michel 
wanderson.senra@udf.edu.br 
IV – Análise semântica 
• Associação de regras semânticas a produções 
• Bibliografia aconselhada: 
– Aho, Sethi e Ullman – capítulo 5.1 a 5.4 
 130 
Tradução orientada pela sintaxe 
• Existem duas formas de associar regras 
semânticas a produções 
– Definições orientadas pela sintaxe (gramática de 
atributos): especificações de alto nível para traduções 
– Esquemas de tradução: indicam a ordem de avaliação 
das regras semânticas 
 131 
Gramática de atributos 
• Gramática independente de contexto onde cada símbolo 
gramatical (nó na árvore de derivação) tem associado um 
conjunto de atributos 
• Estes atributos podem ser: 
– Sintetizados: valor obtido a partir dos filhos 
– Herdados: valor obtido a partir do pai ou outros descendentes 
deste 
• Os atributos podem ser qualquer coisa: número, tipo, 
endereço de memória, etc... 
 132 
Exemplo – calculadora 
 133 
PRODUÇÃO REGRA SEMÂNTICA 
L  E ‘\n’ Print(E.val) 
E  E1 + T E.val=E1.val+T.val 
E  T E.val=T.val 
T  T1 * F T.val=T1.val*F.val 
T  F T.val=F.val 
F  ( E ) F.val=E.val 
F  INT F.val=INT.val 
Exemplo – declaração de variável 
 134 
PRODUÇÃO REGRA SEMÂNTICA 
D  T L L.herd = T.tipo 
T  int T.tipo=inteiro 
T  real T.tipo=real 
L  L1 , ID L1.herd=L.herd 
ad_tipo(ID.entr,L.herd) 
L  ID ad_tipo(ID.entr,L.herd) 
Esquemas de tradução 
• Gramática independente de contexto onde 
existem atributos associados aos símbolos 
gramaticais e as ações semânticas são colocadas 
entre chaves 
• O valor do atributo tem que estar disponível 
quando for usado 
 135 
Exemplo – calculadora 
L  E ‘\n’ { Print(E.val) } 
E  E1 + T { E.val = E1.val+T.val } 
E  T { E.val = T.val } 
T  T1 * F { T.val = T1.val*F.val } 
T  F { T.val = F.val } 
F  ( E ) { F.val = E.val } 
F  INT { F.val = INT.val } 
 136 
Exemplo – declaração de variável 
D  T {L.herd = T.tipo} L 
T  int {T.tipo = inteiro} 
T  real {T.tipo = real} 
L  {L1.herd = L.herd} L1 , ID 
 { ad_tipo(ID.entr,L.herd) } 
L  ID { ad_tipo(ID.entr,L.herd) } 
 137 
Exemplo – notação pós fixa 
E  T E’ 
E’  + T { Print(‘+’) } E’ |  
T  F T’ 
T’  * F { Print(‘*’) } T’ |  
F  INT { Print(INT.val) } | ( E ) 
 138 
IV – Análise semântica 
• Implementação da tabela de símbolos 
• Verificação estática 
• Bibliografia aconselhada: 
– Aho, Sethi e Ullman – capítulo 6 
– Crespo – capítulo 6 
 139 
Tabelas de símbolos 
• Inserção e pesquisa eficiente dos identificadores 
• Capacidade de armazenar atributos para 
diferentes tipos de identificadores 
• Visibilidade nas várias fases da compilação 
• Versatilidade na verificação de tipos 
 140 
Árvores binárias 
• Inserção ordenada de 
informação 
• Pesquisa de informação 
eficiente 
• Existência de algoritmos 
de balanceamento de 
árvores binárias 
 141 
Tabelas de hashing 
• Divisão da informação em 
várias parcelas 
• Função de hashing: 
Função simples que faz 
essa divisão e acessa 
rapidamente o local de 
armazenamento 
 142 
Verificação estática 
• Verificação de tipos: verificar se os tipos de duas 
variáveis numa operação são compatíveis 
• Verificação de fluxo de controle: verificar se 
algumas instruções de fluxo de controle estão 
bem definidas: 
– goto label só é possível se existir label 
– break só é possível dentro de um ciclo 
 143 
Verificação estática (cont.) 
• Unicidade: verificação da unicidade de algumas 
construções: 
– funções definidas uma única vez 
– switch-case com alternativas únicas 
• Verificação relacionada com nomes 
 144 
Verificação de tipos 
• Verificação de tipos pode ser realizada em: 
– Expressões 
– Instruções 
– Funções 
• Equivalência de tipos 
• Conversão de tipos 
• Tipos polimórficos 
• Funções polimórficas 
 145