[antlr-interest] Translating expressions - advice?

[Jim Idle]

If the output language has the same operator precedence as the input
language then there is no need to add additional parens. Just preserve the
presence of parens in the input and reflect them in the output:

expression : expr -> ^(EXPRESSION expr) ; // In AST will indicate ()
expr : orexpr -> orexpr ; // In AST, indicates no ()
...
atom : LPAREN! expression RPAREN!  // Yields EXPRESSION node, which means
()

---

expression
  : ^(EXPRESSION expr)
  ;


expr
  : ^(AND expr expr)
   ... etc
  | atom
  ;

atom : INT
     | expression // Parens were present
;


If you are trying to remove extraneous parens from the input then you
would need to know the operations on either side of the AND and OR and
decide if the discovered expressions are required. Remember that the
parens are sometimes extraneous but used to  clarify and expression
though, so removing them may not be the best thing to do.

Jim


> -----Original Message-----
> From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-
> bounces at antlr.org] On Behalf Of Hans-Juergen Rennau
> Sent: Monday, May 09, 2011 8:16 AM
> To: Bart Kiers
> Cc: antlr-interest at antlr.orginterest
> Subject: Re: [antlr-interest] Translating expressions - advice?
>
> Hi Bart, thank you for considering my question! Indeed, what I wrote
> was perhaps misleading. Giving the example
>    (((a OR b) OR c) AND d)
>
> I meant the result of translating the AST into text in a "canonical
> way", that is, writing this concatenation:
>
> formula "R"
>    : ^(operator ldefOperand rightOperand) => this string: openBracket +
> leftOperand + closeBracket + operator + openBracket + rightOperand +
> closeBracket
>
> I suppose a deep tree created as sketched in the previous posting, that
> is, by the scheme
>    : operand (operator^ operand)*
>
> can be safely translated by applying the rule given above ("R")
> recursively. So far, so good. But the brackets are superfluous unless
> the current operator has a lower precedence than the operator in the
> "context", the tree level of which the present operand is a child. For
> example, this input
>    A + B + C + D + E + F
>
> generates
> (((((A + B) + C) + D) + E + F)
>
> So my question amounts to: is it a good idea to accomplish the
> translation in these steps:
> a) build the AST in the standard way (meant for operation execution),
> creating a deep tree with one inner node per operator
> b) serialize it using an adapted form of "R", which uses or omits the
> brackets dependent on a rule parameter providing the context operator
>
> ? Or should one build the AST differently, namely, making the top-level
> operands of an operator the children of the operator, like:
> ^('+' A B C D E F)
>
> Thank you, and kind regards
> -- Hans-Juergen
>
>
>
>
> ________________________________
> Von: Bart Kiers <bkiers at gmail.com>
> An: Hans-Juergen Rennau <hrennau at yahoo.de>
> CC: "antlr-interest at antlr.org interest" <antlr-interest at antlr.org>
> Gesendet: Montag, den 9. Mai 2011, 16:16:53 Uhr
> Betreff: Re: [antlr-interest] Translating expressions - advice?
>
> Wait I think I misunderstood. Your example `(a OR (b OR (c AND d)))` is
> just an example expression, right?
> In that case, yes, these parenthesis are part of the token stream, but
> if you apply rewrite rules (or AST operators `^` and `!`) properly,
> these parenthesis are easily removed from your parse tree.
>
> See: http://www.antlr.org/wiki/display/ANTLR3/Tree+construction
> or: http://stackoverflow.com/questions/4931346/how-to-output-the-ast-
> built-using-antlr
>
>
> Regards,
>
> Bart.
>
>
> On Mon, May 9, 2011 at 4:10 PM, Bart Kiers <bkiers at gmail.com> wrote:
>
> I get the impression you think that when creating AST's, ANTLR inserts
> parenthesis (brackets). This is not the case: I guess what you're
> seeing is just the tree's `toStringTree()` that displays these
> parenthesis to make the hierarchy of the tree apparent.
>
> >Or am I misinterpreting your question?
> >
> >
> >Regards,
> >
> >
> >Bart.
> >
> >
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-
> email-address