Ferramentas de Construção de Compilador: Lex e Yacc Explicados
Lex e Yacc são ferramentas fundamentais Unix para construir compiladores e interpretadores. Elas lidam com fases sequenciais de processamento de linguagem.
Lex — Gerador de Analisador Léxico
- Entrada: Expressões regulares (padrões para tokens)
- Saída: Programa C (
lex.yy.c) = lexer/scanner
- Função: Stream de caracteres → Stream de tokens
- Tokens: Palavras-chave, identificadores, literais, operadores, pontuação
- Determinístico: Sempre sabe próximo token (baseado em DFA)
- Mais simples: Mais fácil de aprender, escrever, debugar
Yacc — Yet Another Compiler-Compiler (Gerador de Parser)
- Entrada: Gramática livre de contexto (regras tipo BNF)
- Saída: Programa C (
y.tab.c) = parser
- Função: Stream de tokens → Árvore de parse / AST
- Parsing: LALR(1) — bottom-up, lookahead 1
- Não-determinístico: Pode backtrack/resolver conflitos (shift/reduce, reduce/reduce)
- Complexo: Design de gramática, resolução de conflitos, regras de precedência
Fluxo de Trabalho
[Código Fonte] → [Lex] → [Tokens] → [Yacc] → [Árvore Parse] → [Análise Semântica] → [Geração Código]
Diferenças Principais
| Aspecto | Lex | Yacc |
|---|
| Fase | Análise léxica (scanning) | Análise sintática (parsing) |
| Formalismo | Expressões regulares | Gramática livre de contexto |
| Saída | Tokens (símbolos terminais) | Hierarquia estruturada (AST) |
| Complexidade | Baixa | Alta |
| Determinismo | Sim (DFA) | Não (LALR com conflitos) |
| Tratamento de Erro | Caractere inválido | Recuperação de erro sintático |
Sucessores Modernos
- Flex (GNU Lex) + Bison (GNU Yacc) — padrão no Linux
- ANTLR — gramática unificada, LL(*), multi-target (Java, Python, JS, C++)
- Tree-sitter — parsing incremental para IDEs
Lex/Yacc permanecem a base pedagógica para entender pipelines de processamento de linguagem.
