Skip to content

About

MiniAlgo compiler built with Flex & Bison — lexical analysis, semantic checks, quadruplet IR, multi-pass optimizer, and 8086 Intel/MASM assembly code generation. Includes a GTK3 graphical IDE with syntax highlighting and real-time error reporting.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Repository files navigation

🧠 MiniAlgo Compiler

A full-featured compiler for the MiniAlgo academic language — built with Flex, Bison, and C, featuring lexical analysis, syntax analysis, semantic analysis, quadruplet (IR) generation, optimization, 8086 assembly code generation, and a GTK3 graphical IDE.

🖥️ Screenshots

IDE — Source editor with syntax highlighting (MiniAlgo program): Editor View

📋 Symboles tab — full symbol table with types, scopes, and usage flags: Symboles Tab

🔢 Quadruplets tab — intermediate representation + optimizer statistics: Quadruplets Tab

🚨 Erreurs tab — 8 errors detected (6 semantic + 2 syntactic): Erreurs Tab

💾 Code Objet tab — generated 8086 Intel/MASM assembly (output.asm): Code Objet Tab


📐 Architecture

Compiler Architecture

The compiler follows a classic multi-phase pipeline:

Phase Tool Output
Lexical Analysis Flex (lexer.l) Token stream
Syntax Analysis Bison (parser.y) Parse tree
Semantic Analysis Bison actions Validated AST
IR Generation quadruplets.c Quadruplet table
Optimization optimizer.c Optimized IR
Code Generation codegen.c output.asm (8086)

✨ Features

🔤 Language Support

  • INTEGER and FLOAT scalar types
  • Arrays: INTEGER : T[10]
  • Constants: CONST PI = 3.14
  • Control flow: IF / ELSE, WHILE, FOR
  • I/O: WRITE(x), READ(x), WRITE("string")

🔍 Semantic Analysis (7 rules)

Check Example Error
Undeclared variable Z never declared
Double declaration INTEGER : x, x
Constant modification PI = 9 → ❌
Type mismatch (assign) INTEGER = FLOAT → ❌
Type mismatch (compare) INTEGER > FLOAT → ❌
Division by zero /0 or /CONST_ZERO → ❌
Array bounds T[10] on size-5 array → ❌

⚡ Optimizer

  • Constant Folding — 3 + 4 → 7 at compile time
  • Constant Propagation — replaces variables with known values
  • Algebraic Simplification — x * 1 → x, x + 0 → x
  • Dead Code Elimination — removes unreachable quadruplets

💾 8086 Assembly Generation

Translates quadruplets to Intel/MASM 8086 assembly:

; IF (A > B) { WRITE(A); } ELSE { WRITE(B); }
L9:  MOV AX, A
     MOV BX, B
     CMP AX, BX
     JG  CMP_9_T
     MOV AX, 0
     JMP CMP_9_E
CMP_9_T: MOV AX, 1
CMP_9_E: MOV T1, AX
L10: MOV AX, T1
     CMP AX, 0
     JE L13
L11: MOV AX, A
     CALL PRINT_NUM         ; WRITE(A)
L12: JMP L14
L13: MOV AX, B
     CALL PRINT_NUM         ; WRITE(B)

🔀 Control Flow Graph

After each successful compilation, a CFG is generated in Graphviz DOT format:

Control Flow Graph


📁 Project Structure

projet/
├── lexer.l              # Flex lexer — tokenizer
├── parser.y             # Bison grammar — syntax + semantics + IR
├── src/
│   ├── symbol_table.c   # Hash-table based symbol table (open addressing)
│   ├── quadruplets.c    # Intermediate representation (quadruplets)
│   ├── optimizer.c      # Multi-pass optimizer
│   ├── codegen.c        # 8086 Intel/MASM code generator
│   ├── cfg.c            # Control Flow Graph (Graphviz DOT)
│   └── error_handler.c  # Unified error reporting
├── include/             # Header files
├── tests/
│   ├── test_valid.txt   # Valid program — all constructs
│   └── test_errors.txt  # Invalid program — all 7 semantic errors
├── ui/
│   └── compiler_ui.c    # GTK3 graphical IDE (optional)
├── assets/
│   └── architecture.png
├── output.asm           # Generated 8086 assembly (after compile)
├── cfg.dot / cfg.png    # Control flow graph (after compile)
└── Makefile

🚀 Quick Start

Prerequisites

sudo apt install flex bison gcc make graphviz
# For the UI (optional):
sudo apt install libgtk-3-dev

Build & Run

# Build the compiler
make clean && make

# Run on a test file
./compiler < tests/test_valid.txt

# Run interactively (type code, then Ctrl+D)
./compiler

Terminal Output

