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

https://briancallahan.net/blog/20210816.html

by ingve • 5 years ago

141 50 5 years ago

fishmaster3• 5 years ago

I'm thinking about following the tutorial in Julia or Kotlin, but it would be interesting how the code looks in a different language like F#.

the_benno2• 5 years ago

F# is an ML-family language, and ML stands for meta-language -- it was designed for language tools and compilers! Andrew Appel's Modern Compiler Implementation in ML is a great resource for code examples that aren't exactly F#, but will look damn close. The book has also been published with C and Java, if you want side-by-side comparisons

pfdietz• 5 years ago

ML was designed to be the metalanguage for the LCF proof system, used to write proof tactics. It was then recognized to be interesting in its own right as a programming language.

BazookaMusic• 5 years ago

The code isn't perfect, it's a learning project and still WIP, but you can check the code for a parser for the LOX language ( c-like) from 'Crafting Interpreters' in this project. 'Ast.fs' and 'Parser.fs' should be enough to get an idea of what it's doing.You can also google the grammar of the language which is quite simple:

https://github.com/BazookaMusic/FLOX

nikkinana• 5 years ago

yacc is key

chrisseaton3• 5 years ago

Never use Yacc. Just write your own parser.

eatonphil3• 5 years ago

Adding on, the fraction of "real" language implementations using handwritten parsers vs. parser generators basically seems to be half and half.

The Wikipedia list of Bison users even calls out that a number of them switched from Bison to handwritten parsers.

https://en.wikipedia.org/wiki/GNU_Bison#Use

p4bl04• 5 years ago

Why would you say that? Yacc and other parser generators exist for a good reason: hand written parsers can be quite hairy to debug and extend, while parser generators offer a domain specific language to specify your grammar and can generate efficient parser code based on it.

What are the arguments in favor of manually writing parsers?

arcticbull4• 5 years ago

Lemon is an infinitely better parser generator than Yacc; it solves a lot of the issues that make Yacc terrible to work with: named non-terminals, non-terminal destructors, re-entrancy, etc. It's part of the SQLite codebase. Highly recommended.

In many cases, though, I think parser combinators thread the needle elegantly - nom in Rust for instance. Or even just a hand-rolled LL(1).

kazinator4• 5 years ago

The author forgot default cases in various switch (tok) statements:

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

The TOK_ enumeration has a good many more members than just those three. If any other one occurs in the code, or an outright corrupt type value occurs, it silently falls through. If the error is handled at all, it will result in some strange diagnostic, in some higher level code that thinks it has seen an expression with a factor in it.

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;

to express that explicitly.

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.

p4bl04• 5 years ago

I second all this. Reading the blogpost I was wondering how the author will do with this parser to actually build an AST rather than just validating syntax.

The thing is that building an AST is typically the kind of thing where "do it with some hacks which build the structure procedurally using global variables" as kazinator said is a sure way to have horrible bugs. The inherently recursive nature of an AST doesn't mix very well with procedural manipulation of a global state.

Someone• 5 years ago

I don’t think there will be an AST. https://briancallahan.net/blog/20210814.html: “We will be writing a single-pass compiler for a simple language and immediately output our final output code as soon as our compiler has enough information to do so”

That “as soon as” implies code will be generated before the entire program has been parsed.

Also, for me single-pass implies “no AST”, as you would need at least one pass to construct one, and iterating over an AST counts as another pass for me.

wott• 5 years ago

The author will have a hard time fitting the necessary semantic actions into this code, like constructing an abstract syntax tree,

It's a declared non-goal.

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.

That's not how it works, TOK_* represent whole elements, the element may happen to be a single character, but it can be a word. It would be highly confusing to pass single characters to expect() as you wouldn't know at first sight whether it expects a simple character or an element. The TOK_* could as well be assigned a random number as you say in your following sentence. And they were until yesterday :-) I guess it is easier to debug with mnemonic characters.

https://github.com/ibara/pl0c/commit/aba92627deac3f8cfe08679...

kazinator4• 5 years ago

Using character constants for denoting one-character tokens is a time-honored tradition that everyone understands.

E.g. GNU Awk:

http://git.savannah.gnu.org/cgit/gawk.git/tree/awkgram.y?h=g...

This is readable; it says "I am just what I look like: a terminal symbol corresponding to the actual +".

p4bl04• 5 years ago

[building an AST is] a declared non-goal.

Then what will be going on after parsing? What will be compiled?

userbinator3• 5 years ago

