この記事は Haskell Advent Calendar 2018 の 19 日目の記事です．
Haskell の言語仕様書にある，演算子を含む式の構文解析アルゴリズムを試してみます．
はじめに
Haskell では，演算子の結合性と優先度をプログラムの中で定義できるようになっていますよね．例えばこんな感じに...．
infixl 7 * -- 左結合，優先度 7
infixl 6 + -- 左結合，優先度 6
infixr 5 ++ -- 右結合，優先度 5
infix 4 > -- 非結合，優先度 4
これはプログラマにとっては便利な機能ですが，コンパイラ開発者の立場に立ってみると，悩みの種であったりします．演算子の結合性が決め打ちできない（コンパイル時までわからない）ということは，従来のように yacc の %left ルールで結合性を定義することもできないというわけです．
幸いなことに，Haskell の言語仕様書（Haskell Language Report）には，演算子を含む式の構文解析アルゴリズムが示されています．そのため，Haskell のコンパイラ開発者は，この演算子の問題で悩む必要性はなさそうです．
- 10.6 Fixity Resolution - Haskell Language Report 2010
https://www.haskell.org/onlinereport/haskell2010/haskellch10.html#x17-18100010.6
10.6 Fixity Resolution
The following is an example implementation of fixity resolution for Haskell expressions. Fixity resolution also applies to Haskell patterns, but patterns are a subset of expressions so in what follows we consider only expressions for simplicity.
というわけで，この記事では言語仕様書で示されているアルゴリズムをお試しで使ってみたいと思います．
試してみる
言語仕様書には Haskell のコードで具体的にアルゴリズムが示されているので，この記事ではそのコードをそのまま利用します．言語仕様書にパーサの具体的なコードが載っているというのは面白いですね！
10.6 節 (Fixity Resolution) に示されている約 50 行のコードをファイル（例えば resolve.hs）に保存し，GHCi でロードします．
% ghci
GHCi, version 8.0.2: http://www.haskell.org/ghc/ :? for help
Prelude> :l resolve.hs
[1 of 1] Compiling Main ( resolve.hs, interpreted )
Ok, modules loaded: Main.
これで，以下のデータ型と関数が定義されます．
type Prec = Int -- 優先度
type Var = String -- 変数
data Op -- 二項演算子
= Op String Prec Fixity
deriving (Eq,Show)
data Fixity -- 結合性
= Leftfix -- 左結合
| Rightfix -- 右結合
| Nonfix -- 非結合
deriving (Eq,Show)
data Exp -- 式
= Var Var -- 変数
| OpApp Exp Op Exp -- 二項演算子の適用
| Neg Exp -- 単項マイナスの適用
deriving (Eq,Show)
data Tok -- トークン
= TExp Exp -- 式
| TOp Op -- 二項演算子
| TNeg -- 単項マイナス
deriving (Eq,Show)
resolve :: [Tok] -> Maybe Exp
最後の resolve 関数が，中置演算子を含む式を表すトークン列の結合性を解決します．
試しに x + y + z の結合性を resolve 関数で解決してみましょう．
*Main> let x = TExp (Var "x")
*Main> let y = TExp (Var "y")
*Main> let z = TExp (Var "z")
*Main> let plus = TOp (Op "+" 6 Leftfix)
*Main> resolve [x, plus, y, plus, z]
Just (OpApp (OpApp (Var "x") (Op "+" 6 Leftfix) (Var "y")) (Op "+" 6 Leftfix) (Var "z"))
このように，x + y + z は (x + y) + z と解析されることがわかります．
他の例もいくつか見てみましょう．
*Main> let x = TExp (Var "x")
*Main> let y = TExp (Var "y")
*Main> let z = TExp (Var "z")
*Main>
*Main> let times = TOp (Op "*" 7 Leftfix)
*Main> let plus = TOp (Op "+" 6 Leftfix)
*Main> let append = TOp (Op "++" 5 Rightfix)
*Main> let gt = TOp (Op ">" 4 Nonfix)
*Main>
*Main> -- x + y * z
*Main> resolve [x, plus, y, times, z]
Just (OpApp (Var "x") (Op "+" 6 Leftfix) (OpApp (Var "y") (Op "*" 7 Leftfix) (Var "z")))
*Main>
*Main> -- x ++ y ++ z
*Main> resolve [x, append, y, append, z]
Just (OpApp (Var "x") (Op "++" 5 Rightfix) (OpApp (Var "y") (Op "++" 5 Rightfix) (Var "z")))
*Main>
*Main> -- x > y > z
*Main> resolve [x, gt, y, gt, z]
Nothing
最後の x > y > z は非結合の演算子が並んでいるので，解析に失敗して Nothing と評価されます．
解説
（アルゴリズムを解説しようかと思ってたのですが，既に言語仕様書に十分噛み砕かれた説明が書かれていることを思い出したので，省略します．）
最後に
この記事では，Haskell における中置演算子を含む式の構文解析アルゴリズムを試してみました．Haskell のパーサに限らず使える汎用的なアルゴリズムですので，自分のオレオレ言語のパーサとかで使ってみてはいかがでしょうか．
実は私も，学生のときに作ったオレオレ言語で，このアルゴリズムを使ってパーサを書いたりしていました．そのときは OCaml でパーサを書いていたので，Haskell のコードを OCaml のコードに翻訳して組み込んでいました．
余談ですが，パーサとかを書いてると，代数的データ型のパワーを実感しますよね．一度その魅力を味わってしまうと，代数的データ型がネイティブにサポートされていない言語にはなかなか戻れなくなります．
参考
- 10.6 Fixity Resolution - Haskell Language Report 2010
https://www.haskell.org/onlinereport/haskell2010/haskellch10.html#x17-18100010.6