haskell-jp / questions #104 at 2023-11-04 07:43:32 +0900

happyでsemverの構文解析に取り組んでいます。semverを変形したにも対応したいです。
node-semverでは`1.2.x`のように、"x"をバージョン指定に使うことができます。
一方で`1.2.3-xxxxx`のように、メタタグにも"x"を使うことができます。この場合、xの意味が文脈によって変わってしまい文脈依存文法になる？ため、純粋なhappyだけでは構文解析はできないと思うのですがどう解決すれば良いでしょうか？
トークン化を工夫することでこれを回避できるのでしょうか？

1.2.x の x を patch、`1.2.3-x` の x を tag と名付けるとして、トークン化の段階では patch-or-tag というトークンにして、そのトークン列を構文解析することでなんとかなり、ならないかなあ

Haskellはもっと文法複雑なはずなので気になってGHCの定義を見に行ってみたんですが、どうも継続モナド的な仕組みを使って字句解析と構文解析を行ったり来たりすることで何とかしてるみたいです。難しすぎました。。。

Alexの start-codes でいけませんか？

<0>   \-         { begin tag }
<0, tag> \.      { begin 0 }

<0>   x          { \_ -> TokX }
<tag> @string    { \s -> TokTag s }

こんな感じ？
start codeはデフォルトで0なのですが、`-` に遭遇したらtagというstart codeに切り替えて、`.` に遭遇したら0に戻します。
使用するwrapperによって上の書き方のままできるかはわかりませんが

ありがとうございます。 調べたところ、どうにかして文脈付きのlexerで字句解析するしかないみたいです。試せてないですが、おそらくおっしゃっているstart-codesでもできると思います。alexだとそういうことが簡単？にできそうなので触ってみようと思います。

しかし、文脈付きで字句解析するともはや構文解析に片足を突っ込んでいるような違和感を持つのですが、構文解析とわざわざ分けている理由があるんでしょうか？実はこのタイプは古典的で、最近はPEGなどの字句解析がいらない手法がメジャーになってきてるとかあるんですかね。。。

Haskell だと parsec を始めとするパーサーコンビネーターがメジャーな気がしますね
https://hackage.haskell.org/package/parsec

パーサーコンビネーター人気ですよね。そこらへんの話をたくさんききたい…

解決したので共有します。
結果的にAlexのcontext機能をつかってこの問題を解決できました。
[\-\+]^[\-a-zA-Z0-9]+ { TokenIdentifier }
上のような文法を定義すると、`-` または`+` 以降の文字列を識別子としてパースしてくれます。

ghci> alexScanTokens "--"
[TokenHyphen,TokenIdentifier "-"]

こんな感じで、２回目のハイフンは識別子扱いになります。
Alexを教えてくださったksrkさん、助言を頂いたkakkun61さんありがとうございました。

解決なさったようなので、いまさらの感想ですが。セマンティックバージョンのATSの定義があれば、baseパッケージのText.ParserCombinators.ReadP で字句解析抜き（文字を字句とするだけ）で書けそうに思います。

@nobsun 今回はパーサージェネレータの練習としてhappyを選択したので、パーサーコンビネータを使うつもりはないんです。すいません:pray:
ですがそのモジュールは知らなかったので勉強になりました。ありがとうございます。

いえいえ、グッドジョブ！です。字句解析をさぼれそうなので、lex_state のようなものをもちだすまでもないかもと、実装もしてないのに勝手な感想を述べてしまいました:pray: