|compact recursive-descent parsing of expressions firstname.lastname@example.org (1992-05-25)|
|Re: compact recursive-descent parsing of expressions email@example.com (1992-05-26)|
|From:||firstname.lastname@example.org (Keith Clarke;W208a)|
|Organization:||Computer Science Dept, QMW, University of London|
|Date:||Tue, 26 May 1992 14:14:38 GMT|
In 92-05-137 email@example.com writes:
>It's used by lcc, but you needn't look there for a description:
>%T Compact Recursive-descent Parsing of Expressions
>%A D. R. Hanson
>%J SOFTWARE - Practice and Experience
>%D December 1985
>%K Recursive-descent parsing, Expression parsing, Precedence, Compilers
I wrote up a method I'd been teaching for a couple of years at least,
after reading David Hanson's 1985 paper. You don't need complicated
tables for my method, and the code is very simple too! The program can
parse an expression using a number of procedure calls approximately equal
to the number of nodes in its abstract syntax tree, independent of the
number of precedence levels in the grammar. The operator symbols of any
particular expression grammar appear only in two small functions, which
frequently removes the need for grammar transformation before the method
can be used. Hanson's paper shows how the number of procedure definitions
used in a recursive descent parser can be reduced, but does not show how
the number of procedure activations can be reduced.
Two simple functions Priority and RightAssoc are used to map character
values to numbers (representing precedences) and booleans. I give sum,
product and exponentiation the usual behaviour.
proc Priority(c) =
case c of
"+" : 1; "*" : 2 ; "^" : 3
proc RightAssoc(c) =
case c of "^": true;
Then there are two routines for doing the parsing; one does atomic things
(factors, primaries - e.g. bracketed expressions, numbers), the other does
proc parseE(prec) =
while Priority(input^) >= prec do begin
let oper = get(input);
let oprec = Priority(oper);
p := mknode(p,
parseE(if RightAssoc(oper) then oprec else oprec+1))
proc parsePrimary() =
case input^ of
if input^ <> ")" then fail fi;
if input^ in ['a'..'z'] then
The research report is available still, I think:
K.M.Clarke (1986) "The top-down parsing of expressions", Research Report
383, Dept of Computer Science, QMC.
QMC is now QMW, Mile End Rd, London, UK. I mostly do a sort of
>Still, like most good ideas that someone probably patented last year, this
>one has been about for some time!
My method turned out to have been used in Dave Turner's SASL compiler
(University of St Andrews) - later 70s or early 80s?; a very similar
method was later described in Richard O'Keefe's Prolog book. Larry
Paulson's (1991) ML book has a similar algorithm. Still, I've never come
across it in a compiling textbook.
QMW, University of London.
Return to the
Search the comp.compilers archives again.