[antlr-interest] Tree-Parser Grammer Question

mzukowski at yci.com mzukowski at yci.com
Tue Nov 12 14:12:36 PST 2002


It's really hard to give advice without a specific example.  If you can
parse it you should be able to make an AST of some sort.  Some optional
constructs are able to be handled as I described earlier in this thread, by
making a fixed structure that holds them all and then putting in empty
placeholders as appropriate.  

Representing a translation strategy in a neutral form has been the goal of
many projects outside of antlr, and it is a hard problem to solve.  I think
you'll get further by doing complete translations for two different sources
and targets and then be able to step back and factor the code for the
general cases.  Again if you had specific examples I'd have more to think
about.

Monty

-----Original Message-----
From: Sriram Durbha [mailto:cintyram at yahoo.com]
Sent: Tuesday, November 12, 2002 1:30 PM
To: antlr-interest at yahoogroups.com
Subject: RE: [antlr-interest] Tree-Parser Grammer Question


hi monty,
 in one of the applicaitons that i am writing [a translator] ,
part of the translation can be syntax directed; [ that is ..  target
code canbe generated directly from the parse action ;]

how ever important ones need ast;

now i am in a difficult position;
1.] the source language does not have a special delimiter ;
2. most of the constructs are optional ;
now i am not able to parse the if else construct;
but would like to know if there are any precautions i have to take
specially so that i can build a good and suitable tree ..

3.
 also i am trying to represent the translation strategy in a neutral
form , so that i can apply representations in that form to different
sets of sources and targets; Has any work been done in this area?

cheers
ram




--- mzukowski at yci.com wrote:
> Typically a root is chosen for its structure, not its content.  For
> instance
> a simplistic variable declaration in C would look like #(NDeclarator
> type ID
> (expr)?);  The NDeclarator is an imaginary type, which you might
> consider
> using.  Again I ask why is it important to have the name be the root?
> Typically symbols are stored in a symbol table so you can look them
> up by
> scope and and name and that will point you to the right tree.  
> 
> What do you envision doing with the tree that makes it important to
> have the
> name first?
> 
> Note that your structure for the tree with IDENT as an optional root
> muddles
> things up.  You don't know from the start which of the tree
> alternatives you
> are looking at.  This will slow down your tree traversal as well. 
> Some
> people argue that tree grammars should avoid optional closures
> totally.
> Take for instance a for loop.  In C any of the three expressions are
> optional, but for my tree I don't want to decide based on content, so
> I
> added an imaginary NEmptyExpression alternative to my expr rule.  So
> now a
> missing expr in a for loop is forced in as an NEmptyExpression. 
> Imagine how
> to handle the tree grammar if I left those three exprs optional. 
> It's not
> pretty.  My simple tree grammar for "for" is this:
> 
>                #( "for"
>                 expr expr expr
>                 statement
>                 )
> 
> OK, let's get ready for round two!
> 
> Monty
> 
> -----Original Message-----
> From: Ney, Richard [mailto:richard.ney at aspect.com]
> Sent: Tuesday, November 12, 2002 8:51 AM
> To: 'antlr-interest at yahoogroups.com'
> Subject: RE: [antlr-interest] Tree-Parser Grammer Question
> 
> 
> The rational for this was to have the final output name of each
> column in
> the select statement to always be the root. Now based on SQL92 that
> can be
> the column name, an alias, or the group expression. Now I was
> starting to
> look at making the initial parser always add the alias in to the
> tree.
> Anyone have an example of a conditional rule in the parser that can
> add
> stuff into the tree conditionally?
> 
> -Richard
> 
> -----Original Message-----
> From: mzukowski at yci.com [mailto:mzukowski at yci.com] 
> Sent: Tuesday, November 12, 2002 8:26 AM
> To: antlr-interest at yahoogroups.com
> Subject: RE: [antlr-interest] Tree-Parser Grammer Question
> 
> 
> It is kind of weird to have optional matches like (IDENT^)? promoted
> to the
> root.  What is your rationale for this?  Your tree rule would look
> like
> 
> selectColumn: #(IDENT groupExpression)
> 			| groupExpression
> 	;
> 
> Monty
> 
> -----Original Message-----
> From: Ney, Richard [mailto:richard.ney at aspect.com]
> Sent: Monday, November 11, 2002 11:26 PM
> To: 'antlr-interest at yahoogroups.com'
> Subject: [antlr-interest] Tree-Parser Grammer Question
> 
> 
> I have battled this issue for two days now so I'm at a loss to how to
> solve
> this problem. I created a initial parser for a basic SQL Select. One
> of my
> key rules in the initial parser looks like this: groupExpression 
>         : ("avg"^|"max"^|"min"^|"sum"^) OPEN_PAREN!
> (additiveExpression |
> (("all" | "distinct") field_name)) CLOSE_PAREN! (IDENT^)
>         | ("count"^ OPEN_PAREN! (("all" | "distinct")? field_name |
> STAR)
> CLOSE_PAREN! (IDENT^)?) 
>         | additiveExpression (IDENT^)? 
>         ; 
> The result of this rule is that it builds the tree with the final
> name of
> the column always being to top-most root. I.E. Select test, count(*),
> count(*) test from foo; 
> Results in a tree that looks like 
> select 
>         test 
>         count 
>                 * 
>         test 
>                 count 
>                         * 
> from 
>         foo 
> Now in my tree parser I have a two rules that look like this: 
> selectColumn 
>         : fieldName (groupExpression)? 
>         ; 
>         
> groupExpression 
>         : #("avg" mathExpression) 
>         { 
>         } 
>         | #("sum" mathExpression) 
>         { 
>         } 
>         | #("count" ("all" | "distinct")? (fieldName| STAR)) 
>         { 
>         } 
>         | #("max" mathExpression) 
>         { 
>         } 
>         | #("min" mathExpression) 
>         { 
>         } 
>         ; 
> These rules handle the 1st and 3rd cases in the select statement but
> not the
> 2nd where the count(*) doesn't have an alias. Does anyone have an
> idea how
> to write something like selectColumn 
>         : (fieldName)? (groupExpression)? 
>         ; 
> that is a little less ambiguous? 
> -Richard 
>
----------------------------------------------------------------------------
> ------------------------ 
> Richard Ney     Aspect Communications 
> Principal Software Engineer 
> http://www.aspect.com                           Main:  408.325.2200 
> mailto:richard.ney at aspect.com                   SJ Office:
> 408.325.2464 
>         Home Office: 916.797.9602 
>
----------------------------------------------------------------------------
> ------------------------ 
> The Three Laws of Infernal Dynamics:
> 1. An object in motion will always be headed in the wrong direction.
> 2. An
> object at rest will always be in the wrong place. 3. The energy
> required to
> change either of these states will always be more than you wish to
> expend,
> but never so much as to make the task appear prospectively
> impossible.
> 
> 
> Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service. 
> 
>  
> 
> 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/ 
> 
> 


__________________________________________________
Do you Yahoo!?
U2 on LAUNCH - Exclusive greatest hits videos
http://launch.yahoo.com/u2

 

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