We Need to Know LR and Recursive Descent Parsing Techniques

Re:We Need to Know LR and Recursive Descent Parsing Techniques by not2b on Tuesday January 17, 2023 @02:06PM (#34417127)

There's been a movement away from LR parsing in favor of recursive descent, and it isn't only that many languages are not LR(1) (for example, C++ can require infinite lookahead). It's also that even if the grammar of the language is LR(1), the errors that users will make often don't fit cleanly into the Yacc/bison structure, so error messages will often be poor quality and improving them can feel like unstructured hacking. It's much easier to produce high-quality error messages with a recursive descent parser. Recursive descent is just closer to how people think, so language designers generally create languages that work well with it.

Now, if LR parsing were a simple topic, it would be OK for compiler classes to spend time on it. But it's complex enough that teaching it adequately takes a lot of time, and that time could be better spent on any number of other topics. Get the students to the point where they have a clean abstract syntax tree quickly and go from there.

[ Parent | on HN ]

Re:We Need to Know LR and Recursive Descent Parsing Techniques by bitL on Tuesday January 17, 2023 @02:44PM (#34417654)

LL(1) for recursive descent aren't very powerful; you might hack SQL with it but you still won't do C++ with it.

[ Parent | on HN ]

Re:We Need to Know LR and Recursive Descent Parsing Techniques by not2b on Tuesday January 17, 2023 @09:57PM (#34422913)

gcc's C and C++ parsers are handwritten recursive descent parsers. Years ago, Bison was used, and for C++ a third pass was required between the lexer and the parser to add the needed lookahead to differentiate complex type and function declarations. I didn't say anything about LL(1). The key thing here is that high quality compilers are doing it this way, eschewing parser generation tools.

[ Parent | on HN ]

Re:We Need to Know LR and Recursive Descent Parsing Techniques by bitL on Wednesday January 18, 2023 @09:53AM (#34427294)

I thought that GCC being a handwritten recursive descent parser was giving it a huge disadvantage compared to other compilers when it came to introducing new standards (I remember people complaining about it a lot in the past).

[ Parent | on HN ]

Re:We Need to Know LR and Recursive Descent Parsing Techniques by not2b on Wednesday January 18, 2023 @10:58AM (#34428334)

You're misinformed. clang also has a custom parser. Both gcc and clang have great support for new standards, though as those standards are evolving some features aren't there yet (but none of the missing features have anything to do with parsing difficulties). You can find lots of detail on feature coverage at https://gcc.gnu.org .

[ Parent | on HN ]

Re:We Need to Know LR and Recursive Descent Parsing Techniques by dan-robertson on Saturday January 21, 2023 @04:13PM (#34470606)

The author of the article links to a paper which presents a better error recovery method for lr grammars which the authors implemented in a rust library. Does that help with the error messages much?

[ Parent | on HN ]