3 A Tiger-compiler implementation in (OCa)ML
8 ![screenshot-tests-head](screenshots/tests-head.jpg)
10 ![screenshot-tests-tail](screenshots/tests-tail.jpg)
14 - [x] ch 1: Warm-up AST
18 - [x] ch 5: Semantic Analysis (type checking)
20 - [ ] ch 6: Activation Records
21 #### TODO (short-term)
22 - [ ] ch 7: Translation to Intermediate Code
23 - [ ] ch 08: Basic Blocks and Traces
24 - [ ] ch 09: Instruction Selection
25 - [ ] ch 10: Liveness Analysis
26 - [ ] ch 11: Register Allocation
27 - [ ] ch 12: Putting It All Together
29 - [ ] ch 13: Garbage Collection
30 - [ ] ch 15: Functional Programming Languages
31 - [ ] ch 16: Polymorphic Types
32 - [ ] ch 17: Dataflow Analysis
33 - [ ] ch 18: Loop Optimizations
34 - [ ] ch 19: Static Single-Assignment Form
35 - [ ] ch 20: Pipelining and Scheduling
36 - [ ] ch 21: The Memory Hierarchy
38 - [ ] ch 14: Object-Oriented Languages
41 - [-] testing framework
42 - [x] run arbitrary code snippets
43 - [x] check non-failures
44 - [x] check expected output
45 - [-] check expected exceptions
47 - [ ] generalized expect `Output ('a option) | Exception of (exn -> bool)`
48 - [x] run all book test case files
49 - [-] grid view (cols: lex, pars, semant, etc.; rows: test cases.)
52 - [ ] test time-outs (motive: cycle non-detection caused an infinite loop)
53 - [ ] parallel test execution
61 #### shift/reduce conflicts
62 ##### grouping consecutive declarations
63 In order to support mutual recursion, we need to group consecutive
64 type and function declarations (see Tiger-book pages 97-99).
66 Initially, I defined the rules to do so as:
70 | dec decs { $1 :: $2 }
74 | typ_decs { Ast.TypeDecs $1 }
75 | fun_decs { Ast.FunDecs $1 }
78 which, while straightforward (and working, because `ocamlyacc` defaults to
79 shift in case of a conflict), nonetheless caused a shift/reduce conflict in
80 each of: `typ_decs` and `fun_decs`; where the parser did not know whether to
81 shift and stay in `(typ|fun_)_dec` state or to reduce and get back to `dec`
84 Sadly, tagging the rules with a lower precedence (to explicitly favor
85 shifting) - does not help :(
91 | typ_decs %prec LOWEST { Ast.TypeDecs $1 }
92 | fun_decs %prec LOWEST { Ast.FunDecs $1 }
95 The difficulty seems to be in the lack of a separator token which would be
96 able to definitively mark the end of each sequence of consecutive
97 `(typ_|fun_)` declarations.
99 Keeping this in mind, another alternative is to manually capture the possible
100 interspersion patterns in the rules like:
102 (N * foo) followed-by (N * not-foo)
104 for the exception of `var_dec`, which, since we do not need to group its
105 consecutive sequences, can be reduced upon first sighting.
113 I chose to pretty-print AST as an (indented)
114 [M-expression](https://en.wikipedia.org/wiki/M-expression) - an underrated
115 format, used in Mathematica and was intended for Lisp by McCarthy himself; it
116 is nearly as flexible as S-expressions, but significantly more readable (IMO).
118 As an example, here is what `test28.tig` looks like after parsing and
147 Will most-likely compile to RISC and execute using SPIM (as favored by Appel)