Re: Display a parse tree with minimum parentheses?

haberg@matematik.su.se (Hans Aberg)
15 Apr 2004 12:29:32 -0400

          From comp.compilers

Related articles
Display a parse tree with minimum parentheses? johnmillaway@yahoo.com (John Millaway) (2004-04-14)
Re: Display a parse tree with minimum parentheses? danwang74@hotmail.com (Daniel C. Wang) (2004-04-15)
Re: Display a parse tree with minimum parentheses? haberg@matematik.su.se (2004-04-15)
Re: Display a parse tree with minimum parentheses? clint@0lsen.net (Clint Olsen) (2004-04-15)
| List of all articles for this month |
From: haberg@matematik.su.se (Hans Aberg)
Newsgroups: comp.compilers
Date: 15 Apr 2004 12:29:32 -0400
Organization: Mathematics
References: 04-04-034
Keywords: parse, tools
Posted-Date: 15 Apr 2004 12:29:32 EDT

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


Post a followup to this message

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