Compilador G-V1

Compilador didático para a linguagem G-V1, uma linguagem imperativa simples com palavras-chave em português. Implementa o pipeline completo: análise léxica → sintática → AST → semântica → geração de código MIPS Assembly.

Dependências

Linux (Ubuntu/Debian)

sudo apt update
sudo apt install gcc flex bison make default-jre

Linux (Fedora/RHEL)

sudo dnf install gcc flex bison make java-latest-openjdk

Ferramenta	Versão mínima	Função
gcc	9+	Compilar o compilador
flex	2.6+	Gerar o analisador léxico
bison	3.0+	Gerar o analisador sintático
make	4.0+	Automatizar o build
Java (JRE)	8+	Executar o emulador MARS

Emulador MIPS — MARS

O MARS (MIPS Assembler and Runtime Simulator) é necessário para executar os arquivos .s gerados pelo compilador.

Baixe o JAR do MARS em: https://courses.missouristate.edu/KenVollmar/MARS/
Salve o arquivo (ex.: MARS_4_5.jar) em um diretório de sua preferência.
Execute via terminal:

java -jar MARS_4_5.jar

Ou abra a interface gráfica clicando duas vezes no JAR (requer JRE instalado).

Build

cd compiladores/g-v1_files
make

O executável g-v1 será gerado na mesma pasta.

Uso

# Verificar erros léxicos, sintáticos e semânticos
./g-v1 programa.g

# Exibir a AST
./g-v1 --ast programa.g

# Exibir a tabela de símbolos
./g-v1 --symtab programa.g

# Gerar assembly MIPS na saída padrão
./g-v1 --code programa.g

# Salvar assembly MIPS em arquivo
./g-v1 -o programa.s programa.g

Exemplo completo: compilar e rodar no MARS

./g-v1 -o saida.s tests/validos/example/fatorial.g
java -jar Mars45.jar nc saida.s

Para programas com entrada interativa, redirecione um arquivo de input:

java -jar Mars45.jar nc saida.s < entrada.txt

Testes

Todos os testes ficam em compiladores/g-v1_files/tests/, organizados por categoria.

tests/
├── validos/
│   ├── example/    # Programas válidos (.g)
│   └── correct/    # Assembly esperado (.s)
├── lexicos/
│   ├── example/    # Programas com erros léxicos (.g)
│   └── correct/    # Saída de erro esperada (.out)
├── sintaticos/
│   ├── example/    # Programas com erros sintáticos (.g)
│   └── correct/    # Saída de erro esperada (.out)
├── semanticos/
│   ├── example/    # Programas com erros semânticos (.g)
│   └── correct/    # Saída de erro esperada (.out)
└── structures/
    ├── example/    # Testes de AST, symtab e codegen (.g)
    └── correct/    # Saídas esperadas (.out / .s)

Executar os testes

make test-all        # Todos os testes
make test-valid      # Programas válidos (compara assembly gerado)
make test-lex        # Erros léxicos
make test-syntax     # Erros sintáticos
make test-semantic   # Erros semânticos
make test-ast        # Saída da AST
make test-symtab     # Tabela de símbolos
make test-codegen    # Geração de código MIPS
make test-invalid    # Apenas léxico + sintático + semântico

Limpeza

make clean

Remove o executável, objetos e arquivos gerados pelo Flex/Bison.

Linguagem G-V1 — resumo rápido

principal
{
    x: int;
    c: car;
}
{
    leia x;
    se (x > 0) entao
        escreva "positivo";
    senao
        escreva "nao positivo";
    fimse
    novalinha;
}

Elemento	Sintaxe
Tipos	`int`, `car`
Entrada	`leia x`
Saída	`escreva expr` / `escreva "texto"`
Quebra de linha	`novalinha`
Condicional	`se (...) entao ... senao ... fimse`
Laço	`enquanto (...) cmd`
Comentário	`/* ... */`

Documentação técnica

1. Visão geral do compilador

O projeto implementa um compilador didático para a linguagem G-V1. O fluxo geral é este:

