Goで数式パーサーを作る：構文解析とASTの仕組み

1 + 2 * 3を計算すると、答えは7になります。

この式をプログラムで計算するには、入力された文字列から数字や演算子を読み取り、「掛け算の結果に1を足す」という構造を組み立てる必要があります。

そのための処理が構文解析です。解析した式の構造は、AST（抽象構文木）という木構造で表せます。

この記事では、Goで四則演算のパーサーを作りながら、文字列が計算結果になるまでの仕組みを説明します。扱うのは、四則演算・括弧・小数・単項の符号です。

コードは処理の要点を抜粋して掲載しています。実装全体と、トークン列やASTを確認できるブラウザツールは、末尾のGitHubリンクから参照できます。ローカルで実行しなくても、本文の例を追って理解できる構成です。

数式を計算するまでの3段階

数式の処理を、字句解析・構文解析・評価の3段階に分けます。

1 + 2 * 3を入力した場合、それぞれの段階で次の処理を行います。

字句解析で取り出した数値や演算子を、トークンと呼びます。

トークン列には、何がどの順序で書かれているかが記録されています。構文解析はその並びを読み取り、演算子と計算対象の関係を組み立てます。

評価は、組み立てられた構造をたどって実際に計算する処理です。

まずは、この処理の中心となるASTから見ていきます。

ASTは式の構造を表す

1 + 2 * 3では、掛け算を先に計算します。式全体を構造として捉えると、次のようになります。

flowchart TD
    A["+"] -->|左辺| B["1"]
    A -->|右辺| C["*"]
    C -->|左辺| D["2"]
    C -->|右辺| E["3"]

式全体は足し算で、その右辺に掛け算が含まれています。

このように、数値や演算をノードとして配置し、親子関係で式を表したものがASTです。木の一番上にあるノードを**根（ルート）**と呼びます。この式の根は+です。

根にある演算が最初に計算されるわけではありません。足し算の結果を求めるには、まず左右の値が必要です。右辺の掛け算から6が得られると、最後に1 + 6を計算できます。

括弧が変わると、ASTも変わる

今度は、(1 + 2) * 3を考えます。

flowchart TD
    A["*"] -->|左辺| B["+"]
    A -->|右辺| C["3"]
    B -->|左辺| D["1"]
    B -->|右辺| E["2"]

こちらは掛け算が根になり、その左辺に足し算が含まれています。

2つの式を比較すると、次の違いがあります。

使っている数値と演算子は同じでも、組み合わせ方が違います。ASTは、この違いを木の構造として保持します。

なぜ「抽象」構文木なのか

今回のASTには、空白や括弧そのものを残しません。

括弧が指定したまとまりは、すでにノードの親子関係に反映されています。評価するときは、その構造に従えば計算できます。

このように、入力の表記から処理に必要な構造を取り出しているため、抽象構文木と呼びます。

字句解析：文字列をトークンに分ける

ここからは、文字列を読み取るところから順番に実装を見ていきます。

たとえば、次の入力を考えます。

12 + 3 * (4 - 2)

字句解析では、これを次の単位に分けます。

number("12")
+
number("3")
*
(
number("4")
-
number("2")
)
EOF

12は、連続する数字をまとめた1つの数値トークンです。演算子と括弧は、それぞれ1つのトークンにします。

空白は今回の数式では意味を持たないため、読み飛ばします。最後のEOFは、入力の終わりを表します。

トークンに持たせる情報

Goでは、トークンを次の構造体で表します。

type Token struct {
    Kind string `json:"kind"`
    Text string `json:"text"`
    Pos  int    `json:"pos"`
}

演算子や括弧のKindには、"+"や"("など、記号自体を使います。

Posは0始まりのバイト位置です。エラーが起きた場所を示すために記録しておきます。

数値を1つのトークンにまとめる

字句解析では、入力を先頭から読み進め、連続する数字を1つの数値トークンにまとめます。たとえば、12は1と2に分けず、number("12")として扱います。

トークンには元の文字列を保存し、計算に使う数値への変換は評価の段階で行います。

マイナスの役割は構文解析で決める

-3は、字句解析では-と3の2つのトークンに分けます。-は、式の中の位置によって役割が変わるためです。

字句解析では、どちらの-も同じ種類のトークンとして扱います。構文解析でトークンの並びを読み取り、二項演算か単項演算かを判断して、対応するASTのノードを作ります。

