uDiary

◆ [Tiger][Haskell] Tigerbook 10 章つづき

去年の 10/2 に instrs2graph (命令リストから制御フローグラフをつくる関数）を書きかけていたまま、しばらく間があいてしまって忘れかけていたのを読んだ。

どうも、instrs2graph は完成寸前のところで止まっていたので、今日いちおう完成させて、動かしてみた。

つぎは、

• instrs2graph のテストを書く
• 10 章の残り、生存解析に進む（干渉グラフの生成）

です。

◆ [Tiger][Haskell] Tiger book 12 章、動作確認＆デバッグ開始

前回 は、レジスタ割付けを人手でやってどうにか動かしたんだが、あれから１０章（生存解析）、１１章（レジスタ割付け）を経て、晴れて全部コンパイラでできるようになった。

まだ未実装の機能もあり、機能確認もこれからなので、確認済の限られた機能だけをつかって FizzBuzz をやってみた。実行結果のスクリーンショットが上、ソースが下である。なんか、まだ & 演算子を実装してなかったようで、最初の条件を mod3 = 0 & mod5 = 0 のように書いたらうまくいかなかった。

それはそうと、うまくいかないときに「残念ながらアプリは停止しました」しか情報がないのがつらい。

let
  var mod5 := 0
  var mod3 := 0
in
  for i := 1 to 30 do (
    mod5 := i - i / 5 * 5;
    mod3 := i - i / 3 * 3;

    if (mod5 + mod3) = 0 then
      print("FizzBuzz, ")
    else if mod3 = 0 then
      print("Fizz, ")
    else if mod5 = 0 then
      print("Buzz, ")
    else
      (print(toString(i)); print(", "))
   );
   print("...\n")
end

以下、完全に自分むけメモだけど、今日の修正について。

Assem.hs の修正（oper_dst に src も加えた）は、Assem が複数命令を含んでいることによるもの。Assem の外からみると src と dst が干渉していることがわからないので、src が出口生存でないときにハザードを起した。ほんとは、Assem は１命令に対応するように実装すべきだったかも。

MakeGraph.hs はチョンボの修正。新しいラベルが保留中の前方参照を解決するときに、そのラベルと次の命令をただしく継げられていなかった。

この後、以下のように確認・デバッグを進めようかな。

• 演算、構文をひとつずつ試していく
• 関数の prelude 部分を実装（まだだったの）
• 関数呼出し
• Static link の確認
• Record, Array

◆ [Haskell][Hand] Lexer デバッグ

Haskell x Android プロジェクト（仮）

Tigerbook は基礎編を一通りこなしたので、まえからやりたかった「Haskell で Haskell コンパイラを書いてみる」プロジェクトに移行。

Lexer を一通り書いて、Parser の作成と Absyn (抽象構文）の作成を並行してやる感じかなぁと思いつつとりかかっていた。

んが、「一通りこなした」部分もきちんと勉強しなおそうというのも同時にやっていて、正規言語やら文脈自由言語やらその解析方法やらも復習している。そのために、結局 Dragon book も入手してしまった。で、再帰下降パーサといえば、『プログラミング Haskell』にもそういう章があったなと８章を見直したり。ふむふむ。あそこに述べられているのは、バックトラックのある（予測型ではない）再帰下降パーサーだな。左端のくくり出しもして LL(1) 文法に直すとこまでやっているのに、予測型再帰下降パーサにはせずに終わっている。

そりゃそうと、そんな風に Monadic Parser を復習してたら、これ の書き方がわかったので、Happy による Parser を作らなくても Lexer のデバッグができるようになった。で、案の定、いろいろ間違ってた。

• 文字列が入力ストリームを全部食べてしまう： start code 間違い（チョンボ）
• rsvdop, rsvdid まわり（昨日最後に足した）がおかしかった
• 文字列が layout 開始の位置に来たときの動作が変

いずれも、直したつもり。Lexer の確認のために今日用意したテストケースは ４つ

test1.hs は、Haskell 2010 の Figure 2.1 にあるもの。

$ sample/lexer_sample < testcases/test1.hs 
[TModule (AlexPn 0 1 1),TConid ("AStack",AlexPn 8 1 8),TOParen (AlexPn 15 1 14),TConid ("Stack",AlexPn 18 1 16),TComma (AlexPn 24 1 21),TVarid ("push",AlexPn 27 1 23),TComma (AlexPn 32 1 27),TVarid ("pop",AlexPn 35 1 29),TComma (AlexPn 39 1 32),TVarid ("top",AlexPn 42 1 34),TComma (AlexPn 46 1 37),TVarid ("size",AlexPn 49 1 39),TCParen (AlexPn 55 1 44),TWhere (AlexPn 58 1 46),TVOCurly (AlexPn 66 2 1),TData (AlexPn 66 2 1),TConid ("Stack",AlexPn 72 2 6),TVarid ("a",AlexPn 79 2 12),TEqual (AlexPn 82 2 14),TConid ("Empty",AlexPn 85 2 16),TVBar (AlexPn 107 3 14),TConid ("MkStack",AlexPn 110 3 16),TVarid ("a",AlexPn 119 3 24),TOParen (AlexPn 122 3 26),TConid ("Stack",AlexPn 124 3 27),TVarid ("a",AlexPn 131 3 33),TCParen (AlexPn 133 3 34),TSemi (AlexPn 140 5 1),TVarid ("push",AlexPn 140 5 1),TDColon (AlexPn 147 5 6),TVarid ("a",AlexPn 151 5 9),TRArrow (AlexPn 154 5 11),TConid ("Stack",AlexPn 158 5 14),TVarid ("a",AlexPn 165 5 20),TRArrow (AlexPn 168 5 22),TConid ("Stack",AlexPn 172 5 25),TVarid ("a",AlexPn 179 5 31),TSemi (AlexPn 184 6 1),TVarid ("push",AlexPn 184 6 1),TVarid ("x",AlexPn 191 6 6),TVarid ("s",AlexPn 194 6 8),TEqual (AlexPn 197 6 10),TConid ("MkStack",AlexPn 200 6 12),TVarid ("x",AlexPn 209 6 20),TVarid ("s",AlexPn 212 6 22),TSemi (AlexPn 219 8 1),TVarid ("size",AlexPn 219 8 1),TDColon (AlexPn 226 8 6),TConid ("Stack",AlexPn 230 8 9),TVarid ("a",AlexPn 237 8 15),TRArrow (AlexPn 240 8 17),TConid ("Int",AlexPn 244 8 20),TSemi (AlexPn 251 9 1),TVarid ("size",AlexPn 251 9 1),TVarid ("s",AlexPn 258 9 6),TEqual (AlexPn 261 9 8),TVarid ("length",AlexPn 264 9 10),TOParen (AlexPn 272 9 17),TVarid ("stkToLst",AlexPn 274 9 18),TVarid ("s",AlexPn 284 9 27),TCParen (AlexPn 286 9 28),TWhere (AlexPn 290 9 31),TVOCurly (AlexPn 309 10 12),TVarid ("stkToLst",AlexPn 309 10 12),TConid ("Empty",AlexPn 320 10 22),TEqual (AlexPn 335 10 36),TOBrack (AlexPn 338 10 38),TCBrack (AlexPn 340 10 39),TSemi (AlexPn 356 11 12),TVarid ("stkToLst",AlexPn 356 11 12),TOParen (AlexPn 367 11 21),TConid ("MkStack",AlexPn 369 11 22),TVarid ("x",AlexPn 378 11 30),TVarid ("s",AlexPn 381 11 32),TCParen (AlexPn 383 11 33),TEqual (AlexPn 387 11 36),TVarid ("x",AlexPn 390 11 38),TColon (AlexPn 392 11 39),TVarid ("xs",AlexPn 394 11 40),TWhere (AlexPn 398 11 43),TVOCurly (AlexPn 404 11 49),TVarid ("xs",AlexPn 404 11 49),TEqual (AlexPn 408 11 52),TVarid ("stkToLst",AlexPn 411 11 54),TVarid ("s",AlexPn 421 11 63),TVCCurly (AlexPn 428 13 1),TVCCurly (AlexPn 428 13 1),TSemi (AlexPn 428 13 1),TVarid ("pop",AlexPn 428 13 1),TDColon (AlexPn 436 13 5),TConid ("Stack",AlexPn 440 13 8),TVarid ("a",AlexPn 447 13 14),TRArrow (AlexPn 450 13 16),TOParen (AlexPn 454 13 19),TVarid ("a",AlexPn 456 13 20),TComma (AlexPn 458 13 21),TConid ("Stack",AlexPn 461 13 23),TVarid ("a",AlexPn 468 13 29),TCParen (AlexPn 470 13 30),TSemi (AlexPn 475 14 1),TVarid ("pop",AlexPn 475 14 1),TOParen (AlexPn 481 14 5),TConid ("MkStack",AlexPn 483 14 6),TVarid ("x",AlexPn 492 14 14),TVarid ("s",AlexPn 495 14 16),TCParen (AlexPn 497 14 17),TEqual (AlexPn 504 15 3),TOParen (AlexPn 507 15 5),TVarid ("x",AlexPn 509 15 6),TComma (AlexPn 511 15 7),TCase (AlexPn 514 15 9),TVarid ("s",AlexPn 520 15 14),TOf (AlexPn 523 15 16),TVOCurly (AlexPn 526 15 19),TVarid ("r",AlexPn 526 15 19),TRArrow (AlexPn 529 15 21),TVarid ("i",AlexPn 533 15 24),TVarid ("r",AlexPn 536 15 26),TWhere (AlexPn 539 15 28),TVOCurly (AlexPn 545 15 34),TVarid ("i",AlexPn 545 15 34),TVarid ("x",AlexPn 548 15 36),TEqual (AlexPn 551 15 38),TVarid ("x",AlexPn 554 15 40),TCParen (AlexPn 556 15 41),TVCCurly (AlexPn 588 17 1),TVCCurly (AlexPn 588 17 1),TSemi (AlexPn 588 17 1),TVarid ("top",AlexPn 588 17 1),TDColon (AlexPn 596 17 5),TConid ("Stack",AlexPn 600 17 8),TVarid ("a",AlexPn 607 17 14),TRArrow (AlexPn 610 17 16),TVarid ("a",AlexPn 614 17 19),TSemi (AlexPn 619 18 1),TVarid ("top",AlexPn 619 18 1),TOParen (AlexPn 625 18 5),TConid ("MkStack",AlexPn 627 18 6),TVarid ("x",AlexPn 636 18 14),TVarid ("s",AlexPn 639 18 16),TCParen (AlexPn 641 18 17),TEqual (AlexPn 644 18 19),TVarid ("x",AlexPn 647 18 21)]

うーん、いっぱいだ。あとで見よう。ってことで、小さいやつを用意したのがあとの３つ。

$ sample/lexer_sample < testcases/test2.hs 
[TVOCurly (AlexPn 0 1 1),TVarid ("main",AlexPn 0 1 1),TEqual (AlexPn 6 1 6),TVarid ("putStrLn",AlexPn 9 1 8),TString ("Hello",AlexPn 19 1 17)]


$ sample/lexer_sample < testcases/test3.hs 
[TModule (AlexPn 0 1 1),TConid ("Main",AlexPn 8 1 8),TWhere (AlexPn 14 1 13),TVOCurly (AlexPn 21 3 1),TVarid ("main",AlexPn 21 3 1),TEqual (AlexPn 27 3 6),TDo (AlexPn 30 3 8),TVOCurly (AlexPn 35 4 3),TVarid ("putStr",AlexPn 35 4 3),TString ("Hello",AlexPn 43 4 10),TSemi (AlexPn 54 5 3),TVarid ("putStrLn",AlexPn 54 5 3),TString (", world!",AlexPn 65 5 12)]


$ sample/lexer_sample < testcases/test4.hs 
[TVOCurly (AlexPn 0 1 1),TVarid ("f",AlexPn 0 1 1),TVarid ("s1",AlexPn 3 1 3),TVarid ("s2",AlexPn 7 1 6),TEqual (AlexPn 11 1 9),TVarid ("putStrLn",AlexPn 14 1 11),TVarsym ("$",AlexPn 24 1 20),TVarid ("s1",AlexPn 27 1 22),TVarsym ("++",AlexPn 31 1 25),TVarid ("s2",AlexPn 35 1 28),TSemi (AlexPn 40 3 1),TVarid ("main",AlexPn 40 3 1),TEqual (AlexPn 47 3 6),TDo (AlexPn 50 3 8),TVOCurly (AlexPn 55 4 3),TString ("foo",AlexPn 55 4 3),TBackquote (AlexPn 62 4 9),TVarid ("f",AlexPn 64 4 10),TBackquote (AlexPn 66 4 11),TString ("bar",AlexPn 69 4 13),TSemi (AlexPn 78 5 3),TVarid ("putStrLn",AlexPn 78 5 3),TString ("Hello!",AlexPn 89 5 12)]

最後の test4.hs が今日見つけた問題の確認用で、do 節の最初のトークンが文字列だった場合のやつ。直す前は、文字列の後ろに仮想 ocurly が挿入されてしまっていた。

test1 の結果が正しいかどうかは、明日みましょ。

◆ [Haskell][Hand] Parser.y デバッグ

昨日、Haskell 2010 report みながら、えいっと Parser.y を書いたんだけど、
ずいぶん conflict を出してしまった。

unused rules: 5
shift/reduce conflicts:  144
reduce/reduce conflicts: 212

ひとつひとつ、文法の曖昧なのをなくしていこう。
ひとつの問題で沢山の衝突が引き起される傾向があるようなので、この数ほど修正箇所はないだろう。

1. 空の規則じゃなくて error トークンをつかう

レイアウト規則では、そうしないと構文エラーになる箇所には仮想閉じブレースが補われることに
なっている。

そこで、仮想ブレースが閉じていないのを許容する文法にすればいいのかなと思ったんだけど、
こういうのはいかにも衝突の原因になる。

ccurly_opt: vccurly                            {}
  |          {- empty -}                        { {- pop ctx -} }

GHC のパーサーのソースをみると、error トークンが使われていて、Happy のマニュアルにも
そういう利用方法が書かれている。

close : '}'                  { () }
      | error        { () }

ついでに、非終端記号の名前も真似して close にしてみよう。

unused rules: 5
shift/reduce conflicts:  96
reduce/reduce conflicts: 176

shift/reduce が 48 個減、reduce/reduce が 36 個へった。

2. 単純間違い

lpat: gcon seq_apat

は

lpat: gcon seq1_apat

の間違いだった。このせいで apat: gcon と衝突。

unused rules: 5
shift/reduce conflicts:  128 (+32)
reduce/reduce conflicts: 127 (-49)

3. 空規則の除去

やっぱ空の規則をつくりすぎるのよくないもう一つの例。

topdecl: 'class' sctx_opt tycls tyvar 'where' cdecls

ctx_opt: context '=>'
  |      {- empty -}

こんななのだが、context の最初にも tycls と同じ文字列が来てもいいので曖昧。
GHC のソースをみると、A -> (context '=>' |) のような非終端記号をつくるので
はなく、

tycl_hdr -> context '=>' tycls | tycls

のようにしてあった。こうすることで、問題となる還元規則がなくなり、

パーサは tycls が context の一部なのかそうでないのか判明するまで複数のポインタを
持てるようになる。（「lex&yacc プログラミング」p.301)

ただ、このあたりは、上のように文法を書き直すだけじゃなくて、もうちょっと整理しないとだめっぽい。

qconid, qtycls などもいっぱい衝突している。(軒並 qconid に還元しようとしたり)

まいったな、まだまだだな。