Análise Sin parsi

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.
Atividade Prática
O que são  “regras”?
Observe a lista abaixo:
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | num
é uma gramática que descreve expressões matemáticas simples (com +, *, parênteses e números).
A seta → significa “pode ser substituído por”.
A barra | significa “ou” (escolha de alternativa).
O ε significa vazio, ou seja, não tem nada (pode parar por aí).
Explicando cada regra
E → T E'
Uma Expressão (E) é formada por um Termo (T) seguido possivelmente de mais coisas (E').
E' → + T E' | ε
A parte E' representa repetições de + T.
Ou seja: depois de um termo, posso ter + outro termo, e assim por diante.
Se não houver mais +, usamos ε (vazio) e paramos.
T → F T'
Um Termo (T) é formado por um Fator (F) seguido possivelmente de multiplicações (T').
T' → * F T' | ε
Isso significa: depois de um fator, posso ter × outro fator, e assim por diante.
Se não houver mais *, paramos.
F → ( E ) | num
Um Fator (F) pode ser:
Um número (num), ou
Uma expressão entre parênteses ((E)).
Exemplo prático: analisar num + ( num * num )
Começo com E (expressão). 
E
Pela regra E → T E': 
T E'
Pela regra T → F T': 
F T' E'
Pela regra F → num (porque o primeiro símbolo da entrada é num): 
num T' E'
Como depois de num vem + e não *, usamos T' → ε: 
num E'
Agora E' pode ser + T E', porque vem um +: 
num + T E'
Para esse T, a entrada começa com (, então em F → ( E ): 
num + ( E ) T' E'
Dentro dos parênteses (E): 
num + ( T E' ) T' E'
Esse T vira F T', e F → num: 
num + ( num T' E' ) T' E'
Como depois vem *, usamos T' → * F T':
num + ( num * F T' E' ) T' E'
O F seguinte também vira num:
num + ( num * num T' E' ) T' E'
Não há mais * nem + dentro, então os T' e E' viram ε:
num + ( num * num ) 
Cheguei exatamente na entrada. 
Árvore da expressão
               E
            /     \
           T       E'
          |      +  T
          F         |
          |         F
         num       (E)
                     |
                     T E'
                     |
                     F T'
                     |   \
                    num   * F
                           |
                          num
Ou seja:
num + ( num * num ) é válido,
O parser usa as regras da gramática como um “manual de montagem” da árvore.
Árvore de derivação (com não-terminais)
E
├── T
│   ├── F
│   │   └── num
│   └── T' (ε)
└── E'
    ├── +
    ├── T
    │   ├── F
    │   │   ├── "("
    │   │   ├── E
    │   │   │   ├── T
    │   │   │   │   ├── F
    │   │   │   │   │   └── num
    │   │   │   │   └── T'
    │   │   │   │       ├── *
    │   │   │   │       ├── F
    │   │   │   │       │   └── num
    │   │   │   │       └── T' (ε)
    │   │   │   └── E' (ε)
    │   │   └── ")"
    │   └── T' (ε)
    └── E' (ε)
Árvore de expressão (AST)
        (+)
       /   \
     num    (*)
           /   \
         num   num
Mesma Gramática acima
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | num
Tokens de entrada
num + ( num * num ) $  ($ = fim da entrada)
Regras de decisão (LL(1), por lookahead):
Em F: num → F→num; ( → F→(E).
Em T': * → T'→* F T'; + ou ) ou $ → T'→ε.
Em E': + → E'→+ T E'; ) ou $ → E'→ε.
Traço passo a passo (funções chamadas, lookahead, ação)
Conclusão: a cadeia num + ( num * num ) é aceita. Observe como:
E' implementa “repetições de + T” (soma iterativa).
T' implementa “repetições de * F” (multiplicação iterativa).
F decide entre número ou parênteses, permitindo precedência correta: o * é resolvido dentro dos parênteses antes do +.
A mesma história vista como derivação (mais à esquerda)
E
T E'
F T' E'
num T' E'
num E'
num + T E'
num + F T' E'
num + ( E ) T' E'
num + ( T E' ) T' E'
num + ( F T' E' ) T' E'
num + ( num T' E' ) T' E'
num + ( num * F T' E' ) T' E'
num + ( num * num T' E' ) T' E'
num + ( num * num E' ) T' E'
num + ( num * num ) T' E'
num + ( num * num ) E'
num + ( num * num )
Agora vejamos o passo a passo do parsing descendente (LL(1)) para a entrada:
Entrada: num * num + num $ ($ = fim) Gramática:
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | num
Regras de decisão (por lookahead)
Em F: num → F→num; ( → F→(E).
Em T': * → T'→* F T'; + ) $ → T'→ε.
Em E': + → E'→+ T E'; ) $ → E'→ε.
Traço passo a passo (função, lookahead, ação)
Observações de precedência:
Note que, ao ver * após o primeiro num, o parser escolhe T'→* F T' antes de permitir qualquer + em E'. Assim, ele fecha a multiplicação primeiro e só depois processa a soma — exatamente a precedência desejada: 
(num * num) + num
Derivação (mais à esquerda) correspondente
E
T E'
F T' E'
num T' E'
num * F T' E'
num * num T' E'
num * num E'
num * num + T E'
num * num + F T' E'
num * num + num T' E'
num * num + num E'
num * num + num
A seguir temos a árvore para a entrada num * num + num, usando a mesma gramática LL:
1) Árvore de derivação (com os não-terminais)
E
├── T
│   ├── F
│   │   └── num
│   └── T'
│       ├── *
│       ├── F
│       │   └── num
│       └── T' (ε)
└── E'
    ├── +
    ├── T
    │   ├── F
    │   │   └── num
    │   └── T' (ε)
    └── E' (ε)
2) Árvore de expressão (operadores e operandos)
          (+)
         /   \
       (*)    num
      /   \
    num   num
Exercícios
Exercícios Resolvidos
Exercício 1 – Soma simples
Entrada: num + num $
Gramática (mesma base):
E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → ( E ) | num
Derivação passo a passo
E
T E'
F T' E'
num T' E'
num E' (T' → ε)
num + T E' (E' → + T E')
num + F T' E'
num + num T' E'
num + num E' (T' → ε)
num + num (E' → ε) ✅
Árvore de derivação
E
├── T → F → num
└── E'
    ├── +
    ├── T → F → num
    └── E' → ε
AST
   (+)
  /   \
num   num
Exercício 2 – Multiplicação simples
Entrada: num * num $
Derivação passo a passo
E
T E'
F T' E'
num T' E'
num * F T' E'
num * num T' E'
num * num E' (T' → ε)
num * num (E' → ε) ✅
Árvore de derivação
E
├── T
│   ├── F → num
│   └── T'
│       ├── *
│       └── F → num
└── E' → ε
AST
   (*)
  /   \
num   num
Exercício 3 – Precedência com soma e multiplicação
Entrada: num + num * num $
Derivação resumida
O parser primeiro constrói num como T.
Em E', encontra + → entra em + T E'.
O novo T encontra num * num, então escolhe T' → * F T'.
Fecha corretamente: (num * num) dentro do lado direito do +.
AST
   (+)
  /   \
num   (*)
      / \
    num num
Exercício 4 – Expressão com parênteses
Entrada: ( num + num ) * num $
Derivação resumida
F → (E).
Dentro dos parênteses: num + num.
Depois, fora dos parênteses: multiplicação com outro num.
AST
   (*)
  /   \
 (+)   num
 / \
num num
Exercícios para praticar (com dicas)
Agora alguns desafios para os alunos praticarem sozinhos.
Exercício 5
Entrada: num * num * num $
Derive passo a passo e construa a árvore.
Dica: a gramática permite repetições em T'.
Resultado esperado: AST com três num encadeados por *.
Exercício 6
Entrada: ( num * num ) + num $
Mostre a ordem de precedência.
Dica: parênteses têm prioridade, então multiplica antes da soma.
Resultado esperado: AST com + na raiz, (*) no lado esquerdo.
Exercício 7
Entrada: num + num + num $
Aqui temos duas somas seguidas.
Dica: veja como E' se repete para cada +.
Resultado esperado: AST com + encadeados (associatividade à esquerda).
Exercício 8 (modificação de regra)
Modifique a gramática para aceitar também subtração -. Sugestão: alterar apenas E':
E' → (+|-) T E' | ε
Teste a entrada: num - num + num. Construa a árvore de derivação e a AST.
Exercício 9 (avanço)
Inclua divisão / na gramática, modificando T':
T' → (*|/) F T' | ε
Teste com: num / num * num.
Analise a precedência (divisão e multiplicação têm o mesmo nível).
Mostre a AST resultante.
Estrutura da Gramática em Python (Flyparse)
Primeiro, podemos definir a gramática em Python (com lark ou uma função manual). Vou usar lark porque é leve e próxima da ideia de "fly parsing":
from lark import Lark, Tree, Token

# Gramática LL para expressões simples
grammar = r"""
    ?start: expr

    ?expr: term expr_rest
    ?expr_rest: "+" term expr_rest
              | "-" term expr_rest
              |                   -> empty

    ?term: factor term_rest
    ?term_rest: "*" factor term_rest
              | "/" factor term_rest
              |                   -> empty

    ?factor: NUMBER
           | "(" expr ")"

    NUMBER: /[0-9]+/

    %ignore " "
"""

parser = Lark(grammar, start="start")
Exercícios com Flyparse (Python)
Exercício 1 – Validar expressões
entrada = "2 + 3 * 4"
tree = parser.parse(entrada)
print(tree.pretty())
🔎 Tarefa para o aluno:
Rode com "5 * 6 + 7" e compare a árvore.
Verifique a precedência: multiplicação dentro da soma.
Exercício 2 – Trabalhar com parênteses
entrada = "(2 + 3) * 4"
tree = parser.parse(entrada)
print(tree.pretty())
Questões:
Como os parênteses mudam a ordem da árvore?
Compare a AST dessa expressão com a do Exercício 1.
Exercício 3 – Testar entradas inválidas
try:
    entrada = "2 + * 3"
    tree = parser.parse(entrada)
    print(tree.pretty())
except Exception as e:
    print("Erro de parsing:", e)
Desafio:
Teste "* 2 + 3", "2 +" e veja o erro.
Pergunta: por que a gramática rejeita?
Exercício 4 – Adicionar subtração
A gramática já inclui - em expr_rest. Teste:
entrada = "10 - 3 + 2"
tree = parser.parse(entrada)
print(tree.pretty())
🔎 Questão:
A subtração funciona como a soma (associatividade à esquerda)?
Tente "10 - 3 - 2" e interprete.
Exercício 5 – Adicionar divisão
A gramática já suporta /. Teste:
entrada = "12 / 3 * 2"
tree = parser.parse(entrada)
print(tree.pretty())
Questão:
Multiplicação e divisão têm a mesma precedência?
Compare com "12 / (3 * 2)".
Exercício 6 – Criar uma calculadora simples
Com Transformer do Lark:
from lark import Transformer

class EvalExpr(Transformer):
    def NUMBER(self, token):
        return int(token)
    def expr(self, items):
        val = items[0]
        for op, nxt in zip(items[1::2], items[2::2]):
            if op == '+': val += nxt
            if op == '-': val -= nxt
        return val
    def expr_rest(self, items):
        return items
    def term(self, items):
        val = items[0]
        for op, nxt in zip(items[1::2], items[2::2]):
            if op == '*': val *= nxt
            if op == '/': val //= nxt
        return val
    def term_rest(self, items):
        return items

entrada = "2 + 3 * (4 - 1)"
tree = parser.parse(entrada)
calc = EvalExpr().transform(tree)
print("Resultado:", calc)
Desafio:
Altere para retornar float em vez de int.
Inclua divisão real (/) em vez de inteira (//).
Teste "10 / 4".
Sugestões de Exercícios com Fly Python
Identifique a árvore de derivação para "7 * (2 + 5)".
Explique o erro ao tentar "2 ++ 3".
Adicione potência (^) na gramática com maior precedência que * e /.
Transforme a AST em código Python (ex.: entrada "2 + 3 * 4" vira 2 + (3 * 4)).
Implemente avaliação interativa: o aluno digita expressões e o programa retorna o resultado ou erro de parsing.
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":
S ⇒ AB (expandimos S)
AB ⇒ aB (expandimos A para 'a')
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α | β:
Substituir por: A → β A'
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:
Calcular os conjuntos FIRST para todos os símbolos e sequências de símbolos da gramática
Calcular os conjuntos FOLLOW para todos os não-terminais
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
Se X é terminal, FIRST(X) = {X}
Se X → ε é produção, adicione ε a FIRST(X)
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
Adicione $ a FOLLOW(S), onde S é o símbolo inicial
Se A → αBβ é produção, adicione FIRST(β) - {ε} a FOLLOW(B)
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 → α:
Para cada terminal a em FIRST(α), colocamos A → α na entrada [A, a] da tabela
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
Tokenização: [3, '+', 4, '*', 5]
expr(): chama term()
term(): chama factor() → reconhece 3
term_prime(): não encontra * ou /, retorna
expr_prime(): encontra +, consome
expr_prime(): chama term()
term(): chama factor() → reconhece 4
term_prime(): encontra *, consome
term_prime(): chama factor() → reconhece 5
term_prime(): não encontra * ou /, retorna
expr_prime(): não encontra + ou -, retorna
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.