Compiler and interpreter for the minimal programming language Lispkit.
Project for the course of :
Programming Languages AY 2015/2016 (Univeristy of Padua) - MSc level.
lexer.hs - given a program P as input (check test/ for examples) it generates the related token sequence T
- syntax. hs - verifies the syntax correctness (regarding the lispkit language) of the token list generated by lexi (see lexer.hs): it outputs "REACHED" if everything is correct, otherwise it outputs "ERROR". The parsed tokens are wrapped inside a monad Exc, the purpose of this monad is to handle exceptions in a declarative manner thus preserving the pure functional nature of Haskell;
- parser.hs - builds the parse tree for the grammar G. it translates the token list into a LKC tree adding synthetized and inherited attributes while constructs the parse tree
G is a context-free grammar (CFG). The chosen CFG is an LL(1) grammar:
- L : the input is parsed from left to right;
- L : applying leftmost derivations on non-terminal elements;
- (1) : considering only one symbol at time.
It considers the input only once without backtracking. Initially the given grammar was an ambiguos grammar (see docs/LL1_grammar/g0_*.pdf), it has been corrected into the described grammar (see docs/LL1_grammar/g1_*.pdf)
Note: ambigous grammar means that the parser could have generated the same frontier using different derivation, for more details check docs/LL1_grammar folder
compiler.hs - takes the AST produced by the parser (LKC type) and compiles it into an SECD list of expressions, a set of LKC instructions executable by the SECD virtual machine (see interpreter.hs). Note that it compiles also the static enviroment to execute each lambda and let expression. A particular case regards letrec, the compiler adds the list of (left) binders also to the (right) binders' enviroment to permit the runtime generation of the correct dynamic enviroment for recursive closures (see Rap, lazyE, lazyClo in interpreter.hs)
interpreter.hs - the SECD virtual machine executes the compiled SECD expressions' list generated by the compiler. For more info see SECD.md