パーサー・コンビネーター・ライブラリ「takenoco」入門

本ドキュメントでは、Go言語向けのパーサー・コンビネーター・ライブラリ「takenoco」について解説します。

パーサー・コンビネーターとは、小さなパーサー(構文解析器)の関数を組み合わせて目的のパーサーを構築する、パーサーの構成方法です。
プログラミング言語の「高階関数」という仕組みによって比較的容易に実現することができます。

takenoco は、文字列、または、任意の型のスライスをパースし、AST (abstract syntax tree; 抽象構文木) に変換するための基盤と、汎用的な小さなパーサー群、生成規則によるASTの変換機能を提供します。

takenoco のパッケージ

takenoco は以下のパッケージによって構成されます。

github.com/shellyln/takenoco/
├── base/
├── string/
├── object/
└── extra/

• base/:
  型、パーサー基盤および、文字列/任意の型のスライス 共通の汎用的なパーサー群を提供します。
• string/:
  文字列の汎用的なパーサー群を提供します。
• object/:
  任意の型のスライスの汎用的なパーサー群を提供します。
• extra/:
  追加的なパーサー群を提供します。

最小のパーサー

まずは、イメージを掴むために最小のパーサーを作ってみましょう。

package main

import (
    "fmt"
    "log"
    "play.ground/myparser"
)

func main() {
    data, err := myparser.Parse("foobar") // 1) パース対象のテキストを渡しています
    if err != nil {
        log.Fatal(err)
    }

    fmt.Println(data)
}

-- go.mod --
module play.ground

-- myparser/myparser.go --
package myparser

import (
    "errors"
    "strconv"
    . "github.com/shellyln/takenoco/base"    // 2) takenocoの共通機能パッケージ
    . "github.com/shellyln/takenoco/string"  // 3) takenocoの文字列パーサーパッケージ
)

// パースするプログラムまたはドキュメント全体
func program() ParserFn {
    return FlatGroup( // 4) パーサーをグループ化します
                      //    しかし、パース結果のAST構造体は纏めません
		      //    (フラットに複数個返します)
                      //    このケースでは、1 つの ParserFn を返す必要があるため
		      //    グループ化しています
        Start(), // 5) パース対象ドキュメントの開始を表すゼロ幅の言明です
        Trans(   // 6) パーサーでパースした結果を変換関数に渡します
            OneOrMoreTimes(Alpha()), // 7) ASCIIの英字文字を1回以上繰り返します
	                             //    (1文字-1AST構造体となります)
            Concat, // 8) パースした結果のAST構造体を文字列として結合し、
	            //    1つのAST構造体に変換します
        ),
        End(), // 9) パース対象ドキュメントの終端を表すゼロ幅の言明です
    )
}

// パッケージの初期化
var rootParser ParserFn
func init() {
    rootParser = program() // 10) パーサーを構築します
}

// パーサー
func Parse(s string) (string, error) {
    out, err := rootParser(*NewStringParserContext(s)) // 11) パースを実行します
    if err != nil {
        // 12) エラー位置情報をフォーマットします
        pos := GetLineAndColPosition(s, out.SourcePosition, 4)
        return "", errors.New(
            err.Error() +
                "\n --> Line " + strconv.Itoa(pos.Line) +
                ", Col " + strconv.Itoa(pos.Col) + "\n" +
                pos.ErrSource)
    }

    // 13) MatchStatus_Matched ならばパース成功です
    if out.MatchStatus == MatchStatus_Matched {
        return out.AstStack[0].Value.(string), nil
    } else {
        pos := GetLineAndColPosition(s, out.SourcePosition, 4)
        return "", errors.New(
            "Parse failed" +
                "\n --> Line " + strconv.Itoa(pos.Line) +
                ", Col " + strconv.Itoa(pos.Col) + "\n" +
                pos.ErrSource)
    }
}

myparser.go の func program() を見てみましょう。
Start() と End() でドキュメントの開始と終了を表し、その間に英字にマッチするパーサー Alpha() を1回以上の繰り返しにマッチするパーサー OneOrMoreTimes() でラップして挟んでいます。
何となく、正規表現のようだな、と思いませんか？もし、これを正規表現で表すならば、 /(?:^[A-Za-z]+$)/ となるでしょう。