Launch the Graphical IDE

cd ui && make && ./compiler_ui

📊 Sample Output

Input Program (test_valid.txt)

PROGRAM Test
DECL
  INTEGER : A, B, i ;
  FLOAT : X ;
  CONST BIGGEST = 10 ;
  CONST PI = 3.14 ;
  INTEGER : T[5] ;
ENDDECL
BEGIN
  A = 5 ;
  B = 3 ;
  IF (A > B) {
    WRITE(A) ;
  } ELSE {
    WRITE(B) ;
  }
  FOR (i : 0 : 1 : 5) {
    A = A + i ;
  }
  WHILE (B < 10) {
    B = B + 1 ;
  }
  WRITE(A) ;
  WRITE(B) ;
END

Symbol Table Output

============================================================
|         TABLE DES SYMBOLES (IDF / CONSTANTES)           |
============================================================
| CODE  | NOM     | TYPE       | VALEUR  | CONST | LIGNE |
============================================================
| IDF   | A       | INTEGER    | NULL    | NON   | 3     |
| IDF   | B       | INTEGER    | NULL    | NON   | 3     |
| IDF   | i       | INTEGER    | NULL    | NON   | 3     |
| IDF   | X       | FLOAT      | NULL    | NON   | 4     |
| CONST | BIGGEST | INTEGER    | 10      | OUI   | 5     |
| CONST | PI      | FLOAT      | 3.14000 | OUI   | 6     |
| ARRAY | T       | INTEGER[5] | NULL    | NON   | 7     |
============================================================

Quadruplets (Intermediate Representation)

| 0  — ( =  , 5   ,   , A  )   ← A = 5
| 1  — ( =  , 3   ,   , B  )   ← B = 3
| 2  — ( >  , A   , B , T1 )   ← T1 = (A > B)
| 3  — ( BZ , 6   , T1,    )   ← if false → jump L6
| 4  — ( WRITE, A ,   ,    )   ← WRITE(A)
| 5  — ( BR , 7   ,   ,    )   ← jump L7
| 6  — ( WRITE, B ,   ,    )   ← WRITE(B)

Semantic Errors Output

Erreur Semantique: ligne 10, element BIGGEST — Division par zero via constante symbolique
Erreur Semantique: ligne 10, element Z       — Utilisation d'une variable non declaree
Erreur Semantique: ligne 18, element A       — Affectation d'un FLOAT a un INTEGER
Erreur Semantique: ligne 21, element /       — Division par zero

🛠️ Makefile Targets

make            # Build compiler binary
make clean      # Remove all generated files
make run        # Build + run on test_valid.txt
cd ui && make   # Build the GTK3 IDE

📐 Symbol Table — Hash Table Design

The symbol table uses open addressing with linear probing for O(1) average-case lookups:

┌─────────────────────────────────────┐
│  Hash("A")  → slot 12  → { A, INTEGER, used=true }
│  Hash("PI") → slot 34  → { PI, FLOAT, const=true, val=3.14 }
│  Hash("T")  → slot 07  → { T, INTEGER[5], array=true }
└─────────────────────────────────────┘

Each entry stores: name, type, value, is_const, is_used, is_initialized, scope, line, col.


⚙️ Compiler Phases — Technical Details

Quadruplet Format

( operator , operand1 , operand2 , result )

Examples:
( =   , 5  ,    , x  )   →  x = 5
( +   , x  , y  , T1 )   →  T1 = x + y
( BZ  , L8 , T1 ,    )   →  if T1 == 0 goto L8
( BGE , L5 , i  , 10 )   →  if i >= 10 goto L5  (FOR loop exit)

8086 Registers Convention

Register Role
AX Primary operand / return value
BX Second operand
CX Loop counter (PRINT_NUM)
DX Remainder / I/O character
SI Buffer pointer (READ_NUM)

DOS Interrupts Used

INT 21h / AH Function
02h Print single character
09h Print $-terminated string
0Ah Buffered keyboard input
4Ch Terminate program

🧪 Test Cases

Test Expected
test_valid.txt ✅ 0 errors, full quadruplets + ASM generated
test_errors.txt ❌ 8 errors detected (all 7 semantic rules + 1 syntax)

👥 Authors

USTHB — Département Informatique
Module : Compilation — M1 IL, 2025–2026
Encadrante : Dr. Ibtisam Ferrahi


📄 License

Academic project — USTHB 2026. All rights reserved.

c-compiler

About

MiniAlgo compiler built with Flex & Bison — lexical analysis, semantic checks, quadruplet IR, multi-pass optimizer, and 8086 Intel/MASM assembly code generation. Includes a GTK3 graphical IDE with syntax highlighting and real-time error reporting.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages