|Transparent recursive descent email@example.com (1993-11-01)|
|Re: Transparent recursive descent firstname.lastname@example.org (1993-11-02)|
|Re: Transparent recursive descent Postedforpatl@goldfish.mitron.tek.com (1993-11-04)|
|Re: Transparent recursive descent email@example.com (1993-11-16)|
|From:||firstname.lastname@example.org (Doug Merritt)|
|Summary:||How it's different than the usual|
|Organization:||Netcom Online Communications Services|
|Date:||Tue, 16 Nov 1993 16:57:33 GMT|
It took me a while to reply, so I'm including my original intro paragraph
to refresh people's memories:
>In past years I've been disgruntled that the classic approach to recursive
>descent parsing of arithmetic expressions is inherently complex, long, and
>unintuitive compared with the conceptual simplicity of expressions.
Our moderator commented:
>[I can't say that this looks all that different from any other R.D.
>expression parser I've seen, but it's nice to have the code for the
For comparison, below is the ever-popular ANSI C committee's YACC grammar
(I've excerpted the part that deals with C expressions), which takes the
traditional approach. They rewrote the grammar to avoid using precedence
rules so, that it can map directly into a recursive descent parser, one
function call per left hand side.
I don't have the energy to expand it into the recursive descent form, but
obviously the following hundred lines of grammar would expand noticeably.
By comparison, the C code I posted corresponds 1-to-1 with what the YACC
grammar would look like if one *did* use precedence rules and also relied
on YACC to disambiguate the remaining shift/reduce conflicts. The C
version does that by remaining ambiguous but avoiding backtracking by some
Maybe you've seen this approach taken before (I wouldn't be surprised),
but I'm fairly confident it's not a widely known approach with programmers
in general, because I keep seeing people's R.D. expression parsers follow
the classic lines below.
Hope that clarifies a bit.
------------------ term rewriting expression disambiguation: -------------
| '(' expr ')'
| INC_OP unary_expr
| DEC_OP unary_expr
| unary_operator cast_expr
| SIZEOF unary_expr
| SIZEOF '(' type_name ')'
| '(' type_name ')' cast_expr
| multiplicative_expr '*' cast_expr
| multiplicative_expr '/' cast_expr
| multiplicative_expr '%' cast_expr
| additive_expr '+' multiplicative_expr
| additive_expr '-' multiplicative_expr
| shift_expr LEFT_OP additive_expr
| shift_expr RIGHT_OP additive_expr
| relational_expr '<' shift_expr
| relational_expr '>' shift_expr
| relational_expr LE_OP shift_expr
| relational_expr GE_OP shift_expr
| equality_expr EQ_OP relational_expr
| equality_expr NE_OP relational_expr
| and_expr '&' equality_expr
| exclusive_or_expr '^' and_expr
| inclusive_or_expr '|' exclusive_or_expr
| logical_and_expr AND_OP inclusive_or_expr
| logical_or_expr OR_OP logical_and_expr
| logical_or_expr '?' logical_or_expr ':' conditional_expr
| unary_expr assignment_operator assignment_expr
Doug Merritt email@example.com
Return to the
Search the comp.compilers archives again.