Pascal Compiler & Virtual Machine

A modern C++20 implementation that compiles Pascal source code to bytecode and executes it via a stack-based virtual machine.

Project Overview

This project implements a complete Pascal compiler and stack-based virtual machine. The compiler translates Pascal source code into custom bytecode, which is then executed by a custom VM. The implementation follows modern C++20 practices with a focus on separation of concerns, and educational value.

Current Version: 0.1.0
License: MIT License (see LICENSE.txt)

Design Philosophy

• Modular Architecture: Compiler pipeline divided into distinct phases (Lexing, Parsing, Semantics, Code Generation)
• Type Safety: Comprehensive type checking and semantic analysis before code generation
• Modern C++20: Leveraging latest C++ features for cleaner, safer code
• Educational Focus: Clear structure suitable for learning compiler design and implementation
• Testing: Comprehensive unit tests for both compiler and VM components

Features

Language Features

Basic Types

• Int: Integer type for arithmetic operations
• Real: Floating-point numbers for precise calculations
• Char: Single character values
• Bool: Boolean values (true/false)
• String: String literals for text processing

Complex Types

• Arrays: Multi-dimensional arrays with flexible indexing types
• Records: Structured data types with named fields
• Subranges: Bounded ranges based on ordinal types
• Enumerations: User-defined ordinal types with named values

Control Flow Statements

• if/else: Conditional execution
• case statements: Multi-way branching with constant labels
• while loops: Pre-condition iteration
• repeat/until loops: Post-condition iteration
• for loops: Counted iteration (with to and downto)
• goto with labels: Unconditional jumps for advanced control flow

Functions and Procedures

• Support for both functions (returning values) and procedures
• By-value and by-reference (var) parameters (by values only at the moment)
• Nested function definitions
• Forward declarations

Built-in I/O Operations

• read(): Input for variables of various types
• write(): Output for expressions and literals

Program Structure

• Program header with identifier
• Declaration blocks: labels, constants, types, variables
• Function and procedure definitions
• Main statement block

Implementation Features

• Modern C++20 compilation with CMake build system
• Comprehensive type checking with detailed error messages
• Symbol table management for scoping and name resolution
• Visitor pattern for AST traversal and code generation
• Bytecode generation from AST
• Stack-based virtual machine with 45+ opcodes
• Unit testing with GoogleTest framework
• Error reporting with line and column information

Project Structure

pascal/
├── compiler/
│   ├── src/
│   │   ├── Lexer.cpp/hpp      # Tokenization and token definitions
│   │   ├── Parser.cpp/hpp     # Recursive descent parser
│   │   ├── Ast.cpp/hpp        # Abstract syntax tree nodes with validation
│   │   ├── Semantics.cpp/hpp  # Type checking and symbol management
│   │   ├── Generator.cpp/hpp  # Bytecode code generation
│   │   ├── ValidationUtils.hpp
│   │   ├── Visitor.hpp        # Visitor pattern interfaces
│   │   └── Main.cpp           # Compiler CLI entry point
│   └── tests/                 # Compiler unit tests
├── vm/
│   ├── src/
│   │   ├── vm.cpp/hpp         # Virtual machine implementation
│   │   └── Main.cpp           # VM CLI entry point
│   └── tests/                 # VM unit tests
├── tests/                     # Example Pascal programs
│   ├── hello.pas              # User input with record types
│   ├── calc.pas               # Interactive calculator
│   ├── fib.pas                # Recursive Fibonacci
│   └── adv_calc.pas           # Expression parser
├── CMakeLists.txt             # Build configuration
├── gram.txt                   # Pascal grammar reference
└── LICENSE.txt                # MIT license

Component Descriptions:

• compiler/src/Lexer: Tokenizes source code into lexical tokens with position tracking
• compiler/src/Parser: Recursive descent parser that builds Abstract Syntax Tree from tokens
• compiler/src/Ast: Defines all AST node types representing Pascal expressions/statements
• compiler/src/Semantics: Performs type checking, symbol table construction, and semantic validation
• compiler/src/Generator: Transforms AST into bytecode instructions using visitor pattern
• compiler/src/Visitor: Visitor interfaces for AST traversal and code generation
• vm/src/vm: Stack-based virtual machine that executes bytecode instructions
• gram.txt: Complete Pascal grammar documentation for reference
• tests/: Example Pascal programs demonstrating various language features

Architecture

Compiler Pipeline

┌─────────────────────────────────────────────────────────────┐
│                    Pascal Source Code                        │
│                     (program.pas)                            │
└──────────────────────┬──────────────────────────────────────┘
                       │
                       ▼
┌─────────────────────────────────────────────────────────────┐
│                     Lexer                                    │
│        • Character stream → Token stream                   │
│        • Token: type, value, position                      │
└──────────────────────┬──────────────────────────────────────┘
                       │
                       ▼
┌─────────────────────────────────────────────────────────────┐
│                    Parser                                   │
│        • Recursive descent parser                           │
│        • Tokens → Abstract Syntax Tree (AST)                │
└──────────────────────┬──────────────────────────────────────┘
                       │
                       ▼
