Introduction

This project consists of the implementation of a compiler for the Pascal programming language, developed within the Language Processing course. The compiler translates programs written in Pascal into an intermediate representation and subsequently generates machine code designed to run on the virtual machine provided by the teaching staff.

The compiler implements the traditional phases of a compilation pipeline, namely:

Lexical Analysis: Responsible for converting source code into tokens
Syntactic Analysis (Parsing): Responsible for building the Abstract Syntax Tree (AST)
Semantic Analysis: Performs type checking and structural validation of the program
Code Generation: Produces the intermediate machine code for the target virtual machine

The implementation was developed in Python using the ply (Python Lex-Yacc) library for the lexical and syntactic analysis phases. The compiler supports core Pascal control structures (if-then-else, for, while), arithmetic operations, variables, arrays, and standard function calls like writeln and readln.

Architecture

The compiler follows a modular design, separating responsibilities into distinct components:

tokenizer.py: Implements the lexical analyzer using the lex module from the ply library. It defines the language tokens, including keywords, operators, identifiers, and literals.
pascal_yacc.py: Implements the syntax analyzer, using the defined grammar to construct the Abstract Syntax Tree (AST). Each production rule maps to a dedicated node class in node.py.
node.py: Defines the classes representing AST nodes. Each class implements a generate() method that outputs the corresponding virtual machine code.
symbol_table.py: Implements the symbol table, tracking information about declared variables, arrays, types, and their respective stack offsets in the virtual machine.
main.py: The main coordinator that drives the compilation pipeline: reading the Pascal source file, invoking the parser, and writing the resulting target machine code to an output file.

The compilation pipeline begins by reading the source code, processing it through lexical and syntactic analysis to build the AST, performing semantic checks via the symbol table, and ultimately generating executable code for the virtual machine.

Lexical Analysis

The tokenizer.py module implements the lexical analyzer using PLY's lex. This component splits the raw source code into structured tokens recognizable by the parser.

Supported Tokens:

Keywords: program, var, begin, end, if, then, else, while, for, to, downto, etc.
Data types: integer, boolean, char, real, string, array
Operators: Arithmetic (+, -, *, /), Relational (<, >, <=, >=, =, <>), Logical (and, or, not)
Special symbols: Parentheses, brackets, periods, commas, semicolons, etc.
Identifiers: Variable and program names following Pascal conventions
Literals: Integers, real numbers, strings, characters, and boolean values

Special Handling:

Comments: Stripped by the lexer, supporting both {...} and (*...*) syntax
Whitespace: Ignored by default
Strings and characters: Extracted with surrounding quotes stripped
Case-insensitivity: Configured to treat uppercase and lowercase uniformly, adhering to Pascal specifications
Each token is defined using regular expressions or specific handler functions, ensuring precise identification of language constructs.

Syntactic Analysis (Parsing)

Syntactic analysis is implemented in pascal_yacc.py using PLY (yacc). This component consumes tokens from the lexer to build the Abstract Syntax Tree (AST).

BNF Grammar Definition: Grammar

Supported Grammar Features

The implemented grammar supports:

Basic Pascal program structure: header, variable declarations, and main command block
Variable declarations: primitive types and fixed-size arrays
Arithmetic and logical expressions: with proper operator precedence
Control flow structures: if-then-else, while, for
Built-in function calls: primarily I/O operations (readln, writeln)
Arrays: declaration, indexed access, and element assignment

The axiom (start symbol) of this grammar is the program production.

Key implementation highlights from the grammar:

Left-Recursive Lists

To parse lists of elements efficiently, left recursion was strictly applied because Yacc uses an LALR bottom-up parsing strategy.

For example, the rules for var_declarations and var_declaration apply this pattern; all other list productions (identifiers_list, args_list, etc.) follow the exact same logic:

<var_declarations> -> <var_declarations> <var_declaration>
                     | <var_declaration>

<var_declaration> -> <identifiers_list> ":" <type> ";"

If-Then-Else Blocks

Conditional structures are expressed using the following rules:

<if> -> "IF" <expressionBool> "THEN" <command_list> <else>

<else> -> "ELSE" <command_list>
         | ε

These rules evaluate the conditional expression via expressionBool, followed by the command sequence in command_list. The optional else branch matches either the ELSE token or epsilon (empty).

Although correct, this introduces a classic shift-reduce conflict (dangling else). By default, Yacc resolves shift-reduce conflicts in favor of shifting, which binds the else to the nearest open if, correctly parsing nested conditional structures.

While and For Loops

Loop productions are defined as follows:

for : FOR IDENTIFIER ASSIGN expression to_or_downto expression DO command_list

This production defines the for loop, iterating through a value interval:

FOR: Initiates the loop construct;
IDENTIFIER: Identifies the loop control variable;
ASSIGN: Assignment operator to initialize the control variable;
expression: Expression setting the initial value;
to_or_downto: Helper production determining direction (TO for increment, DOWNTO for decrement);
DO: Marks the start of the body;
command_list: Commands executed during each iteration.

while : WHILE expressionBool DO command_list

This rule defines the while loop, executing a block while a condition remains true. The WHILE token starts the loop, followed by expressionBool defining the loop invariant. The DO token introduces command_list, representing the instructions executed repeatedly.

Binary Operations & Precedence

Binary operations were split into hierarchical rules to prevent grammar ambiguities and enforce operator precedence:

<expressionBool> -> <expression>
                   | <expression> <opRel> <expression>

<opRel> -> "=" | "<>" | "<" | "<=" | ">" | ">="

<expression> -> <term>
               | <expression> <opAd> <term>

<opAd> -> "+" | "-" | "AND"

<term> -> <factor>
         | <term> <opMul> <factor>

<opMul> -> "*" | "/" | "DIV" | "MOD" | "OR"

This hierarchy properly reflects operator precedence: relational operators sit at the top (expressionBool), followed by additive and logical conjunction (expression), and finally multiplicative operations, division, and disjunction (term).

AST Node Construction

Each production rule in the grammar is associated with a constructor function that instantiates the corresponding AST node. For example:

p_program: Instantiates a Program node
p_if: Instantiates an If node with condition, then-block, and else-block
p_while: Instantiates a While node with condition and body
p_for: Instantiates a For node with initialization, direction (to/downto), boundary, and body

Operator precedence is explicitly configured to guarantee that expressions like a + b * c are evaluated in the correct mathematical order (multiplication before addition).

Semantic Analysis

Semantic analysis is performed through coordination between the AST and the symbol table (symbol_table.py). This module tracks all declared variables, their types, and their memory positions on the virtual machine stack.

Implemented Checks

Duplicate variable declaration: Triggers a compile-time error if a variable is declared more than once in the same scope
Type verification: Validates operand types in expressions and assignments
Type compatibility: Handles automatic type promotion (e.g., integer to real) when applicable
Array boundaries: Validates index types and array access expressions

Symbol Table Design

The symbol table uses a symbols dictionary keyed by variable name:

Key: Variable name
Value: A tuple containing:
- For primitive variables: (type, stack_position)
- For arrays: (base_type, stack_position, size)

The stack_pos attribute manages sequential stack allocation. Each primitive variable declaration allocates one slot.

The symbol table tracks:

Variable name
Type (integer, real, string, array, etc.)
Virtual machine stack offset
Array metadata (element type, range, capacity)

When an array is declared, the symbol table calculates the required memory size and reserves a single stack slot for the pointer to the heap-allocated memory block.

Key Operations:

Variable Registration (add):
- Checks for duplicate identifiers and throws an error if already defined.
- For arrays ({'type': 'array', ...}), calculates capacity from range boundaries and reserves a single stack pointer slot.
- For primitive types, normalizes the type identifier and assigns a sequential stack offset.
Stack Position Lookup (get_stack_pos):
- Resolves the stack offset for a given identifier, ensuring valid memory reference generation.
Unused Variable Detection:
- Scans variable usage flags and issues compile-time warnings for variables that were declared but never referenced, helping optimize stack allocation.

Code Generation

Code generation is driven by the generate() method implemented across all AST node classes in node.py. The output targets a stack-based virtual machine instruction set.

Code Generation Properties:

Stack-based architecture: Relies on VM instructions operating on a global stack
Memory allocation: Global variables reside on the stack; arrays are dynamically allocated on the heap
Array manipulation: Uses dedicated instructions (ALLOCN, STOREN, LOADN)
Index normalization: Converts 1-based or arbitrary Pascal index ranges to 0-based virtual machine offsets

Common Instruction Patterns:

Primitive variables: PUSHI, STOREG, PUSHG
Arrays: ALLOCN, PADD, STOREN, LOADN
Arithmetic operations: ADD, SUB, MUL, DIV
Control flow: JZ, JUMP with generated labels

The generated code embeds compile-time type verification warnings and runtime safety checks.

Variable Allocation

Variable declarations are handled dynamically during parsing. When the parser encounters a variable, it registers the identifier and type into the symbol table, which assigns a concrete stack position. Downstream production rules retrieve this stack offset to emit memory access instructions.

