1 Nov 2000 18:30:59 -0500

From: | Ed Davis <ed_davis@my-deja.com> |

Newsgroups: | comp.compilers |

Date: | 1 Nov 2000 18:30:59 -0500 |

Organization: | Deja.com - Before you buy. |

References: | 00-10-061 00-10-067 00-10-093 00-10-109 00-10-130 00-10-193 00-10-209 00-10-221 |

Keywords: | parse |

Posted-Date: | 01 Nov 2000 18:30:59 EST |

*>Besides, the only place recursion really kicks in is within*

*>complex arithmetic expressions. By using a bottom-up parser*

*>(say, operator precedence) here, you can speed this up if it*

*>turns out to be a problem.*

I think even this (excessive recursion) can be mostly controlled, using

a variation of recursive descent called precedence climbing.

Classic recursive descent parsing has three major problems:

The size of the code is proportional to the number of precedence levels.

The speed of the algorithm is proportional to the number of precedence

levels.

The number of precedence levels is built in.

However, precedence climbing solves all three of these, is simpler than

classic recursive descent, and for me at least, is simpler than

operator precedence.

Theodore Norvell has a wonderful little paper about this at:

http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

For additional references, see the following articles in the newsgroup

archive:

92-05-092, 103, 128, 130, 137, 140, 141

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.