Browse Prior Art Database

Traversal of Prefix Order Operators by Iteration

IP.com Disclosure Number: IPCOM000103230D
Original Publication Date: 1990-Aug-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 1 page(s) / 45K

Publishing Venue

IBM

Abstract

This article describes a method for traversing a prefix-ordered set of operators and operands to produce a post-ordered instruction sequence during code generation. An iterative technique that avoids the overhead of recursive descent calls and keeps the entire expression visible on a stack rather than being hidden in recursive stackframes is disclosed.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 83% of the total text.

Traversal of Prefix Order Operators by Iteration

      This article describes a method for traversing a prefix-ordered
set of operators and operands to produce a post-ordered instruction
sequence during code generation. An iterative technique that avoids
the overhead of recursive descent calls and keeps the entire
expression visible on a stack rather than being hidden in recursive
stackframes is disclosed.

      The code generator portion of a compiler uses an iterative
implementation of recursive descent to process a pre-order operation
sequence.  Iterative techniques are advantageous over recursive ones
because all operands and operators are available on stacks for
processing, rather than in separate stack frames.  This allows
optimizations to be performed that would otherwise require additional
passes in the compiler.

      Traditional interactive expression parsing algorithms require
two stacks:  one for operands and one for operators. The entire
push/pop sequence of operators and operands serves only to convert
pre-order to post-order, which must then be further processed into
machine code.

      This implementation uses a single stack of instruction-
list/operand pairs, such that an instruction-list is associated with
the last of its operands to appear in the pre-order sequence.  When
an input operator is seen, the instruction-list for that operator is
generated, with pointers to the unsatisfied operands pushed on the
stack above it.  As the in...