Moacyr Francischetti Corrêa

1 Módulo 08: Projeto do Professor — A Gramática da Peneira

Este é o projeto de referência resolvido pelo professor: a mesma atividade que cada grupo vai executar neste módulo, feita por inteiro, com as decisões justificadas uma a uma. A gramática da sua linguagem será outra, mas o argumento de não ambiguidade precisa ter a mesma forma.

1.1 Visão Geral do Módulo 08

Sete módulos descrevendo palavras. A partir daqui, descrevemos como elas se combinam.

A atividade pede a gramática completa da linguagem, não ambígua, com o argumento de que ela é não ambígua e a justificativa das escolhas de precedência e associatividade — mais as árvores de derivação de pelo menos três programas de exemplo. Nenhum analisador sintático é escrito aqui; ele chega no módulo 10. A gramática é artefato de projeto, e este é o módulo em que ela nasce.

O que vou construir em torno da atividade é uma ferramenta de estudo que muda a natureza da discussão sobre ambiguidade: um enumerador exaustivo de árvores de derivação. Com ele, “esta gramática é ambígua” deixa de ser afirmação a ser acreditada e vira contagem. Duas árvores para a mesma cadeia, exibidas lado a lado, encerram o assunto.

O enumerador não é o analisador sintático do projeto e não vai virar um. Ele é exponencial no pior caso e produz todas as árvores; o do módulo 10 é linear e produz uma. São instrumentos de propósitos opostos, e confundi-los seria erro de projeto.

1.2 Tarefa 1: Escrever a gramática

A atividade — escrever a gramática completa da linguagem em BNF, a partir do design em notação estendida.

O design da Peneira foi anotado em notação estendida, com asterisco para repetição e interrogação para opcional. Uma gramática livre de contexto não tem nenhum dos dois: tem variáveis, terminais, produções e símbolo inicial. A tradução parece mecânica e tem um ponto em que não é.

C++

08_gramatica.h

#ifndef PENEIRA_08_GRAMATICA_H
#define PENEIRA_08_GRAMATICA_H

#include <set>
#include <string>
#include <vector>

namespace peneira {

// Uma produção: a variável do lado esquerdo e a sequência de símbolos do lado
// direito. Corpo vazio representa a produção vazia, que a teoria escreve com
// épsilon.
struct Producao {
    std::string variavel;
    std::vector<std::string> corpo;

    bool ehVazia() const { return corpo.empty(); }
};

// Gramática livre de contexto: variáveis, terminais, produções e símbolo
// inicial.
//
// Não guardo variáveis e terminais em listas separadas. Variável é todo
// símbolo que aparece do lado esquerdo de alguma produção; terminal é todo o
// resto que aparece em algum corpo. Derivar em vez de declarar elimina a
// classe de erro em que um símbolo é declarado variável e nunca recebe
// produção — ele simplesmente vira terminal, e a checagem de símbolos
// improdutivos o encontra.
//
// O nome do formalismo se explica na estrutura: a substituição de uma
// variável depende apenas dela, nunca do que está em volta. Por isso o lado
// esquerdo de toda produção tem exatamente um símbolo.
class Gramatica {
public:
    Gramatica(std::string nome, std::string inicial);

    void adicionar(const std::string& variavel,
                   const std::vector<std::string>& corpo);

    const std::string& nome() const noexcept;
    const std::string& inicial() const noexcept;
    const std::vector<Producao>& producoes() const noexcept;

    std::set<std::string> variaveis() const;
    std::set<std::string> terminais() const;
    std::vector<Producao> producoesDe(const std::string& variavel) const;
    bool ehVariavel(const std::string& simbolo) const;

    std::string formatar() const;

    // Símbolos que derivam a cadeia vazia, direta ou indiretamente. Calculado
    // por ponto fixo: começa com quem tem produção vazia e cresce enquanto
    // alguma variável tiver um corpo inteiro formado por anuláveis.
    std::set<std::string> anulaveis() const;

    // Símbolos produtivos: os que derivam alguma cadeia só de terminais.
    // Variável improdutiva costuma ser esquecimento — uma produção que ficou
    // faltando.
    std::set<std::string> produtivos() const;

    // Símbolos alcançáveis a partir do inicial. Variável inalcançável costuma
    // ser resto de uma reescrita da gramática.
    std::set<std::string> alcancaveis() const;

    // Inúteis = improdutivos ou inalcançáveis. A ordem de remoção importa:
    // tirar improdutivos primeiro pode tornar outras variáveis inalcançáveis,
    // e o contrário não é verdade.
    Gramatica semSimbolosInuteis(std::string novoNome) const;

    // Produções unitárias: corpo formado por uma única variável, como
    // `expr -> exprE`. Não produzem terminal algum; só renomeiam.
    std::vector<Producao> producoesUnitarias() const;

