haskell-jp / mokumoku-online #60 at 2023-11-05 14:18:05 +0900

途中からですが参加させてください
Happyでsemverパーサーを書きます

自分のための整理を兼ねて進捗を共有します。

happyでsemverをパースするの自体は難しくない
1.2.3-alpha+build123 これがsemver。
難しいのは字句解析。ハイフンが識別子としても使えるので`1.2.3-alpha-7`がOKになる。これだとセパレータと識別子ののハイフンとの区別がつかない。

さらに、利便性のためにsemverを拡張したnode-semverというものがある。package.jsonでよく見る`^1.2.3` は実は拡張構文
node-semverでは`X, x, *` をバージョン番号として許容する。つまり、`1.2.x` がOKになる。このため、`-, X, x` だけをみてどのトークンかを判別できない。

よって、１文字ずつ文字列を消費していく単純な字句解析では正しくトークン化できないためParserと文脈を共有しながら字句解析しなければいけない。
今は識別子をパースしてるからハイフンは識別子だよーみたいな

happyにはパーサをユーザー定義のモナドにできるので、Stateモナドを使って文脈を保持することにする。Alexを使うとlexerも生成できるが、とりあえず今回は手書きする。

まだあった。
1.0.0 - 2.0.0 のように、ハイフンをバージョン範囲を指定するのにも使うことができる。このハイフンは前後に１個以上の空白がなければいけない

なので空白を単純に読み飛ばすわけにもいかない

地道にパーサーを描いているが、だんだんとParsecTと同じ型になってしまい、車輪の再発明感がすごい。。。

これ最初からParsecでやればいいのでは・・・！？

semverって多分先読み１でできるだろうからParsecでやるのがベストなのかもしれない・・・

https://tratt.net/laurie/blog/2020/which_parsing_approach.html

構文解析の手法を比較したこの記事を読んでみる

1. 再帰降下
a. 最もわかりやすい
b. 実は形式言語のどのクラスに属するかは明らかではない
c. 曖昧な文法（複数通りの解析ができる文法）を事前に検知できない
d. 素直な実装では左結合の演算子をパースすると無限ループになる
e. 筆者は、再帰下降解析はアセンブリ言語のような、自分の足を自分で打ち抜ける手法だと考えている
2. Generalised parser
a. 文脈自由文法に対応している
b. 曖昧な文法を「ランタイムで」検出できる
c. 筆者は、この手法は動的型付け言語のように強力だが静的解析の難しい手法だと考えている
3. LL, LR parse
a. 文法に曖昧さがない
b. CFGの厳密なサブセットになるわけではない。LRだけど、CFGじゃないみたいな文法が存在できる
4. LL parse
a. 左再帰がない
b. あんまりメジャーじゃない
5. LR parse
a. LLより強い
b. 曖昧さがない
c. 筆者は、静的型付け言語のように制限的だが安全であると考えている
6. PEG
a. 本質的には再帰降下
b. 何らかの問題があるらしい
7. パフォーマンス
a. そもそも現代のマシンではどの手法でも十分に早い
b. それでもLRが早い
8. エラーリカバリー
a. 再帰下降はめっちゃやりやすい
b. LRでリカバリは難しい。けど改善の余地はある
筆者は LR解析が最も実用的と考えている

ということで Happyでパーサー開発を続けます。
確認したらAlexのContextという機能を使えそうなのでAlexも使います。

すごい！AlexのContextを使ったら驚くほど簡単にパースできた！

とりあえずsemverパーサー自体は完成しました！AlexとHappyをうまく使うと驚くほど簡単にできました。
あとはパースできた構文木をバージョン制約に変換する処理を実装します。