Re: precedence modification?

richardm@cogs.susx.ac.uk (Richard Matthias) writes:


>Mike Ball (michael.ball@Eng.Sun.COM) wrote:
>: Just for the record, the Sun C++ compiler, which is based (as were a number
>: of commercial compilers) on the TauMetric frontend, uses recursive descent,
>: with a precedence modification when handling expressions.
>
>Could you (anyone) expand on the phrase "precedence modification when
>handling expressions" for me?


I assume it means that expressions are parsed using an ambiguous
grammar disambiguated via precedences rather than by using a more
complicated unambiguous grammar.


For example, instead of using a grammar fragment such as


expr --> term '+' expr | term ;
term --> factor '*' term | factor ;
factor --> simple_expr ;


you would instead use an ambiguous grammar rule such as


expr --> expr '+' expr
| expr '*' expr
| simple_expr
;


and disambiguate this by assuming that '*' and '+' are both
right-associative, and '*' has a higher precedence than '+'.
This would then be implemented as something vaguely like the
following untested (and probably buggy ;-) C-like pseudo-code:


int max_precedence() { return 10; }


int precedence(token op) {
switch(op) {
case '+': return 1;
case '*': return 2;
}
}


expr parse_expr() {
return parse_expr_with_prec(max_precedence());
}


expr parse_expr_with_prec(int context_precedence) {
expr x = parse_simple_expr();
token op = get_token();
if (is_operator(op) && precedence(op) < context_precedence) {
expr y = parse_expr_with_prec(precedence(op));
return build_expr(op, x, y);
} else {
unget_token(op);
return x;
}
}


--
Fergus Henderson <fjh@cs.mu.oz.au>
WWW: <http://www.cs.mu.oz.au/~fjh>
PGP: finger fjh@128.250.37.3
--

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