[antlr-interest] Tree transformation

[mzukowski at yci.com]

Something like this should do the trick except for the EMPTY_LIST bit:

parent_expr : #(l:PARENT! s:stmt_list);

stmt_list : stmt {##=#([STATEMENT_LIST],##);} (stmt_list)? ;

Try this for EMPTY_LIST functionality, but it probably needs some more
thinking about if you get ambiguity warnings:

stmt_list : stmt {##=#([STATEMENT_LIST],##);} 
           (stmt_list
		| /*empty*/ {##=#(null,##,EMPTY_LIST);}
		) 

;

Note that #(null,a,b) builds a list A B with no root (null is the root--get
it?)

Monty

-----Original Message-----
From: Arnar Birgisson [mailto:arnarb at oddi.is] 
Sent: Thursday, October 09, 2003 4:44 AM
To: antlr-interest at yahoogroups.com
Subject: RE: [antlr-interest] Tree transformation

Hello..

Thanks, but what I need is a bit more. I need a more general method of
converting a list like structure like

PARENT
 |
C1 - C2 - C3 - ... - CN

to a right-balanced tree like this:

FUNC
 |
C1 - FUNC
      |
     C2 - FUNC
           |
          C3 - FUNC
                |
                ... 
                   C(N-1) - FUNC
                             |
                             CN - EMPTY_LIST

What I am implementing is basically the conversion from
"[expr1,expr2,...,exprN]" to a lisp-like list, which is equivalent to
"expr1 : (expr2 : (expr3 : ... (exprN : []) ... ))", where ":" is like
the "cons" operator in lisp, and "[]" is a lexical constant representing
the nil list.

I thought of writing a function that takes three ASTs, one like this
#(FUNC), one #(EMPTY_LIST) and the third one like #(LIST node1 node2 ...
nodeN), and returns an AST like this: #(FUNC node1 #(FUNC node2 #(...
#(FUNC nodeN EMPTY_LIST) ...) ) ). I will try this and let you know.

Hope that explains it..

Arnar
                                        

> -----Original Message-----
> From: mzukowski at yci.com [mailto:mzukowski at yci.com] 
> Sent: 8. október 2003 22:19
> To: antlr-interest at yahoogroups.com
> Subject: RE: [antlr-interest] Tree transformation
> 
> 
> Ack, the formatting got blarked.  Should be this:
> 
> list_expr! : #(l:LIST s:stmt_list) {##=#(#[LPAREN,")"], 
> #[NAME,"func"], s);}
> 
> stmt_list : #(STATEMENT_LIST (stmt)*)
> 
> -----Original Message-----
> From: mzukowski at yci.com [mailto:mzukowski at yci.com] 
> Sent: Wednesday, October 08, 2003 3:11 PM
> To: antlr-interest at yahoogroups.com
> Subject: RE: [antlr-interest] Tree transformation
> 
> Your description is a bit unclear, but to get this:
> 
> LPAREN
>  |
> NAME("func") - STATEMENT_LIST 
>                 |
>                ID(a) - ID(b) - ID(c)
> 
> Do this:
> 
> list_expr! : #(l:LIST s:stmt_list) {##=#(#[LPAREN,")"], 
> #[NAME,"func"], s);}
> stmt_list : #(STATEMENT_LIST (stmt)*)
> 
> Monty
> 
> -----Original Message-----
> From: Arnar Birgisson [mailto:arnarb at oddi.is] 
> Sent: Wednesday, October 08, 2003 12:03 PM
> To: antlr-interest at yahoogroups.com
> Subject: [antlr-interest] Tree transformation
> 
> Hello..
> 
> I have a programming construct "[a,b,c]" which defines a list (in the
> lisp sense) of the results of expressions a, b and c. The 
> parser returns
> this tree: #([LIST,"["], #(STATEMENT_LIST, #a, #b, #c)). I.e.
> 
> LIST
>  |
> STATEMENT_LIST
>  |
>  ID - ID - ID
> 
> My languages sematnics define "[a,b,c]" to be eqivalent
> "func(;a,func(;b,c))", and moreover, the user program might define
> "func" to be whatever function the user wants it to be.
> 
> (As a side note: the function call syntax in the language is
> func(x1,..,xN;y1,..,yM) where x1,..,xN are copy-in copy-out 
> parameters,
> and y1,...,yM are pass-by-value. Also, there is no distinction between
> statements and expressions.)
> 
> I have one tree parser that takes the parser output and simplifies the
> tree, before that is passed to another tree-parser, the code 
> generator.
> 
> The simplifying treeparser (the transformer) does things like convert
> "expr1 + expr1" to "+(;expr1,expr2)", and I furthermore want it to
> convert the tree for "[a,b,c]" to the tree "func(;a,func(;b,c))" would
> have generated.
> 
> In a nutshell, I need to convert trees of the form depicted above, to
> this:
> 
> LPAREN
>  |
> NAME("func") - STATEMENT_LIST - STATEMENT_list
>                                  |
>                                  ID(a) - ID(b) - ID(c)
> 
> How would you do in a tree-parser rule? The rules I have to match the
> input tree are:
> 
> list_expr : #(LIST stmt_list)
> stmt_list : #(STATEMENT_LIST (stmt)*)
> 
> Arnar
> 
> ps. for the sake of completeness, the actual language doesn't 
> use "func"
> as the function name, but rather ":". Operatrs in the language are
> simply functions as the equivalence "a+b"="+(;a,b)" implied.
> 
> 
>  
> 
> Your use of Yahoo! Groups is subject to 
> http://docs.yahoo.com/info/terms/ 
> 
> 
>  
> 
> Your use of Yahoo! 
> Groups is subject to http://docs.yahoo.com/info/terms/ 
> 
> 
>  
> 
> Your use of Yahoo! Groups is subject to 
> http://docs.yahoo.com/info/terms/ 
> 
> 


 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 


 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/