Re: precedence modification?

richardm@cogs.susx.ac.uk (Richard Matthias) wrote (re recursive descent parsing of C++):


>Could you (anyone) expand on the phrase "precedence modification when
>handling expressions" for me? I've not seen it in any compiler texts
>(although these rarely cover such complex languages as c++
>anyway). SIGPLAN references are gratefully received too :-)


Here's one way to do precedence parsing in a recursive descent framework,
from an old comp.compilers posting of mine. It's really not hard to use,
and I think there's example code in C (it looks horrible, of course, but
there's examples of how to do some pretty grungy things) in the
comp.compilers archive.
-
Keith Clarke
Keith.Clarke@dcs.qmw.ac.uk




> Subject: Re: compact recursive-descent parsing of expressions
> Date: Tue, 26 May 1992 14:14:38 GMT
> ...
> 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
> otherwise 0
> endcase
> endproc
>
> proc RightAssoc(c) =
> case c of "^": true;
> otherwise false
> endcase
> endproc
>
> Then there are two routines for doing the parsing; one does atomic things
> (factors, primaries - e.g. bracketed expressions, numbers), the other does
> infix expressions.
> proc parseE(prec) =
> initialise p:=parsePrimary();
> while Priority(input^) >= prec do begin
> let oper = get(input);
> let oprec = Priority(oper);
> p := mknode(p,
> oper,
> parseE(if RightAssoc(oper) then oprec else oprec+1))
> end;
> return p
> endproc
>
> proc parsePrimary() =
> case input^ of
> "(" :
> begin
> get(input);
> let p=E(1);
> if input^ <> ")" then fail fi;
> return p
> end;
> otherwise:
> if input^ in ['a'..'z'] then
> return mkleaf(input^)
> else
> fail
> fi
> endcase
> endproc
>
>
> 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
> proof-by-transformation.
>
> 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.
--


Keith Clarke, QMW
--

Return to the comp.compilers page.
Search the comp.compilers archives again.