INÍCIO
Livros do Prof.
Análise Sintática: Parsing Descendente
Um guia completo sobre parsing descendente, com foco em LL(1) e implementação manual de parsers recursivos para estudantes de compiladores.
Revisão: Análise Sintática e Gramáticas Livres de Contexto
A análise sintática é a segunda fase da compilação, responsável por verificar se a sequência de tokens gerada pelo analisador léxico está estruturalmente correta conforme as regras da linguagem.
As Gramáticas Livres de Contexto (GLCs) são o formalismo matemático utilizado para descrever a sintaxe de linguagens de programação, compostas por:
  • Conjunto de símbolos não-terminais (N)
  • Conjunto de símbolos terminais (Σ)
  • Conjunto de produções (P)
  • Símbolo inicial (S)
A análise sintática usa a GLC para construir uma árvore sintática que representa a estrutura hierárquica do programa, validando sua conformidade com a gramática da linguagem.
O que é Parsing Descendente?
Definição
É uma estratégia de análise sintática que constrói a árvore a partir do símbolo inicial (raiz) em direção aos símbolos terminais (folhas), seguindo uma abordagem top-down.
Objetivo
Reconhecer se uma sequência de tokens pertence à linguagem definida pela gramática, construindo uma representação estrutural (árvore sintática) do programa.
Técnicas
Existem várias técnicas de parsing descendente, como LL(1), LL(k), Recursive Descent e Predictive Parsing, cada uma com características específicas de implementação.
Estratégia Top-Down: Do Símbolo Inicial até os Terminais
O parsing descendente aplica produções gramaticais começando pelo símbolo inicial, expandindo não-terminais até chegar aos terminais que compõem a entrada. A cada passo, o parser tenta encontrar uma derivação à esquerda que corresponda à sequência de tokens.
Esta abordagem segue o processo mental natural de compreensão da estrutura de um programa, facilitando tanto o entendimento quanto a implementação manual do parser. O algoritmo constantemente compara os terminais produzidos com os tokens da entrada para validar as decisões de parsing.
Motivação: Parsing Manual e Controle do Fluxo
Por que implementar manualmente?
  • Maior controle sobre o processo de análise
  • Flexibilidade na recuperação de erros
  • Geração personalizada de mensagens de erro
  • Melhor integração com a semântica da linguagem
  • Possibilidade de otimizações específicas
O parsing manual permite uma compreensão profunda do funcionamento interno dos compiladores, uma habilidade valiosa mesmo quando se utiliza geradores de parsers em projetos reais.
Simulação do Parser com Derivação à Esquerda
Na derivação à esquerda, sempre expandimos o não-terminal mais à esquerda na forma sentencial. Este processo simula exatamente o comportamento de um parser descendente, que tenta construir a árvore da esquerda para a direita.
Considere a gramática: S → AB, A → a, B → b
Derivação à esquerda para reconhecer "ab":
  1. S ⇒ AB (expandimos S)
  1. AB ⇒ aB (expandimos A para 'a')
  1. aB ⇒ ab (expandimos B para 'b')
Problema da Recursão à Esquerda
Recursão à Esquerda
Uma gramática possui recursão à esquerda quando existe uma regra do tipo A → Aα.
Exemplo: E → E + T | T
Problema
Um parser descendente recursivo entraria em loop infinito ao tentar expandir E, pois chamaria repetidamente a mesma função sem consumir tokens.
Solução
Transformar a gramática eliminando a recursão à esquerda:
E → T E'
E' → + T E' | ε
Transformação para Forma Apropriada ao LL(1)
Regras de Transformação
Para eliminar a recursão à esquerda direta em A → Aα | β:
  1. Substituir por: A → β A'
  1. Adicionar: A' → α A' | ε
