Tema 3 Análise Sintática

Prévia do material em texto

DESCRIÇÃO
Funcionamento do analisador sintático, Caracterização das Gramáticas Livres de Contexto e
Ambíguas, Análise dos algoritmos ascendentes e descendentes.
PROPÓSITO
Apresentar as características da Análise Sintática, a estrutura funcional do analisador, as
formas de os implementar e as especificações das gramáticas, para que este passo da
compilação seja realizado corretamente.
OBJETIVOS
MÓDULO 1
Descrever o analisador sintático e o tratamento de erros
MÓDULO 2
Identificar as características das Gramáticas Livres de Contexto e Ambíguas e suas produções
MÓDULO 3
Classificar o funcionamento dos algoritmos ascendentes e descendentes
MÓDULO 4
Classificar as formas de projetar analisadores sintáticos e a utilização de programas que os
geram
INTRODUÇÃO
Na etapa de Análise da Compilação, o seu segundo passo é a Análise Sintática.
O analisador sintático é o componente do compilador responsável por, a partir dos tokens
gerados pela Análise Léxica, verificar se as expressões de entrada são sentenças válidas na
gramática da linguagem-fonte, gerando uma árvore sintática que é repassada para o analisador
semântico visando à continuidade da compilação.
Neste tema, apresentaremos as características do analisador sintático, as técnicas que
emprega e as formas de o implementar. Além disso, veremos as características das gramáticas
que balizam o seu funcionamento.
MÓDULO 1
 Descrever o analisador sintático e o tratamento de erros
A ANÁLISE SINTÁTICA
A Análise Sintática é o segundo passo da etapa de Análise da Compilação, ela recebe do
analisador léxico uma lista de tokens, os processa e passa uma árvore de sintaxe à Análise
Semântica (Figura 1).
 Figura 1 ‒ Passo da Análise Sintática. Fonte: O Autor, 2020.
O analisador sintático (AS), também chamado de parser, tem como principal objetivo verificar
se os tokens gerados no passo de Análise Léxica formam uma sentença (estrutura sintática)
aceita na gramática que especifica a linguagem-fonte.
Mas o que queremos dizer com estrutura sintática aceita?
Veja o seguinte exemplo:
 EXEMPLO
A3 := 6 + B
Esta expressão geraria os seguintes tokens:
LEXEMA TIPO VALOR
A ID A
3 NumInt 3
= ATRIB Atribuição
6 NumInt 6
+ OpArit Soma
B ID B
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Do ponto de vista léxico, está tudo correto. Porém, se a gramática especificar que um
identificador (Id), por exemplo, A3 e B, somente pode ser formado por letras e que antes de
uma atribuição (atrib) somente pode vir um identificador, a expressão não corresponde a uma
sentença correta do ponto de vista da sintaxe da linguagem, e será gerado um erro.
RELAÇÃO COM O ANALISADOR LÉXICO (AL)
OU SCANNER
Os passos de Análises Léxica e Sintática são intimamente associados. Apesar de
academicamente eles serem vistos como sequenciais, ou seja, o scanner gera toda a
sequência de tokens e os passa para o parser, na maior parte dos compiladores reais eles não
funcionam desta forma.
Na verdade, o AS não necessita de todos os tokens terem sido estabelecidos para fazer o seu
trabalho.
Na maioria dos casos, é possível construir a árvore de sintaxe de parte do programa
examinando apenas um pequeno número de tokens de cada vez. Devido a isso, eles
normalmente funcionam em conjunto com o parser, comandando todo o processo de análise e
acionando o analisador léxico pedindo um novo token sempre que necessitar (função
pedetoken()). Já o scanner deve manter controle de que partes já foram processadas do
programa-fonte. (Figura 2).
 Figura 2 ‒ Relação analisador sintático e léxico. Fonte: O Autor, 2020.
 VOCÊ SABIA
Este tipo de funcionamento tem origem nas limitações que os computadores antigos
possuíam, pois sua pouca memória era insuficiente para armazenar toda a sequência de tokens
do programa-fonte, bem como toda a árvore sintática gerada.
Devido a estas limitações, o parser pedia a geração do token, criava árvores parciais e as
passava para o analisador semântico já gerando a representação intermediária. Assim, após a
geração da representação intermediária, a parte da árvore que havia sido gerada podia ser
descartada, e o processo prosseguia pedindo novos tokens, gerando uma nova árvore, uma
nova parte da representação intermediária, e assim, sucessivamente.
Este tipo de funcionamento de um compilador denomina-se tradução dirigida pela sintaxe.
Atualmente, com o aumento do poder computacional, vários compiladores geram a árvore toda
antes de passar para a Análise Semântica, pois esta muitas vezes se beneficia da ter a árvore
toda, mas a relação scanner/parser continua, normalmente, da forma tradicional.
Conforme vimos, a partir do conjunto de sentenças válidas, o parser deve gerar a árvore de
sintaxe, mas o que vem a ser exatamente uma árvore de sintaxe?
ÁRVORES DE SINTAXE
A árvore de sintaxe nada mais é que a estrutura de dados denominada árvore, onde a raiz fica
no topo (Figura 3) e a partir da qual toda a estrutura se origina. Cada um dos nós pode ou não
ter filho. Os que possuem filhos estão abaixo ligados por um arco ou aresta. Já os nós sem
filhos são chamados folhas e aparecem na “ponta” da árvore.
 Figura 3 ‒ Estrutura de dados árvore. Fonte: O Autor, 2020.
Imagine o seguinte comando:
Se <cond> 
Então <C1> 
Senão <C2>
O comando SE possui as seguintes partes:
A condição.
O(s) comando(s) a ser(em) executado(s) se o resultado do teste for verdadeiro.
O(s) comando(s) a ser(em) executado(s) se o resultado do teste for falso.
Quando o compilador encontra o SE, ele necessita acessar estas partes todas para poder gerar
o código executável do comando, por isso não basta identificar os tokens – ele precisa montar
uma estrutura sintática para o comando. A árvore que representaria o SE seria a da Figura 4.
 Figura 4 ‒ Árvore do SE. Fonte: O Autor, 2020.
A árvore representa o seguinte:
Comece com a raiz se é um SE.
Teste a condição no filho à esquerda. Se o resultado for:
Verdadeiro, siga pelo então.
Falso, siga pelo senão.
 COMENTÁRIO
Entretanto, a árvore da Figura 4 está incompleta, pois a condição e os comandos do então e do
senão possuem estruturas que também precisam ser representadas na árvore, porém num tipo
diferente: A árvore de expressão.
ÁRVORE DE EXPRESSÃO
Este tipo de árvore é construído para representar expressões aritméticas, lógicas ou de
comparação. Uma expressão é composta por operadores que designam a operação que será
realizada e operandos, que são os valores ou expressões que irão interagir na operação.
Devido a estas características, uma árvore de expressão possui uma estrutura de
representação diferente da árvore de sintaxe de um comando, já que os operadores são nós
internos (possuem filhos) e os valores são as folhas das árvores.
Considere a seguinte expressão:
2 + 3
� Atenção! Para visualização completa da equação utilize a rolagem horizontal
Sua árvore seria:
Onde:
O operador é +.
Os operandos são 2 e 3.
Vejamos um exemplo um pouco mais complexo. Considere a expressão (2 + 3) * 7, cuja árvore
seria:
Neste tipo de árvore, o percurso é das folhas para a raiz. Então, a interpretação seria:
Pegue os operandos 2 e 3.
Realize a soma.
Pegue como operandos agora o resultado da soma e 7.
Realize a multiplicação.
Note que, pela forma como a árvore foi construída, ela representa a ordem de execução das
operações, não necessitando dos parênteses como acontece quando representamos a
expressão como uma expressão matemática.
Normalmente, as operações em expressões são binárias, ou seja, possuem dois operandos.
Algumas poucas expressões podem ser unárias com o Não lógico ou negativar um número.
Devido a estas características, árvores de expressão são do tipo binário, ou seja, um nó pode
ter 0, 1 ou no máximo dois filhos.
CONSTRUINDO A ÁRVORE COMPLETA DO
COMANDO SE
Voltando ao nosso comando SE, imagine o seguinte trecho de código:
Se (x > 2) 
Então 
y = (x - 2) * 7; 
Senão 
y = x + 2 * 5;
Neste comando, podemos observaro seguinte:
A condição é verificar se X é maior que dois (x > 2).
O comando do então é a atribuição a Y do resultado de (x - 2) * 7.
O comando do senão é a atribuição a Y do resultado de x + 2 * 5.
A estrutura da árvore deste comando é construída a partir da árvore da Figura 4, substituindo
Cond, Então e Senão pelas árvores de expressão correspondentes, conforme você pode ver na
Figura 5.
 Figura 5 ‒ Árvore sintática completa do SE. Fonte: O Autor, 2020.
TRATAMENTO DE ERROS
Se todo programa fosse escrito sem erros, o projeto do compilador seria muito simplificado.
 COMENTÁRIO
