Tue, 16 Nov 1993 16:57:33 GMT

Related articles |
---|

Transparent recursive descent doug@netcom.com (1993-11-01) |

Re: Transparent recursive descent norman@flaubert.bellcore.com (1993-11-02) |

Re: Transparent recursive descent Postedforpatl@goldfish.mitron.tek.com (1993-11-04) |

Re: Transparent recursive descent doug@netcom.com (1993-11-16) |

Newsgroups: | comp.compilers |

From: | doug@netcom.com (Doug Merritt) |

Summary: | How it's different than the usual |

Keywords: | parse, code |

Organization: | Netcom Online Communications Services |

References: | 93-11-012 |

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*

*>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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.