SableCC 3.6 - fixes a subtle inlining bug

[Etienne Gagnon]

Hi folks,

While working on SableCC 4, I discovered two bugs in SableCC 3: one bug where an ambiguity was hidden by the inlining engine, and another one in the setXXX method of list elements in the generated AST.

I fixed the two bugs and released SableCC 3.6. Here's the download link:

• http://downloads.sourceforge.net/sablecc/sablecc-3.6.zip
  

Have fun!

Etienne

[Pomeroy, Roger C]

I have a question about this change.  I had a rather complicated syntax I have been using for some time (apparently successfully).  I tried compiling under 3.6 and found that I got a reduce/reduce conflict that had not appeared there before.  Upon looking at my syntax I found I had a (nearly) duplicate line – the {scoped} alternative should not have been there!

   array_unpack_member {->variable_name}  =

        {name}      [object]:local_name blank?     {->New variable_name.scoped([object.name_component],Null)} |

        {scoped}    [object]:local_name blank?     {->New variable_name.scoped([object.name_component],Null)} |

        {list}      [object]:array_unpack_list     {->New variable_name.list([object.variable_name])}

     ;

 

( I removed that, and now I am getting even more reduce/reduce errors in other places where I cannot see any reason for the conflict. )

 

My question is what does this say about the state of the parser generated under previous version ... I have been using it for over 2 years with no apparent problems in its behavior.  I know for example, that I have test cases that have exercised the syntax above, and they are processed correctly.  Now, after seeing all the other errors that are apparently being reported, I’m worried about the validity of the rest of the tree.    On the one hand, I know that for whatever reason the old parser is correctly handling the statement there, but can I be assured of that for other errors that are reported?    Is there any way to predict (other than just by trial and error) what sort of errors were hidden by this bug?

 

Thanks!

 

 

Roger Pomeroy
Associate Technical Fellow
Aerodynamics/Geometry
Phone  425-237-5293 New

--
-- You received this message because you are subscribed to the SableCC group. To post to this group, send email to sab...@googlegroups.com. To unsubscribe from this group, send email to sablecc+u...@googlegroups.com. For more options, visit this group at https://groups.google.com/d/forum/sablecc?hl=en
 
 

[Etienne Gagnon]

Hi Roger,

Yep, SableCC was hiding ambiguities/conflicts in some grammars. [Note that pure LALR(1) grammars were not affected by the bug.]

The net effect, on generated parsers, is that they were:

1. able to parse some obviously ambiguous grammars (i.e. identical alternatives), yielding one of many possible ASTs;
2. rejecting some valid input (due to missing alternatives in the parser***).

So, this means for you, that your existing parsers never accepted an invalid program. You might, only, have annoyed a user by rejecting a valid program.

Now, the fix introduced in SableCC 3.6, in many cases, will happen transparently. In other words, invalidly rejected programs will be accepted. But, there are two cases where SableCC 3.6 requires fixes to the grammar:

1. when the grammar is ambiguous due to duplicate alternatives;
2. when the missing alternatives cause LALR(1) conflicts.
   

You have hit these two cases with your complex grammar. As you have noticed, the ambiguity problem is easy to solve; you only have to remove the spurious duplicate alternative. The conflicts, on the other hand, are a pain as usual.

I am sorry for the hassle. Let me know if I can help you with the conflicts.

Etienne

*** SableCC 3.x implements inlining by cloning parts of the AST. The "list element setter" bug did cause SableCC to lose some inlined alternatives in specific grammar configurations. So, the generated parser was rejecting programs using these missing alternatives!



On 2012-08-22 10:22, Pomeroy, Roger C wrote:

I have a question about this change.  I had a rather complicated syntax I have been using for some time (apparently successfully).  I tried compiling under 3.6 and found that I got a reduce/reduce conflict that had not appeared there before.  [...]

[Pomeroy, Roger C]

Thanks, Etienne ...

 

As usual, after a lot of head scratching, SableCC was right ... I did  have 3 other subtle ambiguities that were being hidden by this bug.  After fixing those 3, I found two very beneficial side effects!   The first one is that the time it took to generate the parser dropped dramatically (cut it by about 2/3!).  More importantly, I had been running into the problem of the “parse” routine getting too large (>32k) for Java to compile, so I was not able to make many changes to my syntax for fear of being unable to compile the result.  But after fixing these, I appear to be well under that limit ... I have not hit that problem again!

 

Thanks much for this fix, and for the tool ... it is absolutely indispensible!

 

 

Roger Pomeroy

--