Mormente, muitos erros ocorrem, e um bom compilador deve ajudar o programador a corrigir o
seu código provendo mensagens de erros que sejam compreensíveis.
Em verdade, as linguagens de programação não são projetadas tendo os erros em mente, já
que elas não especificam em seus padrões como os tratar. Esta tarefa acaba ficando a cargo
do projeto do compilador, gerando maior dificuldade na recuperação das incorreções dos
programas.
Os programas podem conter erros em múltiplos níveis, por exemplo:
LÉXICOS
Como colocar um símbolo não existente na linguagem.
SINTÁTICOS
Como uma expressão que abre um parêntese, mas não o fecha.
SEMÂNTICOS
Como um operador aritmético aplicado a um valor de string.
LÓGICOS
Como colocar um programa em loop infinito.
A maior parte dos erros é detectada durante a Análise Sintática, pois, em sua maioria, são
expostos quando o fluxo de tokens é validado a partir da gramática de linguagem e a cadeia
não gera uma sentença válida. Outro fator que contribui para isso é a eficiência dos modernos
javascript:void(0)
javascript:void(0)
javascript:void(0)
javascript:void(0)
algoritmos de AS nesta detecção. Sendo que fazer a detecção semântica ou lógica é muito
mais difícil.
As metas para o tratamento de erros pelo parser são:
Deve relatar de forma clara e acurada os erros encontrados.
A recuperação de cada erro deve ser rápida, de forma a não impactar a detecção de um
novo erro.
Não deve retardar de forma significativa a análise de programas sem erros.
Estas metas, apesar de parecerem simples, são, na realidade, difíceis de serem implementadas,
mas felizmente os erros mais comuns são simples e podem ser tratados de forma
relativamente direta.
 ATENÇÃO
A maior dificuldade é que um erro, muitas vezes, ocorre bem antes no código em relação ao
ponto onde foi detectado, fazendo com que o mecanismo de tratamento tenha que “adivinhar”
o que o programador pretendia fazer.
Devido a isto, os algoritmos de parser, sejam LL ou LR, tentam detectá-los tão cedo quanto
possível. Para tal, usam o conceito de prefixo viável, que consiste em considerar que ocorreu
um erro assim que percebem que determinado token não irá corresponder a uma sentença
válida.
Para tornar o assunto mais claro, vejamos os aspectos obtidos por Ripley e Druseikis (1978),
que realizaram uma pesquisa em um conjunto de programas escrito na linguagem Pascal por
estudantes da área de TI.
Eles descobriram que os erros ocorrem com uma frequência relativamente baixa, já que 60%
dos programas não continham erros. Dos restantes, 80% possuíam apenas 1 erro e 13% dois
erros, sendo que 90% eram erros triviais que afetavam apenas um token.
Dos erros, 60% eram de pontuação, 20% de operandos e operadores, 15% de palavras-chave e
os 5% restantes de outros tipos, sendo que, dos erros de pontuação, a maioria era em torno do
uso incorreto do ponto e vírgula, por exemplo:
Trocar o ponto e vírgula por vírgula na linha de argumentos de uma função
Certo - funcao exemplo (i: inteiro; j:inteiro):
Errado - funcao exemplo (i: inteiro, j:inteiro):
Colocar um ponto e vírgula antes de um senão
Certo – se a> b entao a := a - 5
senao b := b + 10;
Errado - se a> b entao a := a + 5;
senao b := b + 10;
Não colocar um ponto e vírgula obrigatório
Certo - Programa exemplo;
Errado - Programa exemplo
Deixar de colocar os dois pontos na atribuição
Certo – A:= 8;
Errado – A = 8;
 ATENÇÃO
Os exemplos estão em pseudocódigo com sintaxe similar à linguagem Pascal. Vários dos erros
decorrem também das diferenças entre as linguagens que usam os mesmos símbolos, mas
com significados diferentes, o que confunde os programadores, como acontece com o “=”, que
em C é atribuição e em Pascal comparador de igualdade, já que nesta linguagem a atribuição é
“:=”.
A maior parte dos compiladores lidam com esses tipos de erro sem dificuldade. Emitem um
alerta e prosseguem a análise, porém, outros tipos de erros, como deixar de marcar o início ou
fim de um bloco de instruções, podem ser de tratamento mais complexo.
Considere o seguinte trecho de código:
Se a > b entao a:= a -5 
 senao b:= b +10; 
c:= b + a;
Da forma como está escrito, o senão corresponde apenas ao comando b:= b+10; e a opção da
atribuição a “c” sempre irá ocorrer. Porém, se desejássemos que isso fosse parte do senão,
teríamos que abrir e fechar um bloco no senão. Este seria um erro que o tratamento não
conseguiria detectar.
O código correto neste caso seria:
Se a > b entao a:= a - 5 
 senao inicio 
 b:= b +10; 
 c:= b + a; 
 fim;
O compilador deve reportar a presença de erro informando no mínimo o local no programa-
fonte onde ele foi detectado, já que existe uma boa chance de o erro ser na verdade em um
token anterior.
Veja este exemplo a partir de um comando SQL:
 Fonte: O Autor.
Uma estratégia comumente usada é imprimir a linha ilegal marcando o local onde o erro foi
gerado, com uma mensagem apontando, sempre que possível, o tipo do erro, por exemplo, a
falta de ponto e vírgula. No exemplo acima, foi informado que não tem uma tabela
especificada.
 Fonte: O Autor.
Mas você pode dizer que está ali o nome da tabela CURSO. O que acontece é que o ponto e
vírgula antes do from faz o SGBD entender que o comando acabou ali, ou seja, o erro foi gerado
por um token anterior ao from. Se retirarmos o ponto e vírgula, o comando funciona.
Feita a detecção, como o compilador se recupera para poder continuar a análise?
 RESPOSTA
Existem várias estratégias, a ideia principal é que o parser volte a um estado que permita que
continue o processamento da lista de tokens sem que novos erros sem sentido sejam gerados.
Como assim erros sem sentido? Observe o seguinte código:
Programa exemplo 
Var 
a,b,c: inteiro; 
Inicio 
a:=10; 
b:= 5; 
Se a > b entao a:= a -5 
 senao b:= b +10; 
c:= b + a; 
Fim;
Note que falta o ponto e vírgula após o nome do programa. O correto seria:
Programa exemplo;
Se o compilador não atentar para este fato, pode gerar erro em todas as outras linhas, que
seriam indevidos, já que o restante do programa está correto.
Outro exemplo seria, se ao declarar uma variável, ocorresse um erro sintático. Ele prosseguiria
na análise e não seriam gerados novos erros sintáticos, mas no próximo passo ocorreria um
erro na Análise Semântica, já que a variável não teria sido criada na tabela de símbolos.
Se ocorrem muitos erros logo no início da Análise Sintática, pode ser melhor abortar o
processo. Imagine a seguinte situação: Um compilador C recebe como entrada um programa-
fonte em Pascal. Melhor abortar logo.
As estratégias mais utilizadas de recuperação para o parser são:
MODALIDADE DO DESESPERO
É o método mais simples de implementar. Ao descobrir um erro, o parser descarta os símbolos
de entrada, um de cada vez, até encontrar um token que pertença ao conjunto de tokens de
sincronização.
Tokens de sincronização são usualmente os delimitadores de comando ou blocos de comando,
tais como “;” “,” “}” ou “fim”, e que possuem um papel claro no programa-fonte.
Este tipo de correção normalmente pula uma parte considerável da entrada sem verificar. Tem
como vantagens a simplicidade e o fato de não ficar em loop infinito, o que pode ocorrer com
outros métodos.
RECUPERAÇÃO DE FRASES
Ao detectar um erro, o parser pode corrigir a entrada restante, ou seja, substituir um prefixo da
entrada por alguma cadeia que permita que ele sigaem frente.
Um exemplo deste tipo de recuperação seria substituir uma vírgula entre os parâmetros de uma
função por um ponto e vírgula.
Originalmente desenvolvido para a Análise Descendente, tem como principal desvantagem a
dificuldade em lidar com erros que efetivamente ocorreram antes do ponto de detecção.
REGRAS DE PRODUÇÃO PARA ERRO
Quando se tem de antemão uma boa ideia dos erros mais comuns que podem ser cometidos
ao se escrever o programa-fonte em uma determinada linguagem, a sua gramática poderia ser
expandida com as produções que gerassem construções ilegais.
A partir daí, ela pode ser utilizada para construir um parser que gere diagnósticos apropriados
para indicar o reconhecimento das construções ilegais ocorridas na lista de tokens de entrada.
Ã
CORREÇÃO GLOBAL
O ideal é que um compilador faça o mínimo de mudanças no programa-fonte ao processar uma
cadeia inválida.
Existem algoritmos que determinam a menor quantidade de mudanças a partir de uma cadeia
de entrada incorreta X e uma Gramática G. Estes algoritmos construirão uma árvore gramatical
para outra cadeia Y que seja derivada de X e atenda a G.
Estes métodos infelizmente são custosos em termos de memória e tempo de processamento e
raramente utilizados na prática.
 ATENÇÃO
