acmfiu@fiu.edu (ACMFIU) (04/13/91)
I have a postfix->infix converter and need to output the least number of
parentheses as possible. The resulting infix expression is kept in a
binary tree and I just traverse the tree outputting the left/right
parentheses at each level. This was done for convenience. but now I'd
like to make it better. As this will involve, to my knowledge, some
lookahead to test the next operator, I don't see the binary tree as the
best data structure. What can I use to make the lookahead "not hard" and
how would I go about doing what I want?
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]
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.ressler@cs.cornell.edu (Gene Ressler) (04/15/91)
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.
firth@sei.cmu.edu (Robert Firth) (04/15/91)
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. The resulting infix expression is kept in a >binary tree and I just traverse the tree outputting the left/right >parentheses at each level. Easy. You need to know the priority of the operators (obviously), and, before emittinga subtree that isn't a leaf, you compare the priority of its operator to that of the parent node. If the sub has a higher priority, no parens. If the sub has a lowe priority, parens always. If the sub has the same priority, then you use parens around the right subtree for a left-associative operator, and the left subtree for a right-associative operator. Examples: ab*c+ => a*b+c ab+c* => (a+b)*c abc-- => a-(b-c) Hope that helps. -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
ge@dbf.kun.nl (Ge' Weijers) (04/15/91)
In comp.compilers acmfiu@fiu.edu writes: >I have a postfix->infix converter and need to output the least number of >parentheses as possible. The resulting infix expression is kept in a >binary tree and I just traverse the tree outputting the left/right >parentheses at each level. ... I assume you use a recursive traversal routine on the tree. The algorithm is not hard. Just pass a priority to this expression-printer: prio[ADD] := 1; prio[MUL] := 2; PROCEDURE PrintExpression (node: EXPRESSION, ctxPrio: PRIO); BEGIN IF node is primary THEN PrintPrimary(node); ELSIF node is binary operator expression THEN IF ctxPrio > prio[node^.operator] THEN write('('); END; PrintExpression(node^.left, prio[node^.operator]+1); write(repr[node^.operator]); PrintExpression(node^.right, prio[node^.operator]); IF ctxPrio > prio[node^.operator] THEN write(')'); END ELSE ... (* other syntactic constructs *) END END PrintExpression; This works for languages that have left-to-right binding. The algorithm can be made more general by adding left- and right-priority arrays, for instance for right-to-left binding X ** Y operators. As you can see deciding whether to print the parentheses requires knowledge of the operator one level up in the tree. In RPN this operator can be arbitrarily far ahead in the input. I'm afraid you have to use a tree or reading the expression backwards. This gives an unreversed Polish or prefix representation of the tree, which can be scanned by an algorithm quite similar to the tree traversal algorithm. -- Ge' Weijers Internet/UUCP: ge@cs.kun.nl Faculty of Mathematics and Computer Science, (uunet.uu.net!cs.kun.nl!ge) University of Nijmegen, Toernooiveld 1 6525 ED Nijmegen, the Netherlands tel. +3180652483 (UTC-2) -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.