Home > Archive > Compilers > April 2004 > Display a parse tree with minimum parentheses?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Display a parse tree with minimum parentheses?
|
|
| John Millaway 2004-04-14, 1:31 am |
| 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)?
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.
Thanks, -John M
[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]
| |
| Daniel C. Wang 2004-04-15, 1:35 pm |
| See
Unparsing Expressions With Prefix and postfix Operators
Norman Ramsey
http://citeseer.ist.psu.edu/194913.html
John Millaway 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)?
For an algorithm and code in SML to actually do it. The ideas can probably
be easily adpated to any language with a little work.
| |
| Hans Aberg 2004-04-15, 1:35 pm |
| 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
| |
| Clint Olsen 2004-04-15, 1:35 pm |
| 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
|
|
|
|
|