[antlr-interest] Tree transformation
Arnar Birgisson
arnarb at oddi.is
Thu Oct 9 11:42:39 PDT 2003
Yeah.. tried that also, which seems to end up in an infinite loop :o(
Anyways.. I have a working c++ function that takes the factory and the
list as parameters and does the thing for me. It's equivalent in antlr
construction syntax would be something like this:
list_expression! : #(LIST slist:stmt_list)
{
antlr::RefAST current = slist->getFirstChild();
if (current == antlr::nullAST) {
## = #([EMPTY_LIST,"[]"]);
} else {
antlr::RefAST subtree = #([STMT_LIST,"function arguments"]);
antlr::RefAST root = #([LPAREN,"("], [ID,":"], subtree);
while (current != antlr::nullAST) {
subtree->addChild(current);
antlr::RefAST temp1 = current->getNextSibling();
current->setNextSibling(antlr::nullAST);
current = temp1;
if (current != antlr::nullAST) {
antlr::RefAST newSubtree = #([STMT_LIST,"function arguments"]);
antlr::RefAST temp2 = #([LPAREN,"("], [ID,":"], newSubtree);
subtree->addChild(temp2);
subtree = newSubtree;
}
}
subtree->addChild( #([EMPTY_LIST,"[]"]) );
## = root;
}
};
I tried this out also, and it works pretty well.
Arnar
> -----Original Message-----
> From: mzukowski at yci.com [mailto:mzukowski at yci.com]
> Sent: 9. október 2003 18:19
> To: antlr-interest at yahoogroups.com
> Subject: RE: [antlr-interest] Tree transformation
>
>
> Huh, then do this
>
> parent_expr! : #(l:PARENT s:stmt_list) {##=s;};
>
> Monty
>
> -----Original Message-----
> From: Arnar Birgisson [mailto:arnarb at oddi.is]
> Sent: Thursday, October 09, 2003 11:10 AM
> To: antlr-interest at yahoogroups.com
> Subject: RE: [antlr-interest] Tree transformation
>
> Hello..
>
> I get this:
>
> g:\j2sdk1.4.2\bin\java -cp g:\jars\antlr.jar antlr.Tool
> FjolnirTransformer.g
> ANTLR Parser Generator Version 2.7.3-20030430 1989-2003 jGuru.com
> FjolnirTransformer.g:115:11: Suffixing a root node with '!' is not
> implemented
> Exiting due to errors.
>
> I think I'm running the latest and greatest (2.7.3 from Ric, dated
> 2003-09-11).
>
> Arnar
>
>
>
> > -----Original Message-----
> > From: mzukowski at yci.com [mailto:mzukowski at yci.com]
> > Sent: 9. október 2003 15:51
> > To: antlr-interest at yahoogroups.com
> > Subject: RE: [antlr-interest] Tree transformation
> >
> >
> > 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/
> >
> >
>
>
>
>
> 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/
More information about the antlr-interest
mailing list