The parser would be a more future proof

There's already plenty of bikeshed here but that just takes the cake. The only code that's truly "future proof" is code that you're willing to rewrite; which I'm sure the author is capable of doing if/when the need arises.

eatonphil3• 5 years ago

Anyone can do whatever they want, and if you do want to write a parser in C this may be a good guide for you. But it's hard to understand the benefit to writing a language frontend in C, generally speaking. (An obvious exception might be if you are writing one of the first languages for a new architecture/operating system or one where only a C compiler exists.)

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.

arkj• 5 years ago

But it's hard to understand the benefit to writing a language frontend in C, generally speaking.

The advantage of writing in C is that the language provides very little “high” level features. All you have is just functions and memory so you end up doing everything which is a laborious process but rewarding to the mind especially if you are someone who never did low level programming.

fishmaster3• 5 years ago

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.

That's true and was my first thought. C seems like an arcane choice for an introduction course.

david2ndaccount• 5 years ago

C is a simple language and at least used to be a language almost everyone knew.

I don’t know why they’re writing the parser using globals though instead of passing a pointer to a parser state struct.

arcticbull4• 5 years ago

C is an incredibly complex language, it just appears simple. It's simple to get started and incredibly hard to do correctly, like skiing.

int_19h• 5 years ago

Parsers involve a lot of string processing, which is really inconvenient and easy to get wrong in C.

userbinator3• 5 years ago

I don’t know why they’re writing the parser using globals though instead of passing a pointer to a parser state struct.

Because there's only one. Why obfuscate that fact? Don't be tempted by the cargo-cult to make things more complex than they need to be just to appease some dogmatic "best" practices that actually aren't.

foxfluff• 5 years ago

Brian's choice to use C is perfectly well justified:

"I am thinking that we should choose C to implement our PL/0 compiler. Eventually we will want to have this compiler run on many different platforms, including Unix, MS-DOS, and potentially even CP/M. C is a language that will run on every platform I would want to run our PL/0 compiler on, so C works for me. C also requires no special setup so our usual development platform of vim on OpenBSD will work just fine. Finally, it will help with bootstrapping the self-hosting version of the PL/0 compiler, since we in theory could natively compile the C implementation on our target platform then use that to compile the PL/0 implementation, also on the target platform."

The reader may learn something from these posts whether they choose to write a compiler in C or not.

eatonphil3• 5 years ago

I don't mean to debate Brian's choice (your quote shows it does fall into my exception anyway) but mention to readers here why they may be more interested in following guides on compiling/interpreting implemented in other languages than C.

ibains• 5 years ago

This post is good for learning, we have too many “systems“ developed in Java (Hadoop et al - I’m looking at you - you sluggish bugs in the rug), we need more programmers to learn C and build systems in it.

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...

macintux• 5 years ago

…we need more programmers to learn C and build systems in it.

I agree with the first, but not the second. C is a valuable language to know, but for security’s sake we need fewer complex programs in it, not more.

userbinator3• 5 years ago

"security"? You mean the paranoia FUD of Big Tech justifying their enslavement of users and locking them out of their own bought general-purpose-computers --- I mean devices --- to further the authoritarian corporatocracy?

"Trusted" computing, DRM, and all its ugly ilk are premised on making things "secure". Maybe its time we opened our eyes to realise that uncomfortable truth. If the government and the megacorps are scared enough by encryption to want backdoors into our lives, maybe we should want ones into them too.

"Those who give up freedom for security deserve neither."

adrian_b• 5 years ago

While C may be criticized for making it too easy to misuse pointers, for other features that are usually mentioned as security problems for C programs, e.g. out-of-bounds addressing and numeric overflow, the culprit is not the C language, but the manufacturers of the most popular CPUs, e.g. the Intel/AMD CPUs.

On most modern CPUs, checking for addressing bounds or for overflow is too expensive and the software developers almost always choose speed over correctness.

There have been a few C compilers with optional run-time checks for bounds and overflow, but almost nobody used those options for production code.

Unlike the Intel/AMD ISA, there are other instruction sets which include a variety of exception conditions, for a cheap implementation of the run-time checks (e.g. the IBM POWER ISA), but even there I do not know if the most recent implementations of those architectures have efficient exceptions.

musicale• 5 years ago

I expect this series is similar to Wirth's own chapter on writing a PL/0 compiler. It seems to be following the same recursive descent approach, but using C rather than Pascal.

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.

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

Related Stories