another newbie question...

Jul 1, 2009 at 10:38 AM
Edited Jul 1, 2009 at 11:00 AM

There seems to be a lot of us...  Probably because Irony makes it look feasible to use grammar parsing even for us that don't REALLY understand what we are doing... :-)

I am trying to build a tool that is supposed to help me translate a rather big database structure from MSSQL to MySQL. I have started to extend and rebuild the SQL sample grammar from Irony, and have actually managed to create a grammar that seems to properly parse my rather large SQL file that i get when doing "Create database scripts" from SQL-server. (Luckily it doesn't use any really hairy SQL constructs)

So I have a parseTree.

What now?

I understand that I in some way should build an AST-tree with classes that is able to emit corresponding MySQL code, but I don't just get how I am supposed to do this... 

I know that i can add classtypes for corresponding AST objects on the nonTerminals, or use the creator interface, and end up with a parsetree with attached AST objects, but then what? How do I use this? I have looked at the Scheme implementation, but that didn't really help...

My plan is to create one AST-class for each command type that have different syntax in MySQL,one general that just emits what it was fed for those that have the same syntax, and one that emits the source commented out for those that doesn't translate at all..

Any really super simple example would help a lot, just to get the idea.


Another thing that puzzles me is that the parse tree gets simplified in the process, and how that works if I were to attach AST objects to the nonterminals that doesn't show.




   selectStmt -> select selRestrOpt selTopOpt selList intoClauseOpt fromClauseOpt whereClauseOpt groupClauseOpt orderClauseOpt unionClause 


   selList -> columnItemList 

   selList -> * 



If I parse a statement that starts "SELECT * FROM" it doesnt't give me a parsenode for "selList ", just a Symbol node in its place for the "*" , so if i want to handle all kinds of selList by an AST object attached to the selList NonTerminal, how do I do?



Jul 1, 2009 at 6:31 PM


For your scenario, you probably don't need to create AST tree, but instead directly traverse the tree and spit out SQL as you go. Your task is very similar to the one of SearchGrammar - to convert query from one format to another. So have a look at SearchGrammar sample, and do something simililar. You'll probably need to do the following:

1. From the parse tree, select all the nodes containing some top-level statements like "Create Table", Create Index, or whatever you have there, and put all these nodes into a plain list

2. Iterate the list, and write out SQL for each statement type using some specialized methods in the same class or module, without creating any AST node subclasses. These methods should know what to expect in child nodes, how to get details of the result SQL from child parse tree, and form the output SQL accordingly

I think this would work.


Jul 1, 2009 at 11:56 PM


Thanks for your answer. I will try that strategy.



Jul 4, 2009 at 5:00 PM


Another problem popped up when I added something seemingly quite separate from what the error mentions (Tried to add handling of exec statement.): 


Shift-reduce conflict. State SN728, lookaheads: joinKindOpt applyJoinOp
Shift-reduce conflict. State SN748, lookaheads: )

Parser builder detected parsing conflicts that can be resolved by restructuring.
Add WrapTail() hint method in place of '.' to the following productions in original grammar: 
joined_table -> table_source ·joinKindOpt join table_source on logExpression 
joined_table -> table_source ·applyJoinOp apply table_source 
parSelectStmt -> ( selectStmt ·) 
compExpression -> expression notOpt in ( funArgs ·) 

The mentioned states:


State SN728 (Inadequate)
  Shift items:
    joined_table -> table_source ·joinKindOpt join table_source on logExpression 
    joinKindOpt -> ·right outer 
    joinKindOpt -> ·left outer 
    joinKindOpt -> ·full 
    joinKindOpt -> ·inner 
    joined_table -> table_source ·applyJoinOp apply table_source 
    applyJoinOp -> ·cross 
    applyJoinOp -> ·outer 
  Reduce items:
    joined_table -> table_source applyJoinOp apply table_source · [, ) on applyJoinOp joinKindOpt where group order union]
  Shifts: joinKindOpt->SN670, applyJoinOp->SN675, 
  Jump to non-canonical state  SN756 on lookaheads: right left full inner cross outer
State SN748 (Inadequate) Shift items: parSelectStmt -> ( selectStmt ·) Reduce items: funArgs -> selectStmt · [)] Shifts: )->SN595,

(Looking at the states, there are a lot of them that is marked (Inadequate), it that a problem generally?)

When I follow the recommentation, inserting WrapTail() at the pointed out positions, it seems to get into a loop when loading the grammar, it just hangs...

Could you maybe explain how to interpret the different hints for someone that isn't that fluent in grammar parsing :-) ?

What does WrapTail() actually DO, for example? When the parser hits the WrapTail, what does it do, as opposed to what it would have done otherwise?





Jul 4, 2009 at 8:44 PM

Some additional info:

-I think i managed to get rid of the ")" related statement, I think I had mare than one thing defined as "(" + exprList+ ")", when I managed to remove those the error stopped showing.

- The other problem I have made some progress with, but now it looks like this:

Shift-reduce conflict. State SN685, lookaheads: joinKindOpt joinConditionOpt

