6 ms·
Let's write a compiler, part 3: A parser
- fishmaster 5y agoI'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_benno 5y agoF# 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 5y agoML 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.
- the_benno 5y agoOh, thanks for the correction and apologies for the inadvertent misinfo. Your comment sent me reading the HOPL paper about SML -- I think I (based on folklore knowledge/informal conversations) conflate the original development of ML with subsequent development and standardization around SML. All of this was well before my time so it's quite interesting to read about some of the details.
- BazookaMusic 5y agoThe 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 https://github.com/BazookaMusic/FLOX
- nikkinana 5y agoyacc is key
- chrisseaton 5y agoNever use Yacc. Just write your own parser.
- eatonphil 5y agoAdding 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 https://en.wikipedia.org/wiki/GNU_Bison#Use
- p4bl0 5y agoWhy 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?
- codr7 5y agoWhat few seem to realize is that it's perfectly possible to abstract out some of the work and create an extensible foundation for manual parsers. Since it's all regular code, you can use the full power of the host language to deal with the problem. https://github.com/codr7/swifties/blob/main/Sources/Swifties/Parser.swift https://github.com/codr7/swifties/blob/main/Sources/Swifties...
- p4bl0 5y agoI understand that, but I still find it easier to write/maintain/extend a grammar than a parser for that grammar.
- kazinator 5y agoThe 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.
- p4bl0 5y ago
- eatonphil 5y agoAnyone 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 5y 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.
- fishmaster 5y 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 5y ago
- ibains 5y agoThis 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-combinators-for-dsls https://www.prophecy.io/blogs/scala-packrat-parser-combinato...
- macintux 5y 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.
- userbinator 5y 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."
- d110af5ccf 5y agoThe comment you replied to had absolutely nothing to do with encryption or DRM. C being low level means you're forced to do many tedious and complicated things manually. This makes the code you write prone to errors which (in the worst case) can be exploited by attackers to run arbitrary code on your system. ... but I'm sure you're already well aware of this which leaves me wondering why you wrote what you did.
- adrian_b 5y ago
- musicale 5y agoI 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.