    // Remove as unitárias por fechamento: cada variável herda diretamente as
    // produções não unitárias de tudo que ela alcança por renomeação.
    //
    // Cuidado ao aplicar: a estratificação por precedência PRODUZ unitárias de
    // propósito — `expr -> exprE` é o elo entre dois níveis. Removê-las
    // encurta a derivação e destrói a hierarquia que tornava a precedência
    // legível na própria gramática. A transformação existe porque certos
    // algoritmos a exigem, não porque a gramática fique melhor.
    Gramatica semProducoesUnitarias(std::string novoNome) const;

    std::size_t quantidadeDeProducoes() const noexcept;

private:
    std::string nome_;
    std::string inicial_;
    std::vector<Producao> producoes_;
};

}  // namespace peneira

#endif  // PENEIRA_08_GRAMATICA_H

Antes da gramática, a representação. Uma decisão vale explicar: não guardo variáveis e terminais em listas separadas. Variável é todo símbolo que aparece do lado esquerdo de alguma produção; terminal é todo o resto que aparece em algum corpo. Derivar em vez de declarar elimina uma classe inteira de erro — a variável declarada que nunca recebe produção. Nessa representação ela simplesmente vira terminal, e a checagem de símbolos improdutivos a encontra.

A gramática:

C++

08_gramaticas.cpp

#include "08_gramaticas.h"

#include <set>

#include "01_diagnostico.h"
#include "01_source.h"
#include "07_lexer.h"

namespace peneira {

Gramatica gramaticaPeneira() {
    Gramatica g("gramatica da Peneira", "programa");

    // A repetição da notação estendida vira recursão. Escolhi recursão à
    // DIREITA para as listas de declaração e de ação: elas não têm operador
    // entre os elementos, então a associatividade não significa nada, e a
    // recursão à direita produz árvores que se leem de cima para baixo na
    // ordem do texto.
    g.adicionar("programa", {"listaDecl"});
    g.adicionar("listaDecl", {"decl", "listaDecl"});
    g.adicionar("listaDecl", {"decl"});

    g.adicionar("decl", {"declPadrao"});
    g.adicionar("decl", {"blocoRegra"});

    g.adicionar("declPadrao", {"pattern", "ID", "=", "PADRAO", ";"});

    g.adicionar("blocoRegra", {"rule", "{", "listaAcao", "}"});
    g.adicionar("listaAcao", {"acao", "listaAcao"});
    g.adicionar("listaAcao", {"acao"});

    // O opcional da notação estendida vira duas produções. Não há como
    // representar "opcional" numa gramática livre de contexto senão assim, e é
    // por isso que a versão em BNF é mais longa que o design.
    g.adicionar("acao", {"on", "ID", "(", "ID", ")", "=>", "emit", "(", "TEXTO",
                         ",", "expr", ")", ";"});
    g.adicionar("acao", {"on", "ID", "(", "ID", ")", "where", "expr", "=>",
                         "emit", "(", "TEXTO", ",", "expr", ")", ";"});

    // Aqui o lado da recursão IMPORTA. Recursão à esquerda dá associatividade
    // à esquerda: "a or b or c" agrupa como "(a or b) or c", que é o que se
    // espera de um operador binário. Trocar o lado mudaria o agrupamento sem
    // mudar a linguagem reconhecida — mesmo conjunto de cadeias, árvores
    // diferentes, semântica diferente no módulo 12.
    g.adicionar("expr", {"expr", "or", "exprE"});
    g.adicionar("expr", {"exprE"});

    g.adicionar("exprE", {"exprE", "and", "comparacao"});
    g.adicionar("exprE", {"comparacao"});

    // A comparação NÃO é recursiva: "a > b > c" não faz sentido nesta
    // linguagem, e a gramática recusa em vez de aceitar e deixar a semântica
    // resolver. Recusar cedo é mais barato que explicar depois.
    g.adicionar("comparacao", {"primaria", "OPREL", "primaria"});
    g.adicionar("comparacao", {"primaria"});

    g.adicionar("primaria", {"ID"});
    g.adicionar("primaria", {"NUMERO"});
    g.adicionar("primaria", {"TEXTO"});
    g.adicionar("primaria", {"value", "(", "ID", ")"});
    g.adicionar("primaria", {"(", "expr", ")"});

    return g;
}

Gramatica gramaticaExpressaoAmbigua() {
    Gramatica g("expressao sem estratificacao", "E");
    g.adicionar("E", {"E", "+", "E"});
    g.adicionar("E", {"E", "*", "E"});
    g.adicionar("E", {"num"});
    return g;
}

Gramatica gramaticaExpressaoEstratificada() {
    Gramatica g("expressao estratificada", "E");
    // Um nível por precedência, do operador que liga mais fraco para o que
    // liga mais forte. A recursão à esquerda em cada nível dá a
    // associatividade à esquerda.
    g.adicionar("E", {"E", "+", "T"});
    g.adicionar("E", {"T"});
    g.adicionar("T", {"T", "*", "F"});
    g.adicionar("T", {"F"});
    g.adicionar("F", {"num"});
    return g;
}

Gramatica gramaticaCondicionalAmbigua() {
    Gramatica g("condicional ambiguo", "S");
    g.adicionar("S", {"se", "c", "entao", "S"});
    g.adicionar("S", {"se", "c", "entao", "S", "senao", "S"});
    g.adicionar("S", {"cmd"});
    return g;
}

Gramatica gramaticaCondicionalDesambiguada() {
    Gramatica g("condicional desambiguado", "S");
    // A separação em "casado" e "aberto" força o `senao` a se ligar ao `se`
    // mais próximo: o ramo verdadeiro de um condicional com alternativa só
    // aceita comandos que já tenham a sua própria alternativa.
    g.adicionar("S", {"casado"});
    g.adicionar("S", {"aberto"});
    g.adicionar("casado", {"se", "c", "entao", "casado", "senao", "casado"});
    g.adicionar("casado", {"cmd"});
    g.adicionar("aberto", {"se", "c", "entao", "S"});
    g.adicionar("aberto", {"se", "c", "entao", "casado", "senao", "aberto"});
    return g;
}

Gramatica gramaticaComDefeitos() {
    Gramatica g("gramatica com defeitos", "S");
    g.adicionar("S", {"A", "B"});
    g.adicionar("S", {"a"});
    g.adicionar("A", {"a", "A"});
    g.adicionar("A", {});              // produção vazia: A é anulável
    g.adicionar("B", {"b"});
    g.adicionar("C", {"c", "C"});      // improdutiva: nunca chega a terminais
    g.adicionar("D", {"d"});           // inalcançável a partir de S
    return g;
}

std::vector<std::string> terminaisDe(
    const std::vector<SimboloLexico>& simbolos) {
    static const std::set<std::string> comparadores{"<", ">", "==",
                                                    "!=", ">=", "<="};
    std::vector<std::string> terminais;

    for (const SimboloLexico& s : simbolos) {
        switch (s.categoria) {
            case Categoria::PalavraReservada:
                terminais.push_back(s.lexema);
                break;
            case Categoria::Identificador:
                terminais.push_back("ID");
                break;
            case Categoria::Numero:
                terminais.push_back("NUMERO");
                break;
            case Categoria::Texto:
                terminais.push_back("TEXTO");
                break;
            case Categoria::Padrao:
                terminais.push_back("PADRAO");
                break;
            case Categoria::Pontuacao:
                terminais.push_back(comparadores.count(s.lexema) > 0
                                        ? std::string("OPREL")
                                        : s.lexema);
                break;
            case Categoria::FimDeArquivo:
            case Categoria::Invalido:
                break;
        }
    }
    return terminais;
}

std::vector<std::string> terminaisDoPrograma(const std::string& fonte) {
    const SourceFile arquivo = SourceFile::fromText("trecho.pen", fonte);
    DiagnosticBag diagnosticos;
    AnalisadorLexico lexer(arquivo, diagnosticos);
    return terminaisDe(lexer.todos());
}

}  // namespace peneira