O usuário executa ./g-v1 arquivo.g.
O main, definido no arquivo g-v1.y, processa as opções de linha de comando.
O parser (yyparse) começa a analisar o arquivo fonte.
Durante o parsing, o analisador léxico (yylex), gerado a partir de g-v1.l, reconhece tokens.
As ações semânticas do Bison montam a AST usando as funções de ast.c.
Depois do parsing, o compilador executa a análise semântica em semantic.c.
Se não houver erro, o compilador pode:
- imprimir a AST (--ast),
- imprimir os escopos/tabela de símbolos (--symtab),
- gerar assembly MIPS (--code ou -S).
A geração de código é feita em codegen.c.

Os blocos principais do projeto são:

g-v1.l: léxico
g-v1.y: sintático + AST + main
ast.[ch]: estrutura da árvore sintática abstrata
symtab.[ch]: pilha de tabelas de símbolos
semantic.[ch]: checagem semântica
codegen.[ch]: geração de código MIPS
Makefile: build e testes
tests/: suíte de validação

2. Arquitetura lógica do projeto

2.1. Léxico

O léxico transforma caracteres em tokens. Exemplos:

principal → token PRINCIPAL
x → token IDENTIFICADOR
123 → token INTCONST
'a' → token CARCONST
"abc" → token CADEIACARACTERES

Também detecta erros como caractere inválido, comentário não encerrado e string que atravessa linha.

2.2. Sintático

O parser verifica se a sequência de tokens obedece à gramática da G-V1. Ao mesmo tempo, constrói a AST: o parser não só diz "está certo" ou "está errado"; ele também cria uma representação estruturada do programa.

2.3. AST

A AST representa o programa de forma mais compacta do que a árvore sintática concreta. Ela guarda:

tipo de nó (AST_IF, AST_ASSIGN, AST_IDENT etc.);
linha do fonte;
tipo semântico quando disponível (int, car);
lexema quando necessário;
ponteiros para filhos e próximo nó da lista.

2.4. Tabela de símbolos

A tabela de símbolos controla escopos. Como a linguagem permite blocos aninhados, um identificador pode existir em um escopo externo e outro com o mesmo nome em um bloco interno. A estrutura foi implementada como pilha de escopos.

2.5. Semântica

A análise semântica verifica regras que a gramática sozinha não consegue garantir:

uso de variável não declarada;
redeclaração no mesmo escopo;
tipos incompatíveis em atribuição;
uso de car em operação aritmética;
operação lógica com tipos errados.

2.6. Geração de código

Depois que o programa passa pela semântica, o compilador percorre a AST e emite assembly MIPS:

alocação de variáveis locais na pilha;
leitura e escrita;
avaliação de expressões;
emissão de labels para if e while;
suporte a blocos e escopos aninhados;
seção .data para strings.

3. Arquivo `g-v1.l`

3.1. Função do arquivo

g-v1.l é a especificação do Flex. Ele define como o analisador léxico reconhece os tokens da linguagem.

3.2. Opções do Flex

%option noyywrap yylineno noinput nounput

noyywrap: evita precisar implementar yywrap.
yylineno: o Flex controla o número da linha atual.
noinput e nounput: evitam geração de funções auxiliares não usadas.

3.3. Bloco `%{ ... %}`

Inclui stdio.h, stdlib.h, string.h e g-v1.tab.h. Define a macro YY_USER_ACTION, que preenche yylloc com a linha atual a cada token reconhecido. Guarda comment_start_line e string_start_line para apontar a linha correta nos erros.

3.4. Estados léxicos

%x COMMENT STRING

COMMENT: enquanto lê um comentário /* ... */
STRING: enquanto lê uma string "..."

3.5. Macros léxicas

Macro	O que reconhece
`LETRA`	letras ou `_`
`DIGITO`	dígitos
`ID`	identificadores válidos
`INTLIT`	inteiros sem sinal
`CAR_ESC`	escapes como `\n`, `\t`, `\'`, `\\`
`CARACTERE`	literais como `'a'` ou `'\n'`

