Geradores de Lexer
Video da aula estara disponivel em breve
lex/flex: O Modelo Classico
O lex (e seu sucessor open-source flex) e o gerador de lexer classico. Voce escreve uma especificacao com regras regex e acoes em C; a ferramenta gera um scanner C otimizado baseado em tabelas DFA.
C (flex)
/* calculadora.l — especificacao flex */
%{
#include <stdio.h>
%}
%%
[0-9]+ { printf("NUMBER: %s\n", yytext); }
[a-zA-Z_]+ { printf("ID: %s\n", yytext); }
"+" { printf("PLUS\n"); }
"-" { printf("MINUS\n"); }
"*" { printf("STAR\n"); }
"/" { printf("SLASH\n"); }
"=" { printf("ASSIGN\n"); }
";" { printf("SEMI\n"); }
[ \t\n] { /* ignora whitespace */ }
. { printf("UNKNOWN: %s\n", yytext); }
%%
int main() { yylex(); return 0; }
int yywrap() { return 1; }
/* Compilar e executar:
flex calculadora.l
gcc lex.yy.c -o calc_lexer -lfl
echo "x = 42 + y;" | ./calc_lexer
*/PLY: Python Lex-Yacc
PLY (Python Lex-Yacc) e uma implementacao Python pura de lex e yacc. Usa convencoes de nomes e docstrings para definir tokens:
Python
import ply.lex as lex
# Lista de nomes de tokens (obrigatoria)
tokens = (
'NUMBER', 'ID', 'PLUS', 'MINUS', 'STAR',
'SLASH', 'ASSIGN', 'SEMI', 'LPAREN', 'RPAREN',
)
# Tokens simples (regex como string)
t_PLUS = r'\+'
t_MINUS = r'-'
t_STAR = r'\*'
t_SLASH = r'/'
t_ASSIGN = r'='
t_SEMI = r';'
t_LPAREN = r'\('
t_RPAREN = r'\)'
# Tokens com acoes (funcoes, docstring = regex)
def t_NUMBER(t):
r'\d+(\.\d+)?'
t.value = float(t.value) if '.' in t.value else int(t.value)
return t
def t_ID(t):
r'[a-zA-Z_]\w*'
return t
# Ignorar whitespace
t_ignore = ' \t'
# Contar linhas
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)
# Erros
def t_error(t):
print(f"Caractere ilegal '{t.value[0]}' na linha {t.lineno}")
t.lexer.skip(1)
# Criar o lexer
lexer = lex.lex()
# Tokenizar
lexer.input("resultado = 42 + bonus;")
for tok in lexer:
print(tok)
# LexToken(ID,'resultado',1,0)
# LexToken(ASSIGN,'=',1,10)
# LexToken(NUMBER,42,1,12)
# LexToken(PLUS,'+',1,15)
# LexToken(ID,'bonus',1,17)
# LexToken(SEMI,';',1,22)Hand-Written vs. Gerado: Trade-offs
Diagrama
Criterio Hand-Written Gerado (lex/PLY)
-------- ------------ ----------------
Controle Total Limitado pela ferramenta
Performance Pode ser otimo Otimo (tabelas DFA)
Diagnosticos Customizaveis Genericos
Tempo de dev Mais lento Mais rapido
Manutenibilidade Depende da qualidade Depende da especificacao
Debug Direto (breakpoints) Indireto (tabelas)
Flexibilidade Ilimitada Limitada ao modelo regex
Compiladores maduros (GCC, Clang, Go, Rust) usam hand-written.
Prototipagem e linguagens menores usam geradores.
Decisao pragmatica, nao dogmatica.
Tendencia moderna
A maioria dos compiladores de producao modernos (Go, Rust, Swift, TypeScript) usa lexers hand-written. A razao principal e mensagens de erro — um lexer manual pode gerar diagnosticos muito mais claros. Geradores ainda sao excelentes para prototipagem, DSLs internas, e linguagens menores.
No harness.os
O harness.os usa YAML como formato principal para configuracao, rules, e knowledge chunks. Isso significa que o "lexer" ja existe — e o parser YAML (PyYAML ou ruamel.yaml). Mas ha trade-offs:
Python
import yaml
import time
# Trade-off: YAML parser generico vs custom parser
# Opcao 1: PyYAML (parser generico)
rule_yaml = """
title: Commit Hygiene
context: git-commit
concern: governance
priority: high
content: |
Nao adicionar Co-Authored-By: Claude
Usar mensagens concisas
"""
start = time.perf_counter()
for _ in range(10000):
result = yaml.safe_load(rule_yaml)
yaml_time = time.perf_counter() - start
# Opcao 2: Custom parser (so para frontmatter simples)
def parse_frontmatter(text):
fields = {}
for line in text.strip().split('\n'):
if ':' in line:
key, _, val = line.partition(':')
fields[key.strip()] = val.strip()
return fields
start = time.perf_counter()
for _ in range(10000):
result = parse_frontmatter(rule_yaml)
custom_time = time.perf_counter() - start
print(f"PyYAML: {yaml_time:.3f}s")
print(f"Custom: {custom_time:.3f}s")
print(f"Speedup: {yaml_time/custom_time:.1f}x")
# Tipicamente: custom e 10-50x mais rapido para casos simples
# Mas YAML generico trata todos os edge cases (multiline, listas, etc.)
Decisao pragmatica
Para o harness.os, o YAML parser generico e a escolha correta: os arquivos de configuracao sao lidos poucas vezes (na inicializacao), e a flexibilidade do YAML vale mais que a performance bruta. Se o harness processasse milhares de rules por segundo (batch processing), um parser custom faria sentido.
Resumo
- flex gera scanners C a partir de especificacoes regex — rapido, mas pouco flexivel
- PLY traz o modelo lex/yacc para Python com convencoes de nome e docstrings
- Lexers hand-written oferecem mais controle sobre diagnosticos e edge cases
- Compiladores de producao preferem hand-written; prototipagem prefere geradores
- Parsers YAML genericos sao a escolha certa quando performance nao e gargalo
Exercicio
Compare a performance de parsing YAML (PyYAML) vs um parser custom simples para frontmatter de regras do harness.os. Meça o tempo de 10.000 iteracoes para cada. Depois, identifique um caso onde o parser custom falharia mas o PyYAML funcionaria corretamente (dica: pense em valores multi-linha, listas, e caracteres especiais).
Verifique seu entendimento
Qual e a principal razao pela qual compiladores como GCC, Go e Rust usam lexers hand-written em vez de geradores?