RE: C++ intermediate representation.

Chris Clark said:


> Second, even if one is convinced that a backtracking recursive descent
> parser is the desired implementation, there are many fine tools that
> will create recursive descent parsers with backtracking from grammars.
> Thus, one doesn't have write the parser by hand. Writing a grammar
> and using a tool to translate it into code allows the grammar to be
> checked that it is formally correct--something that is much harder to
> do with code (and I've never heard of anyone doing on a hand-written
> parser).


Egads, yes, I agree. I would never attempt in a million years to write a
recursive descent parser "by hand" except as an exercise on something such
as a simple expression evaluator, just to get a feel for how it's done.


As an example of one difficult to find construct: how would one determine by
looking at a hand-written C++ RD parser that one hasn't introduced indirect
left recursion with possibly lambda construct?


In the following grammar:


X -> A B;
A -> "a" | "b" | #lambda;
B -> C | X;
C -> A;


one can see, and one can surely use automated techniques to tell us that X
is potentially left recursive, and will crash in stack-hell fed "c". In a
hand written RD parser, where the cycle may occur as a result of some deep
reference back to X, all bets are off. The Grammar Forge, and other tools,
will tell you that LL(k) rules have been broken before you ever crash a
computer, given a construction like that, whereas handwritten parsers will
tell you when someone one day feeds the parser a string that has neither an
"a" or "b" in the expected place.


The hiding of left-recursion via deep references is just one such example.


Besides that, automatically generated grammars often give you a parse tree
for free, thereby reducing the need for semantic code in each function to
build a tree (or manipulate it).


--
Chev. Quinn Tyler Jackson
Computer Scientist, Novelist, Poet


http://members.shaw.ca/qjackson/

Return to the comp.compilers page.
Search the comp.compilers archives again.