# Operator precedence and Recursive Descent

## stt@inmet.com (Tucker Taft)Fri, 22 May 1992 20:30:53 GMT

From comp.compilers

Related articles
LL vs LR, no jihad initiation, but... parrt@ecn.purdue.edu (1992-05-11)
Re: LL vs LR, strengths and weaknesses henry@zoo.toronto.edu (1992-05-15)
Operator precedence and Recursive Descent stt@inmet.com (1992-05-22)
Re: Operator precedence and Recursive Descent graham@maths.su.oz.au (1992-05-23)
Re: Operator precedence and Recursive Descent man@labrea.zko.dec.com (1992-05-26)
| List of all articles for this month |

 Newsgroups: comp.compilers From: stt@inmet.com (Tucker Taft) Summary: Recursive plunge can be avoided Keywords: LL(1), parse Organization: Intermetrics Inc, Cambridge MA References: 92-05-059 92-05-103 Date: Fri, 22 May 1992 20:30:53 GMT

There has been some discussion of the problem of "recursive plunge" when a
language has many levels of operator precedence. We found a neat trick
that solves this problem in the "lcc" compiler recently made available by
David Hanson.

It works best in recursive descent parsers because it is so easy to pass

1) Have exactly one function for parsing operator expressions
2) Pass it the precedence at which to stop accumulating operators

Has this technique been known for a long time and/or reinvented
repeatedly?

Here is the (rough) algorithm for this "parse_operator_expression"

function Parse_Operator_Expression(
Left_Precedence : Operator_Precedence := Operator_Precedence'FIRST)
return Expression_Tree is
-- Parse operands and operators.
-- Quit parsing if next operator has precedence <= Left_Precedence
Op : Token_Type;
Result_So_Far : Expression_Tree;
-- Next_Token is a global, initialized by Advance_To_Next_Token
begin
if Is_Unary_Operator(Next_Token) then
Op := Next_Token;

-- Leftmost operand is unary-op tree
Result_So_Far := Make_Unary_Op_Tree(
Operator => Op,
Right_Operand => Parse_Operator_Expression(
Left_Precedence => Precedence(Op)));
-- Recurse with precedence of unary operator to gets
-- its operand
else
-- Leftmost operand is atom
Result_So_Far := Parse_Atom; -- Note: No "plunge" needed here
end if;

-- We have leftmost operand, now accumulate more operators
-- and operands
while Is_Binary_Operator(Next_Token) and then
Precedence(Next_Token) > Left_Precedence loop
Op := Next_Token;

-- Assuming Left Associativity for ops at same precedence
Result_So_Far := Make_Binary_Op_Tree(
Left_Operand => Result_So_Far,
Operator => Op,
Right_Operand => Parse_Operator_Expression(
Left_Precedence => Precedence(Op)));
-- Recurse with precedence of binary operator
-- to get its right operand
end loop;

-- Return now, since we can't accumulate any more operators
return Result_So_Far;
end Parse_Operator_Expression;

To parse a whole expression, call "Parse_Operator_Expression" without
parameters, so it defaults to the lowest operator precedence (actually, 1
lower than the precedence of the lowest precedence operator).

-S. Tucker Taft stt@inmet.com
Intermetrics, Inc.
Cambridge, MA 02138
--

Post a followup to this message