Movatterモバイル変換

[0]ホーム
URL:

Future Tech Blog
フューチャー技術ブログ
Programmingカテゴリ

パーサーコンビネータを自作してみる

秋のブログ週間 6本目です。

夏休みの自由研究でパーサーコンビネータをもっと身近にするという記事でパーサーコンビネータを使ってみる記事を書きました。せっかくなので作ってみたくなったのでチャレンジしてみました。出来上がったライブラリは以下のところにあります。ただ、要件が変わると欲しい機能も変わってくるし、どんなケースにもマッチするライブラリを作るのは難しいと思うので、規制のライブラリを使うのではなく、自分の用途に合わせて作れるようになった方が良いのかなという気がします。

とりあえず作ってみるには次のようにClaude.aiに次のようにタイプすればざっと作ってくれます。

パーサーコンビネータをGoで作成して

長いので全部は貼り付けませんが（各自実行してみてください）、こんな感じで使えるコードが生成されました。

funcmain() {
// 数字をパースする例
    digit := Digit()
    result, rest, err := digit("123")
// result: 1, rest: "23", err: nil

// 文字'a'をパースする例
    charA := Char('a')
    result, rest, err := charA("abc")
// result: 'a', rest: "bc", err: nil

// 数字を複数回パースする例
    digits := Many(Digit())
    results, rest, err := digits("123abc")
// results: [1, 2, 3], rest: "abc", err: nil
}

これはとてもシンプルです。生成されたパーサーに文字列を渡すと、そのパーサーが解釈した結果と、残りの文字列を返します。Digit()は1文字の数値にマッチします。Char()は特定の文字です。このプリミティブなパーサを受け取ってパーサーを返す関数もいくつか実装されました。ここではMany()しか使われていませんが、以下の3つも生成されました。

  • Many(): 指定された1このパーサーをマッチしなくなるまで繰り返し適用する
  • Sequence(): パーサーを2つ引数で受けとり、その順序でマッチするかしなければエラーを返す
  • Choice(): 指定された複数のパーサーのうち、1つにマッチしたらそれを返す

パーサーを組み合わせてパーサーを生成する関数を使うことで、任意の文字列にマッチする関数ができるというわけです。パーサーを組み合わせるのでパーサーコンビネータと呼ばれます。

ここを出発点として、実用的なパーサーコンビネータのAPIを考えてみます。

基本的な改造方針

自動生成されたものは1つの文字列からトークン化を行う由緒正しいパーサー（というよりもトークナイザー）用途には問題ないですが、前回同様、既成のパーサーの作ったトークンを解釈する用途で使いたいのでそちら方面にフォーカスします。

前回の記事で書いたように、小さいパーサーを組み合わせて実行するだけではなく、多段で重ねて実行できる方が、その構文木を処理するコードもその上に載せられて便利です。また、わかりやすいエラー処理も載せられます。たとえば、次のような式があったとします。いろんな形式の数値を扱いたいとします。

0x1 + 0o9 + 0b2 + 10

この場合に、全部のバリエーションをパーサー上で扱うのでも良いですが、全部をひとまず数字っぽいトークンとして扱って、実際の値の解釈はあとでやれる方が便利です。

  • ゆるい構文処理パーサと厳しい数値パーサを分けて作れる
  • より分かりやすいエラーメッセージが出しやすい

パーサーはちょっと複雑な文法を実装しようとするとすぐに長大な定義になってしまいます。これを分割する方法があるというのは便利です。パーサーコンビネータはパーサーを組み立てるので、1つ1つのパーサ関数自体は小さく分離できるのですが、最終的なパーサーはでかいルール定義になるので、実行時の動きを追いかけるのは大変です。

上記のコードは2進数なのに2を使ったり、8進数なのに9を使っているのでエラーにすべきです。最初からSequence(Char('0'), Char('b'), Choice(Char('0'), Char('1')))というガチガチのルールで書いてしまうと、バックトラックが発生して「入力文字列はマッチしなかった」しか結果がわかりません。よく観察するとルールとマッチしないというのがようやくわかる感じです。ゆるいルールで「数値っぽいもの」を一度解釈して、から後から細かく解釈して「2進数っぽいが数値が範囲外」という情報を出したほうが人間には優しいです。なるべくバックトラックさせない動きにした方が人間が解釈するメンタルモデルに近い動きになると思います。

実用化に向けて

途中経過ではパース中に変換した内容など、多様な情報を扱う必要がありますが、アプリケーションによって扱う情報は異なるため、ジェネリクスを使って任意の追加情報をもてるような、次のような形式のトークン列を受け取って、それを変換していくというコードにします。

type Token[T any]struct {
Typestring// トークンの型
    Rawstring// ソース情報
Val  T// 変換の出力などに使うデータ
}

パーサーは次のような形式の関数とします。

// パーサーは関数。消費したトークン数、変換後のトークン、エラーを返す
type Parser[T any]
func(src []Token[T]) (consumedint, newTokens []Token[T], errerror)

返すエラーで後続の処理が変える必要があるかと思うので追加しておきます。

var (
// マッチしなかった: Choice()相当で他の候補にマッチしたら回復
ErrNotMatch = fmt.Errorf("not match")
// 回復不能なエラー
ErrCritical = fmt.Errorf("critical error")
)

トークン列を受け取り、解釈した数を最初の返り値として返します。新たに生成されたトークンやエラー情報を返します。これを連続して実行していくことで期待されるトークン列に変換していきます。次のコードはRawに入っている文字列が数字だったらそれに変換するするパーサです。

funcDigit(src []Token[int]) Parser[int] {
if src[0].Type =="raw" {
        t := src[0]
        i, err := strconv.Atoi(t.Raw)
if err !=nil {
return0,nil, ErrNotMatch// 変換失敗
        }
// 成功
return1, []Token[int]{{Type:"digit", Pos: t.Pos, Val:int(i)}},nil
    }elseif src[0].Type =="digit" {// すでに変換済み
return1, src[0:1],nil
    }
return0,nil, ErrNotMatch// どれにもマッチせず
}

基本要素を作る

生成AIが作ってくれた要素のうち、シーケンス、複数の候補のマッチは最低限必要です。リピート系は1つ以上とかいろいろ必要になるのでとりあえず後回し。あと、マッチした候補を置き換える変換処理も実装します。

// 連続した要素にマッチ
funcSeq[Tany](parsers ...Parser[T]) Parser[T] {
returnfunc(src []Token[T]) (int, []Token[T],error) {
converted :=make([]Token[T],0,len(parsers))
offset :=0
for _, p :=range parsers {
if offset >=len(src) {// ソースを消費しきったけどまだパーサが残っている
return0,nil, ErrNotMatch
}
consumed, newTokens, err := p(src[offset:])// 変換エラー
if err !=nil {
return0, src, ErrNotMatch
}
converted =append(converted, newTokens...)
offset += consumed
}
return offset, converted,nil
}
}

// どれかの候補にマッチ
funcOr[Tany](parsers ...Parser[T]) Parser[T] {
returnfunc(pctx *ParseContext[T], src []Token[T]) (int, []Token[T],error) {
for _, p :=range parsers {
offset, newTokens, err := p(src[offset:])
if err ==nil {// マッチした
return offset, newTokens,nil
}elseif errors.Is(err, ErrNotMatch) {// 回復可能なエラー
continue
}
// 回復不能なエラー
return offset,nil, err
}
// どの候補にもマッチしなかった
return offset,nil, ErrNotMatch,
}
}

// 変換関数
type Transformer[T any]func(src []Token[T]) (converted []Token[T], errerror)

