expression rewrites - how to?

While developing a Pascal to Ada translator, I've encountered a subproblem:


        The source language (Pascal) and the target language (Ada) have
        differing operator priorities (and associativity). The translator
        must rewrite expressions from the source language into those
        of the target language, while preserving the order of evaluation
        expressed in the source language. An additional constraint that
        is desirable is to keep the parenthesization present in the original
        source text, if this parenthesization is adequate to preserve the
        order of evaluation when translated into the target language.
        Additionally, the expression should be rewritten with minimal
        parenthesization.


To make the problem more concrete, assume that the source expression
is expressed as an expression tree, where each subtree contains
the operator and its direct descendants are the left and right hand
operands (or a single operand in the case of unary operators). The
resulting tree would have similar form, with nodes added or removed
as necessary to express the 'parenthesis operation'.


The source language (HP-Apollo Pascal) has the following operator
priorities (high-to-low).


  ~ NOT
  **
  & * / DIV MOD AND
  unary + -
  ! + - OR
  = <> < > >= <= IN
  AND-THEN OR-ELSE


(where ~ = bitwise NOT, ! = bitwise OR, &, = bitwise AND,
and <> is not equal). The exponentation operator, **, is right associative
The AND-THEN, OR-ELSE operators are an extension, and represent
'short-circuit' logical operations.) [I'm not sure about the
relative priority of unary +/- above.]


The Ada operators have the following precedence (high-to-low):


  ** ABS NOT
  * / MOD REM
  unary + -
  + - &
  = /= < <= > >= IN NOT-IN
  AND OR XOR AND-THEN OR-ELSE


(where /= is not equal, & is concatenation, and ** is right associative).


As we can see the major divergence is relative ordering of logical
operators (AND, OR, XOR, AND-THEN, OR-ELSE).


Would you please suggest an approach, algorithm, or any references that
might apply to the problem described above? Also, if I've missed
something important in summarizing the differences between Pascal
and Ada, I'd appreciate any corrections.


      thanks,


      - Gary
--
| Gary Funck gary@intrepid.com [uunet!uupsi!intrpd!gary]
| Intrepid Technology Inc., Mountain View CA (415) 964-8135
[This shouldn't be very hard. Make your expression tree, treating
grouping parens as a unary operator. Then recursively walk down the tree,
turning subtrees into infix. At each stage, look at the relative
precedence of the op at the root of each subtree and the current operator.
If the subtree's op is lower precedence than the current op, you have to
parenthesize the infix-ized subtree. You also have to parenthesize if the
precedence is equal but there are associativity problems. This keeps all
of the existing parens, and adds more as needed to keep the meaning the
same. For minimal parens, don't put the original parens in the parse
tree. -John]
--

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