Re: precedence modification? (Keith Clarke)
17 Jan 1997 23:26:32 -0500

          From comp.compilers

Related articles
Re: Is YACC / PCCTS used in commercial comp michael.ball@Eng.Sun.COM (1997-01-03)
Re: precedence modification? (1997-01-12)
Re: precedence modification? (1997-01-15)
Re: precedence modification? (1997-01-17)
| List of all articles for this month |

From: (Keith Clarke)
Newsgroups: comp.compilers
Date: 17 Jan 1997 23:26:32 -0500
Organization: Dept of Computer Science, QMW, University of London
References: 97-01-026 97-01-089
Keywords: parse (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

> 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

Post a followup to this message

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