8 ms·
Parsing / Recursive Descent Parser
- e19293001 4y agoThe book: Compiler Construction by Anthony Dos Reis explains very clearly about parsing. You'll be able to build you own regex parser. I highly recommend the book for anyone interested in learning compiler theory.
- fjfaase 4y agoMake it back-track and add some caching to make it a simple, reasonably efficient parser for a wide range of grammers found in programming languages.
- mikewarot 4y agoLet's Build a Compiler[1] by Jack Crenshaw is a classic work in this field. 1 - https://compilers.iecc.com/crenshaw/ https://compilers.iecc.com/crenshaw/
- dunefox 4y agoIt's classic but is it good in 2022?
- mdoms 4y agoHmm this article really misses out on what makes the recursive decent parser special by not diving deep into the "recursive" part. An example grammar one level more complex would have been great.
- eatonphil 4y agoThe post shows how parsing functions call each other so it isn't really so far off: fn parse_money(&mut self) -> ParseResult<MoneyNode> { let currency = self.parse_currency_symbol()?; let amount = self.parse_amount()?; return Ok(MoneyNode { currency, amount }); }
- KptMarchewa 4y agoThat code could be copied directly from some real-world examples - sqlparser-rs code looks pretty much exactly the same. https://github.com/sqlparser-rs/sqlparser-rs https://github.com/sqlparser-rs/sqlparser-rs
- jfno67 4y agoI feel obliged to mention "Compilers: Principles, Techniques, and Tools" or more commonly known as the dragon book. I loved that book.
- vkazanov 4y agodid you read it on your own? Or as a part of a uni course? It it a classic, sure, but it's definitely not a book to recommend to beginners. Many compiler engineers and academics think the book is... Outdated a bit.
- oxff 4y agoFor beginners getting into "compilers", I would recommend starting with: 1. https://www.plai.org https://www.plai.org 2. Essentials of Compilation (Siek)
- vkazanov 4y agoWell, these 2 books lie on the academic side of language implementation / compilation. Both outstanding, but I cannot really suggest these to working programmers. A very easy way in would be a venerable Wirth's "Compiler Contruction", which takes a simplistic approach, e.g. concentrating on getting the result out as fast as possible. Somewhat similar, crisp in style and exposition, would be Nystrom's "Crafting Interpreters". It explains modern interpreter kind of language implementation (Python, JS, PHP and others), which includes compiling to bytecode and bytecode VM. There is a free online version of the book. Now, compilers are one of the oldest area of computer-related software research. There are many good books, numerous approaches and schools. Any recommendation should take concrete student's background into account. Say, improving a massive modern compiler backend requires a very different kind of recommendation compared with a make-my-own-language project.
- eru 4y agoIt felt quite outdated to me. I tried reading it quite a few years ago as a student, but gave up on the books old-fashioned ideas. The book is very imperative and doesn't really know much about modern abstractions for data structures. Something like https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_... is probably more fun for a beginner these days. (Languages in the ML family are really well suited to writing parsers, interpreters and compilers. That what that family of languages was designed for.)
- oxff 4y agoWell since everyfuckingone is posting links, https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html https://matklad.github.io/2020/04/13/simple-but-powerful-pra..., shows an alternative approach (looping instead of pure recursion)
- jonsen 4y ago(So looping is contaminated recursion.)
- tempodox 4y agoRather, it's a transformation of the tail-recursive part so it only costs constant stack space instead of linear.
- eru 4y agoConceptually loops are a very special case of recursion, and are mostly popular in languages that make some 'interesting' trade-offs in their implementation of function calls. (Stacks are an implementation detail. Only some languages implement function calls with stacks.)
- tempodox 4y agoCan you give some examples of languages that don't use a stack for function calls? I'd love to read the assembly generated by their respective compilers to see how that looks like on the CPU level.
- eatonphil 4y agoLanguages that compile to continuations often put the continuations on the heap. So think Standard ML and Scheme implementations, not all of them of course. SML/NJ is a specific example. https://par.nsf.gov/servlets/purl/10201136 https://par.nsf.gov/servlets/purl/10201136
- habibur 4y agoWhile all the parser I had written were bottom up parser. Find those easier to write.
- ChrisMarshallNY 4y agoRecursive descent parsing was probably the first “real” algorithm that I learned (in the 1980s). Like most of these, I’ve never actually seen one “in the wild,” but it was a great example of the power of recursion.
- tempodox 4y agoI found it in the wild, in the source code of the (1980s) Unix `expr` command. I used it in my own parsers for a while, before getting started with yacc/bison. It was only many years later that I learned the technique is called “recursive descent parsing” :)
- CipherThrowaway 4y agoWhat do you mean by "in the wild"? I would have thought it was the opposite. Handwritten recursive descent is the way to build a parser if most compiler projects are to go by. OpenJDK, GCC, Clang, Rust, Spidermonkey are examples. Occasionally you see a generated lexer but generated parsers seem to be a rarity in practice while recursive descent is ubiquitous.
- ChrisMarshallNY 4y agoIn my case, I have not had occasion to write compilers and parsers. I've used parsers that others have written, frequently. But, like I said, the idea behind it was quite useful, to me. I use recursion all the time, and RDPs are a pretty "pure" form of recursion.
- CipherThrowaway 4y agoYes I agree. There is something quite elegant and fundamental about recursive descent parsing.
- eatonphil 4y agoMost SQL systems (postgres, mysql, sqlite) use generated parsers but yeah other than that handwritten is the norm. Is there a reason for that? None that I can think of. SQL systems tend to have worse error messages but I don't believe parser generators require error messages to be as bad as SQL error messages (I'm talking about how they often don't give line number or column number info). So my guess (and it sounds kind of absurd to say) is that most SQL systems just don't put much thought into parsing. And not that parser generators fit the domain better.
- zabzonk 4y agoRecusive descent is the best way to write a parser because it gives you the best way of producing meaningful error messages.
- eatonphil 4y agoI hear this statement all the time but I don't know parser generators well enough to actually know what this statement means. I have no reason to believe it's not true. What is an example of an error message that is easy in handwritten parsers that is (much?) harder in parser generators?
- kabdib 4y agoThe classic one is with yacc, where your user is looking at a message like "syntax error" instead of "Missing comma, foo.p line 23". IIRC you could improve yacc error messages but you had to modify the grammar, and it usually created even more conflicts and made more bugs.
- eatonphil 4y agoAh wow so the errors are truly useless by default then.
- electroly 4y agoIt's not really even "by default" -- that suggests you could change it from the default. It's generally really hard to stick any custom error messages of any kind into a generated parser. You're often limited to making your grammar accept things that are wrong, and then writing a check that detects those invalid situations in the resulting AST. The parser generator doesn't understand any specifics about your language, so it's not capable of producing useful errors by itself in essentially any situation at all. If you're lucky, you can get "I didn't understand this token at this position; here's a list of other tokens that would have been valid." Meanwhile, with a hand-rolled recursive descent parser, you are writing literally every error message yourself. You can generate an error from anywhere you'd like, using any information you need (local or global!), since it's all just code that you're writing. I have a large-ish grammar that I spent a lot of time on, and I'll be damned if I don't still sometimes get "Invalid statement." with no useful location information. I even wrote my own parser generator; it's not just a shortcoming of existing tools, it's just really hard to write a generic parser generator that's capable of generating custom and useful errors.
- kmstout 4y agoA long time ago I did a pair of articles about recursive descent parsing [1] [2], from very basic theory to a crappy programming language. As a side effect I also made a cantankerous parser generator [3] that produces a backtracking recursive descent parser from EBNF. [1] https://reindeereffect.github.io/2018/12/08/index.html https://reindeereffect.github.io/2018/12/08/index.html [2] https://reindeereffect.github.io/2019/01/16/index.html https://reindeereffect.github.io/2019/01/16/index.html [3] https://github.com/reindeereffect/tools-from-blog/tree/master/yakety https://github.com/reindeereffect/tools-from-blog/tree/maste...
- fjfaase 4y agoAbout 20 years ago, I too started working on a back-tracking recursive descent parser. I wrote it in C. In started with an interpretter that would just take the EBNF rules. It could parse a preprocessed C file using the C grammar (almost taken verbatim from The Book), but it was rather slow. My first idea was to turn the interpretter in a code generator that would generate C code. It produced a massive file, which took very long to compile and to my surprise, was slower than the interpretter. This might be due many missed cache hits. Next, I decided to implement some caching, simply remembering at each point of the input which non-terminals were parsed or not. This gave a huge performance improvement. I also added some mechanism to let it generate a Abstract Syntax Tree. Later, I wrote a C++ version that also included an unparser, based on the input grammar. Instant pretty-printer and 'unifier'. Recently, I developed a JavaScript version (with a simple caching strategy), which turned out to be still fast enough to follow key strokes for small inputs. (Just parsing the whole input on each key stroke.) See: https://fransfaase.github.io/ParserWorkshop/Online_inter_parser.html https://fransfaase.github.io/ParserWorkshop/Online_inter_par...
- _vdpp 4y agoRecursive descent parsing is such a handy tool to have in one’s toolbox. Jack Crenshaw’s series of articles is where I was first exposed to it. For people without a CS background (like me) it can be a bit intimidating to get started. Parsers tend to have their own vocabulary with terminals, productions, grammars, DFA, NFA, etc. I never took a compilers class and therefore feel like I was never admitted to the club. Crenshaw’s articles are much more approachable and give a way for the rest of us to use this great technique.