if688

Tutorial de Implementação — Visitors para Extração e Verificação de Tipos em ASTs

Contexto e objetivo

Neste tutorial, vamos trabalhar com a linguagem BASIC utilizada na aula anterior. O objetivo é aplicar o padrão Visitor para:

Extrair informações da AST (por exemplo, montar uma tabela de símbolos, ou contar declarações de variáveis);
Verificar tipos e garantir a consistência semântica do programa (por exemplo, detectar uso de variáveis não declaradas ou tipos incompatíveis).

Tomaremos como exemplo, mais uma vez, o programa abaixo:

PROGRAM fibonacci BEGIN
  PRINT "How many fibonacci numbers do you want?"
  DECL nums : INT
  INPUT nums
  DECL a : INT
  DECL b : INT
  DECL c : INT
  LET a = 0
  LET b = 1
  WHILE nums > 0 REPEAT
    PRINT a
    LET c = a + b
    LET a = b
    LET b = c
    LET nums = nums - 1
  ENDWHILE
  PRINT b
ENDPROGRAM

🔗 Arquivos-fonte:

AST

Lexer

Parser

Tabela de Símbolos

Visitors

Main

Revisando a AST

A Árvore Sintática Abstrata (AST) é a representação usada para o programa após as fases de análise léxica e sintática. A AST criada para esta pequena linguagem separa comandos (Statements) e expressões (Expressions). Cada construção relevante da linguagem possui uma classe própria.

Estrutura principal: `Program`

class Program(object):
    def __init__(self,name,ls):
        self.name = name   # nome do programa
        self.stmts = ls    # lista de Stmt (comandos)

No exemplo do fibonacci, o nó raiz Program contém:

name = "fibonacci"
stmts: lista de objetos (nós da AST) com os comandos do programa, na ordem em que aparecem (PRINT, DECL, INPUT, WHILE, etc.)

Comandos (`Stmt`)

A classe base Stmt serve de superclasse para todos os tipos de comandos:

class Stmt(object):
    pass

Impressão (`PrintStmt`)

class PrintStmt(Stmt):
    def __init__(self, exp):
        self.exp = exp   # expressão a ser impressa

Leitura (`InputStmt`)

class InputStmt(Stmt):
    def __init__(self, nome):
        self.id = nome # nome da variável que recebe entrada do usuário

Declaração de variável (`VarDeclStmt`)

class VarDeclStmt(Stmt):
    def __init__(self, nome, t):
        self.id = nome # nome da variável declarada (identificador)
        self.type = t # tipo da variável declarada

Atribuição (`LetStmt`)

class LetStmt(Stmt):
    def __init__(self, nome, e):
        self.id = nome # nome da variável atribuída (identificador)
        self.exp = e # expressão a ser avaliada para atribuição da variável

Estruturas de controle (`IfStmt`, `WhileStmt`, `BlockStmt`)

As estruturas IF e WHILE tem o comportamento padrão. A estrutura BLOCK será usada em atividade posterior e permite aninhamento de código, onde teremos a possibilidade de declarar, dentro do bloco, variáveis que já foram declaradas antes, inclusive associando com outro tipo. Como exemplo veja o arquivo block.basic, que já ilustra um programa correto, mas que não será aceito pelo type-checker ainda, de acordo com a implementação desta aula.

class IfStmt(Stmt):
    def __init__(self, c, corpo):
        self.cond = c
        self.body = corpo

class WhileStmt(Stmt):
    def __init__(self, c, corpo):
        self.cond = c
        self.body = corpo

class BlockStmt(Stmt):
    def __init__(self, nome, corpo):
        self.name = nome
        self.body = corpo

Expressões (`Expr`)

A classe base é:

class Expr(object):
    pass

Expressões atômicas

class IdExpr(Expr):
    def __init__(self, nome):
        self.id = nome

class StringExpr(Expr):
    def __init__(self, s):
        self.str = s

class NumExpr(Expr):
    def __init__(self, valor):
        self.v = valor

Esses nós representam nomes de variáveis, strings (literais) e números inteiros.

Expressões aritméticas

class SumExpr(Expr):
    def __init__(self, left, right):
        self.left = left
        self.right = right

class SubExpr(Expr):
    def __init__(self, left, right):
        self.left = left
        self.right = right

class MulExpr(Expr):
    def __init__(self, left, right):
        self.left = left
        self.right = right

class DivExpr(Expr):
    def __init__(self, left, right):
        self.left = left
        self.right = right

Operadores unários:

class UnaryPlusExpr(Expr):
    def __init__(self, e):
        self.exp = e

class UnaryMinusExpr(Expr):
    def __init__(self, e):
        self.exp = e

Expressões booleanas

class EqualsExpr(Expr):
    def __init__(self, left, right):
        self.left = left
        self.right = right

class GreaterThanExpr(Expr):
    def __init__(self, left, right):
        self.left = left
        self.right = right

# ... e assim por diante para NotEquals, LessThan, etc.

Lexer e Parser

Os analisadores léxico e sintático estão prontos e geram a AST automaticamente, conforme já visto em aulas anteriores. O parser é implementado usando a técnica de recursive-descent parsing, com funções para cada um dos símbolos não terminais, retornando instâncias das classes de expressão e comando.

Lexer

Parser

Tabela de Símbolos

Para verificar tipos, precisamos de uma tabela de símbolos. Ela associa nomes a objetos do tipo Symbol.

🔗 Arquivo: SymbolTable

Estrutura básica

Um símbolo consiste de um nome (identificador), um tipo, e opcionalmente, um valor (para o caso de construirmos um interpretador).

class Symbol(object):
    def __init__(self, n, t=None, v=None):
        self.name = n
        self.type = t
        self.value = v

Tipos e variáveis

Separamos em duas classes para distinguir símbolos built-in (int, string, boolean) de símbolos variáveis (nomes de variáveis).

class BuiltInTypeSymbol(Symbol):
    def __init__(self, n):
        super().__init__(n)

class VarSymbol(Symbol):
    def __init__(self, n, t, v=None):
        super().__init__(n, t, v=v)

A tabela em si

class SymbolTable(object):
    def __init__(self):
        self.symbols = {}
        for primitive in ['INT', 'BOOLEAN', 'STRING']:
            self.insert(primitive, BuiltInTypeSymbol(primitive))

    def insert(self, name, data):
        self.symbols[name] = data

    def lookup(self, name):
        return self.symbols.get(name)

Toda tabela começa com INT, BOOLEAN, e STRING já registrados, associados como BuiltInTypeSymbol correspondente.

O padrão Visitor

Queremos percorrer a AST e executar ações dependendo do tipo de nó. Em vez de escrever um monte de if isinstance(node, ...), usamos despacho dinâmico (dynamic dispatch): o método a ser chamado é inferido automaticamente pelo nome da classe.

Classe base `NodeVisitor`

class NodeVisitor(object):
    def visit(self, node):
        method_name = 'visit_' + type(node).__name__
        visitor = getattr(self, method_name, self.generic_visit)
        return visitor(node)

    def generic_visit(self, node):
        raise Exception('No visit_{} method'.format(type(node).__name__))

Se o objeto for PrintStmt, o método chamado será visit_PrintStmt. Se não houver método correspondente, chamamos generic_visit, que lança exceção.

`GenericVisitor`: o esqueleto do percurso

Essa classe percorre a AST inteira, mas não faz nada — ela é a base para criar visitors mais específicos.

class GenericVisitor(NodeVisitor):
    def __init__(self, tree):
        self.ast = tree

    def traverse(self):
        self.visit(self.ast)

    def erro(self, msg):
        raise Exception(msg)

Métodos de visita (exemplos)

def visit_Program(self,node):
    for stmt in node.stmts:
        self.visit(stmt)

def visit_PrintStmt(self,node):
    self.visit(node.exp)

def visit_LetStmt(self,node):
    self.visit(node.exp)

def visit_WhileStmt(self,node):
    self.visit(node.cond)
    for stm in node.body:
        self.visit(stm)

E assim por diante para cada tipo de nó. O raciocínio e ideia por trás é de que GenericVisitor é um template. Criamos visitors concretos herdando desta classe e redefinindo apenas o necessário.

Exemplo simples: contar variáveis

Como CountVars herda de GenericVisitor, não precisamos implementar nenhum outro método visit_..., sem prejuízo à corretude. A única coisa que nos interessa, se queremos contar declarações de variáveis, é monitorar o que acontece ao encontrarmos um nó do tipo VarDeclStmt.

class CountVars(GenericVisitor):
    def __init__(self, tree):
        super().__init__(tree)
        self.numVars = 0

    def visit_VarDeclStmt(self, node):
        self.numVars += 1

Como usar:

ast = Parser(Lexer(codigo)).parse()
counter = CountVars(ast)
counter.traverse()
print("Número de variáveis declaradas:", counter.numVars)

Primeira passada: construção da tabela de símbolos

Agora, criamos um visitor que varre o programa e registra todas as variáveis declaradas na tabela de símbolos.