Note
正確には正規表現の非キャプチャーグループ((?:)) と takenoco の FlatGroup() では意味が異なりますが、対比する上での例えとして記載しました。

演習

• The Go Playground で実行してみましょう。上記コード全体をそのまま貼り付けられます。
• 1) の "foobar" を "foobar1" にするとどうなるでしょうか？

汎用的なパーサーの紹介

takenoco では、良く使う基本的・汎用的なパーサーを予め用意しています。ほとんどの場合、これらを組み合わせることで目的のパーサーを構築できるでしょう。

github.com/shellyln/takenoco/base

func Indirect(fn func() ParserFn) 

再帰的な表現をパースする際に使用します。パーサーの呼び出しが循環していると、パーサー構築時にスタックオーバーフローして実行時エラーとなります。防止するために循環参照となるパーサーを Indirect でラップします。
ラップされる関数は構築時にパラメーターを取れないことに注意してください。

func If(b bool, fnT ParserFn, fnF ParserFn) ParserFn

パーサー構築時に条件分岐をします。パーサー実行時ではないことに注意してください。

func Error(msg string) ParserFn

呼び出されるとパース失敗となります。パース失敗となるとバックトラックされません。後述の First() の引数の最後のアイテムとして挿入することで、文法的に許されないトークンが現れたときに、エラー発生場所とエラーメッセージをユーザーに示すことができます。
文法的にバックトラックの余地があるところに挿入するとパース出来るはずなのに失敗となってしまいます。挿入場所はよく検討してください。

func Unmatched() ParserFn

呼び出されるとアンマッチとなります。バックトラックが発生するので、パース全体としてはまだ成功する可能性があります。

func Zero(astsToInsert ...Ast) ParserFn

ゼロ幅 (ソース位置を進めない) の言明です。呼び出されると必ずマッチします。引数のAST構造体 (複数) をパース結果に追加します。

func Start() ParserFn

パース対象ソースの先頭にマッチするゼロ幅の言明です。

func FlatGroup(children ...ParserFn) ParserFn

引数のパーサーをグループ化し、1つのパーサーにします。各パーサーが出力する結果のAST構造体は、フラットに (複数) パース結果に追加されます。

func Group(children ...ParserFn) ParserFn

引数のパーサーをグループ化し、1つのパーサーにします。各パーサーが出力する結果のAST構造体は、1つのAST構造体の Value としてパース結果に追加されます。 Value の型はAST構造体のスライスとなります。

func First(children ...ParserFn) ParserFn

引数のパーサーのうち、最初にマッチしたものにマッチします。

func LookAhead(children ...ParserFn) ParserFn

ゼロ幅 (ソース位置を進めない) の「先読み」言明です。引数のパーサーのすべてに順番にマッチする場合マッチし、ソース位置を元に戻します。

func LookAheadN(children ...ParserFn) ParserFn

ゼロ幅 (ソース位置を進めない) の「否定先読み」言明です。引数のパーサーの並びにマッチしない場合にマッチし、ソース位置を元に戻します。

func LookBehind(minN, maxN int, children ...ParserFn) ParserFn

ゼロ幅 (ソース位置を進めない) の「後読み」言明です。引数のパーサーのすべてに順番にマッチする場合マッチし、ソース位置を元に戻します。マッチはソース位置を現在位置から minN 戻して試行します。マッチしない場合は maxN まで+1ずつ進めた位置から試します。マッチの終端位置が元の位置と一致するかはチェックされません。

func LookBehindN(minN, maxN int, children ...ParserFn) ParserFn

ゼロ幅 (ソース位置を進めない) の「否定後読み」言明です。引数のパーサーの並びにマッチしない場合にマッチし、ソース位置を元に戻します。マッチはソース位置を現在位置から minN 戻して試行します。マッチしない場合は maxN まで+1ずつ進めた位置から試します。マッチの終端位置が元の位置と一致するかはチェックされません。

func Repeat(times Times, children ...ParserFn) ParserFn

type Times struct {
    Min int
    Max int
}

引数のパーサーの並びに Min 回以上、最大 Max 回マッチします。Max 回を超えてマッチすることが出来ても、Max 回で打ち切ります。
Min, Max にマイナスを指定した場合は、それぞれ回数を制限しません。

