Re: Display a parse tree with minimum parentheses?

John Millaway <johnmillaway@yahoo.com> wrote:


>Given a parse tree representing a typical boolean expression, where the
>grouping is implicit in the tree structure, is there an algorithm to print
>the equivalent unambiguous infix expression with the minimum parentheses
>(preserving left-to-right order)?


>My best guess is that the the left subtree requires parentheses if the
>precedence of the right-most unparenthesized operator in that subtree is less
>than or equal to the precedence of the current operator, and similarly for
>the right subtree.


>[This is a very familiar question, and I think your idea about adding
>parens when there's a precedence drop is the right one. -John]


The reason this works is roughly this:


Precedence conditions disambiguates a grammar by prohibiting certain
expansion in the derivation of the parse tree. What one then usually does
is to admit those prohibited expansions by a rule:
        E -> '(' E ')'
together with an identity action that hides it away in the semantic object
created. Thus, if the parse tree generated has a prohibited combination, a
precedence drop, it must come from this parenthesis rule. So then put them
back when writing out the expressions.


This description makes it possible to handle more complex situations, for
example when using other grouping rules as well other than just "(...)".


    Hans Aberg

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