UNIFACS DL - Compiladores - unidade III

Prévia do material em texto

11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiUp… 1/36
COMPILADORESCOMPILADORES
ANÁLISES NAANÁLISES NA
CONSTRUÇÃO DECONSTRUÇÃO DE
COMPILADORESCOMPILADORES
Au to r ( a ) : D r. J o ã o C a r l o s L o p e s Fe r n a n d e s
R ev i s o r : Ed i l s o n R o d r i g u e s
Tempo de leitura do conteúdo estimado em 1 hora e 10 minutos.
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiUp… 2/36
Introdução
Caro(a) estudante, os sistemas de computação compreendem apenas a linguagem
de máquina, ou seja, a generalização das linguagens de baixo nível composta por
códigos, quem faz essa função na verdade, são os processadores (arquitetura). As
pessoas não são capazes de compreender a linguagem de máquina. Por esse
motivo, os programadores desenvolvem os programas com linguagens de alto nível,
pois ela é mais parecida com a comunicação humana e mais fácil de ser
interpretada. Quanto às linguagens de alto nível, destacam-se as seguintes: C, C++,
C#, Java, PHP, dentre outras. Os programadores desenvolvem os programas em
uma dessas linguagens e os códigos produzidos são transformados para a
linguagem de máquina a �m de que os processadores consigam interpretar. O
processo de transformação das linguagens de alto nível em linguagem de máquina
recebe o nome de compilação, esse processo possui diversas etapas. A fase da
análise sintática é a responsável por realizar uma veri�cação na estrutura gramatical
da linguagem, ela é a segunda etapa do processo de compilação de um código.
Um abraço e bom estudo!
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiUp… 3/36
Você já ouviu falar sobre a “Análise léxica”? Vamos estudar um pouco mais a fundo
o que ela signi�ca? A análise léxica tem a função de realizar o agrupamento dos
conjuntos de caracteres para elementos léxicos e/ou tokens que possuam os
recursos de expressões regulares. O processamento dessas expressões pode
acontecer ou ser realizado com analisadores bem simples, que consomem pouca
memória RAM. Para a análise de programas como o C/C++ e/ou Java, os caracteres
@ ou $ não podem ser utilizados fora de cadeias de caracteres e/ou comentários,
por exemplo, no idioma português, a análise léxica deve identi�car a palavra
“bolacha” como um nome, mas, caso encontre a palavra “bolaxa”, um erro deverá ser
gerado, isso acontece nos bons corretores ortográ�cos linguísticos.
Fonte: undrey / 123RF.
Análise Léxica
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiUp… 4/36
Por esse motivo, os compiladores possuem o analisador léxico como o primeiro
componente a interagir com o código fonte. Sua função é identi�car todos os tokens
presentes e também serem responsáveis por remover os espaços em branco e os
comentários que foram adicionados ao programa fonte, deixando apenas o que será
necessário para as próximas etapas de análise e síntese.
Projeto de um Gerador de Analisador Léxico
A análise léxica também se preocupa com a categorização dos tokens, como
exemplo os identi�cadores das palavras reservadas. Todas as etapas possuem uma
determinada �nalidade na geração dos analisadores que realizam a divisão do
programa em várias partes (de�nição de tokens), para remover espaços em branco
e gerar, quando necessário, as mensagens de erros indicando as linhas das colunas
da tabela de tokens afetadas.
Em linguagens mais modernas, a análise léxica é relativamente mais
simples de se realizar. Esse não era o caso de algumas linguagens mais
antigas, como o Fortran. Isso porque, por exemplo, os espaços em branco
nessa linguagem também eram ignorados (BARBOSA et al., 2021, p. 72).
Para ajudar na tokenização, a análise léxica busca automatizar os processos
baseando-se em regras para melhorar a performance dos geradores, isso acontece
em algumas linguagens.
Implementação com o Suporte de uma
Ferramenta
ANother Tool for Language Recognition (ANTLR) é uma ferramenta utilizada em
processos de compilação, ela necessita de arquivos de entrada com sintaxe muito
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiUp… 5/36
similar ao do Java. Esse arquivo também deve estar dividido em seções, com as
divisões das funções do Java.
Uma ferramenta útil para a análise de estruturas de ativação complexas
em um programa é a árvore de ativação: cada registro de ativação se torna
um nó nessa árvore, e os descendentes de cada nó representam todas as
ativações efetuadas durante a ativação que corresponde àquele nó
(LOUDEN, 2004, p. 374).
Atualmente, existem várias ferramentas para a construção de compiladores. A
maioria foi projetada para trabalhar em conjunto com outras linguagens de
programação, por exemplo, o JFlex, para a análise léxica, utiliza a base do Java e o
Lex utiliza C. Podemos citar também o CUP (Java) e o ANTLR (C). No caso do GALS,
ele permite especi�car as análises léxica e sintática com a utilização de uma API
Java.
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiUp… 6/36
O JFlex foi desenvolvido para trabalhar junto com o gerador de analisador sintático
(parser), já o CUP foi desenvolvido para trabalhar junto com o ANTLR, mas ele
também pode ser utilizado com outros geradores de parser.
Figura 3.1 - JFlex
Fonte: Elaborada pelo autor.
#PraCegoVer: a �gura apresenta, na parte superior, um retângulo na cor verde, trazendo a
frase “Regras léxicas”, cuja seta, logo abaixo dele, aponta para o segundo retângulo.
Abaixo desse segundo retângulo, de cor roxa, está escrito “JFlex”, cuja seta aponta para
baixo, na direção do terceiro e último retângulo, de cor amarela, que contém o termo
“Código Java”.
O termo Application Programming Interface (API), ou interface de programação de
aplicativos, é uma interface entre as aplicações de diferentes de negócio, como
exemplo, uma API especí�ca consegue interligar o Facebook com os aplicativos
(APPs) de compras.
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiUp… 7/36
REFLITA
As soluções para compilação estão sempre em
desenvolvimento e, com os avanços na arquitetura
dos computadores, ela precisa se adequar. As
soluções de código aberto são ótimas, elas permitem
que os programadores interajam diretamente na nas
ferramentas que são utilizadas para criar um processo
de compilação. Sendo assim, conhecer software de
código aberto é considerado um diferencial em muitas
áreas de desenvolvimento.
Análise Sintática
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiUp… 8/36
Agora, vamos falar sobre Análise Sintática. Na língua portuguesa, assim como em
outras línguas conhecidas, a análise sintática busca identi�car a função das
palavras de uma frase para que as pessoas consigam entender o seu signi�cado.
Isso está relacionado, por exemplo, com o entendimento do sujeito de uma frase ou
em saber a diferença do predicado e dos adjetivos ou advérbios. Sendo assim, a
análise sintática baseia-se em classes gramaticais, como: verbo, sujeito, adjetivo,
dentre outros, que determinam as regras e as normas. Para a área de computação,
também existem os procedimentos para a análise sintática que �caram associados
aos processos de compilação. A compilação transforma um código de uma
linguagem de alto nível para a linguagem de máquina. Essa transformação é
realizada pelo compilador do programa. Os compiladores são programasque
traduzem de um idioma de origem para um idioma de destino, implementados em
alguma linguagem de programação (DEITEL, 2017).
Toda linguagem possui uma forma padrão de escrita, ou seja, possui uma
estrutura. A forma de escrever o código é conhecida como sintaxe. Cada
linguagem tem sua estrutura própria, sendo que algumas possuem
similaridades de sintaxe. Por exemplo, ao escrever o comando de controle
de decisão if... else em linguagem C (BARBOSA et al., 2021, p. 89).
Uma linguagem de programação é a representação de códigos, conhecida como
sintaxe, e as suas funções, conhecidas como semântica. Ela é formada pelo
conjunto de cadeias baseados em um alfabeto, por exemplo, a língua portuguesa é
baseada em 23 letras (A a Z), já o American Standard Code for Information Inter-
change (ASCII) é utilizado na computação para a comunicação entre dispositivos e
possui 128 símbolos representativos. O alfabeto Unicode, por exemplo, é utilizado
nas linguagens de programação mundial e tem a capacidade de atuar com 38 mil
símbolos (LANGLOIS; SANTOS, 2018).
Definição e Exemplos
Na Figura 3.2 é possível visualizar a palavra reservada if (condição), o bloco
indicando verdadeiro (true), else e o bloco falso (false). A linguagens como C++, Java
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiUp… 9/36
e C#, que foram baseadas na estrutura da linguagem C, possuem sua sintaxe
semelhante. A Figura 3.3 apresenta um exemplo do comando if...else em Java.
Observe a semelhança dos códigos apresentados nas Figuras 3.2 e 3.3
relacionados à estrutura do comando if...else. Já no caso do Visual Basic, existe em
sua estrutura algumas pequenas diferenças, como podemos notar na Figura 3.4, a
palavra reservada then é colocada antes do bloco verdadeiro, mas a �nalização do
bloco de comando é com end if.
Figura 3.2 - Sintaxe do comando if ... else em C
Fonte: Barbosa et al. (2021, p. 89).
#PraCegoVer: a imagem apresenta uma tela preta com números na lateral direita que
estão distribuídos na primeira coluna e vão de 1 a 16. Na linha 1, está escrito a frase:
“#include <stdio.h>, na linha 2 #include <stlib.h>”; nas linhas abaixo, vem “int main (void),
{, int N1 =0;, int N2 = 1”; a linha 7 está vazia; na linha 8: “if (N1 == N2)”; nas próximas:
“printf(‘Os números são iguais!’); else, printf(‘Os números são diferentes!’)”; a linha 12
está em branco; a linha 13 possui a frase “print(“\n”)”; nas próxima linha:
“system(‘pause’)”; linha 15: “return(0)”; e a linha 16 está vazia.
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 10/36
Figura 3.3 - Sintaxe do comando if ... else em Java
Fonte: Barbosa et al. (2021, p. 90).
#PraCegoVer: a imagem apresenta uma tela preta com números na lateral direita que
estão distribuídos na primeira coluna e vão de 1 a 13. Na linha 1, está escrito a frase:
“public class IfExemplo {“; na linha 2: “public static void main(String[ ] args) {“; e nas
linhas abaixo: “int idade = 15”; a linha 4 está em banco; na linha 5: “if (idade > 18) {, nas
próximas, System.out.println(idade é maior que 18”); {, else {, System.out.println(“Idade é
menor que 18”);, }, }”;na linha 12: “}”, a linha 13 está vazia.
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 11/36
Figura 3.4 - Sintaxe do comando if ... else em VB
Fonte: Barbosa et al. (2021, p. 90).
#PraCegoVer: a imagem apresenta uma tela preta com números na lateral direita que
estão distribuídos na primeira coluna e vão de 1 a 7. Na linha 1, está escrito a frase: “Sub
AlertUser(value as Long)”; na linha 2: “if value = 0 then”; nas próximas linhas:
“AlertLabel.ForeColor = vbRed, else, AlertLabel.Forecolor = vbBlack, end if”; e na linha 7:
“end sub”.
Sendo assim, notamos que a sintaxe é a estrutura de apresentação das linguagens,
mas não é só ela que de�ne a compilação, pois sozinha ela não é su�ciente para
determinar as expressões que serão executadas no processamento. Por isso, como
complemento, existe a semântica, que é o comando a ser executado.
Cada linguagem de programação possui regras que determinam a
estrutura sintática dos programas bem formatados. Essas regras são
conhecidas como gramáticas. Assim, a gramática in�uencia diretamente
no analisador sintático, ou seja, o analisador sintático é dependente dos
tipos de gramáticas. (BARBOSA et al., 2021, p. 93).
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 12/36
A sintaxe não é difícil de compreender, pois nela �ca a estrutura da escrita na
descrição do comando, isso não acontece com a semântica. A semântica entra em
ação quando o valor inicial é acrescido em 1 a cada loop e deve ser comparado com
o valor �nal (parada do loop); a cada loop em que a condição ainda não é satisfeita,
o comando é executado.
Análise Top-down
Você já ouviu falar sobre a análise de top-down? Vamos estudar sobre esse tema? A
análise top-down também é conhecida como sintática descendente, pois a árvore de
derivação é construída de cima para baixo, ou seja, da raiz para as folhas. Nesse tipo
de análise, sempre é necessário decidir qual regra A→β será aplicada aos nós que
estão rotulados por uma não-terminação A.
Nesse tipo de análise, a reserva de registros tem a função de corresponder os
registros físicos com instruções geradas e, depois, realizar o escalonamento; para
que isso aconteça, existem diversos métodos de atribuição de registros.
Para resolver o problema da reserva dos registros, deve-se minimizar sua utilização,
pois os processadores possuem número limitado de registros. Toda vez que o
número for insu�ciente, a reserva consegue introduzir instruções que movimentam
os valores entre os registros, por exemplo, isso acontece na arquitetura de registros
não uniformes e registros de memória.
A reserva de registros pelo algoritmo top-down já efetua duas passagens
sobre a sequência de instruções. Na primeira passagem, conta o número
Dentre os métodos mais utilizados, possuímos: algoritmos greedy,
ordenação de subárvores, próximo uso, pesquisa linear e/ou
coloração de grafos.
 
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 13/36
de ocorrências de cada registro virtual no bloco básico, usando a
respectiva frequência para de�nir as prioridades. No �m, é necessário
ordenar o resultado em ordem decrescente do número de ocorrências.
Aos k registros virtuais mais utilizados são atribuídos registros físicos. O
objetivo é manter os valores mais utilizados em registros (LANGLOIS;
SANTOS, 2018, p. 291).
Na segunda fase top-down, a lista deve ser percorrida novamente e assim serão
geradas as instruções com registros físicos atribuídos. Caso as instruções não
possuam referências a registros não atribuídos, serão introduzidas as instruções
“load e store” necessárias e, assim, os registros temporários �carão liberados.
Como sempre, a reserva ocorre em duas etapas, ela é mais lenta. O problema
acontece decorrente dos registros utilizados no início do bloco, por não serem
liberados até que o bloco seja �nalizado. Sendo assim, o algoritmo trabalha
uniformemente distribuído, inserindo os registros na sequência das instruções.
A análise sintática top-down descobre a sequência das derivações à esquerda,
sempre partindo do símbolo inicial, e cria uma sequência de “símbolos terminais”.
Fonte: cobracz / 123RF.
Os analisadores top-down sempre realizam a
derivação mais à esquerda da cadeia de entrada e,
para isso, utilizam os símbolos iniciais da gramática.
Uma árvore gramatical, nesse tipo de cadeia, é
construída da raiz para as folhas.
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU…14/36
Essa tarefa é que constrói as árvores sintáticas a serem analisadas, como exemplo
de uma análise sintática simples, considere a gramática:
e a sequência de entrada “w = ugk”. Precisamos de um ponteiro que indique o
símbolo de entrada corrente. Esse ponteiro é inicializado com a posição do primeiro
símbolo “u”. Para construir a árvore sintática, começamos por um nó “S” (símbolo
inicial).
Figura 3.5 - Construção da árvore sintática
Fonte: Langlois e Santos (2018, p. 47).
#PraCegoVer: a imagem apresenta 3 letras “S” distribuídas à direita, no centro e à
esquerda da imagem. Da letra “S”, à direita, saem 3 linhas que apontam para as letras “u,
X e k”; abaixo vem a notação “(a)”. Da letra “S”, do centro, saem também 3 linhas para as
letras “u, X e k”, que estão abaixo dessa coluna e, da letra “X”, saem duas setas para as
letras “g” e “n”, e, abaixo, vem a notação “(b)”. Da letra “S”, à esquerda, saem três retas
para as letras “u, X e k”, que estão nessa coluna e, da letra “X”, sai uma linha para uma
letra “g”, abaixo; e, mais abaixo, vem a notação “(c)”.
1S → uXk
2X → gn
3X → g
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 15/36
A primeira produção é usada para expandir o nó e criar três �lhos: “u, X e k” (Figura
3.5). As folhas são examinadas da esquerda para a direita. A primeira folha
corresponde ao símbolo de entrada “(u)”, o ponteiro é avançado para o símbolo
seguinte “g”.
Se olharmos para uma gramática do ponto de vista descendente, isto é,
partindo do símbolo inicial, as regras de produção são consideradas como
regras de derivação ou de «reescrita». A regra E → E + E signi�ca que uma
expressão pode ser representada pela soma de duas expressões.
Seguindo a gramática de um ponto de vista ascendente, olhamos para as
regras no sentido inverso – a mesma regra signi�ca que a soma de duas
expressões é também uma expressão (LANGLOIS; SANTOS, 2018, p. 38).
O nó “X” (Figura 1.4 b) é expandido criando os �lhos “g e n”, onde a primeira folha
corresponde ao símbolo de entrada “(g)”, logo, o ponteiro vai avançar para o símbolo
seguinte na entrada “k”. Agora, aparece um problema, “k” não corresponde à próxima
folha da árvore “(n)”; dessa forma, será necessário voltar e localizar uma alternativa
para “X”. Sendo assim, o ponteiro é deslocado para a posição anterior “(símbolo u)”.
Agora, “X” é expandido com a terceira regra. O símbolo de entrada (Figura 1.4 c) será
correspondido com a primeira folha e, �nalmente, o ponteiro de entrada vai para “k”,
que é a última folha da árvore.
S A I B A M A I S
Com o computador de programa armazenado criado por John Von Neumann na década
de 1940, �cou clara a necessidade de se escrever códigos (programas) para os
computadores realizarem as funções desejadas. No começo, os programas eram escritos
na linguagem de Máquina, que eram códigos numéricos que representavam as operações
que a máquina deveria efetuar.Para saber mais acesse o link a seguir:
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 16/36
O Backtracking é um algoritmo de re�namento que utiliza força bruta para resolver
os problemas, mas, para que isso aconteça, ele elimina múltiplas soluções sem
determinar o motivo. Esse procedimento é utilizado em linguagens de programação
como, por exemplo, na Programação Lógica (Prolog).
O processo de voltar atrás se uma folha da árvore não corresponde ao símbolo que
foi designado de entrada recebe o nome de retrocesso ou backtracking. Esse
processo necessita de tempo e memória; por esse motivo, é mais recomendado
alterar a gramática para ajustar as sequências e, assim, não ser necessário realizar
retrocessos.
Conhecimento
Teste seus Conhecimentos
(Atividade não pontuada)
Alguns compiladores possuem uma fase de otimização entre o front-end e o back-
end, independentemente da máquina. Essa fase tem o intuito de realizar mudanças
q qPara saber mais, acesse o link a seguir:
http://faef.revista.inf.br/imagens_arquivos/arquivos_destaque/mPd7q0kH4YgxlRK_2013-
5-28-10-54-8.pdf
Fonte: Branco e Tamae (2008).
http://faef.revista.inf.br/imagens_arquivos/arquivos_destaque/mPd7q0kH4YgxlRK_2013-5-28-10-54-8.pdf
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 17/36
na representação intermediária, de modo que o back-end possa produzir um
programa de destino melhor do que teria produzido de uma representação
intermediária não otimizada. Vale ressaltar que a fase de otimização é opcional e,
por isso, pode variar entre diferentes compiladores.
AHO, A. V. et al. Compiladores: princípios, técnicas e ferramentas. 2. ed. São Paulo:
Pearson, 2008.
Podemos considerar que o agrupamento de tokens é uma “frase gramatical”, na
qual o analisador sintático deverá criar uma representação hierárquica na saída,
que é conhecida como árvore gramatical. Na realização da análise sintática,
existem dois métodos utilizados. Quais são eles?
a) Descendente (bottom-up) e recursivamente ascendente (top-down).
b) Ascendente (top-down) e recursivamente descendente (bottom-up).
c) Descendente (top-down) e ascendente (bottom-up).
d) Recursivamente ascendente (top-down) e recursivamente descendente
(bottom-up).
e) Árvore binária da raiz para as folhas e o inverso das folhas para a raiz.
Análise Sintática
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 18/36
Agora, vamos estudar sobre o bottom-up. O bottom-up é conhecido também como
uma análise do empilhamento e tem como principal função reduzir ao máximo as
instruções, ela realiza a redução sempre mais à esquerda da cadeia de entrada X
para o símbolo inicial da gramática. A árvore gramatical que será construída inicia-
se pelas folhas e termina na raiz.
Esse procedimento é diferente do que acontece no top-down, no qual a análise é
realizada a partir dos “não terminais” mais à direita. Isso pode gerar um problema no
nível acima atual da árvore de derivação para chegar até o topo. A �m de resolver
esse problema, muitas vezes, será necessário pensar em realizar algumas
alterações no código fonte.
Definição e Exemplos
Nas análises sintáticas descendente, que são tentativas para se construir uma
árvore de derivação da esquerda para a direita, devemos seguir os seguintes passos:
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 19/36
Fonte: abert84 [Adaptado] / 123RF.
#PraCegoVer: o infográ�co interativo, intitulado “Análises Sintáticas Descendentes”,
possui três botões interativos, enumerados de um a três. O primeiro botão interativo, ao
ser clicado, apresenta o texto “Criar a raiz da árvore e, em seguida, criar as subárvores”. O
segundo botão interativo, ao ser clicado, apresenta o texto “Produzir as derivações mais
à esquerda da sentença que estiver em análise”. O terceiro botão interativo, ao ser
clicado, apresenta o texto “Construir a árvore de derivação para a cadeia de entrada de
cima para baixo (top-down)”.
Para que isso seja realizado, existem duas formas de se utilizar os analisadores
sintáticos descendentes, as com retrocesso e as preditivas.
Além dos problemas de ambiguidade e recursividade, uma gramática pode
ter problemas de não determinismo, ou seja, evitar um processamento
desnecessário (overhead) e diminuir o tempo de processamento. Os
algoritmos tipo descendente (top-down) conhecidos que usam recurso de
backtracking possuem essas características de aumento do custo de
processamento (BARBOSA et al., 2021, p. 98).
O analisador sintático preditivo busca prever a construção seguinte da cadeia de
entrada baseando-se em marcas de veri�cação à frente.
O analisador sintático comretrocesso, primeiro, testa e/ou analisa as possibilidades
de análise sintática de entrada e, caso exista alguma possibilidade de o sistema
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 20/36
falhar, realiza o retrocedendo. Esse tipo de solução é mais completo, mas em
contrapartida mais lento.
No caso da análise sintática descendente recursiva, ela consiste em um conjunto de
procedimentos, um para cada ponto não terminal da gramática. Sua execução inicia
com a ativação dos procedimentos referentes aos símbolos iniciais da gramática.
Nesse tipo de análise, pode ser exigido o retrocesso, ou seja, voltar o
reconhecimento, para fazer várias leituras sobre a entrada. Esse tipo de análise não
está muito presente nas linguagens de programação por não ser muito e�ciente.
Por esse motivo, as análises mais utilizadas são baseadas em tabelas, como o
algoritmo de programação dinâmica.
Já no caso dos analisadores recursivos com retrocesso, são utilizados o LETOKEN,
que retorna um token lido a partir da sentença de entrada, o MARCA_PONTO, que
indica, na sentença de entrada, um ponto de possível reinício da análise, e o
RETROCEDE, que volta o ponteiro de leitura para o último ponto marcado.
Análise Sintática
Bottom-up
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 21/36
As análises sintáticas ascendentes, conhecidas como bottom-up, constroem a
árvore de derivação de baixo para cima, ou seja, das folhas para raiz, produzindo
uma derivação mais à direita para uma cadeia de entrada.
O processo completo de seleção de instruções por programação dinâmica
é composto de duas etapas. A primeira etapa, que acabamos de ver,
consiste em percorrer a árvore sintática das folhas para a raiz (bottom-up),
determinando em cada nó qual a regra que produz, com um custo mais
reduzido, cada um dos possíveis símbolos não terminais. A segunda etapa
consiste na geração das instruções e é efetuado da raiz para as folhas,
mas levando em conta os custos ideais em cada nó (LANGLOIS; SANTOS,
2018, p. 275).
A principal função da análise bottom-up é a redução de uma string w para o símbolo
inicial da gramática. Para que isso aconteça, em cada passo da redução, uma
substring será associada ao corpo de uma produção para se obter “cabeça” da
produção. Para tal, são utilizadas as decisões chave, que de�nem “quando” e
“quanto” reduzir e quais produções podem ser utilizadas. Por de�nição, a redução
sempre será o inverso da derivação. No caso de derivação, o bottom-up parsing
constrói derivações em modo reverso.
Análise Bottom-up
Os analisadores Bottom-up / Shift Reduce Parsers constroem árvores de análise das
folhas à raiz, sendo assim, a análise ascendente pode ser de�nida como uma
tentativa de reduzir a string de entrada w ao símbolo inicial da gramática, traçando
assim as derivações mais à direita de w no sentido inverso.
Além dos algoritmos LL(1) e da família LR, há outro algoritmo do tipo
ascendente (bottom-up) usado para operações aritméticas, chamado de
algoritmo de precedência de operadores. Esses algoritmos também utiliza
a estrutura de pilha e uma tabela sintática para uma gramática de
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 22/36
operador, por exemplo, S => S + S | S * S | a. (BARBOSA; SANTOS, 2021, p.
104).
Para uma análise geral da redução do deslocamento, utiliza-se a análise LR. O L
signi�ca varrer a entrada da esquerda para a direita e o R signi�ca construir uma
derivação mais à direita no sentido inverso. A utilização do LR traz alguns benefícios,
por isso muitas linguagens de programação utilizam ele e/ou algumas de suas
variações. Dentre as linguagens que o utilizam, vale a pena citar o C++ e Perl, pois o
LR Parser pode ser implementado de forma muito e�ciente. Dentre todos os
analisadores que realizam varreduras da esquerda para a direita, os analisadores LR
são os que detectam mais erros sintáticos e de forma bem rápida.
As análises que são realizadas durante o processo de compilação têm papel
fundamental na qualidade do programa compilado, pois nelas, além de diagnosticar
possíveis erros, existe a possibilidade de reescrever partes do código antes de criar
o programa alvo.
Conhecimento
Teste seus Conhecimentos
(Atividade não pontuada)
Os compiladores para as linguagens de programação de alto nível traduzem os
programas-fonte de uma linguagem de entrada, conhecida como “programa-
objeto”, para uma linguagem de saída (compilada). No processo de tradução, o
compilador deve sempre veri�car a sintaxe das sentenças do programa-fonte. Esse
processo de análise sintática é realizado na construção das árvores de análise
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 23/36
segundo duas abordagens: top-down, quando a árvore é investigada da raiz às
folhas; ou bottom-up, quando a investigação acontece das folhas à raiz.
Acerca desse assunto, analise as a�rmativas a seguir.
I - A análise top-down funciona melhor quando a linguagem de entrada utiliza uma
gramática recursiva à esquerda.
II - Sem se preocupar com a abordagem adotada, no top-down e/ou no bottom-up, o
analisador sintático sempre utilizará informações resultantes da análise léxica.
III – Para que os programas em uma determinada linguagem possam ser
analisados tanto em top-down como em bottom-up, a gramática da linguagem
sempre deverá ser ambígua.
IV – Na análise bottom-up, sempre se utilizam ações conhecidas como
deslocamento e redução nas sentenças do programa-fonte.
Está correto o que se a�rma em:
a) I e II, apenas.
b) I e III, apenas.
c) II e IV, apenas.
d) I, III e IV, apenas.
e) II, III e IV, apenas.
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 24/36
Agora vamos estudar sobre análise sintática projeto / implantação. Quando falamos
em gramática para uma linguagem de programação, estamos nos referindo a uma
especi�cação sintática “clara” e bem fácil de entender. Em algumas classes
gramaticais, é permitido a construção automática de analisadores sintáticos que
realizam, caso o programa-fonte não esteja sintaticamente bem-formado, sua
correção, além de que, no processo de construção, o analisador pode revelar
ambiguidades sintáticas e outras construções difíceis de se analisar
gramaticalmente.
Quando a gramática projetada possui uma estrutura de linguagem de programação
fácil de ser traduzida do programa-fonte para a geração de códigos objeto e para a
detecção de erros, o processo de compilação �ca mais simples. Mas, para isso,
existem ferramentas disponíveis que convertem as descrições de traduções,
baseadas em gramáticas, em programas �nalizados.
Com base em uma terminologia similar à dos analisadores sintáticos
LL(1), o algoritmo ascendente mais geral é denominado análise sintática
LR(1) (o L indica que a entrada é processada da esquerda para a direita, o
R indica que uma derivação à direita é produzida e o número 1 indica que
um símbolo de veri�cação à frente é utilizado) (LOUDEN, 2004, p. 213).
Análise Sintática
Projeto /
Implementação
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 25/36
As linguagens evoluíram ao longo do tempo e, com isso, adquiram novas
construções sintáticas. Essas novas construções deveriam ser mais fáceis de serem
incluídas quando uma implementação, baseada nessa gramática da linguagem,
fosse utilizada.
Projeto de um Gerador de Analisador
Sintático
Os compiladores podem ser divididos em quatro etapas básicas, como veremos a
seguir.
Um detalheimpotente é que, em todas as fases do processo de compilação, são
utilizadas a tabela de símbolos, fornecendo informações e propriedades ou caos
necessários inserindo novos tokens entre as operações. No processo, também, é
necessária a existência de um tratador de erros, que é o responsável por gerenciar
qualquer erro léxico, sintático, semântico ou de geração de código.
Fonte: bsd555 / 123RF.
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 26/36
O tratamento de erros consiste em procedimentos alternativos quando um
arquivo de entrada não está de acordo com a linguagem identi�cada pela
gramática especi�cada. Claro que, uma vez detectado um erro sintático no
arquivo de entrada (syntax error), já não é, na maioria dos casos, possível
produzir resultados corretos. Assim, o tratamento de erros permite, em
geral, continuar o processamento para a identi�cação de mais erros e não
para produzir resultados, pois estes di�cilmente seriam corrigidos
(LANGLOIS; SANTOS, 2018, p. 166).
Para recuperar um erro e continuar o processamento, devem ser introduzidas
algumas regras especí�cas. Essas regras podem, algumas vezes, entrar em con�ito
como as outras existentes, sendo assim, é recomendado a construção de uma
gramática sem processamento de erros e, assim, introduzir as regras apenas após
terem eliminado todos os con�itos.
Implementação com o Suporte de uma
Ferramenta
Os compiladores necessitam de várias ferramentas para caso seja preciso
reposicionar algum ponto de leitura no arquivo de entrada e isso deve ser realizado
de forma transparente. Esse processo pode ocorrer por sucessivas chamadas ao
analisador léxico (yylex()) e pela manipulação direta do ponteiro para o arquivo de
entrada (yyin), que vai chamar, por exemplo, a macro yyclearin para repor o símbolo
faltante e/ou modi�cá-lo e assim auxiliar o restante do estado do analisador. Mesmo
resolvendo o problema, esse procedimento deve ser evitado, pois, em alguns casos,
ele é mal executado e o processo �ca comprometido (NIEMANN, 2022).
As ações semânticas em yacc, como em lex, permitem efetuar o
processamento quando as regras são reconhecidas. Na ausência de
ações semânticas, a gramática permite apenas veri�car se o arquivo de
entrada tem erros sintáticos ou se está de acordo com a gramática (isto é,
sintaticamente correto) (LANGLOIS; SANTOS, 2018, p. 167).
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 27/36
Possuímos várias maneiras para fazer a programação de um analisador léxico, o
mais recomendado é o uso de um gerador automático de analisadores lexicais
(como LEX ou FLEX). Embora seja possível escrever um lexer diretamente no código
fonte (à mão), os lexers costumam ser gerados por ferramentas automatizadas.
Essas ferramentas aceitam todas as expressões regulares que descrevem os tokens
permitidos no �uxo de entrada. Dessa forma, a entrada �ca relacionada com a
especi�cação, sendo assim expressões regulares padrões. As ações a serem
tomadas sempre estarão de acordo com o token especí�co. As expressões
regulares estão associadas sempre a uma “frase” em uma linguagem de
programação.
A ferramenta ANTLR, como já vimos anteriormente, é outra ferramenta utilizada para
a criação de um parser/lexer. O ANTLR precisa do arquivo de entrada com sintaxe
similar ao Java, como demonstrado no exemplo a seguir.
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 28/36
As ferramentas que fornecem suporte às etapas de um processo de
desenvolvimento são classi�cadas como frameworks, IDEs (integrated development
environment), dentre elas, vale a pena citar Xtext, que é um framework; Eclipse, que
auxilia na criação de linguagens textuais. O Eclipse Xtext, entre as linguagens e/ou
ferramentas existentes para o desenvolvimento de compiladores, é uma das opções
mais robustas. Ele permite desenvolver todo o compilador (utilizando a linguagem
Java), ou seja, a fase da análise léxica, depois a sintática e semântica até a geração
de código �nal.
Fonte: prima91 / 123RF.
Compilação em sistemas operacionais
diferentes
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 29/36
O programa fonte é o mesmo para todos os sistemas operacionais, ele é gerado por
linguagens de alto nível. O compilador é o responsável por gerar os programas
objetivos e vinculá-los com a linguagem de máquina de cada arquitetura e/ou
sistema operacional.
praticar
Vamos Praticar
Leia o trecho a seguir:
“O Cadastro de Pessoas Físicas (CPF) é um banco de dados, gerenciado pela
Secretaria da Receita Federal do Brasil – RFB, que armazena informações
cadastrais de contribuintes obrigados à inscrição no CPF, ou de cidadãos que se
inscreveram voluntariamente”.
CONSULTAR CPF. Gov.br, [2022]. Disponível em: https://www.gov.br/pt-
br/servicos/consultar-cadastro-de-pessoas-�sicas. Acesso em: 05 abr. 2022.
O número do CPF é composto por 11 dígitos. Suponhamos que sejam aceitos dois
(2) formatos para o CPF, nnn.nnn.nnn-nn ou nnnnnnnnnnn, em que n é um dígito
entre 0 e 9. Qual expressão regular, em Java, aceita/reconhece os dois formatos
indicados?
https://www.gov.br/pt-br/servicos/consultar-cadastro-de-pessoas-fisicas
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 30/36
Material
Complementar
F I L M E
O jogo da imitação
Ano: 2014
Comentário: Esse �lme conta uma história do ano de 1939,
quando a agência de inteligência britânica MI6 contrata Alan
Turing, aluno da Universidade de Cambridge, para entender
códigos nazistas, incluindo o "Enigma", que possuía uma
criptogra�a considerada inquebrável. Alan Turing constrói uma
máquina que foi capaz de decifrar todas as mensagens secretas
que eram enviadas pelos rádios nazistas na guerra e, assim, os
exércitos aliados conseguiram estar à frente da Alemanha e
vencer a guerra.
Para conhecer mais sobre o �lme, assista o trailer, disponível
em:
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 31/36
TRA I LER
L I V R O
Compiladores: da teoria à prática
Autor: Thibault Langlois e Pedro Reis dos Santos
Editora: LTC
Capítulo: 8 – 8.3.4 Tratamento de erros
Ano: 2018
ISBN: 978-85-216-3515-4
Comentário: O processo de tratamento de erros é uma fase
importante no processo de compilação. Vários compiladores,
quando encontram um erro, reportam-os e a tarefa da análise
sintática é �nalizada. Na prática, os compiladores podem e
devem reportar o erro e tentar continuar a análise sintática para
detectar novos erros, caso existam e, dessa forma, diminuir a
necessidade do processo de recompilação a cada relato de erro.
Disponível em: Minha Biblioteca
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 32/36
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 33/36
Conclusão
Caro(a) estudante, o processo de compilação é estruturado em fases que se comunicam
de forma sequencial, ou seja, com a seguinte, para fazer isso utilizam-se de uma
linguagem intermediária adequada. O processo de compilação é dividido em duas partes,
a análise, que divide o programa fonte em partes e cria a representação intermediária, e a
síntese, que é a responsável pela construção do programa alvo, a partir da representação
intermediária. Durante a análise semântica, o compilador tenta detectar as construções
que possuam a estrutura sintáticacorreta do programa, e não existe nenhuma
preocupação com os signi�cados das operações envolvidas, ou seja, em adicionar os
identi�cadores, como matrizes e procedimentos.
Referênci
as
AHO, A. V. et al. Compiladores:
princípios, técnicas e ferramentas.
2. ed. São Paulo: Pearson, 2008.
BARBOSA, C. da S. et al.
Compiladores. Porto Alegre:
SAGAH, 2021.
BRANCO, G. A. J.; TAMAE, R. Y. Uma breve introdução ao estudo e implementação de
compiladores. Revista cientí�ca eletrônica de psicologia, São Paulo, v. 5, n. 8, fev. 2008.
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 34/36
Disponível em:
http://faef.revista.inf.br/imagens_arquivos/arquivos_destaque/mPd7q0kH4YgxlRK_2013-
5-28-10-54-8.pdf. Acesso em: 05 abr. 2022
CONSULTAR CPF. Gov.br, [2022]. Disponível em: https://www.gov.br/pt-
br/servicos/consultar-cadastro-de-pessoas-�sicas. Acesso em: 05 abr. 2022.
CRUZ, M. S. B. da. Estudo comparativo de ferramentas de apoio a compiladores: JFlex,
XText e CUP. 2020. Trabalho de conclusão de curso (Bacharelado) - Ciência da
Computação, Centro de Engenharia Elétrica e Informática, Universidade Federal de
Campina Grande, 2020. Disponível em:
http://dspace.sti.ufcg.edu.br:8080/jspui/handle/riufcg/20334. Acesso em: 05 abr. 2022.
DELAMARO, M. Como construir um compilador utilizando ferramentas Java. São Paulo:
Novatec, 2004. Disponível em:
http://conteudo.icmc.usp.br/pessoas/delamaro/SlidesCompiladores/CompiladoresFinal.p
df. Acesso em: 05 abr. 2022.
DEITEL, P. Java: como programar. São Paulo: Pearson Education do Brasil, 2017.
(Disponível na Biblioteca Virtual).
LANGLOIS, T.; SANTOS, P. R. Compiladores: da teoria à prática. Rio de Janeiro: LTC, 2018.
LOUDEN, K. C. Compiladores: princípios e práticas. São Paulo: Cengage Learning, 2004.
NIEMANN, I. A guide to LEX & YACC. Oregon: E-papers, [2002]. Disponível em:
https://arcb.csc.ncsu.edu/~mueller/codeopt/codeopt00/y_man.pdf. Acesso em 05 abr.
2022.
O JOGO DA IMITAÇÃO - Trailer Legendado. [S. l.: s. n.], 2015. 1 vídeo (2 min 31 s).
Publicado pelo canal Cinemaginando. Disponível em: https://www.youtube.com/watch?
v=NM4GZ3NQvxQ. Acesso em: 05 abr. 2022.
http://faef.revista.inf.br/imagens_arquivos/arquivos_destaque/mPd7q0kH4YgxlRK_2013-5-28-10-54-8.pdf
https://www.gov.br/pt-br/servicos/consultar-cadastro-de-pessoas-fisicas
http://dspace.sti.ufcg.edu.br:8080/jspui/handle/riufcg/20334
http://conteudo.icmc.usp.br/pessoas/delamaro/SlidesCompiladores/CompiladoresFinal.pdf
https://arcb.csc.ncsu.edu/~mueller/codeopt/codeopt00/y_man.pdf
https://www.youtube.com/watch?v=NM4GZ3NQvxQ
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 35/36
11/06/2023, 19:21 E-book
https://student.ulife.com.br/ContentPlayer/Index?lc=e6IUL5ncVpNnpafasMtHtw%3d%3d&l=1OdIzZ8xcachsr3pzfvcBA%3d%3d&cd=euiSKCRHJrkiU… 36/36