3.6. Palavras reservadas

principal, int, car, leia, escreva, novalinha, se, entao, senao, fimse, enquanto — cada uma retorna seu token correspondente.

3.7. Operadores compostos

|| → OU, & → E, == → IGUAL, != → DIFERENTE, >= → MAIORIGUAL, <= → MENORIGUAL.

3.8. Literais e identificadores

CARACTERE, INTLIT e ID armazenam o texto bruto em yylval.str. O texto bruto é importante porque o parser usa esse lexema para criar nós da AST.

3.9. Regra de erro genérica

. { lexical_error_at("CARACTERE INVALIDO", yylineno); }

Qualquer caractere não reconhecido cai aqui.

3.10. Funções auxiliares

xstrdup_local: duplica lexemas em memória dinâmica, evitando depender do buffer interno do Flex.
lexical_error_at: imprime a mensagem no formato exato esperado pelos testes e encerra com falha.

4. Arquivo `g-v1.y`

4.1. Função do arquivo

g-v1.y é a especificação do Bison e faz três papéis:

define a gramática da linguagem;
cria a AST durante o parsing;
implementa o main do compilador e integra semântica, AST, tabela e codegen.

4.2. `%union`

O parser manipula três tipos de valores semânticos:

char *str: lexemas vindos do léxico
ASTNode *node: nós da árvore
int type_code: código de tipo (AST_TYPE_INT, AST_TYPE_CAR)

4.3. Variáveis de controle

ast_root: raiz da AST
opt_print_ast: ativa impressão da árvore
opt_print_symtab: ativa impressão dos escopos
opt_emit_code: ativa geração de assembly
opt_output_path: caminho de saída do .s

4.4. Regras da gramática e ações semânticas

Não-terminal	Nó gerado
`DeclPrograma`	`AST_PROGRAM`
`Bloco`	`AST_BLOCK` (child1 = decls, child2 = cmds)
`ListaDeclVar`	lista de `AST_VAR_DECL`
`Comando: SE...FIMSE`	`AST_IF`
`Comando: ENQUANTO`	`AST_WHILE`
`Comando: LEIA`	`AST_READ`
`Comando: ESCREVA`	`AST_WRITE`
`Expr: IDENT = Expr`	`AST_ASSIGN`
`BinaryOp`	`AST_BINARY_OP`
`UnExpr`	`AST_UNARY_OP`

A precedência de operadores é implementada pelos níveis OrExpr → AndExpr → EqExpr → DesigExpr → AddExpr → MulExpr → UnExpr.

4.5. `yyerror`

O parser ignora a mensagem detalhada do Bison e imprime sempre:

ERRO: ERRO SINTATICO <linha>

Isso mantém a saída exatamente como a suíte de testes espera.

4.6. `main` — fluxo

lê as opções com parse_cli;
abre o arquivo de entrada em yyin;
chama yyparse();
se bem-sucedido, roda semantic_check;
se a semântica passar: imprime AST / escopos / gera assembly conforme as flags;
libera a AST.

5. Arquivo `ast.h` / `ast.c`

5.1. `ASTKind` — 16 tipos de nós

AST_PROGRAM, AST_BLOCK, AST_VAR_DECL, AST_EMPTY_STMT, AST_ASSIGN, AST_READ, AST_WRITE, AST_NEWLINE, AST_IF, AST_WHILE, AST_BINARY_OP, AST_UNARY_OP, AST_IDENT, AST_INT_CONST, AST_CHAR_CONST, AST_STRING_LITERAL.

5.2. `ASTDataType`

AST_TYPE_INVALID
AST_TYPE_INT
AST_TYPE_CAR

5.3. `struct ASTNode`

typedef struct ASTNode {
    ASTKind      kind;
    int          line;
    ASTDataType  data_type;
    char        *lexeme;
    struct ASTNode *child1, *child2, *child3;
    struct ASTNode *next;   // encadeamento de listas
} ASTNode;