Cabe observar que atualmente, com a substituição dos antigos computadores de grande porte,
a compilação passou a ser uma atividade tipicamente interativa. Desta forma, interromper o
processo no momento da ocorrência do erro se tornou menos problemático e permite que a
correção seja realizada imediatamente, como acontece na interpretação, o que facilita a
correção dos programas e a construção dos compiladores em relação à recuperação de erros.
No vídeo a seguir, você verá a construção de uma árvore sintática e as formas ascendente e
descendente.
VERIFICANDO O APRENDIZADO
1. DURANTE A REALIZAÇÃO DA ANÁLISE, PODEM SER DETECTADOS ERROS.
EM PRINCÍPIO, O PARSER NÃO DEVE ABORTAR A ANÁLISE, DEVE REPORTAR
O ERRO E REALIZAR SUA RECUPERAÇÃO. EXISTEM DIVERSAS FORMAS DE
REALIZAR O TRATAMENTO DE ERRO. QUANDO A GRAMÁTICA DE
LINGUAGEM-FONTE JÁ PREVÊ O QUE FAZER PARA OS ERROS MAIS COMUNS,
PODEMOS UTILIZAR O MÉTODO DE TRATAMENTO:
A) Modalidade do desespero
B) Recuperação de frases
C) Correção global
D) Regras de produção para erro
E) Recuperação sintática
2. ÁRVORES DE SINTAXE SÃO O PRODUTO DO PARSER E SERVEM PARA
REPRESENTAR A FORMA DE EXECUÇÃO DE UM COMANDO. OBSERVE A
FIGURA ABAIXO E INDIQUE A OPÇÃO QUE APRESENTA O COMANDO QUE A
PRODUZ.
A) Se X <= Z
Entao Y = X * 2 + 7
Senao Y = X * Z - 5
B) Se X < Z
Entao Y = X * 2 + 7
Senao Y = X * (Z – 5)
C) Se X <= Z
Entao Y = X * 2 + 7
Senao Y = X * (Z – 5)
D) Se X <= Z
Entao Y = X * (2 + 7)
Senao Y = X * Z – 5
E) Se X <= Z
Entao Y = X * (Z - 5)
Senao Y = X * 2 + 7
GABARITO
1. Durante a realização da análise, podem ser detectados erros. Em princípio, o parser não
deve abortar a análise, deve reportar o erro e realizar sua recuperação. Existem diversas
formas de realizar o tratamento de erro. Quando a gramática de linguagem-fonte já prevê o
que fazer para os erros mais comuns, podemos utilizar o método de tratamento:
A alternativa "D " está correta.
As quatro respostas correspondem a métodos de recuperação de erro. A modalidade
desespero corresponde a descartar todos os símbolos até ser encontrado um token que
permita a sincronização. A recuperação de frases tenta corrigir a entrada substituindo os
símbolos que geraram erros por alguma outra cadeia que permita prosseguir com a análise. A
correção global visa a analisar o código-fonte minimizando a quantidade de mudanças para
fazer a recuperação. As regras de produção para erro utilizam as produções especificadas na
gramática para a correção de erros.
2. Árvores de sintaxe são o produto do parser e servem para representar a forma de execução
de um comando. Observe a figura abaixo e indique a opção que apresenta o comando que a
produz.
A alternativa "C " está correta.
Se observarmos a árvore, podemos notar que, no ramo do então, a multiplicação é realizada
antes da soma e, no ramo do senão, a soma é realizada antes. Desta forma, analisando as
opções, temos que: Na opção A, não existem parênteses no senão e, assim, a multiplicação
deveria ser realizada antes. Na opção B, embora o senão esteja correto, o teste da condição
está errado: consta < e é <=. A opção C está correta. Na opção D, os parênteses estão no então
e não no senão, portanto a soma seria realizada antes de multiplicação no então e depois no
senão.
MÓDULO 2
 Identificar as características das Gramáticas Livres de Contexto e Ambíguas e suas
produções
GRAMÁTICAS LIVRES DE CONTEXTO
As linguagens de programação são um tipo de linguagem como outra qualquer, sendo
compostas de símbolos, o seu alfabeto, e de suas regras de escrita, a sua gramática.
Dentre os vários tipos de linguagem, as livres de contexto são as mais adequadas para a
especificação de linguagens de programação, pois, apesar de as linguagens regulares poderem
definir de forma muito eficiente os aspectos léxicos, não possuem expressividade suficiente
para definir as regras de escrita da linguagem, ou seja, sua sintaxe.
 ATENÇÃO
Desta forma, as linguagens livres de contexto e as respectivas Gramáticas Livres de Contexto
(GLC) vão especificar os padrões que serão utilizados na verificação da sintaxe do programa-
fonte.
Uma Gramática Livre de Contexto G funciona para especificar formalmente as regras da
linguagem e possui em sua especificação quatro componentes:
O CONJUNTO DE SÍMBOLOS TERMINAIS T
Que representam os símbolos que aparecem na linguagem.
Á Í Ã
O CONJUNTO DE VARIÁVEIS OU SÍMBOLOS NÃO
TERMINAIS V
Que são símbolos auxiliares durante as substituições.
O CONJUNTO DE PRODUÇÕES P
Que nos permitem gerar cadeias ou sentenças da linguagem que está sendo analisada.
O SÍMBOLO INICIAL S
Sendo que este símbolo S deve ser um dos símbolos variáveis (S ∈ V).
Antes de continuarmos, vamos estabelecer alguns conceitos básicos que são muito
importantes para o entendimento de nosso tema.
SÍMBOLOS TERMINAIS
SÍMBOLOS NÃO TERMINAIS
REGRAS DE PRODUÇÃO
FORMA SENTENCIAL E SENTENÇA
SÍMBOLOS TERMINAIS
São símbolos na especificação da gramática que não possuem regras que os modifiquem. Por
exemplo, na seguinte gramática abaixo, 0 e 1 são símbolos terminais.
S pode se tornar 0S0
S pode se tornar 1S1
S pode se tornar 1
S pode se tornar 0
S pode se tornar vazio
SÍMBOLOS NÃO TERMINAIS
São aqueles que pelas regras da gramática podem ser substituídos por outros, ou seja, seriam
como variáveis. No exemplo da gramática acima, S é um não terminal.
FORMA SENTENCIAL E SENTENÇA
Especificam os lexemas que podem ser substituídos por outros. Estas regras podem ser
representadas de várias formas, mas em nossos exemplos, usaremos uma notação que deriva
da teoria dos conjuntos, por exemplo, a gramática:
S pode se tornar 0S0
S pode se tornar 1S1
S pode se tornar 1
S pode se tornar 0
S pode se tornar vazio
Poderia ser representada da seguinte forma:
S → 0S0
S → 1S1
S → 0
S → 1
S → Ɛ
Onde do lado esquerdo temos um símbolo não terminal ligado por uma seta (→) à produção
que o pode substituir.
Observação: Ɛ representa vazio.
FORMA SENTENCIAL E SENTENÇA
Sentença - É uma sequência de símbolos terminais.
Forma Sentencial – Sequência de símbolos terminais e variáveis (símbolos não terminais). Ela
pode ter apenas símbolos terminais, apenas variáveis ou uma mistura dos dois, o que implica
que uma sentença é sempre uma forma sentencial, mas nem toda forma sentencial é uma
sentença.
Por exemplo, considerando a gramática com que temos feito os nossos exemplos, que valida
se um número binário possui as seguintes características:
Se o número tiver uma quantidade par de dígitos, a primeira metade deve ser o “espelho“
da segunda metade, por exemplo 011110 – note que a primeira metade é 011, logo a
segunda deve ser 110.
Se o número tiver uma quantidade ímpar dedígitos, o digito do meio deve ser separado e
os dígitos antes dele devem ser espelho dos dígitos posteriores, por exemplo 0110110 –
o dígito do meio é 0, os anteriores 011 e os posteriores 110.
As sequências 010, 0110, 000, 111,1001 constituem sentenças.
Já 0S0, 1S1 são formas sentenciais que não são sentenças.
DERIVAÇÕES
A derivação de uma gramática é a sequência de formas sentenciais tal que:
A primeira forma é apenas o símbolo inicial da gramática.
A última forma é sempre uma sentença.
As formas intermediárias podem ser obtidas pela substituição de um único símbolo não
terminal pelo lado direito de uma das produções.
EXEMPLOS
 EXEMPLO 1
Considerando nossa gramática de números binários, considere a seguinte derivação:
S ⟹ 1
Esta derivação possui duas formas sentenciais que são sempre separadas pelo símbolo ⟹
O símbolo inicial da gramática S.
1 que é uma sentença.
A derivação mostra que a cadeia é uma sentença da linguagem. Vejamos passo a passo:
Temos a primeira forma sentencial, que é o símbolo inicial da gramática, no caso S.
Utilizando a quarta produção, substituímos S por 1, criando a segunda forma sentencial,
que no caso também é uma sentença e, portanto, a última forma da sequência, já que não
existem mais substituições que possam ser realizadas.
 EXEMPLO 2
Vejamos um exemplo um pouco mais complexo. Você deseja validar se 00 pertence à
gramática. Para isso, a seguinte derivação seria gerada e validaria a cadeia:
S ⟹ 0S0 ⟹ 00
Inicialmente, temos a forma sentencial correspondente ao símbolo inicial S.
A seguir, utilizando a primeira produção, o substituímos por 0S0, que também é uma
forma sentencial, mas não uma sentença, pois possui uma variável.
Por último, utilizando a produção 5, substituímos S por vazio, gerando a sentença 00.
 EXEMPLO 3
Um último exemplo, agora você deseja validar a cadeia 01110.
S ⟹ 0S0 ⟹ 01S10 ⟹ 01110
Inicialmente, temos a forma sentencial correspondente ao símbolo inicial S.
A seguir, utilizando a primeira produção, o substituímos por 0S0, que também é uma
forma sentencial, mas não uma sentença, pois possui uma variável.
O próximo passo é, utilizando a produção 2, substituir S por 1S1, e a cadeia fica então
01S10, que também é uma forma sentencial, mas não uma sentença, pois possui uma
variável.
Por último, utilizando a produção 4, substituímos S por 1 gerando a sentença 01110 e
validando a entrada.
ÁRVORE DE DERIVAÇÃO
Outra forma de representar as derivações é usar árvores de derivação, em vez da sequência
linear.
 ATENÇÃO
