12 ms·
Show HN: How to write a recursive descent parser
- tbrock 10y agoLove the confidence of this author: > Writing a real parser — one with decent error-handling, a coherent internal structure, and the ability to robustly chew through a sophisticated syntax — is considered a rare, impressive skill. In this chapter, you will attain it.
- mstade 10y agoFWIW Bob Nystrom wrote one of my favorite posts of all times, about Pratt parsers[1]. Really looking forward to read his new work! [1]: http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e...
- munificent 10y agoThanks! When we get to the second interpreter in the book (the one implemented in C), it uses a Pratt parser for expressions.
- zellyn 10y agoHaving written a recursive descent parser after reading Bob's Pratt Parser post (and the other three notable Pratt Parser blog posts), I can attest to the fact that you can attain it :-)
- golergka 10y agoWhen you're teaching someone, projecting confidence is not a bad thing to do.
- munificent 10y agoIt's not that I'm confident in myself, it's that I'm confident in the reader. I'm certain you can do it because once you strip away a lot of the formality and historical baggage, it's actually pretty simple. If I can do it, you can.
- tbrock 10y agoI'm fired up either way. Thank you!
- CJefferson 10y agoOne piece of advice I have for people writing a new language. Consider making your language so you can do one-character lookahead, with something like the 'shunting algorithm' to handle precedence. I work on a system called gap ( www.gap-system.org ), and when parsing we only ever need to look one character ahead to know what we are parsing. This makes the error messages easy, and amazingly good -- we can say "At this character we expected A,B or C, but we found foo". It also makes the language easy to extend, as long as we fight hard against anyone who wants to introduce ambiguity. If your language is ambiguous, and you have to try parsing statements multiple times to find out what they are, then your error handling is always going to be incredibly hard, as you won't know where the problem arose. Of course, if you are parsing a language given to you, you just have to do the best you can.
- chrisseaton 10y agoIt's a balancing act between designing syntax that makes sense for the programmer and syntax that makes sense for the parsing technology. I'd feel a bit silly explaining to someone that some twisted or ugly syntax construct was like that because it made writing the parser a bit easier, when the parser only has to be written once but the syntax has to be used in every program written using the language.
- barrkel 10y agoCode that's hard to parse is easy to get wrong in surprising ways. Difficulty in parsing almost always means ambiguous parses that need to be resolved with sufficient lookahead or semantic lookup; if the user makes a mistake, it may be in one of the ambiguous cases, which leads to surprise. In particular, error messages are impossible to keep clearly prescriptive in every case, because thy needs to take account of the inherent ambiguity.
- tgb 10y agoI used to use gap! I'd love some examples of explicit choices that were made that allow one-character lookahead.
- mishoo 10y agoI wrote some time back a tutorial on this: http://lisperator.net/pltut/ http://lisperator.net/pltut/ — but the implementation language is JS, and the language we implement is quite trivial (no objects, inheritance etc.; but does have lexical scope, first-class functions and continuations). I think Java is ugly, but putting this knowledge in an accessible book is great. Typography is also very nice.
- yisheng 10y agoI used your tutorial for learning to make my first interpreter and learnt a lot from it. Thank you for sharing!
- wry_discontent 10y agoI learned a ton doing this! Thanks for making it! I also really enjoyed "A Little Javascript Problem"
- ch4s3 10y agoI really enjoyed that tutorial!
- JustSomeNobody 10y agoI didn't see mention of first/follow sets. Might be handy to have that in there?
- munificent 10y agoOne of the hardest things about writing a book is deciding what to not include. This chapter is already over 7k words, which is longer than I'd like. First/follow sets are useful but I haven't found them that useful to think about in my own parsers, so I left them out.
- JustSomeNobody 10y agoFair point.
- UK-AL 10y agoA good grasp on first and follows sets is essential if you are building a bottom up parser. Not so much for recursive descent.
- grabcocque 10y agoIt's a shame parsers are such a PITA to write. So many problems could be trivially solved if writing a grammar and generating a parser for it were in any way a pleasant process.
- justinpombrio 10y agoThis is the pain of text. The text format has won so handily that we rarely consider the possibility that files could be anything other than a sequence of characters. But if it were a tree instead, then "parsing" would be a simple, linear-time process with good error messages.
- megous 10y agoEditing would be annoying as hell though.
- justinpombrio 10y agoYou would use a different editor: a tree or structured editor. It would be different, but I doubt it would be worse.
- megous 10y agoSo, where are all the professional programmers doing blocks programming, or something like that? All visual programming is very niche. Last I got close to some was 18 years ago when working with LabView. It's not just different. It's suboptimal. It's just not compelling. You'd need visual everything. Like visual diff, visual git, make it easy to copy visual crap between various applications. Copy visual code to a web page? Copy it to chat to send to a friend? Instead of just writing, you'd need to remember UI shortcuts/icon to insert visual crap into your codebase... It's bleh. I clearly hate the idea. :D
- e12e 10y agoYeah, that's why no-one uses Maya to edit 3d scenes. It lacks the finesse of text, like povray ;-)
- rch 10y agoI enjoyed experimenting with this project, back when it was active... http://www.acooke.org/lepl/ http://www.acooke.org/lepl/ -- A recursive descent parser for Python -- Grammars are written directly as Python code, using a syntax similar to BNF -- New matchers can be simple functions
- e19293001 10y agoI learned about recursive descent parser by reading Anthony Dos Reis book: compiler construction using java, javacc and yacc[0]. I'm a bit lazy {tired} now I'll just refer to my previous comment. It has been my favorite book. Trust me, you'll learn about compiler technology with this wonderful book. https://news.ycombinator.com/item?id=13664714 https://news.ycombinator.com/item?id=13664714 [0] - https://www.amazon.com/Compiler-Construction-Using-Java-JavaCC/dp/0470949597 https://www.amazon.com/Compiler-Construction-Using-Java-Java...
- amorphid 10y agoI worked on a recursive descent JSON parser. That was a valuable learning experience.
- jdormit 10y agoWas it for fun or for business?
- amorphid 10y agoMostly fun. I was initially pissed off out how a JSON encoder/decoder exploded when parsing a large float. After a while, I learned what I wanted to learn about why it works they way it does and moved on to other things.
- jdormit 10y agoInteresting. What encoder exploded at the large float? I ask because I would be surprised if an encoder/decoder from one of the major languages couldn't handle that.
- amorphid 10y agoIt's Poison, a hex package for Elixir. It blows up if you try to parse a number somewhere between "1e308" and "1e309". That is a limitation of the Elixir standard lib. Elixir doesn't try to handle that in a special way, it just raises and exception. I'd love to see something like a BigFloat, or an plug-in hook giving you the option to not explode if you didn't want to. In Ruby, when you parse "1e309" with the built in JSON gem, you get "Infinity". That drives me bonkers, too :)
- Drup 10y agoI don't understand why so many people glorify hand-written parsers. Maybe because they never used good parser generators (not unlike type systems and Java) ? Personal opinion: writing parsers is the least interesting part of an interpreter/compiler, and your grammar should be boring if you want your syntax to be easy to understand by humans. Boring, in this case, mean LL(*), LR(1), or another well known class. Just pick a damn parser generator and get the job done quickly, so you can spend time on the really difficult tasks. The grammar in this article is LR(1) and is trivial to implement in yacc-like generators, locations tracking and error messages included. Bonus point: since your grammar stays in a well known class, it's much easier for other people to re-implement it. You can't introduce bullshit ambiguous extensions to your grammar (C typedefs, anyone ?). This article gives a good explanation of this: http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why-parsing-tools.html http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why...
- dukoid 10y agoBecause the problem is not parsing alone, but doing type checks / ambiguity resolution during parsing and linking up the parse tree with type information etc. See http://stackoverflow.com/questions/6319086/are-gcc-and-clang-parsers-really-handwritten http://stackoverflow.com/questions/6319086/are-gcc-and-clang... Also, you people may just want to learn how to build a parser. Shameless plug if you need a small but flexible expression parser for java: https://github.com/stefanhaustein/expressionparser https://github.com/stefanhaustein/expressionparser
- Drup 10y agoMy point is precisely that, if you are creating your language from scratch, you shouldn't have to do that. Those are mistake needed because the C grammar is full of cruft (and the C++ one is even worse). It's much better, for a new language, to separate type checking from parsing completely, and to avoid any ambiguity.
- deleted 10y ago[deleted]
- hasbot 10y agoBeen there. Done that. Yuck! I so much prefer bison or yacc.
- prions 10y agoIf you're serious about writing a parser, why not go for a bottom up parser? It eliminates a lot of the headaches with top down/recursive descent parsers like left recursion and backtracking.
- WhitneyLand 10y agoWhy is it called recursive descent, isn't that redundant? I normally think of any recursion as some kind of descent into deeper levels. Maybe I'm being biased due to awareness of stackframes being a common way to implement recursion. Or maybe it's a known phrase made popular by a paper or researcher. like "embarrassingly parallel". There are other ways to say it but comp sci people know by convention what an embarrassing problem is and that it's usually a good thing. If everyone started saying only "recursive parser" would there really be any confusion?
- megous 10y ago> I normally think of any recursion as some kind of descent into deeper levels. Maybe I'm being biased due to awareness of stackframes being a common way to implement recursion. You can write bottom up algorithms using recursion too. It still technically goes down first, but does the real work on the way up.
- bjterry 10y agoFor a simple example, this is like the difference between function sum(lst) { if (length(lst) > 0) { return head(lst) + sum(tail(lst)); } return 0; } vs. function sum(lst, currentSum) { if (length(lst) > 0) { return sum(tail(lst), currentSum + head(lst)); } return currentSum; } In the first case you don't actually start doing addition until after you get to the end of the list, while the latter is doing addition on the way down.
- munificent 10y ago> Or maybe it's a known phrase made popular by a paper or researcher. Right. "Recursive descent" is the canonical term for this style of parser. You conceivably could have a non-recursive descent parser if your language grammar didn't have any cycles. (For example, if you only supported arithmetic expressions and didn't have parentheses for grouping.) In practice, languages are almost always recursive. My hunch is that the inventor of recursive descent (can't remember his name at the moment) stressed "recursive" because recursive procedure calls were considered a fairly advanced topic at the time. Recall that this was back when Fortran didn't even support recursion. > If everyone started saying only "recursive parser" would there really be any confusion? Yes, "recursive ascent" is a thing too, though it was invented much later.
- coldcode 10y agoMy first project ever as a professional programmer was writing a recursive descent parser - in 1981, in Fortran, of Jovial language code. Of course there were no other choices. Thankfully today you can avoid writing your own, though sometimes it still pays to write it by hand.
- megous 10y agoAnother fun way to write a recursive descent parser is to abstract and parametrize the recursive descent algorithm. Best done in dynamic languages. I wrote an abstract recursive descent parser in JS which accepts an array of terminal (regexp) and non-terminal definitions (array of terminal/non-terminal names + action callback), and returns the function that will parse the text. The parser "generator" has 125 lines of code and doesn't really generate anything. It's an extremely lightweight solution to quickly produce purpose made languages in the browser without need for any tooling. Together with `` template strings to write your custom made language code in, it makes for a lot of fun in JS. :D
- Stratoscope 10y agoIt would be really interesting to see that code if you ever want to publish it. Thanks!
- megous 10y agoI guess why not. :) https://megous.com/dl/parser/tests/index.html https://megous.com/dl/parser/tests/index.html See the code. AGPL.
- w23j 10y agoOh my god, a dream come true! I had always hoped Bob Nystrom would write a book about interpreters/compilers. Back when I tried to learn how to write a recursive descent parser, the examples I found either ignored correct expression parsing or wrote an additional parse method for each precedence level. Writing a parser by hand seemed just too much work. Along comes this great article about pratt parsers http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e... and all can be done with two simple functions, a loop and a map. :) Saved my enthusiasm right there. Another great example is this article about garbage collection: http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/ http://journal.stuffwithstuff.com/2013/12/08/babys-first-gar... Instead of making things more complicated than they are, Bob Nystrom simplifies daunting topics and makes the accessible. Thanks so much for your work! Really looking forward to this one. Will there be code generation too? :)
- munificent 10y agoYou're welcome! Some of the book will revisit topics I've already covered in my blog (but I'll write all new prose to seamlessly integrate it into the rest of the material and the language we're building). In Part III where we build an interpreter in C, it will use a Pratt parser and we'll implement a mark-sweep GC from scratch. The book doesn't touch on native code generation because (1) that's a really big, messy topic and (2) I don't have much experience with it. The C interpreter does compile to bytecode, though, so we cover a lot of the basic concepts around lowering the code into a denser more efficient representation, representing the stack and callframes, etc.
- panic 10y agoHere's a recursive descent trick worth mentioning: instead of decomposing expressions into levels called things like "term" and "factor" by the precedence of the operators involved, you can do it all using a while loop: function parseExpressionAtPrecedence(currentPrecedence) { expr = parseExpressionAtom() while op = parseOperator() && op.precedence < currentPrecedence { if op.rightAssociative { b = parseExpressionAtPrecedence(op.precedence) } else { b = parseExpressionAtPrecedence(op.precedence + 1) } expr = OperatorExpression(op, expr, b) } return expr } The parseExpressionAtom function handles literals, expressions in parentheses, and so on. The idea is to keep pushing more operators on to the end of an expression until a higher-precedence operator appears and you can't any more. This technique (called precedence climbing) makes parsing these sorts of arithmetic expressions a lot less painful.
- munificent 10y agoYes! Using explicit functions for each precedence level is a little tedious. It's also really simple and fairly common, though, so I thought it was a good gentle way to ease people into parsing. In part III of the book, when we write a second interpreter in C, we use a Pratt parser for expressions and it's a lot less boilerplate-heavy.
- asrp 10y agoBy going to the other extreme, you can use only precedence climbing (with just a grammar) by using Floyd's algorithm, which will treat all tokens as operators. It uses two precedences functions instead of one, a left and right precedence. https://en.wikipedia.org/wiki/Operator-precedence_grammar https://en.wikipedia.org/wiki/Operator-precedence_grammar
- chubot 10y agoYes, and if you need more expressiveness for the ternary operator and so forth, you will want to structure it as mutually recursive functions, like Pratt parsing. See "Pratt Parsing and Precedence Climbing Are the Same Algorithm": http://www.oilshell.org/blog/2016/11/01.html http://www.oilshell.org/blog/2016/11/01.html The difference is really about how you structure your code. If you have a single recursive procedure like the above, it looks like "precedence climbing". But if you have a set of mutually recursive procedures, it looks more like Pratt parsing. But they are the same algorithm, or you can say "precedence climbing" is just a special case of Pratt parsing.
- lhorie 10y agoI'm writing a Javascript parser right now so this is actually super useful. Thank you!
- rzimmerman 10y agoIf anyone would be helped by an example, I worked on this recursive descent-based compiler a few years ago with a focus on clarity and readability: https://github.com/rzimmerman/kal https://github.com/rzimmerman/kal The actual parsing is here: https://github.com/rzimmerman/kal/blob/master/source/grammar.litkal https://github.com/rzimmerman/kal/blob/master/source/grammar... It's somewhere between a toy language and something professional, so it could be a helpful reference if you're doing this for the first time. Beware, the project is no longer maintained and probably doesn't work with modern node.js runtimes.
- asrp 10y agoI've found parser expression grammars (PEG) to be a good solution to avoiding the ambiguity stated at the very beginning. This is done by making all choices (|) into ordered choices. I've recently used PEGs to write a Python parser (parsing all of Python, except for possible bugs) in ~500 lines of Python [2]. Its entirely interpreted. No parser is generated, only trees. I'll also add that Floyd's operator precedence grammar [3] includes an algorithm which can deduce precedences from a grammar. [1] https://en.wikipedia.org/wiki/Parsing_expression_grammar https://en.wikipedia.org/wiki/Parsing_expression_grammar [2] https://github.com/asrp/pymetaterp https://github.com/asrp/pymetaterp [3] https://en.wikipedia.org/wiki/Operator-precedence_grammar https://en.wikipedia.org/wiki/Operator-precedence_grammar
- zem 10y agohow do recursive descent parsers compare to parser combinators? so far i've tended to use a combinator library when one of my small projects needs a parser, but now i'm wondering if i should just get good at doing recursive descent parsers instead.
- fooker 10y agoThey are essentially same.
- wideem 10y agoHaha, I had assignement to built a recursive descent parser for a simple Ada-like language just 3 days ago. It was fun task, but if this guide was posted earlier, I could have used it.
- munificent 10y agoI'm writing as fast as I can. :)
- fjfaase 10y agoEver thought about using an interpreting parser, which takes a grammar and parses a string/file according to it. (To parse the grammar you use the interpreting parser itself with a hard coded version of the grammar of the grammar.) Have a look at: https://github.com/FransFaase/IParse https://github.com/FransFaase/IParse
- gnuvince 10y agoVery cool Bob! I'm a big fan of your writing and Jasic was a nice and small project that really helped me understand compilers better. I look forward to my lunch hour when I can go over this chapter. I'm actually going through a similar process at the moment. I would like to write a few articles about implementation considerations in compilers that text books often omit. For example, in the scanner phase, should identifier tokens contain a copy of the identifier name, should they have a length + pointer into the original stream, should they contain an index into a symbol table, etc.