Impressa, ela cabe em onze linhas:

programa    -> listaDecl
listaDecl   -> decl listaDecl | decl
decl        -> declPadrao | blocoRegra
declPadrao  -> pattern ID = PADRAO ;
blocoRegra  -> rule { listaAcao }
listaAcao   -> acao listaAcao | acao
acao        -> on ID ( ID ) => emit ( TEXTO , expr ) ;
             | on ID ( ID ) where expr => emit ( TEXTO , expr ) ;
expr        -> expr or exprE | exprE
exprE       -> exprE and comparacao | comparacao
comparacao  -> primaria OPREL primaria | primaria
primaria    -> ID | NUMERO | TEXTO | value ( ID ) | ( expr )

Onze variáveis, vinte e um terminais, vinte e duas produções. Quatro decisões de tradução merecem defesa.

A repetição virou recursão, e o lado importa em um caso e não no outro. Para as listas de declaração e de ação escolhi recursão à direita: elas não têm operador entre os elementos, então a associatividade não significa nada, e a recursão à direita produz árvores que se leem de cima para baixo na ordem do texto. Para os operadores or e and, escolhi recursão à esquerda, e aí a escolha é semântica: ela agrupa a or b or c como (a or b) or c. Trocar o lado não mudaria a linguagem reconhecida — mesmo conjunto de cadeias — e mudaria as árvores, e portanto o significado que o módulo 12 vai extrair delas.

O opcional virou duas produções. A ação com where e a ação sem where são produções distintas, e não há alternativa: uma gramática livre de contexto não tem como dizer “opcional”. É a razão de a versão em BNF ser mais longa que o design, e é honesto reconhecer que a notação estendida existe justamente porque essa expansão é chata de escrever à mão.