Árvores de derivação são similares a árvores de sintaxe, mas possuem mais elementos
referentes às produções da gramática, inclusive das variáveis utilizadas, para balizar o
funcionamento do parser.
Numa árvore de derivação, as folhas são os símbolos terminais, e os nós internos são as
variáveis.
Um nó de variável V vai ter como filhos na árvore os símbolos pelos quais é substituído na
derivação.
Utilizando nosso último exemplo S ⟹ 0S0 ⟹ 01S10 ⟹ 01110, a árvore seria a da Figura 6:
 Figura 6 ‒ Árvore de derivação. Fonte: O Autor, 2020.
DERIVAÇÕES MAIS À ESQUERDA E MAIS À
DIREITA
Quando, ao fazermos a derivação, substituímos a variável mais à esquerda, ela é chamada
derivação à esquerda. Se substituirmos a da direita, ela se chama derivação à direita.
Considere a seguinte gramática:
S → 0TS
S → 0
T → S1T
T → SS
T → 10
Os terminais são 0 e 1, e os não terminais S e T, sendo o símbolo inicial S.
A figura 7 mostra a árvore de derivação, com os nós numerados para facilitar a explicação, que
seria gerada a partir da gramática.
 Figura 7 ‒ Árvore de derivação. Fonte: O Autor, 2020.
Note o seguinte:
Os nós 1, 3, 4, 5 e 7 são interiores e possuem símbolos não terminais.
Os nós 2, 6, 8, 9, 10 e 11 são folhas e possuem os símbolos terminais que formam uma
sentença.
Os filhos do nó 1 (2, 3 e 4) correspondem a uma produção da gramática S → 0TS.
O mesmo acontece com:
O nó 3 - T → S1T.
Os nós 4 e 5 - S → 0.
O nó 7 - T → 10.
A partir da árvore, a sentença gerada seria percorrendo as folhas da esquerda para a direita, ou
seja, a sequência seria 2, 9, 6, 10, 11 e 8, sendo a sentença 001100.
 COMENTÁRIO
Se tivesse sido utilizada uma derivação mais à esquerda para a árvore, a ordem seria:
S ⟹ 0TS ⟹ 0S1TS ⟹ 001TS ⟹ 00110S ⟹ 001100
Já uma derivação mais à direita produziria a seguinte sequência:
S ⟹ 0TS ⟹ 0T0 ⟹ 0S1T0⟹0S11000 ⟹ 001100
Mas a sentença final seria a mesma.
VALIDANDO TOKENS DE UM PROGRAMA
Até agora, temos trabalhado com uma gramática bem distante das situações de uma
linguagem de programação. Vamos nos aproximar da realidade.
Considere uma gramática que realiza a soma ou subtração de dois inteiros. Inicialmente,
teríamos que definir através de expressões regulares o que é um número e os operadores, por
exemplo:
int → D D*
D → [0-9]
+ → +
- → -
A seguir, vamos definir o conjunto das produções válidas:
PRODUÇÃO REGRA
E → E + E 1
E → E- E 2
E → int 3
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Este conjunto de regras poderia ser representado como uma sentença da seguinte forma: E →E
+E | E -E | int
Pois bem, a partir destas regras, vamos validar a expressão 125 + 79.
Intuitivamente, podemos perceber que, pela aplicação da regra 3 duas vezes e da regra 1, a
sentença é válida na gramática, mas vamos passo a passo.
A primeira coisa que temos que notar é que a Análise Sintática ocorre a partir dos tokens, ou
seja, o analisador léxico passaria a seguinte lista de tokens:
TOKEN LEXEMA
Int 125
+ +
Int 79
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Desta forma, a sentença a ser analisada pelo parser seria int + int.
PASSO 1
PASSO 2
PASSO 3
PASSO 1
Aplicando a Regra 3 uma primeira vez, substituímos um dos int por E, e a expressão fica E + int.
PASSO 2
Aplicando a Regra 3 uma segunda vez, substituímos o outro int por E, e a expressão fica E + E.
PASSO 3
Aplicando a Regra 1, substituímos E + E por E.
Como chegamos ao final da análise e obtivemos o símbolo inicial, a expressão existe na
linguagem, ou, em outras palavras, o comando está sintaticamente correto.
Esta forma que apresentamos foi ascendente. Outra forma de fazer seria descendente, com os
seguintes passos:
PASSO 1
Aplicando a Regra 1, substituímos E por E + E.
PASSO 2
Aplicando a Regra 3 uma primeira vez, substituímos um dos E por int, e a expressão fica E + int.
PASSO 3
Aplicando a Regra 3 uma segunda vez, substituímos o outro E por int, e a expressão fica int +
int.
Que corresponde à expressão avaliada.
Observe que, na realidade, as duas formas produzem a mesma árvore de derivação (Figura 8a)
e de sintaxe (Figura 8b), a primeira forma a partir das folhas e a segunda a partir da raiz.
javascript:void(0)
javascript:void(0)
javascript:void(0)
 Figura 8 ‒ Árvores geradas. Fonte: O Autor, 2020.
Vejamos agora exemplos mais complexos.
 EXEMPLO
Considere que agora nossa gramática irá se referir a todas as operações aritméticas entre dois
inteiros, mais o uso de parênteses.
Vejamos a sua especificação:
int → D D*
D → [0-9]
+ → +
- → -
* → *
/ → /
( → (
) → )
Conjunto de produções:
PRODUÇÃO REGRA
E → E + E 1
E → E - E 2
E → E * E 3
E → E / E 4
E → (E) 5
E → int 6
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Temos agora os acréscimos de dois operadores, * e /, mais a pontuação pelos parênteses.
A gramática ainda poderia ser representada da seguinte forma:
E →E +E | E -E | E *E | E/E | (E) | int
Estas produções especificam que uma expressão pode ser:
Uma operação aritmética (Regra 1 a 4).
Uma expressão entre parênteses (Regra 5).
Um número inteiro (Regra 6).
Considere agora as seguintes expressões:
(60 + 40) / 5
Que seria entregue pelo Scanner como (int + int) / int.
Vamos fazer então a derivação:
Pela aplicação da Regra 6, três vezes a estrutura sentencial se torna (E + E) / E
Pela aplicação da Regra 1, temos: (E) / E
Pela aplicaçãoda Regra 5, temos: E / E
Pela aplicação da Regra 4, temos: E
O comando está correto.
(60 + 40)5
Que seria entregue pelo Scanner como (int + int ) int
Pela aplicação da Regra 6, três vezes a estrutura sentencial se torna: (E + E)E
Pela aplicação da Regra 1, temos: (E)E
Pela aplicação da Regra 5, temos: EE
Como não existe regra que gere a produção EE, o comando está errado!
GRAMÁTICAS AMBÍGUAS
Determinadas gramáticas podem permitir a derivação de mais de uma árvore para a mesma
expressão. São as Gramáticas Ambíguas.
 ATENÇÃO
Este tipo de gramática é um problema para os compiladores, pois significa que, dependendo do
contexto, uma das árvores geradas será correta e a outra não.
Considere agora esta expressão:
60 + 40 / 5
� Atenção! Para visualização completa da equação utilize a rolagem horizontal
O parser receberia do scanner a seguinte expressão int + int / int.
Vamos validar a expressão considerando as seguintes regras:
PRODUÇÃO REGRA
E → E + E 1
E → E - E 2
E → E * E 3
E → E / E 4
E → (E) 5
E → int 6
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Pela aplicação da Regra 6, três vezes a estrutura sentencial se torna E + E / E
Pela aplicação da Regra 1, temos E / E
Pela aplicação da Regra 4, temos E
Validou, mas existe outra sequência que também valida:
Pela aplicação da Regra 6, três vezes a estrutura sentencial se torna E + E / E
Pela aplicação da Regra 4, temos E + E
Pela aplicação da Regra 1, temos E
Note que temos uma situação de ambiguidade, pois as sequências gerariam árvores diferentes
(Figura 9):
 Figura 9 ‒ Árvores sintáticas geradas pela ambiguidade. Fonte: O Autor, 2020.
 COMENTÁRIO
Para você, pode parecer estranha a árvore que realiza a soma primeiro, pois aprendemos nos
bancos escolares que a divisão tem precedência. O que acontece é que a gramática da forma
que foi especificada não mostra esta precedência.
Para acabar com a ambiguidade, temos que estender a nossa gramática, de forma a deixar
explícita a existência das precedências. Uma possível solução seria:
int → D D*
D → [0-9]
+ → +
- → -
* → *
/ → /
( → (
) → )
Conjunto de produções:
PRODUÇÃO REGRA
E → E + T 1
E → E - T 2
E → T 3
T → T * F 4
T → T / F 5
T → F 6
F → int 7
F → (E) 8
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
A gramática possui agora 3 símbolos variáveis que representam:
E – Soma e subtração (precedência mais baixa).
T – Multiplicação e divisão (precedência intermediária).
F – Números e expressões entre parênteses (precedência mais alta).
Esta gramática permite apenas gerar uma árvore de derivação (Figura 10), pois não é mais
ambígua.
 Figura 10 ‒ Árvores derivação gerada. Fonte: O Autor, 2020.