┌─────────────────────────────────────────────────────────────┐
│                Semantics Analysis                           │
│        • Symbol table construction                         │
│        • Type checking and validation                       │
└──────────────────────┬──────────────────────────────────────┘
                       │
                       ▼
┌─────────────────────────────────────────────────────────────┐
│                   Code Generator                            │
│        • AST → Bytecode instructions                        │
│        • Instruction: opcode + immediate values             │
└──────────────────────┬──────────────────────────────────────┘
                       │
                       ▼
┌─────────────────────────────────────────────────────────────┐
│                  Bytecode File                              │
│                   (.bin format)                             │
└─────────────────────────────────────────────────────────────┘

Virtual Machine Architecture

┌─────────────────────────────────────────────────────────────┐
│                    Bytecode (.bin)                          │
└──────────────────────┬──────────────────────────────────────┘
                       │
                       ▼
┌─────────────────────────────────────────────────────────────┐
│                   Program Counter (PC)                       ││
│                   ───────►│  ◄─────────│
│                                                            ││
│                   Frame Pointer (FP)                       ││
│                   ───────►│  ◄─────────│
│                                                            ││
│         ┌────────────────────────────────┐                ││
│         │      Runtime Stack             │                ││
│         │  ┌──────────────────────────┐ │                ││
│         │  │  Return Address          │ │                ││
│         │  ├──────────────────────────┤ │                ││
│         │  │  Old Frame Pointer       │ │                ││
│         │  ├──────────────────────────┤ │                ││
│         │  │  Local Variables        │ │                ││
│         │  │  (function parameters)  │ │                ││
│         │  └──────────────────────────┘ │                ││
│         └────────────────────────────────┘                ││
│                                                            ││
│         ┌────────────────────────────────┐                ││
│         │   Opcode Decoder & Executor    │                ││
│         └────────────────────────────────┘                ││
└─────────────────────────────────────────────────────────────┘

Opcode Categories:
├── Stack Operations: PUSH_Q, PUSH_B, POP_Q, POP_B
├── Load/Store:    LOAD_Q, LOAD_B, STORE_Q, STORE_B
├── Arithmetic:    ADD_I, MUL_I, DIV_I, ADD_R, MUL_R, DIV_R
├── Comparison:    CMP_I, CMP_R, CMP_C, LE, LT, EQ, NE, GT, GE
├── Logic:         AND, OR, NOT
├── Control:       JMP, JMP_TRUE, JMP_FALSE, CALL, RET
├── I/O:           READ_I, WRITE_I, WRITE_CONST_S
└── Utility:       HALT, DUPL_Q, DUPL_B, MODSTK

Key Design Patterns

• Visitor Pattern: Used for AST traversal across Expression, Statement, and Selector(field for records and element for arrays) visitors
• Recursive Descent Parser: Grammar rules directly mapped to parsing methods
• RAII: Extensive use of unique_ptr/shared_ptr for resource management (with const PTR* for non-owning processes)
• Single Responsibility: Each component (Lexer/Parser/Semantics/Generator) handles a specific phase

Bytecode Format

• Binary file format with 8-byte size header
• Sequential instruction encoding without alignment
• Opcode format:
  • Opcodes: 1 byte
  • Immediate values: 1 or 8 bytes appended inline
• String literals: Embedded directly with null termination

Building the Project

Prerequisites

• CMake: Version 3.10.0 or higher
• C++ Compiler: GCC 10+, Clang 12+, or MSVC 2019+ with C++20 support
• Git: For cloning the repository

Build Steps

# Clone the repository
git clone <repository-url>
cd pascal

# Create build directory
mkdir build
cd build

# Configure and build
cmake ..
cmake --build .

Available Build Targets

• compiler: Main compiler executable for compiling Pascal source files
• vm: Virtual machine executable for running bytecode files
• unit_tests_compiler: Compiler unit tests (GoogleTest based)
• unit_tests_vm: VM unit tests (GoogleTest based)

Usage Guide

Compiling Pascal Programs

• Basic compilation:

  ./compiler program.pas

  Creates program.bin by default

• Custom output file:

  ./compiler program.pas -o output.bin

• Error reporting: Compiler provides detailed errors with line and column information

Running Compiled Programs

• Execute bytecode:

  ./vm program.bin

• File naming: VM accepts filename with or without .bin extension

Complete Workflow Example

1. Write Pascal code in my_program.pas
2. Compile to bytecode:

   ./compiler my_program.pas

3. Run the compiled program:

   ./vm my_program.bin

4. Troubleshooting: Check compiler output for syntax/semantic errors

Command Line Interface

• Compiler:

  • Expects 1 or 3 arguments: source file (with optional -o output_file)
  • Provides usage hints on error
  • Auto-adds .pas extension if not provided

• VM:

  • Expects exactly 1 argument: bytecode file
  • Auto-adds .bin extension if not provided

Sample Programs

hello.pas (17 lines)

Demonstrates string input via read(), record types with fields, and validation loops with repeat/until.

