Re:We Need to Know LR and Recursive Descent Parsing Techniques
by yarg on Tuesday January 17, 2023 @06:27PM
(#34421004)
What do you mean by "regular expression"?
Because they're generally not regular.
If you mean a parser for a notation expressing regular grammars, then it only takes a couple of hours to knock out a recursive descent parser (if you know what you're doing).
Re:We Need to Know LR and Recursive Descent Parsing Techniques
by jcranmer on Tuesday January 17, 2023 @07:57PM
(#34421916)
I mean implementable by your standard regex library in your favorite programming language, which is largely a PCRE-style regular expression (although backreferences and lookahead/lookbehind aren't necessary).
* The lexing/parsing split, and that lexing is basically applying regexes over and over again. (The technique of using a regular expression engine to write your own lexer is a fun idea, but probably should be cut for time).
* What "context-free grammar" means, and the more-or-less standard syntax for writing CFGs.
* Explain how to build a parser with recursive descent as the example. But...
* Demonstrate expression parsing that supports precedence and both left- and right-associativity. We know how to do this very easily algorithmically (there's several different methods, in fact), it's very natural to describe in this manner, and it's so goddamn common that languages have precedence. (As a side note, expressing precedence via AddExpr/MulExpr in grammar should be covered here, since it's commonly written as such in grammars, but if I were ever to build a parser generator, I'd support a syntax that didn't require manual factoring like that).
* Introduce LL and LR parsing in theory. Do not introduce first/follow sets, or the state machine construction for an LR parser. Instead, the points to cover are what makes the languages hard to parse (e.g., ambiguous). Strict adherence to LL/LR grammar isn't necessary and sometimes counterproductive (left-factoring LL grammars is the case in point here).
* Do cover dangling-else ambiguity at some point. It's a great example of something that wasn't discovered until people started applying theoretical tools to existing languages (in this case, ALGOL).
Like the author, I think there is some merit to LR parsing as a theoretical concept, but the emphasis placed on it in existing compiler courses and textbooks is way too high. The end goal of parsing theory, for most students, should be to understand how to build languages that admit unambiguous parsers that require no backtracking, and LR parsers cover a very large subset of those languages. It is also helpful to get people to think about lexing and parsing in more formal terms--I have definitely seen a few people go "oh, that makes things much easier!" when they see the divide between lexing and parsing.