uDiary

◆ [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 の結果が正しいかどうかは、明日みましょ。