Operator precedence and Recursive Descent

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

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