秋のブログ週間 6本目です。
夏休みの自由研究でパーサーコンビネータをもっと身近にするという記事でパーサーコンビネータを使ってみる記事を書きました。せっかくなので作ってみたくなったのでチャレンジしてみました。出来上がったライブラリは以下のところにあります。ただ、要件が変わると欲しい機能も変わってくるし、どんなケースにもマッチするライブラリを作るのは難しいと思うので、規制のライブラリを使うのではなく、自分の用途に合わせて作れるようになった方が良いのかなという気がします。
とりあえず作ってみるには次のようにClaude.aiに次のようにタイプすればざっと作ってくれます。
長いので全部は貼り付けませんが（各自実行してみてください）、こんな感じで使えるコードが生成されました。
func main() {
digit := Digit()
result, rest, err := digit("123")
charA := Char('a')
result, rest, err := charA("abc")
digits := Many(Digit())
results, rest, err := digits("123abc")
}
|
これはとてもシンプルです。生成されたパーサーに文字列を渡すと、そのパーサーが解釈した結果と、残りの文字列を返します。Digit()は1文字の数値にマッチします。Char()は特定の文字です。このプリミティブなパーサを受け取ってパーサーを返す関数もいくつか実装されました。ここではMany()しか使われていませんが、以下の3つも生成されました。
Many(): 指定された1このパーサーをマッチしなくなるまで繰り返し適用するSequence(): パーサーを2つ引数で受けとり、その順序でマッチするかしなければエラーを返すChoice(): 指定された複数のパーサーのうち、1つにマッチしたらそれを返す
パーサーを組み合わせてパーサーを生成する関数を使うことで、任意の文字列にマッチする関数ができるというわけです。パーサーを組み合わせるのでパーサーコンビネータと呼ばれます。
ここを出発点として、実用的なパーサーコンビネータのAPIを考えてみます。
基本的な改造方針
自動生成されたものは1つの文字列からトークン化を行う由緒正しいパーサー（というよりもトークナイザー）用途には問題ないですが、前回同様、既成のパーサーの作ったトークンを解釈する用途で使いたいのでそちら方面にフォーカスします。
前回の記事で書いたように、小さいパーサーを組み合わせて実行するだけではなく、多段で重ねて実行できる方が、その構文木を処理するコードもその上に載せられて便利です。また、わかりやすいエラー処理も載せられます。たとえば、次のような式があったとします。いろんな形式の数値を扱いたいとします。
この場合に、全部のバリエーションをパーサー上で扱うのでも良いですが、全部をひとまず数字っぽいトークンとして扱って、実際の値の解釈はあとでやれる方が便利です。
- ゆるい構文処理パーサと厳しい数値パーサを分けて作れる
- より分かりやすいエラーメッセージが出しやすい
パーサーはちょっと複雑な文法を実装しようとするとすぐに長大な定義になってしまいます。これを分割する方法があるというのは便利です。パーサーコンビネータはパーサーを組み立てるので、1つ1つのパーサ関数自体は小さく分離できるのですが、最終的なパーサーはでかいルール定義になるので、実行時の動きを追いかけるのは大変です。
上記のコードは2進数なのに2を使ったり、8進数なのに9を使っているのでエラーにすべきです。最初からSequence(Char('0'), Char('b'), Choice(Char('0'), Char('1')))というガチガチのルールで書いてしまうと、バックトラックが発生して「入力文字列はマッチしなかった」しか結果がわかりません。よく観察するとルールとマッチしないというのがようやくわかる感じです。ゆるいルールで「数値っぽいもの」を一度解釈して、から後から細かく解釈して「2進数っぽいが数値が範囲外」という情報を出したほうが人間には優しいです。なるべくバックトラックさせない動きにした方が人間が解釈するメンタルモデルに近い動きになると思います。
実用化に向けて
途中経過ではパース中に変換した内容など、多様な情報を扱う必要がありますが、アプリケーションによって扱う情報は異なるため、ジェネリクスを使って任意の追加情報をもてるような、次のような形式のトークン列を受け取って、それを変換していくというコードにします。
type Token[T any] struct {
Type string
Raw string
Val T
}
|
パーサーは次のような形式の関数とします。
type Parser[T any]
func(src []Token[T]) (consumed int, newTokens []Token[T], err error)
|
返すエラーで後続の処理が変える必要があるかと思うので追加しておきます。
var (
ErrNotMatch = fmt.Errorf("not match")
ErrCritical = fmt.Errorf("critical error")
)
|
トークン列を受け取り、解釈した数を最初の返り値として返します。新たに生成されたトークンやエラー情報を返します。これを連続して実行していくことで期待されるトークン列に変換していきます。次のコードはRawに入っている文字列が数字だったらそれに変換するするパーサです。
func Digit(src []Token[int]) Parser[int] {
if src[0].Type == "raw" {
t := src[0]
i, err := strconv.Atoi(t.Raw)
if err != nil {
return 0, nil, ErrNotMatch
}
return 1, []Token[int]{{Type: "digit", Pos: t.Pos, Val: int(i)}}, nil
} else if src[0].Type == "digit" {
return 1, src[0:1], nil
}
return 0, nil, ErrNotMatch
}
|
基本要素を作る
生成AIが作ってくれた要素のうち、シーケンス、複数の候補のマッチは最低限必要です。リピート系は1つ以上とかいろいろ必要になるのでとりあえず後回し。あと、マッチした候補を置き換える変換処理も実装します。
func Seq[T any](parsers ...Parser[T]) Parser[T] {
return func(src []Token[T]) (int, []Token[T], error) {
converted := make([]Token[T], 0, len(parsers))
offset := 0
for _, p := range parsers {
if offset >= len(src) {
return 0, nil, ErrNotMatch
}
consumed, newTokens, err := p(src[offset:])
if err != nil {
return 0, src, ErrNotMatch
}
converted = append(converted, newTokens...)
offset += consumed
}
return offset, converted, nil
}
}
func Or[T any](parsers ...Parser[T]) Parser[T] {
return func(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
} else if errors.Is(err, ErrNotMatch) {
continue
}
return offset, nil, err
}
return offset, nil, ErrNotMatch,
}
}
type Transformer[T any] func(src []Token[T]) (converted []Token[T], err error)
func Trans[T any](parser Parser[T], tf Transformer[T]) Parser[T] {
return func(src []Token[T]) (int, []Token[T], error) {
consumed, newTokens, err := parser(src)
if err != nil {
return 0, src, err
}
result, err := tf(newTokens)
if err != nil {
return 0, src, err
}
return consumed, result, nil
}
}
|
ここまでできると、さきほどのDigit()と組みわせて簡単な数式とその処理ができるようになります。
func Operator(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 {
return 1, []Token[int]{{Type: "operator", Raw: t.Raw}}, nil
}
return 0, nil, ErrCritical
} else if src[0].Type == "operator" {
return 1, nil, nil
}
return 0, nil, ErrNotMatch
}
func Expression() Parser[int] {
expressionTransform := func(src []Token[int]) (converted []Token[int], err error) {
var result int
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
}
return []Token[int]{{Type: "digit", Val: result}}, nil
}
return Trans(
Seq(Digit, Operator, Digit),
expressionTransform)
}
|
func Evaluate[T any](src []Token[T], parser Parser[T]) (result []T, remained []Token[T], err error) {
consumed, newTokens, err := parser(pctx, src)
if err != nil {
return nil, nil, err
}
remained = src[consumed:]
result = make([]T, len(newTokens))
for i, t := range newTokens {
result[i] = t.Val
}
return result, remained, nil
}
func EvaluateWithRawTokens[T any](src []string, parser Parser[T]) (result []T, remained []Token[T], err error) {
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())
|
実行のトレースできるようにする
数式のコードは以下のようになっていましたが、ErrNotMatchが帰ってきたところで、数字のところに文字が入ってしまったのか、演算子が不正だったのか、トークンが足りなかったのかどこまで処理が正しく進んだのか情報がありません。ユニットテストで小さくコードを育てていっても、いざリファクタリングしてちょっとでもエラーが出てしまうと何が起きているのかわからなくなってお手上げです。全部のテストを捨ててまた積み上げをしていかないといけなくなります。
Seq(Digit, Operator, Digit)
|
場所情報をエラーに付与する
トークンに場所情報を付与します。エラー発生時にはエラーにその情報を付与するようにします。元のパーサーが作ってくれるASTには行と列の情報が載っているかもしれません。それを付与しておけば元のソースの位置が特定できます。ない場合はトークンのインデックスを代わりに使う必要があるでしょう。
type Pos struct {
Line int
Col int
Index int
}
type Token[T any] struct {
:
Pos *Pos
}
func NewErrNotMatch(expected, actual string, pos *Pos) error {
var err error
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 ParseError struct {
Parent error
Pos *Pos
}
|
実行のトレースをする
連続した要素のSeq()の要素の途中で止まった、ぐらいであればトークンの位置情報だけあれば良いですが、Or()や要素のリピート（まだ作ってないですが）を駆使してくると、ここでマッチするはずだったのだが、マッチせずに期待しないパーサの実行が行われたみたいなことが起きたりします。例えば、 10 * aという掛け算のつもりが、10がなくて、aという変数のポインタ演算になったり・・・みたいな。特にパーサのバグを見つける場合にはどこが実行されたのかのログが見たくなります。
トレースのログはスレッドローカル的な場所に貯めておきたいところですがGoではそれはコンテキストと呼ばれる機構で行うのが定石です。context.Context型である必要はないのですが、実行コンテキストを作って各パース処理に渡して回るようにします。
ここではトレース目的のみで作っていますが、変数を書き換えて他の場所からアクセスする、関数定義をしてパーサーを構造化できるようにするといった場合の変数やロジック置き場にもなるかもしれません。
type TraceInfo struct {
TraceType TraceType
Depth int
Name string
Pos *Pos
Result string
}
type ParseContext[T any] struct {
Traces []*TraceInfo
Depth int
TraceEnable bool
}
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]) (consumed int, newTokens []Token[T], err error)
type Transformer[T any] func(pctx *ParseContext, src []Token[T]) (converted []Token[T], err error)
|
func Trace[T any](name string, p Parser[T]) Parser[T] {
return func(pctx *ParseContext, tokens []Token[T]) (int, []Token[T], error) {
var pos *Pos
if pctx.TraceEnable {
if len(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 result string
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--
if len(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だったらこんなことしなくてもいいのでしょうけど、多くの言語では必要でしょう。
func Seq[T any](label string, 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) {
if len(src) > 0 {
return 0, nil, NewErrNotMatch(label, "end of tokens", src[0].Pos)
}
return 0, nil, NewErrNotMatch(label, "end of tokens", nil)
}
consumed, newTokens, err := p(pctx, src[offset:])
return 0, src, err
}
converted = append(converted, newTokens...)
offset += consumed
}
return offset, converted, nil
})
}
func Or[T any](label string, 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
} else if errors.Is(err, ErrNotMatch) {
continue
}
return offset, nil, err
}
return offset, nil, NewErrNotMatch(label, "", src[0].Pos)
})
}
|
さきほどのDigit()もこうなります
func Digit() 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 {
return 0, nil, NewErrNotMatch("integer", fmt.Sprintf("'%s'", t.Raw), src[0].Pos)
}
return 1, []Token[int]{{Type: "digit", Pos: t.Pos, Val: int(i)}}, nil
} else if src[0].Type == "digit" {
return 1, src[0:1], nil
}
return 0, 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つ目以降のエラーが出ないと、全体としてどの程度エラーがあるのかわからないと、デバッグが賽の河原の石積みみたいに感じてしまいます。
この場合は1つめでエラーがあっても、2つめは独立した文として解釈してあげると良いですね。
GoのpanicのrecoverみたいなRecoverパーサを作ってみました。特定の要素とマッチするかどうかをまず確認し、問題なければパースをしてマッチしなければ、skipUntilパーサがマッチするまで要素を読み飛ばすという動きをしています。この場合はエラーをreturnで返すのではなく、さきほど作ったパースコンテキストにエラーを貯めておくようにします。
一度パースするのは、Recoverでラップした要素をOrで並べる場合に、「ここがマッチしなければエラーは記録しない」というモードがないとOrがあるたびにエラーが記録されてしまうのを防ぐためです。
func Recover[T any](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 {
return 0, 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
}
}
return len(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を使いましたが、任意の言語でトライできると思います。
前回紹介したtakenocoはすごく勉強させてもらった良いライブラリですが、前回も紹介した既存のパーサライブラリと組み合わせだとキャストのコードが増えちゃうのでジェネリクス対応してみたりとか、エラー処理周りのサンプルがなくて使い方がわからなかったりして作りました。文字列を解釈するところからやるのであればヘルパーも多いしtakenocoは使いやすいんじゃないかと思います。