O campo next é fundamental porque várias listas da AST (declarações, comandos) são listas ligadas.

5.4. Funções principais

Função	Descrição
`ast_new`	função-base de criação de nós
`ast_make_*`	construtores específicos para cada tipo de nó
`ast_append`	concatena listas encadeadas
`ast_build_decl_list`	transforma `IDENT(x)->IDENT(y)` em `VAR_DECL(x:int)->VAR_DECL(y:int)`
`ast_print`	imprime a árvore textualmente
`ast_free`	libera recursivamente toda a memória

6. Arquivo `symtab.h` / `symtab.c`

6.1. Estruturas

typedef struct SymbolEntry {
    char *name;
    ASTDataType type;
    int decl_line, scope_level, scope_id;
    struct SymbolEntry *next;
} SymbolEntry;

typedef struct ScopeFrame {
    int scope_id, level;
    SymbolEntry *symbols;
    struct ScopeFrame *next;
} ScopeFrame;

typedef struct SymbolTableStack {
    ScopeFrame *top;
    int size, next_scope_id;
} SymbolTableStack;

6.2. Funções principais

Função	Descrição
`symtab_init`	inicializa a pilha vazia
`symtab_push_scope`	empilha novo escopo (id único, nível = tamanho atual)
`symtab_pop_scope`	remove o escopo do topo e libera seus símbolos
`symtab_insert`	insere variável no escopo atual; rejeita redeclaração
`symtab_lookup_current`	procura apenas no escopo do topo (detecta redeclaração)
`symtab_lookup`	procura do topo até a base (implementa escopo léxico / shadowing)
`symtab_print_stack`	imprime todos os escopos no formato esperado pelos testes
`symtab_dump_from_ast`	reconstrói e imprime escopos percorrendo a AST

6.3. Como o shadowing funciona

symtab_lookup começa do topo da pilha. O identificador do escopo mais interno é encontrado antes do externo.

7. Arquivo `semantic.h` / `semantic.c`

7.1. Interface pública

int semantic_check(ASTNode *root);

Retorna 1 se o programa é semanticamente válido, 0 se houver erro.

7.2. `SemanticContext`

Agrupa estado interno: pilha de símbolos e flag error_reported para parar na primeira violação detectada.

7.3. Regras verificadas

Regra	Erro emitido
Variável usada sem declaração	`IDENTIFICADOR NAO DECLARADO`
Variável declarada duas vezes no mesmo escopo	`IDENTIFICADOR JA DECLARADO`
Atribuição com tipos incompatíveis	`TIPOS INCOMPATIVEIS`
Aritmética com `car`	`OPERACAO ARITMETICA REQUER INT`
Lógica com `car`	`OPERACAO LOGICA REQUER INT`
Relacional entre tipos diferentes	`TIPOS INCOMPATIVEIS`

7.4. Anotação de tipos

analyze_identifier_use copia o tipo da entrada da tabela para node->data_type. Isso é importante porque a geração de código consulta esse campo para escolher a syscall correta de I/O.

7.5. Fluxo em `analyze_block`

empilha escopo;
analisa declarações;
analisa comandos;
desempilha escopo.

Isso faz a tabela de símbolos acompanhar corretamente blocos aninhados.

8. Arquivo `codegen.h` / `codegen.c`

8.1. Interface pública

int codegen_emit(FILE *out, const ASTNode *root);

Recebe um FILE * porque a saída pode ir tanto para stdout quanto para um arquivo .s.

8.2. Estruturas internas

Estrutura	Descrição
`CGVar`	variável com `name`, `type`, `offset` relativo ao `$fp`
`CGScope`	escopo com `alloc_bytes` e lista de `CGVar`
`StringLiteralEntry`	tabela de strings com label para a seção `.data`
`CodegenContext`	estado global: arquivo de saída, pilha de escopos, contadores de labels

8.3. Alocação de variáveis

Cada declaração:

soma 4 bytes ao escopo atual e ao frame_bytes total;
emite addiu $sp, $sp, -4;
inicializa a posição com zero;
cria CGVar com offset = -frame_bytes.