No vídeo a seguir, você encontrará um exemplo de uma Gramática Ambígua, os problemas que
podem ocorrer e a vantagem de empregar uma Gramática Livre de Contexto (GLC).
VERIFICANDO O APRENDIZADO
1. AS DERIVAÇÕES RESULTANTES DAS PRODUÇÕES DE UMA GRAMÁTICA
PODEM SER DESCRITAS DE FORMA LINEAR OU EM FORMA DE ÁRVORE DE
DERIVAÇÃO. CONSIDERE A ÁRVORE DE DERIVAÇÃO ABAIXO:
SABENDO-SE QUE AS PRODUÇÕES DA GRAMATICA SÃO E →E +E | E -E | INT E
QUE FOI REALIZADA UMA DERIVAÇÃO MAIS À DIREITA DESCENDENTE,
ESCOLHA A OPÇÃO QUE MOSTRA A REPRESENTAÇÃO CORRETA NA FORMA
LINEAR:
A) E ⟹ E E ⟹ E + E ⟹ E + int ⟹ int + int
B) E ⟹ E E ⟹ E + E ⟹ int + E ⟹ int + intS5
C) E ⟹ E + E ⟹ int + E ⟹ int + int
D) E ⟹ E + E ⟹ E + int ⟹ int + int
E) E ⟹ int E ⟹ int + E ⟹ int + intS5
2. GRAMÁTICAS LIVRES DE CONTEXTO SÃO DEFINIDAS PELA LISTA DE
SÍMBOLOS TERMINAIS, DE SÍMBOLOS NÃO TERMINAIS, PELO SÍMBOLO
INICIAL E PELAS PRODUÇÕES. CONSIDERE A GRAMÁTICA ABAIXO:
S → 0S0
S → 1S1
S → 0
S → 1
S → Ɛ
A PARTIR DE SUA ANÁLISE, ESCOLHA A OPÇÃO ABAIXO QUE CORRESPONDE
A UMA SENTENÇA:
A) 0S1
B) 0001110
C) SS0
D) 110S
E) 010
GABARITO
1. As derivações resultantes das produções de uma gramática podem ser descritas de forma
linear ou em forma de árvore de derivação. Considere a árvore de derivação abaixo:
Sabendo-se que as produções da gramatica são E →E +E | E -E | int e que foi realizada uma
derivação mais à direita descendente, escolha a opção que mostra a representação correta na
forma linear:
A alternativa "D " está correta.
Como vamos operar de forma descendente, começamos com a raiz com o símbolo inicial da
gramática equivalente a E.
A seguir, expandimos E utilizando a segunda produção equivalente a E ⟹ E + E.
Como estamos utilizando derivação mais à direita, expandimos o E mais à direita por int.
Ficando então E ⟹ E + E ⟹ E + int
E, finalmente, expandimos o último E ficando como E ⟹ E + E ⟹ E + int ⟹ int + int
2. Gramáticas Livres de Contexto são definidas pela lista de símbolos terminais, de símbolos
não terminais, pelo símbolo inicial e pelas produções. Considere a gramática abaixo:
S → 0S0
S → 1S1
S → 0
S → 1
S → Ɛ
A partir de sua análise, escolha a opção abaixo que corresponde a uma sentença:
A alternativa "B " está correta.
Os símbolos terminais da gramática são 0 e 1 e o não terminal S.
Estruturas formadas por símbolos terminais e não terminais que pertençam à gramática
correspondem a formas sentenciais.
Formas sentenciais que possuem apenas símbolos terminais formam as sentenças.
Portanto, a resposta é 0001110.
MÓDULO 3
 Classificar o funcionamento dos algoritmos ascendentes e descendentes
MÉTODOS DE IMPLEMENTAÇÃO
Os analisadores sintáticos podem utilizar os seguintes métodos para sua implementação:
MÉTODOS UNIVERSAIS
Que podem tratar qualquer gramática. Apesar de lidarem com qualquer tipo de gramática, são
ineficientes e, portanto, não utilizados em compiladores comerciais.
MÉTODOS DESCENDENTES (TOP-DOWN OU PARSER LL)
Que buscam construir a árvore de derivação a partir da raiz para as folhas e que trabalham
como gramática LL.
MÉTODOS ASCENDENTES (BOTTOM-UP OU PARSER LR)
Que tratam gramáticas LR e constroem a árvore de derivação das folhas para a raiz.
 ATENÇÃO
Os dois últimos métodos varrem a entrada da esquerda para a direita e são amplamente
utilizados tanto em implementações manuais, que normalmente empregam métodos
descendentes, quanto por geradores de analisadores sintáticos, mormente métodos
ascendentes.
ALGORITMOS DE ANÁLISE SINTÁTICA
ASCENDENTES
Estes algoritmos são chamados também Análise Sintática LR e constroem a árvore de sintaxe
das folhas para a raiz.
Ele começa sua análise com uma entrada de tokens e tenta reescrever a árvore até o símbolo
inicial. Na realidade, ele tenta localizar os símbolos mais básicos e, a partir destes, elementos
maiores que enquadrem os mais básicos, e assim, sucessivamente.
 ATENÇÃO
Se ao final da análise for obtida uma árvore de sintaxe válida pela gramática da linguagem, ou
seja, o símbolo inicial está na raiz e nos rótulos das folhas, temos a cadeia de entrada,
formando, desta forma, uma sentença da linguagem, e ela é passada para o próximo passo da
compilação.
Se isto não for possível, a cadeia não pertence à linguagem especificada pela gramática.
Este processo de construção das folhas para a raiz é chamado redução, já que a cada passo se
tenta reduzir uma cadeia de tokens (ou subcadeia) ao seu símbolo de origem, seguindo
sucessivamente até ser atingido o símbolo inicial da gramática.
O funcionamento geral é apresentado a seguir:
Toma-se uma determinada sequência de tokens S.

Procura-se por uma subcadeia S que possa ser substituída pelo seu símbolo de origem R na
gramática.

Repetir o passo (2) até que R = símbolo inicial da gramática. Se isso não for possível, S não
pertence à gramática.
Vejamos um exemplo:
Considere a seguinte gramática:
PRODUÇÃO REGRA
E → E + T | T 1
T → T * F | F 2
F → x | y | z | (E) 3
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Verificando se a cadeia x + y * z pertence à linguagem.
PASSO 1
PASSO 2
PASSO 3
PASSO 4
PASSO 5
PASSO 6
PASSO 7
PASSO 8
PASSO 1
Substituir o x por F utilizando a regra 3.
x + y *z ⟹ F + y * z
Em termos de árvore seria:
PASSO 2
Aplicar a regra 2 a F.
F + y * z ⟹ T + y * z
A árvore fica então:
PASSO 3
Aplicar a regra 1 a T.
T + y * z ⟹ E + y * z
A árvore fica então:
Note que x já foi reduzido ao símbolo inicial E.
PASSO 4
Substituir o y por F utilizando a regra 3.
T + y * z ⟹ E + F * z
A árvore fica então:
PASSO 5
Aplicar a regra 2 a F.
E + F * z ⟹ E + T * z
A árvore fica então:
PASSO 6
Aplicar a regra 3 a z, substituindo-o por F.
E + T * z ⟹ E + T * F
A árvore fica então:
PASSO 7
Aplicar a regra 2 e substituir a multiplicação por T.
E + T * F ⟹ E + T
A árvore fica então:
PASSO 8
Aplicar a regra 1 à soma substituído por ET.
E + T ⟹ E
A árvore fica então:
ALGORITMOS DE ANÁLISE SINTÁTICA
DESCENDENTES (ASD)
Neste tipo de algoritmo, a Análise Sintática parte da raiz da árvore em direção às folhas, ou
seja, a partir do símbolo inicial da gramática, procura substituir os símbolos não terminais de
forma a obter nas folhas a cadeia desejada.
Também conhecida como Análise LL (do inglês left left) , ela lê a entrada de texto da esquerda
para a direita, e produz uma derivação mais à esquerda.
O que significa que, observando apenas o primeiro símbolo da cadeia, o algoritmo decide qual
regra de derivação deve utilizar.
Funcionamento geral:
1
Faz a leitura de uma cadeia β e do símbolo inicial da gramática S.
2
Busca-se uma regra que permita derivar ou pelo menos se aproximar de β.
3
Repete-se o passo 2 até que a cadeia não tenha mais símbolos não terminais.
4
Compara-se a cadeia obtida com β; se for igual à derivação, foi bem-sucedida. Se forem
diferentes, significa que a cadeia analisada não pertence à linguagem.
Vejamos um exemplo. Considere a seguinte gramática:
S→cTd
T→ a
Se a sequência de tokens for cad, a construção seria da seguinte forma:
Criar a árvore com o símbolo inicial na raiz, no caso S:
A partir desta árvore, deriva-se a primeira produção expandindo-se S.
A seguir, expande-se T, o que origina a árvore representada na figura.
 ATENÇÃO