A comparação não é recursiva. a > b > c não faz sentido nesta linguagem, e a gramática recusa em vez de aceitar e deixar a semântica reclamar depois. Recusar cedo é mais barato que explicar tarde: o erro sai como erro de sintaxe apontando o segundo operador, em vez de virar uma mensagem obscura sobre tipos no módulo 12.

Não há produção vazia, de propósito. Escrevi as listas exigindo pelo menos um elemento. Um programa vazio ou um bloco de regra sem ação não são úteis, e proibi-los na gramática evita tratar o caso em todas as fases seguintes. A verificação confirma: o conjunto de anuláveis é vazio.

A checagem de higiene também passa limpa — nenhum símbolo improdutivo, nenhum inalcançável:

  11 variaveis, 21 terminais, 22 producoes
  Simbolos improdutivos: {}
  Simbolos inalcancaveis: {}

Onde é fácil errar aqui. Traduzir o opcional como uma variável anulável — algo como whereOpcional -> where expr | e. Funciona e é pior: introduz produção vazia numa gramática que não precisava de nenhuma, e o módulo 10 vai pagar por isso no cálculo dos conjuntos que orientam a análise, onde variáveis anuláveis são a principal fonte de erro.

Como verificar. Além dos conjuntos vazios de símbolos inúteis, cada programa de exemplo precisa derivar — e derivar de uma única forma. É a tarefa 3.

1.3 Tarefa 2: O argumento de não ambiguidade

A atividade — argumentar que a gramática é não ambígua, com a justificativa das escolhas de precedência e associatividade.

Antes de argumentar sobre a gramática da Peneira, construí a ferramenta que torna o argumento verificável.

C++

08_derivacao.h

#ifndef PENEIRA_08_DERIVACAO_H
#define PENEIRA_08_DERIVACAO_H

#include <cstddef>
#include <memory>
#include <string>
#include <vector>

#include "08_gramatica.h"

namespace peneira {

// Nó de uma árvore de derivação. Folha é o nó sem filhos, e o rótulo dela é um
// terminal; nó interno é rotulado por uma variável, e seus filhos são o corpo
// da produção aplicada.
struct NoDerivacao;
using ArvorePtr = std::shared_ptr<const NoDerivacao>;

struct NoDerivacao {
    std::string rotulo;
    std::vector<ArvorePtr> filhos;
};

// Enumera TODAS as árvores de derivação de uma sequência de terminais.
//
// É um reconhecedor exaustivo, no espírito do algoritmo de Cocke, Younger e
// Kasami: preenche uma tabela indexada por (variável, início, fim) e combina
// os pedaços. Não é o analisador sintático do projeto — aquele chega no módulo
// 10, é linear e produz UMA árvore. Este é instrumento de estudo: serve para
// responder "quantas árvores existem?", e é assim que a ambiguidade deixa de
// ser afirmação e vira contagem.
//
// Exige gramática SEM produções vazias. Com elas, um span de tamanho zero
// admitiria infinitas derivações e a enumeração não terminaria. A restrição
// está aqui em vez de ser contornada porque as gramáticas que interessam a
// este módulo são todas livres de vazio.
//
// `limite` corta a coleta por célula, para que uma gramática muito ambígua não
// exploda a memória. Quando o corte age, o resultado é "pelo menos isto", e o
// chamador é avisado por `atingiuLimite`.
struct ResultadoDerivacao {
    std::vector<ArvorePtr> arvores;
    bool atingiuLimite = false;
};

ResultadoDerivacao derivacoes(const Gramatica& g,
                              const std::vector<std::string>& entrada,
                              std::size_t limite);

// Desenho da árvore em texto, por indentação.
std::string desenhar(const ArvorePtr& raiz);

// Sequência de formas sentenciais da derivação mais à esquerda que a árvore
// representa. É o que torna precisa a relação entre árvore e derivação: cada
// árvore corresponde a exatamente uma derivação mais à esquerda.
std::vector<std::string> derivacaoMaisAEsquerda(const Gramatica& g,
                                                const ArvorePtr& raiz);

// Frontier da árvore: a cadeia de terminais que ela deriva.
std::vector<std::string> fronteira(const ArvorePtr& raiz);

}  // namespace peneira

#endif  // PENEIRA_08_DERIVACAO_H

C++

08_derivacao.cpp

#include "08_derivacao.h"

#include <map>
#include <sstream>
#include <utility>

namespace peneira {

namespace {

using Chave = std::tuple<std::string, std::size_t, std::size_t>;

class Enumerador {
public:
    Enumerador(const Gramatica& g, const std::vector<std::string>& entrada,
               std::size_t limite)
        : g_(g), entrada_(entrada), limite_(limite) {}