Primitive variables are allocated as they are encountered in the program flow, whereas arrays are reserved at the program preamble to ensure heap allocations are completed before execution begins.

AST Nodes

Each syntactic production maps to an AST node class responsible for emitting target bytecode recursively:

BinaryOp: Evaluates binary expressions. Connects left and right sub-expressions with corresponding bytecode instructions (ADD, SUB, MUL, etc.) while verifying type compatibility.
If: Represents conditional branching. Emits conditional jumps (JZ) and generates unique jump labels for then and else blocks.
For: Handles loop counting and boundaries. Generates loop initialization, boundary check (SUP for to, INF for downto), loop body code, and counter step increments.
Array: Handles array allocations (ALLOCN) and indexed element access. Uses PUSHG to put the base address onto the stack and LOADN / STOREN to read/write elements. Also supports string character indexing via CHARAT.
Identifier: Loads variable values onto the stack using PUSHG with the assigned stack offset.
FunctionCall: Manages calls to I/O routines like writeln and readln. For multi-argument write calls, string arguments are concatenated prior to issuing WRITES for clean output.
Literal: Pushes constant integer, float, string, or boolean values directly onto the stack.
Assignment: Stores evaluated expression results into the target variable offset using STOREG.
While: Manages condition evaluation, loop entry jumps, body execution, and backward loop iteration jumps.
Program: The root node of the AST. Emits stack initialization instructions, calls recursive generation across all statement nodes, and finalizes the VM output program.

Optimizations

Constant Folding

For binary operations whose operands are known literals at compile time, the evaluation is calculated directly by the compiler rather than emitting runtime instructions. To support nested expressions (e.g., 5 + 5 + 5), nodes carry an optional compile-time value field. If both sub-nodes have defined values, the operation is folded into a single constant literal.

Redundant Operation Elimination

The compiler detects algebraic identities and eliminates redundant operations, such as x + 0, x * 1, or x * 0, emitting direct values or skipping instruction generation altogether.

Dead Variable Elimination

Variables that are declared but never referenced in executable statements are excluded from stack slot allocation, preventing unnecessary memory consumption.

Testing & Validation

The compiler was validated against multiple Pascal test programs to ensure correctness across parsing, semantics, and execution.

Test 1: Nested Conditional Statements

Validates correct branching and label scoping in deeply nested if-then-else blocks (t1.pas).

As shown in the output t1.vm, all conditionals are correctly isolated and executed in the expected order.

Input: t1.pas | Output: t1.vm

Test 2: Invalid Operation Verification

Tests semantic error detection when performing illegal operations (e.g., adding an integer to a string):

Error at line 11: Incompatible types for '+': integer, string
  result := a + b;  { Invalid: cannot add integer and string }
Could not compile program.

The compiler identifies the illegal operation, reports the offending line number, and safely aborts code generation.

Input: t2.pas

Test 3: Constant Folding on Binary Operations

Tests compile-time constant evaluation on binary expressions containing literals and validates that only the precomputed result is emitted into the target VM code.

Input: t3.pas | Output: t3.vm

Test 4: Redundant Arithmetic Operations

Validates algebraic identity simplifications (e.g., adding 0, multiplying by 1). The generated bytecode avoids emitting unnecessary ADD or MUL instructions.

Input: t4.pas | Output: t4.vm

Test 5: Literal Comparisons

Verifies compile-time evaluation of relational expressions between constant literals, emitting direct boolean outcomes to the virtual machine.

Input: t5.pas | Output: t5.vm

Test 6: Unused Variable Detection

Validates memory optimization when unreferenced variables are declared (t6.pas). The terminal outputs informative warnings:

Variable 'd' declared but never used.
Variable 'e' declared but never used.
Code compiled in: ../out/t6.vm

The compiler notifies the developer while successfully generating code without wasting stack slots on unused variables.

Input: t6.pas | Output: t6.vm

Conclusions

The implemented Pascal compiler showcases fundamental compiler engineering concepts, from lexical tokenization to target bytecode generation.

Key Challenges:

Array Memory Mapping: Bridging arbitrary Pascal index ranges to 0-based virtual machine memory addresses
Type Conversion: Ensuring type safety with implicit conversions (e.g., integer to real promotion)
Stack VM Architecture: Managing stack pointer offsets and instruction sequences correctly

Future Improvements:

Support for user-defined procedures and functions with activation records
Advanced control flow optimizations (dead code elimination, loop unrolling)
Extended data types: records, enumerations, sets
More expressive compile-time diagnostic error messages
Additional Pascal standard library intrinsics

Pascal Compiler