Features:

• Program structure with const declarations
• var with record containing array and fields
• User I/O with prompts and data reading
• Input validation with boolean logic

Run:

./compiler tests/hello.pas
./vm tests/hello.bin

calc.pas (35 lines)

Interactive calculator supporting arithmetic operations: +, -, *, /.

Features:

• Function definitions with boolean returns
• while loops for user interaction
• case statements for operation selection
• Boolean logic with logical operators

Run:

./compiler tests/calc.pas
./vm tests/calc.bin

fib.pas (18 lines)

Recursive Fibonacci function accepting input from 0-20.

Features:

• Function recursion
• Integer validation with range checks
• Function calls within expressions
• Mathematical computation

Run:

./compiler tests/fib.pas
./vm tests/fib.bin

adv_calc.pas (122 lines)

Mathematical expression parser supporting integers, parentheses, and operator precedence.

Features:

• Arrays for character-to-integer mapping (Should support type-conversion sometime in the future)
• Forward declarations for functions
• Nested functions and procedures
• Comprehensive expression evaluation with precedence
• Lexing and parsing of mathematical expressions
• Infix-to-postfix conversion implementation

Run:

./compiler tests/adv_calc.pas
./vm tests/adv_calc.bin

Each example demonstrates specific language constructs and patterns for Pascal programming.

Testing

Running Test Suite

• Compiler tests only:

  ./unit_tests_compiler

• VM tests only:

  ./unit_tests_vm

Test Coverage

Compiler Tests

• Lexer: Token generation and error handling, identifier recognition, literal parsing
• Parser: AST construction validation, grammar rule compliance, error detection
• Semantics: Type checking and scope management, symbol table construction, error detection

VM Tests

• Opcode execution: Arithmetic, logic, comparison, stack operations
• Stack management: Push, pop, load, store operations
• Function call/return: Frame pointer handling, parameter passing
• I/O operations: Input/output for various types

Language Reference

Grammar Overview

Program Structure:

program := PROGRAM ID ';' block '.'

Declaration Sections:

• Labels: LABEL (INT | ID) { ',' (INT | ID) } ';'
• Constants: CONST NAME '=' constant ';' { NAME '=' constant ';' }
• Types: TYPE NAME '=' type ';' { NAME '=' type ';' }
• Variables: VAR id_list ':' type ';' { id_list ':' type ';' }

Statement Types:

• Simple: assignment, procedure call, goto
• Structured: compound, conditional, repetitive
• Compound: BEGIN statement_sequence END

Expression Syntax:

• Relational: simple_expression [ relational_operator simple_expression ]
• Simple: [ '+' | '-' ] term { addition_operator term }
• Terms: factor { multiplication_operator factor }
• Factors: literals, variables, function calls, parenthesized expressions, unary NOT

Type Categories:

• Basic types: integer types, char, boolean, real
• Structured types: arrays, records
• Subranges: constant '..' constant
• Enumerations: '(' id_list ')'

Supported Opcodes

Arithmetic

• Integer: ADD_I, SUB_I, MUL_I, DIV_I
• Real: ADD_R, SUB_R, MUL_R, DIV_R
• Character: ADD_C, SUB_C, MUL_C, DIV_C

Stack Manipulation

• PUSH_Q, PUSH_B, PUSH_FP, POP_Q, POP_B
• DUPL_Q, DUPL_B, MODSTK

Memory Operations

• LOAD_Q, LOAD_B, STORE_Q, STORE_B

Comparison

• CMP_I, CMP_R, CMP_C, LE, LT, EQ, NE, GT, GE

Logical Operations

• AND, OR, NOT

Control Flow

• JMP, JMP_TRUE, JMP_FALSE, CALL, RET

I/O Operations

• READ_I, READ_R, READ_C, READ_B, READ_S
• WRITE_I, WRITE_R, WRITE_C, WRITE_B, WRITE_S, WRITE_CONST_S

Utility

• C2I (char to int conversion), HALT

Troubleshooting

Debugging Tips

• Enable debug output in VM: Edit vm/src/CMakeLists.txt and set DEBUG_VM=1 Rebuild and run with verbose output

• Low-level bytecode inspection: Use debugger (gdb...) to examine bytecode execution flow Compare expected vs actual instruction sequences

• Validate parsing: Check gram.txt for correct grammar rules Add debug print statements in Parser for rule matching

Development Notes

Extending the Compiler

To add new language features:

1. Tokens: Add to Lexer.hpp in TOKEN_TYPE enum
2. Grammar: Implement parsing rules in Parser.cpp
3. AST: Create node definitions in Ast.hpp/cpp
4. Semantics: Add type checking in Semantics.cpp
5. Generator: Emit bytecode in Generator.cpp
6. Visitor: Implement visitor methods for AST node types

License & Credits

License: MIT License (c) 2025 Anass Serroukh

Full license text available in LICENSE.txt file.

This project implements a comprehensive Pascal compiler and virtual machine designed for educational purposes and demonstrating compiler construction principles using modern C++20 practices.