Parsing Top-Down

Modulo 3 · Aula 2 ~28 min de leitura Nivel: Intermediario

Video da aula estara disponivel em breve

Recursive Descent Parsing

Um parser recursive descent é a implementação mais intuitiva de um parser top-down: cada não-terminal da gramática vira uma função. O parser começa pelo símbolo inicial e expande não-terminais recursivamente, consumindo tokens da esquerda para a direita. Segundo Aho, Sethi e Ullman (Dragon Book, Cap. 4.4), este é o tipo de parser mais utilizado em compiladores escritos à mão.

Definição formal: um parser top-down constrói a árvore de derivação da raiz (símbolo inicial) para as folhas (tokens), produzindo uma derivação leftmost. Em cada passo, o parser escolhe qual produção aplicar para o não-terminal mais à esquerda, baseado no próximo token da entrada (lookahead).

BNF

# Gramática para recursive descent (sem recursão à esquerda):
# Precisamos eliminar recursão à esquerda da gramática original

# Original (com recursão à esquerda — NÃO funciona):
# expr ::= expr '+' term | term

# Transformada (sem recursão à esquerda — funciona):
expr       ::= term expr_rest
expr_rest  ::= '+' term expr_rest
             | '-' term expr_rest
             | /* vazio */

term       ::= factor term_rest
term_rest  ::= '*' factor term_rest
             | '/' factor term_rest
             | /* vazio */

factor     ::= '(' expr ')'
             | NUMBER
             | ID

Eliminação de Recursão à Esquerda

A transformação para eliminar recursão à esquerda é mecânica e se aplica a qualquer gramática. O Dragon Book (Cap. 4.3.3) formaliza a regra:

Diagrama

Regra geral de eliminação de recursão à esquerda direta:

  Original:    A → Aα₁ | Aα₂ | ... | Aαm | β₁ | β₂ | ... | βn
               (onde nenhum βᵢ começa com A)

  Transformada: A  → β₁ A' | β₂ A' | ... | βn A'
                A' → α₁ A' | α₂ A' | ... | αm A' | ε

Exemplo concreto:
  Original:    expr → expr + term | expr - term | term
               (A = expr, α₁ = + term, α₂ = - term, β₁ = term)

  Transformada: expr      → term expr_rest
                expr_rest → + term expr_rest
                          | - term expr_rest
                          | ε

Recursão à esquerda indireta (A → B... , B → A...):
  1. Ordenar os não-terminais: A₁, A₂, ..., An
  2. Para i = 1 até n:
     Para j = 1 até i-1:
       Substituir Aᵢ → Aⱼγ por Aᵢ → δ₁γ | δ₂γ | ...
       (onde Aⱼ → δ₁ | δ₂ | ... são as produções de Aⱼ)
     Eliminar recursão à esquerda direta de Aᵢ

Implementação do Parser Recursive Descent

Python

class Parser:
    """Recursive descent parser para expressões aritméticas."""

    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def peek(self):
        if self.pos >= len(self.tokens):
            return ('EOF', '')
        return self.tokens[self.pos]

    def consume(self, expected_type=None):
        tok = self.peek()
        if expected_type and tok[0] != expected_type:
            raise SyntaxError(
                f"Esperado {expected_type}, encontrado {tok[0]} ('{tok[1]}')"
            )
        self.pos += 1
        return tok

    # expr ::= term (('+' | '-') term)*
    def parse_expr(self):
        left = self.parse_term()
        while self.peek()[0] in ('PLUS', 'MINUS'):
            op = self.consume()
            right = self.parse_term()
            left = ('binop', op[1], left, right)
        return left

    # term ::= factor (('*' | '/') factor)*
    def parse_term(self):
        left = self.parse_factor()
        while self.peek()[0] in ('STAR', 'SLASH'):
            op = self.consume()
            right = self.parse_factor()
            left = ('binop', op[1], left, right)
        return left

    # factor ::= '(' expr ')' | NUMBER | ID
    def parse_factor(self):
        tok = self.peek()
        if tok[0] == 'LPAREN':
            self.consume('LPAREN')
            node = self.parse_expr()
            self.consume('RPAREN')
            return node
        elif tok[0] == 'NUMBER':
            return ('num', self.consume()[1])
        elif tok[0] == 'ID':
            return ('id', self.consume()[1])
        else:
            raise SyntaxError(f"Token inesperado: {tok}")

