Tokens e Expressoes Regulares
Video da aula estara disponivel em breve
O que sao Tokens
A analise lexica (ou scanning) e a primeira fase do compilador. Ela lê o fluxo de caracteres do codigo-fonte e agrupa-os em unidades significativas chamadas tokens. Um token e um par (tipo, valor) que representa uma unidade atomica da linguagem.
Diagrama
Entrada (fluxo de caracteres):
i f ( x > = 1 0 ) { r e t u r n x * 2 ; }
Saida (fluxo de tokens):
(KEYWORD, "if")
(LPAREN, "(")
(ID, "x")
(GE, ">=")
(NUMBER, "10")
(RPAREN, ")")
(LBRACE, "{")
(KEYWORD, "return")
(ID, "x")
(STAR, "*")
(NUMBER, "2")
(SEMI, ";")
(RBRACE, "}")
Espacos em branco e comentarios sao descartados pelo lexer.Categorias de Tokens
As categorias de tokens variam por linguagem, mas geralmente incluem:
Diagrama
Categoria Exemplos Regex (simplificada)
--------- -------- --------------------
Keywords if, else, while, return if|else|while|return
Identificadores x, resultado, calcular [a-zA-Z_][a-zA-Z0-9_]*
Inteiros 42, 0, 1000 [0-9]+
Floats 3.14, 0.5, 1e10 [0-9]+\.[0-9]+([eE][0-9]+)?
Strings "hello", 'world' "([^"\\]|\\.)*"
Operadores +, -, *, >=, ==, != \+|\-|\*|>=|==|!=
Delimitadores (, ), {, }, ;, , \(|\)|\{|\}|;|,
Comentarios // ..., /* ... */ //.*|/\*[\s\S]*?\*/
Whitespace espacos, tabs, newlines [ \t\n\r]+Expressoes Regulares: Fundamentos
Expressoes regulares definem padroes para linguagens regulares. Todo token pode ser descrito por uma regex. Os operadores fundamentais sao:
Diagrama
Operador Significado Exemplo Reconhece
-------- ----------- ------- ---------
a literal 'a' a {"a"}
a|b alternativa (a ou b) a|b {"a", "b"}
ab concatenacao ab {"ab"}
a* zero ou mais a* {"", "a", "aa", ...}
a+ um ou mais a+ {"a", "aa", "aaa", ...}
a? zero ou um a? {"", "a"}
[abc] classe de caracteres [abc] {"a", "b", "c"}
[a-z] faixa [a-z] {"a", "b", ..., "z"}
[^a] negacao [^a] tudo exceto "a"
. qualquer caractere . qualquer um
(...) agrupamento (ab)+ {"ab", "abab", ...}De Regex para NFA: Construcao de Thompson
A construcao de Thompson converte uma regex em um NFA equivalente, construindo sub-automatos para cada operador:
Diagrama
Regex: a NFA: ---> (s) --a--> ((f))
Regex: a|b NFA: +--a--> (f1)--+
(s)--e--| |--e--> ((f))
+--b--> (f2)--+
Regex: ab NFA: ---> (s) --a--> (m) --b--> ((f))
Regex: a* NFA: +----e-----------+
(s)--e--| |--e--> ((f))
(m1)--a-->(m2)--+
^ |
+----e-----+
e = transicao epsilon (sem consumir caractere)
Python
import re
# Definindo tokens com regex em Python
token_patterns = [
('NUMBER', r'\d+(\.\d+)?'),
('ID', r'[a-zA-Z_]\w*'),
('ASSIGN', r'='),
('PLUS', r'\+'),
('MINUS', r'-'),
('STAR', r'\*'),
('SLASH', r'/'),
('LPAREN', r'\('),
('RPAREN', r'\)'),
('SEMI', r';'),
('SKIP', r'[ \t]+'),
('NEWLINE', r'\n'),
('MISMATCH', r'.'),
]
# Combinar todas as regex em uma so, usando grupos nomeados
master_pattern = '|'.join(
f'(?P<{name}>{pattern})'
for name, pattern in token_patterns
)
def tokenize(code):
"""Tokeniza o codigo-fonte usando regex."""
tokens = []
for match in re.finditer(master_pattern, code):
kind = match.lastgroup
value = match.group()
if kind == 'SKIP' or kind == 'NEWLINE':
continue
elif kind == 'MISMATCH':
raise SyntaxError(f'Caractere inesperado: {value!r}')
tokens.append((kind, value))
return tokens
# Exemplo de uso
code = "resultado = taxa * 100 + bonus;"
for tok in tokenize(code):
print(tok)
# ('ID', 'resultado')
# ('ASSIGN', '=')
# ('ID', 'taxa')
# ('STAR', '*')
# ('NUMBER', '100')
# ('PLUS', '+')
# ('ID', 'bonus')
# ('SEMI', ';')
Prioridade de tokens
Quando duas regras casam com o mesmo prefixo, o lexer usa duas regras: (1) longest match — escolhe o match mais longo, e (2) rule priority — em caso de empate, escolhe a regra que aparece primeiro. Por isso, keywords como
if devem ter prioridade sobre identificadores genericos.
No harness.os
O harness.os precisa parsear frontmatter YAML para extrair metadados de knowledge chunks e rules. A primeira fase e lexica — identificar os tokens do frontmatter:
Python
import re
# Tokens do frontmatter YAML do harness.os
frontmatter_tokens = [
('DELIMITER', r'^---$'), # delimitador de frontmatter
('KEY', r'^[a-z_]+(?=:)'), # chave YAML (title, context, etc.)
('COLON', r':'), # separador chave:valor
('PIPE', r'\|'), # indicador de bloco multi-linha
('STRING', r'"[^"]*"'), # valor entre aspas
('VALUE', r'[^\n]+'), # valor da chave
('NEWLINE', r'\n'), # fim de linha
('INDENT', r'^ +'), # indentacao (bloco)
]
# Exemplo de frontmatter
frontmatter = """---
title: Commit Hygiene
context: git-commit
concern: governance
content: |
Nao adicionar Co-Authored-By
Usar mensagens concisas
---"""
# Extrair campos com regex simples
fields = {}
in_block = False
block_key = None
block_lines = []
for line in frontmatter.split('\n'):
if line.strip() == '---':
if in_block:
fields[block_key] = '\n'.join(block_lines)
continue
if in_block and line.startswith(' '):
block_lines.append(line.strip())
continue
elif in_block:
fields[block_key] = '\n'.join(block_lines)
in_block = False
match = re.match(r'(\w+):\s*(.*)', line)
if match:
key, val = match.groups()
if val == '|':
in_block = True
block_key = key
block_lines = []
else:
fields[key] = val
print(fields)
# {'title': 'Commit Hygiene', 'context': 'git-commit',
# 'concern': 'governance', 'content': 'Nao adicionar...'}Resumo
- A analise lexica transforma caracteres em tokens (tipo + valor)
- Cada categoria de token e definida por uma expressao regular
- Regras de desambiguacao: longest match e rule priority
- A construcao de Thompson converte regex em NFA sistematicamente
- Python
re.finditercom grupos nomeados implementa um tokenizer simples
Exercicio
Escreva padroes regex que tokenizem os campos do frontmatter YAML usado pelo harness.os. Seu tokenizer deve reconhecer: delimitadores ---, chaves (title, context, concern, content), separador :, valores string, e indicador de bloco |. Teste com pelo menos 3 exemplos de frontmatter diferentes.
Verifique seu entendimento
Quando o lexer encontra "iffy" no codigo-fonte, qual regra de desambiguacao decide se e o keyword "if" seguido de "fy" ou o identificador "iffy"?