// パーサを呼び出し、マッチした要素に変換をかける
funcTrans[Tany](parser Parser[T], tf Transformer[T]) Parser[T] {
returnfunc(src []Token[T]) (int, []Token[T],error) {
consumed, newTokens, err := parser(src)
if err !=nil {
return0, src, err
}
result, err := tf(newTokens)
if err !=nil {
return0, src, err
}
return consumed, result,nil
}
}

ここまでできると、さきほどのDigit()と組みわせて簡単な数式とその処理ができるようになります。

// 演算子
funcOperator(src []Token[int]) (int, []Token[int],error) {
supportedOperators :=map[string]bool{
"+":true,
"-":true,
"*":true,
"/":true,
}
if src[0].Type =="raw" {
        t := src[0]
if _, ok := supportedOperators[t.Raw]; ok {
return1, []Token[int]{{Type:"operator", Raw: t.Raw}},nil
        }
return0,nil, ErrCritical
    }elseif src[0].Type =="operator" {
return1,nil,nil
    }
return0,nil, ErrNotMatch
}

// 数式
funcExpression() Parser[int] {
// Transを使って計算を行う
expressionTransform :=func(src []Token[int]) (converted []Token[int], errerror) {
var resultint
switch src[1].Raw {
case"+":
result = src[0].Val + src[2].Val
case"-":
result = src[0].Val - src[2].Val
case"*":
result = src[0].Val * src[2].Val
case"/":
result = src[0].Val / src[2].Val
}
// 演算した結果を新しいdigitノードとして返す
return []Token[int]{{Type:"digit", Val: result}},nil
}
return Trans(
        Seq(Digit, Operator, Digit),
        expressionTransform)
}
// パーサを評価して結果を返す
funcEvaluate[Tany](src []Token[T], parser Parser[T]) (result []T, remained []Token[T], errerror) {
consumed, newTokens, err := parser(pctx, src)
if err !=nil {
returnnil,nil, err
}
remained = src[consumed:]
result =make([]T,len(newTokens))
for i, t :=range newTokens {
result[i] = t.Val
}

return result, remained,nil
}

// 文字列のスライスをトークン化してから評価
funcEvaluateWithRawTokens[Tany](src []string, parser Parser[T]) (result []T, remained []Token[T], errerror) {
tokens :=make([]Token[T],len(src))
for i, rt :=range src {
tokens[i] = Token[T]{Type:"raw", Raw: rt}
}
return Evaluate(tokens, parser)
}

実行はこんな感じ

result, _, err := EvaluateWithRawTokens([]string{"100","+","200"}, Expression())
// result -> []int{300}

実行のトレースできるようにする

数式のコードは以下のようになっていましたが、ErrNotMatchが帰ってきたところで、数字のところに文字が入ってしまったのか、演算子が不正だったのか、トークンが足りなかったのかどこまで処理が正しく進んだのか情報がありません。ユニットテストで小さくコードを育てていっても、いざリファクタリングしてちょっとでもエラーが出てしまうと何が起きているのかわからなくなってお手上げです。全部のテストを捨ててまた積み上げをしていかないといけなくなります。

Seq(Digit, Operator, Digit)

場所情報をエラーに付与する

トークンに場所情報を付与します。エラー発生時にはエラーにその情報を付与するようにします。元のパーサーが作ってくれるASTには行と列の情報が載っているかもしれません。それを付与しておけば元のソースの位置が特定できます。ない場合はトークンのインデックスを代わりに使う必要があるでしょう。

type Posstruct {
Lineint
Colint
Indexint
}

type Token[T any]struct {
    :
Pos  *Pos// これを足す
}

// ErrNotMatchは直接返さずにこのファクトリ関数で作って返すようにする
// ErrNotMatchをラップしているのでOr内の条件は変える必要がない
funcNewErrNotMatch(expected, actualstring, pos *Pos)error {
var errerror
if actual !="" {
err = fmt.Errorf("%w expected: %s, actual: %s", ErrNotMatch, expected, actual)
}else {
err = fmt.Errorf("%w expected: %s, but not", ErrNotMatch, expected)
}
return &ParseError{
Parent: err,
Pos:    pos,
}
}