O offset negativo relativo a $fp funciona porque o frame cresce para baixo na pilha.

8.4. Avaliação de expressões — pilha temporária

Para expressões binárias:

gera filho esquerdo em $v0 e empilha (push_eval);
gera filho direito em $v0;
desempilha para $t0 (pop_eval_to);
combina $t0 e $v0.

8.5. Operadores binários emitidos

Operador	Instrução MIPS
`+`	`addu`
`-`	`subu`
`*`	`mul`
`/`	`div` + `mflo`
`\|\|`	normaliza com `sltu` + `or`
`&`	normaliza com `sltu` + `and`
`==`	`xor` + `sltiu`
`!=`	`xor` + `sltu`
`<`	`slt`
`>`	`slt` invertendo operandos
`<=`	`slt` + `xori 1`
`>=`	`slt` invertido + `xori 1`

8.6. Syscalls de I/O

Operação	Syscall
`escreva` (int)	1
`escreva` (string)	4
`leia` (int)	5
encerramento	10
`escreva` (car)	11
`leia` (car)	12

8.7. Controle de fluxo

AST_IF: gera labels else_N e endif_N; salta para else_N se condição for zero.
AST_WHILE: gera labels while_begin_N e while_end_N; volta ao início após o corpo.

8.8. Fluxo de `codegen_emit`

coleta strings da AST;
emite .data com as strings;
emite .text e main:;
inicializa move $fp, $sp;
gera o bloco principal;
emite syscall 10 (encerramento).

9. Descrição dos testes

9.1. Programas válidos (`tests/validos/`)

Cada programa é compilado com --code e o assembly gerado é comparado com o arquivo .s em correct/.

Arquivo	O que valida
`fatorial.g`	laço `enquanto`, operações aritméticas, I/O de inteiro
`nota_em_conceito.g`	`se/senao/fimse` aninhados, escopos com `car`
`pa.g`	progressão aritmética, blocos aninhados, I/O
`seq_ordenada.g`	sequência ordenada, escopos aninhados dentro de `enquanto`
`soma.g`	soma de progressão aritmética, bloco aninhado
`media.g`	média de N números, declaração dentro de `enquanto`
`mdc.g`	máximo divisor comum (algoritmo de Euclides)
`fibonacci.g`	n-ésimo termo da sequência de Fibonacci
`par_impar.g`	verificação de paridade com expressão aritmética
`potencia.g`	potenciação por multiplicações sucessivas

9.2. Erros léxicos (`tests/lexicos/`)

Arquivo	Erro validado
`invalid_lex_01_caractere.g`	`CARACTERE INVALIDO` — símbolo `@`
`invalid_lex_02_comment.g`	`COMENTARIO NAO TERMINA` — `/*` sem fechamento
`invalid_lex_03_string.g`	`CADEIA DE CARACTERES OCUPA MAIS DE UMA LINHA`

9.3. Erros sintáticos (`tests/sintaticos/`)

Arquivo	Erro validado
`invalid_syn_01_missing_semicolon.g`	`;` faltando depois de atribuição
`invalid_syn_02_missing_fimse.g`	`se/entao` sem `fimse`
`invalid_syn_03_escreva_sem_ponto_virgula.g`	`;` faltando depois de `escreva`
`invalid_syn_04_nota_abre_chaves.g`	`{` faltando para iniciar bloco de comandos
`invalid_syn_05_nota_decl_sem_chaves.g`	declaração fora de bloco após `entao`
`invalid_syn_06_nota_fecha_chaves.g`	`}` faltando para fechar bloco de comandos
`invalid_syn_07_nota_fimse_faltando.g`	`fimse` faltando em `se` aninhado
`invalid_syn_08_nota_ponto_virgula.g`	`;` faltando após `escreva "string"`

9.4. Erros semânticos (`tests/semanticos/`)