Note que a lista de tokens cad aparece nas folhas da esquerda para a direita, o que quer dizer
que são válidas na gramática.
ANALISADORES DESCENDENTES COM
RETROCESSO
Neste tipo de implementação de ASD, se ao se fazer uma avaliação ocorrer um erro e ainda
houver como continuar a análise, o processo retrocede ao último estado válido e reinicia a
expansão.
A utilização do retrocesso permite que um conjunto maior de GLCs sejam analisadas,
entretanto apresenta algumas desvantagens que derivam da natureza não determinística do
método:
A análise é mais demorada.
A recuperação de erros é mais difícil.
Pode gerar problemas para a Análise Semântica e posterior geração de código.
 ATENÇÃO
DETERMINISMO
Analisadores sintáticos são determinísticos se sempre souberem que ação tomar,
independentemente da entrada de texto.
Vejamos o funcionamento deste método. Considere a seguinte gramática:
S → xTz
T → xy | y
Para a cadeia de entrada xyz, temos a seguinte sequência de análise:
1 – Inicialmente, é criada a árvore com o símbolo inicial da gramática na raiz, e a entrada não é
processada.
2 – A seguir, S é expandido pela primeira produção, e o apontador da entrada é posicionado no
primeiro símbolo da cadeia.
3 - É feita a comparação da folha mais à esquerda com o símbolo apontado na entrada.
4 - Como a folha mais à esquerda possui o mesmo terminal da cadeia, o símbolo é consumido,
e o apontador avança para o próximo símbolo.
5 - Como a próxima folha é um não terminal (T), faz-se a sua expansão. Como existem duas
produções possíveis, xy ou y, vamos utilizar a primeira.
6 - Faz-se a comparação da folha mais à esquerda ainda não processada com o símbolo
apontado na cadeia de entrada.
7 - Como a folha em análise possui um símbolo terminal e ele não é igual ao símbolo da
entrada, ocorreu uma falha. Ocorre, então, o retrocesso, eliminando a última expansão.
8 - Como ainda existe uma produção que pode ser utilizada para expandir T, ela é realizada. Se
não houvesse mais produções para fazer a expansão de T, o ASD deveria retornar um erro e
fazer o seu tratamento.
9 - Faz-se a comparação da folha mais à esquerda ainda não processada com o símbolo
apontado na cadeia de entrada.
10 - Como a folha em processamento possui o mesmo terminal da cadeia, o símbolo é
consumido e o apontador avança para o próximo símbolo.
11 - Como a próxima folha a ser processada possui um símbolo terminal, ele é comparado com
o símbolo apontado na entrada.
12 - Como a folha em processamento possui o mesmo terminal da cadeia, o símbolo é
consumido. Como a cadeia de entrada acabou e todos os tokens foram reconhecidos, a cadeia
é aceita, pois pertence à gramática.
 RESUMINDO
Este exemplo nos mostra que:
A construção da árvore ocorre na raiz para as folhas, utilizando o símbolo inicial na raiz.
À medida que símbolos não terminais são encontrados, eles são expandidos.
Se a expansão de um não terminal gerar um símbolo terminal que não tem
correspondência com a cadeia de entrada, ocorre o retrocesso, o que implica realizar
tentativas e erros até encontrar a produção correta.
Símbolos terminais são consumidos, ou seja, retirados da entrada quando correspondem
a uma produção correta na gramática.
Se ao final não for gerada uma sentença correta nas folhas, será reportado um erro.
O sistema é não determinístico, pois mais de uma produção pode ter que ser testada para
um mesmo símbolo não terminal.
A quantidade de derivações cresce de forma exponencial em função do tamanho da
cadeia de entrada e do número de produções da gramática.
ANALISADORES DESCENDENTES PREDITIVOS
O uso do retrocesso gera, como vimos, várias desvantagens. Uma forma de evitar o seu uso é
criar um analisador preditivo.
Neste tipo de analisador, a ideia é descobrir qual construção utilizar, evitando, assim, o
retrocesso.
 COMENTÁRIO
Imagine: Se no exemplo do ASD com retrocesso, no passo 5, tivéssemos utilizado a produção T
→ y em vez da produção T → xy, não teriam ocorrido o erro e o retrocesso.
Fica a questão: Então, como o ASD consegue “prever” a produção a ser utilizada?
 RESPOSTA
Inicialmente, o que você deve entender é que nem toda gramática pode ser analisada por este
tipo de ASD. É necessário que ela permita que, ao olhar o primeiro símbolo da cadeia de
entrada, possa se determinar qual produção deve ser utilizada. Veja que a gramática do último
exemplo não permitia isto.
Para tal, a gramática deve ter as seguintes características:
NÃO PODE TER RECURSÃO À ESQUERDA
O lado direito das produções deve começar com terminais.
DEVE ESTAR FATORADA
javascript:void(0)
javascript:void(0)
Para cada símbolo não terminal, deve existir apenas uma regra que comece com o mesmo
terminal.
Este tipo de gramática é chamado de LL(1) (Left to Right - Leftmost derivation 1) , que
significa que a cadeia é lida da esquerda para a direita, fazendo uma derivação mais à
esquerda, e que é utilizado o símbolo à frente, daí o 1, para determinar que produção utilizar na
expansão.
O conjunto de símbolos à frente que são analisados para determinar a produção denomina-se
lookahead.
Vejamos um exemplo.
Considere a seguinte gramática:
E → +EE Produção 1
E → *EE Produção 2
E → a Produção 3
E → b Produção 4
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Note que ela obedece a todas as regras, pois todas as produções começam com um símbolo
terminal e não existem duas produções que começam com o mesmo símbolo.
Considere agora que queremos avaliar a seguinte expressão “+ a * ba”.
Inicialmente, criamos a árvore com o símbolo inicial na raiz e, ao fazermos a análise do
primeiro símbolo (+), notamos que temos que aplicar a produção 1.
Após a expansão da raiz, analisamos o próximo símbolo a. Ele indica que temos que aplicar a
produção 3 na expansão do segundo E.
Após a expansão, o próximo símbolo * indica que temos que aplicar a produção 2 na expansão
doterceiro E.
Após a expansão, o próximo símbolo b indica que temos que aplicar a produção 4 na expansão
do quarto E.
Após a expansão, o próximo símbolo a indica que temos que aplicar a produção 3 na expansão
do quinto E.
Finalmente, chegamos ao final da análise e verificamos que a sentença gerada corresponde a
uma construção válida na gramática.
Note que, neste tipo de ASD, nunca irá ocorrer retrocesso, e seu funcionamento é bem mais
rápido que o anterior, pois não existe tentativa e erro.
 COMENTÁRIO
Um fato que você deve ter achado estranho é a forma da notação utilizada + a * ba em vez de a
+ b * a, que utilizamos normalmente. Esta notação é chamada de polonesa. Ela foi utilizada no
exemplo para podermos definir a gramática como LL(1), pois, se utilizássemos a notação
normal, a produção 1, por exemplo, seria E → E + E, que começaria com um não terminal, ou
seja, teríamos uma recursão à esquerda.
Neste vídeo, você encontrará exemplos de analisadores descendentes.
VERIFICANDO O APRENDIZADO
1. PARSERS PODEM SER IMPLEMENTADOS COM ALGORITMOS
ASCENDENTES OU DESCENDENTES. DENTRE OS DESCENDENTES, TEMOS O
PREDITIVO. QUANTO A ESTE ALGORITMO EM RELAÇÃO À GRAMÁTICA
ABAIXO, PODEMOS AFIRMAR QUE:
S → (L)
S → A
L : → L , S
L → S
A) Ela pode ser analisada por estar fatorada.
B) Ela pode ser analisada por ser LL(1).
C) Ela não pode ser analisada por não estar fatorada.
D) Ela pode ser analisada por ter recursão à esquerda.
E) Ela não pode ser analisada por ter recursão à esquerda.
2. DURANTE O PROCESSO DE ANÁLISE, O PARSER, A PARTIR DAS
PRODUÇÕES DA GRAMÁTICA E DA CADEIA DE ENTRADA, GERA ÁRVORES DE
DERIVAÇÃO QUE REPRESENTAM A FORMA DE SER EXECUTADO O COMANDO
QUE CONSTA NA ENTRADA.
CONSIDERE A SEGUINTE GRAMÁTICA:
E → E + T|T
T → T * F | F
F → INT |(E)
DURANTE A ANÁLISE DA EXPRESSÃO INT * INT – INT, EM DETERMINADO
PONTO FOI GERADA A SEGUINTE ÁRVORE INTERMEDIÁRIA:
COM BASE NA ÁRVORE, NA GRAMÁTICA E NA EXPRESSÃO, PODEMOS
AFIRMAR QUE:
A) O analisador é descendente preditivo.
B) O analisador é descendente com retrocesso.
C) O analisador é descendente sem retrocesso.
D) O analisador é ascendente.
E) O analisador é ascendente com retrocesso.
GABARITO
1. Parsers podem ser implementados com algoritmos ascendentes ou descendentes. Dentre
os descendentes, temos o preditivo. Quanto a este algoritmo em relação à gramática abaixo,
podemos afirmar que:
S → (L)
S → a
L : → L , S
L → S
A alternativa "E " está correta.
Analisadores sintáticos preditivos exigem que a gramática não tenha recursão à esquerda e
esteja fatorada, o que equivale a ser LL(1). A gramática proposta possui recursão à esquerda,
pois a terceira produção – L : → L, S – provoca esta situação.
2. Durante o processo de análise, o parser, a partir das produções da gramática e da cadeia de
entrada, gera árvores de derivação que representam a forma de ser executado o comando que
consta na entrada.
Considere a seguinte gramática:
E → E + T|T
T → T * F | F
F → int |(E)
Durante a análise da expressão int * int – int, em determinado ponto foi gerada a seguinte
árvore intermediária:
Com base na árvore, na gramática e na expressão, podemos afirmar que:
A alternativa "D " está correta.
Todo método descendente começa criando a raiz com o símbolo inicial da gramática, que no
caso é E. Como a árvore intermediária não possui E na raiz, ela tem que estar sendo construída
a partir das folhas, portanto o analisador é ascendente.
MÓDULO 4
 Classificar as formas de projetar analisadores sintáticos e a utilização de programas que