type ParseErrorstruct {
Parenterror
Pos    *Pos
}

実行のトレースをする

連続した要素のSeq()の要素の途中で止まった、ぐらいであればトークンの位置情報だけあれば良いですが、Or()や要素のリピート（まだ作ってないですが）を駆使してくると、ここでマッチするはずだったのだが、マッチせずに期待しないパーサの実行が行われたみたいなことが起きたりします。例えば、10 * aという掛け算のつもりが、10がなくて、aという変数のポインタ演算になったり・・・みたいな。特にパーサのバグを見つける場合にはどこが実行されたのかのログが見たくなります。

トレースのログはスレッドローカル的な場所に貯めておきたいところですがGoではそれはコンテキストと呼ばれる機構で行うのが定石です。context.Context型である必要はないのですが、実行コンテキストを作って各パース処理に渡して回るようにします。

ここではトレース目的のみで作っていますが、変数を書き換えて他の場所からアクセスする、関数定義をしてパーサーを構造化できるようにするといった場合の変数やロジック置き場にもなるかもしれません。

// トレース情報
type TraceInfostruct {
TraceType TraceType
Depthint
Namestring
Pos       *Pos
Resultstring
}

// 実行コンテキスト
type ParseContext[T any]struct {
Traces         []*TraceInfo
Depthint
TraceEnablebool
}

// トレースを整形して出力
func(pc *ParseContext) DumpTraceTo(w io.Writer) {
for _, t :=range pc.Traces {
switch t.TraceType {
case Enter:
fmt.Fprintf(w,"%s%s %s at %s\n", strings.Repeat("  ", t.Depth), Enter, t.Name, t.Pos.String())
case EnterMatch:
fmt.Fprintf(w,"%s%s %s at %s -> %s\n", strings.Repeat("  ", t.Depth), Enter, t.Name, t.Pos.String(), t.Result)
case Match:
fmt.Fprintf(w,"%s%s %s => %#v\n", strings.Repeat("  ", t.Depth), Match, t.Name, t.Result)
case NotMatch:
fmt.Fprintf(w,"%s%s %s => %#v\n", strings.Repeat("  ", t.Depth), NotMatch, t.Name, t.Result)
}
}
}

// パーサと変換関数の第一引数に渡すように変える
type Parser[T any]func(*ParseContext, []Token[T]) (consumedint, newTokens []Token[T], errerror)
type Transformer[T any]func(pctx *ParseContext, src []Token[T]) (converted []Token[T], errerror)
funcTrace[Tany](namestring, p Parser[T]) Parser[T] {
returnfunc(pctx *ParseContext, tokens []Token[T]) (int, []Token[T],error) {
var pos *Pos
if pctx.TraceEnable {
iflen(tokens) >0 {
pos = tokens[0].Pos
}
pctx.Traces =append(pctx.Traces, &TraceInfo{
TraceType: Enter,
Depth:     pctx.Depth,
Name:      name,
Pos:       pos,
})
pctx.Depth++
}
traceIndex :=len(pctx.Traces)
consumed, newTokens, err := p(pctx, tokens)
if pctx.TraceEnable {
tt := Match
if err !=nil {
tt = NotMatch
}
var resultstring
if err !=nil {
result = err.Error()
}else {
builder := strings.Builder{}
builder.WriteString("[")
for i, t :=range newTokens {
if i !=0 {
builder.WriteString(", ")
}
fmt.Fprintf(&builder,"%#v", t.Val)
}
builder.WriteString("]")
result = builder.String()
}
pctx.Depth--
iflen(pctx.Traces) == traceIndex {
lastTrace := pctx.Traces[len(pctx.Traces)-1]
if tt == NotMatch {
lastTrace.TraceType = EnterNotMatch
}else {
lastTrace.TraceType = EnterMatch
}
lastTrace.Result = result
}else {
pctx.Traces =append(pctx.Traces, &TraceInfo{
TraceType: tt,
Depth:     pctx.Depth,
Name:      name,
Pos:       pos,
Result:    result,
})
}
}
return consumed, newTokens, err
}
}

