8 ms·
Parsing Algorithms
- wtetzner 6y agoAny chance of also including GLL (generalized LL)? I found the paper (http://dotat.at/tmp/gll.pdf http://dotat.at/tmp/gll.pdf) quite hard to follow, and haven't been able to find a good explanation anywhere else.
- DonaldPShimoda 6y agoJust generalized parsing algorithms in general would be good to include, I think. It looks like the course only plans to cover basic LL/LR, which are admittedly the most commonly used parsers but more would be interesting. A fun one to include might be Might's "Parsing with Derivatives", which is algorithmically novel (though not very performant). I think there was a recent innovation on this: "Parsing with Zippers" at ICFP this year. Hard agree that GLL is hard to follow. I've read the paper a number of times and struggle with it every time haha.
- giraj 6y agoThanks for mentioning "Parsing with Zippers"! I read "Parsing with Derivatives" last week and wondered if that could be taken further. The paper can be found here: https://dl.acm.org/doi/10.1145/3408990 https://dl.acm.org/doi/10.1145/3408990
- DonaldPShimoda 6y agoIt's always fun to spread new research around the community! I remember reading PwD and thinking it was just so cool as an algorithm, though the performance concerns were a bit of a turn-off. Still, I always like to talk to people about it because I just think it's such an elegant approach to the problem. As for PwZ, I know one of the authors so maybe I'm a little biased, but I also thought his ICFP talk was quite good. It's here: https://youtu.be/fakSKvP9yaM?t=6180 https://youtu.be/fakSKvP9yaM?t=6180
- thesz 6y agoParsing with derivatives is not all that slow: https://www.microsoft.com/en-us/research/uploads/prod/2019/02/SRM_tacas19.pdf https://www.microsoft.com/en-us/research/uploads/prod/2019/0... The paper shows that it can compete with re2 (by google).
- DonaldPShimoda 6y agoThis is not what I'm talking about. "Parsing with Derivatives" is the title of a 2011 paper by Matt Might, David Darais, and Daniel Spiewak that generalizes the Brzozowski derivative from regular expressions to context-free grammars. In the present discussion, I assumed the context to be about CFGs instead of REs because that is most often what people are referring to when we talk about parsers in programming languages, though I admit that I could have been more explicit about this. What you linked is an improvement of the Brzozowski derivative, but it does not constitute a parser for CFGs.
- thesz 6y agoAccording to "Parsing Techniques: A Practical Guide" [1], it is quite common for computer languages to have most of the grammar in the regular grammars class and some parts to be, actually, context-free. [1] https://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf https://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf For example, consider addition and subtraction in most grammars. They can be expressed as "summation ::= factor ((PLUS | MINUS) factor) * " and factor can be similarly defined as "factor ::= multiplicand ((MUL | DIV) multiplicand) * ". Authors of PTAPG note that these regularities can be exploited for speed. And I think "parsing with derivatives" techniques can be used for speedy parsing too.
- DonaldPShimoda 6y agoUhh sure, but you're kind of deflecting. The phrase "parsing with derivatives" (or "Might's 'Parsing with Derivatives'" as I wrote in my initial comment to which you first replied) refers specifically to the technique developed by Might et al that generalizes the Brzozowski derivative to CFGs. And, more to the point, their technique has very poor performance, which is addressed directly in the paper. If you talk to parsing people about "parsing with derivatives", they will undoubtedly assume that you specifically mean the Might et al work and not some other, more general notion, regardless of whether one could technically call such notion a "parsing with derivatives" technique. I have never heard of anybody calling anything else "parsing with derivatives" and, indeed, the paper you linked never uses this phrase (the closest they come is "matching with derivatives", which is a bit different in semantics). I appreciate the points you've raised, and I do think the RE-parsing paper you linked previously looks very interesting (I hadn't seen it before), but the crux of the issue is that you misinterpreted what I said and haven't yet acknowledged that misinterpretation. Instead, it feels like you're trying to fight me on other points to win back some ground or something, though I hope I'm just misreading this because I find that kind of a frustrating conversational method.
- eru 6y agoParsing with derivatives has been around for a long time, at least for regular languages.
- DonaldPShimoda 6y agoYes, the technique was introduced in 1964 by Brzozowski. But the Brzozowski derivative (as it is now known) was generalized to handle all CFGs (instead of only REs) in the 2011 Might et al paper titled "Parsing with Derivatives". This work was then refined this year with "Parsing with Zippers", which generalizes Huet's Zipper data structure to represent CFGs (instead of acyclical, deterministic tree structures) and uses that to re-build the 2011 algorithm with a better representation, achieving greater performance with a small algorithm.
- eru 6y agoThanks! I'll check out the papers.
- samatman 6y agoI found the code for Instaparse (relatively) easy to follow. I had considered leaving a comment here like "hey could you cover combinators and PEGs?", but after thinking it over, it's important to limit the scope for a class like this. It would be pretty great to offer a "201" edition, covering ALL*, GLR, GLL, combinators/PEGs, Earley, parsing-with-derivatives, Marpa, and anything else I might have forgotten: basically a survey of modern parsing algorithms, which frankly, LR and LL are not. But for your own learning, I bet you could take this course, and then spend some time with Instaparse and the GLL paper, and walk away with a solid understanding of GLL in practice.
- DmitrySoshnikov 6y agoGreat point on combinators, PEG, and GLL -- this potentially would be covered in 201 as suggested, since it's good having a foundation of the LL/LR, and then gradually moving to combinators if needed. LALR(1) covers a pretty wide range of the most practical languages.
- samatman 6y agoTo a significant degree, the arrow of causality runs LALR(1) -> practical languages, not the other direction! The languages and formats we use have been heavily shaped by the practical parsing algorithms of the 20th century. An example: you can't have a struct field called "while" in C, because once the lexer declares a token to be a keyword, that's that.
- jcranmer 6y agoContextual keywords are a growing thing in modern languages. Modern compilers don't tend to have strictly separated lexers and parsers, but instead use a combined lexer/parser model that feeds information back and forth between them. If your language is designed such that you aren't often in multiple potential parse states, then it's easy to feed into the lexer "get me the next token, and by the way, expect function attributes to be keywords right now." Note that the requirement to not be in multiple potential parse states also tends to boil down to "build a language that's usually LL(1) or LALR(1)."
- DmitrySoshnikov 6y agoYes, GLL is a good algorithm and I potentially going to publish it separately as a single public video.
- wtetzner 6y agoThat would be fantastic!
- andreygrehov 6y agoVery well done! I like video animations. What software do you use to make them?
- DmitrySoshnikov 6y agoThanks for the feedback, glad you like it. For production I use combination of software: Keynote, Notability, Good notes, Camtasia, and live editing on iPad.
- redwoolf 6y agoThis is great! I'm working on designing a language right now and I'm just getting to the point where I have to parse the AST. Looking forward to taking this course, I just purchased it on Udemy.
- DmitrySoshnikov 6y agoCongrats, and hope this makes building of your parser easy and fun! This course covers a lot of parsing theory as well, and if you're interested in pure practical (manual) parser, there will be also "Building a Recursive descent parser from scratch", which is mainly coding class and is an extension for the "Parsing Algorithms".
- jeofken 6y agoIf you are implementing it in a functional and GC language (like OCaml, Scheme/Clojure, JavaScript, F#, Elm, Haskell) using parser combinators is a lovely technique where you make composable mini-parsers. Worth researching! As a side effect (hehe) you’ll learn how to simulate state in a pure language... Enjoy
- waynesonfire 6y agosuper interesting subject; can anyone recommend resources for self learners?
- egonschiele 6y agoIsn't this for self-learners? > The course starts now and never ends! It is a completely self-paced online course - you decide when you start and when you finish.
- davidkellis 6y agoI'd like to see something like this for practitioners. I kind of have a feel for what's out there, but I don't know of anything that is: 1. pleasant to use 2. simple 3. scannerless 4. supports left recursion that produces a left-associative parse
- bmn__ 6y agoMarpa meets 2.a) 2.b) 3. 1. is subjective.
- DmitrySoshnikov 6y agoYes, we use LALR(1) parsing mode to build the actual parser, and it exactly supports Left recursive grammars (which are much more elegant than LL). We also don't focus much on scanner (tokenizer) since this is a topic of Regular expressions and Finite automata which we discuss in detail in the separate class "Building a RegExp machine".
- norswap 6y agoShameless self-promotion: https://github.com/norswap/autumn https://github.com/norswap/autumn
- rschachte 6y agoIs the site down?
- DmitrySoshnikov 6y agoShould be up by now; seems auto-DDOS'ed, lol
- cjauvin 6y agoFor an alternative take on a related topic, this is really a fantastically well-written and practical (free) book: http://craftinginterpreters.com http://craftinginterpreters.com
- mssundaram 6y agoNot free but also very good is https://interpreterbook.com/ https://interpreterbook.com/
- bensonalec 6y agoBoth of Thorsten Ball's books in that series are phenomenal, could not recommend more. He's also got a great discussion of it on the Go Time podcast, https://changelog.com/gotime/28 https://changelog.com/gotime/28 and https://changelog.com/gotime/107 https://changelog.com/gotime/107.
- mssundaram 6y agoThanks for sharing the podcast links, I hadn't known about that
- DmitrySoshnikov 6y agoYeah, this class is specifically on parsing pipeline and syntactic analysis. For runtime semantics (Interpreters and Virtual Machines) you can address "Essentials of Interpretation" aka "Building an Interpreter from scratch".
- ufo 6y agoI a big fan of the way Bob Nystrom skips the LR and LL theory and goes straight to recursive descent parsing plus the precedence-climbing trick. I'm of the opinion that if you have to learn ONE thing about parsing then it should be how to write a recursive descent parser by hand. It is the parsing technique that you are most likely to use in a real project if someone throws a parsing hot potato in your direction. That said, if you are on the mood to learn at least two things about parsing then there is no way around the LL and LR fundamentals. :)
- ChuckMcM 6y agoFWIW, parsing and lexical analysis was the CS class I have used most thoroughly in my career. Sure data structures is probably the most often used, but other than hash tables and b-trees, not much of that class was useful. But lexing and parsing? Seems like every other project benefited by it either in handling configuration files, or log/sensor data, or some other need to convert what was human readable into machine manipulable. That said, I really recommend the crafting interpreters work. It covers all the bases pretty solidly. If you want more depth and theory then get the dragon book (Ullman on compiler design) and read it afterwards :-)
- DmitrySoshnikov 6y agoYes, in the "Essentials of Interpretation" class (aka "Building an Interpreter from scratch" we focus exactly on runtime semantics, and evaluating the language. The S-expression allows greatly simplifying, focus on runtime specifics themselves, skipping parsing stage altogether. In "Essentials of Parsing" class (aka "Parsing Algorithms") we shift exactly to the syntax, and understanding the parsing process from within -- this in general may have nothing to do with runtime -- for the same exact syntax you may have different interpreters or VMs (even with different semantics).
- chubot 6y agoYeah I think that makes sense, and that's how I learned... The s-expressions let you concentrate on the meaning without getting bogged down in details. And then parsing has some nice algorithms, but it's full of details ... I actually find the parsing part harder in many respects. At least it's more code to write, and test.
- humanlion87 6y agoApologies for the tangential question. I am currently working on a codebase that involves trying to understand code that parses and input string (that has various search parameters and values) and generates an appropriate SQL query to search the associated database. I am struggling to build a mental model of how this parsing works. Will going through one of the resources mentioned in this thread help with my understanding?
- DmitrySoshnikov 6y agoYes, if you need to parse that input string to generates an appropriate SQL query, you would need to have a small DSL (domain-specific language) for that "string", whatever it contains. If the string contains SQL-like syntax, e.g. "SELECT name from users", then yes, it would be easy to build a grammar for this.
- bgorman 6y agoThanks for building this, I completed the "make a lisp" project, but the parsing stage was greatly simplified so it is nice to have a resource to learn more about the parsing/lexing stage.
- DmitrySoshnikov 6y agoAbsolutely! S-expression (used in Scheme, Lisp, etc) is a great AST-based syntax to start building an interpreter right away. But for fully ergonomic language you would need a parser for a more complex syntax.
- default-kramer 6y agoDoes anyone know if there are any good resources on "tolerant parsing," if that is the correct terminology? For example, when I write C# in Visual Studio, the IDE remains amazingly helpful even when the code is incomplete and would be rejected by a traditional parser. I'd guess that Microsoft simply has the budget to have the VS/C# dev teams grind out hundreds or thousands of special cases that are specific to C#... but I would love to learn that there are some fundamental techniques that would fit into a few credits worth of CS education.
- mrits 6y agohttps://github.com/rust-analyzer/rust-analyzer https://github.com/rust-analyzer/rust-analyzer is a good resource. I went there because I was surprised how good the project worked. I found some really great docs and learned quite a bit from the code.
- derriz 6y agoIt's fairly straightforward to offer some functionality in this area with hand-written recursive descent parsers. For example, a language with a C-like syntax, you'll often be parsing a sequence of statements separated by semi-colons (a block). If a statement fails to parse, you can just consume tokens until you hit the next semi-colon and then try to continue to parse statements from there. Fairly crude approaches like this are easy to implement (at least with recursive-descent) but can be surprisingly effective. It's easy to construct counter examples where an approach like this will get it wrong but in practice it's hugely more useful to the poor user than just abandoning the parse completely.
- eru 6y agoYou can probably make your heuristic even more robust, by looking at hints from indentation and parens and braces in addition to just semicolons.
- DmitrySoshnikov 6y agoYes, this is called "parse error recovery" and there are multiple techniques for this. In fact, most of the production parsers support this mode. E.g. when you try executing a C++ or Java file, it shows you all the errors at once instead of failing on first parse error. The way it's achieved is by constructing a "dummy" AST node (caught up to some delimiter, e.g. semicolon in statements) and continue the parsing process as there would be no any error.
- MaxBarraclough 6y agoSeems the place to ask: what do folks make of the IELR algorithm? [0] Apparently GNU Bison supports it these days. [1] [0] https://cs.stackexchange.com/a/99463/ https://cs.stackexchange.com/a/99463/ [1] https://en.wikipedia.org/wiki/GNU_Bison https://en.wikipedia.org/wiki/GNU_Bison
- rmasters 6y agoI think its great. IELR is a straightforward optimization that just makes sense to use when building an LR family parser. You can think of LALR(1) as just taking an LR(1) state graph and merging together nodes that are compatible (in that they are essentially the same parsing state, but differ in which "lookahead" tokens are valid). A grammar is consider to be LALR(1) if combining states in this way still results in a correct parser. IELR, which is derived from David Pager's PGM and Lane Tracing "Minimal LR" techniques from the 1970s, applies a stricter compatibility test for nodes. This check usually allows a large majority of merges while rejecting the ones that will lead to parsing errors. In this way, a more sophisticated grammar, all the way up to LR(1) can still be processed correctly using a table size much closer to what you get with LALR. You essentially get the best of both worlds and its tragic that this fairly simple technique is so obscure. I believe the reason for the obscurity of these techniques is that Pager's PGM and lane tracing papers are extremely terse, somewhat confusing, and lacking in sufficient detail in certain areas. For example, the PGM paper on p.256 crucially notes that successors may need to be "regenerated as a distinct state" without further explanation. (Until his protege Chen provided some pseudo-code 34 years later in his dissertation of 2009. BTW, I have verified that the Wisent and Menhir parsers and others implement PGM correctly, if anyone is looking for actual details.) Note that there is some additional time and complexity required to detect conflicts and regenerate/split nodes and so the benefits or IELR are not entirely free. More obscurely, it should be noted that IELR suffers the same problem as LALR in that combining states can introduce conflicts between tokens when context aware lexing [Nawrocki 1991] is being utilized. (BTW, Tree Sitter uses context aware lexing but its not very common otherwise - yacc/bison doesn't AFAIK). Suddenly tokens are eligible for matching alongside other tokens that normally would not be matched together. Unless your tokens are globally conflict-free or you've got a priority scheme that always resolves conflicts properly (but then you wouldn't need context-aware-lexing would you?), you'll start matching tokens that shouldn't be matched in a particular parsing state. There are ways to avoid those conflics as well (see PSLR - also from IELR author Joel Denny) but it is a lot more work. Even if you avoid conflicts, invalid content can match tokens that shouldn't be matched which complicates error reporting because you get a confusing parse error instead of a correct tokenization error. So this is one case where the full LR(1) may be preferred over IELR. But I can't think of a convincing argument for preferring LALR over IELR.
- xc468 6y agoI recommend compilers course by Alex Aiken from Stanford open
- DmitrySoshnikov 6y agoProfessor Aiken is a great teacher and I love his compilers course. However as for the parsering stage, that course goes as maximum as to SLR(1) which is pretty "toy" parsing mode. That's the problem with a combined "compilers class" -- one simply can't put everything, and everything is becoming slightly superficial. That's why I have Parsers and Garbage Collectors class as separate and fully specialized course.
- LordGrey 6y agoI really liked the intro. I purchased both the "Building an Interpreter from scratch" and the "Parsing Algorithms" courses from Udemy and went through the first four modules of the former. Very clear presentation!
- DmitrySoshnikov 6y agoThank you for the feedback, glad you liked it, and glad to see more people interested in deeper CS topics!
- siraben 6y agoOne parsing technique that covers a lot of ground for little code is parser combinators[0]. And the more space and time efficient Parsec library[1]. Recursive descent is not difficult to hand-roll but the correspondence between the code and BNF can be more obscured, whereas with parser combinators the correspondence is quite clear. [0] http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf [1] https://dspace.library.uu.nl/bitstream/handle/1874/2535/2001-35.pdf https://dspace.library.uu.nl/bitstream/handle/1874/2535/2001...
- esrh 6y agoWhile i find the topic really interesting, I'm don't enjoy or learn very well from video lectures. Is there some comprehensive textbook on the topic?
- DmitrySoshnikov 6y agoYes, I recommend "Parsing Techniques" book.
- fjfaase 6y agoThis course follows the traditional approach to writing parsers. These traditional approaches were developed in times when memory was scarce and where back-tracking was impossible, simply because files were too large to be stored in RAM. Back-tracking parsers are much easier to write and in most cases performance can be brought to acceptable levels by applying caching. I have experimented with developing interpreting parsers that work with user-friendly grammar representations, and discovered that using caching can result in acceptable performance. I also discovered that a small interpreter often is faster than generated code, probably due to a better CPU cache performance. For two examples of these approaches see: https://github.com/FransFaase/IParse https://github.com/FransFaase/IParse and https://github.com/FransFaase/RawParser https://github.com/FransFaase/RawParser (WIP).
- sleavey 6y agoGuido van Rossum talks about this in his series on designing a PEG parser for Python [1], now used in 3.9. [1] https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d41b2ed60 https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d...
- DmitrySoshnikov 6y agoYes, backtracking still might be an option although has its known limitations in terms of parallel paths. We describe backtracking in this class too. The LL in the the view of manual Recursive descent is the most used on practice along with combinators and LALR(1).
- red_admiral 6y agoI don't mind paying for quality content (and I mind paying in cash a lot less than paying with personal data), but if someone wants a free alternative to this, I recommend https://craftinginterpreters.com/ https://craftinginterpreters.com/ . Bit lighter on the theory side, but exactly what you need if you want to write a parser in practice.
- _0ffh 6y agoFunny, I used to dig into everything about parsing that I could get my grubby fingers on, and now I don't even care anymore. Use recursive descent + TDOP for expressions!
- nly 6y agoTDOP / Pratt parsing is basically the same as recursive descent, it's just an optimization where rules with the same or lower precedence are matched iteratively rather than recursively. I can't find the link now but I found a great page once where this was shown, and it made all the complexity vanish for me.
- _0ffh 6y agoYeah, the advantage here is that once you wrote your Pratt parser it's a nice, quite generic piece of code that you can just drop into any new project, reconfigure a bit and it does it's job. Don't know what page you mean, but personally I first stumbled upon it on Douglas Crockford's page [1]. A couple of years later Eli Bendersky did a nice writeup for Python [2]. I wrote my first Pratt parser in D, based on Crockford's. It was a learning project that ended up as a Javascript interpreter. I parsed JS into a Lispy syntax tree and added a simple Lisp interpreter based on Norvig's [3]. In the meantime I've switched my default language (to Nim [4]), but I've since never used anything but RD and/or Pratt for any parsing job. [1] https://crockford.com/javascript/tdop/tdop.html https://crockford.com/javascript/tdop/tdop.html [2] https://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing/ https://eli.thegreenplace.net/2010/01/02/top-down-operator-p... [3] https://norvig.com/lispy.html https://norvig.com/lispy.html [4] https://nim-lang.org/ https://nim-lang.org/
- nly 6y agoI found it : https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#more_climbing https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#more_clim... It shows the transformations that get you from recursive descent to table driven precedence climbing Pratt/TDOP and precedence climbing are actually the same algorithm: https://www.oilshell.org/blog/2016/11/01.html https://www.oilshell.org/blog/2016/11/01.html ...so basically everything can be derived from simple, straightforward predictive recursive descent.
- kayson 6y agoThis is really great! Thanks for posting. Watched the first video on youtube and just grabbed the rest on Udemy. Your style works perfectly for me.
- DmitrySoshnikov 6y agoThanks for the feedback, and glad to see more engineers interested in deeper topics!