func Once(children ...ParserFn) ParserFn

引数のパーサーの並びに 1 回マッチします。 Once() でラップしない場合と等価ですが、以下の ZeroOrOnce, ZeroOrMoreTimes, ZeroOrMoreTimes, OneOrMoreTimes と語彙を揃える目的で設けています。
Repeat(Times{Min: 1, Max: 1}, ...) と等価です。

func ZeroOrOnce(children ...ParserFn) ParserFn

引数のパーサーの並びに 0～1 回マッチします。
Repeat(Times{Min: 0, Max: 1}, ...) と等価です。

func ZeroOrMoreTimes(children ...ParserFn) ParserFn

引数のパーサーの並びに 0 回以上マッチします。
Repeat(Times{Min: 0, Max: -1}, ...) と等価です。

func OneOrMoreTimes(children ...ParserFn) ParserFn

引数のパーサーの並びに 1 回以上マッチします。
Repeat(Times{Min: 1, Max: -1}, ...) と等価です。

func Trans(child ParserFn, tr ...TransformerFn) ParserFn

引数 child でマッチした場合、結果のAST構造体スライスを変換関数で書き換えます。

Warning
変換関数では、引数で与えられたAST構造体スライスの値を変更してはなりません。
引数で与えられたAST構造体スライスをそのまま返すことは許されます。

github.com/shellyln/takenoco/string

func Any() ParserFn

任意の (すべての) 1 文字にマッチします。

func End() ParserFn

パース対象ソースの終端にマッチするゼロ幅の言明です。

func Seq(s string) ParserFn

引数の文字列にマッチします。

func SeqI(s string) ParserFn

引数の文字列にマッチします。大文字小文字の違いを無視します。

func CharRange(cr ...RuneRange) ParserFn
type RuneRange struct {
    Start rune
    End rune
}

引数の文字コード範囲のいずれかに一致すればマッチします。

func CharRangeN(cr ...RuneRange) ParserFn

引数の文字コード範囲のいずれにも一致しなければマッチします。

func CharClass(cc ...string) ParserFn

引数の文字列のいずれかに一致すればマッチします。

func CharClassN(cc ...string) ParserFn

引数の文字列のいずれにも一致しなければマッチします。

func CharClassFn(fn func(c rune) bool) ParserFn

関数で判定する 1 文字に一致すればマッチします。

func Whitespace() ParserFn

HT, LF, VT, FF, CR, SP, NEL, NBSP 1 文字にマッチします。

func WhitespaceNoLineBreak() ParserFn

HT, SP, NBSP 1 文字にマッチします。

func LineBreak() ParserFn

LF, VT, FF, CR, NEL 1 文字にマッチします。

func Alpha() ParserFn

/[A-Za-z]/ 1 文字にマッチします。

func Number() ParserFn

/[0-9]/ 1 文字にマッチします。

func Alnum() ParserFn

/[0-9A-Za-z]/ 1 文字にマッチします。

func BinNumber() ParserFn

/[0-1]/ 1 文字にマッチします。

func OctNumber() ParserFn

/[0-7]/ 1 文字にマッチします。

func HexNumber() ParserFn

/[0-9A-Fa-f]/ 1 文字にマッチします。

func WordBoundary() ParserFn 

ゼロ幅 (ソース位置を進めない) の言明です。 /[0-9A-Za-z_$]/ を単語構成文字として、単語構成文字と (非単語構成文字 または ソースの先頭 または ソースの終端) の間にマッチします。

github.com/shellyln/takenoco/object

func Any() ParserFn

任意の (すべての) 1 個の値にマッチします。

func End() ParserFn

パース対象ソースの終端にマッチするゼロ幅の言明です。

func Seq(seq ...interface{}) ParserFn

引数の値の並びにマッチします。

func ObjClass(oc ...interface{}) ParserFn

引数の値のいずれかに一致すればマッチします。

func ObjClassN(oc ...interface{}) ParserFn

引数の値のいずれにも一致しなければマッチします。

func ObjClassFn(fn func(c interface{}) bool) ParserFn

関数で判定する値に一致すればマッチします。

github.com/shellyln/takenoco/extra

func BinaryNumberStr() ParserFn