    ResultadoDerivacao executar() {
        ResultadoDerivacao r;
        if (entrada_.empty()) {
            return r;
        }
        r.arvores = paraVariavel(g_.inicial(), 0, entrada_.size());
        r.atingiuLimite = cortou_;
        return r;
    }

private:
    // Todas as árvores de `variavel` cobrindo exatamente o intervalo [i, j).
    std::vector<ArvorePtr> paraVariavel(const std::string& variavel,
                                        std::size_t i, std::size_t j) {
        const Chave chave{variavel, i, j};
        const auto emCache = memo_.find(chave);
        if (emCache != memo_.end()) {
            return emCache->second;
        }

        // Marca o cache antes de descer, para que recursão à esquerda não gire
        // para sempre. Uma variável que precise de si mesma no mesmo intervalo
        // encontra a lista vazia e desiste daquele caminho — que é o
        // comportamento correto, já que sem consumir entrada não há progresso.
        memo_[chave] = std::vector<ArvorePtr>();

        std::vector<ArvorePtr> resultado;
        for (const Producao& p : g_.producoesDe(variavel)) {
            if (p.ehVazia()) {
                continue;  // gramática sem vazio, por contrato
            }
            for (std::vector<ArvorePtr>& filhos : paraCorpo(p.corpo, 0, i, j)) {
                if (resultado.size() >= limite_) {
                    cortou_ = true;
                    break;
                }
                NoDerivacao no;
                no.rotulo = variavel;
                no.filhos = std::move(filhos);
                resultado.push_back(std::make_shared<const NoDerivacao>(
                    std::move(no)));
            }
        }

        memo_[chave] = resultado;
        return resultado;
    }

    // Todas as formas de casar corpo[pos..] com o intervalo [i, j).
    std::vector<std::vector<ArvorePtr>> paraCorpo(
        const std::vector<std::string>& corpo, std::size_t pos, std::size_t i,
        std::size_t j) {
        std::vector<std::vector<ArvorePtr>> resultado;

        if (pos == corpo.size()) {
            if (i == j) {
                resultado.emplace_back();
            }
            return resultado;
        }

        const std::string& simbolo = corpo[pos];
        const bool ultimo = pos + 1 == corpo.size();

        // Cada símbolo consome ao menos um terminal, porque a gramática não
        // tem produção vazia. Isso limita as divisões possíveis e é o que faz
        // a enumeração terminar.
        const std::size_t restantes = corpo.size() - pos - 1;
        for (std::size_t corte = i + 1; corte + restantes <= j; ++corte) {
            if (ultimo && corte != j) {
                continue;
            }

            std::vector<ArvorePtr> cabecas;
            if (g_.ehVariavel(simbolo)) {
                cabecas = paraVariavel(simbolo, i, corte);
            } else if (corte == i + 1 && entrada_[i] == simbolo) {
                NoDerivacao folha;
                folha.rotulo = simbolo;
                cabecas.push_back(
                    std::make_shared<const NoDerivacao>(std::move(folha)));
            }
            if (cabecas.empty()) {
                continue;
            }

            for (const std::vector<ArvorePtr>& cauda :
                 paraCorpo(corpo, pos + 1, corte, j)) {
                for (const ArvorePtr& cabeca : cabecas) {
                    if (resultado.size() >= limite_) {
                        cortou_ = true;
                        return resultado;
                    }
                    std::vector<ArvorePtr> junto;
                    junto.reserve(cauda.size() + 1);
                    junto.push_back(cabeca);
                    junto.insert(junto.end(), cauda.begin(), cauda.end());
                    resultado.push_back(std::move(junto));
                }
            }
        }
        return resultado;
    }

