Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| 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
Return to the
comp.compilers page.
Search the
comp.compilers archives again.