すべてのパーサにTraceを付与します。プログラムもデータというLispだったらこんなことしなくてもいいのでしょうけど、多くの言語では必要でしょう。

funcSeq[Tany](labelstring, parsers ...Parser[T]) Parser[T] {
return Trace(label,func(pctx *ParseContext, src []Token[T]) (int, []Token[T],error) {
converted :=make([]Token[T],0,len(parsers))
offset :=0
for _, p :=range parsers {
if offset >=len(src) {
iflen(src) >0 {
return0,nil, NewErrNotMatch(label,"end of tokens", src[0].Pos)
}
return0,nil, NewErrNotMatch(label,"end of tokens",nil)
}
consumed, newTokens, err := p(pctx, src[offset:])
return0, src, err
}
converted =append(converted, newTokens...)
offset += consumed
}
return offset, converted,nil
})
}

funcOr[Tany](labelstring, parsers ...Parser[T]) Parser[T] {
return Trace(label,func(pctx *ParseContext, src []Token[T]) (int, []Token[T],error) {
for _, p :=range parsers {
offset, newTokens, err := p(pctx, src[offset:])
if err ==nil {// マッチ
return offset, newTokens,nil
}elseif errors.Is(err, ErrNotMatch) {
// 回復可能なエラー
continue
}
return offset,nil, err// 回復不能なエラー
}
// どれにもマッチしなかった
return offset,nil, NewErrNotMatch(label,"", src[0].Pos)
})
}

さきほどのDigit()もこうなります

funcDigit() Parser[int] {
return Trace("digit",func(pc *ParseContext, src []Token[int]) (int, []Token[int],error) {
if src[0].Type =="raw" {
t := src[0]
i, err := strconv.Atoi(t.Raw)
if err !=nil {
return0,nil, NewErrNotMatch("integer", fmt.Sprintf("'%s'", t.Raw), src[0].Pos)
}
return1, []Token[int]{{Type:"digit", Pos: t.Pos, Val:int(i)}},nil
}elseif src[0].Type =="digit" {
return1, src[0:1],nil
}
return0,nil, NewErrNotMatch("raw or digit type", src[0].Type, src[0].Pos)
})
}

失敗時と成功時のトレース情報をこんな感じで出力できるようになります。

> expression at 0
  >seq at 0
    > digit at 0 -> [100]
    > operator at 1 -> [0]
    > digit at 2 -> [200]
  <seq =>"[100, 0, 200]"
< expression =>"[300]"
> expression at 0
  >seq at 0
    > digit at 0 -> [100]
    > operator at 1 -> [0]
  !seq =>"not match expected: integer, actual: 'a' at 2"
! expression =>"not match expected: integer, actual: 'a' at 2"

複数のエラーを出力できるようにする

普段プログラムを書いていて、1つのファイルに複数のエラーが登場することはよくあります。先頭のエラーだけ出力して2つ目以降のエラーが出ないと、全体としてどの程度エラーがあるのかわからないと、デバッグが賽の河原の石積みみたいに感じてしまいます。

Print(10)// 小文字printが正しい
fmt.print(20)// 大文字Printが正しい

この場合は1つめでエラーがあっても、2つめは独立した文として解釈してあげると良いですね。

GoのpanicのrecoverみたいなRecoverパーサを作ってみました。特定の要素とマッチするかどうかをまず確認し、問題なければパースをしてマッチしなければ、skipUntilパーサがマッチするまで要素を読み飛ばすという動きをしています。この場合はエラーをreturnで返すのではなく、さきほど作ったパースコンテキストにエラーを貯めておくようにします。

