LISP-Compiler

Introduction

This is a compiler that extends on a subclass of common-LISP that covers integer arithmetic, an experimental string handling, if clause, if-else clause and switch clause. The authors of the module have taken liberty to handle strings in an experimental way that strays away from the common-LISP standard to give a better experience for the users.

As a part of the project, the contributors have implemented:

1. Lexical Analysis
2. Parsing
3. Abstract Syntax Tree creation
4. Syntax Directed Translation to 3 Address Code
5. Intermediate code optimization
6. Superoptimization using pre-computation
7. Assembly code generation to NASM targeting x86_64 machines running GNU/Linux

To generate relocatable binary, we are using GCC to convert object file generated by NASM assembler into a relocatable binary that can be run on an x86_64 machine running GNU/Linux based operating system.

The compiler is built using:

• POSIX Lex
• POSIX Yacc
• GCC
• NASM

Type Definiation

• Boolean: #t for true and #f for false
• Number: Signed integer from −( 2^31 ) to 2^31

Operation

Name	Symbol	Example
Plus	+	(+ 1 2) => 3
Minus	-	(- 1 2) => -1
Multiply	*	(* 2 3) => 6
Divide	/	(/ 6 3) => 2
Modulus	mod	(mod 8 3) => 2
Greater	>	(> 1 2) => #f
Smaller	<	(< 1 2) => #t
Equal	=	(= 1 2) => #f
And	and	(and #t #f) => #f
Or	or	(or #t #f) => #t
Not	not	(not #t) => #f
	define
	fun
	if

Lexical Details

separator  [ \t\n\r]
letter     [a-z]
digit      [0-9]
number     0|[1-9]{digit}*|-[1-9]{digit}*
ID         {letter}({letter}|{digit}|"-")*
bool-val   #[t|f]

Grammar and Behavior

1. Program

PROGRAM : STMT STMTS
STMTS   : STMT STMTS | {}
STMT    : EXP | DEF-STMT | PRINT-STMT

2. Print

PRINT_STMT : '(' print_num EXP ')' 
           | '(' print_bool EXP ')'

3. Expression

EXPS  : EXP EXPS | {}
EXP   : bool_val | number | VARIABLE | NUM_OP | LOGICAL_OP | FUN_EXP | FUN_CALL | IF_EXP 

4. Numerical Operations

NUM_OP : PLUS | MINUS | MULTIPLY | DIVIDE | MODULES | GREATER | SMALLER | EQUAL

5. Logical Operations

LOGICAL_OP : AND_OP | OR_OP | NOT_OP

6. Define statement

DEF_STMT : '(' define VARIABLE EXP ')'
VARIABLE : id 

8. If Expression

IF_EXP  : '(' _if TEST_EXP THAN_EXP ELSE_EXP ')' 
TEST_EXP: EXP             
THAN_EXP: EXP             
ELSE_EXP: EXP 

Instruction to run the program

Clone this repository and execute the following command:

./compile.sh <path to lisp file> 

---

Further elaborate details regarding this project can be found in 'Project Report.pdf' file present in this repository