While 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?
Yes, I recommend "Parsing Techniques" book.
Parsing Algorithms
61–70 of 87 posts
Re: Parsing Algorithms
#62I 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!
Thank you for the feedback, glad you liked it, and glad to see more people interested in deeper CS topics!
Re: Parsing Algorithms
#63Earlier quoted context omitted.
With your IDE example you need the full parser and type checker to be "tolerant". For recursive-descent parsing, there isn't much to say about theory. You try to pick reliable synchronization points and prevent cascading errors. Here's the classic example: In a statement-oriented language like C#, synchronizing to the next statement upon finding an error by scanning for a semicolon token is a good place to start. (St…
Great details, thanks! > A benefit of a syntax with indentation-defined block structure is that you don't need to rely on balanced grouping tokens like { ... } In fact from the lexer perspective there is no big difference, the matching indent-dedent is the same token type as would be { and }
Indeed, the difference is that the lexer offers guarantees about the synthetic INDENT/DEDENT tokens. From an error sync perspective, the benefit is that the programmer (redundantly) re-asserts the block level every line by the amount of indentation. As a small addendum on Python's suspension of indentation tracking when nesting > 0, when I designed the syntax for indentation-based block structure in another language, I required such nested code to always have indentation beyond the current block's level even though no INDENT/DEDENT/NEWLINE tokens are emitted in this state. So this was legal:
x = (1 +
2)
x = (1 +
2)
x = (1 +
2)
x = (1 +
2)
x = (1 +
2)
x = (1 + 2)
The moral of a lot of these tricks is that by turning idioms and conventions into language enforced constraints you can detect programmer errors more reliably and you can do a better job of error recovery. That said, even in a curly brace language like C# you could still use the indentation structure as a heuristic guide for error recovery--it's just going to be less reliable.
Re: Parsing Algorithms
#64I recommend compilers course by Alex Aiken from Stanford open
Professor 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.
Re: Parsing Algorithms
#65Earlier quoted context omitted.
Great details, thanks! > A benefit of a syntax with indentation-defined block structure is that you don't need to rely on balanced grouping tokens like { ... } In fact from the lexer perspective there is no big difference, the matching indent-dedent is the same token type as would be { and }
Indeed, the difference is that the lexer offers guarantees about the synthetic INDENT/DEDENT tokens. From an error sync perspective, the benefit is that the programmer (redundantly) re-asserts the block level every line by the amount of indentation. As a small addendum on Python's suspension of indentation tracking when nesting > 0, when I designed the syntax for indentation-based block structure in another language,…
Yeah, this makes sense, thanks.
Re: Parsing Algorithms
#66This 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 and https://github.com/FransFaase/RawParser (WIP).
Re: Parsing Algorithms
#67This 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…
Guido 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-de5d...
Re: Parsing Algorithms
#68Does 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#...…
Another commenter recommended rust-analyzer as a source of inspiration. the main author, matklad, has written some very interesting blog posts describing ideas used that might be of interest to you:
* https://rust-analyzer.github.io/blog/2020/09/16/challeging-L...
* https://rust-analyzer.github.io/blog/2020/10/24/introducing-...
* https://rust-analyzer.github.io/blog/2020/09/28/how-to-make-...
* https://matklad.github.io/2020/04/13/simple-but-powerful-pra...
* https://matklad.github.io/2020/04/15/from-pratt-to-dijkstra....
Re: Parsing Algorithms
#69For an alternative take on a related topic, this is really a fantastically well-written and practical (free) book: http://craftinginterpreters.com
I 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. Tha…
I second this. Recursive descent is so good. I've used it for all my languages with no issues.
Re: Parsing Algorithms
#70Does 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#...…
Tree-sitter is the library that Atom uses to parse as you type. It's incremental: if you just add one character, you don't have to parse the entire file from scratch. And it's robust: it tries to provide useful results even if there are syntax errors.
If you're more interested in the theoretical side of how it works, there are some talks and articles that cover it.