一度パースするのは、Recoverでラップした要素をOrで並べる場合に、「ここがマッチしなければエラーは記録しない」というモードがないとOrがあるたびにエラーが記録されてしまうのを防ぐためです。


funcRecover[Tany](search, body, skipUntil Parser[T]) Parser[T] {
return Trace("recover",func(pc *ParseContext, src []Token[T]) (int, []Token[T],error) {
_, _, err := Trace("precondition-check", search)(pc, src)
if err !=nil {
return0,nil, err
}
consumed, newTokens, err := Trace("process", body)(pc, src)
if err !=nil {
pc.AppendError(err, src[0].Pos)// エラーを蓄積
return Trace("healing",func(pc *ParseContext[T], src []Token[T]) (int, []Token[T],error) {
for i :=range src {
consumed, _, err = skipUntil(pc, src[i:])
if err ==nil {
return i + consumed,nil,nil
}
}
returnlen(src),nil,nil
})(pc, src)
}
return consumed, newTokens,nil
})
}

次のように書くと、「数字、何か、数字」という並びにマッチすると本処理に入り、「数字、演算子、数字」にマッチすればOK、なければ行末記号に飛ぶ、という動きをします。Recoverがないと、単に「マッチしなかった」だけですが、これを書くと、「2つ目が演算子ではなかった」というエラー情報を残しつつ、次のパースを行います。

パズルのようにトレースバックを仕込むよりはデバッグが簡単かな、と。

Recover(
  Seq(Digit(), Any(), Digit(), EOL()),
  Seq(Digit(), Operator(), Digit(), EOL()),
  EOL(),
)

まとめ

ある程度使ってみて「こうしたい」という気持ちが強くなってきたので自作してみたという記録でした。実際に処理系を作ったことがあって「エラー処理の実装わかりにくいわー」という実感を持った人向けに書いているので、わかりにくかったかもしれません。

パーサジェネレータでもパーサコンビネータでも「これが正しい定義の文法」というのを定義して動かす方法は教科書的な説明ではよく見かけますが、ユーザーが間違った入力をしたときにどのように分かりやすい情報を出してガイドするか、パーサーが動かなかったときにどうデバッグするかというところは実際にやってみないと難しいですね。

  • パーサーの実行自体を多段で行えるようにする
  • トレーサーを作っておく

最終的なコードには1バイトも残っていませんが、生成AIでスタートダッシュを決めてアルゴリズムを書くのは良いですね。論文の疑似コードを読み解いて実装するとかそういうところの苦労がだいぶ減りました。自分が使いたい言語のサンプルが得られますし。ただ、今回やったようなチャレンジはいくら指示してもうまく生成されなかったり2つ以上の改善を入れようとしたら片方しか考慮されなかったりして、最終的には最初のコードは捨て去りましたが初速出せるのでこういう使い方は良いですね。この記事はGoを使いましたが、任意の言語でトライできると思います。

自分で作成したパーサコンビネータ上で自分で書いたアプリケーションががりがりドキュメントを処理してくれると、なんというか俺つえー万能感がすごい。

— 渋川よしき (@shibu_jp)September 18, 2024

前回紹介したtakenocoはすごく勉強させてもらった良いライブラリですが、前回も紹介した既存のパーサライブラリと組み合わせだとキャストのコードが増えちゃうのでジェネリクス対応してみたりとか、エラー処理周りのサンプルがなくて使い方がわからなかったりして作りました。文字列を解釈するところからやるのであればヘルパーも多いしtakenocoは使いやすいんじゃないかと思います。

目次

  1. 基本的な改造方針
  2. 実用化に向けて
  3. 基本要素を作る
  4. 実行のトレースできるようにする
    1. 場所情報をエラーに付与する
    2. 実行のトレースをする
  5. 複数のエラーを出力できるようにする
  6. まとめ

カテゴリー

[8]ページ先頭
©2009-2025 Movatter.jp