os geram
IMPLEMENTAÇÃO DO ANALISADOR
SINTÁTICO ASCENDENTE
Em sua implementação, um algoritmo ascendente vai trabalhar com um autômato de pilha e
vai necessitar de:
Um buffer onde ficam armazenados os tokens de entrada.
Uma pilha onde é feito o controle dos tokens processados.
Uma tabela que indica a transição de estados a ser realizada.
Uma tabela de regras gramaticais a serem aplicadas no token de entrada com as ações a
serem realizadas.
A base de funcionamento do algoritmo são duas ações – Reduzir e deslocar (em inglês, shift
reduce) .
REDUÇÃO
Compreende substituir uma produção (a parte à direita da gramática) pela parte à esquerda.
Por exemplo, na regra E → E + E, se tivermos a expressão E + E, iremos substituí-la por E.
DESLOCAMENTO
Corresponde a varrer a entrada colocando o token atual na pilha e lendo o próximo. Por
exemplo, se tivermos na entrada id + int e for feito o deslocamento, id irá para o topo da pilha e
será processado o +.
Para um melhor entendimento, vamos a um exemplo:
Considere a seguinte gramática referente à soma de números inteiros binários:
E → E + E
E → int
E a expressão int + int
O primeiro fator a ser identificado são os handles, que são uma subcadeia de caracteres que
correspondem a uma produção, ou seja, ao lado direito de uma regra da gramática.
No caso de nosso exemplo, os handles são “E + E” e “int”.
Para cada um destes handles, a produção redutora é:
HANDLE PRODUÇÃO SIGNIFICADO Redução
Int E → int Substituir int por E 1
E + E E → E + E Substituir E + E por E 2
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Outro símbolo importante no processamento é o $, que identifica o final tanto da pilha quanto
da cadeia de entrada.
A próxima estrutura é a criação da tabela de regras de ação que possui basicamente a seguinte
lógica, com base nos símbolos da pilha e na entrada:
PILHA ENTRADA AÇÃO SIGNIFICADO
$
Diferente
de $
Deslocar
Ler o próximo símbolo e colocá-lo
na pilha
Corresponde a
uma produção
Indiferente Reduzir Aplicar a regra de redução, retirar
o símbolo da pilha e substituí-lo
pela redução
Não corresponde
a uma produção
Diferente
de $
Deslocar
Ler o próximo símbolo e colocá-lo
na pilha
$ $ Aceitar A expressão existe na gramática
Símbolo diferente
do inicial
$ Erro Realizar tratamento de erro
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
No caso específico de nosso exemplo, a tabela seria:
PILHA ENTRADA AÇÃO REGRA
$ Diferente de $ Deslocar 1
Int Indiferente Reduzir 2
E + E Indiferente Reduzir 3
+ Diferente de $ Deslocar 4
E Indiferente Deslocar 5
$ $ Aceitar 6
Diferente de $ $ Erro 7
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
PASSO 1
Na inicialização, colocamos na pilha o símbolo $ para identificar o seu final e na entrada
também acrescentamos o mesmo símbolo ao final da expressão que está sendo analisada.
Ficamos, então, da seguinte forma:
PASSO 2
Aplicando a regra 1, lemos o próximo símbolo e o empilhamos retirando-o da entrada:
PASSO 3
Lemos o primeiro elemento da pilha e verificamos se é uma produção:
PASSO 4
No caso, int é uma produção. Aplicamos, então, a redução 1 e o substituímos por E, salvando E
na pilha:
PASSO 5
Retiramos novamente o primeiro símbolo da pilha e vamos analisar se é uma produção:
Como E não é uma produção, a pilha está vazia e temos símbolos na entrada, salvamos ‘E’ na
pilha e aplicamos a regra 1. Lemos o próximo símbolo na entrada colocando-o na pilha:
PASSO 6
Retiramos novamente o primeiro símbolo da pilha e vamos analisar se é uma produção:
Como ‘+’ não é uma produção e ainda temos símbolos na pilha, fazemos uma nova leitura para
a análise:
Como ‘E + ‘não é uma produção, a pilha está vazia e temos símbolos na entrada, salvamos E na
pilha. Aplicamos a regra 1 e lemos o próximo símbolo na entrada colocando-o na pilha:
PASSO 7
Lemos o primeiro elemento da pilha e verificamos se é uma produção:
Como, no caso, int é uma produção, aplicamos, então, a redução 1 e o substituímos por E,
salvando E na pilha:
PASSO 8
Lemos novamente o primeiro elemento da pilha e verificamos se é uma produção:
Como ‘E’ não é uma produção e temos mais símbolos na pilha, continuamos lendo até
encontrar uma produção ou chegarmos ao final da fila. No caso, achamos uma produção:
Como ‘E + E’ é uma produção, aplicamos a redução 2 substituindo por Ee salvando E na pilha:
PASSO 9
Lemos novamente o primeiro elemento da pilha e verificamos se é uma produção:
Como ‘E’ não é uma produção, mas é o símbolo inicial da gramática, e tanto a pilha quanto a
entrada estão vazias, significa que ocorreu a aceitação, não havendo erro na expressão.
IMPLEMENTAÇÃO DO ANALISADOR
SINTÁTICO DESCENDENTE PREDITIVO
Dentre as várias formas possíveis de implementar um ASD preditivo, o não recursivo baseado
em tabela é a mais comum. Para podermos construir este tipo de parser, precisamos ter
algumas condições:
A gramática tem que ser LL(1), ou seja, sem recursão à esquerda e fatorada.
Construir os conjuntos first e follow, que indicam como escolher a produção a ser
aplicada na expansão do símbolo não terminal.
Quanto à estrutura, iremos necessitar de:
Um buffer de entrada onde $ indica o fim da cadeia de entrada.
Um fluxo de saída.
Uma pilha cujo fundo é marcado por $ e inicializada com o símbolo da gramática.
Uma tabela sintática preditiva.
 Figura 11 ‒ Estrutura ASD não recursivo preditivo. Fonte: Adaptado de Aho et al, 2008.
Observe na Figura 11 que o símbolo no topo da pilha é X, que é o inicial da entrada e que será
analisado. A partir desta configuração, vamos ver como funciona este esquema:
SE X = $ E A = $
Significa que toda a entrada foi analisada e não ocorreu, desta forma ela é reconhecida.
javascript:void(0)
SE X = A E <> $
Desempilha X e avança de um símbolo na entrada.
SE X É NÃO TERMINAL
Consulta a tabela sintática M e procura a produção a ser aplicada.
Se não existir produção para X em M, ou seja, a entrada é vazia, retorna um erro.
Se contém uma produção, por exemplo, X :: = UVW, então substitui na pilha X por UVW (U
no topo).
CONSTRUÇÃO DOS CONJUNTOS FIRST E
FOLLOW
Vejamos agora como construir os conjuntos First e Follow. Para tal, considere a seguinte
gramática:
S→ cAa
A→ cB | B
B→ bcB| ε
Lembrando que ε significa produção vazia.
CONJUNTO FIRST
O conjunto First é composto pelos símbolos terminais que podem iniciar (que podem aparecer
mais à esquerda) das sentenças derivadas de uma forma sentencial ou de suas sequências
derivadas.
Para o criar, utilizamos uma função First(α), tal que α representa uma forma sentencial, que
retorna o conjunto de First da forma sentencial.
javascript:void(0)
javascript:void(0)
Para isso, temos algumas regras:
Se α = ε ou α → ε então ε pertence ao conjunto First.
Se α é um terminal, então ele próprio pertence ao conjunto First.
Se α é um não terminal, então todos os terminais de todas as suas produções pertencem ao
conjunto First.
Para maior clareza, vejamos como iremos derivar o conjunto First dos não terminais em nossa
gramática.
Primeiramente criamos uma tabela com uma linha para cada um dos não terminais da
gramática com o seu conjunto First Vazio:
Não Terminal First
S ∅
A ∅
B ∅
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Muito bem. Começamos observando que, em S→ cAa, temos um terminal c na primeira
posição; portanto, c pertence a First(S):
Não Terminal First
S {c}
A ∅
B ∅
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Tratemos agora o A. Como ele tem duas produções, mas somente a primeira tem um terminal
c, este pertence ao conjunto de A:
Não Terminal First
S {c}
A {c}
B ∅
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Vamos agora tratar o B. Com ele, há duas produções que atendem às regras, que são bc e ε. E
as duas entram em seu conjunto First:
Não Terminal First
S {c}
A {c}
B {b, ε }
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Agora, temos que rever se S ou A herdam algo. Como a única produção de S é iniciada por
terminal, não existe nada a ser reprocessado; porém, A tem uma produção do tipo A→ B.
Portanto, First(A) = First(A) ∪ First(B), e a tabela final fica sendo então:
Não Terminal First
S {c}
A { b, c, ε }
B {b, ε }
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
CONJUNTO FOLLOW
O conjunto Follow(X) é definido como sendo composto pelos símbolos terminais que podem
aparecer imediatamente após X.
As regras gerais para produção do conjunto Follow são:
Se um símbolo X é o não terminal mais à direita de alguma forma sentencial, então $
estará no conjunto.
Se X é o símbolo inicial da gramática, $ será o seu conjunto Follow.
Se existir produção na forma V→ cST, então tudo em First(T), exceto vazio(Ɛ), está em
Follow(S).
Se existir produção do tipo A → aB ou produção A → aBC onde First(C) contém ɛ, inclua
Follow(A) em Follow(B).
Vejamos um exemplo continuando com nossa gramática:
S→ cAa
A→ cB | B
B→ bcB| ε
E seu conjunto First:
Não Terminal First
S {c}
A { b, c, ε }
B {b, ε }
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Comecemos analisando S. Como ele é o símbolo inicial da gramática, terá como Follow $:
Não Terminal Follow
S {$}
A ∅
B ∅
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Analisando as possibilidades do símbolo A, que pela produção cAa após A pode vir o símbolo
A, sendo esta a única produção onde ele aparece à direita:
Não Terminal Follow
S {$}
A {a}
B ∅
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Analisando o símbolo B, ele aparece à direita em 3 produções:
A→ cB
A→ B
Pelas regras, a primeira produção faz com que Follow(B) receba Follow(A):
Não Terminal Follow
S {$}
A {a}
B {a}
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
 ATENÇÃO
