1 Módulo 10: Projeto do Professor — O Front-End Fica Pronto
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. É o segundo marco de consolidação — o modelo do que o seu grupo entrega, não algo a copiar.
1.1 Visão Geral do Módulo 10
O módulo mais denso do semestre, e o segundo marco. Ao final dele o texto vira estrutura: um programa Peneira entra como sequência de caracteres e sai como árvore.
A atividade tem cinco partes encadeadas, e a ordem entre elas não é negociável. Preparar a gramática, eliminando recursão à esquerda e fatorando. Calcular os conjuntos que orientam as decisões. Verificar a condição que permite decidir com um símbolo de antecipação, interpretando os conflitos que aparecerem. Implementar o analisador por descida recursiva, produzindo a árvore sintática abstrata. E fazer o analisador se recuperar de erros em vez de abortar.
Escrever este módulo custou três defeitos encontrados no próprio código, e resolvi documentá-los em vez de apagá-los. Dois deles são erros que qualquer grupo vai cometer — um uso após movimento e um laço que não progride —, e o terceiro é uma decisão de recuperação que parecia certa e produzia mensagem no lugar errado. Os três foram encontrados rodando, e nenhum teria aparecido em revisão de código.
1.2 Tarefa 1: Preparar a gramática
A atividade — eliminar recursão à esquerda e fatorar, registrando cada transformação e verificando que a linguagem não mudou.
O módulo 9 estabeleceu por que isso vem primeiro: a recursão à esquerda é inofensiva no autômato de pilha não determinístico e fatal na descida recursiva, porque uma função que chama a si mesma antes de consumir símbolo não retorna. Aqui ela é paga.
10_transformacao.h
#ifndef PENEIRA_10_TRANSFORMACAO_H
#define PENEIRA_10_TRANSFORMACAO_H
#include <string>
#include <vector>
#include "08_gramatica.h"
namespace peneira {
// Registro de uma transformação aplicada à gramática. Sem ele, a gramática
// transformada aparece do nada e não há como conferir que ela ainda descreve
// a mesma linguagem.
struct Transformacao {
std::string tipo;
std::string variavel;
std::string descricao;
};
struct ResultadoTransformacao {
Gramatica gramatica;
std::vector<Transformacao> registro;
};
// Elimina recursão à esquerda IMEDIATA. Para `A -> A a1 | ... | b1 | ...`,
// produz `A -> b1 A' | ...` e `A' -> a1 A' | ... | e`.
//
// A transformação preserva a linguagem e MUDA as árvores: o que era recursão
// à esquerda, e portanto associatividade à esquerda, vira recursão à direita.
// A associatividade terá de ser reconstruída na montagem da árvore sintática
// abstrata — dívida registrada no módulo 9 e paga no analisador.
//
// Introduz produções vazias numa gramática que não tinha nenhuma. É o preço, e
// é o que torna obrigatório o tratamento de anuláveis no cálculo dos conjuntos.
ResultadoTransformacao eliminarRecursaoAEsquerda(const Gramatica& g);
// Detecta recursão à esquerda INDIRETA — o ciclo `A` deriva `B` deriva `A`,
// sem consumir nada no caminho. A eliminação geral exige ordenar as variáveis
// e substituir umas nas outras; não a implementei porque a gramática da
// Peneira não tem nenhuma, e implementar um algoritmo sem caso de uso seria
// código morto. Esta função existe para que a ausência seja verificada em vez
// de suposta.
std::vector<std::string> ciclosDeRecursaoIndireta(const Gramatica& g);
// Fatoração à esquerda: quando duas ou mais produções da mesma variável
// começam igual, o analisador de um símbolo de antecipação não consegue
// escolher entre elas. A fatoração adia a escolha até depois do prefixo comum.
ResultadoTransformacao fatorarAEsquerda(const Gramatica& g);
// Aplica as duas transformações na ordem correta e devolve o registro
// acumulado. A ordem importa: fatorar depois de eliminar a recursão evita
// fatorar prefixos que a eliminação teria dissolvido.
ResultadoTransformacao prepararParaDescida(const Gramatica& g);
} // namespace peneira
#endif // PENEIRA_10_TRANSFORMACAO_H10_transformacao.cpp
#include "10_transformacao.h"
#include <algorithm>
#include <map>
#include <set>
#include <utility>
namespace peneira {
namespace {
// Mantém a ordem em que as variáveis aparecem na gramática original. Refazer a
// gramática a partir de um conjunto ordenado alfabeticamente embaralharia a
// leitura, e a gramática transformada precisa continuar legível.
std::vector<std::string> ordemDasVariaveis(const Gramatica& g) {
std::vector<std::string> ordem;
std::set<std::string> vistas;
for (const Producao& p : g.producoes()) {
if (vistas.insert(p.variavel).second) {
ordem.push_back(p.variavel);
}
}
return ordem;
}
std::string corpoEmTexto(const std::vector<std::string>& corpo) {
if (corpo.empty()) {
return "e";
}
std::string s;
for (std::size_t i = 0; i < corpo.size(); ++i) {
if (i > 0) s += ' ';
s += corpo[i];
}
return s;
}
} // namespace
ResultadoTransformacao eliminarRecursaoAEsquerda(const Gramatica& g) {
ResultadoTransformacao r{Gramatica(g.nome() + " sem recursao a esquerda",
g.inicial()),
{}};
for (const std::string& v : ordemDasVariaveis(g)) {
std::vector<std::vector<std::string>> recursivas;
std::vector<std::vector<std::string>> demais;
for (const Producao& p : g.producoesDe(v)) {
if (!p.corpo.empty() && p.corpo.front() == v) {
// Guarda o corpo SEM a variável da frente: é o `a` de `A -> A a`.
recursivas.emplace_back(p.corpo.begin() + 1, p.corpo.end());
} else {
demais.push_back(p.corpo);
}
}
if (recursivas.empty()) {
for (const std::vector<std::string>& corpo : demais) {
r.gramatica.adicionar(v, corpo);
}
continue;
}
const std::string resto = v + "'";
// Cada produção não recursiva ganha a nova variável no fim.
for (const std::vector<std::string>& corpo : demais) {
std::vector<std::string> novo = corpo;
novo.push_back(resto);
r.gramatica.adicionar(v, novo);
}
// E cada recursiva vira uma produção da nova variável, também com ela
// no fim: a recursão passa da esquerda para a direita.
for (const std::vector<std::string>& corpo : recursivas) {
std::vector<std::string> novo = corpo;
novo.push_back(resto);
r.gramatica.adicionar(resto, novo);
}
// A produção vazia é o que permite parar de repetir.
r.gramatica.adicionar(resto, {});
r.registro.push_back(Transformacao{
"recursao a esquerda", v,
"criada " + resto + " com " + std::to_string(recursivas.size()) +
" producao(oes) recursiva(s) e uma vazia; associatividade a "
"esquerda passa a ser responsabilidade do analisador"});
}
return r;
}
std::vector<std::string> ciclosDeRecursaoIndireta(const Gramatica& g) {
// Um passo de "A pode começar por B sem consumir entrada" existe quando
// alguma produção de A tem B na frente. Fecho transitivo disso; se A
// alcança A por dois passos ou mais, há recursão indireta.
std::map<std::string, std::set<std::string>> comeca;
for (const Producao& p : g.producoes()) {
if (!p.corpo.empty() && g.ehVariavel(p.corpo.front())) {
comeca[p.variavel].insert(p.corpo.front());
}
}
std::vector<std::string> ciclos;
for (const std::string& v : ordemDasVariaveis(g)) {
std::set<std::string> alcancados;
std::vector<std::string> pilha(comeca[v].begin(), comeca[v].end());
while (!pilha.empty()) {
const std::string atual = pilha.back();
pilha.pop_back();
if (!alcancados.insert(atual).second) {
continue;
}
for (const std::string& proximo : comeca[atual]) {
pilha.push_back(proximo);
}
}
// Recursão imediata não conta: ela é tratada pela outra função.
if (alcancados.count(v) > 0 && comeca[v].count(v) == 0) {
ciclos.push_back(v);
}
}
return ciclos;
}
ResultadoTransformacao fatorarAEsquerda(const Gramatica& g) {
Gramatica atual = g;
std::vector<Transformacao> registro;
int sufixo = 0;
for (;;) {
bool fatorou = false;
for (const std::string& v : ordemDasVariaveis(atual)) {
const std::vector<Producao> lista = atual.producoesDe(v);
if (lista.size() < 2) {
continue;
}
// Procura o prefixo comum mais longo entre duas produções
// quaisquer. Fatorar o mais longo de uma vez evita ter de repetir
// a operação sobre a variável recém-criada.
std::vector<std::string> melhorPrefixo;
for (std::size_t i = 0; i < lista.size(); ++i) {
for (std::size_t j = i + 1; j < lista.size(); ++j) {
std::size_t k = 0;
while (k < lista[i].corpo.size() &&
k < lista[j].corpo.size() &&
lista[i].corpo[k] == lista[j].corpo[k]) {
++k;
}
if (k > melhorPrefixo.size()) {
melhorPrefixo.assign(lista[i].corpo.begin(),
lista[i].corpo.begin() +
static_cast<long>(k));
}
}
}
if (melhorPrefixo.empty()) {
continue;
}
const std::string novaVariavel =
v + "_f" + std::to_string(++sufixo);
Gramatica proxima(atual.nome(), atual.inicial());
bool jaEmitiuFatorada = false;
for (const Producao& p : atual.producoes()) {
if (p.variavel != v) {
proxima.adicionar(p.variavel, p.corpo);
continue;
}
const bool temPrefixo =
p.corpo.size() >= melhorPrefixo.size() &&
std::equal(melhorPrefixo.begin(), melhorPrefixo.end(),
p.corpo.begin());
if (!temPrefixo) {
proxima.adicionar(v, p.corpo);
continue;
}
if (!jaEmitiuFatorada) {
std::vector<std::string> comum = melhorPrefixo;
comum.push_back(novaVariavel);
proxima.adicionar(v, comum);
jaEmitiuFatorada = true;
}
proxima.adicionar(
novaVariavel,
std::vector<std::string>(
p.corpo.begin() +
static_cast<long>(melhorPrefixo.size()),
p.corpo.end()));
}
registro.push_back(Transformacao{
"fatoracao a esquerda", v,
"prefixo comum \"" + corpoEmTexto(melhorPrefixo) +
"\" extraido para " + novaVariavel});
atual = std::move(proxima);
fatorou = true;
break;
}
if (!fatorou) {
break;
}
}
Gramatica resultado(g.nome() + " fatorada", g.inicial());
for (const Producao& p : atual.producoes()) {
resultado.adicionar(p.variavel, p.corpo);
}
return ResultadoTransformacao{std::move(resultado), std::move(registro)};
}
ResultadoTransformacao prepararParaDescida(const Gramatica& g) {
ResultadoTransformacao semRecursao = eliminarRecursaoAEsquerda(g);
ResultadoTransformacao fatorada = fatorarAEsquerda(semRecursao.gramatica);
std::vector<Transformacao> registro = std::move(semRecursao.registro);
registro.insert(registro.end(), fatorada.registro.begin(),
fatorada.registro.end());
Gramatica resultado(g.nome() + " preparada", g.inicial());
for (const Producao& p : fatorada.gramatica.producoes()) {
resultado.adicionar(p.variavel, p.corpo);
}
return ResultadoTransformacao{std::move(resultado), std::move(registro)};
}
} // namespace peneiraAntes de transformar, verifiquei o que não precisa ser tratado. A recursão à esquerda indireta — o ciclo em que uma variável deriva outra que deriva a primeira, sem consumir nada — exige um algoritmo bem mais caro, que ordena as variáveis e substitui umas nas outras. A gramática da Peneira não tem nenhuma, e o programa confirma:
recursao a esquerda indireta: nenhumaImplementei a detecção e não a eliminação. É uma escolha que vale explicar: escrever um algoritmo sem caso de uso produz código morto, que ninguém exercita e que apodrece. Verificar a ausência, em vez de supô-la, custa vinte linhas e protege contra a gramática mudar no futuro.
As seis transformações aplicadas:
[recursao a esquerda] expr: criada expr' com 1 producao recursiva e uma vazia
[recursao a esquerda] exprE: criada exprE' com 1 producao recursiva e uma vazia
[fatoracao a esquerda] listaDecl: prefixo comum "decl" extraido para listaDecl_f1
[fatoracao a esquerda] listaAcao: prefixo comum "acao" extraido para listaAcao_f2
[fatoracao a esquerda] acao: prefixo comum "on ID ( ID )" extraido para acao_f3
[fatoracao a esquerda] comparacao: prefixo comum "primaria" extraido para comparacao_f4A terceira fatoração é a mais interessante e a que o design da linguagem tornou inevitável. As duas produções de acao compartilham quatro símbolos de prefixo — on ID ( ID ) — e só divergem no quinto, entre where e =>. Um analisador com um símbolo de antecipação não pode escolher no início; a fatoração adia a escolha até depois do prefixo, que é exatamente onde a informação aparece.
O algoritmo procura o prefixo comum mais longo entre quaisquer duas produções, e não o primeiro que encontrar. Extrair o mais longo de uma vez evita ter de refatorar a variável recém-criada, e é o que faz on ID ( ID ) sair inteiro em vez de sair um símbolo por passada.
A gramática cresce de 22 para 28 produções, e ganha o que não tinha:
anulaveis agora: comparacao_f4 expr' exprE' listaAcao_f2 listaDecl_f1A gramática original não tinha produção vazia alguma — foi escrita assim de propósito no módulo 8. As cinco que aparecem agora são consequência direta das transformações, e são elas que tornam obrigatório o tratamento de anuláveis no cálculo dos conjuntos. O módulo 8 evitou o problema; o módulo 10 o reintroduz, e não há como não reintroduzir.
Onde é fácil errar aqui. Na eliminação da recursão à esquerda, esquecer de acrescentar a nova variável ao final das produções não recursivas. O resultado reconhece apenas uma ocorrência do operador: a or b funciona, a or b or c falha. É um erro que passa em metade dos testes.
Como verificar. A gramática transformada precisa derivar as mesmas cadeias. Como o enumerador do módulo 8 exige gramática sem produção vazia, ele não serve para a transformada — a verificação cruzada foi feita de outro jeito: o analisador construído sobre a gramática preparada aceita os mesmos programas que o enumerador aceita sobre a original, e rejeita os mesmos.
1.3 Tarefa 2: Os conjuntos e a condição LL(1)
A atividade — calcular os conjuntos de primeiros e seguidores, construir a tabela e interpretar os conflitos.
10_conjuntos.cpp
#include "10_conjuntos.h"
#include <algorithm>
#include <set>
#include <sstream>
namespace peneira {
const char* const kFimDeEntrada = "$";
const char* const kVazio = "<vazio>";
namespace {
std::vector<std::string> ordemDasVariaveis(const Gramatica& g) {
std::vector<std::string> ordem;
std::set<std::string> vistas;
for (const Producao& p : g.producoes()) {
if (vistas.insert(p.variavel).second) {
ordem.push_back(p.variavel);
}
}
return ordem;
}
bool inserirTodos(std::set<std::string>& destino,
const std::set<std::string>& origem, bool pularVazio) {
bool mudou = false;
for (const std::string& s : origem) {
if (pularVazio && s == kVazio) {
continue;
}
mudou = destino.insert(s).second || mudou;
}
return mudou;
}
} // namespace
Conjuntos calcularPrimeiros(const Gramatica& g) {
Conjuntos primeiros;
// Terminal é o primeiro de si mesmo. Registrar isso explicitamente evita
// um caso especial em toda consulta.
for (const std::string& t : g.terminais()) {
primeiros[t].insert(t);
}
for (const std::string& v : ordemDasVariaveis(g)) {
primeiros[v]; // cria vazio
}
bool mudou = true;
while (mudou) {
mudou = false;
for (const Producao& p : g.producoes()) {
std::set<std::string>& destino = primeiros[p.variavel];
if (p.corpo.empty()) {
mudou = destino.insert(kVazio).second || mudou;
continue;
}
// Percorre o corpo enquanto os símbolos forem anuláveis. O laço só
// passa do símbolo i para o i+1 quando o i pode desaparecer — é
// esse avanço condicional que o cálculo ingênuo esquece.
bool todosAnulaveis = true;
for (const std::string& s : p.corpo) {
mudou = inserirTodos(destino, primeiros[s], true) || mudou;
if (primeiros[s].count(kVazio) == 0) {
todosAnulaveis = false;
break;
}
}
if (todosAnulaveis) {
mudou = destino.insert(kVazio).second || mudou;
}
}
}
return primeiros;
}
std::set<std::string> primeirosDaSequencia(const std::vector<std::string>& seq,
const Conjuntos& primeiros,
const Gramatica& g) {
(void)g;
std::set<std::string> resultado;
bool todosAnulaveis = true;
for (const std::string& s : seq) {
const auto it = primeiros.find(s);
if (it == primeiros.end()) {
resultado.insert(s); // terminal desconhecido: ele mesmo
todosAnulaveis = false;
break;
}
for (const std::string& t : it->second) {
if (t != kVazio) {
resultado.insert(t);
}
}
if (it->second.count(kVazio) == 0) {
todosAnulaveis = false;
break;
}
}
if (todosAnulaveis) {
resultado.insert(kVazio);
}
return resultado;
}
Conjuntos calcularSeguidores(const Gramatica& g, const Conjuntos& primeiros) {
Conjuntos seguidores;
for (const std::string& v : ordemDasVariaveis(g)) {
seguidores[v];
}
seguidores[g.inicial()].insert(kFimDeEntrada);
bool mudou = true;
while (mudou) {
mudou = false;
for (const Producao& p : g.producoes()) {
for (std::size_t i = 0; i < p.corpo.size(); ++i) {
const std::string& s = p.corpo[i];
if (!g.ehVariavel(s)) {
continue;
}
const std::vector<std::string> resto(
p.corpo.begin() + static_cast<long>(i) + 1, p.corpo.end());
const std::set<std::string> primeirosDoResto =
primeirosDaSequencia(resto, primeiros, g);
mudou = inserirTodos(seguidores[s], primeirosDoResto, true) ||
mudou;
// Quando o que vem depois pode desaparecer — ou não há nada
// depois —, tudo que segue a variável da produção também segue
// este símbolo. É o caso que o cálculo à mão mais erra.
if (primeirosDoResto.count(kVazio) > 0 || resto.empty()) {
mudou =
inserirTodos(seguidores[s], seguidores[p.variavel],
false) ||
mudou;
}
}
}
}
return seguidores;
}
const std::vector<Producao>* TabelaLL1::consultar(
const std::string& variavel, const std::string& terminal) const {
for (const EntradaDaTabela& e : entradas) {
if (e.variavel == variavel && e.terminal == terminal) {
return &e.producoes;
}
}
return nullptr;
}
TabelaLL1 construirTabela(const Gramatica& g, const Conjuntos& primeiros,
const Conjuntos& seguidores) {
std::map<std::pair<std::string, std::string>, std::vector<Producao>> celulas;
for (const Producao& p : g.producoes()) {
const std::set<std::string> primeirosDoCorpo =
primeirosDaSequencia(p.corpo, primeiros, g);
for (const std::string& t : primeirosDoCorpo) {
if (t == kVazio) {
continue;
}
celulas[{p.variavel, t}].push_back(p);
}
// Se o corpo pode desaparecer, a produção também serve para todo
// terminal que possa seguir a variável — é assim que a produção vazia
// entra na tabela.
if (primeirosDoCorpo.count(kVazio) > 0) {
const auto it = seguidores.find(p.variavel);
if (it != seguidores.end()) {
for (const std::string& t : it->second) {
celulas[{p.variavel, t}].push_back(p);
}
}
}
}
TabelaLL1 tabela;
for (const auto& par : celulas) {
EntradaDaTabela e{par.first.first, par.first.second, par.second};
tabela.entradas.push_back(e);
if (e.ehConflito()) {
tabela.conflitos.push_back(e);
}
}
return tabela;
}
std::string formatarConjuntos(const Gramatica& g, const Conjuntos& c,
const std::string& titulo) {
std::ostringstream saida;
saida << titulo << '\n';
for (const std::string& v : ordemDasVariaveis(g)) {
const auto it = c.find(v);
if (it == c.end()) {
continue;
}
saida << " " << v << ": {";
bool primeiro = true;
for (const std::string& s : it->second) {
if (!primeiro) saida << ", ";
saida << s;
primeiro = false;
}
saida << "}\n";
}
return saida.str();
}
} // namespace peneiraOs dois cálculos são pontos fixos, e os dois têm o mesmo ponto de tropeço: as variáveis anuláveis.
No cálculo dos primeiros, o laço que percorre o corpo de uma produção só avança do símbolo para o seguinte quando o atual pode desaparecer. Quem escreve o laço percorrendo o corpo inteiro obtém conjuntos grandes demais; quem para sempre no primeiro símbolo obtém conjuntos pequenos demais, e a tabela resultante rejeita programas válidos. O avanço condicional é a linha que separa as duas coisas.
No cálculo dos seguidores, o caso análogo é o do que vem depois do símbolo. Quando o resto da produção pode desaparecer — ou quando não há resto —, tudo que segue a variável da produção também segue o símbolo. É o caso que o cálculo à mão mais erra, e é por isso que ele está comentado no código.
Uma decisão pequena que se paga: registrei cada terminal como primeiro de si mesmo, em vez de tratar terminais como caso especial em toda consulta. Custa um laço de inicialização e elimina uma condicional de todos os lugares que consultam.
Com os conjuntos prontos, a tabela:
tabela de analise: 49 celulas
conflitos: 0
a gramatica preparada e LL(1)? SIMQuarenta e nove células, zero conflitos. Um símbolo de antecipação basta em toda situação — que é exatamente a adivinhação que o autômato de pilha do módulo 9 tinha de fazer às cegas, agora decidida.
1.3.1 O conflito como diagnóstico
Construir a tabela da gramática original, sem preparo, mostra o que o preparo comprou:
para comparar, a gramatica ORIGINAL, sem preparo:
celulas: 30, conflitos: 19
(acao, on) com 2 producoes
(comparacao, ID) com 2 producoes
(expr, ID) com 2 producoes
(exprE, ID) com 2 producoes
(listaDecl, pattern) com 2 producoes
... e mais 14Dezenove conflitos. Cada um é um lugar onde a descida recursiva ingênua não saberia o que fazer, e eles se agrupam por causa: os de expr e exprE vêm da recursão à esquerda, os de acao, listaDecl, listaAcao e comparacao vêm dos prefixos comuns.
Vale insistir no ponto: conflito não é falha do algoritmo, é diagnóstico da gramática. A tabela não está errada — ela está informando que a gramática, como escrita, não permite decidir com um símbolo. Ler o conflito e identificar a causa é a habilidade que o módulo ensina, e é a mesma que se usa depois para interpretar o relatório de um gerador de analisadores.
Onde é fácil errar aqui. Esquecer o marcador de fim de entrada no conjunto de seguidores do símbolo inicial. Sem ele, a produção vazia da variável mais externa não entra na tabela, e o analisador rejeita o programa exatamente no último símbolo — erro que aparece só em entrada completa e some em qualquer teste de trecho.
1.4 Tarefa 3: O analisador por descida recursiva
A atividade — implementar o analisador e produzir a árvore sintática abstrata.
10_ast.h
#ifndef PENEIRA_10_AST_H
#define PENEIRA_10_AST_H
#include <cstdint>
#include <memory>
#include <string>
#include <vector>
#include "01_source.h"
namespace peneira {
// Árvore sintática ABSTRATA — não é a árvore de derivação.
//
// A diferença é o que fica de fora. A árvore de derivação do módulo 8 tem um
// nó para cada aplicação de produção, incluindo as variáveis auxiliares que a
// eliminação de recursão criou e os terminais de pontuação. A abstrata guarda
// só o que as fases seguintes precisam: nada de ponto e vírgula, nada de
// parênteses, nada de `expr'`.
//
// Decidir o que ela carrega é decisão de projeto com consequência nos módulos
// 12 a 14, que a percorrem. Guardei a posição em todo nó, porque a análise
// semântica precisa reportar erro em algum lugar, e o tipo de nó como
// enumerado, porque os percursos seguintes vão despachar sobre ele.
enum class TipoAst : std::uint8_t {
Programa,
DeclPadrao, // texto = nome do padrão, conteudo = a expressão regular
BlocoRegra,
Acao, // texto = padrão referenciado, conteudo = variável de ligação
Ou,
E,
Comparacao, // texto = operador
Referencia, // texto = nome
LiteralNumero,
LiteralTexto,
ValorDe, // texto = nome da variável de ligação
Emissao, // texto = rótulo emitido
};
const char* nomeDoTipoAst(TipoAst t) noexcept;
struct NoAst;
using AstPtr = std::unique_ptr<NoAst>;
// Nó com marcador de tipo, em vez de hierarquia de classes com despacho
// virtual. A troca é consciente: os percursos dos módulos 12 a 14 vão decidir
// sobre o tipo de qualquer forma, e o nó uniforme mantém curtos o código de
// impressão e o de travessia. O custo é que a estrutura não impede um nó de
// carregar filhos que não fazem sentido para o seu tipo — risco que o
// construtor único, usado por todo o analisador, mantém sob controle.
struct NoAst {
TipoAst tipo;
std::string texto;
std::string conteudo;
double numero = 0.0;
Position posicao{0, 0, 0};
std::vector<AstPtr> filhos;
};
AstPtr criarNo(TipoAst tipo, Position posicao, std::string texto = "",
std::string conteudo = "");
std::string desenharAst(const NoAst& raiz);
// Conta os nós, para comparar com a árvore de derivação concreta.
std::size_t contarNos(const NoAst& raiz);
} // namespace peneira
#endif // PENEIRA_10_AST_HAntes do analisador, o que ele produz. A árvore sintática abstrata não é a árvore de derivação, e a diferença é o que fica de fora: nada de ponto e vírgula, nada de parênteses, nada das variáveis auxiliares que as transformações da tarefa 1 criaram.
Decidir o que ela carrega é decisão de projeto com consequência nos módulos 12 a 14, que vão percorrê-la. Guardei a posição em todo nó, porque a análise semântica precisa reportar erro em algum lugar, e sem posição a mensagem seria inútil. E guardei o tipo como enumerado, porque os percursos seguintes vão despachar sobre ele.
O nó é uniforme, com marcador de tipo, em vez de hierarquia de classes com despacho virtual. A troca é consciente e está comentada: os percursos vão decidir sobre o tipo de qualquer forma, e o nó uniforme mantém curtos o código de impressão e o de travessia. O custo é que a estrutura não impede um nó de carregar filhos que não fazem sentido para o seu tipo — risco que o construtor único, usado por todo o analisador, mantém sob controle.
10_parser.cpp
#include "10_parser.h"
#include <set>
#include <utility>
namespace peneira {
namespace {
bool ehOperadorRelacional(const std::string& lexema) {
static const std::set<std::string> relacionais{"<", ">", "==",
"!=", ">=", "<="};
return relacionais.count(lexema) > 0;
}
} // namespace
AnalisadorSintatico::AnalisadorSintatico(const SourceFile& fonte,
DiagnosticBag& diagnosticos)
: fonte_(fonte), diagnosticos_(diagnosticos), lexer_(fonte, diagnosticos) {
atual_ = lexer_.proximo();
}
const SimboloLexico& AnalisadorSintatico::atual() const noexcept {
return atual_;
}
bool AnalisadorSintatico::ehCategoria(Categoria c) const noexcept {
return atual_.categoria == c;
}
bool AnalisadorSintatico::ehLexema(const std::string& lexema) const noexcept {
return atual_.lexema == lexema;
}
void AnalisadorSintatico::avancar() {
if (atual_.categoria != Categoria::FimDeArquivo) {
atual_ = lexer_.proximo();
++consumidos_;
}
}
std::size_t AnalisadorSintatico::errosSintaticos() const noexcept {
return erros_;
}
void AnalisadorSintatico::erro(const std::string& mensagem) {
// Enquanto estamos recuperando de um erro anterior, não reportamos os
// seguintes. É o que impede a cascata: um ponto e vírgula esquecido
// costuma provocar meia dúzia de erros derivados, e só o primeiro
// aponta a causa.
if (emRecuperacao_) {
return;
}
++erros_;
emRecuperacao_ = true;
const std::string encontrado =
atual_.categoria == Categoria::FimDeArquivo
? std::string("fim do arquivo")
: ("\"" + atual_.lexema + "\"");
diagnosticos_.error(atual_.posicao, mensagem + ", encontrado " + encontrado);
}
void AnalisadorSintatico::sincronizar() {
// Modo pânico com dois critérios de parada, e o segundo é o que faz a
// diferença.
//
// O primeiro é o delimitador de fim de construção — ponto e vírgula ou
// chave —, consumido junto para que a próxima construção comece limpa.
//
// O segundo é a palavra que pode INICIAR uma construção nova: `pattern`,
// `rule` e `on`. Sem ele, um erro numa declaração faz o descarte engolir
// tudo até o próximo ponto e vírgula — que pode estar lá dentro do bloco
// seguinte, levando junto uma construção inteira que estava correta. Foi
// exatamente o que aconteceu na primeira versão: um `=` faltando na linha
// 2 apagou o bloco de regra da linha 3, e o segundo erro reportado
// apontava para o lugar errado.
while (atual_.categoria != Categoria::FimDeArquivo) {
if (atual_.categoria == Categoria::PalavraReservada &&
(atual_.lexema == "pattern" || atual_.lexema == "rule" ||
atual_.lexema == "on")) {
break; // não consome: a construção nova começa aqui
}
// Os dois delimitadores param o descarte, e por motivos diferentes.
//
// O ponto e vírgula ENCERRA a construção em que o erro ocorreu, então
// é consumido junto: quem chamou já não precisa dele.
//
// A chave de fechamento pertence ao bloco de FORA, e quem chamou
// precisa vê-la para saber que o bloco terminou. Consumi-la aqui faria
// o bloco ficar sem fechamento e geraria um erro derivado apontando
// para a construção seguinte — que foi exatamente o sintoma observado
// antes desta distinção existir.
if (atual_.categoria == Categoria::Pontuacao && atual_.lexema == ";") {
avancar();
break;
}
if (atual_.categoria == Categoria::Pontuacao && atual_.lexema == "}") {
break;
}
avancar();
}
emRecuperacao_ = false;
}
std::string AnalisadorSintatico::consumirLexema(const std::string& lexema,
const std::string& contexto) {
if (ehLexema(lexema)) {
const std::string consumido = atual_.lexema;
avancar();
return consumido;
}
erro("esperava \"" + lexema + "\" " + contexto);
return std::string();
}
std::string AnalisadorSintatico::consumirCategoria(Categoria c,
const std::string& nome,
const std::string& contexto) {
if (ehCategoria(c)) {
const std::string consumido =
(c == Categoria::Texto || c == Categoria::Padrao) ? atual_.conteudo
: atual_.lexema;
avancar();
return consumido;
}
erro("esperava " + nome + " " + contexto);
return std::string();
}
AstPtr AnalisadorSintatico::analisar() { return programa(); }
AstPtr AnalisadorSintatico::programa() {
AstPtr raiz = criarNo(TipoAst::Programa, atual_.posicao);
while (!ehCategoria(Categoria::FimDeArquivo)) {
const std::size_t antes = erros_;
AstPtr d = declaracao();
// O teste precisa ser feito ANTES de mover: depois do move, `d` é
// nulo, e verificar `!d` em seguida acusaria erro em toda declaração
// bem-sucedida. Guardar o resultado numa variável separada é o que
// torna a ordem irrelevante.
const bool reconheceu = d != nullptr;
if (reconheceu) {
raiz->filhos.push_back(std::move(d));
}
const std::size_t marcaAntes = consumidos_;
if (erros_ > antes) {
sincronizar();
} else if (!reconheceu) {
erro("esperava uma declaracao de padrao ou um bloco de regra");
sincronizar();
}
// Garantia de progresso. A sincronização pode parar sem consumir nada
// — é o caso quando ela encontra logo de cara uma palavra que inicia
// construção. Se a iteração inteira não consumiu símbolo algum,
// forçamos um avanço, porque repetir a mesma tentativa daria o mesmo
// resultado indefinidamente.
if (!reconheceu && consumidos_ == marcaAntes) {
avancar();
}
}
return raiz;
}
AstPtr AnalisadorSintatico::declaracao() {
// A escolha entre as duas alternativas usa UM símbolo de antecipação, que
// é exatamente a adivinhação que o autômato de pilha do módulo 9 tinha de
// fazer às cegas. Aqui ela é decidida.
if (ehLexema("pattern")) {
return declPadrao();
}
if (ehLexema("rule")) {
return blocoRegra();
}
return nullptr;
}
AstPtr AnalisadorSintatico::declPadrao() {
const Position inicio = atual_.posicao;
consumirLexema("pattern", "no inicio da declaracao de padrao");
const std::string nome =
consumirCategoria(Categoria::Identificador, "o nome do padrao",
"depois de \"pattern\"");
consumirLexema("=", "depois do nome do padrao");
const std::string padrao = consumirCategoria(
Categoria::Padrao, "uma expressao entre barras", "depois do \"=\"");
consumirLexema(";", "no fim da declaracao de padrao");
return criarNo(TipoAst::DeclPadrao, inicio, nome, padrao);
}
AstPtr AnalisadorSintatico::blocoRegra() {
const Position inicio = atual_.posicao;
consumirLexema("rule", "no inicio do bloco de regra");
consumirLexema("{", "depois de \"rule\"");
AstPtr bloco = criarNo(TipoAst::BlocoRegra, inicio);
while (!ehCategoria(Categoria::FimDeArquivo) && !ehLexema("}")) {
// Uma ação só pode começar por "on". Encontrar outra coisa aqui
// significa que o bloco acabou mal — sair e deixar o nível de cima
// tratar é melhor que insistir dentro de um bloco que já se perdeu.
if (!ehLexema("on")) {
erro("esperava \"on\" ou \"}\" dentro do bloco de regra");
break;
}
const std::size_t antes = erros_;
const std::size_t marcaAntes = consumidos_;
AstPtr a = acao();
if (a) {
bloco->filhos.push_back(std::move(a));
}
if (erros_ > antes) {
sincronizar();
}
if (consumidos_ == marcaAntes) {
avancar();
}
}
consumirLexema("}", "no fim do bloco de regra");
return bloco;
}
AstPtr AnalisadorSintatico::acao() {
const Position inicio = atual_.posicao;
consumirLexema("on", "no inicio da acao");
const std::string padrao = consumirCategoria(
Categoria::Identificador, "o nome do padrao", "depois de \"on\"");
consumirLexema("(", "depois do nome do padrao");
const std::string ligacao =
consumirCategoria(Categoria::Identificador, "a variavel de ligacao",
"dentro dos parenteses");
consumirLexema(")", "depois da variavel de ligacao");
AstPtr no = criarNo(TipoAst::Acao, inicio, padrao, ligacao);
// Aqui está a fatoração à esquerda em ação. As duas produções de `acao`
// compartilhavam `on ID ( ID )`, e a escolha entre elas só é possível
// DEPOIS do prefixo comum — que é precisamente o que a fatoração formaliza.
// No código, a escolha é este `if`.
if (ehLexema("where")) {
avancar();
no->filhos.push_back(expressao());
} else {
no->filhos.push_back(nullptr); // sem condição
}
consumirLexema("=>", "antes de \"emit\"");
const Position posEmissao = atual_.posicao;
consumirLexema("emit", "depois de \"=>\"");
consumirLexema("(", "depois de \"emit\"");
const std::string rotulo = consumirCategoria(
Categoria::Texto, "o rotulo entre aspas", "dentro de \"emit\"");
consumirLexema(",", "depois do rotulo");
AstPtr emissao = criarNo(TipoAst::Emissao, posEmissao, rotulo);
emissao->filhos.push_back(expressao());
consumirLexema(")", "no fim de \"emit\"");
consumirLexema(";", "no fim da acao");
no->filhos.push_back(std::move(emissao));
return no;
}
AstPtr AnalisadorSintatico::expressao() {
// AQUI SE PAGA A DÍVIDA DO MÓDULO 9.
//
// A gramática original tinha `expr -> expr or exprE`, recursão à esquerda,
// que dava associatividade à esquerda de graça. A eliminação transformou
// isso em `expr -> exprE expr'` com `expr' -> or exprE expr' | e`, que é
// recursão à DIREITA — e uma implementação ingênua produziria árvores
// agrupadas à direita.
//
// O laço abaixo reconstrói a associatividade original: cada nova operação
// recebe como filho esquerdo a árvore acumulada até aqui. É a razão de
// este ser um laço, e não uma chamada recursiva.
AstPtr esquerda = expressaoE();
while (ehLexema("or")) {
const Position pos = atual_.posicao;
avancar();
AstPtr direita = expressaoE();
AstPtr no = criarNo(TipoAst::Ou, pos);
no->filhos.push_back(std::move(esquerda));
no->filhos.push_back(std::move(direita));
esquerda = std::move(no);
}
return esquerda;
}
AstPtr AnalisadorSintatico::expressaoE() {
AstPtr esquerda = comparacao();
while (ehLexema("and")) {
const Position pos = atual_.posicao;
avancar();
AstPtr direita = comparacao();
AstPtr no = criarNo(TipoAst::E, pos);
no->filhos.push_back(std::move(esquerda));
no->filhos.push_back(std::move(direita));
esquerda = std::move(no);
}
return esquerda;
}
AstPtr AnalisadorSintatico::comparacao() {
AstPtr esquerda = primaria();
// Sem laço, de propósito: a gramática não permite `a > b > c`, e usar `if`
// em vez de `while` é o que faz o analisador recusar em vez de aceitar.
if (ehCategoria(Categoria::Pontuacao) && ehOperadorRelacional(atual_.lexema)) {
const Position pos = atual_.posicao;
const std::string operador = atual_.lexema;
avancar();
AstPtr direita = primaria();
AstPtr no = criarNo(TipoAst::Comparacao, pos, operador);
no->filhos.push_back(std::move(esquerda));
no->filhos.push_back(std::move(direita));
return no;
}
return esquerda;
}
AstPtr AnalisadorSintatico::primaria() {
const Position pos = atual_.posicao;
if (ehLexema("value")) {
avancar();
consumirLexema("(", "depois de \"value\"");
const std::string nome = consumirCategoria(
Categoria::Identificador, "a variavel de ligacao",
"dentro de \"value\"");
consumirLexema(")", "no fim de \"value\"");
return criarNo(TipoAst::ValorDe, pos, nome);
}
if (ehLexema("(")) {
avancar();
AstPtr dentro = expressao();
consumirLexema(")", "fechando o agrupamento");
return dentro;
}
if (ehCategoria(Categoria::Identificador)) {
const std::string nome = atual_.lexema;
avancar();
return criarNo(TipoAst::Referencia, pos, nome);
}
if (ehCategoria(Categoria::Numero)) {
AstPtr no = criarNo(TipoAst::LiteralNumero, pos, atual_.lexema);
no->numero = atual_.valor;
avancar();
return no;
}
if (ehCategoria(Categoria::Texto)) {
const std::string conteudo = atual_.conteudo;
avancar();
return criarNo(TipoAst::LiteralTexto, pos, conteudo);
}
erro("esperava um nome, numero, texto, \"value\" ou \"(\"");
return criarNo(TipoAst::Referencia, pos, "<erro>");
}
AstPtr analisarArquivo(const SourceFile& arquivo, DiagnosticBag& diagnosticos,
std::size_t& erros) {
AnalisadorSintatico parser(arquivo, diagnosticos);
AstPtr raiz = parser.analisar();
erros = parser.errosSintaticos();
return raiz;
}
} // namespace peneiraUma função por variável da gramática preparada, na mesma ordem em que elas aparecem. É a realização concreta do autômato de pilha do módulo 9: a pilha de chamadas do programa é a pilha do autômato, e cada retorno de função é um símbolo saindo do topo. Quem fez o traçado manual do módulo 9 reconhece a estrutura.
Rodando sobre o programa de exemplo:
Programa [2:1]
DeclPadrao "email" ([a-z0-9._]+@[a-z]+\.[a-z]+) [2:1]
DeclPadrao "numero" (-?[0-9]+(\.[0-9]+)?) [3:1]
BlocoRegra [5:1]
Acao "email" (e) [6:5]
Emissao "contato" [6:43]
Referencia "e" [6:59]
Acao "numero" (n) [7:5]
Comparacao ">" [7:33]
ValorDe "n" [7:24]
LiteralNumero "100" 100 [7:35]
Emissao "grande" [7:43]
Referencia "n" [7:58]Treze nós para quarenta e seis terminais lidos, zero erros. A diferença não é perda: os trinta e três terminais que sumiram são pontuação, parênteses e palavras reservadas, que a árvore de derivação concreta guardaria e que nenhuma fase seguinte precisa.
1.4.1 A dívida do módulo 9, paga
O módulo 9 registrou que a eliminação da recursão à esquerda troca associatividade à esquerda por recursão à direita, e que a associatividade teria de ser reconstruída no analisador. É o que o laço em expressao faz: cada nova operação recebe como filho esquerdo a árvore acumulada até ali.
Sobre três or encadeados:
Ou
Ou
Comparacao ">" (value(v) > 1)
Comparacao ">" (value(v) > 2)
Comparacao ">" (value(v) > 3)O Ou mais externo tem outro Ou como filho esquerdo — agrupamento (a or b) or c, que é o que a recursão à esquerda da gramática original garantia. Uma implementação recursiva ingênua produziria a or (b or c): mesma linguagem, árvore diferente, semântica diferente no módulo 12.
É por isso que ali é um laço e não uma chamada recursiva, e é a razão de o comentário mais longo do arquivo estar nessa função.
Repare também que comparacao usa if e não while. A gramática não permite a > b > c, e a diferença entre as duas palavras-chave é exatamente o que faz o analisador recusar em vez de aceitar.
Dois defeitos que só a execução revelou.
O primeiro foi uso após movimento. Eu escrevia if (d) filhos.push_back(std::move(d)); e, logo abaixo, if (!d) erro(...). Depois do movimento, o ponteiro é nulo — então toda declaração bem-sucedida disparava um erro falso, e a recuperação subsequente engolia a declaração seguinte. O sintoma era estranho: o analisador reportava “esperava uma declaração” apontando para a palavra pattern, que é justamente o que ele esperava. A correção é guardar o resultado do teste numa variável antes de mover.
O segundo foi um laço que não progride. Ao melhorar a sincronização para parar em palavras que iniciam construção — sem consumi-las —, criei o caso em que a recuperação retorna sem ter avançado, e o laço que a chamou tenta de novo, indefinidamente. O programa travou. A correção foi um contador de símbolos consumidos: se uma iteração inteira não consumiu nada, força-se um avanço.
Os dois são erros que qualquer grupo vai cometer, e nenhum dos dois apareceria em revisão de código.
1.5 Tarefa 4: Recuperação de erros
A atividade — recuperar-se de erros sintáticos, continuando a análise, com o critério de qualidade da mensagem.
O critério é o do módulo 7, agora mais difícil de cumprir: um erro real vale mais que dez derivados. No analisador léxico bastava coalescer caracteres inválidos; aqui, um ponto e vírgula esquecido pode desalinhar o resto do arquivo.
Duas peças sustentam a solução. A supressão durante a recuperação faz com que, enquanto o analisador se reorganiza, os erros seguintes não sejam reportados — só o primeiro aponta a causa. E o modo pânico descarta símbolos até um ponto em que faça sentido retomar.
O que define a qualidade é a escolha dos pontos de retomada, e ela me custou duas iterações.
A primeira versão parava em ponto e vírgula ou chave de fechamento. Parecia razoável e produzia isto: um = faltando na linha 2 fazia o descarte correr até o ponto e vírgula seguinte — que estava dentro do bloco de regra da linha 3 —, apagando um bloco inteiro que estava correto. O segundo erro reportado apontava para o lugar errado.
A correção foi acrescentar um segundo critério de parada: as palavras que iniciam construção, pattern, rule e on, param o descarte sem serem consumidas. Foi essa mudança que criou o laço infinito descrito acima, e que exigiu a garantia de progresso.
E restou uma terceira sutileza. Ao parar num delimitador, os dois casos precisam de tratamento diferente: o ponto e vírgula encerra a construção em que o erro ocorreu e é consumido junto; a chave de fechamento pertence ao bloco de fora, e quem chamou precisa vê-la para saber que o bloco terminou. Consumi-la produzia um erro derivado apontando para a construção seguinte.
Com as três correções, sobre uma entrada com dois defeitos:
erros.pen:2:14: erro: esperava "=" depois do nome do padrao, encontrado "/[0-9]+/"
pattern ruim /[0-9]+/;
^
erros.pen:3:30: erro: esperava "," depois do rotulo, encontrado "v"
rule { on bom(v) => emit("a" v); }
^
erros reportados: 2
declaracoes recuperadas: 4Dois erros para dois defeitos, cada um apontando exatamente o símbolo que falta, e as quatro declarações do arquivo recuperadas — inclusive a que vinha depois do bloco com problema.
Onde é fácil errar aqui. Medir a qualidade da recuperação pela contagem de erros. Duas mensagens é melhor que dez, mas o que importa é se elas apontam os defeitos certos. A primeira versão deste analisador também reportava dois, e um deles estava errado. O teste honesto é contar defeitos reais na entrada e conferir se há uma mensagem para cada, no lugar de cada.
1.6 Tarefa 5: O front-end completo
A atividade — demonstrar o front-end ponta a ponta, do texto de entrada à árvore.
arquivo: 257 caracteres, 9 linhas
erros lexicos: 0
erros sintaticos: 0
nos na arvore: 13
terminais lidos: 46
declaracoes de padrao: 2, blocos de regra: 1Duzentos e cinquenta e sete caracteres viram quarenta e seis símbolos, que viram treze nós. Cada etapa descarta o que a seguinte não precisa: o analisador léxico descarta espaço e comentário, o sintático descarta pontuação e estrutura auxiliar.
O que sobra é a árvore que os módulos 12 a 14 vão consumir — e vale notar que a estrutura dela já antecipa o que eles farão. O nó de ação carrega o padrão referenciado e a variável de ligação, que o módulo 12 vai verificar contra a tabela de símbolos. O nó de emissão carrega o rótulo, que o módulo 14 vai colocar no objeto gerado. As decisões de forma tomadas aqui são consumidas lá.
Como verificar. O programa de exemplo tem de passar com zero erros léxicos e zero sintáticos, e a contagem de declarações precisa bater com o que está escrito no arquivo — dois padrões e um bloco. Foi esse último teste que denunciou o defeito de uso após movimento: a contagem dizia um padrão onde havia dois.
1.7 Referência teórica: o analisador dirigido por tabela
O módulo apresenta as duas realizações do método descendente, e implementei apenas uma. Vale a comparação, porque a escolha não é óbvia.
A tabela existe no projeto — foi construída na tarefa 2 e é ela que prova a condição LL(1). O que não escrevi é o laço que a executa com pilha explícita, empurrando e retirando símbolos em vez de usar chamadas de função.
As duas realizações reconhecem exatamente as mesmas entradas. A dirigida por tabela é mais compacta, e é a forma que um gerador produz, porque gerar uma tabela é mais fácil que gerar código. Em compensação, ela é opaca: quando algo dá errado, o que se depura é o conteúdo de uma matriz.
A recursiva tem a propriedade que decidiu a escolha aqui: a estrutura do código espelha a estrutura da gramática. Cada variável tem uma função com o nome dela, e ler as duas lado a lado é imediato. Para um projeto didático, em que o código é lido muito mais vezes do que executado, isso vale mais do que compacidade. E há um ganho prático: mensagens de erro específicas por contexto, como “esperava = depois do nome do padrão”, saem naturalmente na versão recursiva e exigiriam uma tabela paralela de mensagens na outra.
Não escrever o laço dirigido por tabela é decisão consciente, e não lacuna: ele reconheceria a mesma linguagem e produziria mensagens piores.
1.8 Verificação da entrega consolidada
| Item | Como conferir | Estado nesta referência |
|---|---|---|
| Recursão à esquerda eliminada | Nenhuma produção começa pela própria variável | Duas variáveis transformadas |
| Recursão indireta | Detecção executada, não suposta | Nenhuma encontrada |
| Fatoração | Nenhum par de produções com prefixo comum | Quatro fatorações, a maior de 4 símbolos |
| Transformações registradas | Uma linha por transformação, com a causa | Seis registros |
| Conjuntos calculados | Primeiros e seguidores, com anuláveis tratados | Cinco variáveis anuláveis |
| Condição LL(1) | Tabela sem conflito | 49 células, 0 conflitos |
| Conflitos interpretados | Comparação com a gramática não preparada | 19 conflitos, agrupados por causa |
| Analisador funcionando | Programa de exemplo vira árvore | 13 nós, 0 erros |
| Associatividade preservada | Três or agrupam à esquerda |
Confirmado na árvore |
| Recuperação sem cascata | Um erro por defeito, no lugar certo | 2 defeitos, 2 mensagens corretas |
| Front-end ponta a ponta | Texto a árvore, contagens conferidas | 257 caracteres, 46 símbolos, 13 nós |
| Código compila limpo | Nenhum aviso sob o modo estrito | Atende, verificado por compilação e execução |
O que quero deixar registrado sobre este marco é o custo real dele. As cinco tarefas somam menos de mil linhas de código, e três defeitos passaram por elas — dois de programação e um de projeto. Nenhum foi encontrado relendo; todos apareceram quando a saída foi comparada com o que ela deveria ser. Um grupo que implemente este módulo sem rodar contra entradas com defeito deliberado vai entregar um analisador que parece funcionar, e o módulo 12 vai receber árvores erradas sem saber.
O front-end está pronto. Do texto à árvore, com posição em cada nó e recuperação que aponta o lugar certo. O que vem a seguir não é mais sobre forma: é sobre o que o programa significa.