Thanks 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.
Parsing Algorithms
31–40 of 87 posts
Re: Parsing Algorithms
#32I'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
Yes, 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".
Re: Parsing Algorithms
#33Any chance of also including GLL (generalized LL)? I found the paper ( http://dotat.at/tmp/gll.pdf ) quite hard to follow, and haven't been able to find a good explanation anywhere else.
Just 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"…
Parsing with derivatives is not all that slow: https://www.microsoft.com/en-us/research/uploads/prod/2019/0...
The paper shows that it can compete with re2 (by google).
Re: Parsing Algorithms
#34Earlier quoted context omitted.
Great 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.
To 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.
Yes, to some degree -- Syntax tool normally support lexer states, and the same "while" token may mean a keyword or the property/field name of a struct. You can find more details of the lexer states in the docs.
Re: Parsing Algorithms
#35Apologies 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 understa…
Yes, 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.
Re: Parsing Algorithms
#36Is the site down?
Should be up by now; seems auto-DDOS'ed, lol
Re: Parsing Algorithms
#37FWIW, 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…
Yes, 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).
Re: Parsing Algorithms
#38Earlier quoted context omitted.
Just 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"…
Parsing with derivatives is not all that slow: https://www.microsoft.com/en-us/research/uploads/prod/2019/0... The paper shows that it can compete with re2 (by google).
This 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.
Re: Parsing Algorithms
#39Earlier quoted context omitted.
Not free but also very good is https://interpreterbook.com/
Both 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 and https://changelog.com/gotime/107 .
Thanks for sharing the podcast links, I hadn't known about that
Re: Parsing Algorithms
#40Earlier quoted context omitted.
Yep, that was a typo, fixed it
Ah okay. Note that GLR isn't exactly modern (1974). However, I would also remove "modern" as a requirement here... what really matters is how good the algorithm is, not how old it is. "Modern" algorithms easily end up being less powerful than the old ones... they just end up becoming popular due to other factors, e.g. simplicity.
"Advanced" would have been more expressive, agreed.
In the sense that LALR and LL with limited lookahead are the introductory parsing algorithms which everyone knows, and there's a reason for that.