Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!mintaka!spdcc!iecc!compilers-sender
From: ressler@cs.cornell.edu (Gene Ressler)
Newsgroups: comp.compilers
Subject: Re: Minimizing parentheses in a postfix->infix converter output
Keywords: design
Message-ID: <1991Apr14.172800.17477@cs.cornell.edu>
Date: 14 Apr 91 17:28:00 GMT
References: <9104130521.AA00996@fiu.edu>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: ressler@cs.cornell.edu (Gene Ressler)
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Lines: 35
Approved: compilers@iecc.cambridge.ma.us

In article <9104130521.AA00996@fiu.edu> acmfiu@fiu.edu (ACMFIU) writes:
>I have a postfix->infix converter and need to output the least number of
>parentheses as possible. ...
>
>albert chin
>[It is my recollection that there is an easy way to do paren minimization,
>but the details escape me. Roughly, at each level you build the expression
>string, and wrap a subexpression in parens if its operator binds looser
>than the one in the current expression. -John]

As I recall, something like this is an exercise in the Dragon Book chapter
on syntax-directed translation.  John is right.  In a SDT, you can pass
down an inherited attribute consisting of the current operator.  (In a
tree-walker, of course, this is just a function parameter.)  Call this
attribute `parent'.  Then each operator's rule looks at `parent' to see if
it should emit `( E op E )', when parent binds tighter than op or just `E
op E', when it doesn't.  You also need an inherited attribute `side' that
tells whether the current operator is the left or right (or only) child of
its parent.  This allows rules for non-associative operators to
parenthesize their emitted code correctly; e.g. for A * D / (B * C), the
rule for '*' causes parens to be emitted when `*' is the right child of
'/'.

There are other details depending on the language you want to emit, and
other approaches work, too.  For instance, if you pass the code itself as
an attribute (rather than emitting a stream), then you can put parens
around everything, but strip them off when the current op binds more
loosely than the child; here you're using synthesized attributes.  The
school of hard knocks has convinced me that a the time to write out the
SDT before coding things like this is paid back many-fold.  Good luck.

Gene
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.