Parser builder detected parsing conflicts that can be resolved by restructuring.
Add WrapTail() hint method in place of '.' to the following productions in original grammar: 
joined_table -> table_source ·joinKindOpt table_source joinConditionOpt 
joined_table -> table_source joinKindOpt table_source ·joinConditionOpt 
I suspect this is because there is a recursive definition here, one of the alternatives for a "table_source" is a "joined_table"
   table_sourceList -> table_source 
   table_sourceList -> table_sourceList , table_source 
   table_source -> Id aliasOpt 
   table_source -> funCall aliasOpt 
   table_source -> parSelectStmt aliasOpt 
   table_source -> joined_table 
   joined_table -> ( joined_table ) 
   joined_table -> table_source joinKindOpt table_source joinConditionOpt 
   joinKindOpt -> right outer join 
   joinKindOpt -> left outer join 
   joinKindOpt -> full join 
   joinKindOpt -> inner join 
   joinKindOpt -> cross join 
   joinKindOpt -> cross apply 
   joinKindOpt -> outer apply 
joinConditionOpt  (Nullable) 
   joinConditionOpt -> 
   joinConditionOpt -> on logExpression 
How to solve this kind of problem?
Jul 4, 2009 at 9:00 PM
Edited Jul 4, 2009 at 9:00 PM

You're in non-canonical parsing algorithm, don't get into this unless you have some understanding of parsing methods. All these obscure messages you see are result of this.

NLALR method is an extension of classical LALR, but it is for use by more advanced folks; plus, it does not quite work very well yet.

So, first of all, set in grammar constructor:

this.ParseMethod = ParseMethod.Lalr;

or remove similar statement that sets method to NLalr. Then see what conflicts you have. See if you can eliminate them by explicitly assigning preferred action using "PrefereShiftHere()"


Jul 5, 2009 at 2:46 AM
Edited Jul 5, 2009 at 2:47 AM

I looked at your grammar and it seems to me that your problem is ambiguity of the grammar in terms of "associativity of join operation".

If you have expression like:

tA join tB join tC

- how to interpret it?

is it 

 (tA join tB) join tC


 tA join (tB join tC)

I think the first version should be preferred. Parser cannot decide by himself what is correct interpretation, so it identifies this as a conflict. You can give explict instruction, hint, to help parser decide in this situation. In technical terms, you must tell parser to prefer "reduce" operation in this situation; you do this by adding "ReduceThis()" call into the grammar rule for the join table:

joined_table.Rule = table_source +  joinKindOpt + table_source + joinConditionOpt + ReduceThis();

Try this, see if it eliminates the conflict message; then try parsing some samples involving multiple joins


PS: and previous message still holds - switch to LALR parsing method.

Jul 5, 2009 at 12:03 PM


Thank you for spending time on this, I should probably read up on parsing instead of asking a lot of questions... :-)

Yes, switching to LALR showed a lot of other errsors that probably were causing all kinds of troubles, and I managed to get rid of them by adding "PrefereShiftHere()", and that actually cleared up the error for the join as well, but i haven't tested it against any really hairy joins yet..

I am not sure you are right about how i want the joins to evaluate...

If in MS SQL the rules should be (as found on the net):

1) JOINS are (effectively) executed left to right, following the usual
rules for nesting parentheses.  There is no precedence for INNER and
OUTER joins.
2) The ON clause associates with the nearest JOIN clause.

But the output I am currently getting, with your recommended ReduceHere() hints seems to work out according to that, so...

SELECT * FROM tA cross join tB cross Join tC

INNER JOIN tB ON tA.AffiliationId = tB.AffiliationId 
  INNER JOIN tE ON tD.MediaId = tE.MediaId 
ON tB.MediaId = tD.MediaId


    SELECT   *
    FROM  ( ( `tA`CROSS JOIN `tB` ) CROSS JOIN `tC` ) ;

    SELECT   *
              INNER JOIN `tB` ON ( `tA`.`AffiliationId`  = `tB`.`AffiliationId` )
            RIGHT OUTER JOIN 
              ( `tC`CROSS JOIN `tD` ) 
              INNER JOIN `tE` ON ( `tD`.`MediaId`  = `tE`.`MediaId` )
            ON ( `tB`.`MediaId`  = `tD`.`MediaId` )


The reason i was using NLALR was that it seemed to work, as opposed to LALR, wich i suppose it did by hiding my basic problems until they got worse enough, and also that I from your blog entry of Apr 27 mistakenly deduced that ther was something wrong with the LALR implementation and that NLALR was the corrected version.

Re-reading it now, with a little bit more knowledge of the subject, I see my mistake. ( I will try to understand your "NonCanonTestGrammars" samples before i use it... :-) )

Thanks for your help. If I ever get this translator done I will put it up on codeplex.






Jul 5, 2009 at 7:55 PM

So, just to confirm, the parser seems to be working correctly, right?

In the last mult-join statement - it is interpreted correctly, according to MS SQL join rules you cited, as far as I can see...


Jul 6, 2009 at 1:10 AM


Yes, it works as it shold.

Thanks again.