Re: Display a parse tree with minimum parentheses?

On 2004-04-14, John Millaway <johnmillaway@yahoo.com> wrote:
> For example, the parse tree for the expression, "a or b and c," would be
> naively printed as "(a or (b and c))," although no parentheses are
> required, assuming that the `and' operator has higher precedence than the
> `or' operator.
>
> 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.


Yes, I've implemented something similar to this in some language
translators where the languages have differing operator precedences. The
parse tree reflects the appropriate precedence for the source language, and
as you do the tree walk, you can check to see if the precedence of the
current operator is less than (rather than less than or equal to) the
parent operator. You know this to be true since the precedence of the
operators generally increase as you descend in the tree - barring
precedence override operators like parens.


Your algorithm is going to be similar except you'll have the proviso that
you'll be at the operator '()' and you'll want to check the parent operator
against the operator of it's child. If the child operator precedence is
less than the parent operator, then the parens were necessary. Otherwise,
prune the parens out of the tree. You can also short circuit redundant
parentheses by checking the last operator against the current one.


-Clint

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