flowchart LR
A["texto-fonte<br/>cadeia sobre o alfabeto"] --> B["análise léxica<br/>autômatos finitos"]
B --> C["sequência de símbolos<br/>categoria, lexema, posição"]
C --> D["análise sintática<br/>gramática livre de contexto"]
D --> E["árvore sintática"]
B -.-> F["diagnósticos coletados"]
B -.-> G["descartado:<br/>espaço e comentário"]
1 Módulo 07: Análise Léxica
Bem-vindo ao módulo em que a teoria vira produto. Não há nenhum algoritmo novo aqui — nenhum mesmo. O que se acrescenta é o que os teoremas não mencionam: como a fase seguinte pede um símbolo, o que fazer quando duas categorias casam a mesma entrada, para onde vai o espaço em branco, e o que dizer diante de um caractere que não pertence a lugar nenhum. É aí que mora a maior parte do esforço de um analisador léxico que funcione sobre arquivos de verdade.
1.1 O problema: o analisador que engoliu o ônibus
Imagina a cena. Você ligou o motor de autômatos que vinha construindo há vários módulos, escreveu o seu primeiro analisador léxico, testou a palavra reservada on e ela saiu como palavra reservada. Todos os testes passam.
Aí alguém escreve uma variável chamada onibus, e o seu analisador devolve a palavra reservada on seguida de um identificador ibus. A análise sintática reclama três símbolos adiante, com uma mensagem que não aponta a causa, e o usuário olha para um programa impecável sem entender nada.
Repara: nenhum autômato errou. O defeito estava na ordem em que duas convenções foram aplicadas, e essa ordem não está em teorema algum. Guarde o contraste: um erro na construção de subconjuntos aparece na primeira bateria de testes; um erro na regra de desempate atravessa o projeto escondido.
Este capítulo é o primeiro que não constrói teoria nova, e por isso convém ser explícito sobre o que ele pressupõe pronto — não como pré-requisito formal, mas como material que precisa estar fresco para que a leitura renda.
Pressuponho o vocabulário elementar: alfabeto, cadeia, linguagem como subconjunto de \Sigma^*, e a noção de que uma linguagem infinita precisa de descrição finita. Pressuponho a expressão regular como notação para esse fim, com os seus operadores de união, concatenação e fecho, e as formas derivadas que se montam sobre eles. Pressuponho o autômato finito determinístico como quíntupla, com função de transição total ou parcial, e a diferença entre parar por falta de transição e parar em estado não final.
Pressuponho, sobretudo, o percurso completo que liga a notação à máquina: a construção de Thompson, que converte a árvore da expressão regular em autômato não determinístico com transições vazias; a construção de subconjuntos, que o determiniza; e o refinamento de partições, que minimiza o determinístico. Esses três algoritmos são o motor que este capítulo vai embrulhar, e a leitura fica muito mais rica para quem consegue, ao ver uma tabela de transição, lembrar por qual dos três passos cada estado dela apareceu.
E pressuponho o resultado de impossibilidade — o lema do bombeamento e a demonstração de que a linguagem dos delimitadores balanceados não é regular. Ele reaparece aqui de forma inesperada, decidindo uma característica visível da linguagem que se constrói, e é o momento em que a teoria deixa de parecer preâmbulo.
O que não pressuponho é qualquer contato prévio com ferramentas de geração de analisadores léxicos. Elas aparecem no fim do capítulo, e aparecem no fim de propósito.
1.2 O que a fase faz, e por que existe sozinha
O analisador léxico recebe caracteres e devolve símbolos — verdadeiro, e não diz o que interessa, que é a mudança de natureza. Antes dele, o programa é um objeto sem estrutura interna, uma cadeia na qual nenhuma subcadeia tem privilégio sobre outra. Depois, é uma sequência de unidades com categoria, cujas fronteiras foram decididas em definitivo.
Formalmente, dado um alfabeto \Sigma e um conjunto finito C de categorias, a fase é uma função parcial
\Lambda : \Sigma^* \longrightarrow (C \times \Sigma^* \times \mathbb{N})^* \times D,
que leva o texto-fonte a uma sequência de triplas — categoria, lexema e posição de início — mais um conjunto D de diagnósticos. Há um compromisso escondido aí: o analisador não inventa e não reordena, porque todo lexema é trecho contíguo do original, na ordem em que aparece. O único direito dele é o de omitir.
Por que uma fase separada, se a gramática poderia descer até o caractere? Por três razões que se acumulam. Adequação de formalismo: a estrutura interna de identificadores e números é regular, reconhecível por autômato finito em tempo linear, enquanto a de um programa exige o formalismo caro. Legibilidade da gramática: ao nível do caractere, ela precisaria admitir espaço opcional entre cada par de símbolos, e vinte produções legíveis virariam vinte ilegíveis. E concentração de dependências: tudo que depende de conjunto de caracteres, codificação e fim de linha fica num componente só.
Pare e pense. Há linguagens em que um mesmo nome designa um tipo ou uma variável conforme tenha sido declarado antes, e o analisador léxico precisa consultar informação semântica para decidir a categoria — realimentação da terceira fase para a primeira. Que decisão de sintaxe obrigou a arquitetura inteira do compilador a ficar mais feia?
1.3 A interface: tudo de uma vez ou um por vez
Estabelecido que a fase existe, resta decidir como ela conversa com a seguinte. É a decisão de projeto mais consequente do módulo.
Varre o arquivo inteiro e entrega a lista de símbolos pronta — o mais simples de testar. O preço: memória proporcional ao arquivo, diagnóstico que só sai depois da varredura inteira, e o fim da análise léxica fixado antes do começo da análise sintática.
A fase seguinte pede o próximo símbolo e o analisador produz um, mantendo o estado da varredura entre chamadas. Logicamente as duas fases continuam distintas; fisicamente, as duas travessias do texto se fundem numa só. É a opção consagrada.
Memória é argumento circunstancial; latência é melhor, porque o erro sintático da terceira linha sai assim que a análise chega nele. O decisivo é o acoplamento temporal, e eu o aprendi do jeito caro: materializei tudo no meu primeiro analisador léxico, e meses depois, ao acrescentar uma construção que exigia a tabela de símbolos para decidir a categoria de um nome, descobri que a análise léxica já tinha terminado quando a informação passou a existir. Reescrevi a interface inteira, por erro de acoplamento no tempo.
sequenceDiagram
participant P as Análise sintática
participant L as Análise léxica
participant T as Texto carregado
P->>L: pede o próximo símbolo
L->>T: lê a partir do índice corrente
T-->>L: caracteres
L-->>P: símbolo com categoria, lexema e posição
P->>L: pede o próximo símbolo
L-->>P: símbolo de fim de entrada
P->>L: pede de novo, durante a recuperação
L-->>P: símbolo de fim de entrada outra vez
Pode existir, ao lado da principal, uma operação que devolva a lista inteira, ótima para demonstração e teste — desde que fique declaradamente secundária no próprio código, porque quem a adotar como caminho principal reintroduz o acoplamento que se quis evitar.
E vale dizer o que a fase promete não fazer: não verifica se a sequência forma um programa, porque um sinal de igual seguido de ponto e vírgula é lexicamente impecável; não sabe se um nome foi declarado; não verifica se um literal de quarenta dígitos cabe no tipo que o receberá; e não decide o que fazer com os erros, apenas registra e continua.
1.4 Padrão, lexema, símbolo e atributo
Agora o vocabulário, porque a confusão aqui é a fonte de mal-entendidos mais persistente do assunto. Um padrão é uma expressão regular que descreve uma classe de trechos equivalentes para a fase seguinte. Um lexema é uma cadeia concreta, ocorrência contígua no texto, pertencente à linguagem de algum padrão. Um símbolo léxico é o par formado pela categoria do padrão vencedor e pelos atributos daquele lexema. E um atributo é informação adicional de que alguma fase posterior vai precisar — entre elas, sempre, a posição.
A assimetria entre os quatro vale mais que as definições: o padrão vive na especificação e não aparece durante a varredura — o que aparece é o autômato que dele derivou —, o lexema vive no texto do usuário, o símbolo vive na comunicação entre fases, e o atributo vive pendurado no símbolo.
flowchart TD
P["padrão<br/>expressão regular na especificação"] -->|"compilado uma vez"| A["autômato da categoria"]
T["texto-fonte do usuário"] -->|"trecho contíguo"| L["lexema"]
A -->|"reconhece"| L
L --> S["símbolo léxico<br/>categoria mais atributos"]
S --> AT["atributos<br/>posição, valor numérico,<br/>miolo do literal"]
S -->|"atravessa a interface"| F["fase seguinte"]
Concretizando: com o padrão dos números e o trecho -3.14 no texto, o padrão é a expressão regular, o lexema é a cadeia de cinco caracteres, o símbolo é a categoria “número”, e um dos seus atributos é o valor numérico. Quatro objetos, quatro naturezas — e a conversa informal chama todos de “token”. A especificação léxica é uma sequência ordenada de pares categoria-padrão: duas especificações com os mesmos pares em ordens diferentes são diferentes, e reordenar regras é alteração semântica, não faxina de arquivo.
Uma pergunta que separa quem entendeu. Por que a categoria de espaço em branco precisa estar declarada na especificação, se ela nunca produz símbolo nenhum? A resposta não é “por organização”.
Sobre o atributo, o princípio cabe numa linha: carregue o que só a análise léxica sabe calcular barato. O valor numérico é o caso exemplar — no reconhecimento o texto do número está contíguo e delimitado, e converter é uma chamada; se não for feito ali, alguma fase adiante refará a delimitação, que é a definição de acoplamento ruim. O mesmo vale para o miolo de um literal de texto. Não carregue o que dependa de contexto sintático ou de declaração, nem campos “para o caso de precisar”.
E a posição não é opcional. Ela existe naturalmente num único lugar do compilador, que é aqui, no instante em que o índice do caractere é conhecido; depois o texto foi descartado e a árvore foi construída, e reconstruir a posição de um nó a partir do nada é impossível. O custo são alguns bytes e uma atribuição, e não conheço decisão com melhor relação custo-benefício num compilador.
1.5 As duas regras de desempate
Numa posição i do texto, vários autômatos podem aceitar prefixos de comprimentos diferentes, o mesmo autômato pode aceitar em vários comprimentos, e dois podem aceitar a mesma cadeia. A especificação, portanto, não determina sozinha a segmentação: ela é ambígua por construção, não por descuido, porque categorias léxicas se sobrepõem. Duas convenções externas resolvem, e tratam conflitos de naturezas diferentes — confundi-las é o erro conceitual mais comum do módulo.
O casamento mais longo resolve o conflito entre comprimentos diferentes: vence quem chegar mais longe. Definindo, para cada regra j,
m_j(i) = \max\{\, \ell \ge 1 \;\mid\; w[i \ldots i+\ell-1] \in L(r_j) \,\},
o lexema reconhecido é o trecho de comprimento M(i) = \max_j m_j(i). Esse máximo existe sempre que existe candidato: os comprimentos são inteiros positivos limitados por |w| - i, porque um lexema não ultrapassa o fim do texto. A demonstração é de duas linhas e ainda assim vale, porque explicita a hipótese que a sustenta — o texto é finito.
A alternativa oposta é implementável e inutilizável. Sob casamento mais curto, um operador de dois caracteres viraria dois símbolos e um identificador viraria vários de um caractere. A consequência para quem projeta linguagem: a leitura será sempre a mais longa, e não há como pedir a curta sem separar por espaço.
A definição é declarativa e não diz como computar. O mecanismo é o último aceite, e aqui mora o erro de implementação mais comum de todos. Cada autômato avança enquanto tiver transição, registrando a posição toda vez que passa por estado final; quando trava, o candidato é o último aceite registrado, não a posição de parada. Um autômato de número lendo 12. avança pelos dígitos, aceita, avança pelo ponto e trava: parou depois do ponto, aceitou pela última vez depois do 2, e o candidato correto é 12. Quem devolve a posição de parada produz um lexema que nem pertence à linguagem do padrão, e isso só aparece nas entradas que ninguém escreve nos primeiros testes. Os caracteres entre o último aceite e a parada são relidos depois: esse é o retrocesso.
Resolvido o comprimento, resta o empate. A regra de prioridade determina que, entre as regras que atingiram o comprimento máximo, vence a de menor índice na especificação. Juntas, as duas convenções tornam a segmentação uma função bem definida, e é isso que autoriza dizer que o analisador léxico é determinístico. Esse determinismo é outra coisa, completamente, do determinismo dos autômatos: quem funde os dois acredita que determinizar resolve o desempate, e não resolve.
flowchart TD
I["posição i do texto"] --> D{"trecho descartável?<br/>espaço ou comentário"}
D -->|"sim"| D2["consome e repete o teste"] --> D
D -->|"não"| R["roda cada autômato<br/>registrando o último aceite"]
R --> M{"algum aceitou?"}
M -->|"não"| E["erro léxico:<br/>coalesce a corrida inválida"]
M -->|"sim"| C["casamento mais longo:<br/>vence o maior comprimento"]
C --> Pr["prioridade:<br/>entre os empatados,<br/>a regra de menor índice"]
Pr --> S["emite o símbolo<br/>e avança para i mais M"]
E --> S2["registra o diagnóstico<br/>e continua a varredura"]
S2 --> I
S --> I
O caso que dá visibilidade à prioridade é universal: em praticamente toda linguagem, o padrão de identificador descreve uma linguagem que contém todas as palavras reservadas. Há duas maneiras de implementar a decisão.
Cada palavra reservada ganha o seu próprio padrão, antes do padrão de identificador, e a prioridade faz o resto. Usa só o mecanismo que já existe, e é o que os geradores incentivam. O preço: um autômato por palavra reservada, e a correção passa a depender da ordem das linhas — mover uma delas para baixo do identificador quebra a linguagem em silêncio.
Reconhece tudo como identificador e, depois de o casamento mais longo decidir o comprimento, consulta uma lista com o lexema inteiro; se estiver lá, reclassifica. O preço é uma consulta por identificador, praticamente constante com tabela de dispersão. O ganho é de acoplamento: as palavras reservadas ficam num lugar só e nenhuma reordenação de regras as afeta.
Eu prefiro a segunda, pelo acoplamento, e reconheço que é preferência, não teorema. Se usar um gerador, você adotará a primeira, e então avise em comentário que a ordem daquelas linhas é semanticamente significativa.
E agora o ponto que fecha a abertura: o casamento mais longo vem primeiro, a prioridade vem depois. Nessa ordem, e não na inversa. Se a implementação consultar a lista assim que os caracteres lidos formarem uma palavra dela, onibus produz on seguido de lixo; e se o laço retornar assim que uma regra de índice baixo aceitar, sem calcular o máximo global, o comportamento é idêntico. A prioridade se aplica entre os candidatos de comprimento máximo, nunca a qualquer aceitação.
Por que esse defeito sobrevive aos testes. Ele passa em todo caso com palavra reservada isolada, que é justamente o que a gente escreve ao testar palavras reservadas. Escreva hoje, de propósito, um caso com identificador prefixado por palavra reservada.
1.6 O que a teoria não menciona
Espaço em branco é um caractere como outro qualquer, e o tratamento especial que recebe é convenção da fase, não fato matemático. A distinção que importa é entre descartar — reconhecer o trecho, consumi-lo e não produzir símbolo — e ignorar, que seria não reconhecê-lo e é errado. O espaço precisa ser reconhecido porque é ele que define fronteiras: dois identificadores separados por espaço são dois lexemas porque o espaço interrompe o avanço do autômato de identificador. Aí está a resposta da pergunta que deixei atrás. E o “pular” tem de ser em laço, porque depois do espaço pode vir comentário e depois do comentário mais espaço.
Comentário parece trivialidade e não é: há uma decisão de projeto de linguagem escondida na escolha da forma, e quem a decide é um resultado de impossibilidade.
flowchart TD
C["forma do comentário<br/>a escolher no projeto da linguagem"] --> L["de linha"]
C --> B["de bloco não aninhável"]
C --> N["de bloco aninhável"]
L --> R["linguagem regular:<br/>cabe no motor de autômatos<br/>que você já tem"]
B --> R
N --> X["não regular pelo lema do bombeamento:<br/>exige um contador escrito à mão,<br/>fora do modelo"]
Comentário de linha é regular: a marca inicial seguida de qualquer sequência sem quebra de linha. De bloco não aninhável também é. Já o de bloco aninhável não é regular, pela demonstração do módulo anterior — reconhecer o equilíbrio entre n aberturas e n fechamentos exige contar, o número é ilimitado, e o lema do bombeamento fecha a porta. Aninhar custa, portanto, um contador escrito à mão, fora do modelo. É a primeira vez, num projeto de compilador, que um teorema de impossibilidade decide uma característica visível da linguagem, e não será a última. O ponto não é que aninhar seja ruim — sem aninhamento, comentar um bloco que já contém comentário produz resultado errado —, é que aninhar tem preço, e saber o preço permite decidir por consciência.
O fim do arquivo é o caso de borda que quase todo mundo trata mal na primeira vez, e o tratamento correto é curto: emita um símbolo de fim de entrada explícito, com categoria própria e posição no fim do texto — não devolva “nada”, não sinalize por valor especial, não lance exceção. A fase seguinte compara o símbolo corrente com o esperado, e comparar contra a ausência de coisa exige caso especial em toda comparação. Depois de emitido, chamadas seguintes devem continuar devolvendo o mesmo símbolo, porque a fase seguinte pode pedir mais de uma vez durante a recuperação de um erro.
Fecho com dois casos de borda de literais cujas respostas são opostas. Literal de texto sem fechamento pede tratamento específico, porque o genérico faz o autômato consumir o resto do arquivo e o conteúdo acabar analisado como código: reporte “literal de texto não encerrado” na posição da abertura e consuma até o fim da linha. Já um número com dois pontos decimais não pede nada — o autômato aceita até o primeiro ponto seguido de dígitos, para, e o segundo ponto vira pontuação; a sequência é lexicamente válida e sintaticamente inválida, e quem reclama é a fase seguinte.
1.7 Erro léxico: detectar, dizer e continuar
Ocorre erro léxico na posição i quando nenhuma regra admite casamento não vazio a partir de i — quando o texto contém ali algo que não pode iniciar unidade alguma da linguagem, como um byte de controle vindo de uma cópia malfeita. Erro de estrutura é da fase seguinte; erro de nome é da fase depois dela. Essa estreiteza tem consequência agradável: os erros léxicos de um compilador real são poucos e parecidos, e por isso se estabelece aqui o padrão de qualidade que valerá para todas as fases seguintes.
| Propriedade | O que é | Onde se erra |
|---|---|---|
| Localização precisa | arquivo, linha e coluna a partir de um | contar de zero e esquecer de somar um na exibição |
| Formato consagrado | campos separados por dois-pontos | inventar formato e perder a navegação clicável |
| Linha ofensora com cursor | reproduzir a linha e apontar a coluna | trocar tabulações por espaços e quebrar o alinhamento |
| Causa provável | dizer com o que o caractere se parece | afirmar causa sem poder inferi-la com segurança |
| Ausência de ruído | uma mensagem por problema real | uma mensagem por caractere afetado |
A última é onde a maioria falha. Detectado o erro, o analisador precisa continuar, porque abortar no primeiro problema é praticamente sofrível. A estratégia ingênua é avançar um caractere e tentar de novo: dez caracteres inválidos colados por engano produzem dez mensagens idênticas.
flowchart LR
A["caractere que não inicia<br/>símbolo algum"] --> B{"estratégia de recuperação"}
B -->|"avançar um caractere"| C["uma mensagem por caractere:<br/>parede de ruído"]
B -->|"coalescer a corrida"| D["consome enquanto nenhuma regra<br/>tiver transição inicial"]
D --> E["para em caractere descartável<br/>ou em início de comentário"]
E --> F["uma mensagem por trecho,<br/>com o trecho citado"]
A estratégia que recomendo é a coalescência da corrida inválida: consuma a sequência inteira de caracteres consecutivos que não podem iniciar símbolo algum e reporte uma vez, citando o trecho. Avance enquanto nenhuma regra tiver transição definida a partir do estado inicial, com um cuidado que só aparece na entrada que ninguém pensou em testar — a corrida precisa parar também em caractere descartável e em início de comentário, ou um caractere inválido seguido de espaço engole o identificador seguinte.
O critério por trás disso vale para todas as fases: um erro real vale mais que dez erros derivados, porque a mensagem que interessa some no ruído, e ele volta com força na análise sintática. E o contrato: ao encontrar um erro, o analisador registra um diagnóstico e continua produzindo símbolos. Quem decide se vale prosseguir é o programa principal, ao consultar o conjunto de diagnósticos — vantagem concreta de coletar diagnósticos em vez de lançar exceções.
1.8 O custo: buffers e retrocesso
Os livros clássicos dedicam espaço a uma técnica de leitura em blocos com dois buffers alternados e um caractere sentinela. Ler do disco caractere a caractere paga uma chamada ao sistema por caractere; ler em blocos esbarra no fato de que um lexema pode atravessar a fronteira, e o último aceite exige poder voltar atrás. Daí dois buffers adjacentes recarregados alternadamente, com um sentinela fora do alfabeto no fim de cada um, para que o teste de fim de buffer se funda com o de caractere inesperado.
Quando você pode dispensar tudo isso. Se o arquivo-fonte couber na memória — e programas-fonte cabem, mesmo os grandes —, carregue-o inteiro na abertura e trabalhe sobre um índice. Sem buffer a gerenciar, sem fronteira de bloco, sem limite de comprimento de lexema, e o retrocesso vira uma subtração de índices. De brinde, exibir a linha ofensora nas mensagens fica trivial.
Buffer é questão de entrada e saída; retrocesso é questão de algoritmo, e existe independentemente de como você lê. Chamando de E o total de transições de autômato executadas numa varredura e de C o número de caracteres que compuseram lexemas produzidos, o fator de releitura é
\frac{E}{C},
que vale 1 apenas no caso ideal e cresce por duas causas independentes.
flowchart TD
F["fator de releitura<br/>examinados sobre consumidos"] --> A["causa 1: retrocesso"]
F --> B["causa 2: paralelismo entre regras"]
A --> A1["caracteres lidos entre o último aceite<br/>e a posição de parada"]
A1 --> A2["inerente ao mecanismo:<br/>não desaparece"]
B --> B1["k autômatos leem<br/>o mesmo caractere na mesma tentativa"]
B1 --> B2["decisão de implementação:<br/>some com o autômato combinado"]
Há uma cota útil: com k regras, t símbolos produzidos e L o maior prefixo que algum autômato percorre antes de travar, vale E \le k \cdot L \cdot t. Se L for limitado por constante, a varredura é linear; se alguma categoria admitir lexemas arbitrariamente longos e falhar tarde, L chega à ordem do tamanho do arquivo e a varredura degenera para comportamento quadrático. Não é hipotético: um autômato de literal textual, num arquivo com uma abertura esquecida, percorre todo o resto a partir de cada posição de início.
A segunda causa é escolha sua. Nada obriga a manter um autômato por categoria: dá para construir um único que reconheça a união de todas as linguagens, com cada estado final rotulado pela categoria — e, quando um final for alcançável por mais de uma, pela de maior prioridade. Assim cada caractere é lido uma vez, e é o que um gerador faz. A favor de manter separados está a legibilidade da decisão, porque a prioridade fica explícita no laço em vez de escondida na rotulação dos finais. Mas o modo honesto de decidir é medindo: com dois contadores e o fator de releitura impresso, a escolha entre clareza e velocidade vira comparação entre um número e um requisito.
1.9 Geradores automáticos, e por que vêm por último
Um gerador recebe uma especificação — a lista ordenada de padrões, cada um com uma ação associada — e produz o código-fonte de um analisador léxico. Entrada declarativa, saída em forma de programa: ele é, no sentido próprio, um compilador.
flowchart LR
S["especificação ordenada:<br/>categoria, padrão e ação"] --> T["árvore de cada<br/>expressão regular"]
T --> N["construção de Thompson"]
N --> U["união sob um<br/>estado inicial comum"]
U --> D["construção de subconjuntos<br/>com rótulos propagados"]
D --> M["minimização"]
M --> O["tabela de transição<br/>mais laço de casamento mais longo"]
O --> P["código-fonte do<br/>analisador léxico"]
Olha o tamanho da afirmação contida nesse diagrama: não há nada num gerador de analisadores léxicos que você não tenha construído. A ferramenta que parecia mágica é o que os módulos anteriores produziram, acrescida de emissão de código.
Três recursos além do padrão nomeiam problemas reais. A ação associada é o código executado quando aquele padrão vence: é onde se constrói o símbolo e se converte o valor, e descartar o espaço é simplesmente uma ação que não devolve símbolo. As condições de início, ou estados léxicos, dão modos à especificação, com regras diferentes ativas em cada um, e é assim que se tratam construções que não são regulares no conjunto — um mecanismo fora do modelo, acrescentado porque o modelo não basta. E a antecipação condiciona o casamento ao que vem depois sem consumi-lo; é cara e é fonte conhecida do comportamento quadrático.
Por que, então, alguém escreveria um à mão? Por controle do diagnóstico, sobretudo: refinar as mensagens de um analisador gerado exige lutar contra o mecanismo, e compiladores de produção que investem pesado nisso costumam ter o léxico escrito à mão. Também por dependência de construção e por depurabilidade, já que a tabela emitida não foi escrita para ser lida. A favor do gerador: se a especificação muda muito, ele troca alteração de código por alteração de dado.
A pergunta que decide. Não é “qual é melhor”, é “o que muda mais neste projeto”: se muda a especificação, use o gerador; se muda o comportamento diante de entrada defeituosa, escreva à mão.
Devo a explicação do título. Se eu tivesse apresentado os geradores logo depois das expressões regulares, teria economizado o seu tempo e destruído o seu aprendizado: você rodaria a ferramenta, obteria um analisador funcionando e não teria motivo para estudar Thompson, subconjuntos ou minimização. Apresentados agora, você olha para a tabela emitida e reconhece a determinização, e ganha a capacidade de estimar o que a ferramenta vai produzir: quantos estados, que categorias vão colidir, onde o retrocesso vai doer.
1.10 O analisador léxico do caso conduzido
O critério de leitura é este: o interesse não está em novidade algorítmica, porque não há nenhuma, e sim em ver cada decisão discutida acima aparecer como escolha localizada no código. Repare no que não aparece: nenhuma construção de autômato está escrita ali — os autômatos saem de aplicar à especificação, uma única vez na inicialização, o percurso já pronto. Se o seu analisador léxico contiver construção de autômato, a fase virou uma segunda implementação do motor de que ela deveria ser apenas cliente.
1.10.1 8.1 O símbolo léxico da Peneira
A linguagem que este livro constrói chama-se Peneira, e o seu analisador léxico é o primeiro componente do compilador que tem cliente. Começo, portanto, pela estrutura que atravessa a interface, porque é ela que define o contrato.
A Definição 2.1 separou quatro noções, e quis que essa separação ficasse visível na própria estrutura de dados em vez de morar apenas na prosa. O padrão não aparece: ele vive na especificação léxica, escrita quando a linguagem foi projetada, e o que sobrevive dele em tempo de execução é o autômato. Os outros três aparecem, cada um em seu campo.
07_token.h
#ifndef PENEIRA_07_TOKEN_H
#define PENEIRA_07_TOKEN_H
#include <cstdint>
#include <string>
#include "01_source.h"
namespace peneira {
// As quatro noções que o módulo distingue e que se confundem com facilidade:
//
// padrão — a descrição de uma classe de cadeias (a expressão regular)
// lexema — o trecho concreto do texto que casou com o padrão
// símbolo — a categoria produzida, que é o que a fase seguinte consome
// atributo— a informação adicional que o símbolo carrega além da categoria
//
// O padrão vive na especificação léxica; os outros três vivem aqui.
enum class Categoria : std::uint8_t {
Identificador,
PalavraReservada,
Numero,
Texto,
Padrao,
Pontuacao,
FimDeArquivo,
Invalido,
};
const char* nomeDaCategoria(Categoria c) noexcept;
// Um símbolo léxico. Guarda a posição de propósito: sem ela, o analisador
// sintático do módulo 10 não teria como reportar erro em lugar nenhum, e a
// infraestrutura de diagnóstico do módulo 1 ficaria sem uso.
struct SimboloLexico {
Categoria categoria = Categoria::Invalido;
std::string lexema;
Position posicao{0, 0, 0};
// Atributo. Só um dos dois é significativo, conforme a categoria:
// `valor` para número, `conteudo` para texto e padrão (o miolo, já sem os
// delimitadores). Manter os dois num par de campos em vez de uma união
// discriminada é escolha de simplicidade: são poucos bytes e o código que
// lê fica direto.
double valor = 0.0;
std::string conteudo;
std::string emTexto() const;
};
} // namespace peneira
#endif // PENEIRA_07_TOKEN_H
Três decisões merecem comentário.
A categoria é um tipo enumerado e não uma cadeia de texto. A fase seguinte compara categorias milhares de vezes, e comparar inteiros é mais rápido e menos sujeito a erro de digitação do que comparar cadeias. O nome legível existe, e existe apenas para exibição.
O atributo do texto e do padrão guarda o miolo já sem os delimitadores. É a aplicação direta do princípio da seção 2.3: quem consome não deveria precisar lembrar de tirar as aspas. Essa decisão pequena tem consequência concreta neste projeto — o conteúdo do literal de padrão é exatamente o que a construção de autômatos vai receber para compilar o padrão declarado pelo usuário, e entregá-lo com as barras delimitadoras produziria uma expressão regular malformada de um jeito difícil de diagnosticar.
E a posição está em todo símbolo, sem exceção e sem ser opcional. É aqui que a infraestrutura de posições indexadas e de coleta de diagnósticos, construída antes de existir fase alguma, finalmente encontra uso real. Até este ponto ela tinha sido exercitada apenas com arquivos vazios.
1.10.2 8.2 A interface
A interface é o segundo artefato a olhar, e ela materializa a Definição 1.2.
07_lexer.h
#ifndef PENEIRA_07_LEXER_H
#define PENEIRA_07_LEXER_H
#include <cstddef>
#include <string>
#include <vector>
#include "01_diagnostico.h"
#include "01_source.h"
#include "03_afd.h"
#include "07_token.h"
namespace peneira {
// Analisador léxico da Peneira.
//
// Não há motor novo aqui: os autômatos vêm da especificação do módulo 2,
// passada pelo analisador de notação do módulo 4 e pelo pipeline do módulo 5.
// O que este módulo acrescenta é tudo o que a teoria não menciona — a
// interface sob demanda, o desempate entre padrões, o descarte de espaço e
// comentário, e o erro léxico que informa onde está o problema.
//
// A interface é SOB DEMANDA: o analisador sintático pede o próximo símbolo e
// recebe um. Não produzimos a lista inteira de antemão, porque a fase seguinte
// consome um de cada vez e porque, num arquivo grande, materializar tudo
// custaria memória sem ganho. O método que devolve a lista existe só para as
// demonstrações e para os testes.
class AnalisadorLexico {
public:
AnalisadorLexico(const SourceFile& fonte, DiagnosticBag& diagnosticos);
SimboloLexico proximo();
bool terminou() const noexcept;
std::vector<SimboloLexico> todos();
// Instrumentação do retrocesso. `examinados` conta cada caractere que
// algum autômato leu durante a busca pelo casamento mais longo;
// `consumidos` conta os que viraram lexema. A diferença é o custo do
// retrocesso, e ela é medível em vez de teórica.
std::size_t caracteresExaminados() const noexcept;
std::size_t caracteresConsumidos() const noexcept;
private:
struct Regra {
Categoria categoria;
std::string nome;
Afd automato;
};
void pularIgnoraveis();
bool ehPalavraReservada(const std::string& lexema) const;
SimboloLexico montar(Categoria categoria, const std::string& lexema,
Position posicao) const;
void reportarInvalido();
const SourceFile& fonte_;
DiagnosticBag& diagnosticos_;
std::vector<Regra> regras_;
std::size_t posicao_ = 0;
std::size_t examinados_ = 0;
std::size_t consumidos_ = 0;
bool entregouFim_ = false;
};
// Monta as regras a partir da especificação léxica, na ordem de prioridade.
// Exposta para que as demonstrações possam inspecionar os autômatos.
std::vector<std::string> categoriasEmPrioridade();
} // namespace peneira
#endif // PENEIRA_07_LEXER_H
A operação principal entrega um símbolo por chamada e mantém o estado da varredura entre elas. A operação que devolve a lista inteira existe, e deixei escrito no próprio cabeçalho que ela é para demonstração e teste — precaução deliberada contra o risco descrito na seção 1.3, que é alguém adotá-la como caminho principal e reintroduzir o acoplamento temporal que se quis evitar.
Repare também nos dois contadores de instrumentação declarados na interface pública. Eles não servem ao compilador; servem para medir o fator de releitura da Definição 6.1. Colocá-los na interface, e não em uma variável escondida ativada por uma opção de depuração, é uma escolha: uma medida que custa esforço para obter não é obtida, e uma decisão de projeto que se apoia em intuição sobre desempenho é uma decisão sem fundamento.
O construtor recebe o texto-fonte e o conjunto de diagnósticos, e é ele quem monta as regras. As cinco regras são construídas uma única vez, na inicialização, aplicando à especificação léxica o percurso completo já pronto: análise da notação, construção de Thompson, determinização, minimização. Nenhuma linha de construção de autômato foi escrita neste componente, e essa ausência é o ponto arquitetural do capítulo — a fase é cliente do motor, não uma segunda implementação dele.
1.10.3 8.3 O laço de varredura
Chego ao corpo da fase, onde cada decisão discutida nas seções anteriores aparece localizada.
07_lexer.cpp
#include "07_lexer.h"
#include <algorithm>
#include <cstdlib>
#include <map>
#include <utility>
#include "02_lexico.h"
#include "04_notacao.h"
#include "04_thompson.h"
#include "05_determinizacao.h"
#include "05_minimizacao.h"
namespace peneira {
namespace {
// Ordem de prioridade das categorias. É ela que desempata quando dois padrões
// casam a MESMA quantidade de caracteres — situação diferente do casamento
// mais longo, que desempata por comprimento.
//
// ESPACO fica de fora: espaço em branco é descartado pelo laço de varredura e
// nunca vira símbolo. Precisa existir na especificação mesmo assim, porque é
// ele que delimita onde um identificador termina.
const std::vector<std::pair<std::string, Categoria>>& ordemDasRegras() {
static const std::vector<std::pair<std::string, Categoria>> ordem{
{"NUMERO", Categoria::Numero},
{"IDENTIFICADOR", Categoria::Identificador},
{"TEXTO", Categoria::Texto},
{"PADRAO", Categoria::Padrao},
{"PONTUACAO", Categoria::Pontuacao},
};
return ordem;
}
// Comentário de linha: inicia em '#' e vai até o fim da linha.
//
// A escolha por comentário de LINHA, e não de bloco, tem uma razão que vem
// direto do módulo 6. Comentário de bloco aninhavel — em que um comentário
// pode conter outro — exige contar profundidade, e contar profundidade é
// exatamente o que um autômato finito nao faz. Um analisador léxico que os
// suporte precisa de um contador escrito à mão, fora do modelo. Comentário de
// linha é regular, cabe no modelo, e resolve o problema do usuário.
constexpr char kInicioDeComentario = '#';
bool ehEspacoEmBranco(char c) {
return c == ' ' || c == '\t' || c == '\r' || c == '\n';
}
} // namespace
std::vector<std::string> categoriasEmPrioridade() {
std::vector<std::string> nomes;
for (const auto& par : ordemDasRegras()) {
nomes.push_back(par.first);
}
return nomes;
}
AnalisadorLexico::AnalisadorLexico(const SourceFile& fonte,
DiagnosticBag& diagnosticos)
: fonte_(fonte), diagnosticos_(diagnosticos) {
// Constrói um autômato mínimo por categoria, uma vez só, no início.
// Poderíamos combinar tudo num autômato único, com os estados finais
// marcados por categoria — é o que um gerador de analisadores faz, e é
// mais rápido. Mantive separados porque assim o desempate por prioridade
// fica explícito no laço, em vez de escondido na marcação dos estados.
std::map<std::string, std::string> notacaoPorNome;
for (const CategoriaLexica& c : especificacaoLexica()) {
notacaoPorNome[c.nome] = c.notacao;
}
for (const auto& par : ordemDasRegras()) {
const auto it = notacaoPorNome.find(par.first);
if (it == notacaoPorNome.end()) {
continue;
}
const ResultadoNotacao r = analisarNotacao(it->second);
if (!r.ok) {
continue;
}
const Afn afn = thompson(*r.expressao, par.first);
Afd minimo = minimizar(determinizar(afn, par.first), par.first);
regras_.push_back(Regra{par.second, par.first, std::move(minimo)});
}
}
bool AnalisadorLexico::terminou() const noexcept {
return entregouFim_;
}
std::size_t AnalisadorLexico::caracteresExaminados() const noexcept {
return examinados_;
}
std::size_t AnalisadorLexico::caracteresConsumidos() const noexcept {
return consumidos_;
}
void AnalisadorLexico::pularIgnoraveis() {
const std::string& texto = fonte_.text();
for (;;) {
while (posicao_ < texto.size() && ehEspacoEmBranco(texto[posicao_])) {
++posicao_;
}
if (posicao_ < texto.size() && texto[posicao_] == kInicioDeComentario) {
while (posicao_ < texto.size() && texto[posicao_] != '\n') {
++posicao_;
}
continue; // pode haver mais espaço ou outro comentário adiante
}
return;
}
}
bool AnalisadorLexico::ehPalavraReservada(const std::string& lexema) const {
const std::vector<std::string>& lista = palavrasReservadas();
return std::find(lista.begin(), lista.end(), lexema) != lista.end();
}
SimboloLexico AnalisadorLexico::montar(Categoria categoria,
const std::string& lexema,
Position posicao) const {
SimboloLexico s;
s.categoria = categoria;
s.lexema = lexema;
s.posicao = posicao;
if (categoria == Categoria::Numero) {
s.valor = std::strtod(lexema.c_str(), nullptr);
} else if (categoria == Categoria::Texto || categoria == Categoria::Padrao) {
// O atributo do texto e do padrão é o miolo, sem os delimitadores.
// Quem consome não deveria precisar lembrar de tirar as aspas.
s.conteudo = lexema.size() >= 2 ? lexema.substr(1, lexema.size() - 2)
: std::string();
}
return s;
}
void AnalisadorLexico::reportarInvalido() {
const std::string& texto = fonte_.text();
const std::size_t inicio = posicao_;
// Consome a corrida inteira de caracteres que não podem iniciar símbolo
// algum e reporta UMA vez. Reportar por caractere transformaria uma
// sequência estranha de dez bytes em dez erros, e o critério de qualidade
// deste módulo é o oposto disso: um erro real vale mais que dez derivados.
while (posicao_ < texto.size()) {
if (ehEspacoEmBranco(texto[posicao_]) ||
texto[posicao_] == kInicioDeComentario) {
break;
}
bool algumInicia = false;
for (const Regra& regra : regras_) {
if (regra.automato.transicao(regra.automato.inicial(),
static_cast<Simbolo>(texto[posicao_])) !=
kSemEstado) {
algumInicia = true;
break;
}
}
if (algumInicia && posicao_ > inicio) {
break;
}
++posicao_;
if (algumInicia) {
break;
}
}
const std::size_t tamanho = posicao_ - inicio;
const std::string trecho = texto.substr(inicio, tamanho);
diagnosticos_.error(fonte_.positionAt(inicio),
"caractere inesperado: \"" + trecho + "\"");
}
SimboloLexico AnalisadorLexico::proximo() {
const std::string& texto = fonte_.text();
for (;;) {
pularIgnoraveis();
if (posicao_ >= texto.size()) {
entregouFim_ = true;
SimboloLexico fim;
fim.categoria = Categoria::FimDeArquivo;
fim.posicao = fonte_.positionAt(texto.size());
return fim;
}
const std::size_t inicio = posicao_;
// Casamento mais longo: cada autômato avança enquanto puder, e
// registra a última posição em que passou por estado final. Vence o
// que chegar mais longe; empate resolve pela ordem de prioridade, que
// é a ordem em que as regras estão no vetor.
std::size_t melhorFim = inicio;
Categoria melhorCategoria = Categoria::Invalido;
for (const Regra& regra : regras_) {
Estado atual = regra.automato.inicial();
std::size_t ultimoAceite = inicio;
bool aceitou = false;
for (std::size_t i = inicio; i < texto.size(); ++i) {
atual = regra.automato.transicao(atual,
static_cast<Simbolo>(texto[i]));
++examinados_;
if (atual == kSemEstado) {
break;
}
if (regra.automato.ehFinal(atual)) {
ultimoAceite = i + 1;
aceitou = true;
}
}
if (aceitou && ultimoAceite > melhorFim) {
melhorFim = ultimoAceite;
melhorCategoria = regra.categoria;
}
}
if (melhorCategoria == Categoria::Invalido) {
reportarInvalido();
continue; // recupera e segue: erro léxico não aborta a análise
}
const std::string lexema = texto.substr(inicio, melhorFim - inicio);
const Position posicao = fonte_.positionAt(inicio);
posicao_ = melhorFim;
consumidos_ += lexema.size();
// Prioridade entre padrões que casam a MESMA cadeia: toda palavra
// reservada é um identificador válido segundo a expressão. A escolha
// aqui é a segunda das duas estratégias usuais — reconhecer como
// identificador e reclassificar por consulta a uma lista, em vez de
// dar a cada palavra reservada seu próprio padrão. Custa uma busca por
// símbolo e evita oito autômatos a mais.
Categoria categoria = melhorCategoria;
if (categoria == Categoria::Identificador && ehPalavraReservada(lexema)) {
categoria = Categoria::PalavraReservada;
}
return montar(categoria, lexema, posicao);
}
}
std::vector<SimboloLexico> AnalisadorLexico::todos() {
std::vector<SimboloLexico> lista;
for (;;) {
SimboloLexico s = proximo();
const bool fim = s.categoria == Categoria::FimDeArquivo;
lista.push_back(std::move(s));
if (fim) {
return lista;
}
}
}
} // namespace peneira
Percorro as decisões na ordem em que aparecem.
A ordem das regras é dado, e está escrita em um lugar só. A especificação léxica tem seis categorias; a de espaço em branco fica de fora da lista de regras, porque é descartada pelo laço e nunca vira símbolo. Ela continua existindo na especificação, pela razão da seção 4.1: é ela que define onde um identificador termina.
Cinco autômatos separados, e não um combinado. A alternativa foi discutida na seção 6.3 e é mais rápida. Mantive separados porque assim a regra de prioridade fica explícita no laço, como uma comparação que qualquer leitor entende, em vez de escondida na rotulação dos estados finais produzida pela determinização. A troca é deliberada, e adiante ela tem preço medido em vez de estimado.
O descarte é em laço, não em passada única. Depois de pular espaço pode vir comentário, e depois do comentário pode vir mais espaço. Um while só resolveria o primeiro caso e deixaria o segundo passar.
O comentário é de linha, e a escolha vem de um teorema. Comentário de bloco aninhável exigiria contar profundidade, e contar profundidade é exatamente o que autômato finito não faz — pelo resultado demonstrado no capítulo anterior. Comentário de linha é regular, cabe no motor, e resolve o problema de quem escreve o programa. É a primeira vez, neste projeto, que um resultado de impossibilidade decide uma característica visível da linguagem, e registro isso porque é o tipo de conexão que costuma passar despercebida.
O casamento mais longo usa o último aceite. Cada autômato avança enquanto tiver transição e registra a posição toda vez que passa por estado final; o candidato é o último aceite, não a posição de parada. É o mecanismo da seção 3.3, e é a linha que separa 12 de 12. quando o ponto não é seguido de dígito.
A prioridade vem depois, e compara a cadeia inteira. A reclassificação de palavra reservada acontece depois de o casamento mais longo ter decidido onde o identificador termina, e compara o lexema completo contra a lista. É a ordem defendida na seção 3.6. Invertê-la faria a entrada onibus sair como a palavra reservada on seguida de ibus, e o defeito passaria em todo teste com palavra reservada isolada.
O erro coalesce a corrida inválida. A recuperação consome a sequência inteira de caracteres que não podem iniciar símbolo algum e reporta uma vez, parando também em caractere descartável e em início de comentário — a precaução da seção 5.3. E, depois de reportar, o laço continua: erro léxico não aborta a análise.
1.10.4 8.4 O que a execução mostrou
Rodando sobre o programa de exemplo da linguagem, o analisador produz quarenta e sete símbolos para duzentos e cinquenta e sete caracteres distribuídos em nove linhas, sem nenhum erro. A numeração de linha do primeiro símbolo é 2, e não 1, porque a primeira linha do arquivo é um comentário que não produziu símbolo algum — a confirmação mais barata de que o descarte funciona.
O comportamento diante de entrada defeituosa é o que mais interessa. Uma entrada com dois trechos inválidos, um deles com cinco caracteres seguidos, produz dois diagnósticos, cada um com arquivo, linha, coluna, linha ofensora e cursor, e a análise segue reconhecendo trinta símbolos, incluindo os das linhas posteriores ao problema. A corrida de cinco caracteres virou uma mensagem, e não cinco. Sem a coalescência, o mesmo arquivo produziria seis mensagens para dois defeitos.
E o custo. A instrumentação mede, sobre o programa de exemplo, cento e sessenta e um caracteres consumidos contra trezentos e noventa e um examinados, o que dá um fator de releitura de aproximadamente 2,43. Cada caractere que virou lexema foi lido, em média, duas vezes e meia. O número vem quase inteiramente da decisão de rodar cinco autômatos em paralelo a cada posição; um autômato combinado o levaria para perto de um. A conta fecha a favor da decisão tomada: em arquivos de programa desta linguagem, duas vezes e meia quase nada continua sendo quase nada. Se o alvo fossem arquivos de megabytes, a decisão seria outra — e agora existe um número para embasá-la em vez de uma impressão.
1.10.5 8.5 O defeito que só apareceu aqui
Encerro com o achado mais instrutivo desta fase, e ele não é sobre análise léxica.
Ao ligar o analisador aos autômatos das seis categorias, uma delas falhou contra os exemplos de aceitação e rejeição escritos junto com a especificação. A causa era antiga: a notação da categoria de pontuação tinha sido escrita como prosa legível, com espaços entre as alternativas e parênteses usados como se fossem os caracteres de pontuação que se queria descrever. Na mini-notação, os espaços são símbolos literais e os parênteses são operadores de agrupamento. A expressão foi analisada sem erro, produziu um autômato bem formado, atravessou a determinização e a minimização, e apareceu em duas tabelas de contagem de estados — reconhecendo a linguagem errada o tempo inteiro.
O defeito sobreviveu porque nunca tinha sido executado. As tabelas de contagem mediram um artefato que não fazia o que dizia fazer, e contagem de estados de um autômato errado é um número perfeitamente plausível. A correção, que escapa os parênteses e dispensa os espaços, derrubou aquela categoria de cento e doze para sessenta e quatro estados após Thompson, de vinte e nove para dezesseis após a determinização e de sete para cinco após a minimização, alterando os totais publicados.
Importante
Medir não é verificar. Uma medida sobre um artefato defeituoso produz um número plausível e não acusa nada. O que pega esse tipo de erro é confrontar comportamento contra expectativa escrita antes — que é a função dos conjuntos de exemplos de aceitação e de rejeição redigidos junto com a especificação, quando ainda não havia implementação alguma. Vale a pena escrevê-los cedo justamente porque o retorno vem tarde.
1.11 Síntese
Volto ao ônibus da abertura, porque agora você tem nome para tudo o que aconteceu ali. O analisador léxico é a fronteira entre caractere e estrutura, e existe como fase separada por adequação de formalismo, legibilidade da gramática e concentração das dependências de codificação. Sua interface é sob demanda, e a razão decisiva não é memória nem latência, e sim não fixar o fim da análise léxica antes do início da análise sintática. Quatro noções que a conversa informal funde precisam ficar separadas — padrão na especificação, lexema no texto, símbolo na interface, atributo pendurado no símbolo —, e entre os atributos a posição não é opcional.
A especificação é ambígua por construção, e duas convenções a resolvem: o casamento mais longo desempata comprimentos diferentes, pelo último aceite; a prioridade desempata comprimentos iguais pela ordem da especificação. A ordem entre elas não é reversível, e invertê-la é o que produz on seguido de ibus. O que a teoria não menciona é a maior parte do trabalho: espaço é descartado e não ignorado, porque é ele que delimita; comentário aninhável não cabe no modelo; fim de entrada é símbolo como outro qualquer; e a recuperação coalesce a corrida inválida porque um erro real vale mais que dez derivados. E os geradores fazem, por dentro, exatamente o percurso que você construiu.
Fecha-se aqui o eixo regular inteiro — notação finita, máquina, Thompson, determinização, minimização e o limite dado pelo lema do bombeamento —, transformado numa peça de software com interface e comportamento previsível diante de entrada malformada. E é também onde o percurso encontra o seu limite: o analisador léxico entrega uma sequência plana de símbolos, porque a memória finita do modelo não guarda profundidade, e um programa é aninhado em toda parte. O módulo seguinte sobe um andar na hierarquia, com as gramáticas livres de contexto e o problema da ambiguidade; depois vem o modelo de máquina que acrescenta ao autômato finito exatamente a memória que faltava; e em seguida o analisador sintático que vai consumir a sequência que esta fase produz. A interface que você definir agora é a que aquele analisador vai usar.