Fri, 22 May 1992 20:30:53 GMT

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) |

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

additional parameters:

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 implemented in Ada:

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;

Advance_To_Next_Token; -- Advance past operator

-- 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;

Advance_To_Next_Token; -- Advance past operator

-- 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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.