Arithmetic Expression Compiler (Python)

CI Pytest Dependencias

A compiler pipeline for arithmetic expressions implemented entirely in Python with no external dependencies. The system performs lexical analysis, LL(1) recursive-descent parsing, 3-address intermediate code (IR) generation, and IR execution — exposed through an interactive REPL.

Playground do compilador — tokens, AST, IR e execução

leonardopcavalcanti.github.io/python-expression-compiler — ferramenta web educacional que mostra, ao vivo, cada fase da compilação: tokens → árvore sintática (AST) → código de 3 endereços → execução passo a passo, além de mensagens de erro com indicador de posição.

O playground (em playground/) é um port fiel do compilador para TypeScript (React + Vite), rodando 100% no navegador. Útil como apoio didático para a disciplina de Compiladores.

Um compilador é uma das ideias mais elegantes da Ciência da Computação: transformar texto em significado executável, fase por fase. Este projeto isola o front-end de um compilador para que cada etapa fique visível.

texto → [Análise Léxica] → tokens → [Análise Sintática] → AST → [Geração de IR] → código intermediário

• Análise léxica (lexer): quebra a sequência de caracteres em tokens (NUMBER, PLUS, STAR, LPAREN...). É reconhecimento de linguagens regulares — por isso o lexer usa expressões regulares.
• Análise sintática (parser): verifica se a sequência de tokens obedece à gramática e constrói a estrutura. Aqui saímos das linguagens regulares para as linguagens livres de contexto (uma regular não conta parênteses balanceados; uma livre de contexto, sim).
• Geração de código intermediário (IR): traduz a estrutura para instruções simples e independentes de máquina.

A gramática deste projeto não é "natural" por acaso:

E → T E' E' → + T E' | ε
T → F T' T' → * F T' | ε
F → number | ( E )

• Eliminação de recursão à esquerda: uma regra como E → E + T faria um parser descendente recursivo entrar em loop infinito. A reescrita com E' remove isso.
• LL(1) = decisão com 1 token de lookahead: o parser escolhe qual regra aplicar olhando apenas o próximo token, sem retroceder (backtracking). É o que torna o recursive descent simples e linear.
• Precedência embutida na estrutura: * fica "mais fundo" na gramática (T) que + (E), então 2 + 3 * 4 agrupa a multiplicação primeiro — sem nenhum pós-processamento.

A IR usa temporários nomeados (t1, t2, ...), cada instrução com no máximo um operador:

t4 = t2 * t3
t5 = t1 + t4

É a forma intermediária clássica entre a árvore e o código de máquina — fácil de otimizar e de mapear para registradores. É também a fronteira onde a avaliação acontece (a expressão vira uma lista de passos executáveis).

Lexer e parser distinguem erro léxico (um caractere que não forma token) de erro sintático (tokens válidos em ordem inválida), reportando a posição — a base de boas mensagens de compilador.

Leituras de referência:

• Aho, Lam, Sethi & Ullman — Compilers: Principles, Techniques, and Tools (o "livro do dragão"), caps. 3 (análise léxica) e 4 (análise sintática).
• Robert Nystrom — Crafting Interpreters (gratuito online), excelente introdução prática a lexers e parsers.

The grammar is factored to eliminate left recursion and encode operator precedence:

E → T E'
E' → + T E' | ε
T → F T'
T' → * F T' | ε
F → number | ( E )

E handles addition, T handles multiplication, and F handles atoms (literals and parenthesized sub-expressions). This structure guarantees correct precedence without any post-processing.

Input string
 │
 ▼
[Lexer] analisador_lexico.py
 │ Tokenizes input into: NUMBER, PLUS, STAR, LPAREN, RPAREN, EOF
 │
 ▼
[Parser] analisador_sintatico.py
 │ LL(1) recursive descent; drives IR generation during parsing
 │
 ▼
[IR Generator] codigo_intermediario.py
 │ Emits 3-address instructions: tN = operand op operand
 │
 ▼
[IR Executor]
 │ Evaluates the instruction list; returns the value of the last temporary
 │
 ▼
Result

Generated IR:

t1 = 2
t2 = 3
t3 = 4
t4 = t2 * t3
t5 = t1 + t4

Result: t5 = 14

python-expression-compiler/
├── main.py # Entry point, launches the REPL
├── requirements.txt # Empty (no external dependencies)
├── src/tradutor_expressoes/
│ ├── tokens.py # Token type definitions
│ ├── analisador_lexico.py # Lexer (tokenizer)
│ ├── analisador_sintatico.py # Parser (LL(1) recursive descent)
│ ├── codigo_intermediario.py # 3-address IR generator and executor
│ ├── interface_repl.py # REPL loop
│ ├── erros.py # Error types (LexicalError, SyntaxError)
│ └── utils.py # Shared utilities
└── tests/
 ├── teste_analisador_lexico.py
 ├── teste_avaliacao_expressao.py
 ├── teste_erros_sintaticos.py
 └── teste_interface_repl.py

python main.py

The REPL reads one expression per line, prints the result, and loops. On error, prints a diagnostic and continues.

> 2 + 3 * 4
Expressão válida. Resultado: 14
> (1 + 2) * (3 + 4)
Expressão válida. Resultado: 21
> 2 +
Erro sintático: token inesperado após '+'

Prints the token stream and full IR listing before the result:

python main.py --debug

The suite in tests/test_tradutor.py covers every phase: tokenization (multi-digit numbers, whitespace handling, lexical errors), end-to-end evaluation (operator precedence, left associativity, nested parentheses) and syntactic error handling (malformed inputs). It runs on every push via GitHub Actions, on Python 3.12 and 3.13.

pip install pytest
# Run all tests
python -m pytest tests/
# Run with verbose output
python -m pytest tests/ -v

The compiler itself has zero dependencies — pytest is needed only to run the tests.