Onde ε representa a cadeia vazia e A' é um novo não-terminal.
Exemplo Prático
Gramática original com recursão à esquerda:
E → E + T | T
Após a transformação:
E → T E'
E' → + T E' | ε
Esta transformação preserva a linguagem gerada pela gramática original, mas elimina a recursão à esquerda, tornando-a adequada para parsing descendente.
Noções de Lookahead e Predição
O lookahead refere-se à capacidade do parser de observar um ou mais tokens à frente na entrada sem consumi-los, auxiliando na tomada de decisões durante o processo de análise.
Em um parser LL(1), utilizamos apenas um token de lookahead para decidir qual produção aplicar. A predição consiste em escolher corretamente qual regra gramatical deve ser aplicada com base no próximo token da entrada.
Esta capacidade de "olhar adiante" é fundamental para parsers determinísticos, permitindo resolver ambiguidades e escolher o caminho correto da derivação.
Parsing Descendente vs. Ascendente
Parsing Descendente (Top-Down)
  • Constrói a árvore da raiz para as folhas
  • Inicia pelo símbolo inicial
  • Mais intuitivo e fácil de implementar manualmente
  • Exemplos: LL(1), Recursive Descent
Parsing Ascendente (Bottom-Up)
  • Constrói a árvore das folhas para a raiz
  • Inicia pelos tokens de entrada
  • Mais poderoso, reconhece mais classes de gramáticas
  • Exemplos: LR(0), SLR, LALR, LR(1)
Definição de LL(1)
Left-to-right, Leftmost derivation, 1 lookahead
Um parser LL(1) processa a entrada da esquerda para a direita, construindo a derivação mais à esquerda, utilizando 1 token de lookahead para tomar decisões.
As três letras do nome LL(1) indicam:
  • L: Leitura da entrada da esquerda para a direita
  • L: Construção da derivação mais à esquerda
  • (1): Utilização de apenas um token de lookahead
Esta técnica é amplamente utilizada por sua simplicidade de implementação e eficiência para muitas linguagens de programação.
Gramáticas LL(1) - Características
Sem Ambiguidade
Uma gramática LL(1) não pode ser ambígua, ou seja, não pode existir mais de uma árvore sintática para a mesma sequência de entrada.
Sem Recursão à Esquerda
Não pode conter regras com recursão à esquerda direta ou indireta, pois isso causaria loop infinito no parser.
Sem Fatoração à Esquerda
Se A → αβ | αγ, não é possível decidir qual produção escolher apenas olhando o próximo token. É necessário fatorar: A → αA', A' → β | γ.
Conjuntos FIRST Disjuntos
Para cada não-terminal A com múltiplas produções A → α | β, os conjuntos FIRST(α) e FIRST(β) devem ser disjuntos.
Construção de Tabelas LL(1): Passo a Passo
A tabela de parsing LL(1) é uma matriz bidimensional que mapeia pares (não-terminal, terminal) para produções gramaticais. O processo de construção envolve:
  1. Calcular os conjuntos FIRST para todos os símbolos e sequências de símbolos da gramática
  1. Calcular os conjuntos FOLLOW para todos os não-terminais
  1. Para cada produção A → α na gramática:
  • Para cada terminal a em FIRST(α), adicionar A → α à tabela na posição [A, a]
  • Se ε está em FIRST(α), para cada terminal b em FOLLOW(A), adicionar A → α à tabela na posição [A, b]
Cálculo de FIRST Sets
Definição
FIRST(α) é o conjunto de terminais que podem aparecer como primeiro símbolo de uma cadeia derivada de α. Se α pode derivar ε, então ε também está em FIRST(α).
Regras de Cálculo
  1. Se X é terminal, FIRST(X) = {X}
  1. Se X → ε é produção, adicione ε a FIRST(X)
  1. Se X → Y1Y2...Yk é produção:
  • Adicione FIRST(Y1) - {ε} a FIRST(X)
  • Se Y1 pode derivar ε, adicione FIRST(Y2) - {ε}, e assim por diante