No conjunto Follow nunca aparece ɛ
TABELA SINTÁTICA
De posse desses conjuntos, podemos construir a tabela sintática para o nosso exemplo:
Isto feito, podemos fazer um exemplo passo a passo da análise da expressão “cbca”.
1. Inicializamos a pilha com o símbolo inicial da gramática S e posicionamos a leitura no
primeiro símbolo da entrada “c”:
2. Como o símbolo no topo de pilha é S e a entrada c, fazemos a expansão de S retirando-o da
pilha e o substituindo por cAa:
3. Como o símbolo no topo de pilha é c e a entrada c, fazemos o casamento dos símbolos,
desempilhamos c e avançamos o ponteiro de entrada:
4. Como agora o símbolo no topo da pilha é A e o da entrada b, fazemos a expansão de A
obedecendo a tabela sintática:
5. Após a expansão no topo de pilha, temos B, e na entrada b, pela tabela, devemos fazer uma
nova expansão, substituindo B na pilha por bcB:
6. Agora, tanto na pilha como na entrada, temos b; portanto, fazemos o casamento entre eles,
desempilhamos b e avançamos o ponteiro da entrada:
7. Como novamente temos no topo da pilha e na entrada o mesmo símbolo, fazemos o
casamento, desempilhamos e avançamos o ponteiro:
8. Como no topo da pilha temos B e na entrada a consultamos a tabela, e observamos que
devemos fazer uma expansão vazia, então retiramos B da pilha:
9. Como novamente temos no topo da pilha e na entrada o mesmo símbolo, fazemos o
casamento, desempilhamos e avançamos o ponteiro:
10. Como agora temos $ tanto na pilha como na entrada, indicando que as duas estão vazias,
isto significa que a análise foi bem-sucedida e a sentença aceita.
Assista, agora, o emprego do software GALS.
VERIFICANDO O APRENDIZADO
1. DURANTE A PREPARAÇÃO PARA A CRIAÇÃO DA TABELA SINTÁTICA DE UM
ANALISADOR DESCENDENTE PREDITIVO, TEMOS QUE DEFINIR OS
CONJUNTOS FOLLOW E FIRST QUE MOSTRAM, RESPECTIVAMENTE, OS
TERMINAIS QUE PODEM SEGUIR UM DETERMINADO SÍMBOLO E OS
TERMINAIS QUE APARECEM MAIS À DIREITA EM UMA FORMA SENTENCIAL.
NO PROCESSAMENTO DE UMA DETERMINADA GRAMÁTICA, FORAM
ESTABELECIDOS OS CONJUNTOS FOLLOW MOSTRADOS NA TABELA ABAIXO:
NÃO TERMINAL FOLLOW
S {$}
A {A, Ɛ}
B {A}
� ATENÇÃO! PARA VISUALIZAÇÃOCOMPLETA DA TABELA UTILIZE A
ROLAGEM HORIZONTAL
COMO BASE NESTES CONJUNTOS, PODEMOS AFIRMAR QUE:
I. HOUVE UM ERRO NO PROCESSAMENTO.
PORQUE
II. NO CONJUNTO FOLLOW NÃO PODE APARECER $.
QUANTO ÀS AFIRMATIVAS ACIMA, PODEMOSAFIRMAR QUE:
A) As duas estão erradas.
B) As duas estão corretas.
C) Somente a primeira está correta.
D) Somente a segunda está correta.
E) A segunda é uma justificativa da primeira.
2. A IMPLEMENTAÇÃO DE UM ANALISADOR SINTÁTICO ENVOLVE,
NORMALMENTE, UM BUFFER COM A CADEIA DE ENTRADA E UMA PILHA,
ONDE SÃO ARMAZENADOS OS SÍMBOLOS EM PROCESSAMENTO.
ANALISANDO AS OPÇÕES, DIGA QUAL A SITUAÇÃO QUE INDICA QUE
OCORREU UM ERRO NO PROCESSAMENTO DA CADEIA.
A)
A)
B)
B)
C)
C)
D)
D)
E)
E)
GABARITO
1. Durante a preparação para a criação da tabela sintática de um analisador descendente
preditivo, temos que definir os conjuntos Follow e First que mostram, respectivamente, os
terminais que podem seguir um determinado símbolo e os terminais que aparecem mais à
direita em uma forma sentencial.
No processamento de uma determinada gramática, foram estabelecidos os conjuntos Follow
mostrados na tabela abaixo:
Não Terminal Follow
S {$}
A {a, Ɛ}
B {a}
� Atenção! Para visualizaçãocompleta da tabela utilize a rolagem horizontal
Como base nestes conjuntos, podemos afirmar que:
I. Houve um erro no processamento.
porque
II. No conjunto Follow não pode aparecer $.
Quanto às afirmativas acima, podemos afirmar que:
A alternativa "C " está correta.
O símbolo de final de entrada $ sempre irá aparecer no conjunto Follow, portanto a segunda
afirmativa está errada. A primeira afirmativa está correta porque a produção vazia Ɛ nunca
pode aparecer no conjunto Follow.
2. A implementação de um analisador sintático envolve, normalmente, um buffer com a cadeia
de entrada e uma pilha, onde são armazenados os símbolos em processamento. Analisando
as opções, diga qual a situação que indica que ocorreu um erro no processamento da cadeia.
A alternativa "A " está correta.
A opção A está correta, pois, se ao atingirmos o final da pilha ainda existem símbolos
diferentes de $ na entrada, fica caracterizado que a sentença não pertence à gramática. As
opções B e C mostram uma situação intermediária da análise ou ainda temos símbolos tanto
na pilha como na entrada. A opção D mostra a situação de aceitação da entrada, pois, tanto a
pilha como a entrada estão vazias, e está errada, já que identificadores aceitam letras que
sejam maiúsculas ou minúsculas da forma que a especificação foi realizada. A opção E mostra
uma situação errada, porque ainda há dados a serem analisados e a pilha está vazia.
CONCLUSÃO
CONSIDERAÇÕES FINAIS
Ao longo deste tema, fizemos uma viagem pelos conceitos relacionados à Análise Sintática.
Iniciamos estudando o que é o analisador sintático, o que é uma árvore de sintaxe e como
construí-la e o tratamento de erro.
No módulo 2, tratamos de Gramáticas Livres de Contexto e Ambíguas.
A seguir, tratamos dos tipos de algoritmos, ascendentes ou descendentes, que podem ser
utilizados pelos parser e suas principais características.
Finalmente, no módulo 4, estudamos especificamente a construção de analisadores sintáticos,
suas funções básicas, o uso da pilha e, no GALS, vimos como configurar a sua criação
automática.
AVALIAÇÃO DO TEMA:
REFERÊNCIAS
AHO, A. V. et al. Compiladores: Princípios, técnicas e ferramentas. 2. ed. São Paulo: Pearson,
2008.
COOPER, K. D.; TORCZON, L. Construindo Compiladores. 2. ed. Rio de Janeiro: Elsevier, 2014.
LOUDEN, K. C. Compiladores: Princípios e práticas. São Paulo: Cengage Learning, 2004.
RIPLEY, G.; DRUSEIKIS, F. A Statistical Analysis of Syntax Errors. In: J. Computer Languages, v.
3, Issue 4, USA, 1978. pp. 227-240.
SANTOS, P. R.; LANGLOIS, T. Compiladores: Da teoria à prática. Rio de Janeiro: LTC, 2018.
TANENBAUM, A. S. Organização Estruturada de Computadores. 5. ed. São Paulo: Pearson,
2006.
EXPLORE+
Para saber mais sobre os assuntos tratados neste tema, leia:
SConceitos de linguagens de programação, Robert Sebesta, 11ª edição, 2018.
CONTEUDISTA
Sidney Nicolau Venturi Filho
 CURRÍCULO LATTES
javascript:void(0);