Let's write a compiler, part 3: A parser

If you are writing a compiler, you'll just be emitting some other language anyway so the parser/emitter being in C doesn't really give you anything even if you are emitting C.

If you are writing an interpreter and you want performance, you're going to have to emit bytecode and have a bytecode interpreter. Wanting your bytecode _interpreter_ to be in C could make sense but your frontend could just emit the bytecode to a file and your interpreter written in C could read from that file.

It's a handwritten parser too so it's not like you picked the language so you could use a certain complex or nice parsing library.

And it's not like the performance (or binary size) of the parser/emitter typically matters so much that you need even that part to be so much faster (or smaller) than a parser/emitter in Go/Java/C#/whatever.

The overhead to writing C makes it a less friendly introduction to the topic if you have never written a compiler or interpreter (or parser, specifically) before.

Again, you can do what you want. And if you must do it in C, you will probably value any posts like this. Just wanted to throw out reasons you may not want to do this.

Since the implementation is in C, perhaps it might make sense to compile a version of PL/0 ("C/0") with C syntax rather than Pascal syntax. It might be possible to get something close to a C/0 compiler that could compile its own source code.

Though one issue with C is you also need a cpp implementation.

  static void
  factor(void)
  {
     switch (type) {
     case TOK_IDENT:
     case TOK_NUMBER:
       next();
       break;
     case TOK_LPAREN:
       expect(TOK_LPAREN);
       expression();
       expect(TOK_RPAREN);
     }
   }

Adding a break after the last block in a switch is a good idea; someone adding a new case might forget. (Wit diagnostic support, like GCC requiring a fallthrough comment, this is less important nowadays).

If a switch deliberately falls through for unmatched cases, have

   default:
     break;

This whole approach of the parser consisting of void functions is poor for 2021. It's as if the author is deliberately trolling everyone who has ever taken any level of interest in functional programming.

The author will have a hard time fitting the necessary semantic actions into this code, like constructing an abstract syntax tree, and might succumb to the temptation to do it with some hacks which build the structure procedurally using global variables.

The parser would be a more future proof if it anticipated the need for backtracking. So that is to say, a function such as factor() above could be considered to be a pattern matching construct, and return a useful value indicating whether it matched or failed to match. Furthermore, if it it failed to match, then it would backtrack, leaving the state of the input stream as it was prior to entry.

You can then do interesting things, because you're essentially LL(k) now, like speculatively parse the input using several possible constructs in priority order, until one matches.

The code inconsistently mixes the use of concrete character constants like '.' and '{' and #define symbols that expand to character constants like #define TOK_PLUS '+'.

Using the character constants in the code as in expect('+') or whatever is clearer. The Yacc approach of using constants for abstract tokens, (which are enumerated starting at some value above 256), and concrete character constants for single-character tokens that denote themselves, is worth mimicking.

You're not going to redefine TOK_PLUS to something other than '+' in the future, and doing so would be like like changing #define FOUR 4 to #define FOUR 5. TOK_PLUS doesn't inform any better than '+', and isn't any easier to find with grep.

Also, you can do this so much easier in scala using parser combinators, if the goal is time to market and the code to be compiled is not very large. Here is an example to see how the approaches compare: https://www.prophecy.io/blogs/scala-packrat-parser-combinato...