Construindo um Lexer
Video da aula estara disponivel em breve
Arquitetura de um Scanner
Um lexer (ou scanner) hand-written segue uma arquitetura simples: um loop que lê caractere por caractere, usando o caractere atual para decidir qual tipo de token construir.
Diagrama
+---> whitespace? ---> ignorar, continuar
|
+---> digito? -------> ler numero completo ---> emit NUMBER
|
char atual ---------+---> letra/_? ------> ler identificador ----> emit ID/KEYWORD
|
+---> '"'? ----------> ler string completa --> emit STRING
|
+---> operador? -----> verificar multi-char -> emit OPERATOR
|
+---> outro? --------> ERRO lexico
Python
from dataclasses import dataclass
from enum import Enum, auto
class TokenType(Enum):
NUMBER = auto()
ID = auto()
KEYWORD = auto()
STRING = auto()
ASSIGN = auto()
PLUS = auto()
MINUS = auto()
STAR = auto()
SLASH = auto()
EQ = auto() # ==
NE = auto() # !=
LT = auto() # <
GT = auto() # >
LE = auto() # <=
GE = auto() # >=
LPAREN = auto()
RPAREN = auto()
LBRACE = auto()
RBRACE = auto()
SEMI = auto()
COMMA = auto()
COLON = auto()
EOF = auto()
KEYWORDS = {'if', 'else', 'while', 'return', 'def', 'let'}
@dataclass
class Token:
type: TokenType
value: str
line: int
col: int
class Lexer:
def __init__(self, source: str):
self.source = source
self.pos = 0
self.line = 1
self.col = 1
self.tokens = []
def peek(self) -> str:
if self.pos >= len(self.source):
return '\0'
return self.source[self.pos]
def advance(self) -> str:
ch = self.source[self.pos]
self.pos += 1
if ch == '\n':
self.line += 1
self.col = 1
else:
self.col += 1
return ch
def skip_whitespace(self):
while self.pos < len(self.source) and self.peek() in ' \t\n\r':
self.advance()
def skip_comment(self):
# Comentario de linha: // ate o fim da linha
while self.pos < len(self.source) and self.peek() != '\n':
self.advance()
def read_number(self) -> Token:
start_col = self.col
num = ''
while self.pos < len(self.source) and self.peek().isdigit():
num += self.advance()
if self.pos < len(self.source) and self.peek() == '.':
num += self.advance()
while self.pos < len(self.source) and self.peek().isdigit():
num += self.advance()
return Token(TokenType.NUMBER, num, self.line, start_col)
def read_identifier(self) -> Token:
start_col = self.col
ident = ''
while self.pos < len(self.source) and (self.peek().isalnum() or self.peek() == '_'):
ident += self.advance()
tok_type = TokenType.KEYWORD if ident in KEYWORDS else TokenType.ID
return Token(tok_type, ident, self.line, start_col)
def read_string(self) -> Token:
start_col = self.col
self.advance() # consume opening quote
s = ''
while self.pos < len(self.source) and self.peek() != '"':
if self.peek() == '\\':
self.advance() # escape char
s += self.advance()
if self.pos < len(self.source):
self.advance() # consume closing quote
return Token(TokenType.STRING, s, self.line, start_col)
def tokenize(self) -> list:
while self.pos < len(self.source):
self.skip_whitespace()
if self.pos >= len(self.source):
break
ch = self.peek()
if ch.isdigit():
self.tokens.append(self.read_number())
elif ch.isalpha() or ch == '_':
self.tokens.append(self.read_identifier())
elif ch == '"':
self.tokens.append(self.read_string())
elif ch == '/' and self.pos + 1 < len(self.source) and self.source[self.pos+1] == '/':
self.skip_comment()
elif ch == '=':
col = self.col; self.advance()
if self.peek() == '=':
self.advance()
self.tokens.append(Token(TokenType.EQ, '==', self.line, col))
else:
self.tokens.append(Token(TokenType.ASSIGN, '=', self.line, col))
elif ch == '+':
self.tokens.append(Token(TokenType.PLUS, '+', self.line, self.col)); self.advance()
elif ch == '-':
self.tokens.append(Token(TokenType.MINUS, '-', self.line, self.col)); self.advance()
elif ch == '*':
self.tokens.append(Token(TokenType.STAR, '*', self.line, self.col)); self.advance()
elif ch == ';':
self.tokens.append(Token(TokenType.SEMI, ';', self.line, self.col)); self.advance()
elif ch == '(':
self.tokens.append(Token(TokenType.LPAREN, '(', self.line, self.col)); self.advance()
elif ch == ')':
self.tokens.append(Token(TokenType.RPAREN, ')', self.line, self.col)); self.advance()
elif ch == '{':
self.tokens.append(Token(TokenType.LBRACE, '{', self.line, self.col)); self.advance()
elif ch == '}':
self.tokens.append(Token(TokenType.RBRACE, '}', self.line, self.col)); self.advance()
else:
raise SyntaxError(f"Caractere inesperado '{ch}' na linha {self.line}:{self.col}")
self.tokens.append(Token(TokenType.EOF, '', self.line, self.col))
return self.tokens
# Uso
lexer = Lexer('let x = 42 + y; // soma')
for tok in lexer.tokenize():
print(f"{tok.type.name:10} {tok.value!r:15} L{tok.line}:C{tok.col}")
# KEYWORD 'let' L1:C1
# ID 'x' L1:C5
# ASSIGN '=' L1:C7
# NUMBER '42' L1:C9
# PLUS '+' L1:C12
# ID 'y' L1:C14
# SEMI ';' L1:C15
# EOF '' L1:C26Tratando Erros Lexicos
Um bom lexer nao para no primeiro erro. Estrategias de recuperacao de erros lexicos:
Diagrama
Estrategia Descricao Exemplo
---------- --------- -------
Panic mode Descarta caracteres ate achar @abc -> descarta @, emite ID "abc"
um token valido
Insercao Insere caractere esperado "hello -> insere " no final
Delecao Remove caractere invalido he$$lo -> remove $$, emite "hello"
Substituicao Troca por caractere valido 1.2.3 -> trata como 1.2 + .3
Na pratica
A maioria dos compiladores modernos usa panic mode para erros lexicos: descarta o caractere invalido, emite um diagnostico, e continua. O objetivo e reportar o maior numero possivel de erros em uma unica passagem, para que o programador nao precise compilar repetidas vezes para descobrir todos os problemas.
No harness.os
Vamos construir um lexer especifico para definicoes de workflow steps do harness.os:
Python
from enum import Enum, auto
class WorkflowTokenType(Enum):
STEP_NUM = auto() # "1.", "2.", etc.
ACTION = auto() # "Call", "Run", "Check", "Log"
TOOL_NAME = auto() # "start_session", "log_decision"
LPAREN = auto()
RPAREN = auto()
ARG = auto() # argumento entre parenteses
ARROW = auto() # "->"
RESULT = auto() # descricao do resultado
NEWLINE = auto()
EOF = auto()
ACTIONS = {'Call', 'Run', 'Check', 'Log', 'Read', 'Write'}
class WorkflowLexer:
"""Lexer para definicoes de workflow do harness.os.
Formato esperado:
1. Call start_session(project_slug) -> session context
2. Run get_rules(context) -> active rules
3. Log log_decision(title, rationale) -> recorded
"""
def __init__(self, source):
self.source = source
self.pos = 0
def peek(self):
return self.source[self.pos] if self.pos < len(self.source) else '\0'
def advance(self):
ch = self.source[self.pos]
self.pos += 1
return ch
def tokenize(self):
tokens = []
while self.pos < len(self.source):
while self.peek() in ' \t':
self.advance()
if self.peek() == '\0':
break
if self.peek() == '\n':
self.advance()
tokens.append(('NEWLINE', '\\n'))
elif self.peek().isdigit():
num = ''
while self.peek().isdigit():
num += self.advance()
if self.peek() == '.':
self.advance()
tokens.append(('STEP_NUM', num))
else:
tokens.append(('ARG', num))
elif self.peek().isalpha():
word = ''
while self.peek().isalnum() or self.peek() == '_':
word += self.advance()
if word in ACTIONS:
tokens.append(('ACTION', word))
else:
tokens.append(('TOOL_NAME', word))
elif self.peek() == '(':
self.advance()
arg = ''
while self.peek() != ')' and self.peek() != '\0':
arg += self.advance()
if self.peek() == ')':
self.advance()
tokens.append(('ARG', arg))
elif self.peek() == '-' and self.pos + 1 < len(self.source) and self.source[self.pos+1] == '>':
self.advance(); self.advance()
tokens.append(('ARROW', '->'))
# resto da linha e RESULT
while self.peek() == ' ':
self.advance()
result = ''
while self.peek() != '\n' and self.peek() != '\0':
result += self.advance()
tokens.append(('RESULT', result.strip()))
else:
self.advance()
tokens.append(('EOF', ''))
return tokens
# Testar
workflow = """1. Call start_session(project_slug) -> session context loaded
2. Run get_rules(context) -> active rules returned
3. Log log_decision(title, rationale) -> decision recorded"""
lexer = WorkflowLexer(workflow.strip())
for tok in lexer.tokenize():
print(f" {tok[0]:12} {tok[1]}")Resumo
- Um lexer hand-written usa peek/advance para inspecionar caracteres
- O caractere atual determina qual tipo de token ler (dispatch)
- Operadores multi-caractere (==, >=, ->) requerem lookahead
- Strings e comentarios precisam de tratamento especial (escape, aninhamento)
- Bons lexers reportam erros com localizacao (linha, coluna) e tentam recuperar
Exercicio
Implemente um lexer Python que tokenize definicoes de workflow em YAML. O lexer deve reconhecer: numeros de step, acoes (Call, Run, Check, Log), nomes de tools MCP, argumentos, setas (->), e descricoes de resultado. Teste com pelo menos 5 steps diferentes.
Verifique seu entendimento
Qual tecnica permite que um lexer hand-written distinga entre "=" (atribuicao) e "==" (comparacao)?