    const Gramatica& g_;
    const std::vector<std::string>& entrada_;
    std::size_t limite_;
    std::map<Chave, std::vector<ArvorePtr>> memo_;
    bool cortou_ = false;
};

void desenharEm(const ArvorePtr& no, std::size_t nivel,
                std::ostringstream& saida) {
    for (std::size_t i = 0; i < nivel; ++i) {
        saida << "  ";
    }
    saida << no->rotulo << '\n';
    for (const ArvorePtr& filho : no->filhos) {
        desenharEm(filho, nivel + 1, saida);
    }
}

void fronteiraEm(const ArvorePtr& no, std::vector<std::string>& saida) {
    if (no->filhos.empty()) {
        saida.push_back(no->rotulo);
        return;
    }
    for (const ArvorePtr& filho : no->filhos) {
        fronteiraEm(filho, saida);
    }
}

}  // namespace

ResultadoDerivacao derivacoes(const Gramatica& g,
                              const std::vector<std::string>& entrada,
                              std::size_t limite) {
    Enumerador e(g, entrada, limite);
    return e.executar();
}

std::string desenhar(const ArvorePtr& raiz) {
    std::ostringstream saida;
    if (raiz) {
        desenharEm(raiz, 1, saida);
    }
    return saida.str();
}

std::vector<std::string> fronteira(const ArvorePtr& raiz) {
    std::vector<std::string> saida;
    if (raiz) {
        fronteiraEm(raiz, saida);
    }
    return saida;
}

std::vector<std::string> derivacaoMaisAEsquerda(const Gramatica& g,
                                                const ArvorePtr& raiz) {
    std::vector<std::string> passos;
    if (!raiz) {
        return passos;
    }

    // A forma sentencial corrente, como lista de símbolos, junto com o nó da
    // árvore que ainda precisa ser expandido em cada posição.
    std::vector<std::string> forma{raiz->rotulo};
    std::vector<ArvorePtr> pendentes{raiz};

    for (;;) {
        std::ostringstream linha;
        for (std::size_t i = 0; i < forma.size(); ++i) {
            if (i > 0) linha << ' ';
            linha << forma[i];
        }
        passos.push_back(linha.str());

        // Expande a variável mais à esquerda que ainda tem filhos.
        std::size_t alvo = forma.size();
        for (std::size_t i = 0; i < forma.size(); ++i) {
            if (pendentes[i] && !pendentes[i]->filhos.empty() &&
                g.ehVariavel(forma[i])) {
                alvo = i;
                break;
            }
        }
        if (alvo == forma.size()) {
            return passos;
        }

        const ArvorePtr no = pendentes[alvo];
        std::vector<std::string> novaForma(forma.begin(), forma.begin() + static_cast<long>(alvo));
        std::vector<ArvorePtr> novosPendentes(pendentes.begin(),
                                              pendentes.begin() + static_cast<long>(alvo));
        for (const ArvorePtr& filho : no->filhos) {
            novaForma.push_back(filho->rotulo);
            novosPendentes.push_back(filho);
        }
        novaForma.insert(novaForma.end(), forma.begin() + static_cast<long>(alvo) + 1,
                         forma.end());
        novosPendentes.insert(novosPendentes.end(),
                              pendentes.begin() + static_cast<long>(alvo) + 1,
                              pendentes.end());
        forma = std::move(novaForma);
        pendentes = std::move(novosPendentes);
    }
}

}  // namespace peneira

O enumerador preenche uma tabela indexada por variável e intervalo da entrada, no espírito do algoritmo de Cocke, Younger e Kasami, e combina os pedaços. Duas particularidades da implementação valem nota.

A memoização é marcada antes da descida, com lista vazia. Isso faz a recursão à esquerda terminar: uma variável que precise de si mesma no mesmo intervalo encontra a lista vazia e desiste daquele caminho — comportamento correto, já que sem consumir entrada não há progresso. Sem essa marca prévia, expr -> expr or exprE giraria para sempre.

E o enumerador exige gramática sem produção vazia. Com elas, um intervalo de tamanho zero admitiria infinitas derivações. A restrição está declarada no cabeçalho em vez de contornada, e ela é satisfeita por construção pelas gramáticas deste módulo.

1.3.1 Ambiguidade é contagem, não opinião

A demonstração pega o exemplo clássico. Duas gramáticas para a mesma linguagem:

expressao sem estratificacao:  E -> E + E | E * E | num
expressao estratificada:       E -> E + T | T
                               T -> T * F | F
                               F -> num

E a mesma cadeia nas duas:

    "num + num * num"  ->  2 arvore(s)      (sem estratificacao)
    "num + num * num"  ->  1 arvore(s)      (estratificada)

As duas leituras, exibidas:

  leitura 1:              leitura 2:
  E                       E
    E                       E
      num                     E
    +                           num
    E                         +
      E                       E
        num                     num
      *                     *
      E                     E
        num                   num

Uma agrupa como soma de um produto; a outra, como produto de uma soma. São valores numéricos diferentes para o mesmo texto, e a gramática não tem como escolher.

A gramática estratificada dá uma árvore só, e a razão é estrutural: um produto só pode aparecer dentro de uma soma, nunca ao contrário, porque T é alcançável a partir de E e E não é alcançável a partir de T senão dentro de parênteses. A precedência deixou de ser convenção externa e virou hierarquia de variáveis.

A associatividade sai do mesmo lugar. Com recursão à esquerda, num + num + num também dá uma árvore só, e ela agrupa à esquerda. É por isso que o lado da recursão foi escolhido conscientemente na tarefa 1.

1.3.2 O argumento para a Peneira

Com o instrumento na mão, o argumento fica curto e verificável. A gramática da Peneira tem três níveis de expressão — expr, exprE e comparacao — estratificados na ordem de precedência or, and, comparação. Cada nível referencia apenas o nível imediatamente mais forte, e o ciclo só se fecha por parênteses explícitos em primaria. É exatamente a estrutura da gramática estratificada de expressões, com três níveis em vez de dois.

Fora das expressões, não há ambiguidade possível: cada produção começa por um terminal distinto. declPadrao começa por pattern, blocoRegra por rule, acao por on, e as duas formas de acao divergem no símbolo que segue o parêntese de fechamento — where ou =>. Não há ponto em que duas produções da mesma variável possam começar igual e seguir diferente.

