PL/0 Compiler

PL/0 is an educational programming language introduced by Niklaus Wirth in his book "Algorithms + Data Structures = Programs" (1976). It serves as an excellent example for teaching compiler construction due to its simplicity while retaining the essential features of a structured programming language.

This is a C implementation of a PL/0 compiler that generates bytecode for a simple stack-based virtual machine.

Features

• Recursive descent parser
• Symbol table for constants, variables, and procedures
• Stack-based virtual machine (P-code style)
• Support for: constants, variables, procedures, if/while statements
• Arithmetic: +, -, *, /
• Relations: =, #, <, <=, >, >=
• Input/Output: ? (read), ! (write)

Building

make          # Build the compiler
make clean    # Remove build artifacts
make test     # Run example programs

Usage

pl0c [options] [source_file]
  -t         Enable instruction trace
  -h         Show help

Examples:

pl0c program.pl0     # Compile and run program.pl0
pl0c -t program.pl0  # Run with VM trace
pl0c -               # Read from stdin

Language Reference

EBNF Grammar

program     = block "." ;

block       = [ "const" ident "=" number {"," ident "=" number} ";"]
              [ "var" ident {"," ident} ";"]
              { "procedure" ident ";" block ";" } statement ;

statement   = [ ident ":=" expression
              | "call" ident
              | "?" ident
              | "!" expression
              | "begin" statement {";" statement } "end"
              | "if" condition "then" statement
              | "while" condition "do" statement ];

condition   = "odd" expression
              | expression ("="|"#"|"<"|"<="|">"|">=") expression ;

expression  = ["+"|"-"] term { ("+"|"-") term};

term        = factor {("*"|"/") factor};

factor      = ident | number | "(" expression ")" ;

Tokens

Keywords: const, var, procedure, call, begin, end, if, then, while, do, odd

Operators: := (assignment), = (equals), # (not equals), <, <=, >, >=

I/O: ? (read integer), ! (write integer)

Example Programs

See the examples/ directory for sample PL/0 programs:

• factorial.pl0: Computes factorial of a number
• primes.pl0: Prints prime numbers up to 100
• fibonacci.pl0: Prints Fibonacci sequence

Virtual Machine

The VM is a simple stack machine with the following opcodes:

CONST  n   Push constant n
LOAD   a   Push value at address a
STORE  a  Pop to address a
ADD        Pop b,a; push a+b
SUB        Pop b,a; push a-b
MUL        Pop b,a; push a*b
DIV        Pop b,a; push a/b
EQ         Pop b,a; push a==b
NEQ        Pop b,a; push a!=b
LT         Pop b,a; push a<b
LTE        Pop b,a; push a<=b
GT         Pop b,a; push a>b
GTE        Pop b,a; push a>=b
ODD        Pop a; push a%2
READ  a    Read integer to address a
WRITE      Pop and print integer
JMP   a    Jump to a
JZ    a    Pop; jump if zero
CALL  a    Call procedure at a
RET        Return from procedure
HALT       Stop execution

---