class BuildSymbolTable(GenericVisitor):
    def __init__(self, tree):
        super().__init__(tree)
        self.symbolTable = SymbolTable()

    def buildTable(self):
        self.traverse()
        return self.symbolTable

    def visit_VarDeclStmt(self, node):
        nome = node.id
        if self.symbolTable.lookup(nome) is not None:
            self.erro('Variável ' + nome + ' já foi declarada.')
        tipo = self.symbolTable.lookup(node.type)
        simbolo = VarSymbol(nome, tipo)
        self.symbolTable.insert(nome, simbolo)

Segunda passada: verificação de tipos

Usamos agora um novo visitor para verificar consistência de tipos e declarações.

class TypeCheckVisitor(GenericVisitor):
    def __init__(self, tree):
        super().__init__(tree)
        builder = BuildSymbolTable(tree)
        self.symbolTable = builder.buildTable()

    def typecheck(self):
        self.traverse()
        return True

Métodos auxiliares

def INT(self):     return self.symbolTable.lookup('INT')
def BOOLEAN(self): return self.symbolTable.lookup('BOOLEAN')
def STRING(self):  return self.symbolTable.lookup('STRING')

Expressões simples

def visit_NumExpr(self, node):
    return self.INT()

def visit_StringExpr(self, node):
    return self.STRING()

def visit_IdExpr(self,node):
    simbolo = self.symbolTable.lookup(node.id)
    if simbolo is None:
        self.erro(f'variável {node.id} não foi declarada')
    return simbolo.type

Operações aritméticas e booleanas

def visit_SumExpr(self, node):
    tL = self.visit(node.left)
    tR = self.visit(node.right)
    if tL == tR == self.INT():
        return self.INT()
    self.erro(f'Tipos incompatíveis: {tL} e {tR}')

def visit_GreaterThanExpr(self, node):
    tL = self.visit(node.left)
    tR = self.visit(node.right)
    if tL == tR == self.INT():
        return self.BOOLEAN()
    self.erro(f'Tipos incompatíveis: {tL} e {tR}')

Condicionais e laços

def visit_IfStmt(self, node):
    t = self.visit(node.cond)
    if t != self.BOOLEAN():
        self.erro('Condição do IF deve ser booleano')
    for stm in node.body:
        self.visit(stm)

def visit_WhileStmt(self, node):
    t = self.visit(node.cond)
    if t != self.BOOLEAN():
        self.erro('Condição do WHILE deve ser booleano')
    for stm in node.body:
        self.visit(stm)

Atribuições e entrada

def visit_LetStmt(self, node):
    simbolo = self.symbolTable.lookup(node.id)
    if simbolo is None:
        self.erro(f'Variável não foi declarada: {node.id}')
    tVar = simbolo.type
    tExp = self.visit(node.exp)
    if tVar != tExp:
        self.erro(f'Tipos incompatíveis em LET: {tVar} e {tExp}')

def visit_InputStmt(self, node):
    if self.symbolTable.lookup(node.id) is None:
        self.erro(f'variável {node.id} não foi declarada')

Arquivo completo: visitor.py

9️⃣ Testando: verificação do programa `fibonacci`

Código de teste

# main_typecheck.py
from lexer import Lexer
from parser import Parser
from visitor import TypeCheckVisitor

codigo = """PROGRAM fibonacci BEGIN
  PRINT "How many fibonacci numbers do you want?"
  DECL nums : INT
  INPUT nums
  DECL a : INT
  DECL b : INT
  DECL c : INT
  LET a = 0
  LET b = 1
  WHILE nums > 0 REPEAT
    PRINT a
    LET c = a + b
    LET a = b
    LET b = c
    LET nums = nums - 1
  ENDWHILE
  PRINT b
ENDPROGRAM
"""

ast = Parser(Lexer(codigo)).parse()
checker = TypeCheckVisitor(ast)
print("Type check:", checker.typecheck())

Saída esperada

Type check: True

Se alterarmos o código para, por exemplo:

LET a = "x"

A saída será:

Exception: Tipos incompatíveis em LET: <<INT>> e <<STRING>>

Atenção

Mantenha o Visitor imutável (não altere a AST durante a visita).
Teste com programas curtos e erros intencionais.
Não se esqueça de inserir os tipos primitivos antes das variáveis.
Evite comparar tipos por string ('INT'); compare objetos Symbol.

Praticar para a aula de hoje (discutir na aula de 04/11/2025)

Completar a implementação das demais operações aritméticas e booleanas;
Permitir STRING + STRING;
Adicionar TRUE e FALSE como literais booleanos.