O enumerador confirma sobre os programas reais, na tarefa 3.

Onde é fácil errar aqui. Confundir “não encontrei ambiguidade” com “não há ambiguidade”. Testar cadeias não demonstra: a ambiguidade de uma gramática arbitrária é indecidível, e nenhum algoritmo decide o caso geral. O que o enumerador oferece é refutação — se ele encontra duas árvores, a gramática é ambígua e ponto final. Não encontrar nada em vinte cadeias é evidência, e o argumento estrutural é o que sustenta a afirmação.

1.4 Tarefa 3: As árvores de derivação

A atividade — produzir a árvore de derivação de pelo menos três programas de exemplo.

As árvores vêm do analisador léxico do módulo 7. O programa é analisado de verdade, os símbolos viram terminais da gramática, e o enumerador deriva. Nenhum passo é feito à mão.

A conversão colapsa os seis operadores de comparação num terminal único, OPREL. A gramática não distingue entre > e <=, e não deveria: quem distingue é a análise semântica do módulo 12, e carregar essa distinção na sintaxe multiplicaria produções sem ganho.

O primeiro programa, pattern email = /[a-z]+/;:

  terminais: pattern ID = PADRAO ;
  arvores: 1   (uma so — a gramatica nao e ambigua para esta cadeia)

  programa
    listaDecl
      decl
        declPadrao
          pattern
          ID
          =
          PADRAO
          ;

Cinco terminais, uma árvore, cinco formas sentenciais na derivação mais à esquerda. Os três programas testados — a declaração de padrão, uma regra simples e uma regra com condição — derivam de forma única.

1.4.1 Árvore e derivação não são a mesma coisa

O módulo insiste nessa distinção e vale materializá-la. A derivação mais à esquerda do primeiro exemplo:

    programa
    listaDecl
    decl
    declPadrao
    pattern ID = PADRAO ;

Cinco formas sentenciais, cada uma obtida da anterior substituindo a variável mais à esquerda. A derivação é uma sequência; a árvore é uma estrutura. A árvore abstrai a ordem em que as substituições aconteceram — e é por isso que cada árvore corresponde a exatamente uma derivação mais à esquerda e a exatamente uma mais à direita.

A consequência prática é o teste de ambiguidade. Contar derivações não serve: a mesma árvore dá derivações diferentes conforme a ordem de expansão. Contar árvores é o teste correto, e é o que o enumerador faz.

Onde é fácil errar aqui. Testar a gramática apenas com programas que você escreveu para funcionar. Os três exemplos aqui exercitam caminhos distintos — declaração, ação sem condição, ação com condição — de propósito. Um quarto exemplo com duas declarações e duas ações verificaria as listas recursivas, e vale acrescentá-lo ao conjunto de teste do grupo.

1.5 Referência teórica: o condicional sem alternativa obrigatória

O segundo exemplo clássico de ambiguidade merece código próprio, porque a solução dele é diferente da estratificação e ensina outra coisa.

S -> se c entao S | se c entao S senao S | cmd

Sobre se c entao se c entao cmd senao cmd, o enumerador encontra duas árvores. Uma liga o senao ao se interno, a outra ao externo — comportamentos diferentes do programa para o mesmo texto.

A desambiguação separa comandos em casados e abertos:

S      -> casado | aberto
casado -> se c entao casado senao casado | cmd
aberto -> se c entao S | se c entao casado senao aberto

Sobre a mesma entrada, uma árvore. O ramo verdadeiro de um condicional com alternativa só aceita comandos que já tenham a sua própria alternativa, o que força o senao a se ligar ao se mais próximo — convenção de praticamente toda linguagem real.

O ponto que quero destacar é o método: a solução não foi acrescentar uma regra fora da gramática dizendo “em caso de dúvida, ligue ao mais próximo”. Foi reescrever a gramática até que ela só admitisse a leitura desejada. A regra externa também funciona, e é o que os geradores de analisadores oferecem via declarações de precedência — mas ela resolve o conflito no analisador, não na especificação, e a especificação continua ambígua para quem a lê.

A Peneira não tem esse problema, e não por sorte: as ações têm delimitador de fim obrigatório e o where não aninha comando algum. Foi escolha de projeto da linguagem, feita lá no módulo 1, quando decidi a aparência dos programas antes de escrever qualquer gramática.

1.6 Referência teórica: simplificação de gramáticas

O módulo trata da remoção de símbolos inúteis, produções vazias e produções unitárias. Implementei os cálculos e demonstro sobre uma gramática pequena e deliberadamente defeituosa:

S -> A B | a
A -> a A | e
B -> b
C -> c C
D -> d

Os três conjuntos:

  anulaveis:      {A}
  produtivos:     {A, B, D, S}
  alcancaveis:    {A, B, S, a, b}

