Compiladores - Unidade 1

Prévia do material em texto

E-Book	-	Apostila
Esse	arquivo	é	uma	versão	estática.	Para	melhor	experiência,	acesse	esse	conteúdo	pela	mídia	interativa.
Unidade	1	-	Estrutura	de	um	compilador
E-Book	-	Apostila
E-Book	-	Apostila
2	-	32
Introdução	da	disciplina
ESPECIALISTA	EM
GESTÃO	PÚBLICA,
GESTÃO	BANCÁRIA	E
NEGÓCIOS.
ESPECIALISTA	EM
MÍDIAS	NA	EDUCAÇÃO.
GRADUADO	EM
ADMINISTRAÇÃO	E	EM
SISTEMAS	PARA
INTERNET.
Gilberto	Aneide	Camargo
Dutra
DOUTOR	EM
ENGENHARIA
BIOMÉDICA
COMPUTACIONAL.
João	Carlos	Lopes
Fernandes
Olá,	estudante!	Tudo	bem?	Para	darmos	início	ao	nosso	conteúdo,	assista	ao	vídeo
de	apresentação	a	seguir.
Recurso	Externo
E-Book	-	Apostila
3	-	32
Recurso	é	melhor	visualizado	no	formato	interativo
Agora,	vamos	dar	início	à	nossa	unidade!
Introdução	da	unidade
Nesta	 unidade,	 falaremos	 sobre	 a	 gramática	 e	 as	 linguagens	 livres	 de	 contexto,
bem	como	suas	definições	e	notações	formais.	Ademais,	estudaremos	sobre	como
representar	uma	árvore	derivativa,	 responsável	por	apresentar,	de	 forma	gráfica,
as	derivações	de	uma	linguagem	livre	de	contexto	e	os	resultados.	Em	um	segundo
momento,	abordaremos	as	 linguagens	de	programação,	responsáveis	por	permitir
o	 entendimento	 entre	 máquina	 e	 programador.	 Aqui,	 o	 foco	 será	 o	 estudo
relacionado	 aos	 compiladores,	 que	 são	 capazes	 de	 receber	 um	 código-fonte	 e
transformá-lo	 em	 programa	 equivalente,	 relatando	 os	 possíveis	 erros.	 Ao	 final,
falaremos	sobre	a	construção	de	compiladores	e	de	ferramentas	compiladoras,	que
são	capazes	de	gerar	sistemas	simples,	a	partir	de	códigos	complexos,	oferecendo
geração	de	analisadores	e	gerenciamento	de	erros.
Vamos	lá?!	Bons	estudos!
Gramática	livre	de	contexto
Iniciaremos	fazendo	uma	breve	revisão	sobre	gramática	livre	de	contexto	e	já	com
uma	pergunta.	
O	que	é	gramática?
E-Book	-	Apostila
4	-	32
Segundo	 o	 Dicionário	 Online	 de	 Português	 (2022),	 gramática	 (do	 grego
grammatiké,	 "arte	 das	 letras";	 e	 do	 latim	grammatica,	 "gramática")	 é	 o	 "[...]
conjunto	de	princípios	que	regem	o	funcionamento	de	uma	língua,	determinando	o
uso	considerado	correto	de	uma	língua",	ou	seja,	refere-se	a	regras	e	estabelece	o
que	é	"proibido"	ou	"permitido"	ao	escrever	ou	falar	em	um	dado	idioma.
Noam	 Chomsky,	 linguista	 norte-americano,	 reverenciado	 no	 mundo	 acadêmico
como	 o	 "pai	 da	 linguística	 moderna",	 concebeu	 uma	 hierarquia	 de	 linguagens
(hierarquia	 de	 Chomsky),	 conforme	 a	 figura	 a	 seguir,	 composta	 por	 linguagens
enumeráveis	 recursivamente,	 linguagens	 sensíveis	 ao	 contexto,	 linguagens	 livre
de	contexto	(objeto	do	nosso	estudo)	e	linguagens	regulares.
FIGURA	1	-	Hierarquia	de	Chomsky
Fonte:	Elaboração	do	autor,	2022.
Nas	linguagens	formais,	a	gramática	(G)	é	responsável	pelo	grupo	de	regramentos
aplicados	a	elementos	(símbolos	terminais	ou	não	terminais),	permitindo	a	geração
de	cadeias	(ou	strings),	que	pertencem	a	uma	linguagem	(L).	Consequentemente,
uma	gramática	G	define	uma	linguagem	L,	denotando-se	da	seguinte	forma:	L(G).
Dessa	maneira,	a	gramática	formal	pode	ser	definida	assim:
E-Book	-	Apostila
5	-	32
G	=	(V,	T,	P,	S),	em	que:
V:	conjunto	de	variáveis	ou	símbolos	não	terminais.
T:	conjunto	de	símbolos	terminais.
P:	conjunto	de	regras	de	derivação.
S:	símbolo	(variável)	não	terminal	inicial.
Nessa	 definição,	 as	 produções	 de	G	 relacionam	 as	 variáveis	V	 entre	 si	 e/ou
símbolos	 terminais	 de	T,	 estabelecendo	as	 regras	que	nortearão	a	 construção	de
cadeias	 de	 linguagem	 especificada	 pela	 gramática.	 Buscando	 facilitar	 a	 notação,
convenciona-se	que:
(Clique	nas	setas	para	avançar	ou	retornar	o	conteúdo)
variáveis	são	denotadas	por	letras	latinas	maiúsculas	do	início	do
alfabeto	(A,	B,	C,	...);
terminais	são	representadas	por	letras	latinas	minúsculas	do
início	do	alfabeto,	dígitos	e	símbolos	especiais	(a,	b,	c,	...,	0,	1,	2,
...,	*,	+	etc.);
formas	sentenciais	são	indicadas	por	letras	gregas	minúsculas	do
início	do	alfabeto	(α,	β,	γ,	...);
cadeias	 são	 representadas	 por	 letras	 latinas	 do	 fim	 do	 alfabeto
(w,	x,	y,	z,	...).
E-Book	-	Apostila
6	-	32
A	seguir,	falaremos	sobre	derivação	e	redução.	Confira!
Derivação	e	redução
A	derivação	ocorre	quando	há	a	substituição	do	 lado	esquerdo	de	uma	sequência
(ou	 de	 parte	 dos	 caracteres,	strings)	 de	 uma	 gramática	 pelos	 símbolos	 do	 lado
direito.	Já	a	redução	é	o	resultado	dessa	derivação.
Para	aprofundar	um	pouco	mais	o	conhecimento	obtido	até	aqui,	assista	ao	vídeo	a
seguir,	 que	 fala	 sobre	 a	 derivação	 e	 a	 redução,	 apresentando	 importantes
considerações	acerca	da	temática	desta	unidade.
Recurso	Externo
Recurso	é	melhor	visualizado	no	formato	interativo
A	partir	do	que	foi	apresentado	no	vídeo,	podemos	continuar	falando	da	derivação
e	da	redução.	Vamos	lá?!
Derivação	mais	à	direita	e	mais	à	esquerda
Seja	 a	 derivação	 S	 ⇒	 α	 ⇒	 β,	 em	 que	 definimos	 que	 β	 é	 resultado	 de	 α,	 pela
substituição	de	um	não	terminal	de	α.	Então,	constatamos	que:
uma	 derivação	 mais	 à	 esquerda	 é	 resultado	 da	 substituição	 de
um	símbolo	presente	mais	à	esquerda;
uma	 derivação	mais	 à	 direita	 é	 resultado	 da	 substituição	 de	 um
símbolo	presente	mais	à	direita.
E-Book	-	Apostila
7	-	32
Desse	 modo,	 entendemos	 que	 α	 é	 uma	 derivação	 à	 esquerda	 ou	 à	 direita,
respectivamente,	quando	 é	 obtido	 de	 uma	derivação	mais	 à	 esquerda	 ou	mais	 à
direita.	As	derivações	da	 sentença	“-	 (	 id	+	 id	 )”	a	 seguir	 são	exemplos,	 sendo	a
primeira	mais	à	esquerda,	e	a	segunda,	mais	à	direita.	
(Passe	o	mouse	no	(+)	e	confira	o	conteúdo	abaixo)
Tendo	 em	 vista	 a	 complexidade	 das	 gramáticas	 livres	 de	 contexto,	 é	 necessário
analisar,	 por	 outro	 ângulo,	 sua	 construção,	 mediante	 definições,	 convenções,
derivações	e	exemplos	comentados.	Ademais,	é	possível	afirmar	que	elas	são	tidas
como	superiores	às	expressões	regulares,	que	também	são	livres	de	contexto.
SAIBA	MAIS
derivação	mais	à	esquerda:
E	→	-	E	→	-	(	E	)	→	-	(	E	+	E	)	→	-	(	id	+	E	)	→	-	(	id	+	id	)
derivação	mais	à	direita:
E	→	-	E	→	-	(	E	)	→	-	(	E	+	E	)	→	-	(	E	+	id	)	→	-	(	id	+	id	)
E-Book	-	Apostila
8	-	32
Leia	 as	 páginas	 125	 a	 131	 do	 livro	 indicado	 a	 seguir,	 em	que	 os	 autores
abordam	 a	 sintaxe	 da	 construção	 das	 linguagens	 de	 programação	 e	 as
definições	da	gramática	 livre	de	contexto,	com	exemplos	de	expressões	e
de	 convenções	 de	 notação.	 Ademais,	 os	 autores	 explicam	 como	 ocorre	 a
derivação	e	 falam	 sobre	 a	 construção	de	uma	árvore	 de	derivação,	 entre
outros	assuntos.
Acesse	sua	biblioteca	virual	e	confira	a	leitura	disponível	no	link:
https://plataforma.bvirtual.com.br/Leitor/Publicacao/280/pdf/0
Agora	que	 já	compreendemos	que	a	gramática	é	responsável	pelo	regramento	de
uma	linguagem,	estamos	prontos	para	aprender	sobre	linguagem	de	programação
e	compiladores.
Linguagem	de	programação
Desde	sempre,	os	computadores	precisam	receber	dos	usuários	e	programadores
instruções	de	entrada	para	processamento.	Esse	processamento	exige	a	execução
de	 sistemas	 ou	 programas,	 sendo	 resultado	 de	 um	 conjunto	 de	 instruções	 que
determinam	o	que	a	máquina	deve	 fazer.	Segundo	Price	e	Toscani	 (2001,	p.	1):	 "
[...]	 no	 início	 não	 tínhamos	 programas	 como	 conhecemos	 hoje,	 os	 computadores
eram	limitados	e	com	baixo	poder	de	processamento.	As	instruções	eram	inseridas
utilizando	notação	binária,	produzindo	uma	comunicação	entre	usuário	e	máquina
direta,	e	usando	sequências	de	zeros	e	uns".
Com	 o	 passar	 dos	 anos,	 a	 programação	 usando	 notação	 binária	 foi	 ficando	 cada
vez	 mais	 complexa,	 principalmente	 com	 o	 aumento	 do	 poder	 de	 processamento
dos	 computadores.	 Foi	 necessário,	 então,	 encontrar	 uma	 forma	 mais	 intuitiva	 e
prática	 de	 enviar	 instruções	 às	 máquinas	 e	 escrever	 programas.	 Nesse	 sentido,
começaram	 a	 ser	 desenvolvidas	 as	 linguagens	 de	 programação,	 bem	 como
tradutores.
As	 linguagens	 de	 programação,	 diferentemente	 das	 linguagens	 naturais,	 têm	 um
únicoobjetivo:	comunicar	comandos	computacionais	por	meio	de	um	conjunto	de
palavras-chaves,	símbolos,	ordens	e	regras	sintáticas	e	semânticas,	compostos	por
dados	 e	 algoritmos	 responsáveis	 por	 permitir	 o	 entendimento	 entre	 máquina	 e
programador.	Essas	 linguagens	chegam	às	máquinas	por	meio	de	tradutores,	que
se	dividem	em	compiladores	e	interpretadores.
https://plataforma.bvirtual.com.br/Leitor/Publicacao/280/pdf/0
E-Book	-	Apostila
9	-	32
Compiladores
De	acordo	 com	Louden	 (2004),	 os	 compiladores	 são	 sistemas	de	 informática	 que
transformam	 uma	 linguagem	 compreensível	 por	 humanos	 em	 um	 código
compreensível	 por	máquinas.	Um	 compilador	 recebe	 como	entrada	 um	programa
escrito	 na	 linguagem-fonte	 e	 produz	 um	 sistema	 resultado	 na	 linguagem-alvo.
Costumeiramente,	 o	 código-fonte	 é	 construído	 com	uma	 linguagem	de	 alto	 nível,
como	C++	ou	C.	A	linguagem-alvo	é	um	código-objeto.
REFLITA
Quando	se	inventou	o	computador,	criou-se	uma
máquina	a	mais;	quando	se	criou	o	compilador,
criou-se	uma	nova	era	tecnológica.
Segundo	Aho	et	al.	(2008,	p.	1):
E-Book	-	Apostila
10	-	32
A	fim	de	compreender	melhor	essa	ideia,	observe	a	figura	a	seguir.
FIGURA	1	-	Compilador
Fonte:	AHO	et	al.,	2008,	p.	1.
[...]	colocando	de	forma	bem	simples,	um	compilador
é	 um	 programa	 que	 recebe	 como	 entrada	 um
programa	 em	 uma	 linguagem	 de	 programação	 –	 a
linguagem-fonte	 –	 e	 o	 traduz	 para	 um	 programa
equivalente	em	outra	linguagem	–	a	linguagem-objeto
[...].	 Um	 papel	 importante	 do	 compilador	 é	 relatar
quaisquer	 erros	 no	 programa-fonte	 detectados
durante	esse	processo	de	tradução.
E-Book	-	Apostila
11	-	32
As	 linguagens	 de	 programação	 evoluíram	 muito	 ao	 longo	 dos	 anos,	 das	 mais
simples,	do	ponto	de	vista	da	máquina,	até	as	de	alto	nível,	tidas	como	mais	fáceis
para	o	entendimento	humano.	Em	meados	de	1950,	surgiu	a	Assembly,	linguagem
simples	 para	 os	 computadores,	mas	 tida	 como	 complexa	 para	 os	 programadores
humanos.	 Buscando	 melhorar	 essa	 relação,	 muitas	 linguagens	 surgiram	 depois
disso.	 Em	 1954,	 surgiu	 o	 Fortran,	 linguagem	 de	 programação	 conhecida	 como
percursora	 das	 linguagens	 de	 alto	 nível.	 Em	 1960,	 surgiu	 o	 ALGOL,	 linguagem
conhecida	também	como	uma	importante	linguagem	científica.
A	 primeira	 linguagem	 que	 se	 popularizou	 comercialmente	 surgiu	 em	 1958,	 o
COBOL.	 Atualizada	 até	 2002,	 ela	 ainda	 pode	 ser	 encontrada	 em	 diversas
aplicações	do	nosso	dia	a	dia.	Exemplos	disso	são	os	famosos	sistemas	de	tela	azul
ou	preta	com	letras	cinzas	ou	verdes	utilizados	em	redes	de	varejos	ou	instituições
bancárias	antes	do	advento	dos	sistemas	web.
Em	1970,	 surgiu	a	PASCAL,	 linguagem	que	permitia	aos	usuários	definirem	 tipos.
Os	 sistemas	web	 trouxeram	 linguagens	 como	 Java,	 Python,	 Perl,	 Visual	 Basic	 e
PHP,	todas	com	orientação	a	objeto.	Quando	falamos	em	IA	(Inteligência	Artificial),
é	 importante	citar,	ainda,	o	surgimento,	em	1960,	da	linguagem	Lisp,	que	evoluiu
para	 Common	 Lisp,	 e	 da	 linguagem	 Prolog,	 nos	 anos	 1970.	 Na	 atualidade,
merecem	destaque:	Python,	C++/C,	Lua,	Java,	JavaScript	e	Swift.
No	infográfico	a	seguir,	apresentaremos	as	principais	linguagens	de	programação,
de	1940	até	1990.
(Clique	nos	(•)	para	visualizar	o	conteúdo)
Recurso	Externo
Recurso	é	melhor	visualizado	no	formato	interativo
Agora	que	você	já	conhece	as	principais	linguagens	de	programação,	é	necessário
conhecer	alguns	princípios	relativos	a	elas.
E-Book	-	Apostila
12	-	32
REFLITA
Na	 atualidade,	 temos	 uma	 série	 de	 novas
linguagens	orientadas	a	objeto	para	aplicação	web.
Assim,	 chegaremos	 ao	 dia	 em	 que	 as	 linhas	 de
código	não	serão	mais	necessárias.	A	programação
será	toda	por	comandos	de	voz	e	gráfica?
Podemos	citar	quatro	princípios	para	uma	 linguagem	de	programação	e	aplicação
de	suas	técnicas	formais	que	permitem	o	desenvolvimento	de	um	compilador.	São
eles:	tipos,	nomes,	semântica	e	sintaxe.	Esse	conhecimento	é	imprescindível,	pois
é	possível	surgir	oportunidades	de	criar	ou	participar	de	um	projeto	de	uma	nova
linguagem.	Saiba	mais	clicando	nas	sanfonas	a	seguir.
Tipos
Tipos	 são	 os	 indicativos	 para	 o	 programador	 implementar	 as	 estruturas	 de
armazenamento	de	dados	e	de	execução	de	cálculos.
E-Book	-	Apostila
13	-	32
Nomes
Nomes	 são	 o	 conjunto	 de	 normas	 a	 serem	 seguidas.	 Por	 exemplo,	 em	 Java,
uma	 variável	 pode	 conter	 letras,	 números	 e	 o	 caractere	 sublinhado	 (_),	 mas
não	pode	começar	com	um	número.
Semântica
A	 semântica,	 nos	 programas,	 diz	 respeito	 aos	 comandos	 com	 valores
determinados,	 tida	 como	 importante	 porque	 permite	 que	 os	 programadores
tenham	 um	 conhecimento	 preciso	 acerca	 das	 instruções	 da	 linguagem.	 Por
exemplo:
Calcule	(	t1,	t2);	/*
calcule	(	t1,	t2);	/*	é	uma	função;	a	semântica	avalia	se	o	método	aceita	dois
parâmetros	e	se	seus	tipos	e	resultado	são	compatíveis.
Por	 fim,	a	sintaxe	abrange	as	 regras	e	 os	 regulamentos	utilizados	para	escrever
qualquer	 instrução	 em	 uma	 linguagem	 de	 programação,	 pertencendo	 ao
formalismo	das	gramáticas	livres	de	contexto.
Interpretadores
Os	interpretadores	são	tradutores	que	leem	um	código-fonte	de	uma	linguagem	de
programação	 interpretada	 e	 o	 converte	 em	 código	 executável.	 Um	 programa
interpretador	 clássico	 é	 o	 BASIC,	 utilizado,	 geralmente,	 em	 ocasiões	 especiais.
Atualmente,	o	Smalltalk,	uma	 linguagem	de	programação	orientada	a	objeto,	 tem
sido	 muito	 difundido.	 Os	 comandos	 (linhas	 de	 código-fonte)	 executam	 todas	 as
fases	de	tradução	até	obter	o	código-alvo,	executando-o	 imediatamente.	Por	esse
motivo,	exigem	a	submissão	a	interpretadores	sempre	que	executados.
E-Book	-	Apostila
14	-	32
A	figura	a	seguir	demonstra	o	funcionamento	de	um	interpretador.	As	entradas	são
o	programa-fonte	e	a	entrada	do	usuário,	 em	que	o	 interpretador	produz	a	 saída
correspondente.
FIGURA	1	-	Árvore	derivativa
Fonte:	Elaboração	do	autor,	2022.
De	acordo	com	Aho	et	al.	(2008,	p.	2),	"[...]	um	interpretador	é	capaz	de	executar
um	 melhor	 diagnóstico	 de	 erros	 que	 os	 compiladores,	 por	 executar	 o	 código
'instrução	por	 instrução',	enquanto	que	os	compiladores	apresentam	agilidade	na
entrada	e	saída	de	informações/dados".	Podemos	entender,	então,	que	não	há	uma
tradução	 nesses	 casos,	 mas	 uma	 interpretação	 do	 código-fonte	 e	 da	 entrada	 de
informação.	 Esse	 processo	 é	 lento	 e,	 geralmente,	 exige	 mais	 capacidade	 de
espaço.	Um	bom	exemplo	dessa	linguagem	é	o	Java,	explicando	nossa	costumeira
reclamação	de	lentidão	nos	programas	gerados.	Outros	exemplos	de	interpretação
são:	PHP,	Scheme	e	Python.
Clique	 nas	 sanfonas	 a	 seguir	 e	 conheça	 um	 pouco	 mais	 as	 vantagens	 e
desvantagens	da	compilação	com	relação	à	interpretação.
E-Book	-	Apostila
15	-	32
Vantagens	da	compilação	com	relação	à	interpretação
Execução	rápida,	já	que	não	necessita	de	qualquer	tradução.
Economia	de	memória	na	execução.
Maior	controle	sobre	o	código	produzido.
Permite	a	otimização	do	código.
Resulta	 em	 uma	 programa	 eficiente	 que	 interage	 diretamente
com	a	máquina.
Desvantagens	da	compilação	com	relação	à	interpretação
Inadequada	 a	 usuários	 inexperientes,	 considerando	 que,	 para	 a
verificação	de	erros,	é	necessário	compilar	o	programa	inteiro;	 já
o	 interpretador	 pausa	 o	 programa	 durante	 a	 execução	 para	 a
correção	do	erro.
Perde-se	 a	 referência	 com	 o	 código-fonte,	 dificultando	 o
apontamento	do	resultado	do	erro.
Construção	complexa.
Permite	 desenvolver	 máquinas	 virtuais	 para	 plataformas
diversificadas,	 resultando	 na	 geração	 de	 códigos	 intermediários
de	alta	portabilidade.
No	próximo	tópico,	vamos	conhecer	as	fases	de	um	compilador.
Fases	de	um	compilador
As	 fases	de	um	compilador	 são	duas:	 a	 fase	de	análise	e	a	 fase	de	 síntese.	Essa
divisão	objetiva	trazer	uma	visão	explícita	e	detalhada	do	processo	de	compilação.
Na	figura	a	seguir,	podemos	observar	as	fases	de	umcompilador.	Nela,	o	fluxo	de
processos	 é	 executado	 durante	 a	 análise,	 com	 uma	 síntese	 de	 suas	 respectivas
etapas,	iniciando	no	programa-fonte	até	chegar	ao	código	final-alvo.
E-Book	-	Apostila
16	-	32
FIGURA	1	-	Fases	de	um	compilador
Fonte:	Elaboração	do	autor,	2022.
Fase	de	análise	ou	front-end
Essa	fase	particiona	o	programa	em	partes	estruturadas	pela	gramática,	sendo	sua
principal	 tarefa	 garantir	 que	 a	 sintaxe	 e	 a	 semântica	 do	 programa	 estejam
corretas,	 ou	 seja,	 ela	 verifica	 se	 o	 código-fonte	 está	 correto,	 de	 acordo	 com	 as
regras	 da	 linguagem.	 Podemos	 dividir	 a	 análise,	 ainda,	 em	 três	 partes,	 segundo
Aho	et	al.	(2008,	p.	3).
Léxica	ou	leitura	(scanning)
A	léxica	ou	leitura	(scanning)	é	responsável	por	verificar	se	os	nomes	das
entidades	do	programa-fonte	estão	corretos,	transformando	o	texto	em	um	fluxo
de	tokens	e	criando	as	tabelas	de	símbolos.	Os	tokens	constituem	classes	de
símbolos,	tais	como	palavras	reservadas,	delimitadores,	identificadores	etc.
E-Book	-	Apostila
17	-	32
Exemplo:
Enunciado:	–	montante	:=	depósito	+	taxa	*	55
																				–	m1	:=	a2	+	b3	*	55
Sintática
A	sintática	é	a	fase	que	verifica	se	os	comandos	estão	corretos,	seja	nas	palavras
correspondentes,	 seja	 na	 sua	 ordem.	 Além	 disso,	 efetua	 uma	 leitura	 do	 fluxo	 de
tokens,	validando	sua	estrutura	e	criando	a	árvore	sintática.
Exemplo:
–	while	<expressão>	do	;
A	 estrutura	 <expressão>	 deve	 se	 apresentar	 sintaticamente	 correta,	 e	 sua
avaliação	deve	retornar	um	valor	do	tipo	lógico.
Semântica
E-Book	-	Apostila
18	-	32
A	semântica	é	a	fase	responsável	por	garantir	que	as	regras	de	semântica	sejam
cumpridas,	verificando	o	contexto	e	se	os	comandos	inseridos	no	código-fonte	são
compatíveis.
Exemplo:
Verifica	 variáveis	 declaradas	 e	 não	 utilizadas,	 bem	 como
incompatibilidade	de	tipos,	variável	utilizada	e	não	declarada
etc.
Fase	de	síntese	ou	back-end
A	 fase	 de	 síntese	 visa	 construir	 o	 programa-objeto,	 a	 partir	 da	 representação
intermediária	desenvolvida	na	fase	de	análise.
Gerenciamento	da	tabela	de	símbolos
É	a	tabela	responsável	pelas	 informações	(nomes,	tipos	e	atributos),	consultada	e
alimentada	pelo	compilador.	Deve	ser	montada	de	forma	que	possibilite	a	extração
rápida	e	a	inserção	de	dados,	mas	sem	deixar	de	ser	compacta.
E-Book	-	Apostila
19	-	32
Exemplo:
Para	 variáveis:	 classe	 (var),	 tamanho,	 precisão,
tipo.
Parâmetros	formais:	classe	(par),	tipo.
Subrotinas:	classe	(proc),	número	de	parâmetros.
Geração	do	código	intermediário
É	o	código-alvo,	criado	em	etapas.	As	instruções	são	representadas	em	até	três
endereços.
Exemplo:
x	=	a	+	b	/	raiz(5)
t1	=	raiz(5)
t2	=	b	/	t1
t3	=	a	+	t2
x	=	t3
E-Book	-	Apostila
20	-	32
Otimização	do	código
Aqui,	devemos	transformar	o	código-fonte	para	obter	um	código	limpo	que	permita
que	a	máquina	diminua	o	seu	tempo	de	execução,	o	consumo	de	memória	e/ou	o
tamanho	do	código.
Exemplo:
Enunciado:	x1	:=	a1	+	a2	*	53
t1:=	inttoreal	(53)
t2	:=	a2	*	t1
t3	:=	a1	+	t2
x1	:=	t3
t1	:=	a2	*	53
x1	:=	a1	+	t1
Geração	do	código
É	a	 fase	de	conclusão,	ou	seja,	a	 fase	 final,	que	mostra	o	código	pronto	para	ser
executado	e	comercializado.
Construindo	compiladores
E-Book	-	Apostila
21	-	32
As	 técnicas	 de	 desenvolvimento	 de	 compiladores	 são	 amplamente	 difundidas	 no
campo	 da	 ciência	 da	 computação.	 São	 técnicas	 com	 algoritmos	 e	 estruturas	 de
dados	 que	 integram	 os	 compiladores.	 Exemplos:	 tabelas	 pré-calculadas,
mecanismo	de	pilhas,	teoria	dos	grafos,	alocação	de	memória,	estrutura	de	dados
etc.
Pensando	na	temática	da	construção	de	compiladores,	assista	ao	vídeo	a	seguir.
Recurso	Externo
Recurso	é	melhor	visualizado	no	formato	interativo
Temos,	ainda,	como	opções	de	aplicações	compiladoras:	JavaCC	e	LISA.	O	JavaCC	é
uma	ferramenta	bastante	popular	e,	segundo	Rebelo	(2002),	permite	a	geração	de
programas	simples	e	de	alta	complexidade	para	 linguagens	em	C++	e	 Java,	bem
como	para	ferramentas	de	análise	gramatical	e	de	transformação	de	código-fonte.
Além	disso,	permite	a	geração	de	analisadores	léxicos	e	sintáticos	com	capacidade
de	 depuração	 e	 de	 gerenciamento	 de	 erros.	 O	 JavaCC	 inclui	 como	 ferramentas
adicionais	o	JJDoc	e	o	JJtree.
A	 primeira	 gera	 documentação	 em	 HTML,	 e	 a	 segunda	 permite	 construir,
automaticamente,	ações	para	a	estrutura	de	árvore,	durante	a	análise	gramatical
de	 um	 sistema.	 Conforme	 Rebelo	 (2002),	 a	 LISA	 é	 uma	 ferramenta	 capaz	 de
fornecer	 um	 compilador	 utilizando	 métodos	 formais	 (expressões	 regulares),
notação	 BNF	 (Backus-Naur	 Form)	 e	 gramática	 de	 atributos.	 Seu	 ambiente	 é	 tido
como	 amigável	 por	 permitir	 escrever	 e	 descrever,	 formalmente,	 a	 linguagem	 de
maneira	simples	e	rápida.	Ainda,	é	capaz	de	gerar	analisadores	 léxicos,	sintáticos
e	semânticos	em	C++.
Para	 aprofundar	 o	 seu	 entendimento	 sobre	 linguagem	de	programação,	 acesse	 a
dica	a	seguir.
E-Book	-	Apostila
22	-	32
DICA
Leia	 as	 páginas	 5	 a	 9	 do	 livro	 disponibilizado	 no
link	 a	 seguir.	 A	 obra	 fornece	 informações	 claras,
simples	 e	 didáticas	 sobre	 como	 programar	 em
Java,	com	ênfase	inicial	em	objetos.	Trata-se	de	um
livro	 essencial	 para	 alunos	 e	 profissionais	 que
desejam	 aprofundar	 os	 seus	 conhecimentos	 sobre
programação	e	desenvolvimento	de	software.
Acesse	 dua	 biblioteca	 virtual	 e	 confira	 a	 leitura
disponível	 em:
https://plataforma.bvirtual.com.br/Leitor/Publicaca
o/2660/pdf/0
O	desenvolvimento	de	compiladores	e	de	códigos-fonte	sofreu	diversas	mudanças
nas	 últimas	 décadas,	 principalmente	 com	 o	 surgimento	 e	 aperfeiçoamento	 de
ferramentas	 capazes	 de	 interpretar	 e	 de	 gerar	 códigos	 de	 alto	 nível	 por	meio	 da
reutilização	 de	 programas.	 Hoje,	 temos	 à	 nossa	 disposição	 linhas	 de	 códigos	 e
algoritmos	 de	 diferentes	 complexidades,	 como,	 por	 exemplo,	 os	 aplicativos	 em
nossos	smartphones.
https://plataforma.bvirtual.com.br/Leitor/Publicacao/2660/pdf/0
E-Book	-	Apostila
23	-	32
Considerações	finais
Nesta	unidade,	você	teve	a	oportunidade	de:
compreender	os	conceitos	relacionados	a	gramáticas	livres	de
contexto;
entender	o	que	é	uma	árvore	de	derivação;
conhecer	a	evolução	dos	compiladores;
diferenciar	o	front-end	do	back-end;
compreender	as	diferenças	entre	compilador	e	interpretador;
conhecer	ferramentas	para	a	construção	de	compiladores.
Ao	 longo	 do	 material,	 apresentamos	 as	 gramáticas	 livres	 de	 contexto,	 suas
derivações	(árvores	de	derivação	e	derivação	mais	à	direita	ou	mais	à	esquerda)	e
reduções.	 Também	 estudamos	 as	 linguagens	 de	 programação,	 sua	 evolução,
princípios	e	paradigmas.	Ainda,	falamos	sobre	tradutores,	como	os	compiladores	e
interpretadores.	 Os	 compiladores	 foram	 o	 nosso	 foco	 principal,	 então,	 falamos
sobre	sua	conceituação	e	estrutura,	de	modo	a	entender	as	 fases	do	processo	de
compilação.	 Por	 fim,	 abordamos	 a	 construção	 dos	 compiladores	 e	 falamos	 sobre
JavaCC	e	LISA.	Esperamos	que	você	tenha	aproveitado	bastante	o	conteúdo!
Agora	que	finalizamos	o	conteúdo,	vamos	testar	os	seus	conhecimentos	por
meio	do	QUIZ	a	seguir.
QUIZ
E-Book	-	Apostila
24	-	32
Leia	o	enunciado	a	seguir.
Sabendo	que	a	gramática	é	a	responsável	pelo	grupo
de	 símbolos	 não	 terminais	 ou	 terminais	 que
permitem	 a	 geração	 de	strings	 de	 uma	 linguagem,
Noam	 Chomsky,	 linguista	 norte-americano,
concebeu	a	hierarquia	de	linguagens.
E	o	que	seria	essa	hierarquia	de	linguagens?
Assinale	a	alternativa	correta,	a	seguir.
Resposta	Correta:
Resposta	correta.	Noam	Chomsky,	linguista	norte-
americano,	concebeu	uma	hierarquia	de	linguagens,
sendo	esta	composta,	de	fato,	por	linguagens
enumeráveis	recursivamente,	linguagens	sensíveis	ao
contexto,	linguagens	livres	de	contexto	e	linguagens
regulares.
Linguagens	enumeráveis	recursivamente,	linguagens
sensíveis	ao	contexto,	linguagens	livres	de	contexto
e	linguagens	regulares.
a
Linguagens	numeráveis	recursivamente,linguagens
sensíveis	ao	contexto,	linguagens	livres	de	contexto
e	linguagens	regulares.
b
E-Book	-	Apostila
25	-	32
Resposta	Incorreta:
Resposta	incorreta.	Noam	Chomsky,	linguista	norte-
americano,	concebeu	uma	hierarquia	de	linguagens,
sendo	esta	composta	por	linguagens	enumeráveis
recursivamente,	linguagens	sensíveis	ao	contexto,
linguagens	livres	de	contexto	e	linguagens	regulares.
Resposta	Incorreta:
Resposta	incorreta.	Noam	Chomsky,	linguista	norte-
americano,	concebeu	uma	hierarquia	de	linguagens,
sendo	esta	composta	por	linguagens	enumeráveis
recursivamente,	linguagens	sensíveis	ao	contexto,
linguagens	livres	de	contexto	e	linguagens	regulares.
Resposta	Incorreta:
Resposta	incorreta.	Noam	Chomsky,	linguista	norte-
americano,	concebeu	uma	hierarquia	de	linguagens,
sendo	esta	composta	por	linguagens	enumeráveis
recursivamente,	linguagens	sensíveis	ao	contexto,
linguagens	livres	de	contexto	e	linguagens	regulares.
Linguagens	enumeráveis	recursivamente,	linguagens
sensíveis	ao	contexto,	linguagens	livres	de	contexto
e	linguagens	irregulares.
c
Linguagens	enumeráveis	recursivamente,	linguagens
sensíveis	ao	contexto,	linguagens	presas	de	contexto
e	linguagens	regulares.
d
E-Book	-	Apostila
26	-	32
Resposta	Incorreta:
Resposta	incorreta.	Noam	Chomsky,	linguista	norte-
americano,	concebeu	uma	hierarquia	de	linguagens,
sendo	esta	composta	por	linguagens	enumeráveis
recursivamente,	linguagens	sensíveis	ao	contexto,
linguagens	livres	de	contexto	e	linguagens	regulares.
Leia	o	enunciado	a	seguir.
Atualmente,	 um	 desenvolvedor	 de	 compiladores
pode	contar	com	diversas	ferramentas	que	oferecem
recursos	 como	 editores	 de	 texto,	 depuradores,
gerenciamento	 de	 versões,	profilers	 e	 ferramentas
de	testes.
Assinale	 a	 alternativa	 que	 indique	 corretamente
quais	 ferramentas	 podem	 ser	 empregadas	 na
construção	de	compiladores.
Linguagens	enumeráveis	recursivamente,	linguagens
insensíveis	ao	contexto,	linguagens	livres	de
contexto	e	linguagens	regulares.
e
Geradores	de	analisadores	sintáticos,	geradores	de
analisadores	léxicos	e	geradores	de	analisadores
disléxicos.
a
E-Book	-	Apostila
27	-	32
Resposta	Incorreta:
Resposta	incorreta.	As	ferramentas	mais	adequadas
para	uso	são	aquelas	capazes	de	ocultar	os	detalhes
de	seus	algoritmos,	produzindo	resultados	facilmente
integrados	ao	computador,	por	meio	de	linguagens
específicas	e	sofisticadas.	Algumas	ferramentas
empregadas	na	construção	de	compiladores	são:
geradores	de	analisadores	sintáticos;	geradores	de
analisadores	léxicos;	mecanismos	de	tradução	dirigida
por	sintaxe;	geradores	de	códigos;	mecanismos	de
fluxo	de	análise	de	dados;	e	conjunto	de	ferramentas
para	construção	de	compiladores.
Resposta	Incorreta:
Resposta	incorreta.	As	ferramentas	mais	adequadas
para	uso	são	aquelas	capazes	de	ocultar	os	detalhes
de	seus	algoritmos,	produzindo	resultados	facilmente
integrados	ao	computador,	por	meio	de	linguagens
específicas	e	sofisticadas.	Algumas	ferramentas
empregadas	na	construção	de	compiladores	são:
geradores	de	analisadores	sintáticos;	geradores	de
analisadores	léxicos;	mecanismos	de	tradução	dirigida
por	sintaxe;	geradores	de	códigos;	mecanismos	de
fluxo	de	análise	de	dados;	e	conjunto	de	ferramentas
para	construção	de	compiladores.
Geradores	de	analisadores	sintáticos,	geradores	de
analisadores	disléxicos	e	geradores	de	códigos.b
Geradores	de	tabela	de	símbolos,	geradores	de
analisadores	disléxicos	e	geradores	de	códigos.c
E-Book	-	Apostila
28	-	32
Resposta	Incorreta:
Resposta	incorreta.	As	ferramentas	mais	adequadas
para	uso	são	aquelas	capazes	de	ocultar	os	detalhes
de	seus	algoritmos,	produzindo	resultados	facilmente
integrados	ao	computador,	por	meio	de	linguagens
específicas	e	sofisticadas.	Algumas	ferramentas
empregadas	na	construção	de	compiladores	são:
geradores	de	analisadores	sintáticos;	geradores	de
analisadores	léxicos;	mecanismos	de	tradução	dirigida
por	sintaxe;	geradores	de	códigos;	mecanismos	de
fluxo	de	análise	de	dados;	e	conjunto	de	ferramentas
para	construção	de	compiladores.
Resposta	Incorreta:
Resposta	incorreta.	As	ferramentas	mais	adequadas
para	uso	são	aquelas	capazes	de	ocultar	os	detalhes
de	seus	algoritmos,	produzindo	resultados	facilmente
integrados	ao	computador,	por	meio	de	linguagens
específicas	e	sofisticadas.	Algumas	ferramentas
empregadas	na	construção	de	compiladores	são:
geradores	de	analisadores	sintáticos;	geradores	de
analisadores	léxicos;	mecanismos	de	tradução	dirigida
por	sintaxe;	geradores	de	códigos;	mecanismos	de
fluxo	de	análise	de	dados;	e	conjunto	de	ferramentas
para	construção	de	compiladores.
Geradores	de	analisadores	sintáticos,	geradores	de
analisadores	léxicos	e	geradores	de	analisadores
derivativos.
d
Geradores	de	códigos,	geradores	de	analisadores
léxicos	e	geradores	de	analisadores	sintáticos.e
E-Book	-	Apostila
29	-	32
Resposta	Correta:
Resposta	correta.	As	ferramentas	mais	adequadas
para	uso	são	aquelas	capazes	de	ocultar	os	detalhes
de	seus	algoritmos,	produzindo	resultados	facilmente
integrados	ao	computador,	por	meio	de	linguagens
específicas	e	sofisticadas.	Algumas	ferramentas
empregadas	na	construção	de	compiladores	são:
geradores	de	analisadores	sintáticos;	geradores	de
analisadores	léxicos;	mecanismos	de	tradução	dirigida
por	sintaxe;	geradores	de	códigos;	mecanismos	de
fluxo	de	análise	de	dados;	e	conjunto	de	ferramentas
para	construção	de	compiladores.
Leia	o	enunciado	a	seguir.
A	 fase	 de	 análise	 ou	front-end	 é	 uma	 das	 fases	 da
construção	 de	 um	 compilador,	 e	 sua	 finalidade
principal	 é	garantir	 que	a	 sintaxe	e	a	 semântica	do
programa	estejam	corretas,	de	acordo	com	as	regras
da	linguagem.
Essa	análise	pode	ser	dividida	em	três	partes.	Quais
seriam	elas?	Assinale	a	alternativa	correta,	a	seguir.
Leitura,	sintática	e	derivada.a
E-Book	-	Apostila
30	-	32
Resposta	Incorreta:
Resposta	incorreta.	A	fase	de	análise	ou	front-end
pode	ser	dividida	em	três	partes:	léxica	ou	leitura
(scanning):	transforma	o	texto	em	fluxo	de	tokens;
sintática:	verifica	se	os	comandos	estão	corretos;	e
semântica:	garante	que	as	regras	de	semânticas
serão	cumpridas.
Resposta	Incorreta:
Resposta	incorreta.	A	fase	de	análise	ou	front-end
pode	ser	dividida	em	três	partes:	léxica	ou	leitura
(scanning):	transforma	o	texto	em	fluxo	de	tokens;
sintática:	verifica	se	os	comandos	estão	corretos;	e
semântica:	garante	que	as	regras	de	semânticas
serão	cumpridas.
Resposta	Correta:
Resposta	correta.	De	fato,	a	fase	de	análise	ou	front-
end	pode	ser	dividida	em	três	partes:	léxica	ou	leitura
(scanning):	transforma	o	texto	em	fluxo	de	tokens;
sintática:	verifica	se	os	comandos	estão	corretos;	e
semântica:	garante	que	as	regras	de	semânticas
serão	cumpridas.
Disléxica,	sintática	e	semântica.b
Scanning,	sintática	e	semântica.c
Tokens,	scanning	e	semântica.d
E-Book	-	Apostila
31	-	32
Resposta	Incorreta:
Resposta	incorreta.	A	fase	de	análise	ou	front-end
pode	ser	dividida	em	três	partes:	léxica	ou	leitura
(scanning):	transforma	o	texto	em	fluxo	de	tokens;
sintática:	verifica	se	os	comandos	estão	corretos;	e
semântica:	garante	que	as	regras	de	semânticas
serão	cumpridas.
Resposta	Incorreta:
Resposta	incorreta.	A	fase	de	análise	ou	front-end
pode	ser	dividida	em	três	partes:	léxica	ou	leitura
(scanning):	transforma	o	texto	em	fluxo	de	tokens;
sintática:	verifica	se	os	comandos	estão	corretos;	e
semântica:	garante	que	as	regras	de	semânticas
serão	cumpridas.
	
Referências	bibliográficas
AHO,	A.	V.	et	al.	Compiladores:	princípios,	técnicas	e	ferramentas.	São	Paulo:
Pearson	Addison-Wesley,	2008.
ASCENCIO,	A.	F.	G.;	ARAÚJO,	G.	S.	Estruturas	de	dados:	algoritmos,	análise	da
complexidade	e	implementações	em	Java	e	C/C++.	São	Paulo:	Pearson	Prentice
Hall,	2010.
Léxica,	sintática	e	variável.e
E-Book	-	Apostila
32	-	32
BERTOLINI,	C.	et	al.	Linguagem	de	programação	I.	1.	ed.	Santa	Maria:
UAB/NTE/UFSM,	2019.	Disponível	em:
https://repositorio.ufsm.br/bitstream/handle/1/18352/Curso_Lic-Cienc-
Relig_Linguagem-Progracamacao.pdf.	Acesso	em:	9	maio2022.
CONVERSE,	T.;	PARK,	J.	PHP	4:	a	Bíblia.	2.	ed.	Rio	de	Janeiro:	Elsevier,	2003.
DEITEL,	P.	Java:	como	programar.	São	Paulo:	Pearson	Education	do	Brasil,	2017.
DEITEL,	P.;	DEITEL,	H.	C:	como	programar.	6.	ed.	São	Paulo:	Pearson	Prentice	Hall,
2011.
DIVERIO,	T.	A.;	MENEZES,	P.	B.	Teoria	da	computação:	máquinas	universais	e
computabilidade.	Porto	Alegre:	Grupo	A,	2011.
GRAMÁTICA.	In:	Dicionário	Online	de	Português.	Porto:	7Graus,	[c2022].	Disponível
em:	https://www.dicio.com.br/gramatica//.	Acesso	em:	9	maio	2022.
LOUDEN,	K.	C.	Compiladores:	princípios	e	práticas.	2.	ed.	São	Paulo:	Cengage
Learning,	2004.
MENEZES,	P.	B.	Linguagens	formais	e	autômatos.	Porto	Alegre:	Grupo	A,	2011.
PRICE,	A.	M.	A.;	TOSCANI,	S.	S.	Implementação	de	linguagens	de
programação:	compiladores.	Porto	Alegre:	Sagra-Luzzatto,	2001.
REBELO,	M.	N.	Desenvolvimento	de	um	protótipo	de	um	gerador	de
analisador	léxico.	2002.	Trabalho	de	Conclusão	de	Curso	(Bacharelado	em
Ciências	da	Computação)	-	Universidade	Regional	de	Blumenau,	Blumenau,	2002.
Disponível	em:	http://campeche.inf.furb.br/tccs/2002-II/2002-
2michelnogueirarebelovf.pdf.	Acesso	em:	9	maio	2022.
SIPSER,	M.	Introdução	à	teoria	da	computação.	São	Paulo:	Cengage	Learning,
2007.
SOMMERVILLE,	I.	Engenharia	de	software.	8.	ed.	São	Paulo:	Pearson	Addison-
Wesley,	2007.
TOSCANI,	L.	V.	Complexidade	de	algoritmos.	3.	ed.	Porto	Alegre:	Bookman,
2012.
https://repositorio.ufsm.br/bitstream/handle/1/18352/Curso_Lic-Cienc-Relig_Linguagem-Progracamacao.pdf
https://www.dicio.com.br/gramatica//
http://campeche.inf.furb.br/tccs/2002-II/2002-2michelnogueirarebelovf.pdf%3E