KRkragen·Nov 7, 2023
a problem that a lot of these series run into is that the author runs out of steam before they finish writing them. crenshaw's otherwise excellent series suffers from this, for example
so far the author of this one has only written the first chapter
i've written a few didactic compilers that are complete enough to compile themselves, though not complete enough to compile anything else; these may be of more interest to someone who's looking for how to make writing a compiler surprisingly easy, though they do lack the extensive explanatory text in the linked blog post
- http://canonical.org/~kragen/sw/urscheme (from a subset of scheme to at&t-syntax i386 assembly, 1553 lines of code)
- https://github.com/kragen/stoneknifeforth (from a forth-like language to an i386 linux elf executable, 132 lines of code)
- https://github.com/kragen/peg-bo
Read the rest
otstrap/blob/master/peg.md (from a peg grammar with semantic actions to javascript, 66 lines of code)
- https://github.com/kragen/peg-bootstrap/blob/master/handaxew... (tangles a literate program in virtually any plain-text format, such as markdown, html, restructuredtext, or tex, into virtually any plain-text programming language, 208 lines of code; used to tangle both itself and the peg compiler compiler above)
- http://canonical.org/~kragen/sw/dev3/meta5ix.m5 (from meta5ix, a language for writing parsers derived from val schorre's meta-ii, to meta5ix assembly, 18 lines of code; it is a top-down parsing language with limited backtracking, like pegs, but less expressive and implementable without heap allocation or the ability to backtrack past the beginning of a line; see http://canonical.org/~kragen/sw/dev3/meta5ixrun.py for an m5asm interpreter)
- http://canonical.org/~kragen/sw/dev3/meta5ix2c2.m5 (from a slightly different variation of meta5ix to c, 133 lines of code)
most of these do take the same ast-free approach as the linked blog post and crenshaw, just emitting code as they finish parsing a production (or, in the case of stoneknifeforth, a token), but ur-scheme in particular does not; it uses scheme s-expressions as its syntax tree, because some kind of syntax tree is necessary to be able to allocate some local variables on the stack while also supporting closures. peg-bootstrap can certainly handle code that builds an ast with its semantic actions, but its implementation of itself just glues together snippets of javascript text
also worth mentioning in this connection:
- darius bacon's work, especially parson (for example, https://github.com/darius/parson/blob/master/eg_calc_compile...)
- the oberon compiler in wirth and gutknecht's oberon book
- the later chapters of sicp