GoでASTのノードを定義する

トークン列から組み立てるASTには、次の3種類のノードを用意します。

今回は、共通の構造体で表します。

type Node struct {
    Kind  string `json:"kind"`
    Value string `json:"value"`
    Left  *Node  `json:"left,omitempty"`
    Right *Node  `json:"right,omitempty"`
}

Kindには"number"、"unary"、"binary"を入れます。

数値ノードのValueは"12"などの数値文字列、演算ノードのValueは"+"や"*"などの演算子です。単項演算の対象は、今回はRightに格納します。

LeftとRightも*Nodeなので、その先に別の演算を持たせられます。

たとえば、1 + 2 * 3は次のように表せます。

node := &Node{
    Kind:  "binary",
    Value: "+",
    Left: &Node{
        Kind:  "number",
        Value: "1",
    },
    Right: &Node{
        Kind:  "binary",
        Value: "*",
        Left: &Node{
            Kind:  "number",
            Value: "2",
        },
        Right: &Node{
            Kind:  "number",
            Value: "3",
        },
    },
}

構文解析器は、この組み立てをトークン列から自動で行います。

文法で演算子の優先順位を決める

ASTを組み立てる前に、受け付ける式のルールを文法として整理します。

expression = term { ("+" | "-") term }
term       = unary { ("*" | "/") unary }
unary      = ("+" | "-") unary | primary
primary    = number | "(" expression ")"

{ ... }は0回以上の繰り返し、|は選択肢を表します。引用符で囲んだ記号は、入力に現れる演算子や括弧です。

規則ごとの役割は、次のとおりです。

優先順位は、呼び出す規則の関係で表せる

最初の2つはAST、3つ目は関数の呼び出し関係なので、図の直前に次の説明を入れます。

flowchart TD
    E["expression：足し算・引き算"]
    T["term：掛け算・割り算"]
    U["unary：単項の符号"]
    P["primary：数値・括弧"]

    E -->|左右の項を読む| T
    T -->|左右の式を読む| U
    U -->|符号があれば対象を読む| U
    U -->|符号がなければ| P
    P -->|括弧の中を読む| E

expressionは、足し算・引き算の左右をtermとして読み取ります。

termは掛け算・割り算をまとめてから返すため、1 + 2 * 3の右辺は2 * 3という1つの部分木になります。

その内側で、unaryが単項の符号を処理します。これにより、今回の文法では-2 * 3を(-2) * 3として組み立てられます。

また、primaryが開き括弧を見つけると、括弧の中を再びexpressionとして読み取ります。これが、括弧の中に四則演算や別の括弧を入れられる仕組みです。

再帰下降構文解析でASTを作る

今回は、文法の規則ごとに関数を用意する再帰下降構文解析を使います。

各関数は、自分が担当する式を読み取り、その式を表すASTのノードを返します。

読み取り状態は、次の構造体で管理します。

type reader struct {
    tokens []Token
    pos    int
}

func (p *reader) peek() Token {
    return p.tokens[p.pos]
}

peek()で現在のトークンを確認し、トークンを消費したらposを進めます。トークン列の末尾には、字句解析で追加したEOFがある前提です。

足し算・引き算を読み取る

expressionは、最初に左辺となるtermを読み取ります。

その後に+または-が続いていれば、右辺のtermも読み取り、二項演算ノードにまとめます。

func (p *reader) expression() (*Node, error) {
    left, err := p.term()
    if err != nil {
        return nil, err
    }

    for p.peek().Kind == "+" || p.peek().Kind == "-" {
        op := p.peek().Kind
        p.pos++

        right, err := p.term()
        if err != nil {
            return nil, err
        }

        left = &Node{
            Kind:  "binary",
            Value: op,
            Left:  left,
            Right: right,
        }
    }

    return left, nil
}

ポイントは、作ったノードをleftに代入していることです。

10 - 3 - 2の場合、leftは次のように更新されます。

このように、同じ優先順位の演算を左側からまとめる性質を左結合と呼びます。

引き算の場合、(10 - 3) - 2は5ですが、10 - (3 - 2)は9です。演算子の優先順位に加えて、結合の向きもASTに反映する必要があります。

掛け算・割り算を読み取る

termも同じ構造です。

対象の演算子を*と/に変え、左右の式をunaryで読み取ります。

