[antlr-interest] Tree-Parser Grammer Question

Tue Nov 12 15:56:43 PST 2002

Monty,

Thanks for the idea of using the imaginary node, by doing that I was able to
shove the column construct and the alias down another level. This of course
made it easy to write a tree grammar that could pull out the alias token (I
also overrode the token type from IDENT to ALIAS) if it existed due to it
being grouped with the column expr under a imaginary root.

This just proves to me the point that sometimes you have to amend the AST
produced a little to make the tree grammar easier to write.

-Richard

-----Original Message-----
From: mzukowski at yci.com [mailto:mzukowski at yci.com] 
Sent: Tuesday, November 12, 2002 1:29 PM
To: antlr-interest at yahoogroups.com
Subject: RE: [antlr-interest] Tree-Parser Grammer Question

The GCC C grammar has plenty of examples of imaginary nodes
http://www.codetransform.com/gcc.html.  I imagine the Java grammar does too.

> 1) if exists any list of such TIPs as you describe above ?
Not that I know of.  I'm not sure if there was sucha  topic in the faq or
not.

> 2) if exists any example grammars written by you for public ?
http://www.codetransform.com/gcc.html is a complete lexer/parser/tree
grammar/tree emitter.

> 3) May be you can send me/us some grammars that are not secret? 
> Especially interesting
>    -- how you put symbols into symbol table.
See the GCC grammar.

>    -- what C/c++ classes of symbol table you use
It is in Java, not C++, but you should get the idea.

>    -- tree parser that *and* its C++ actions.
Unfortunately the tree parser in the above distribution is empty.  A few
months ago I posted a simple transformation using it to swap the if/else
statements.  When Aspect C is done it will be an excellent source of example
transformations.

Monty

-----Original Message-----
From: Ney, Richard [mailto:richard.ney at aspect.com]
Sent: Tuesday, November 12, 2002 9:36 AM
To: 'antlr-interest at yahoogroups.com'
Subject: RE: [antlr-interest] Tree-Parser Grammer Question

Technically it isn't a must to have the final column name as the root, to me
that was just the easiest way to ensure it was in the same location in the
tree each time. Then when I traverse the tree with the tree grammar I can
then do lookups against stored meta-data and translate the underlying
information about that column into a new column statement in a new select
statement. Basically translating one SQL select into another. 

Now your NEmptyExpression rule looks like an option since the main place
where my tree grammar goes ambigious is due to the fact that a field name is
also an IDENT. If that alias is missing I can place the empty expression, as
I mentioned add an alias parameter to columns that don't have an alias. I
assume you are applying the empty in the initial parser so you get a TOKEN
to specify in the tree grammar. Do you know if any of the examples show the
implementation of a forced node or empty expression?

-Richard

-----Original Message-----
From: mzukowski at yci.com [mailto:mzukowski at yci.com] 
Sent: Tuesday, November 12, 2002 9:13 AM
To: antlr-interest at yahoogroups.com
Subject: RE: [antlr-interest] Tree-Parser Grammer Question

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/ 