Mini-LISP Interpreter

Table of Contents

• 1. Documents
• 2. Developement
• 3. Features
  • 3.1. Basic Features
  • 3.2. Bonus Features
• 4. Usage
  • 4.1. Windows
  • 4.2. Mac & Linux
  • 4.3. Run Test (Recommended Way)
• 5. References

Final project for the Compilers course at National Central University, Fall 2023.

— NCU MIS 109403019

1. Documents

• Compiler Final Project Requirements

• Mini-LISP Language Specification

2. Developement

• Operating System: Windows 11, Mac OS M2

• Language: C++14, Lex, Yacc (Bison)

3. Features

3.1. Basic Features

❗	Features 1-4 must be finished before other features.

Table 1. Basic Features

Feature	Description	Points	Public1	Public2	Hidden1	Hidden2
Syntax Validation	Print “syntax error” when parsing invalid syntax	10	✅	✅	✅	✅
Print	Implement print-num statement	10	✅	✅	✅	✅
Numerical Operations	Implement all numerical operations	25	✅	✅	✅	✅
Logical Operations	Implement all logical operations	25	✅	✅	✅	✅
if Expression	Implement if expression	8	✅	✅	✅	✅
Variable Definition	Able to define a variable	8	✅	✅	✅	✅
Function	Able to declare and call an anonymous function	8	✅	✅	✅	✅
Named Function	Able to declare and call a named function	6	✅	✅	✅	✅

Public test case points : Hidden test case points = 80% : 20% (pass partial get partial)

3.2. Bonus Features

Table 2. Bonus Features

Feature	Description	Points	Public1	Public2	Hidden1	Hidden2
Recursion	Support recursive function call	5	✅	✅	✅	✅
Type Checking	Print error messages for type errors	5	✅	✅	✅	✅
Nested Function	Nested function	5	✅	✅	✅	✅
First-class Function	Able to pass functions, support closure	5	❌	❌	❌	❌

4. Usage

4.1. Windows

bison -d -o src/minilisp.tab.c src/minilisp.y
gcc -c -g -I. -o src/minilisp.tab.o src/minilisp.tab.c
flex -o src/lex.yy.c src/minilisp.l
gcc -c -g -I. -o src/lex.yy.o  src/lex.yy.c
gcc -o bin/minilisp src/minilisp.tab.o src/lex.yy.o

4.2. Mac & Linux

bison -d -o src/minilisp.tab.c src/minilisp.y
gcc -c -g -I. -o src/minilisp.tab.o src/minilisp.tab.c
lex -o src/lex.yy.c src/minilisp.l
gcc -c -g -I. -o src/lex.yy.o  src/lex.yy.c
gcc -o bin/minilisp src/minilisp.tab.o src/lex.yy.o

4.3. Run Test (Recommended Way)

Script Features

• Compile, execute tests, and clear output files

• Count the number of test cases passed and failed

• Display expected and actual outputs for failed test cases

Excution Method

./run_test.sh

Sample Project Structure

.
|
|   run_tests.sh
|
+---bin
|       minilisp.exe
|
+---src
|       minilisp.l
|       minilisp.y
|
\---tests
    |   public_test_data_ans.txt
    \---public_test_data

If encountering issues like permission error, try modifying script permissions

chmod +x run_tests.sh

5. References

Books

• Crafting a Compiler 2009

• Lex & Yacc, 2/e

• Compilers Principles, Techniques, & Tools Second Edition

• Crafting Interpreters

Documents and Other Resources

• LISP - Wikipedia

• Bison 3.8.1 Documentation

• NCU CE3006 Course Video and Slides

Articles and Others

• How can I traverse the parse tree generated by YACC? (Stack Overflow) - yacc does not build a parse tree. It does build (and destroy) a parse stack as it works

• Abstract Syntax Tree: an example in C

Tools

• Excalidraw - Virtual whiteboard for sketching hand-drawn like diagrams, good for drawing AST