func (p *reader) term() (*Node, error) {
    left, err := p.unary()
    if err != nil {
        return nil, err
    }

    for p.peek().Kind == "*" || p.peek().Kind == "/" {
        op := p.peek().Kind
        p.pos++

        right, err := p.unary()
        if err != nil {
            return nil, err
        }

        left = &Node{
            Kind:  "binary",
            Value: op,
            Left:  left,
            Right: right,
        }
    }

    return left, nil
}

こちらも左結合なので、8 / 4 / 2は(8 / 4) / 2として組み立てられ、結果は1になります。

単項の符号を読み取る

unaryは、先頭の+または-を単項演算として処理します。

func (p *reader) unary() (*Node, error) {
    if p.peek().Kind == "+" || p.peek().Kind == "-" {
        op := p.peek().Kind
        p.pos++

        right, err := p.unary()
        if err != nil {
            return nil, err
        }

        return &Node{
            Kind:  "unary",
            Value: op,
            Right: right,
        }, nil
    }

    return p.primary()
}

符号があれば、対象の式を読むためにunary自身を呼び出します。そのため、--3は-(-3)として扱えます。

1 - -2の場合は、最初の-をexpressionが引き算として消費し、その右辺を読む途中でunaryが次の-を単項演算として消費します。

字句解析では同じ種類だったトークンに、ここで異なる役割が与えられます。

数値と括弧を読み取る

primaryは、数値または括弧で囲まれた式を読み取ります。

func (p *reader) primary() (*Node, error) {
    t := p.peek()

    switch t.Kind {
    case "number":
        p.pos++

        return &Node{
            Kind:  "number",
            Value: t.Text,
        }, nil

    case "(":
        p.pos++

        node, err := p.expression()
        if err != nil {
            return nil, err
        }

        if p.peek().Kind != ")" {
            return nil, fmt.Errorf(
                "位置%d: 閉じ括弧 ) が必要です",
                p.peek().Pos+1,
            )
        }
        p.pos++

        return node, nil

    default:
        return nil, fmt.Errorf(
            "位置%d: 数値または開き括弧 ( が必要です",
            t.Pos+1,
        )
    }
}

数値の場合は、数値ノードを作って返します。

開き括弧の場合は、その内側をexpressionで解析し、閉じ括弧を確認してから内側のノードを返します。括弧専用のノードは作りません。

たとえば(1 + 2) * 3では、primaryが1 + 2の部分木を返し、外側のtermがそれを掛け算の左辺として使います。

1 + 2 * 3を解析する流れを追う

ここまでの関数がどう連携するのか、1つの式で確認します。

説明を追いやすくするため、下の表では、単純な数値を読むときのunaryとprimaryの呼び出しをまとめています。

各関数は、自分の担当する演算子だけを消費します。

termは+を残して返り、expressionがその続きを処理します。一方、*はtermの中で処理されるため、掛け算がまとまった状態でexpressionへ返ります。

この関数間の役割分担によって、演算子の優先順位を表現しています。

入力を最後まで読んだか確認する

式を解析した後には、現在のトークンがEOFであることも確認します。

node, err := p.expression()

if err == nil && p.peek().Kind != "EOF" {
    err = fmt.Errorf(
        "位置%d: 予期しないトークン %q",
        p.peek().Pos+1,
        p.peek().Text,
    )
}

たとえば、1 2という入力では、先頭の1だけなら数値として解析できます。しかし、その後に演算子のない2が残っています。

末尾の確認によって、このような余分なトークンを検出します。

ASTを評価して計算結果を得る

ASTができたら、ノードを再帰的にたどって計算します。

評価関数は、次の形です。

func Eval(n *Node) (float64, error)

処理は、ノードの種類によって分かれます。

二項演算の場合、まず左右の子ノードを評価します。

left, err := Eval(n.Left)
if err != nil {
    return 0, err
}

right, err := Eval(n.Right)
if err != nil {
    return 0, err
}

得られた値に対して、演算子に応じた計算を行います。

var result float64

switch n.Value {
case "+":
    result = left + right
case "-":
    result = left - right
case "*":
    result = left * right
case "/":
    if right == 0 {
        return 0, fmt.Errorf("ゼロで割ることはできません")
    }
    result = left / right
default:
    return 0, fmt.Errorf("不正な演算子: %s", n.Value)
}