C é improdutiva: toda derivação a partir dela produz outro C e nunca chega a uma cadeia só de terminais. Na prática, é quase sempre uma produção esquecida. D é inalcançável: nenhuma derivação a partir do símbolo inicial chega até ela, e costuma ser resto de uma reescrita anterior.

A ordem da remoção importa e está comentada no código: improdutivos primeiro. Remover uma variável improdutiva pode tornar outras inalcançáveis, e a segunda passagem pega isso. Na ordem inversa, sobram símbolos que já não servem para nada.

O cálculo de anuláveis é um ponto fixo que começa com quem tem produção vazia e cresce enquanto alguma variável tiver um corpo inteiro formado por anuláveis. O caso-base é sutil: o corpo vazio satisfaz a condição por vacuidade, e é isso que dá início ao cálculo.

1.6.1 Produções unitárias, e por que não as removo

A terceira simplificação é a das produções unitárias — aquelas cujo corpo é uma única variável, como expr -> exprE. Elas não produzem terminal algum; apenas renomeiam. A remoção se faz por fechamento: cada variável herda diretamente as produções não unitárias de tudo que ela alcança por renomeação.

A gramática da Peneira tem oito delas, de vinte e duas produções:

    programa -> listaDecl        decl -> blocoRegra
    listaDecl -> decl            listaAcao -> acao
    decl -> declPadrao           expr -> exprE
    exprE -> comparacao          comparacao -> primaria

E aqui está o resultado que vale o tópico inteiro:

  removendo-as: 22 -> 41 producoes

A remoção quase dobra a gramática. O motivo é estrutural: cada variável herda as produções de tudo que alcança por renomeação, e a estratificação criou cadeias longas de renomeação de propósito. expr passa a carregar diretamente tudo que exprE, comparacao e primaria produziam.

Essas oito unitárias são os elos entre os níveis de precedência. Removê-las encurta a derivação em alguns passos e destrói a hierarquia que tornava a precedência legível na própria gramática — o argumento de não ambiguidade da tarefa 2 deixaria de poder ser lido na estrutura. A transformação existe porque certos algoritmos a exigem, não porque a gramática fique melhor, e por isso implementei sem aplicar.

É um caso em que a simplificação canônica é a coisa errada a fazer, e saber disso vale mais que saber executá-la.

A gramática da Peneira, portanto, não precisa de nenhuma das outras simplificações — os conjuntos de inúteis são vazios e não há anuláveis. Isso não é acaso: é consequência de tê-la escrito sem produções vazias e de ter verificado a higiene antes de seguir.

1.7 Tópicos deste módulo sem código de referência

Dois tópicos ficam sem implementação, e registro por quê.

As formas normais de Chomsky e de Greibach são apresentadas pelo que garantem — corpos de tamanho fixo, ou corpo sempre começando por terminal — e são pré-processamento para algoritmos que este projeto não usa. Converter a gramática da Peneira para forma normal de Chomsky produziria uma gramática ilegível, com dezenas de variáveis auxiliares, que serviria a um analisador que não vamos escrever. O enumerador deste módulo, aliás, é uma variante do algoritmo que normalmente exige essa forma — e funciona sem ela porque enumera corpos de qualquer tamanho, ao custo de mais divisões a considerar.

A ambiguidade inerente e a indecidibilidade são resultados negativos sobre a classe. Não há o que implementar sobre a inexistência de um algoritmo; o que o código faz é o oposto e é honesto — o enumerador refuta ambiguidade encontrando duas árvores, e nunca a confirma pela ausência delas. Essa assimetria está escrita no cabeçalho e é a forma prática da indecidibilidade.

1.8 Verificação da entrega

Item	Como conferir	Estado nesta referência
Gramática completa	Todas as construções do design cobertas	11 variáveis, 21 terminais, 22 produções
Sem produções vazias	Conjunto de anuláveis	Vazio
Sem símbolos inúteis	Improdutivos e inalcançáveis	Ambos vazios
Não ambiguidade argumentada	Estratificação em três níveis, produções distinguidas por terminal inicial	Escrito na tarefa 2
Precedência justificada	Hierarquia or, and, comparação	Um nível por precedência
Associatividade justificada	Lado da recursão escolhido por operador	Esquerda nos binários, direita nas listas
Três árvores de derivação	Derivadas dos programas reais via analisador léxico	Três programas, uma árvore cada
Redução de escopo	Nenhuma necessária	A linguagem do módulo 1 coube inteira
Código compila limpo	Nenhum aviso sob o modo estrito	Atende, verificado por compilação e execução

O que quero deixar registrado sobre esta entrega é que ela é a primeira em que o projeto produz um artefato que não é código executável — a gramática é especificação, e o valor dela está em estar correta, não em rodar. O que roda é a ferramenta que a verifica. No módulo 10 essa mesma gramática vira analisador sintático, e cada decisão tomada aqui, sobre lado de recursão e sobre produção vazia, vai cobrar ou poupar trabalho lá.