2 進数の文字列に一致します。プリフィックス (0b 等) は含みません。桁を区切るための _ を含むことでができます。

func OctalNumberStr() ParserFn

8 進数の文字列に一致します。プリフィックス (0o 等) は含みません。桁を区切るための _ を含むことでができます。

func HexNumberStr() ParserFn

16 進数の文字列に一致します。プリフィックス (0x 等) は含みません。桁を区切るための _ を含むことでができます。

func IntegerNumberStr() ParserFn

正負および 0 の整数値を表す文字列に一致します。 +, - の符号は必須ではありません。桁を区切るための _ を含むことでができます。

func FloatNumberStr() ParserFn

小数点を含む数値、または、10 進指数表記を含む数値を表す文字列に一致します。桁を区切るための _ を含むことでができます。

func NumericStr() ParserFn

整数、小数点を含む数値、または、10 進指数表記を含む数値を表す文字列に一致します。桁を区切るための _ を含むことでができます。

func AsciiIdentifierStr() ParserFn

ASCIIの範囲内の識別子を表す文字列に一致します。1 文字目は /[A-Za-z_$]/ 、2 文字目以降は /[0-9A-Za-z_$]/ です。

func UnicodeIdentifierStr() ParserFn

Unicodeの識別子を表す文字列に一致します。1 文字目は {ID_Start, _, $} 、2 文字目以降は {ID_Continue, $, U+200C, U+200D} です。

func UnicodeWordBoundary() ParserFn

ゼロ幅 (ソース位置を進めない) の言明です。 {ID_Continue, $, U+200C, U+200D} を単語構成文字として、単語構成文字と (非単語構成文字 または ソースの先頭 または ソースの終端) の間にマッチします。

func DateStr() ParserFn

ISO 8601 拡張形式日付書式の文字列 (yyyy-MM-dd) に一致します。

func DateTimeStr() ParserFn

ISO 8601 拡張形式日付時刻書式の文字列 (yyyy-MM-ddThh:mmZ～yyyy-MM-ddThh:mm:ss.fffffffffZ, yyyy-MM-ddThh:mm+00:00～yyyy-MM-ddThh:mm:ss.fffffffff+00:00) に一致します。

func TimeStr() ParserFn

ISO 8601 拡張形式時刻書式の文字列 (hh:mm～hh:mm:ss.fffffffff) に一致します。

汎用的な変換関数の紹介

Trans() で使用する汎用的な変換関数も予め用意しています。

github.com/shellyln/takenoco/base

func Erase(_ ParserContext, asts AstSlice) (AstSlice, error)

パースされた結果を捨てます。

func TransformError(s string) TransformerFn

エラーを発生させます。

func GroupingTransform(_ ParserContext, asts AstSlice) (AstSlice, error)

パースされた結果を 1 つのAST構造体に纏めます。Value の型はAST構造体のスライスとなります。

func ToSlice(ctx ParserContext, asts AstSlice) (AstSlice, error)

パースされた結果のAST構造体 (複数) について、それぞれの Value を取得し、スライスにします。
型は NewObjectParserContext(slice) で渡したソースと同じ型となります。
文字列パーサーでは動作しません。

func SetOpCodeAndClassName(opcode AstOpCodeType, name string) TransformerFn

結果のAST構造体スライスの 0 番目の OpCode と ClassName を書き換えます。

func SetOpCode(opcode AstOpCodeType) TransformerFn

結果のAST構造体スライスの 0 番目の OpCode を書き換えます。

func ChangeClassName(name string) TransformerFn

結果のAST構造体スライスの 0 番目の ClassName を書き換えます。

func SetValue(typ AstType, v interface{}) TransformerFn

結果のAST構造体スライスの 0 番目の Type と Value を書き換えます。

func Prepend(ast Ast) TransformerFn

結果のAST構造体スライスの先頭に、引数のAST構造体を追加します。

func Push(ast Ast) TransformerFn

結果のAST構造体スライスの末尾に、引数のAST構造体を追加します。