1 + 2 * 3の場合、右辺の評価で2 * 3から6が返り、根の足し算で1 + 6を計算します。

評価処理は、子ノードの結果を使って演算するだけです。演算子の優先順位は、構文解析でASTの構造に反映されています。

数値型による計算の性質

今回はfloat64を使うため、5 / 2の結果は2.5になります。

ただし、0.1などの小数には、二進数の浮動小数点で正確に表せない値があります。そのため、0.1 + 0.2のような計算では丸め誤差が生じます。

数式を正しい構造に解析することと、数値をどの精度で計算するかは、別々に設計する必要があります。

サンプルでは、ゼロ除算に加え、計算結果が無限大やNaNになった場合もエラーとして扱っています。

エラーはどの段階で起きるのか

字句解析・構文解析・評価を分けると、不正な入力をどこで検出するかも整理できます。

1 / 0は、文法上は正しい式です。左右に数値を持つ割り算としてASTを作れますが、評価するとエラーになります。

一方、1 + * 2は、足し算の右辺を組み立てられません。構文解析の時点で失敗するため、評価には進みません。

この分離は、エラー表示にも利用できます。たとえば、評価に失敗した場合でも、作成済みのASTを表示して式の構造を確認できます。

テストでは結果と構造を確認する

パーサーのテストでは、演算子の優先順位、結合の向き、括弧、単項の符号を確認します。

計算結果に加えて、ASTの構造も確認すると、構文解析そのものを検証できます。

たとえば1 + 2 * 3なら、次の条件を確認します。

• 根が二項演算の+である
• 根の左辺が数値1である
• 根の右辺が二項演算の*である
• 掛け算の左右が、それぞれ数値2と3である

構文解析のテストではASTを確認し、評価のテストではASTから得られる数値を確認する。このように分けると、不具合が起きた段階を絞り込みやすくなります。

あわせて、閉じ括弧の不足、演算子の不足、空の入力、ゼロ除算といったエラーも確認します。

ASTを保持すると、計算以外にも使える

四則演算の結果を一度求めるだけなら、構文解析の途中で計算する実装も可能です。

ASTとして式を保持すると、解析した構造を複数の処理に利用できます。

たとえば、次のような用途があります。

• 式の構造を画面に表示する
• 演算子の数や、式の深さを調べる
• 別の形式の数式文字列を出力する
• 変数に対応させ、異なる値を与えて繰り返し評価する

今回のサンプルでは、ASTをブラウザ上の階層表示とJSON表示に利用しています。

字句解析・構文解析・評価を分けておくことで、式を読み取る処理と、その式を利用する処理を個別に扱えます。

補足：実装全体とブラウザツール

記事で扱った実装全体は、次のリポジトリで公開しています。

GitHub：taako-502/go-expression-parser

ブラウザツールでは、入力した数式について次の情報を確認できます。

• 計算結果
• 字句解析で取り出したトークン列
• ASTの階層表示
• ASTのJSON表現

キャプション：同じ入力について、トークン列・AST・計算結果を並べて確認できる。

ローカルで動かす

実行に必要なGoのバージョンは、リポジトリのREADMEとgo.modを確認してください。

git clone https://github.com/taako-502/go-expression-parser.git
cd go-expression-parser
go run .

起動後、ブラウザで次のURLを開きます。

http://127.0.0.1:8080

go run .で画面の配信と計算用APIが起動します。終了するときはCtrl+Cです。

テストは、次のコマンドで実行できます。

go test ./...

コードを読む場合は、次の3つが記事の内容に対応しています。

今回の対応範囲は、四則演算・括弧・小数・単項の符号です。変数、関数、累乗、指数表記、2(3)のような暗黙の掛け算には対応していません。

まとめ

数式パーサーでは、文字列を次の順序で処理します。

1. 字句解析で、数値や演算子をトークンに分ける
2. 構文解析で、優先順位と結合の向きをASTに反映する
3. 評価で、ASTの子ノードから計算結果を求める

今回の再帰下降構文解析では、文法の規則をGoの関数に対応させました。足し算・引き算の関数が掛け算・割り算の関数を呼び、その結果を子ノードとして組み込むことで、演算子の優先順位を表現しています。

ASTに式の構造を保持すると、評価処理はその構造に従って計算できます。同じ構造を、可視化や解析などの別の処理にも利用できるようになります。