Re:Advanced Compilers: Self-Guided Online Course
by haberman on Friday December 11, 2020 @08:57PM
(#25394550)
> Packrat parsers are notably faster than recursive descent parsers
I think this needs to be qualified. I don't think a packrat parser is going to beat a deterministic top-down parser. Maybe the packrat parser will win if the recursive descent parser is backtracking.
Re:Advanced Compilers: Self-Guided Online Course
by morelisp on Saturday December 12, 2020 @05:32AM
(#25397306)
True - the performance of a top-down parser is going to depend on if/how often it backtracks and how much lookahead it requires. But this requires control over your grammar which you might not have i.e. you are parsing a standardized programming language. Practically speaking, unless you want two separate parsing engines in your IDE, that Lisps are actually LL(1) and Python and Java are "almost LL(1)" doesn't get you closer to parsing C++.
Packrat parsers are equivalent to arbitrary lookahead in either LL or LR grammars.
Re:Advanced Compilers: Self-Guided Online Course
by specialist on Saturday December 12, 2020 @01:55AM
(#25396264)
u/morelisp may have meant faster to develop, not runtime performance.
There are varying techniques to improve error recovery for all forms of parsing but hacked-up recursive descent (certainly the most common kind of parser I still write for my hacked-up DSLs!) have poor error recovery unless you put in the work. Most LR parsers are also awful by default.
When I was in university most focus was on LL and LR parsers with no discussion of error recovery and more focus on memory usage/bounds than speed. I also have no idea how common it is to teach combinator-based parser grammers these days; stuff like ANTLR and yacc dominated during my studies. This would add another level of unfamiliarity for students going to work on a "real compiler".