func Pop(_ ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライスの末尾から 1 個のAST構造体を取り除きます (スライスの長さを -1 します)。

func Exchange(_ ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライスの asts[len(asts)-2] と asts[len(asts)-1] を入れ替えます。

func Roll(n int) TransformerFn

結果のAST構造体スライスの中身を n 個ずらします。

github.com/shellyln/takenoco/string

func Concat(_ ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライス (複数) について、それぞれの Value を取得し、文字列を結合します。
Value が文字列ではない場合はエラーとなります。

func Trim(ctx ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライス (複数) について、それぞれの Value を取得し、文字列を結合し、
文字列の開始と終了から連続する空白を除去します。
Value が文字列ではない場合はエラーとなります。

func TrimStart(ctx ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライス (複数) について、それぞれの Value を取得し、文字列を結合し、
文字列の開始から連続する空白を除去します。
Value が文字列ではない場合はエラーとなります。

func TrimEnd(ctx ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライス (複数) について、それぞれの Value を取得し、文字列を結合し、
文字列の終了から連続する空白を除去します。
Value が文字列ではない場合はエラーとなります。

func ParseIntRadix(base int) TransformerFn

結果のAST構造体スライス (複数) について、それぞれの Value を取得し、文字列を結合し、基数を指定して int64 に変換します。
Value が文字列ではない場合、および、変換できない場合はエラーとなります。

func ParseInt(ctx ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライス (複数) について、それぞれの Value を取得し、文字列を結合し、基数 10 で int64 に変換します。
Value が文字列ではない場合、および、変換できない場合はエラーとなります。

func ParseUintRadix(base int) TransformerFn

結果のAST構造体スライス (複数) について、それぞれの Value を取得し、文字列を結合し、基数を指定して uint64 に変換します。
Value が文字列ではない場合、および、変換できない場合はエラーとなります。

func ParseUint(ctx ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライス (複数) について、それぞれの Value を取得し、文字列を結合し、基数 10 で uint64 に変換します。
Value が文字列ではない場合、および、変換できない場合はエラーとなります。

func ParseFloat(ctx ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライス (複数) について、それぞれの Value を取得し、文字列を結合し、 float64 に変換します。
Value が文字列ではない場合、および、変換できない場合はエラーとなります。

func RuneFromInt(ctx ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライスの 0 番目の Value を int64 から rune に変換します。
Value が int64 ではない場合、panicします。

func IntFromRune(ctx ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライスの 0 番目の Value を rune から int64 に変換します。
Value が rune ではない場合、panicします。

func StringFromInt(ctx ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライスの 0 番目の Value を int64 から rune に変換し、さらに string に変換します。
Value が int64 ではない場合、panicします。

func StringFromRune(ctx ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライスの 0 番目の Value を rune から string に変換します。
Value が rune ではない場合、panicします。

github.com/shellyln/takenoco/extra

func ParseDate(ctx ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライスの [len(asts) - 1] 番目の Value を ISO8061拡張形式の日付文字列として、 time.Time に変換します。タイムゾーンは UTC となります。
Value が string ではない場合、panicします。

func ParseDateTime(ctx ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライスの [len(asts) - 1] 番目の Value を ISO8061拡張形式の日付時刻文字列として、 time.Time に変換します。タイムゾーンは UTC となります。
Value が string ではない場合、panicします。

func ParseTime(ctx ParserContext, asts AstSlice) (AstSlice, error)

結果のAST構造体スライスの [len(asts) - 1] 番目の Value を ISO8061拡張形式の時刻文字列として、 time.Time に変換します。日付部分は Unix epoch となります。タイムゾーンは UTC となります。
Value が string ではない場合、panicします。

生成規則によるパース結果 AST の変換

「汎用的な変換関数の紹介」の章では、ある固定的で小さななパース結果に対して、文字列加工や文字列から数値への変換等の単純な変換を行う関数群を紹介しました。ユーザー定義の変換関数を用いればライブラリで提供していない型変換も行うことができます。

しかし例えば、四則演算の式を演算子の優先順位に従って評価する順にする、といった複数のトークンに跨る変換関数を都度作成するのは手間が掛かります。
takenoco では、そのような変換を「生成規則」と呼ばれるルールに従って行う仕組みを予め用意しています。

この章では、takenoco リポジトリ内のサンプル Formula to RPN converter を用いて、生成規則の適用方法を解説します。
Formula to RPN converter は、整数の四則演算式を逆ポーランド記法 (RPN) の式に変換します。

パーサー

パーサーは、「最小のパーサー」の章の応用です。この例が「最小のパーサー」と異なるのは、汎用的なパーサーを組み合わせたパーサーを関数として定義して呼び出している点です。このように文法的な塊 (「終端記号」、「非終端記号」) を目安に関数を定義すると分かりやすくなります。

生成規則の適用は、前章「汎用的な変換関数の紹介」の関数群と同じく Trans() を用いて行います。

torpn.go

// (略)

// 括弧に囲まれた式
func groupedExpresion() ParserFn {
    return FlatGroup(
        erase(CharClass("(")), // 1) 括弧は結果に含めないように erase で除去します
                               //    括弧は生成規則で変換する方法も取れますが、
                               //    この例ではパーサー側で処理しています。
        First(
            FlatGroup(
                erase(sp0()),
                expression(), // 2) 生成規則を適用済みの式です
                erase(CharClass(")")),
                erase(sp0()),
            ),
            Error("Error in grouped expression"),
        ),
    )
}

// 生成規則を適用する前の式
func expressionInner() ParserFn {
    return FlatGroup(
        ZeroOrMoreTimes(unaryOperator()), // 3) 単項演算子
        First(
            simpleExpression(),         // 4) 括弧を含まない式
            Indirect(groupedExpresion), // 5) 括弧に囲まれた式
            Error("Value required"),
        ),
        ZeroOrMoreTimes(
            binaryOperator(), // 6) 二項演算子
            First(
                FlatGroup(
                    ZeroOrMoreTimes(unaryOperator()),
                    First(
                        simpleExpression(),
                        Indirect(groupedExpresion),
                    ),
                ),
                Error("Error in the expression after the binary operator"),
            ),
        ),
    )
}

// 式に生成規則を適用する
func expression() ParserFn {
    return Trans( // 7) 生成規則の適用にも Trans() を用います
        expressionInner(),
        formulaProductionRules(), // 8) 生成規則を適用する変換関数です
    )
}

// プログラム全体
func program() ParserFn {
    return FlatGroup(
        Start(),
        erase(sp0()),
        expression(),
        End(),
    )
}

// (略)

生成規則

生成規則を用いた変換関数は、優先順位毎に生成規則のマッチ条件と小さな変換関数を作成しておき、 ProductionRule() を呼び出す (19)) ことで構築することができます。

式や文の構文解析では、多くの場合、AST (abstract syntax tree; 抽象構文木) と呼ばれるツリー構造に変換します。
takenoco のパース結果は、AST構造体のスライスとなりますが、この構造体の 1 要素は配下にツリー構造を持てる形式となっています。
しかし、この例では RPN のトークン列に変換するのみですので、生成規則に対する変換関数 (transformUnaryOp, transformBinaryOp) 内で、ツリー構造を取らずにスライスを水平方向に伸ばしています。

precedence.go

// (略)

// 優先順位 3 の生成規則 (単項前置演算子)
var expressionRule3 = Precedence{ // 1) Precedence構造体に属性情報を設定します
    Rules: []ParserFn{ // 2) 生成規則をスライスとして列挙します
                       //    これにより同じ優先順位内で複数の生成規則を適用できます
        Trans(
            FlatGroup( // 3) 生成規則のマッチ条件をパーサーとして記述します
	               //    (objectパーサーです)
                       //    生成文法:
                       //      (Expression -> UnaryOperator Expression)
                       //      (Expression -> Number)
                isOperator("UnaryOperator", []string{"-"}),
                anyOperand(),
            ),
            transformUnaryOp, // 4) 変換ルールを変換関数として記述します
        ),
    },
    Rtol: true, // 5) 規則は右から左の順にスキャンして適用します (デフォルトは左から右)
}

// 優先順位 2 の生成規則 (乗除算の二項演算子)
var expressionRule2 = Precedence{
    Rules: []ParserFn{
        Trans(
            FlatGroup( // 6) 生成規則のマッチ条件をパーサーとして記述します
	               //    (objectパーサーです)
                       //    生成文法:
                       //      (Expression -> Expression BinaryOperator Expression)
                       //      (Expression -> Number)
                anyOperand(),
                isOperator("BinaryOperator", []string{"*", "/"}),
                anyOperand(),
            ),
            transformBinaryOp, // 7) 変換ルールを変換関数として記述します
        ),
    },
}

// 優先順位 1 の生成規則 (加減算の二項演算子)
var expressionRule1 = Precedence{
    Rules: []ParserFn{
        Trans(
            FlatGroup( // 8) 生成規則のマッチ条件をパーサーとして記述します
	               //    (objectパーサーです)
                       //    生成文法:
                       //      (Expression -> Expression BinaryOperator Expression)
                       //      (Expression -> Number)
                anyOperand(),
                isOperator("BinaryOperator", []string{"+", "-"}),
                anyOperand(),
            ),
            transformBinaryOp, // 9) 変換ルールを変換関数として記述します
        ),
    },
}

// 単項前置演算子の変換ルール
func transformUnaryOp(ctx ParserContext, asts AstSlice) (AstSlice, error) {
    switch asts[1].Type {
    case AstType_Int:
        // 10) オペランドが Number の場合は、値に符号を適用します
        opcode := asts[0].Value.(string)
        op1 := asts[1].Value.(int64)

        var v int64
        switch opcode {
        case "-":
            v = -op1
        }

        return AstSlice{{
            Type:      AstType_Int,
            ClassName: "Number",
            Value:     v,
        }}, nil
    case AstType_ListOfAst:
        // 11) オペランドが式の場合には、式の末尾に演算子を追加します
        ret := asts[1].Value.(AstSlice)
        ret = append(ret, asts[0]) // 12) スライスを水平方向に伸ばします
        return AstSlice{{
            Type:      AstType_ListOfAst,
            ClassName: "List",
            Value:     ret,
        }}, nil
    default:
        return nil, errors.New("Cannot apply unary - operator")
    }
}

// 二項演算子の変換ルール
func transformBinaryOp(ctx ParserContext, asts AstSlice) (AstSlice, error) {
    // 13) オペランドと演算子の登場順を [0, 1, 2] から [0, 2, 1] に入れ替えます
    opcode := asts[1].Value.(string)
    ret := make(AstSlice, 0, 3)

    switch asts[0].Type {
    case AstType_Int:
        // 14) スライスを水平方向に伸ばします
        ret = append(ret, asts[0])
    case AstType_ListOfAst:
        // 15) スライスを水平方向に伸ばします
        ret = append(ret, asts[0].Value.(AstSlice)...)
    default:
        return nil, errors.New("Cannot apply binary " + opcode + " operator")
    }

    switch asts[2].Type {
    case AstType_Int:
        // 16) スライスを水平方向に伸ばします
        ret = append(ret, asts[2])
    case AstType_ListOfAst:
        // 17) スライスを水平方向に伸ばします
        ret = append(ret, asts[2].Value.(AstSlice)...)
    default:
        return nil, errors.New("Cannot apply binary " + opcode + " operator")
    }

    ret = append(ret, asts[1])

    return AstSlice{{
        Type:      AstType_ListOfAst,
        ClassName: "List",
        Value:     ret,
    }}, nil
}

// 生成規則の優先順位を定義します
var precedences = []Precedence{
    expressionRule3, // 18) 添字が小さい方から優先されます
    expressionRule2,
    expressionRule1,
}

// 生成規則の変換関数を構築します
func formulaProductionRules() TransformerFn {
    return ProductionRule( // 19) 生成規則の変換関数を返します
        precedences, // 20) 優先順位順の生成規則です

        // 20) すべての生成規則の適用結果が満たすべきパターンをパーサーとして記述します
        //     ここでは、1 つの任意のAST構造体に変換されなければならない、と定義しています
        //     生成文法:
        //       (S -> Expression)
        FlatGroup(Start(), objparser.Any(), objparser.End()),
    )
}

Note
幾つかのヘルパー関数をパッケージ内で定義しています。 (isOperator, anyOperand 等)

演習

• 剰余 (%) 、ビット積 (&) 、ビット和 (|) 演算子を追加してみましょう。

次のステップ

その他のサンプルを確認しましょう。

• CSV parser
• Formula parser
• Formula to RPN converter
• Loose JSON + TOML parsers
  • JSON parser
  • TOML parser
  • Live demo (Loose JSON | TOML normalizer)
• Dust - toy scripting language
  • Parsers
  • Production rules