# Uso com o tokenizer da aula anterior
tokens = [
    ('ID', 'x'), ('PLUS', '+'), ('NUMBER', '2'),
    ('STAR', '*'), ('ID', 'y'),
]
parser = Parser(tokens)
tree = parser.parse_expr()
print(tree)
# ('binop', '+', ('id', 'x'), ('binop', '*', ('num', '2'), ('id', 'y')))

Conjuntos FIRST e FOLLOW

Para construir parsers preditivos (sem backtracking), precisamos saber qual produção escolher baseado no próximo token. Os conjuntos FIRST e FOLLOW resolvem isso formalmente:

Diagrama

FIRST(α) = conjunto de terminais que podem iniciar uma string derivada de α
  Se α ⇒* ε, então ε ∈ FIRST(α)

Regras para calcular FIRST:
  1. Se X é terminal: FIRST(X) = {X}
  2. Se X → ε é produção: ε ∈ FIRST(X)
  3. Se X → Y₁Y₂...Yk:
     Adicione FIRST(Y₁) - {ε} a FIRST(X)
     Se ε ∈ FIRST(Y₁), adicione FIRST(Y₂) - {ε}
     Se ε ∈ FIRST(Y₁) e ε ∈ FIRST(Y₂), adicione FIRST(Y₃) - {ε}
     ... e assim por diante

FOLLOW(A) = conjunto de terminais que podem aparecer imediatamente após A
  $ ∈ FOLLOW(S) (onde S é o símbolo inicial)

Regras para calcular FOLLOW:
  1. $ ∈ FOLLOW(S)
  2. Se A → αBβ: FIRST(β) - {ε} ⊆ FOLLOW(B)
  3. Se A → αB ou A → αBβ onde ε ∈ FIRST(β):
     FOLLOW(A) ⊆ FOLLOW(B)

Exemplo para a gramática de expressões:
FIRST(expr)   = FIRST(term) = FIRST(factor) = { '(', NUMBER, ID }
FIRST('+' term expr_rest) = { '+' }
FIRST('-' term expr_rest) = { '-' }

FOLLOW(expr)     = { ')', $ }
FOLLOW(term)     = { '+', '-', ')', $ }
FOLLOW(factor)   = { '*', '/', '+', '-', ')', $ }

Regra de seleção: para A → α, use esta produção se o próximo
token está em FIRST(α). Se ε ∈ FIRST(α), use também quando
o próximo token está em FOLLOW(A).

Algoritmo para Calcular FIRST/FOLLOW em Python

Python

def compute_first(grammar, nonterminals):
    """Calcula FIRST para todos os não-terminais."""
    first = {nt: set() for nt in nonterminals}
    changed = True

    while changed:
        changed = False
        for head, body in grammar:
            if not body:  # produção vazia (ε)
                if 'ε' not in first[head]:
                    first[head].add('ε')
                    changed = True
                continue

            for symbol in body:
                if symbol not in nonterminals:
                    # Terminal
                    if symbol not in first[head]:
                        first[head].add(symbol)
                        changed = True
                    break
                else:
                    # Não-terminal: adicionar FIRST(symbol) - {ε}
                    new = first[symbol] - {'ε'}
                    if not new.issubset(first[head]):
                        first[head] |= new
                        changed = True
                    if 'ε' not in first[symbol]:
                        break
            else:
                # Todos os símbolos derivam ε
                if 'ε' not in first[head]:
                    first[head].add('ε')
                    changed = True

    return first

# Exemplo
grammar = [
    ('expr', ['term', 'expr_rest']),
    ('expr_rest', ['+', 'term', 'expr_rest']),
    ('expr_rest', []),  # ε
    ('term', ['factor', 'term_rest']),
    ('term_rest', ['*', 'factor', 'term_rest']),
    ('term_rest', []),  # ε
    ('factor', ['NUMBER']),
    ('factor', ['(', 'expr', ')']),
]
nts = {'expr', 'expr_rest', 'term', 'term_rest', 'factor'}
first = compute_first(grammar, nts)
for nt, f in first.items():
    print(f"FIRST({nt}) = {f}")

LL(1) Parsing

Um parser LL(1) lê a entrada da Left to right, produz uma derivação Leftmost, e usa 1 token de lookahead. A tabela de parsing LL(1) usa FIRST e FOLLOW:

Diagrama

Construção da tabela LL(1):

Para cada produção A → α:
  1. Para cada terminal a ∈ FIRST(α), adicione A → α em M[A, a]
  2. Se ε ∈ FIRST(α), para cada terminal b ∈ FOLLOW(A),
     adicione A → α em M[A, b]
  3. Se ε ∈ FIRST(α) e $ ∈ FOLLOW(A),
     adicione A → α em M[A, $]

Se alguma célula M[A, a] tiver mais de uma produção,
a gramática NÃO é LL(1).

Tabela LL(1) para expressões:

              |  NUMBER  |    ID    |    (     |    +     |    -     |    )     |   $
--------------+----------+----------+----------+----------+----------+----------+---------
expr          | term e'  | term e'  | term e'  |          |          |          |
expr_rest(e') |          |          |          | + term e'| - term e'| ε        | ε
term          | fact t'  | fact t'  | fact t'  |          |          |          |
term_rest(t') |          |          |          | ε        | ε        | ε        | ε
              |          |          |          |          |          |          |
factor        | NUMBER   | ID       | ( expr ) |          |          |          |

Cada célula diz qual produção usar dado o não-terminal atual e o próximo token.

Recursão à esquerda mata LL(1) Se a gramática tem recursão à esquerda (A ::= A x), o parser LL(1) entra em loop infinito — a função para A chama a si mesma sem consumir nenhum token. Sempre elimine recursão à esquerda antes de implementar um parser top-down. A transformação é mecânica: A ::= A a | b vira A ::= b A' e A' ::= a A' | epsilon.

Pratt Parsing (Operator Precedence)

Na prática, a técnica mais usada em compiladores escritos à mão é Pratt parsing (operator-precedence parsing), que combina recursive descent com uma tabela de precedência de operadores. Isso evita a necessidade de criar não-terminais auxiliares para cada nível de precedência:

Python

# Pratt parser — precedência por tabela, não por gramática
PRECEDENCE = {
    '+': 10, '-': 10,
    '*': 20, '/': 20,
    '**': 30,  # exponenciação (associativo à direita)
}

RIGHT_ASSOC = {'**'}

class PrattParser:
    """Parser Pratt — uma função para expressões, precedência por tabela."""

    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def peek(self):
        if self.pos >= len(self.tokens):
            return ('EOF', '')
        return self.tokens[self.pos]

    def consume(self):
        tok = self.tokens[self.pos]
        self.pos += 1
        return tok

    def parse_expr(self, min_prec=0):
        """Parse uma expressão com precedência mínima min_prec."""
        left = self.parse_atom()

        while True:
            tok = self.peek()
            if tok[1] not in PRECEDENCE:
                break
            prec = PRECEDENCE[tok[1]]
            if prec < min_prec:
                break

            op = self.consume()
            # Associatividade à direita: mesma precedência
            # Associatividade à esquerda: precedência + 1
            next_prec = prec if op[1] in RIGHT_ASSOC else prec + 1
            right = self.parse_expr(next_prec)
            left = ('binop', op[1], left, right)

        return left

    def parse_atom(self):
        tok = self.peek()
        if tok[0] == 'NUMBER':
            return ('num', self.consume()[1])
        elif tok[0] == 'LPAREN':
            self.consume()
            node = self.parse_expr()
            self.consume()  # RPAREN
            return node
        raise SyntaxError(f"Token inesperado: {tok}")

# 2 ** 3 ** 2 deve ser 2 ** (3 ** 2) = 512, não (2 ** 3) ** 2 = 64

No harness.os

Parsing recursive descent é o padrão para linguagens internas e DSLs. O parser de condições de regras do harness.os é um exemplo direto: cada não-terminal da gramática de condições (condition, term, atom) vira uma função, e a estrutura recursiva permite expressões arbitrariamente complexas.

A conexão com arquitetura de software é direta: o padrão Interpreter (GoF) é essencialmente uma gramática recursive descent onde cada não-terminal é uma classe com um método evaluate(). Validadores de configuração, query builders e filtros complexos usam exatamente esta técnica.

Python

class RuleParser:
    """Parser para condições de regras do harness.os.

    Gramática:
      condition ::= term (('AND' | 'OR') term)*
      term      ::= 'NOT'? atom
      atom      ::= field comparator value
                   | '(' condition ')'
      field     ::= 'context' | 'project' | 'concern' | 'phase'
      comparator ::= '==' | '!=' | 'contains'
      value     ::= STRING

    Exemplo: context == "git-commit" AND concern != "security"
    """

    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def peek(self):
        if self.pos >= len(self.tokens):
            return ('EOF', '')
        return self.tokens[self.pos]

    def consume(self, expected=None):
        tok = self.peek()
        if expected and tok[0] != expected:
            raise SyntaxError(f"Esperado {expected}, achei {tok[0]}")
        self.pos += 1
        return tok

    def parse_condition(self):
        left = self.parse_term()
        while self.peek()[0] in ('AND', 'OR'):
            op = self.consume()
            right = self.parse_term()
            left = ('logic', op[1], left, right)
        return left

    def parse_term(self):
        if self.peek()[0] == 'NOT':
            self.consume()
            return ('not', self.parse_atom())
        return self.parse_atom()

    def parse_atom(self):
        if self.peek()[0] == 'LPAREN':
            self.consume('LPAREN')
            node = self.parse_condition()
            self.consume('RPAREN')
            return node
        field = self.consume('FIELD')
        comp = self.consume('COMP')
        val = self.consume('STRING')
        return ('compare', field[1], comp[1], val[1])

# Testar
tokens = [
    ('FIELD', 'context'), ('COMP', '=='), ('STRING', 'git-commit'),
    ('AND', 'AND'),
    ('FIELD', 'concern'), ('COMP', '!='), ('STRING', 'security'),
]
parser = RuleParser(tokens)
tree = parser.parse_condition()
print(tree)
# ('logic', 'AND',
#   ('compare', 'context', '==', 'git-commit'),
#   ('compare', 'concern', '!=', 'security'))

Homework

FIRST e FOLLOW: Dada a gramática S → aBDh; B → cC; C → bC | ε; D → EF; E → g | ε; F → f | ε, calcule manualmente FIRST e FOLLOW para todos os não-terminais. Verifique seus resultados implementando o algoritmo compute_first em Python.
Parser com recuperação de erros: Estenda o parser recursive descent de expressões para incluir recuperação de erros em modo pânico: quando encontrar um token inesperado, o parser deve pular tokens até encontrar um token de sincronização (como ; ou )) e continuar o parsing, coletando todos os erros em vez de parar no primeiro.
Pratt parser: Implemente um parser Pratt para expressões com: +, -, *, /, ** (exponenciação à direita), unário - e +, parênteses e chamadas de função. Verifique que 2 ** 3 ** 2 produz 2 ** (3 ** 2) e que -2 * 3 produz (-2) * 3.
Tabela LL(1): Construa a tabela LL(1) para a gramática de expressões (após eliminação de recursão à esquerda). Implemente um parser dirigido por tabela que use a tabela LL(1) com uma pilha explícita (sem recursão) e trace cada passo do parsing de (2 + 3) * 4.

Resumo

Recursive descent: cada não-terminal é uma função; o mais intuitivo dos parsers
Recursão à esquerda deve ser eliminada para parsers top-down — a transformação é mecânica
FIRST(α) = terminais que podem iniciar strings derivadas de α
FOLLOW(A) = terminais que podem aparecer imediatamente após A
A tabela LL(1) é construída com FIRST/FOLLOW — cada célula indica a produção a usar
Pratt parsing (operator precedence) é o padrão industrial para parsers escritos à mão
Na prática, recursive descent com Pratt parsing cobre a maioria das necessidades

Verifique seu entendimento

Por que um parser LL(1) não funciona com gramáticas que têm recursão à esquerda?

Porque a tabela LL(1) fica grande demais
Porque o parser entra em loop infinito tentando expandir o não-terminal recursivo sem consumir tokens
Porque recursão à esquerda torna a gramática ambígua
Porque FIRST e FOLLOW não podem ser calculados

Verifique seu entendimento

Para que serve o conjunto FIRST(α) na construção de um parser preditivo?

Determinar qual produção usar baseado no próximo token da entrada
Verificar se a gramática é ambígua
Calcular a precedência dos operadores
Eliminar recursão à esquerda automaticamente

Aula anterior 3.1 Gramaticas Livres de Contexto Proxima aula 3.3 Parsing Bottom-Up