Re: parsing tools, was Dragon Book - update necessary?

Ed Davis <ed_davis@my-deja.com>
1 Nov 2000 18:30:59 -0500

          From comp.compilers

Related articles
[2 earlier articles]
Re: Dragon Book - update necessary? LLkParsing@aol.com (2000-10-12)
Re: Dragon Book - update necessary? rhyde@cs.ucr.edu (Randall Hyde) (2000-10-15)
Re: Dragon Book - update necessary? bruce@hoult.org (Bruce Hoult) (2000-10-19)
Re: Dragon Book - update necessary? rhyde@cs.ucr.edu (Randall Hyde) (2000-10-23)
Re: parsing tools, was Dragon Book - update necessary? LLkParsing@aol.com (2000-10-26)
Re: parsing tools, was Dragon Book - update necessary? rhyde@cs.ucr.edu (Randall Hyde) (2000-10-31)
Re: parsing tools, was Dragon Book - update necessary? ed_davis@my-deja.com (Ed Davis) (2000-11-01)
Re: parsing tools, was Dragon Book - update necessary? jim.granville@designtools.co.nz (Jim Granville) (2000-11-01)
Re: parsing tools, was Dragon Book - update necessary? iank@idiom.com (2000-11-01)
Re: parsing tools, was Dragon Book - update necessary? jmochel@foliage.com (2000-11-01)
Re: parsing tools, was Dragon Book - update necessary? joachim_d@gmx.de (Joachim Durchholz) (2000-11-01)
Re: parsing tools, was Dragon Book - update necessary? LLkParsing@aol.com (2000-11-01)
Re: parsing tools, was Dragon Book - update necessary? rhyde@cs.ucr.edu (Randall Hyde) (2000-11-04)
[2 later articles]
| List of all articles for this month |

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.