Re: Transparent recursive descent

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
>archives. -John]


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
simple memoization.


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.
Doug
------------------ term rewriting expression disambiguation: -------------
postfix_expr
: identifier
| CONSTANT
| STRING_LITERAL
| '(' expr ')'
;
unary_expr
: postfix_expr
| INC_OP unary_expr
| DEC_OP unary_expr
| unary_operator cast_expr
| SIZEOF unary_expr
| SIZEOF '(' type_name ')'
;
unary_operator
: '&'
| '*'
| '+'
| '-'
| '~'
| '!'
;
cast_expr
: unary_expr
| '(' type_name ')' cast_expr
;
multiplicative_expr
: cast_expr
| multiplicative_expr '*' cast_expr
| multiplicative_expr '/' cast_expr
| multiplicative_expr '%' cast_expr
;
additive_expr
: multiplicative_expr
| additive_expr '+' multiplicative_expr
| additive_expr '-' multiplicative_expr
;
shift_expr
: additive_expr
| shift_expr LEFT_OP additive_expr
| shift_expr RIGHT_OP additive_expr
;
relational_expr
: shift_expr
| relational_expr '<' shift_expr
| relational_expr '>' shift_expr
| relational_expr LE_OP shift_expr
| relational_expr GE_OP shift_expr
;
equality_expr
: relational_expr
| equality_expr EQ_OP relational_expr
| equality_expr NE_OP relational_expr
;
and_expr
: equality_expr
| and_expr '&' equality_expr
;
exclusive_or_expr
: and_expr
| exclusive_or_expr '^' and_expr
;
inclusive_or_expr
: exclusive_or_expr
| inclusive_or_expr '|' exclusive_or_expr
;
logical_and_expr
: inclusive_or_expr
| logical_and_expr AND_OP inclusive_or_expr
;
logical_or_expr
: logical_and_expr
| logical_or_expr OR_OP logical_and_expr
;
conditional_expr
: logical_or_expr
| logical_or_expr '?' logical_or_expr ':' conditional_expr
;
assignment_expr
: conditional_expr
| unary_expr assignment_operator assignment_expr
;
assignment_operator
: '='
| MUL_ASSIGN
| DIV_ASSIGN
| MOD_ASSIGN
| ADD_ASSIGN
| SUB_ASSIGN
| LEFT_ASSIGN
| RIGHT_ASSIGN
| AND_ASSIGN
| XOR_ASSIGN
| OR_ASSIGN
;
expr
: assignment_expr
;
--
Doug Merritt doug@netcom.com
--

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