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 — Resumo
Esta é a versão de revisão. Recapitulo o módulo em ritmo de véspera, sem demonstrar nada por inteiro — para isso existem a versão completa do material deste módulo e o livro. Um aviso que vale mais que o resto: aqui não há algoritmo novo nenhum. O que se acrescenta é tudo aquilo que os teoremas não mencionam, e é justamente aí que os defeitos moram.
Você testou a palavra reservada on, ela saiu como palavra reservada, todos os testes passaram. Aí alguém escreveu uma variável chamada onibus e o seu analisador devolveu on seguido de um identificador ibus. Repare: 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. Um erro na construção de subconjuntos aparece na primeira bateria de testes; um erro de desempate atravessa o projeto escondido.
1.1 O que a fase faz, e por que existe sozinha
Dizer que 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 em que 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 é a função parcial
\Lambda : \Sigma^* \longrightarrow (C \times \Sigma^* \times \mathbb{N})^* \times D,
que leva o texto 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. 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. Adequação de formalismo: a estrutura interna de identificadores e números é regular, reconhecível em tempo linear por autômato finito, 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ó.
Sobre a conversa com a fase seguinte há duas opções, e essa é a decisão de projeto mais consequente do módulo. Entregar a lista completa é o mais simples de testar, e cobra memória proporcional ao arquivo, diagnóstico que só sai no fim da varredura e — o que decide — o fim da análise léxica fixado antes do começo da análise sintática. A opção sob demanda produz um símbolo por chamada: logicamente as fases continuam distintas, fisicamente as duas travessias do texto se fundem numa só. Memória é argumento circunstancial, latência é melhor, mas o decisivo é o acoplamento temporal, e eu aprendi isso do jeito caro: materializei tudo no meu primeiro analisador léxico e, meses depois, precisei da tabela de símbolos para decidir a categoria de um nome — a análise léxica já havia terminado quando a informação passou a existir.
Pare e pense. Há linguagens em que um mesmo nome designa um tipo ou uma variável conforme tenha sido declarado antes, e a primeira fase precisa consultar informação da terceira para decidir a categoria. Que decisão de sintaxe obrigou a arquitetura inteira do compilador a ficar mais feia?
E vale registrar 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; e não decide o que fazer com os erros — registra e continua.
1.2 Padrão, lexema, símbolo e atributo
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. Um símbolo léxico é o par formado pela categoria do padrão vencedor e pelos atributos daquele lexema. Um atributo é informação adicional de que alguma fase posterior vai precisar. A assimetria 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. 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. Sobre atributos, 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, porque ali 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. E a posição não é opcional: ela existe naturalmente num único instante, aquele em que o índice do caractere é conhecido; depois o texto foi descartado e reconstruir a posição de um nó é impossível.
1.3 As duas regras de desempate
Numa posição i, 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 não determina sozinha a segmentação: é 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.
O casamento mais longo resolve comprimentos diferentes: vence quem chegar mais longe. Com m_j(i) = \max\{\ell \ge 1 \mid w[i \ldots i+\ell-1] \in L(r_j)\} para cada regra j, o lexema é o trecho de comprimento M(i) = \max_j m_j(i), máximo que existe sempre que existe candidato, porque os comprimentos são inteiros positivos limitados por |w| - i. 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. aceitou pela última vez depois do 2 e parou depois do ponto — quem devolve a parada produz um lexema que nem pertence à linguagem do padrão. Os caracteres entre um ponto e outro são relidos: isso é o retrocesso.
Resolvido o comprimento, resta o empate, e aí entra a regra de prioridade: entre as regras que atingiram o comprimento máximo, vence a de menor índice na especificação. Juntas, as duas tornam a segmentação uma função bem definida, e é isso que autoriza chamar o analisador léxico de determinístico — determinismo que é outra coisa, completamente, do dos autômatos.
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 universal é o das palavras reservadas, porque o padrão de identificador descreve uma linguagem que as contém. Ou cada palavra ganha o seu padrão antes do identificador, ao preço de um autômato por palavra e de uma correção que depende da ordem das linhas; ou se reconhece tudo como identificador e, decidido o comprimento, consulta-se uma lista com o lexema inteiro. Eu prefiro a segunda, pelo acoplamento, e reconheço que é preferência, não teorema.
E agora o ponto que fecha a abertura: o casamento mais longo vem primeiro, a prioridade vem depois. Se a implementação consultar a lista assim que os caracteres lidos formarem uma palavra dela, onibus produz on seguido de lixo. 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 é exatamente o que a gente escreve ao testar palavras reservadas. Escreva hoje, de propósito, um caso com identificador prefixado por palavra reservada.
1.4 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. E o pular tem de ser em laço, porque depois do espaço vem comentário e depois do comentário mais espaço.
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; 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, e o lema do bombeamento fecha a porta. Aninhar custa 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.
O fim do arquivo pede 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, e continue devolvendo o mesmo símbolo nas chamadas seguintes, porque a fase seguinte pode pedir mais de uma vez durante a recuperação. Dois casos de borda de literais têm respostas opostas: texto sem fechamento pede tratamento específico, senão o autômato consome o resto do arquivo; número com dois pontos decimais não pede nada, porque a sequência é lexicamente válida e sintaticamente inválida.
1.5 Erro léxico, retrocesso e geradores
Ocorre erro léxico na posição i quando nenhuma regra admite casamento não vazio a partir dali. Erro de estrutura é da fase seguinte, erro de nome é da fase depois dela, e por isso os erros léxicos são poucos e parecidos — é aqui que se estabelece o padrão de qualidade que valerá para todas as fases.
| 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 |
| Formato consagrado | campos separados por dois-pontos | perder a navegação clicável |
| Linha ofensora com cursor | reproduzir a linha, apontar a coluna | trocar tabulações e desalinhar |
| Ausência de ruído | uma mensagem por problema real | uma por caractere afetado |
A última é onde a maioria falha. Avançar um caractere e tentar de novo transforma dez caracteres inválidos colados em dez mensagens idênticas. A estratégia que recomendo é a coalescência da corrida inválida: consuma a sequência inteira de caracteres que não podem iniciar símbolo algum e reporte uma vez, com o cuidado de parar também em caractere descartável e em início de comentário. Um erro real vale mais que dez erros derivados.
Buffer é questão de entrada e saída, e se o arquivo couber na memória — e cabe — carregue-o inteiro e trabalhe sobre um índice. Retrocesso é questão de algoritmo e existe de qualquer jeito: chamando E o total de transições executadas e C o número de caracteres que viraram lexema, o fator de releitura é
\frac{E}{C},
que vale 1 só no caso ideal. Com k regras, t símbolos e L o maior prefixo percorrido antes de travar, vale E \le k \cdot L \cdot t; se L crescer com o arquivo, a varredura degenera para comportamento quadrático. A segunda causa é escolha sua: um único autômato da união, com finais rotulados pela categoria de maior prioridade, lê cada caractere uma vez. Na implementação de referência da Peneira mantive cinco autômatos separados, para que a prioridade fique explícita no laço, e instrumentei a decisão em vez de defendê-la por intuição:
Rodando sobre o programa de exemplo, o analisador produz quarenta e sete símbolos sem erro, uma entrada com dois trechos defeituosos produz dois diagnósticos em vez de seis, e o fator de releitura medido é 2,43. Nenhuma construção de autômato aparece nesse componente: as regras são montadas uma vez, na inicialização, aplicando à especificação o percurso já pronto.
Fecho com os geradores, que vêm por último de propósito. Um gerador recebe a lista ordenada de padrões com ações associadas e produz o código-fonte de um analisador léxico — é, no sentido próprio, um compilador. E olha o tamanho da afirmação: não há nada dentro dele que você não tenha construído. Se eu os tivesse apresentado logo depois das expressões regulares, você rodaria a ferramenta, obteria um analisador funcionando e não teria motivo para estudar Thompson, subconjuntos ou minimização.
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.
1.6 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, existe como fase separada por adequação de formalismo, legibilidade e concentração de dependências, e conversa sob demanda para não fixar o seu próprio fim antes do início da análise sintática. Padrão, lexema, símbolo e atributo vivem em lugares diferentes, e a posição não é atributo opcional. A especificação é ambígua por construção, e as duas convenções que a resolvem não são comutáveis: casamento mais longo pelo último aceite, depois prioridade pela ordem. O resto do trabalho é o que a teoria não menciona — espaço descartado e não ignorado, comentário aninhável fora do modelo, fim de entrada como símbolo, corrida inválida coalescida. Fecha-se aqui o eixo regular inteiro, virado peça de software, e é aqui também que ele encontra o limite: a saída é uma sequência plana, e um programa é aninhado em toda parte. O marco deste módulo — analisador completo, casos de teste, documentação revisada — define a interface que o analisador sintático vai consumir.