HaskellのAlexとHappyでnode-semverパーサーを実装する
この記事はHaskell Advent Calendar 2023４日目の記事です。
最近node-semverのパーサーを作る機会があったので、HappyとAlexを用いたパーサーの作り方について紹介します。あまりnode-semverの仕様には立ち入らず、HappyとAlexの使い方について焦点を当てます。
パーサーの実装はここです。
パーサの種類
パーサーの実装は主に手書きするか文法書から生成する２通りの方法があります。最も有名なのは再帰降下構文解析と、LR構文解析でしょうか。
PEGやパーサーコンビネータは再帰降下に属し、yaccやbisonはLR系の構文解析に属します。
こちらのサイトでは様々な構文解析法の分析をしています。箇条書きで抄訳したいと思います。
- 再帰降下系
- わかりやすい
- 実はどの文法クラスに対応するか理論的に明らかになっていない
- 曖昧な文法を事前に検知できない
- 無限に先読みができるため、計算量の見積もりがしづらい
- 左結合の演算子のパースが素直にできない
- エラーリカバリーしやすい
- LR系
- 曖昧な文法を事前に検知できる
- 先読みが制限されるので、計算量の見積もりができる(LR(1)なら
O(n) - 文脈自由文法のうち、広めのサブセットを受理できる
- エラーリカバリーはやりにくい
- 演算子の優先度を考慮できる
この記事の筆者は、「再帰降下法は動的型付け言語のようにとっつきやすいが問題が起こりやすい手法で、 LR法は静的型付け言語のように難しいが問題を事前に検知しやすい手法だ」と喩えています。
HappyはLR系の一種であるLALR(1)パーサジェネレータです。LALR(1)系の構文解析のアイデア自体は単純です。入力トークンを尺取り虫のように１つずつ見ていって最終的に構文木を生成します。この性質のおかげで、生成したパーサが
また、レキサージェネレータであるAlexと組み合わせてパーサを作っていきます。AlexとHappyはHaskell自体のパーサにも使われているため実績があります。
レキサーの生成
Alexは.xファイルに文法を定義することでレキサーを生成します。node-semverの文法定義はリポジトリにあるので、詳しくはそこを見てください。解説のため少しだけ抜粋します。
tokens :-
[1-9][0-9]* { readTokenDigits }
"." { token TokenDot }
"+" { token TokenPlus }
[1-9][0-9]*や"."は、トークンに対応する正規表現を表します。右の{}に囲まれた部分には後述するaction型を持つ任意のHaskellコードを書くことができます。
AlexにはWrapperといって、様々なインターフェースのレキサーを生成するオプションがあるのですが、最も基本的なインターフェースが重要です。Alexは結局のところ、以下のインターフェースのみを提供します。
alexScan :: -- Alexの生成するレキサー
AlexInput -> -- ユーザー定義の任意の入力
Int -> -- start code(後述)
AlexReturn action -- 返り値。actionはユーザー定義のトークンを返す関数
data AlexReturn action
= AlexEOF
| AlexError
!AlexInput
| AlexSkip
!AlexInput
!Int -- トークンの長さ
| AlexToken
!AlexInput -- 残りの入力
!Int -- トークンの長さ
action
alexScanの型を見ていただければわかるのですが、alexScanは入力と状態を受け取って、１トークンだけ読み進めます。このAPIをラップしてモナド版のレキサーなどを作ることができます。
モナドには以下の型が使われることが多いようです。
import Control.Monad.Trans.State.Strict (StateT)
type Alex a = StateT AlexState (Either String) a
alexMonadScan :: Alex Token -- Alexモナドで実行したalexScanの結果。ユーザーが書く。要はLexerの状態を受け取って１トークン返す。
状態付き字句解析
Alexには便利な機能として、状態付き字句解析があります。レキサーは文字列をみるだけで対応するトークンを判別できるのが理想ですが、実際には文字列が使われる状況によって対応するトークンが変わることがあります。
SemVerで言えばハイフンの扱いが挙げられます。
1.2.3-alpha-2
このバージョンでは、1つ目のハイフンは1.2.3とalpha-2を分けるセパレータとして用いられていますが、２つ目のハイフンは識別子alpha-2の一部として使われています。
Alexの状態付き字句解析には
- context
- start-code
の２通りの方法があります。
context
contextを使うと、識別子は以下のように定義できます
[\-]^[\-a-zA-Z0-9]+ { readTokenIdentifier }
[\-]^とはハイフンで始まった時のみ、右の定義がマッチするということを表します。この場合は１つ目のハイフンの後は識別子だということを表しています。
ちなみに文字列のprefixだけでなくsuffixの条件を指定することもできます。
start-code
start-codeを使うとcontextより自由に状態を設定できます。
例えば以下のように書けます。
<ident>[\-a-zA-Z0-9]+ { readTokenIdentifier }
と書くと、ident状態の時のみこのルールが適用できることを示します。start-codeはcontexより自由度が高いですが、状態を手作業で管理しなければいけないので煩雑になりがちです。
パーサーの生成
happyは.y拡張子の文法定義からパーサーを生成します。文法の定義も長いので少しだけ抜粋します。詳細はリポジトリをみてください
range_set :: { RangeSet }
: range { [$1] }
| range_set logical_or range { $3:$1 }
これは1.2.3 || 1.2.4のような文法を表します。range_setは非終端記号を表し、:以降にその生成規則を書きます。 :: { RangeSet }というのはrange_setをパースしたときに返される値の型です。$1や$3のようにすることで生成規則の各項を参照できます。
%monadと%lexerディレクティブを設定すると、Happyの生成するパーサーの型は以下になります。
-- %tokentype { Token }
-- %name parse
-- %error { parseError }
-- %lexer { lexer } { TokenEOF }
-- %monad { Alex } { >>= } { pure }
parse :: Alex t -- tは構文木の型。happyが生成する
parseError :: Token -> Alex a -- エラーハンドリング関数。ユーザーが実装する
lexer :: (Token -> Alex a) -> Alex a -- レキサー関数。ユーザーが実装する
Happyの動作がイメージしづらいと思うので少し解説します。
parseはHappyの生成する構文解析器です。Alexは名前からして字句解析のためのモナドの印象が強いですが、実際には「パーサーとレキサーで必要なもの全般」を放り込んでおくモナドです。Alexモナドを使ってレキサーとパーサーで情報をやり取りすることができます。
parseErrorはわかりやすいと思います。今見ているトークンとパーサーの状態を参照してエラーを返します。
lexerはそのままレキサーですが、型が直感的ではないですね。第一引数は"１トークン受け取ってそれを消費するパーサー”です。これはhappyが渡します。ユーザーはこのトークンを消費する過程でLexerの状態を変更して文脈に依存した解析などをすることができます。happyは終了トークンが渡されるまでこのlexerを呼んで構文解析を行います。
パーサーを動かしてみる
ということでパーサーができました。動かしてみましょう。1.2.3が^1.2.3を満たすことを確かめてみます。
range = fromRight undefined (parseRange "^1.2.3") -- ^1.2.3 is >=1.2.3 <2.0.0-0
v_123 = version 1 2 3 [] []
print (satisfies v_123 range) -- True
期待通りに動きました。
まとめ
今回の実装ではパーサージェネレータを使うことで、パーサーを宣言的に実装することができました。手書きで再帰降下パーサーを実装したこともあるのですが、パーサーを手書きすると文法と実装が密結合してしまったり先読みが多くなって見通しが悪くなる印象です。パーサージェネレータは習得にコストがかかりますが、メリットも大きいと感じました。
Discussion