10 Mar
2025
10 Mar
'25
3:19 p.m.
I was working at the whiteboard during a job interview once. I had been
asked to write a function to report if its input had balanced parentheses.
No problem: I wrote an RD parser in Python (which I prefer for
whiteboarding) to detect balance and return True if the parse was
successful and False if EOF was reached.
I was starting to write some tests when the interviewer interrupted me.
"What is that?"
"It's a recursive descent parser. It detects if the input is well-formed."
Blank look.
I started to walk him through the code.
He interrupted me. "Excuse me, I'll be back in a few minutes."
Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the
recruiter will get back to you." That's the last I hear from them.
On Mon, Mar 10, 2025, 12:10 AM Rob Pike <robpike(a)gmail.com> wrote:
A rare case where I disagree with you, Doug. If the
language is reasonably
regular (I do not mean in the strict Kleene sense), a recursive descent
parser is not much harder to write than a yacc grammar, and much smoother
at providing good error messages. Having done many yaccs and many RD
parsers, I no longer go to yacc.
To put it another way, there are few programming tasks I enjoy more than
writing a recursive descent parser for a sane language.
Now if the language is not so regular, my position might shift. I do
recall Bjarne dynamically editing the generated tables mid-parse to get
yacc to handle at least one stage of C++'s development.
Another way to think of it is that if you are designing the language and
it is undergoing frequent changes in grammar, yacc could certainly be move
you along faster. But even then once things had settled I'd still redo it
as RD, for the quality of the result.
You can credit Stephen R. "Software" Steve for this change in my thinking.
-rob
On Mon, Mar 10, 2025 at 1:12 PM Douglas McIlroy <
douglas.mcilroy(a)dartmouth.edu> wrote:
everyone
should write for their first compiler in Pascal for a
simple language and no cheating using YACC. You need to write the whole
thing if you want to understand how parsing really works.
Yacc certainly makes it easier to write parsers for big grammars, but
it's far from cheating. You need to know a lot more about parsing to use
Yacc than you need to roll your own.
Hand parsing of a tiny grammar is almost a necessary step on the way to
understanding Yacc. But I think hand-building the whole parser for a
compiler is unnecessary torture--like doing trigonometry with log tables.
Doug