Exemplo
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id
Calculando FIRST:
  • FIRST(F) = {(, id}
  • FIRST(T') = {*, ε}
  • FIRST(T) = FIRST(F) = {(, id}
  • FIRST(E') = {+, ε}
  • FIRST(E) = FIRST(T) = {(, id}
Cálculo de FOLLOW Sets
Definição
FOLLOW(A) é o conjunto de terminais que podem aparecer imediatamente após o não-terminal A em alguma forma sentencial derivável do símbolo inicial.
Regras de Cálculo
  1. Adicione $ a FOLLOW(S), onde S é o símbolo inicial
  1. Se A → αBβ é produção, adicione FIRST(β) - {ε} a FOLLOW(B)
  1. Se A → αB é produção, ou A → αBβ é produção e β pode derivar ε, adicione FOLLOW(A) a FOLLOW(B)
Exemplo (continuação)
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | id
Calculando FOLLOW:
  • FOLLOW(E) = {$, )}
  • FOLLOW(E') = FOLLOW(E) = {$, )}
  • FOLLOW(T) = {+, $, )}
  • FOLLOW(T') = FOLLOW(T) = {+, $, )}
  • FOLLOW(F) = {*, +, $, )}
Montagem da Tabela Preditiva LL(1)
Para construir a tabela preditiva LL(1), aplicamos duas regras para cada produção A → α:
  1. Para cada terminal a em FIRST(α), colocamos A → α na entrada [A, a] da tabela
  1. Se ε está em FIRST(α), para cada terminal b em FOLLOW(A), colocamos A → α na entrada [A, b]
Uma gramática é LL(1) se e somente se cada entrada da tabela contém no máximo uma produção. Se alguma entrada contiver múltiplas produções, temos um conflito e a gramática não é LL(1).
Esta tabela será utilizada pelo parser para decidir qual produção aplicar com base no não-terminal atual e no próximo token de entrada.
Estrutura Básica do Parser Recursivo
Componentes Principais
  • Analisador Léxico: fornece tokens
  • Funções de parsing: uma para cada não-terminal
  • Gerenciamento de lookahead: armazena o token atual
  • Tratamento de erros: detecta e reporta erros sintáticos
A estrutura segue o formato da gramática, com cada não-terminal implementado como uma função que verifica e consome tokens conforme as regras gramaticais.
class Parser:
 def __init__(self, tokens):
 self.tokens = tokens
 self.pos = 0
 self.lookahead = tokens[0]
 
 def match(self, expected):
 if self.lookahead == expected:
 self.pos += 1
 if self.pos < len(self.tokens):
 self.lookahead = self.tokens[self.pos]
 else:
 self.error(f"Esperado {expected}")
 
 def error(self, message):
 raise Exception(message)
 
 def parse(self):
 self.expr()
 if self.pos < len(self.tokens):
 self.error("Tokens extras após fim da expressão")
Funções Recursivas para Regras da Gramática
Cada não-terminal da gramática é implementado como uma função recursiva. A estrutura dessas funções segue diretamente a estrutura das produções gramaticais:
# Para a gramática:
# E → T E'
# E' → + T E' | ε
# T → F T'
# T' → * F T' | ε
# F → ( E ) | id

def expr(self):
 self.term()
 self.expr_prime()
 
def expr_prime(self):
 if self.lookahead == '+':
 self.match('+')
 self.term()
 self.expr_prime()
 # ε caso (não precisa fazer nada)
 
def term(self):
 self.factor()
 self.term_prime()
 
def term_prime(self):
 if self.lookahead == '*':
 self.match('*')
 self.factor()
 self.term_prime()
 # ε caso
 
def factor(self):
 if self.lookahead == '(':
 self.match('(')
 self.expr()
 self.match(')')
 elif self.lookahead == 'id':
 self.match('id')
 else:
 self.error("Esperado '(' ou 'id'")
Exemplo Prático: Implementação da Função expr()
Gramática
expr → term { ('+' | '-') term }
term → factor { ('*' | '/') factor }
factor → number | '(' expr ')'
A gramática acima define expressões aritméticas com operadores +, -, *, / e parênteses, respeitando a precedência usual de operadores.
Implementação da função expr()
def expr(self):
 # Primeiro reconhece um term
 self.term()
 
 # Depois processa sequência de + ou - seguidos de term
 while self.lookahead in ('+', '-'):
 operator = self.lookahead
 self.match(operator)
 self.term()
 
 # Aqui poderia adicionar código para 
 # construir a árvore ou avaliar a expressão
Controle do Lookahead e Função match()
Lookahead
O lookahead é o próximo token a ser processado. É mantido como uma variável de estado do parser e atualizado a cada token consumido.
self.lookahead = self.tokens[self.pos]
Função match()
A função match() é responsável por verificar se o token atual corresponde ao esperado e avançar para o próximo token.
def match(self, expected):
 if self.lookahead == expected:
 self.pos += 1
 if self.pos < len(self.tokens):
 self.lookahead = self.tokens[self.pos]
 else:
 self.lookahead = '$' # Fim da entrada
 else:
 self.error(f"Esperado {expected}, encontrado {self.lookahead}")
Analisador Léxico Simplificado para Teste
Para testar o parser recursivo, precisamos de um analisador léxico que converta a entrada em uma sequência de tokens. Para expressões aritméticas simples, podemos implementar um tokenizador básico:
def tokenize(text):
    tokens = []
    i = 0
    while i < len(text):
        # Ignora espaços em branco
        if text[i].isspace():
            i += 1
            continue
            
        # Operadores e parênteses
        if text[i] in "+-*/()":
            tokens.append(text[i])
            i += 1
            continue
    
        # Números
        if text[i].isdigit():
            start = i
            while i < len(text) and text[i].isdigit():
                i += 1
            tokens.append(int(text[start:i]))
            continue
            
        # Caractere desconhecido
        raise Exception(f"Caractere inválido: {text[i]}")
        
    return tokens
Este tokenizador simples reconhece operadores, parênteses e números inteiros, ignorando espaços em branco. Tokens numéricos são convertidos para inteiros, enquanto operadores e parênteses são mantidos como caracteres.
Tratamento de Erro e Mensagens
Um bom parser deve fornecer mensagens de erro claras e informativas. O tratamento de erros em um parser recursivo descendente pode ser implementado de várias formas:
def error(self, message):
    line = self.get_current_line()
    column = self.get_current_column()
    error_message = f"Erro sintático na linha {line}, coluna {column}: {message}"
    
    # Exibir o contexto do erro
    line_content = self.get_line_content(line)
    pointer = ' ' * (column - 1) + '^'
    
    print(error_message)
    print(line_content)
    print(pointer)
    
    raise SyntaxError(error_message)
Além de reportar erros, um parser robusto deve ser capaz de se recuperar de erros para continuar a análise. Técnicas comuns incluem modo pânico, sincronização por tokens de sincronização e correção de erros.
Teste Completo com Input: 3 + 4 * 5
Processamento Passo a Passo
  1. Tokenização: [3, '+', 4, '*', 5]
  1. expr(): chama term()
  1. term(): chama factor() → reconhece 3
  1. term_prime(): não encontra * ou /, retorna
  1. expr_prime(): encontra +, consome
  1. expr_prime(): chama term()
  1. term(): chama factor() → reconhece 4
  1. term_prime(): encontra *, consome
  1. term_prime(): chama factor() → reconhece 5
  1. term_prime(): não encontra * ou /, retorna
  1. expr_prime(): não encontra + ou -, retorna
  1. expr(): retorna com sucesso
A árvore sintática construída respeita a precedência de operadores, com a multiplicação (4 * 5) sendo agrupada antes da adição. O resultado é equivalente a 3 + (4 * 5) = 23, e não (3 + 4) * 5 = 35.
Exibição da Árvore Sintática Construída
Para visualizar a árvore sintática, podemos modificar nosso parser para construí-la durante a análise. Cada nó da árvore representa uma construção sintática, como expressão, termo ou fator.
def expr(self):
    # Primeiro reconhece um term
    left = self.term()
    
    # Depois processa sequência de + ou - seguidos de term
    while self.lookahead in ('+', '-'):
        operator = self.lookahead
        self.match(operator)
        right = self.term()
        
        # Cria um nó para a operação binária
        left = Node('BinOp', operator, [left, right])
        
    return left
A árvore resultante pode ser visualizada em texto usando indentação ou graficamente com bibliotecas como Graphviz, permitindo verificar se a estrutura sintática está correta.
Atividade 1: Parser para expr → term { + term }
Especificação da Gramática
expr → term { '+' term }
term → factor { '*' factor }
factor → number | '(' expr ')'
Implementar um parser recursivo descendente para esta gramática simplificada que suporta apenas adição e multiplicação.
Esqueleto do Código
class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0
        self.lookahead = tokens[0]
    
    def match(self, expected):
        # Implementar
    
    def expr(self):
        # Implementar
    
    def term(self):
        # Implementar
    
    def factor(self):
        # Implementar
Utilize este esqueleto para implementar o parser e teste-o com expressões como "3 + 4 * 5" e "(3 + 4) * 5" para verificar se ele reconhece corretamente a precedência de operadores.
Atividade 2: Adicionar Parênteses e Precedência
Expandir a gramática
Adicione suporte para parênteses e operadores de subtração e divisão, mantendo a precedência correta:
expr → term { ('+' | '-') term }
term → factor { ('*' | '/') factor }
factor → number | '(' expr ')'
Implementar funções do parser
Modifique as funções expr(), term() e factor() para suportar os novos operadores e parênteses:
  • expr() deve reconhecer termos separados por + ou -
  • term() deve reconhecer fatores separados por * ou /
  • factor() deve reconhecer números ou expressões entre parênteses
Testar com expressões complexas
Verifique se o parser reconhece corretamente expressões como:
  • 3 + 4 * 5 - 6 / 2
  • (3 + 4) * (5 - 6 / 2)
  • 3 * (4 + 5) - 6 * 7
Exercício Desafiador: Gramática com if-else
Gramática para if-else
stmt → if_stmt | other_stmt
if_stmt → 'if' '(' expr ')' stmt ['else' stmt]
expr → 'true' | 'false'
other_stmt → 'A' | 'B'
Esta gramática apresenta o problema do "else pendurado", que ocorre quando há ambiguidade sobre a qual if um else está associado em casos de ifs aninhados.
Desafio
Implemente um parser recursivo descendente para esta gramática que resolva o problema do "else pendurado" seguindo a regra: um else sempre se associa ao if mais próximo sem else.
Teste seu parser com a entrada: "if ( true ) if ( false ) A else B"
Revisão dos Erros Comuns
Loops Infinitos
Ocorrem quando a gramática possui recursão à esquerda não tratada. Sempre verifique e elimine recursão à esquerda antes de implementar o parser.
# Problema: recursão à esquerda
expr → expr + term | term

# Solução
expr → term expr'
expr' → + term expr' | ε
Ambiguidade
Uma gramática ambígua pode gerar mais de uma árvore sintática para a mesma entrada. Isso causa indeterminismo no parser LL(1).
# Problema: ambiguidade no if-else
stmt → if expr then stmt | if expr then stmt else stmt

# Solução
stmt → matched_stmt | unmatched_stmt
matched_stmt → if expr then matched_stmt else matched_stmt | other_stmt
unmatched_stmt → if expr then stmt | if expr then matched_stmt else unmatched_stmt
Outros erros comuns incluem falta de tratamento de erros adequado, inconsistências na implementação da função match() e problemas com o gerenciamento do lookahead.
Resumo da Aula
Parsing Descendente
Estratégia top-down que constrói a árvore sintática da raiz para as folhas, seguindo a derivação mais à esquerda.
LL(1)
Técnica de parsing descendente que utiliza 1 token de lookahead e uma tabela preditiva para tomar decisões.
Parser Recursivo
Implementação direta de um parser descendente usando funções recursivas para cada não-terminal da gramática.
Árvore Sintática
Representação estrutural hierárquica do programa que reflete as regras da gramática aplicadas durante o parsing.
Nesta aula, estudamos os fundamentos do parsing descendente, com foco na técnica LL(1) e na implementação manual de parsers recursivos. Aprendemos a transformar gramáticas para eliminar recursão à esquerda, calcular conjuntos FIRST e FOLLOW, e construir tabelas preditivas para guiar o processo de parsing.
Tarefa para Casa
Implemente um parser recursivo descendente completo para expressões aritméticas que suporte:
  • Operadores: +, -, *, /, ^ (exponenciação)
  • Parênteses para agrupar expressões
  • Funções matemáticas: sin, cos, sqrt
  • Números reais (com ponto decimal)
  • Variáveis (identificadores)
O parser deve construir uma árvore sintática completa e incluir tratamento de erros adequado. Bônus: implemente um avaliador que calcule o resultado da expressão dado um conjunto de valores para as variáveis.
Data de entrega: próxima aula.