Módulo 02: Projeto do Professor — Da Cadeia à Expressão Regular, e a Especificação Léxica 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. Use como modelo do que a sua especificação deve parecer — as categorias da sua linguagem são outras, e as decisões sobre elas serão suas.
Visão Geral do Módulo 02
O módulo 2 pede uma coisa só do grupo, e ela não tem código: especificar as categorias léxicas da própria linguagem em notação de expressões regulares, com os conjuntos de cadeias que devem ser aceitas e rejeitadas por cada uma. É uma entrega de documento, e é a primeira vez que a intuição do módulo anterior precisa virar precisão.
Só que o projeto do professor tem um segundo dever, além de resolver a atividade: ele é a fonte única de código do módulo, e precisa dar corpo executável a toda a teoria apresentada. E a teoria deste módulo é implementável quase inteira — operações sobre cadeias, operações sobre linguagens, a sintaxe das expressões regulares e a sua semântica definida por indução. Nada disso aparece no compilador da Peneira ainda, mas tudo isso pode ser rodado, e rodar muda o entendimento.
Vamos então resolver a atividade e, em torno dela, construir o ferramental que torna a teoria conferível. Começo pelas cadeias, subo para as linguagens, chego às expressões regulares com a sua semântica, e só então escrevo a especificação léxica da Peneira — que é a entrega propriamente dita. A ordem não é arbitrária: a especificação usa o vocabulário construído antes dela.
Uma escolha de projeto atravessa o módulo e vale antecipar. Tudo que representa linguagem aqui é finito e limitado por comprimento. O fecho de Kleene de um conjunto não vazio é infinito, e não existe estrutura de dados que o guarde por extensão. O que fazemos é gerar a fatia até um comprimento dado. Isso é aproximação de demonstração, não implementação do conceito — e é exatamente a limitação que o módulo 3 resolve, quando o autômato aparece e passa a representar o conjunto infinito em espaço finito. Deixar essa insuficiência visível agora é o que torna o autômato uma resposta, e não uma novidade arbitrária.
Tarefa 1: A especificação léxica da Peneira
A atividade — identificar as categorias de símbolos léxicos da linguagem e descrever cada uma com precisão total, acompanhada dos corpora de aceitação e rejeição.
Comecei pela pergunta que a atividade realmente faz: quais são os tipos de “palavra” que um programa Peneira contém? Olhando o programa de exemplo do módulo 1, encontro nomes, números, textos entre aspas, padrões entre barras, sinais de pontuação e espaços. São seis categorias.
A decisão de projeto que tomei aqui, e que recomendo, foi escrever a especificação como código em vez de como prosa solta. A partir do módulo 7, é essa especificação que o analisador léxico consome. Se ela viver só num documento de texto, documento e implementação divergem na primeira alteração — e divergem em silêncio.
02_lexico.h
#ifndef PENEIRA_02_LEXICO_H
#define PENEIRA_02_LEXICO_H
#include <string>
#include <vector>
#include "02_cadeia.h"
#include "02_regex.h"
namespace peneira {
// Uma categoria léxica da linguagem Peneira: o nome, a expressão regular que
// a descreve (em notação textual) e os dois corpora de verificação.
//
// A especificação vive aqui, em código, e não apenas em prosa, porque a
// partir do módulo 7 é ela que o analisador léxico consome. Documento e
// implementação passam a ser a mesma coisa, e não podem divergir.
struct CategoriaLexica {
std::string nome;
std::string notacao;
std::string observacao;
std::vector<Cadeia> aceitas;
std::vector<Cadeia> rejeitadas;
};
// A especificação léxica completa da Peneira.
std::vector<CategoriaLexica> especificacaoLexica();
// Palavras reservadas: casam com a mesma forma de um identificador e precisam
// de desempate por prioridade. O tratamento é do módulo 7; a lista é fixada
// aqui, junto com o resto da especificação.
const std::vector<std::string>& palavrasReservadas();
// Duas categorias ganham também a árvore da expressão regular, e não só a
// notação textual: são as que servem de exemplo de trabalho nos módulos 3 a 5,
// quando a expressão vira autômato. As demais só ganham árvore no módulo 4,
// quando o analisador da notação existir e puder construí-las a partir do
// texto, em vez de à mão.
RegexPtr regexIdentificador();
RegexPtr regexNumero();
} // namespace peneira
#endif // PENEIRA_02_LEXICO_H
02_lexico.cpp
#include "02_lexico.h"
#include <utility>
namespace peneira {
const std::vector<std::string>& palavrasReservadas() {
static const std::vector<std::string> lista{
"pattern", "rule", "on", "where", "emit", "value", "and", "or",
};
return lista;
}
RegexPtr regexIdentificador() {
// letra ( letra | digito | _ )*
RegexPtr letra = faixaRegex('a', 'z');
RegexPtr digito = faixaRegex('0', '9');
RegexPtr sublinhado = simboloRegex('_');
RegexPtr corpo = uniaoRegex(uniaoRegex(letra, digito), std::move(sublinhado));
return concatRegex(faixaRegex('a', 'z'), estrelaRegex(std::move(corpo)));
}
RegexPtr regexNumero() {
// -? digito+ ( . digito+ )?
RegexPtr digito = faixaRegex('0', '9');
RegexPtr sinal = opcionalRegex(simboloRegex('-'));
RegexPtr inteiro = maisUmRegex(digito);
RegexPtr fracao = opcionalRegex(
concatRegex(simboloRegex('.'), maisUmRegex(faixaRegex('0', '9'))));
return concatRegex(concatRegex(std::move(sinal), std::move(inteiro)),
std::move(fracao));
}
std::vector<CategoriaLexica> especificacaoLexica() {
return std::vector<CategoriaLexica>{
CategoriaLexica{
"IDENTIFICADOR",
"[a-z][a-z0-9_]*",
"Começa por letra minúscula. Nomes de padrão e variáveis de "
"ligação. Casa também com as palavras reservadas, que são "
"desempatadas por prioridade no módulo 7.",
{"email", "numero", "e", "n2", "valor_alto", "pattern"},
{"", "2fast", "_oculto", "Email", "com-traco"},
},
CategoriaLexica{
"NUMERO",
"-?[0-9]+(\\.[0-9]+)?",
"Sinal opcional, parte inteira obrigatória, parte fracionária "
"opcional mas com pelo menos um dígito quando presente. Zeros à "
"esquerda são aceitos: rejeitá-los exigiria uma expressão bem "
"maior sem ganho para a linguagem.",
{"0", "100", "-5", "3.14", "-0.5", "007"},
{"", "-", ".5", "5.", "1.2.3", "1e10", "+3"},
},
CategoriaLexica{
"TEXTO",
"\"[^\"]*\"",
"Delimitado por aspas duplas, sem sequências de escape e sem "
"quebra de linha no interior. A ausência de escape é decisão de "
"projeto: evita um subanalisador dentro do analisador léxico.",
{"\"contato\"", "\"\"", "\"valor grande\""},
{"\"", "\"sem fim", "'aspas simples'"},
},
CategoriaLexica{
"PADRAO",
"/[^/]*/",
"O literal de padrão do usuário, delimitado por barras. O texto "
"interno é a mini-expressão regular que o módulo 4 vai analisar; "
"aqui ele é apenas reconhecido como um bloco opaco.",
{"/[a-z]+/", "//", "/-?[0-9]+/"},
{"/", "/sem fim", "[a-z]+"},
},
CategoriaLexica{
"PONTUACAO",
"\\(|\\)|\\{|\\}|;|,|=>|==|!=|>=|<=|=|>|<",
"Inclui os operadores de comparação. Os de dois caracteres criam "
"a necessidade do casamento mais longo: sem ele, \">=\" seria "
"lido como \">\" seguido de \"=\". Os parênteses vão escapados "
"porque na notação eles são agrupamento, não símbolo — a versão "
"anterior desta linha estava escrita como prosa legível, com "
"espaços entre as alternativas, e reconhecia a linguagem errada "
"em silêncio. O defeito só apareceu no módulo 7, quando o "
"analisador léxico passou a usar este autômato de verdade.",
{"=", "=>", ">=", "!=", ";", "{"},
{"", "=>>", "=!", "%"},
},
CategoriaLexica{
"ESPACO",
"[ \\t\\r\\n]+",
"Separa símbolos e é descartado pelo analisador léxico, sem virar "
"símbolo. Precisa existir na especificação mesmo sendo descartado: "
"é o que permite ao analisador saber onde um identificador termina.",
{" ", " ", "\t"},
{"", "a "},
},
};
}
} // namespace peneira
Cada categoria carrega quatro coisas: o nome, a notação, uma observação que registra a decisão de projeto por trás dela, e os dois corpora. A observação é a parte que mais me custou e a que mais vale, porque é onde ficam as escolhas que ninguém lembraria depois.
Vale percorrer as decisões que a especificação registra.
Identificadores começam por letra minúscula e podem conter dígitos e sublinhado depois. Não aceito maiúsculas, o que é uma restrição real da linguagem e não um descuido: reduz o alfabeto e me poupa de decidir se Email e email são o mesmo nome. Repare que a categoria casa também com as palavras reservadas — pattern é um identificador perfeitamente válido segundo essa expressão. Isso não é defeito: é a situação normal em qualquer linguagem, e o desempate por prioridade é assunto do módulo 7. Registrei o fato na observação para não parecer descuido quando alguém reler.
Números aceitam zeros à esquerda. Escrevi 007 no corpus de aceitação de propósito. Rejeitar zeros à esquerda exigiria uma expressão bem maior — algo como um dígito não zero seguido de dígitos, ou um zero isolado — e não traz ganho para esta linguagem. É uma decisão consciente de deixar a expressão simples, e ela está anotada.
Textos não têm sequências de escape. Essa é a decisão de escopo mais importante do módulo. Suportar \" dentro de um texto significa um pequeno analisador dentro do analisador léxico, com estado próprio. Cortei. A linguagem fica menos expressiva e o semestre fica viável.
O literal de padrão é reconhecido como bloco opaco. O conteúdo entre barras é a mini-expressão regular do usuário, mas o analisador léxico não olha para dentro dele — só reconhece que vai de barra a barra. Quem analisa o interior é o módulo 4. Separar as duas coisas é o que impede que o analisador léxico da linguagem e o analisador da notação de padrões virem um emaranhado só.
A pontuação inclui operadores de dois caracteres, e é isso que cria a necessidade do casamento mais longo. Anotei na observação: sem essa regra, >= seria lido como > seguido de =, e a condição where value(n) >= 100 seria analisada errado sem que nada acusasse. É o exemplo mais concreto que tenho para justificar, no módulo 7, uma regra que de outro modo pareceria detalhe.
Espaços são categoria de primeira classe, ainda que descartados. Estudantes costumam esquecê-los da especificação porque não viram símbolo. Mas é o espaço que informa onde um identificador termina, e ele precisa estar descrito.
Os corpora, e o que eles ainda não podem fazer
Cada categoria carrega cadeias que devem ser aceitas e cadeias que devem ser rejeitadas, com os casos de fronteira escolhidos deliberadamente por serem difíceis. Em números, incluí .5 e 5. entre as rejeitadas: as duas parecem números e nenhuma satisfaz a expressão, porque exijo pelo menos um dígito de cada lado do ponto. Incluí 1e10 porque notação científica é a extensão que todo mundo pede depois, e quero registrado que ela não faz parte da linguagem. Incluí +3 porque aceito sinal negativo e não positivo, o que é assimétrico e proposital.
E aqui está a limitação honesta desta entrega: os corpora ainda não são executáveis. Não existe reconhecedor. Eles são contrato, escrito antes da implementação e de propósito — no módulo 3 o primeiro reconhecedor aparece e passa a consumi-los, e no módulo 5 a ferramenta completa os verifica todos. Escrever o teste antes do código não é formalidade aqui: é o que me permitirá, daqui a três módulos, saber se o que construí está certo.
Onde é fácil errar aqui. Especificar por exemplo em vez de por expressão. É tentador escrever “números são coisas como 42 ou 3.14” e seguir em frente. Isso não é especificação, é ilustração, e desmonta no primeiro caso de fronteira. O teste que uso é perguntar de uma cadeia esquisita — -.5, digamos — se ela é aceita. Se eu preciso pensar, a expressão está imprecisa.
Como verificar. Rodando o subcomando que imprime a especificação, saem as seis categorias com notação, observação e os dois corpora. A saída é o documento de entrega, gerado a partir da mesma fonte que o compilador vai usar.
Referência teórica: operações sobre cadeias
O primeiro tópico do módulo é o vocabulário elementar — símbolo, alfabeto, cadeia — e as operações sobre cadeias. É material que parece simples demais para merecer código, e escrevi o código justamente porque ele não é.
02_cadeia.h
#ifndef PENEIRA_02_CADEIA_H
#define PENEIRA_02_CADEIA_H
#include <cstddef>
#include <string>
#include <vector>
namespace peneira {
// Uma cadeia é uma sequência finita de símbolos sobre um alfabeto. Usamos
// std::string como representação: os símbolos são caracteres, e a cadeia vazia
// é a string de comprimento zero.
using Cadeia = std::string;
// A cadeia vazia, que a teoria escreve como épsilon. Existe como função
// nomeada para que o código se leia como a definição formal.
const Cadeia& vazia();
Cadeia concatenar(const Cadeia& a, const Cadeia& b);
// Potência: a cadeia concatenada com ela mesma n vezes. Por definição,
// qualquer cadeia elevada a zero é a cadeia vazia — inclusive a própria
// cadeia vazia.
Cadeia potencia(const Cadeia& s, std::size_t n);
Cadeia reverso(const Cadeia& s);
// Prefixos, sufixos e subcadeias incluem a cadeia vazia e a própria cadeia,
// como manda a definição. Esquecer os extremos é o erro mais comum ao
// enumerá-los à mão.
std::vector<Cadeia> prefixos(const Cadeia& s);
std::vector<Cadeia> sufixos(const Cadeia& s);
std::vector<Cadeia> subcadeias(const Cadeia& s);
bool ehPrefixoDe(const Cadeia& possivel, const Cadeia& s);
bool ehSufixoDe(const Cadeia& possivel, const Cadeia& s);
} // namespace peneira
#endif // PENEIRA_02_CADEIA_H
02_cadeia.cpp
#include "02_cadeia.h"
#include <algorithm>
#include <set>
namespace peneira {
const Cadeia& vazia() {
static const Cadeia epsilon;
return epsilon;
}
Cadeia concatenar(const Cadeia& a, const Cadeia& b) { return a + b; }
Cadeia potencia(const Cadeia& s, std::size_t n) {
Cadeia resultado;
resultado.reserve(s.size() * n);
for (std::size_t i = 0; i < n; ++i) {
resultado += s;
}
return resultado;
}
Cadeia reverso(const Cadeia& s) {
Cadeia resultado(s);
std::reverse(resultado.begin(), resultado.end());
return resultado;
}
std::vector<Cadeia> prefixos(const Cadeia& s) {
std::vector<Cadeia> resultado;
resultado.reserve(s.size() + 1);
for (std::size_t i = 0; i <= s.size(); ++i) {
resultado.push_back(s.substr(0, i));
}
return resultado;
}
std::vector<Cadeia> sufixos(const Cadeia& s) {
std::vector<Cadeia> resultado;
resultado.reserve(s.size() + 1);
for (std::size_t i = 0; i <= s.size(); ++i) {
resultado.push_back(s.substr(i));
}
return resultado;
}
std::vector<Cadeia> subcadeias(const Cadeia& s) {
// Coletamos num conjunto para eliminar repetições: em "aaa" a subcadeia
// "aa" aparece em duas posições e é uma só. O conjunto também deixa a
// saída ordenada, o que torna a demonstração reproduzível.
std::set<Cadeia> distintas;
for (std::size_t inicio = 0; inicio <= s.size(); ++inicio) {
for (std::size_t fim = inicio; fim <= s.size(); ++fim) {
distintas.insert(s.substr(inicio, fim - inicio));
}
}
return std::vector<Cadeia>(distintas.begin(), distintas.end());
}
bool ehPrefixoDe(const Cadeia& possivel, const Cadeia& s) {
return possivel.size() <= s.size() &&
s.compare(0, possivel.size(), possivel) == 0;
}
bool ehSufixoDe(const Cadeia& possivel, const Cadeia& s) {
return possivel.size() <= s.size() &&
s.compare(s.size() - possivel.size(), possivel.size(), possivel) == 0;
}
} // namespace peneira
Antes das decisões de implementação, uma decisão de projeto que o código deixa implícita e convém explicitar: qual é o alfabeto da Peneira?
A teoria define cadeia como sequência finita de símbolos sobre um alfabeto, e o alfabeto precisa ser fixado antes de qualquer coisa. Adotei o conjunto de caracteres de um byte, e restringi na prática ao que as categorias léxicas usam — letras minúsculas, dígitos, sublinhado, os delimitadores e os sinais de pontuação. Represento cadeias com o tipo de texto da linguagem de implementação, o que significa que o alfabeto é o conjunto dos valores de um caractere.
A consequência dessa escolha aparece já aqui e cresce nos módulos seguintes. Um alfabeto de duzentos e cinquenta e seis símbolos torna a tabela de transição de um autômato larga, e é o que motivará, no módulo 3, representá-la por mapa esparso em vez de matriz densa. Se eu tivesse escolhido um alfabeto de texto multibyte, o número de símbolos deixaria de ser finito para efeitos práticos e a tabela de transição precisaria de outra estrutura inteira. É uma decisão pequena agora e cara de reverter depois, e por isso está tomada e anotada no módulo 2, não descoberta no módulo 5.
Duas decisões de implementação merecem explicação.
A cadeia vazia tem uma função nomeada em vez de aparecer como string literal vazia espalhada pelo código. Poderia ter escrito "" em toda parte e funcionaria. Nomeei porque o código passa a se ler como a definição formal, e porque a cadeia vazia é a fonte da maioria dos erros neste tópico — dar nome a ela força quem lê a notar que ela está ali.
Subcadeias são coletadas num conjunto ordenado. Em aaa, a subcadeia aa ocorre em duas posições e é uma só — conjunto não tem repetição. Enumerar por posição e devolver duplicatas é o erro clássico, e a estrutura de dados o impede por construção. O efeito colateral bom é que a saída sai ordenada e igual em toda execução, o que importa quando ela vai para um livro.
Rodando a demonstração sobre a cadeia abc, saem os quatro prefixos, os quatro sufixos e as sete subcadeias distintas. Repare que a cadeia vazia aparece em todas as três listas e que a própria abc aparece nas três também. São os dois extremos que somem quando alguém enumera à mão, e é por isso que a saída os mostra explicitamente.
Referência teórica: operações sobre linguagens
Subindo um nível: linguagens são conjuntos de cadeias, e as operações sobre elas são o próximo bloco do módulo.
02_linguagem.h
#ifndef PENEIRA_02_LINGUAGEM_H
#define PENEIRA_02_LINGUAGEM_H
#include <cstddef>
#include <set>
#include <string>
#include "02_cadeia.h"
namespace peneira {
// Uma linguagem é um conjunto de cadeias. Representamos com std::set por dois
// motivos: elimina repetições, como manda a definição de conjunto, e mantém
// ordem determinística, o que faz as demonstrações imprimirem sempre igual.
//
// Limitação assumida: só conseguimos representar linguagens FINITAS. As
// operações que produzem conjuntos infinitos (fecho) recebem um limite de
// comprimento e devolvem a fatia até ali. Isso é aproximação de demonstração,
// não implementação do conceito — o objeto infinito só ganha representação
// finita no módulo 3, quando o autômato entra.
using Linguagem = std::set<Cadeia>;
Linguagem uniao(const Linguagem& a, const Linguagem& b);
Linguagem intersecao(const Linguagem& a, const Linguagem& b);
Linguagem diferenca(const Linguagem& a, const Linguagem& b);
// Concatenação de linguagens: toda cadeia de `a` seguida de toda cadeia de
// `b`. O número de resultados é o produto dos tamanhos, e é por isso que o
// limite de comprimento existe.
Linguagem concatenacao(const Linguagem& a, const Linguagem& b,
std::size_t comprimentoMaximo);
Linguagem potencia(const Linguagem& a, std::size_t n,
std::size_t comprimentoMaximo);
// Fecho de Kleene: união de todas as potências, da zero em diante. Contém
// sempre a cadeia vazia — inclusive quando a linguagem de partida é vazia.
Linguagem fechoKleene(const Linguagem& a, std::size_t comprimentoMaximo);
// Fecho positivo: idem, mas a partir da potência um. Só contém a cadeia vazia
// se a linguagem de partida já a contiver.
Linguagem fechoPositivo(const Linguagem& a, std::size_t comprimentoMaximo);
// Formatação em notação de conjunto, com reticências quando há mais itens do
// que o limite pedido.
std::string formatar(const Linguagem& a, std::size_t maximoDeItens);
} // namespace peneira
#endif // PENEIRA_02_LINGUAGEM_H
02_linguagem.cpp
#include "02_linguagem.h"
#include <algorithm>
#include <iterator>
#include <sstream>
namespace peneira {
Linguagem uniao(const Linguagem& a, const Linguagem& b) {
Linguagem resultado(a);
resultado.insert(b.begin(), b.end());
return resultado;
}
Linguagem intersecao(const Linguagem& a, const Linguagem& b) {
Linguagem resultado;
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
std::inserter(resultado, resultado.end()));
return resultado;
}
Linguagem diferenca(const Linguagem& a, const Linguagem& b) {
Linguagem resultado;
std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
std::inserter(resultado, resultado.end()));
return resultado;
}
Linguagem concatenacao(const Linguagem& a, const Linguagem& b,
std::size_t comprimentoMaximo) {
Linguagem resultado;
for (const Cadeia& x : a) {
for (const Cadeia& y : b) {
if (x.size() + y.size() <= comprimentoMaximo) {
resultado.insert(x + y);
}
}
}
return resultado;
}
Linguagem potencia(const Linguagem& a, std::size_t n,
std::size_t comprimentoMaximo) {
// Potência zero é o conjunto que contém apenas a cadeia vazia — não é o
// conjunto vazio. Confundir os dois é o erro clássico deste tópico.
Linguagem resultado{vazia()};
for (std::size_t i = 0; i < n; ++i) {
resultado = concatenacao(resultado, a, comprimentoMaximo);
}
return resultado;
}
Linguagem fechoKleene(const Linguagem& a, std::size_t comprimentoMaximo) {
Linguagem resultado{vazia()};
// Iteramos até o ponto fixo: enquanto concatenar com `a` acrescentar
// cadeia nova dentro do limite, continuamos. O limite de comprimento é o
// que garante a terminação — sem ele, o laço não pararia para qualquer
// linguagem que contenha uma cadeia não vazia.
for (;;) {
const Linguagem novas = concatenacao(resultado, a, comprimentoMaximo);
const std::size_t antes = resultado.size();
resultado.insert(novas.begin(), novas.end());
if (resultado.size() == antes) {
break;
}
}
return resultado;
}
Linguagem fechoPositivo(const Linguagem& a, std::size_t comprimentoMaximo) {
return concatenacao(a, fechoKleene(a, comprimentoMaximo), comprimentoMaximo);
}
std::string formatar(const Linguagem& a, std::size_t maximoDeItens) {
if (a.empty()) {
return "{ }";
}
std::ostringstream saida;
saida << "{ ";
std::size_t escritos = 0;
for (const Cadeia& c : a) {
if (escritos == maximoDeItens) {
saida << ", ... (" << a.size() - escritos << " a mais)";
break;
}
if (escritos > 0) {
saida << ", ";
}
saida << (c.empty() ? std::string("<vazia>") : c);
++escritos;
}
saida << " }";
return saida.str();
}
} // namespace peneira
O fecho de Kleene é onde a implementação encontra o limite do que é representável, e resolvi assim: itero concatenando com a linguagem de partida até que nada de novo apareça dentro do limite de comprimento — um cálculo de ponto fixo. O limite não é detalhe de implementação, é o que garante a terminação. Sem ele, o laço não pararia para nenhuma linguagem que contenha uma cadeia não vazia, porque sempre haveria uma cadeia mais longa a produzir.
A demonstração exibe de propósito os dois casos que contrariam a intuição da turma. O primeiro é a potência zero de uma linguagem, que vale o conjunto contendo a cadeia vazia, e não o conjunto vazio. O segundo é o fecho de Kleene do conjunto vazio, que também contém a cadeia vazia — enquanto o fecho positivo do conjunto vazio é, esse sim, vazio. Rodando, sai literalmente:
fecho de Kleene do conjunto vazio = { <vazia> } (contém a cadeia vazia)
fecho positivo do conjunto vazio = { } (este sim é vazio)Discutir isso no quadro convence menos que mostrar o programa imprimindo. A diferença entre a linguagem vazia e a linguagem que contém apenas a cadeia vazia é a distinção mais escorregadia do módulo, e ela reaparece com consequência prática no módulo 4, quando as transições vazias entrarem.
Onde é fácil errar aqui. Ao implementar a concatenação de linguagens, esquecer o filtro de comprimento e deixar o conjunto crescer sem controle. Com duas linguagens de dez cadeias cada, uma concatenação produz cem resultados, e dentro do laço do fecho isso multiplica rápido. O filtro precisa estar na concatenação, não depois dela.
Referência teórica: expressões regulares e sua semântica
O tópico central do módulo. Uma expressão regular é definida por indução: três casos-base e três construtores. Representei exatamente isso.
02_regex.h
#ifndef PENEIRA_02_REGEX_H
#define PENEIRA_02_REGEX_H
#include <cstddef>
#include <cstdint>
#include <memory>
#include <string>
#include "02_linguagem.h"
namespace peneira {
// Sintaxe abstrata de uma expressão regular, na definição indutiva da teoria:
// os três casos-base (linguagem vazia, cadeia vazia, símbolo) e os três
// construtores (união, concatenação, estrela). Tudo o mais é açúcar sobre
// esses seis.
enum class TipoRegex : std::uint8_t {
Vazio, // denota a linguagem { }
Epsilon, // denota a linguagem { cadeia vazia }
Simbolo, // denota a linguagem { "c" }
Uniao,
Concatenacao,
Estrela,
};
struct Regex;
// Ponteiro compartilhado, e não exclusivo, porque as formas derivadas
// reaproveitam a mesma subárvore: `r+` é montado como `r` concatenado com
// `r*`, e o mesmo `r` aparece nos dois lados.
using RegexPtr = std::shared_ptr<const Regex>;
struct Regex {
TipoRegex tipo;
char simbolo; // significativo quando tipo == Simbolo
RegexPtr esquerda; // subexpressão; nula nos casos-base
RegexPtr direita; // segunda subexpressão; nula fora de União/Concatenação
};
RegexPtr vazioRegex();
RegexPtr epsilonRegex();
RegexPtr simboloRegex(char c);
RegexPtr uniaoRegex(RegexPtr a, RegexPtr b);
RegexPtr concatRegex(RegexPtr a, RegexPtr b);
RegexPtr estrelaRegex(RegexPtr a);
// Formas derivadas, definidas em termos das seis primitivas.
RegexPtr maisUmRegex(RegexPtr a); // r+ = r r*
RegexPtr opcionalRegex(RegexPtr a); // r? = r | epsilon
// Uma classe de caracteres é união de símbolos. Escrevemos assim para deixar
// explícito que `[a-z]` não é um construtor novo da teoria: é notação para
// vinte e seis uniões.
RegexPtr faixaRegex(char de, char ate);
RegexPtr conjuntoRegex(const std::string& simbolos);
// Notação textual da expressão, com parênteses apenas onde a precedência
// exige (estrela liga mais forte que concatenação, que liga mais forte que
// união).
std::string formatarRegex(const Regex& r);
// Semântica: a linguagem denotada pela expressão, calculada por indução sobre
// a estrutura — um caso para cada construtor, exatamente como a definição.
// Limitada por comprimento porque a linguagem pode ser infinita.
Linguagem linguagemDe(const Regex& r, std::size_t comprimentoMaximo);
// Compara duas expressões pelas linguagens que denotam, até o comprimento
// dado. Serve para exercitar as identidades algébricas.
//
// Atenção ao que isto é e ao que não é: concordar até um comprimento é
// evidência, não demonstração. Duas expressões podem coincidir até o
// comprimento dez e divergir no onze. A prova de equivalência vem no módulo 5,
// com a unicidade do autômato mínimo.
bool mesmaLinguagemAte(const Regex& a, const Regex& b,
std::size_t comprimentoMaximo);
} // namespace peneira
#endif // PENEIRA_02_REGEX_H
02_regex.cpp
#include "02_regex.h"
#include <sstream>
#include <utility>
namespace peneira {
namespace {
RegexPtr criar(TipoRegex tipo, char simbolo, RegexPtr esquerda, RegexPtr direita) {
Regex r{tipo, simbolo, std::move(esquerda), std::move(direita)};
return std::make_shared<const Regex>(std::move(r));
}
// Precedência para decidir parênteses: quanto maior, mais forte a ligação.
int precedencia(TipoRegex tipo) {
switch (tipo) {
case TipoRegex::Uniao:
return 1;
case TipoRegex::Concatenacao:
return 2;
case TipoRegex::Estrela:
return 3;
case TipoRegex::Vazio:
case TipoRegex::Epsilon:
case TipoRegex::Simbolo:
return 4;
}
return 4;
}
std::string comParenteses(const Regex& filho, int precedenciaDoPai) {
const std::string texto = formatarRegex(filho);
if (precedencia(filho.tipo) < precedenciaDoPai) {
return "(" + texto + ")";
}
return texto;
}
} // namespace
RegexPtr vazioRegex() { return criar(TipoRegex::Vazio, '\0', nullptr, nullptr); }
RegexPtr epsilonRegex() {
return criar(TipoRegex::Epsilon, '\0', nullptr, nullptr);
}
RegexPtr simboloRegex(char c) {
return criar(TipoRegex::Simbolo, c, nullptr, nullptr);
}
RegexPtr uniaoRegex(RegexPtr a, RegexPtr b) {
return criar(TipoRegex::Uniao, '\0', std::move(a), std::move(b));
}
RegexPtr concatRegex(RegexPtr a, RegexPtr b) {
return criar(TipoRegex::Concatenacao, '\0', std::move(a), std::move(b));
}
RegexPtr estrelaRegex(RegexPtr a) {
return criar(TipoRegex::Estrela, '\0', std::move(a), nullptr);
}
RegexPtr maisUmRegex(RegexPtr a) {
// A mesma subárvore aparece duas vezes; é o que motiva o ponteiro
// compartilhado em vez do exclusivo.
RegexPtr estrela = estrelaRegex(a);
return concatRegex(std::move(a), std::move(estrela));
}
RegexPtr opcionalRegex(RegexPtr a) {
return uniaoRegex(std::move(a), epsilonRegex());
}
RegexPtr faixaRegex(char de, char ate) {
RegexPtr resultado = simboloRegex(de);
for (char c = static_cast<char>(de + 1); c <= ate; ++c) {
resultado = uniaoRegex(std::move(resultado), simboloRegex(c));
}
return resultado;
}
RegexPtr conjuntoRegex(const std::string& simbolos) {
if (simbolos.empty()) {
return vazioRegex();
}
RegexPtr resultado = simboloRegex(simbolos[0]);
for (std::size_t i = 1; i < simbolos.size(); ++i) {
resultado = uniaoRegex(std::move(resultado), simboloRegex(simbolos[i]));
}
return resultado;
}
std::string formatarRegex(const Regex& r) {
switch (r.tipo) {
case TipoRegex::Vazio:
return "0";
case TipoRegex::Epsilon:
return "e";
case TipoRegex::Simbolo:
return std::string(1, r.simbolo);
case TipoRegex::Uniao:
return comParenteses(*r.esquerda, precedencia(TipoRegex::Uniao)) +
"|" +
comParenteses(*r.direita, precedencia(TipoRegex::Uniao));
case TipoRegex::Concatenacao:
return comParenteses(*r.esquerda,
precedencia(TipoRegex::Concatenacao)) +
comParenteses(*r.direita,
precedencia(TipoRegex::Concatenacao));
case TipoRegex::Estrela:
return comParenteses(*r.esquerda, precedencia(TipoRegex::Estrela)) +
"*";
}
return std::string();
}
Linguagem linguagemDe(const Regex& r, std::size_t comprimentoMaximo) {
// Um caso por construtor: a função é a definição indutiva transcrita.
switch (r.tipo) {
case TipoRegex::Vazio:
return Linguagem{};
case TipoRegex::Epsilon:
return Linguagem{vazia()};
case TipoRegex::Simbolo:
return Linguagem{std::string(1, r.simbolo)};
case TipoRegex::Uniao:
return uniao(linguagemDe(*r.esquerda, comprimentoMaximo),
linguagemDe(*r.direita, comprimentoMaximo));
case TipoRegex::Concatenacao:
return concatenacao(linguagemDe(*r.esquerda, comprimentoMaximo),
linguagemDe(*r.direita, comprimentoMaximo),
comprimentoMaximo);
case TipoRegex::Estrela:
return fechoKleene(linguagemDe(*r.esquerda, comprimentoMaximo),
comprimentoMaximo);
}
return Linguagem{};
}
bool mesmaLinguagemAte(const Regex& a, const Regex& b,
std::size_t comprimentoMaximo) {
return linguagemDe(a, comprimentoMaximo) ==
linguagemDe(b, comprimentoMaximo);
}
} // namespace peneira
Três pontos da implementação merecem comentário.
Só existem seis construtores. Linguagem vazia, cadeia vazia, símbolo, união, concatenação e estrela. Tudo o mais é açúcar: r+ é montado como r concatenado com r*, r? como r unido com a cadeia vazia, e uma classe como [a-z] como vinte e seis uniões. Escrever as formas derivadas em termos das primitivas, e não como casos novos do enumerado, é a decisão que mantém honesta a correspondência com a teoria — e ela se paga no módulo 4, quando a construção de Thompson precisar tratar apenas seis casos em vez de doze.
O ponteiro é compartilhado, e não exclusivo. Quando monto r+ como r seguido de r*, a mesma subárvore aparece nos dois lados. Com ponteiro exclusivo eu precisaria duplicar a árvore; com compartilhado, aponto duas vezes para a mesma. É uma das poucas situações em que o compartilhamento é a escolha certa por razão estrutural, e não por conveniência.
A função que calcula a linguagem denotada é a definição transcrita. Um caso para cada construtor, cada um devolvendo exatamente o que a definição diz: o conjunto vazio, o conjunto com a cadeia vazia, o conjunto com um símbolo, a união, a concatenação, o fecho. Quem ler essa função lado a lado com a definição do livro vai encontrar a mesma coisa em duas notações. Era esse o objetivo.
A demonstração exercita as identidades algébricas comparando as linguagens geradas. Rodando, sai:
(a|b)* == (a*b*)* : confere
a** == a* : confere
ab == ba : diverge (esperado: diverge)O terceiro caso está ali de propósito. Uma bateria de verificações em que tudo passa não prova que a verificação funciona — pode ser que ela sempre responda “confere”. Incluir um caso que deve falhar é o que dá confiança nos outros dois.
A ressalva que precisa ser dita em voz alta. Concordar até um comprimento dado é evidência, não demonstração. Duas expressões podem denotar linguagens que coincidem até o comprimento dez e divergem no onze, e este verificador diria “confere”. Deixei isso escrito no comentário do cabeçalho e impresso na saída da demonstração, porque é exatamente o tipo de conclusão apressada que um programa que funciona induz. A decisão de equivalência de verdade chega no módulo 5, com a unicidade do autômato mínimo — e é um dos motivos pelos quais aquele resultado importa.
Onde é fácil errar aqui. Ao formatar a expressão de volta para texto, esquecer os parênteses de precedência. Sem eles, a união de a com b, tudo sob estrela, imprimiria como a|b*, que é outra expressão. Resolvi com uma tabela de precedência e parentização condicional: o filho só ganha parênteses quando liga mais fraco que o pai. Verifiquei que (a|b)* imprime com os parênteses e que aa* imprime sem, que é o comportamento correto nos dois sentidos.
Tópicos deste módulo sem código de referência
Um tópico ficou sem implementação, e registro por quê.
A distinção entre a notação teórica e as notações das bibliotecas de programação é conceitual. As construções que as bibliotecas oferecem além da teoria — retrovisores, âncoras, olhares adiante — não são regulares, e implementá-las aqui seria implementar exatamente aquilo que a disciplina quer que o estudante reconheça como fora da classe. O que o código faz é o oposto e é mais útil: por só oferecer os seis construtores, ele torna a fronteira palpável. Quando alguém perguntar por que não dá para escrever um retrovisor com estas peças, a resposta está na ausência delas.
Verificação da entrega
| Item | Como conferir | Estado nesta referência |
|---|---|---|
| Categorias léxicas identificadas | Toda “palavra” do programa de exemplo cai em alguma categoria | Seis categorias, cobrindo o exemplo do módulo 1 |
| Notação precisa | Cadeia de fronteira é classificável sem hesitação | Atende; casos difíceis nos corpora |
| Corpus de aceitação | Casos típicos e de fronteira, por categoria | Entre três e seis por categoria |
| Corpus de rejeição | Casos que quase passam | Entre dois e sete por categoria |
| Decisões registradas | Cada escolha de escopo tem justificativa escrita | Uma observação por categoria |
| Código compila limpo | Sem nenhum aviso sob o modo estrito | Atende, verificado por compilação |
O que quero deixar registrado sobre esta entrega é que a parte avaliada — a especificação — não tem código, e que o código que a acompanha existe para tornar a teoria conferível, não para adiantar o compilador. Nenhuma linha escrita neste módulo faz parte do analisador léxico. Grupos que tentarem começar o analisador agora estarão implementando sobre uma teoria que ainda não estudaram: o autômato chega no módulo 3, e a construção que transforma expressão em autômato, no módulo 4.