if688

Tutorial de Implementação - Árvores Sintáticas Abstratas (ASTs)

1) Introdução

Vamos estudar como um programa simples, escrito em um pequeno dialeto de BASIC, é processado pelo analisador léxico (lexer) e analisador sintático (parser), produzindo uma árvore sintática abstrata (AST).

A linguagem é propositalmente simples, mas já contém:

Declarações de variáveis e tipos;
Comandos de entrada (INPUT) e saída (PRINT);
Atribuições (LET);
Estruturas de controle (IF, WHILE);
a blocos de código (BEGIN/ENDPROGRAM).

2) Exemplos de Programas

Exemplo 1 — Comparação de número

PROGRAM outronome BEGIN
  PRINT "Type a number"
  DECL num : INT
  INPUT num
  IF num > 100 THEN
    PRINT "Maior que 100"
  ENDIF
ENDPROGRAM

Exemplo 2 — Sequência de Fibonacci

PROGRAM fibonacci BEGIN
  PRINT "How many fibonacci numbers do you want?"
  DECL nums : INT
  INPUT nums
  DECL a : INT
  DECL b : 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

Esses dois programas serão nossa referência para entender como cada comando é reconhecido pelo lexer, interpretado pelo parser e representado na AST.

3) O papel do Lexer e do Parser

Lembre-se que o papel do Lexer é transformar o texto em uma sequência de tokens, que são as palavras da linguagem (como PROGRAM, IDENTIFICADOR, NUMERO, IF, THEN, EQ, PLUS, etc.).

O parser, então, lê esses tokens e constrói uma árvore — a AST — que mostra a estrutura lógica do programa.

Ideia geral: Fonte → Tokens → Árvore Sintática (AST)

Por exemplo, a linha:

LET c = a + b * 2

é transformada nos tokens:

LET | IDENT(c) | EQ(=) | IDENT(a) | PLUS(+) | IDENT(b) | ASTERISK(*) | NUMERO(2)

e vira a seguinte AST:

LetStmt
 ├── id: "c"
 └── exp: SumExpr
       ├── left: IdExpr("a")
       └── right: MulExpr(IdExpr("b"), NumExpr(2))

Observe que a árvore já reflete a precedência: a multiplicação (*) é avaliada antes da adição (+).

4) Estrutura da AST: nós e significados

Cada construção da linguagem vira um nó de uma árvore, com subclasses que representam comandos (Stmt, do inglês statements) e expressões (Expr).

4.1 Estrutura geral

Categoria	Exemplo de código	Nó da AST
Programa	`PROGRAM fibo BEGIN ... ENDPROGRAM`	`Program(name, stmts)`
Comando de saída	`PRINT "Type a number"`	`PrintStmt(StringExpr("Type a number"))`
Declaração	`DECL num : INT`	`VarDeclStmt("num", "INT")`
Leitura	`INPUT num`	`InputStmt("num")`
Atribuição	`LET a = 0`	`LetStmt("a", NumExpr(0))`
Condicional	`IF num > 100 THEN ... ENDIF`	`IfStmt(cond, body)`
Laço	`WHILE nums > 0 REPEAT ... ENDWHILE`	`WhileStmt(cond, body)`

4.2 Estrutura do programa

O programa completo é um nó Program:

Program(
  name = "fibonacci",
  stmts = [ PrintStmt(...), VarDeclStmt(...), InputStmt(...), ... ]
)

Cada comando aparece em ordem dentro de stmts.

4.3 Comandos

1. PRINT

PRINT "How many fibonacci numbers do you want?"

AST:

PrintStmt( StringExpr("How many fibonacci numbers do you want?") )

2. DECL

DECL nums : INT

AST:

VarDeclStmt("nums", "INT")

3. INPUT

INPUT nums

AST:

InputStmt("nums")

4. LET

LET nums = nums - 1

AST:

LetStmt("nums",
  SubExpr(IdExpr("nums"), NumExpr(1))
)

5. IF / THEN / ENDIF

IF num > 100 THEN
  PRINT "Maior que 100"
ENDIF

AST:

IfStmt(
  cond = GreaterThanExpr(IdExpr("num"), NumExpr(100)),
  body = [ PrintStmt(StringExpr("Maior que 100")) ]
)

6. WHILE / REPEAT / ENDWHILE

WHILE nums > 0 REPEAT
  PRINT a
  LET c = a + b
  LET a = b
  LET b = c
  LET nums = nums - 1
ENDWHILE

AST:

WhileStmt(
  cond = GreaterThanExpr(IdExpr("nums"), NumExpr(0)),
  body = [
    PrintStmt(IdExpr("a")),
    LetStmt("c", SumExpr(IdExpr("a"), IdExpr("b"))),
    LetStmt("a", IdExpr("b")),
    LetStmt("b", IdExpr("c")),
    LetStmt("nums", SubExpr(IdExpr("nums"), NumExpr(1)))
  ]
)

Cada comando dentro do laço aparece como um item na lista body.

4.4 Expressões aritméticas e booleanas

As expressões formam uma hierarquia própria, usada dentro dos comandos.

Tipo de expressão	Exemplo	Nó da AST
Número	`5`	`NumExpr(5)`
Identificador	`x`	`IdExpr("x")`
String literal	`"Hello"`	`StringExpr("Hello")`
Soma	`a + b`	`SumExpr(IdExpr("a"), IdExpr("b"))`
Subtração	`a - b`	`SubExpr(IdExpr("a"), IdExpr("b"))`
Multiplicação	`a * b`	`MulExpr(IdExpr("a"), IdExpr("b"))`
Divisão	`a / b`	`DivExpr(IdExpr("a"), IdExpr("b"))`
Unário	`-a`	`UnaryMinusExpr(IdExpr("a"))`
Igualdade	`x == 10`	`EqualsExpr(IdExpr("x"), NumExpr(10))`
Desigualdade	`x != 0`	`NotEqualsExpr(IdExpr("x"), NumExpr(0))`
Comparação	`x > 100`	`GreaterThanExpr(IdExpr("x"), NumExpr(100))`

5) O analisador léxico (Lexer)

O lexer é responsável por dividir o texto em tokens, identificando palavras-chave, operadores e literais.

Exemplo

Para a linha:

IF num > 100 THEN

O lexer produz a sequência:

Token(IF)
Token(IDENTIFICADOR, "num")
Token(GT, ">")
Token(NUMERO, "100")
Token(THEN)
Token(QUEBRA_LINHA)

Esses tokens são o “vocabulário” que o parser vai usar para reconhecer a estrutura do programa.

6) O analisador sintático (Parser)

O parser percorre os tokens seguindo a gramática da linguagem. Cada função do parser corresponde a uma regra gramatical e constrói nós da AST, usando a estratégia recursive-descent.

Por exemplo o trecho de código a seguir:

def statement(self):
    if self.checkToken(TokenType.PRINT):
        self.match(TokenType.PRINT)
        e = self.expression()
        stm = PrintStmt(e)

Significa que:

Quando o parser lê o token PRINT, ele em seguida lê uma expressão e cria um nó PrintStmt.

A gramática completa é:

program     ::= PROGRAM IDENTIFICADOR BEGIN nl {statement} ENDPROGRAM nl EOF
statement   ::= PRINT expression nl
              | INPUT IDENTIFICADOR nl
              | DECL IDENTIFICADOR ":" TYPE nl
              | LET IDENTIFICADOR "=" expression nl
              | IF expression THEN nl {statement} ENDIF nl
              | WHILE expression REPEAT nl {statement} ENDWHILE nl
expression  ::= equality
equality    ::= comparison { ("==" | "!=") comparison }
comparison  ::= term { ("<" | "<=" | ">" | ">=") term }
term        ::= factor { ("+" | "-") factor }
factor      ::= unary { ("*" | "/") unary }
unary       ::= ("+" | "-") unary | primary
primary     ::= NUMERO | IDENTIFICADOR | STRING_LITERAL

Cada regra chama a próxima — e, no final, as folhas da árvore são literais e identificadores.

7) Montando a AST: o fluxo completo

Para o programa:

PROGRAM outronome BEGIN
  PRINT "Type a number"
  DECL num : INT
  INPUT num
  IF num > 100 THEN
    PRINT "Maior que 100"
  ENDIF
ENDPROGRAM

A árvore principal é:

Program("outronome")
 ├── PrintStmt(StringExpr("Type a number"))
 ├── VarDeclStmt("num", "INT")
 ├── InputStmt("num")
 └── IfStmt
       ├── cond: GreaterThanExpr(IdExpr("num"), NumExpr(100))
       └── body:
            └── PrintStmt(StringExpr("Maior que 100"))

9) Conclusão

Vimos como:

O lexer transforma texto em tokens;
O parser organiza esses tokens segundo a gramática;
A AST representa a estrutura lógica do programa, separando comandos e expressões.

IF688 – Teoria e Implementação de Linguagens Computacionais

Atividade – Modelagem de uma AST em Python para MiniJava

Este exercício tem como objetivo exercitar a modelagem de uma Árvore de Sintaxe Abstrata (AST) em Python para um subconjunto da linguagem MiniJava, com base na mesma gramática utilizada na atividade de recursive-descent parsing.

A ideia é modelar, em Python, a Árvore Sintática Abstrata (AST) de um subconjunto de MiniJava. A AST deve capturar estrutura lógica e semântica, omitindo símbolos puramente sintáticos (chaves, parênteses, ponto-e-vírgula, palavras fixas como public static void, etc.).

Gramática de Referência

A gramática abaixo define um subconjunto da linguagem MiniJava, conforme já visto na atividade anterior:

