Skip to content

A simple compiler for a simple language. Compiles to RISC instructions with dead code optimization.

Notifications You must be signed in to change notification settings

Isaac-DeFrain/simple-compiler

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

34 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

TinyL compiler, interpreter, and code optimizer

Implementation of compiler, interpreter, and code optimizer for the tinyL language

The lexer and parser are implemented with menhir

Build

git clone https://github.com/Isaac-DeFrain/simple-compiler.git
cd simple-compiler
opam switch create simple-compiler 4.14.1
opam install . --deps-only
eval $(opam env)
dune build

Help

make help

Interactive mode

# translation from tinyL to risc
dune exec -- _build/default/bin/main.exe -i
# evaluate tinyL program
dune exec -- _build/default/bin/main.exe -i -e

TinyL grammar

<program>   ::= <stmt_list> .
<stmt list> ::= <stmt> <morestmts>
<morestmts> ::= ; <stmt_list> | ε
<stmt>      ::= <assign> | <read> | <print>
<assign>    ::= <variable> = <expr>
<read>      ::= ? <variable>
<print>     ::= # <variable>
<expr>      ::= + <expr> <expr>
              | − <expr> <expr>
              | * <expr> <expr>
              | & <expr> <expr>
              | ^ <expr> <expr>
              | <variable>
              | <digit>
<variable>  ::= a | b | c | d | e
<digit>     ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Example

# tinyL program
cat test/test1.tyl 
# Output:
#   ?a;?b;c=+ab;#c.

# risc-ify the tinyL
dune exec -- _build/default/bin/main.exe -f test/test1.tyl
# Output:
#   READ a;
#   READ b;
#   c = ADD a b ;
#   PRINT c;

# now evaluate the tinyL program
dune exec -- _build/default/bin/main.exe -f test/test1.tyl -e
# we need to provide values for the variables a and b, e.g.
#   a -> 19
#   b -> 23
# Output:
#   c -> 42

more examples

Compiler

Written in 5 parts:

  1. lexer.mll generates the lexer

  2. parser.mly generates the parser (tinyL AST)

  3. ast.ml defines the tinyL AST

  4. risc.ml defines the RISC AST

  5. gen.ml translates tinyL ASTs to RISC ASTs

Interpreter

There are 2 interpreters:

  1. eval.ml interprets tinyL ASTs

  2. eval_risc.ml interprets RISC ASTs

Code Optimizer

optimize.ml eliminates dead RISC code

Command line tool

main.ml defines the command line functionality

About

A simple compiler for a simple language. Compiles to RISC instructions with dead code optimization.

Topics

Resources

Stars

Watchers

Forks