プログラミングと絵と音楽

コンピューター科学を専攻し、絵と音楽を趣味とするエンジニアのブログです。

何故か確率的にしか動かないC言語の構文解析プログラム

Scala構文木出力のためのパーサーコンビネーターを書きました。多言語対応にするつもりで、現在はC言語のそれが大体動くようにはなったのですが、
何故か構文解析プログラムで勝手にトークン列が変更されてしまうという原因不明のバグにはまってしまったので一応記録しておきたいと思います。
URL はこちら、Parser.c の関数 parse はトークン列を構文解析して構文木を作るプログラムです。
yacc/Parser.c at master · tfull/yacc · GitHub
例えば入力を

1 + 2

と与えると、

1 + 2
Integer(1) [1:1 - 1:1]
Plus [1:3 - 1:3]
Integer(2) [1:5 - 1:5]
[ 0] [0,2,0,]
[ 0] state 0 and tid 0 (& 0x7fefa8c03a20)
[ 0] shift
[ 1] [0,2,0,]
[ 1] state 4 and tid 2 (& 0x7fefa8c03a20)
[ 1] reduce
[ 1] end for r_n = 8, stack.size = 1[0,2,0,]
[ 1] --[0,2,7,]
[ 1] before push
[ 1] [0,2,7,]
[ 1] state 5 and tid 2 (& 0x7fefa8c03a20)
[ 1] reduce
[ 1] end for r_n = 7, stack.size = 1[0,2,7,]
[ 1] --[0,2,7,]
[ 1] before push
[ 1] [0,2,7,]
[ 1] state 2 and tid 2 (& 0x7fefa8c03a20)
[ 1] reduce
[ 1] end for r_n = 3, stack.size = 1[0,2,7,]
[ 1] --[0,2,7,]
[ 1] before push
[ 1] [0,2,7,]
[ 1] state 3 and tid 2 (& 0x7fefa8c03a20)
[ 1] shift
[ 2] [0,2,7,]
[ 2] state 8 and tid 7 (& 0x7fefa8c03a20)
[ 2] shift
[ 3] [0,2,7,]
[ 3] state 6 and tid 8 (& 0x7fefa8c03a20)
parse error: token(1:5 - 1:5)

というようにパースエラーが出力されます。ここで、 [0,2,0] というのが入力されたトークンの種類で、例えば INT, PLUS, STAR というようにトークンの情報が入っています。 0 は INT を、 2 は PLUS を表しています。
なぜか、途中でトークン列が [0,2,0] から [0,2,7] に変わっているのがわかります。 7 は MINUS を表します。トークンが変わる間、すなわち print("end for") と print("--") の間には 1 行の関数実行があるだけです。しかも、トークン列は渡してすらいません。
このバグの恐ろしさは、たまに成功することにあります。同じ入力を 10 回ほど渡し続けると、たまに

1 + 2
Integer(1) [1:1 - 1:1]
Plus [1:3 - 1:3]
Integer(2) [1:5 - 1:5]
[ 0] [0,2,0,]
[ 0] state 0 and tid 0 (& 0x7ffcead00040)
[ 0] shift
[ 1] [0,2,0,]
[ 1] state 4 and tid 2 (& 0x7ffcead00040)
[ 1] reduce
[ 1] end for r_n = 8, stack.size = 1[0,2,0,]
[ 1] --[0,2,0,]
[ 1] before push
[ 1] [0,2,0,]
[ 1] state 5 and tid 2 (& 0x7ffcead00040)
[ 1] reduce
[ 1] end for r_n = 7, stack.size = 1[0,2,0,]
[ 1] --[0,2,0,]
[ 1] before push
[ 1] [0,2,0,]
[ 1] state 2 and tid 2 (& 0x7ffcead00040)
[ 1] reduce
[ 1] end for r_n = 3, stack.size = 1[0,2,0,]
[ 1] --[0,2,0,]
[ 1] before push
[ 1] [0,2,0,]
[ 1] state 3 and tid 2 (& 0x7ffcead00040)
[ 1] shift
[ 2] [0,2,0,]
[ 2] state 8 and tid 0 (& 0x7ffcead00040)
[ 2] shift
[ 3] [0,2,0,]
[ 3] state 4 and tid 8 (& 0x7ffcead00040)
[ 3] reduce
[ 3] end for r_n = 8, stack.size = 3[0,2,0,]
[ 3] --[0,2,0,]
[ 3] before push
[ 3] [0,2,0,]
[ 3] state 5 and tid 8 (& 0x7ffcead00040)
[ 3] reduce
[ 3] end for r_n = 7, stack.size = 3[0,2,0,]
[ 3] --[0,2,0,]
[ 3] before push
[ 3] [0,2,0,]
[ 3] state 24 and tid 8 (& 0x7ffcead00040)
[ 3] reduce
[ 3] end for r_n = 1, stack.size = 1[0,2,0,]
[ 3] --[0,2,0,]
[ 3] before push
[ 3] [0,2,0,]
[ 3] state 3 and tid 8 (& 0x7ffcead00040)
Add(Int(1),Int(2))

と、正常に構文木を出力しています。
さらにおかしなことに、確率的に動くという状態が、 clang でも gcc でも再現可能なのです。
本当に原因不明で、一人じゃ解決できないかもしれません。
とりあえず、 Java とか Haskell ではこのような事にはならないと思うので、解決を先延ばしにするのが吉かもしれません。
C言語は仕組みを理解していれば動作がわかりやすいですが、たまにこのような意味不明な事態になるのが辛いです。