20234日目の記事です。最近node-semverのパーサーを作る機会があったので、HappyとAlexを用いたパーサーの作り方について紹介します。node-semverの仕様には立ち入らず、HappyとAlexの使い方について焦点を当てます。パーサーの実装はここです。https://github.com/Hagihara-A/node-semver-hsパーサの種類パーサーの実装は主に手書きするか文法書から生成する2通りの方法があります。有名なのは再帰降下構文解析と、LR構文解析でしょうか。PEGやパーサーコンビネータは再帰降下に属し、yaccやbisonはLR系の構文解析に属します。こちらのサイトでは様々な構文解析法の分析をしています。箇条書きで抄訳したいと思います。LR法は静的型付け言語のように難しいが問題を事前に検知しやすい手法だ」と喩えています。HappyはLR系の一種であるLALR(1)パーサジェネレータです。LALR(1)系の構文解析のアイデア自体は単純です。入力トークンを尺取り虫のように1つずつ見ていって最終的に構文木を生成します。この性質のおかげで、生成したパーサがO(n)で動くということを保証できます。レキサージェネレータであるAlexと組み合わせてパーサを作っていきます。AlexとHappyはHaskell自体のパーサにも使われているため実績があります。レキサーの生成Alexは.xファイルに文法を定義することでレキサーを生成します。node-semverの文法定義はリポジトリにあるので、詳しくはそこを見てください。解説のため少しだけ抜粋します。}[1-9][0-9]*や"."は、トークンに対応する正規表現を表します。右の{}に囲まれた部分には後述するaction型を持つ任意のHaskellコードを書くことができます。AlexにはWrapperといって、様々なインターフェースのレキサーを生成するオプションがあるのですが、最も基本的なインターフェースが重要です。Alexは結局のところ、以下のインターフェースのみを提供します。actionalexScanの型を見ていただければわかるのですが、alexScanは入力と状態を受け取って、1トークンだけ読み進めます。このAPIをラップしてモナド版のレキサーなどを作ることができます。モナドには以下の型が使われることが多いようです。Alexモナドで実行したalexScanの結果。要はLexerの状態を受け取って1トークン返す。状態付き字句解析Alexには便利な機能として、状態付き字句解析があります。レキサーは文字列をみるだけで対応するトークンを判別できるのが理想ですが、実際には文字列が使われる状況によって対応するトークンが変わることがあります。SemVerで言えばハイフンの扱いが挙げられます。1.2.3-alpha-2このバージョンでは、1つ目のハイフンは1.2.3とalpha-2を分けるセパレータとして用いられていますが、2つ目のハイフンは識別子alpha-2の一部として使われています。Alexの状態付き字句解析にはcontextstart-codeの2通りの方法があります。}[\-]^とはハイフンで始まった時のみ、右の定義がマッチするということを表します。この場合は1つ目のハイフンの後は識別子だということを表しています。ちなみに文字列のprefixだけでなくsuffixの条件を指定することもできます。start-codestart-codeを使うとcontextより自由に状態を設定できます。以下のように書けます。}と書くと、ident状態の時のみこのルールが適用できることを示します。start-codeはcontexより自由度が高いですが、状態を手作業で管理しなければいけないので煩雑になりがちです。パーサーの生成happyは.y拡張子の文法定義からパーサーを生成します。文法の定義も長いので少しだけ抜粋します。1.2.4のような文法を表します。range_setは非終端記号を表し、:以降にその生成規則を書きます。}というのはrange_setをパースしたときに返される値の型です。$1や$3のようにすることで生成規則の各項を参照できます。%monadと%lexerディレクティブを設定すると、Happyの生成するパーサーの型は以下になります。エラーハンドリング関数。ユーザーが実装するHappyの動作がイメージしづらいと思うので少し解説します。parseはHappyの生成する構文解析器です。Alexは名前からして字句解析のためのモナドの印象が強いですが、実際には「パーサーとレキサーで必要なもの全般」を放り込んでおくモナドです。Alexモナドを使ってレキサーとパーサーで情報をやり取りすることができます。parseErrorはわかりやすいと思います。今見ているトークンとパーサーの状態を参照してエラーを返します。lexerはそのままレキサーですが、型が直感的ではないですね。引数は"1トークン受け取ってそれを消費するパーサー”です。これはhappyが渡します。ユーザーはこのトークンを消費する過程でLexerの状態を変更して文脈に依存した解析などをすることができます。happyは終了トークンが渡されるまでこのlexerを呼んで構文解析を行います。パーサーを動かしてみるということでパーサーができました。1.2.3が^1.2.3を満たすことを確かめてみます。True期待通りに動きました。まとめ今回の実装ではパーサージェネレータを使うことで、パーサーを宣言的に実装することができました。手書きで再帰降下パーサーを実装したこともあるのですが、パーサーを手書きすると文法と実装が密結合してしまったり先読みが多くなって見通しが悪くなる印象です。パーサージェネレータは習得にコストがかかりますが、メリットも大きいと感じました。arark2024/4/1現在社会人バッジを贈って著者を応援しようバッジを受け取った著者にはZennから現金やAmazonギフトカードが還元されます。Proよくある質問LinksX(Twitter)GitHubメディアキットLegal利用規約プライバシーポリシ。