Arquivo	Erro validado
`invalid_sem_01_undeclared.g`	uso de variável não declarada
`invalid_sem_02_redecl_same_scope.g`	declaração duplicada no mesmo bloco
`invalid_sem_03_assign_type.g`	`int = car` — tipos incompatíveis
`invalid_sem_04_arith_requires_int.g`	`car + car` — aritmética requer `int`
`invalid_sem_05_relational_mismatch.g`	`int == car` — relacional entre tipos diferentes
`invalid_sem_06_logic_requires_int.g`	`car & car` — lógica requer `int`
`invalid_sem_07_fatorial.g`	variável `i` usada sem declaração em programa de fatorial
`invalid_sem_08_redecl_fatorial.g`	variável `fatorial` redeclarada no mesmo escopo
`invalid_sem_09_nota_tipos_incompativeis.g`	comparação `int < car` em relacional
`invalid_sem_10_nota_atrib_tipo_incompativel.g`	atribuição `car = int`
`invalid_sem_11_nota_conceito_fora_escopo.g`	variável usada fora do escopo onde foi declarada

9.5. Testes de estruturas internas (`tests/structures/`)

AST

Arquivo	O que valida
`ast_01_assign.g`	nós `AST_ASSIGN` e `AST_WRITE`
`ast_02_control.g`	nós `AST_WHILE` e `AST_IF` aninhados

Tabela de símbolos

Arquivo	O que valida
`symtab_01_nested.g`	dois escopos distintos, nível e linha da declaração
`symtab_02_empty_scope.g`	escopo vazio (imprime `<vazio>`)

Geração de código

Arquivo	O que valida
`codegen_01_assign_write.g`	alocação, atribuição, syscall de escrita de inteiro
`codegen_02_if_else.g`	seção `.data`, labels `if/else`, syscall de escrita de string
`codegen_03_nested_scope.g`	offsets `$fp` em escopos aninhados, desalocação correta

10. Pontos fortes do projeto

Separação por fases: cada fase do compilador está em um módulo distinto.
AST limpa: compacta e reutilizável em semântica e codegen.
Tabela de símbolos por pilha: combina bem com blocos aninhados e shadowing.
Semântica independente do parser: testável com ASTs construídas à mão.
Codegen desacoplado: também pode ser testado a partir de AST pronta.
Suíte de testes por fase: facilita depuração e demonstra robustez por camada.

11. Perguntas frequentes

Por que usar next na AST? Várias partes da árvore representam listas (comandos, declarações). Em vez de criar um nó "lista", foi mais simples encadear nós homogêneos.

Por que guardar line em cada nó? Para que erros semânticos possam apontar a linha correta mesmo depois que o parser já terminou.

Como o shadowing funciona? symtab_lookup começa do topo da pilha; o identificador do escopo mais interno é encontrado antes do externo.

Por que o parser já cria a AST? Elimina uma fase extra de reconstrução. O próprio reconhecimento sintático monta a representação intermediária.

Como o codegen sabe o tipo do que está imprimindo? A fase semântica anota data_type nos nós da AST; o codegen consulta esse campo para escolher a syscall correta.

Como variáveis locais são alocadas? Cada declaração reserva 4 bytes na pilha com um offset negativo relativo ao $fp.

Como if e while são gerados? Com labels únicos (else_N, endif_N, while_begin_N, while_end_N) e instruções de desvio (beq, j).

12. Resumo do fluxo (para apresentação)

"O compilador recebe um programa G-V1, faz análise léxica com Flex, análise sintática com Bison, constrói uma AST durante o parsing, percorre essa AST para fazer análise semântica com apoio de uma pilha de tabelas de símbolos e, se o programa for válido, percorre a AST novamente para gerar código MIPS. O projeto também tem uma suíte de testes por fase, cobrindo léxico, sintaxe, semântica, AST, escopos e geração de código."

Name		Name	Last commit message	Last commit date
compiladores/g-v1_files		compiladores/g-v1_files
.gitignore		.gitignore
Mars45.jar		Mars45.jar
README.md		README.md
explicacao.md		explicacao.md

Latest commit

History

Folders and files

Repository files navigation