Análise sintática

Funcionamento do analisador sintático, Caracterização das Gramáticas Livres de Contexto e Ambíguas,

Análise dos algoritmos ascendentes e descendentes.
Prof. Sidney Nicolau Venturi Filho
1. Itens iniciais

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
• Descrever o analisador sintático e o tratamento de erros.

• Identificar as características das Gramáticas Livres de Contexto e Ambíguas e suas produções.

• Classificar o funcionamento dos algoritmos ascendentes e descendentes.

• 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.
1. 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.

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

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.

Saiba mais
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.

Imagine o seguinte comando:

plain-text

Se
Então
Senão

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.

A árvore representa o seguinte:

1. Comece com a raiz se é um SE.

2. 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

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:

1. Pegue os operandos 2 e 3.

2. Realize a soma.

3. Pegue como operandos agora o resultado da soma e 7.

4. 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:

plain-text

Se (x > 2)
Então
y = (x - 2) * 7;
Senão
y = x + 2 * 5;

Neste comando, podemos observar o 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.

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 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:

plain-text

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:

 plain-text

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:

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.

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?

Chave de 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:

 plain-text

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:

plain-text

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 siga em 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.

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.

Construindo uma árvore sintática

No vídeo a seguir, você verá a construção de uma árvore sintática e as formas ascendente e descendente.

Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.

Verificando o aprendizado

Questão 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:

Modalidade do desespero

Recuperação de frases

Correção global

Regras de produção para erro

Recuperação sintática

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.

Questão 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

Se X < Z
Entao Y = X * 2 + 7
Senao Y = X * (Z – 5)

Se X <= Z
Entao Y = X * 2 + 7
Senao Y = X * (Z – 5)

Se X <= Z
Entao Y = X * (2 + 7)
Senao Y = X * Z – 5

Se X <= Z
Entao Y = X * (Z - 5)
Senao Y = X * 2 + 7

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.
2. Características e produções das gramáticas livres de contexto e ambíguas

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ã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.

Regras de produção

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 de dí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:

1. A primeira forma é apenas o símbolo inicial da gramática.

2. A última forma é sempre uma sentença.

3. 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 ⟹

1. O símbolo inicial da gramática S.

2. 1 que é uma sentença.

A derivação mostra que a cadeia é uma sentença da linguagem. Vejamos passo a passo:

1. Temos a primeira forma sentencial, que é o símbolo inicial da gramática, no caso S.

2. 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

1. Inicialmente, temos a forma sentencial correspondente ao símbolo inicial S.

2. 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.

3. 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

1. Inicialmente, temos a forma sentencial correspondente ao símbolo inicial S.

2. 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.

3. 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.

4. 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.

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.

• 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

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

Desta forma, a sentença a ser analisada pelo parser seria int + int.

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.

Figura 8 ‒ Árvores geradas.

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

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ção da 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:

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

• 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.

 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

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.

Gramáticas Ambíguas x Gramáticas Livres de Contexto (GLC)

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).

Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.

Verificando o aprendizado
Questão 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:

E ⟹ E E ⟹ E + E ⟹ E + int ⟹ int + int

E ⟹ E E ⟹ E + E ⟹ int + E ⟹ int + intS5

E ⟹ E + E ⟹ int + E ⟹ int + int

E ⟹ E + E ⟹ E + int ⟹ int + int

E ⟹ int E ⟹ int + E ⟹ int + intS5

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

Questão 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:

0S1

0001110

SS0

110S

010
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.

3. 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.

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

Verificando se a cadeia x + y * z pertence à linguagem.

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:

 Passo 1
Criar a árvore com o símbolo inicial na raiz, no caso S:

Passo 2
A partir desta árvore, deriva-se a primeira produção expandindo-se S.

Passo 3
A seguir, expande-se T, o que origina a árvore representada na figura.

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?
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 Deve estar fatorada

O lado direito das produções deve começar Para cada símbolo não terminal, deve existir
com terminais. 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

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 do terceiro 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.
Analisadores descendentes preditivos
Neste vídeo, você encontrará exemplos de analisadores descendentes.

Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.

Verificando o aprendizado

Questão 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

Ela pode ser analisada por estar fatorada.

Ela pode ser analisada por ser LL(1).

Ela não pode ser analisada por não estar fatorada.

Ela pode ser analisada por ter recursão à esquerda.

Ela não pode ser analisada por ter recursão à esquerda.

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.

Questã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:

O analisador é descendente preditivo.

 B

O analisador é descendente com retrocesso.

O analisador é descendente sem retrocesso.

O analisador é ascendente.

O analisador é ascendente com retrocesso.

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.
4. Classificação e uso de analisadores sintáticos

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 Deslocamento

Compreende substituir uma produção (a parte à Corresponde a varrer a entrada colocando o

direita da gramática) pela parte à esquerda. Por token atual na pilha e lendo o próximo. Por
exemplo, na regra E → E + E, se tivermos a exemplo, se tivermos na entrada id + int e for
expressão E + E, iremos substituí-la por E. 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

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 Ler o próximo símbolo e colocá-lo na

$ Deslocar
de $ pilha

Aplicar a regra de redução, retirar o

Corresponde a uma
Indiferente Reduzir símbolo da pilha e substituí-lo pela
produção
redução

Não corresponde a Diferente Ler o próximo símbolo e colocá-lo na

Deslocar
uma produção de $ pilha

$ $ Aceitar A expressão existe na gramática

Símbolo diferente do
$ Erro Realizar tratamento de erro
inicial

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

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 E e 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.

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.

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.

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 ∅

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 ∅

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 ∅

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, ε }
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, ε }

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, ε }

Comecemos analisando S. Como ele é o símbolo inicial da gramática, terá como Follow $:

Não Terminal Follow

 S {$}

A ∅

B ∅

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 ∅

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
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.

Utilizando o GALS
Assista, agora, o emprego do software GALS.

Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.

Verificando o aprendizado
Questão 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}

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:

As duas estão erradas.

As duas estão corretas.

Somente a primeira está correta.

 D

Somente a segunda está correta.

A segunda é uma justificativa da primeira.

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.

Questão 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.

Lorem Ipsum

Lorem Ipsum

Lorem Ipsum

Lorem Ipsum

Lorem Ipsum

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.
5. 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.

Podcast

Para encerra, ouça sobre análise sintática.

Conteúdo interativo
Acesse a versão digital para ouvir o áudio.

Explore+
Para saber mais sobre os assuntos tratados neste tema, leia:

• SConceitos de linguagens de programação, Robert Sebesta, 11ª edição, 2018.

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.