Gramáticas e linguagens

Quando um DFA não basta: precisamos de memória

A linguagem aⁿbⁿ — strings com o mesmo número de 'a' e 'b' — não pode ser reconhecida por um DFA porque exige contar. Um DFA tem memória fixa (o estado atual), então não consegue representar "vi n 'a's e agora preciso ver exatamente n 'b's" para n arbitrário.

A solução é adicionar uma pilha: empilhamos um símbolo para cada 'a' e desempilhamos um para cada 'b'. Se a pilha esvaziar exatamente quando a entrada terminar, aceitamos. Esse modelo é o autômato com pilha (PDA), e ele reconhece exatamente as linguagens livres de contexto (CFL).

PDA para aⁿbⁿ

Escolha o valor de n. O PDA empilha A para cada 'a' e desempilha para cada 'b'. A pilha deve ter apenas Z₀ ao final para aceitar.

Gramáticas livres de contexto (CFG)

# Gramática livre de contexto (CFG) para aⁿbⁿ
# Notação BNF

S → a S b   # regra recursiva: envolve S com a e b
S → ε       # caso base: string vazia

# Derivações:
S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaabbb    # n=3
S ⇒ ε                                    # n=0

# Gramática para expressões aritméticas simples:
E → E + T | T
T → T * F | F
F → ( E ) | num

# Derivação de "3 * (2 + 1)":
E ⇒ T ⇒ T*F ⇒ F*F ⇒ num*F ⇒ num*(E) ⇒ num*(T+T) ⇒ ...

# Árvore de derivação (parse tree) — estrutura do parser
#          E
#          |
#          T
#        / | \
#       T  *  F
#       |   / | \
#       F  ( E   )
#       |    |
#      num  E+T → ...

Autômato com pilha (PDA) em Python

# Autômato com pilha (PDA) para aⁿbⁿ em Python
# Simulação manual — usa uma pilha explícita

def aceita_anbn(string):
    pilha = ["Z"]   # Z = marcador de fundo
    estado = "q0"

    for ch in string:
        if estado == "q0":
            if ch == "a":
                pilha.append("A")      # empilha A para cada 'a'
            elif ch == "b":
                if pilha[-1] != "A":
                    return False    # mais 'b' que 'a'
                pilha.pop()
                estado = "q1"
            else:
                return False
        elif estado == "q1":
            if ch == "b":
                if pilha[-1] != "A":
                    return False
                pilha.pop()
            else:
                return False

    return pilha == ["Z"]  # stack vazia (exceto Z) → aceita

aceita_anbn("aabb")    # True
aceita_anbn("aaabbb")  # True
aceita_anbn("aab")     # False
aceita_anbn("ab")      # True

Construindo um parser

Mini projeto: escreva um parser recursivo descendente para expressões aritméticas com +, * e parênteses (sem variáveis). Use a gramática: E → T ('+' T)*, T → F ('*' F)*, F → num | '(' E ')'. Retorne o valor calculado diretamente.

Projeto principal: estenda o parser para construir uma árvore de sintaxe abstrata (AST) em vez de avaliar diretamente. Implemente: parser → AST → visitor de avaliação. Adicione suporte a variáveis (x = 3 + 2) usando um dicionário de ambiente. Gere a representação textual da AST (pretty-print com indentação).

Desafio extra: implemente um parser LR(1) a partir de uma gramática arbitrária. Construa as tabelas ACTION e GOTO automaticamente. Teste com gramáticas ambíguas (como expressões sem precedência definida) e observe os conflitos shift/reduce. Compare a velocidade com o parser recursivo descendente para arquivos grandes.

Teste sua intuição

Onde você encontra isso