problem with semantic actions

[Steve Greenburg]

Hi,

I am implementing a parser which removes unnecessary parentheses from infix 
expressions, however I came across a very strange bug which I don't 
understand at all. My system is Fedora Core 6 with Bison 2.3 with latest 
kernel and updates as of 04/07. However I tested the same grammar file on a 
cygwin environment and got similar erroneous behavior (also Bison version 
2.3), leading me to believe the problem is either with bison or how I am 
using it. Sorry in advance if this is not a problem with bison itself, and 
also sorry for the size of the attached grammar file, but since I don't 
understand this bug I can't really make a smaller grammar file which 
reproduces it. Here is the basic grammar I had when I found the bug:

expr -> term moreterms
moreterms -> '+' moreterms | e.
term -> factor morefactors
morefactors -> '*' morefactors | e.
factor -> '(' expr ')'

To compile and run the file I enter these commands:

bison unparen.y; cc -o unparen unparen.tab.cc; ./unparen < expr

The file expr contains the following:

((((((((((1)+2)*3)+4)*5)+6)*7)+8)*9)+10)

While the semantic actions seem to successfully remove the unwanted parens, 
it replaces the '9' character with a '!' character:

((((1+2)*3+4)*5+6)*7+8)*!+10

On the cygwin box it replaced the '5' with two '!' characters. After 
compiling with debugging enabled and running it through gdb, I found that 
when the semantic action for "term" is being executed the expression is 
correct, e.g. $$.str is "((((1+2)*3+4)*5+6)*7+8)*9". Yet when I check the 
same value as $1.str from the "expr" semantic action it prints out as 
"((((1+2)*3+4)*5+6)*7+8)*!".  Changing some of the * signs to + signs and 
vice versa sometimes eliminates the effect. Also I couldn't reproduce the 
bug with a shorter input, and changing various things (like the sizes of 
allocated memory in each semantic action) seems to have no effect. One other 
thing - gdb says that this line from the "moreterms" semantic action is 
responsible for changing the '9' to a '!' (based on repeatedly printing out 
the area of memory in question), but I don't see how that can be since it's 
a different semantic action from term.

$$.str = (char *)malloc(1);*$$.str = '\0';

That is all the information I have, any insight you could offer would be 
appreciated, and thanks in advance.

-Steve

_________________________________________________________________
PC Magazine’s 2007 editors’ choice for best Web mail—award-winning Windows 
Live Hotmail. 
http://imagine-windowslive.com/hotmail/?locale=en-us&ocid=TXT_TAGHM_migration_HM_mini_pcmag_0507

unparen.y
Description: Binary data