Program ::= MainClass Classes
MainClass ::= "class" <IDENTIFIER> "{" "public static void main(String[] a) { System.out.println(); } }"
Classes ::= ClassDecl Classes | ϵ
ClassDecl ::= "class" <IDENTIFIER> ClassA
ClassA ::= "extends" <IDENTIFIER> "{" ClassB | "{" ClassB
ClassB ::=  "}"
          | "static" VarDecl ClassB
          | VarDecl ClassB
          | "public" MethodDecl ClassC
ClassC ::=  "}"
          | "public" MethodDecl ClassC
VarDecl ::= Type <IDENTIFIER> ";"
MethodDecl ::= Type <IDENTIFIER> "(" MethodA
MethodA ::= ")" "{" "}"
          | Type <IDENTIFIER> MethodB
MethodB ::= ")" "{" "}"
          | "," Type <IDENTIFIER> MethodB
Type ::= SimpleType ArrayPart
SimpleType ::= "boolean"
          | "float"
          | "int"
          | <IDENTIFIER>
ArrayPart ::= ϵ
          | "[" "]" ArrayPart

Atividade a ser realizada

Você deverá:

Projetar uma estrutura de classes Python para representar a AST da linguagem MiniJava, com base na gramática acima.
- Utilize uma classe por entidade relevante da linguagem (ex: Program, MainClass, ClassDecl, etc.).
- Decida o que deve ou não ser representado na AST. Por exemplo, símbolos como { e ; podem ser omitidos.
- O mecanismo de herança pode ser usado se fizer sentido.
Instanciar manualmente uma AST para o seguinte programa MiniJava de exemplo:

class Main {
    public static void main(String[] a) {
        System.out.println();
    }
}

class Point {
    int x;
    int y;
}

Escrever um pequeno texto comentando as decisões de modelagem que foram tomadas.
- O que você optou por representar ou omitir?
- Como modelou listas, herança e elementos opcionais?
- Houve dificuldades de representar alguma parte da gramática?
- Omissões sintáticas: {}, ;, public, static na assinatura do main, parênteses etc.

Entrega

Você deverá entregar três arquivos até o dia 04/11/25 (23h59), via formulário disponível em https://forms.gle/dJJiqZBet9sAsdwe8:

astminijava.py: sua implementação das classes da AST.
sample_program.py: uma instância manual da AST representando o programa de exemplo.
justificativa.md: um pequeno texto explicando suas decisões de modelagem.

ATENÇÃO!

O foco está na clareza da modelagem e na sua capacidade de justificar as escolhas feitas.
Não é necessário implementar parsing, apenas a estrutura da AST e sua instanciação manual. Se desejar implementar um parser, vide sugestão abaixo.

Atividade Opcional (Integração com a Atividade de Recursive-Descent parsing)

Se desejar ir além, você pode estender o parser recursivo-descendente construído na Atividade 3 de forma que ele, ao invés de apenas aceitar ou rejeitar o programa de entrada, construa e retorne uma instância da AST utilizando as classes desenvolvidas nesta atividade. Essa integração é opcional, mas altamente recomendada para quem deseja reforçar o entendimento do papel do parser como etapa de construção da representação interna do programa como AST.

"""
astminijava.py

Este arquivo deve conter a definição das classes que representam a Árvore de Sintaxe Abstrata (AST)
para o subconjunto da linguagem MiniJava definido na Atividade da disciplina IF688.
"""
from typing import List, Optional

class ASTNode:
    pass

# Exemplo de início de modelagem:
class Program(ASTNode):
    def __init__(self, main_class, classes: List['ClassDecl']):
        self.main_class = main_class
        self.classes = classes

class MainClass(ASTNode):
    def __init__(self, name: str):
        self.name = name

# Continue a modelagem com outras classes da gramática...

Justificativa de Modelagem da AST

Este arquivo deve conter uma explicação clara e objetiva das decisões que você tomou ao modelar a Árvore de Sintaxe Abstrata (AST) para MiniJava.

O que você deve abordar:

Quais elementos da gramática foram representados diretamente como classes na AST? Explique quais você considerou relevantes e por quê.
O que foi omitido na sua modelagem da AST e qual o motivo?
Como você representou listas e elementos opcionais?
Você utilizou herança entre classes da AST? Em caso positivo, explique a motivação.
Houve dificuldades específicas ao tentar representar partes da gramática na AST? Descreva como lidou com esses pontos.

Sinta-se à vontade para incluir diagramas, exemplos ou trechos de código se achar necessário.

"""
sample_program.py

Este arquivo deve conter a criação manual de uma instância da AST
para o programa MiniJava de exemplo fornecido no enunciado da atividade.
"""

from astminijava import *

# Exemplo de instância inicial (incompleto):
program = Program(
    main_class=MainClass("Main"),
    classes=[
        # Adicione aqui o restante...
    ]
)