翻訳片手に再びトライ。この章にあるdo構文は、ghci環境では動作しないこともあり等価の(>>=）を使い（原著p77,翻訳p93参照）ます。また、ghci環境下ではPrelude.>>=と重複するためすべてMainの修飾子を付加しています。

8.10 (1) int::Parser Intを定義せよ

int :: Parser Int
int = mnat +++ nat
      where mnat = char '-' Main.>>= \_ ->
                   nat Main.>>= \v ->
                   return' (v*(-1))

これは簡単に突破。(Main.>>=)と(+++)を直接連結する書き方がわからなかったのでとりあえずwhere句を使ってますが、むしろこの方がコードは読みやすいと僕は思います。

ただし、解答では最後vの部分をreturn (-v)としています。natは負の数を返さないので*(-1)でも良いのですが余計な演算ですか？

8.10 (2) 普通のコメントを解析するパーサー comment ::Parser ()を定義せよ

tolf :: Parser String
tolf = many1 (sat (/='\n')) Main.>>= \x ->
       char '\n' Main.>>= \_ ->
       return' (x++['\n'])

comment :: Parser ()
comment = char '-' Main.>>= \_ ->
          char '-' Main.>>= \_ ->
          tolf Main.>>= \v ->
          return' ()

概ね正解と言えるのですが、コメントの始まりを検出するのに(char '-')二回は無駄。stringの定義はすっかり頭から消去されていました。模範解答は、

comment = string "--" Main.>>= \_ ->
          many (sat (/='\n')) Main.>>= \_ ->
          return' ()

です。僕は馬鹿正直に"改行まで"とあるのでmany1 を使っていますが、プログラム最終行など改行なしのEOFで終わるコードはパースできないかも...あと、使いもしないのにtolf でコメント部分の文字列を返してます。これはおバカ。パーサを作るっていうお題なのに。

8.10 (3) 二番目の構文規則を用いて、「2+3+4」に対する構文木を二つ書け。

本文中に例があるのでそれを参考にしながらやりました。

8.10 (4) 三番目の構文規則を用いて、「2+3」「2*3*4」「(2+3)+4」の構文木を書け

ややこしいですが、構文規則を丁寧に追っていけばなんとか作図できます。再帰を使った処理を行うときにこういう絵を描いてみるのは有効な手法だということを初めて知りました。眺めているだけだとわかった気にはなるだけだけど、手を動かすことでよりリアルにイメージできる気がします。

8.10 (5) 構文規則を最後に簡略化すると性能に劇的な効果を与えるのは何故か

最後の行程がない場合、パーサーの再帰処理が行われないため性能に大きな効果がある。

という当たり前すぎる解答しかひねり出せませんでした。う〜ん、当たり前のこと言っているだけ？模範解答は

Without left-factorising the grammar, the resulting parser would backtrack excessively and have exponential time complexity in the size of the expression. For example, a number would be parsed four times before being recognised as an expression.

なんだかわかるようでわからないようで。一つの数値をパースするのに四回も手順が要るんだから、複雑な式では手順がバクハツするぜ！ってことを言っているようですが正確なニュアンスがよく理解できていません。この問題については継続的に考えていくことにします。

8.10 (6) 減算と除算ができるように拡張せよ。

s2op :: String -> (Int -> Int -> Int)
s2op = \s -> case s of
        "+" -> (+)
        "-" -> (-)
        "*" -> (*)
        "/" -> div
        "^" -> (^)

op :: Parser Int -> String -> Int -> Parser Int
op p s v = symbol s Main.>>= \o ->
           p Main.>>= \e ->
           return' ((s2op o) v e)

expr' :: Parser Int
expr' = term' Main.>>= \t ->
        op expr' "+" t +++ op expr' "-" t +++ return' t

term' :: Parser Int
term' = factor' Main.>>= \f ->
        op term' "*" f +++ op term' "/" f +++ return' f

最初は、以下のように演算子毎に関数を作成し、

minus :: Int -> Parser Int
minus v = symbol "-" Main.>>= \_ ->
          expr' Main.>>= \e ->
          return' (v - e)
divd :: Int -> Parser Int
divd v = symbol "/" Main.>>= \_ ->
         term' Main.>>= \t ->
         return' (v `div` t)

これをexpr'とterm'で

plus t +++ minus t +++ return' t
mult f +++ divd f +++ return' f

のように呼び分けていました。が、演算子の関数はどれも同じパターンなのでこれをまとめてopという関数にしました。

8.10 (7) さらに累乗演算子を扱えるように拡張せよ。

乗算・除算より優先度が高く、括弧や数値より優先度が低いということから、構文規則を

term ::= expo('*' term' | '/' term' | E)
expo ::= factor('^' expo' | E)

のように定義してそのまま実装。

expo :: Parser Int
expo = factor' Main.>>= \e ->
        op expo "^" e +++ return' e

これで正しく動作するのですが、模範解答では演算子の位置が違います。結果的には同じことだと思うのですが考え方としてはどちらが正しいのか判断つきません。AとBの間に入れるということはAのお尻かBの頭か？

8.10 (8) 自然数と左結合の減算演算子について

a.構文規則を定義せよ

expr=expr('-' factor | factor)
factor=factor('(' expr ')' | nat)
nat=nat('0'|'1'|'2'|..)

b.パーサー　expr::Parser Intに変換せよ

expr :: Parser Int
expr = expr Main.>>= \n ->
       op factor "-" n +++ return n
       
factor :: Parser Int
factor = f' +++ natural
        where f' = symbol "(" Main.>>= \_ ->
                   expr Main.>>= \e ->
                   symbol ")" Main.>>= \_ ->
                   return' e

解答は単純に減算のみを扱うパーサになっていました。なのでfactorとかはなしでした

c. このパーサの問題点は何か

exprの再帰による無限ループ。これは訳書にそのままずばり書かれていましたし、実際b.のコードを実行してみればすぐにわかりました。

d. 問題点の解決策を示せ。manyとfoldlを使ってパーサを書き直せ

実はコレまだできていません。自分の中でまだたたみ込みがうまく消化し切れていないのでしょうか、ヒントがあっても手を出せずにいます。このまま停滞していても仕方がないので進みますが、継続課題ですね。やっぱこの章鬼門だ。