Go 言語による有理数電卓

2013-02-15 (鈴)

1. はじめに

Go 言語は UTF-8 テキストに対する字句解析器を標準パッケージ "text/scanner" (scanner - The Go Programming Language [golang.org]) で用意している。 この字句解析器が認識する文字列リテラルや数値リテラルの形式は Go 言語の文法にしたがったものに限られるが,それらは今日普及している慣習に沿っており,さらに +* などの記号については文字コードがそのまま返され,iffor などの単語については予約語ではなく単に識別子として認識されるから,広くユーザ定義のオリジナルなプログラミング言語の字句解析器として利用できる。

ここではその初歩的な応用として,与えられた有理数の式を解釈して値を計算し表示する電卓プログラムを示す。 Go 言語による電卓プログラムはすでに Google による GDD 2010: Go language (pdf) [google.com] の例があるが,Go 言語自体の紹介を主眼とし,パッケージとしては "fmt", "os", "bufio" だけを使い字句解析を手作りしていた点で,ここで示すものとは趣旨が異なる。

電卓プログラムのコンパイル&実行例を下記に示す。

01:~/tmp$ tar xvf calc-25-02-13.tar.bz2 
x calc-25-02-13/
x calc-25-02-13/src/
x calc-25-02-13/src/arith/
x calc-25-02-13/src/calc/
x calc-25-02-13/src/calc/calc.go
x calc-25-02-13/src/arith/num.go
x calc-25-02-13/src/arith/num_test.go
01:~/tmp$ cd calc-25-02-13
01:~/tmp/arith-25-02-13$ GOPATH=`pwd` go install calc
01:~/tmp/arith-25-02-13$ ./bin/calc
5 + 6
= 11
5 / 6
= 5/6   ≒ 0.8333333333333334
 
Mac OS X や Linux などでは上記のとおりにできますが,Windows の Cygwin では GOPATH=`pwd` のかわりに GOPATH=`cygpath -w -a .` としてください。 また,≒ を表示できるように UTF-8 端末を使ってください (今の Cygwin の既定の端末プログラム mintty で OK です)。

2. トークンの取り出し

字句解析器 (lexical analyzer) とはソース・テキストからトークン (token) を次々と取り出すある種のイテレータである。 "text/scanner" パッケージの scanner.Scanner 構造体は慣習的な形式の数や記号に対する字句解析器の実装として使うことができる。 その中心的なメソッドである

func (s *Scanner) Scan() rune

はソース・テキストから現在位置を進めてトークンを取り出し,戻り値とする。 この戻り値はトークンがファイル終端 (End Of File),識別子 (identifier),整数 (integer) 等ならば下記のように定義された負数になり,それ以外の記号類 (+* など) ならばその文字コードそのもの ('+''*' など) になる。

const (
    EOF = -(iota + 1)
    Ident
    Int
    Float
    Char
    String
    RawString
    Comment
)
Go 言語の rune 型はいわゆる Unicode 文字型ですが符号付き 32 ビット長整数として定義されています。 その負数は,現行の文字はもちろん予想できる将来の拡張まで含めて,どの Unicode 文字ともビットパターンが重複せずに安全に使えます。

識別子や整数 (abc123 など) のトークンは,ソース・テキストで実際にどんな文字の列として表現されているかが重要である。 ソース・テキストの現在位置のトークンの文字列 ("abc""123" など) は次のメソッドの戻り値として得られる。

func (s *Scanner) TokenText() string

scanner.Scanner 構造体が読み込むソース・テキスト src はあらかじめ次の初期化メソッドで与えておく。

func (s *Scanner) Init(src io.Reader) *Scanner

ここで io.Reader 型とは次のようにバイト列からの Read メソッドの実装を要求するインタフェースである。

type Reader interface {
    Read(p []byte) (n int, err error)
}

代表的には標準入力 os.Stdin などが属する os.File 構造体がこれに該当するが,"strings" パッケージの strings.Reader 構造体も同様に該当する。 電卓プログラムは,入力された1行を同パッケージの

func NewReader(s string) *Reader

に与えて strings.Reader 構造体を作成し,ソース・テキストとする。

厳密にいえば,標準入力 os.Stdinos.File 構造体へのポインタであり, io.Reader インタフェースが要求する Read メソッドは os.File 構造体へのポインタや strings.Reader 構造体へのポインタに対して設けられています。 Go 言語では構造体そのものをレシーバとしてメソッドを定義することも,構造体へのポインタをレシーバとしてメソッドを定義することも両方できますから, この区別はあまりないがしろにはできません。

2.1Lex 構造体

構文解析ではソース・テキストの現在位置のトークンが何であるか ('+' なのか scanner.Int なのか等々) を判別する必要がある。 そこで下記のように scanner.Scanner と現在のトークンをあわせた構造体 Lex とそのメソッドを定義する。

// 字句解析器 (Lexical analyzer)
type Lex struct {
    scanner.Scanner
    Token rune // 現在のトークン
}

// 次のトークンを lex.Token に得る。
func (lex *Lex) NextToken() {
    lex.Token = lex.Scan()
}

// 文脈情報を伴った error でパニックを発生させる。
func (lex *Lex) Panic(msg string) {
    panic(fmt.Errorf("%s: %q", msg, lex.TokenText()))
}
上記 Panic メソッドの fmt.Errorf の書式引数にある %q は,対応する文字列引数を引用符で囲み安全にエスケープして文字列化します。

電卓プログラムは,入力された1行を表す line string に対し次のようにして構文解析の準備を整える。

    var src io.Reader = strings.NewReader(line)
    var lex Lex
    lex.Init(src)
    lex.NextToken()

3. 再帰下降法による式の解釈と評価

前節のように構文解析の準備が整った後,次の1文で構文解析を行う。 戻り値として式を解釈し評価した数値が返される。変数 x にその値を格納する。

   x := addSubExp(&lex)

Go 言語は任意精度の有理数演算のために "math/big" パッケージ (big - The Go Programming Language [golang.org]) を標準で備えているが,電卓プログラムではそれを簡単に使えるようにラップした "arith" パッケージ (有理数を含む混合演算のための Go 言語パッケージの試作) を利用する。

// 加減式 (単項プラス/マイナスを含む) を読んで値を返す。
func addSubExp(lex *Lex) arith.Number {
    unaryMinus := false
    switch lex.Token {
    case '+':
        lex.NextToken()
    case '-':
        unaryMinus = true
        lex.NextToken()
    }
    x := mulDivExp(lex)
    if unaryMinus {
        x = arith.Subtract(0, x)
    }
LOOP:
    for {
        switch lex.Token {
        case '+':
            lex.NextToken()
            y := mulDivExp(lex)
            x = arith.Add(x, y)
        case '-':
            lex.NextToken()
            y := mulDivExp(lex)
            x = arith.Subtract(x, y)
        default:
            break LOOP
        }
    }
    return x
}

式の解釈は単純な再帰下降法によって行う。 乗除式が + または - を間にはさんで出現しているかどうかを調べることで暗黙のうちに +- が最も低い優先度の演算子として解釈される。

// 乗除式を読んで値を返す。
func mulDivExp(lex *Lex) arith.Number {
    x := unaryExp(lex)
LOOP:
    for {
        switch lex.Token {
        case '*':
            lex.NextToken()
            y := unaryExp(lex)
            x = arith.Multiply(x, y)
        case '/':
            lex.NextToken()
            y := unaryExp(lex)
            if arith.Compare(y, 0) == 0 {
                panic(fmt.Errorf("division by zero"))
            }
            x = arith.DivideReal(x, y)
        case scanner.Ident:
            text := lex.TokenText()
            if text != "div" {
                break LOOP
            }
            lex.NextToken()
            y := unaryExp(lex)
            if arith.Compare(y, 0) == 0 {
                panic(fmt.Errorf("integer division by zero"))
            }
            x = arith.DivideInt(x, y)
        default:
            break LOOP
        }
    }
    return x
}

この電卓プログラムでは実数除算の演算子として / を使い,整数除算の演算子として div を使う。 字句解析器からは div は識別子 (identifier) として認識されるから,scanner.Ident でケース分けした後で lex.TokenText()"div" と等しいかどうかを調べる。

単項マイナス演算子を2項マイナス演算子と同じ優先度にしたのは,数学的な慣習に一致させたというよりは div 演算子と同じく Pascal にならったものです。 Go や C や Java のように単項マイナス演算子を * / div より高い優先度にする (例えば 5 と -6 の掛け算を 5 * (-6) と書く必要はなく 5 * -6 とも書けるようにする) ことは読者へのやさしい課題として残します。
// 単項式を読んで値を返す。
func unaryExp(lex *Lex) arith.Number {
    if lex.Token == '(' {
        lex.NextToken()
        x := addSubExp(lex)
        if lex.Token != ')' {
            lex.Panic("')' expected")
        }
        lex.NextToken()
        return x
    }
    if lex.Token != scanner.Int && lex.Token != scanner.Float {
        lex.Panic("number expected")
    }
    r, ok := ratFor(lex.TokenText())
    if !ok {
        lex.Panic("invalid number")
    }
    lex.NextToken()
    return r
}

単項式の解釈では,もしも現在のトークンが '(' ならば最初の addSubExp 関数を再帰的に呼び出してから,括弧が閉じているかどうか ')' を確かめる。 こうすることで何重にも括弧で入れ子にした式を正しく解釈し評価できる。

もしもトークンが整数または浮動小数点数だったら ratFor(lex.TokenText()) で対応する有理数を読み込む。

// 文字列に対する有理数を得る。
func ratFor(text string) (*big.Rat, bool) {
    r := new(big.Rat)
    return r.SetString(text)
}
ここで「浮動小数点数」とは厳密にいえば Go 言語のソース・テキストとしてならば浮動小数点数として解釈されたはずの文字の列のことです。 ratFor 関数が使う有理数の SetString メソッドはこれをあくまで正確な数として解釈し有理数として読み込みます。 例えば 1.23 と書かれてあれば 123/100 として読み込みます。
1.23
= 123/100	= 1.23
 

4 有理数の表示

式の結果が x に得られた後,その文字列表現を s1 := arith.String(x) で得て表示する。 このとき小数点数は 123/100 のような分数として表現される。 これは必ずしも直感的な表現ではない。 そこで arith.Float64(x) として倍精度浮動小数点数に変換し,その文字列表現を Go 言語のデフォルト文字列変換である %v 形式で s2 に得る。

二つの文字列表現 s1s2 が等しいときは一方だけを表示する。 11 など一定範囲の整数がこのケースである。

文字列表現は一致しないが,s2 を前節の ratFor 関数で再び有理数に変換した結果が x と等しくなるならば,等号 = をはさんで s1s2 を表示する。 123/100 (= 1.23) などがこのケースである。

どちらのケースにもあてはまらないときは をはさんで s1s2 を表示する。 5/6 (= 0.8333…) などがこのケースである。

    // 値を表示する。もしその浮動小数点数表示が異なるならばそれも表示する。
    s1 := arith.String(x)
    s2 := fmt.Sprintf("%v", arith.Float64(x))
    if s1 == s2 {
        fmt.Printf("= %s\n", s1)
    } else if r, ok := ratFor(s2); ok && arith.Compare(x, r) == 0 {
        fmt.Printf("= %s\t= %s\n", s1, s2)
    } else {
        fmt.Printf("= %s\t≒ %s\n", s1, s2)
    }
有効桁数を考えなければ,分母を素因数分解した結果が 2m5n と表現できれば正確に小数点数として表現できます。 現実には有効桁数があるために,もとが整数であっても倍精度浮動小数点数では近似表現となる場合があります。
1e20 + 1
= 100000000000000000001	≒ 1e+20
 

5. おわりに

ここでは Go 言語の標準パッケージ "text/scanner" が与える scanner.Scanner 構造体を字句解析器として利用する例を示した。 ここでの作例は優先順位付きの式を解釈する有理数電卓だが,同じ方法がより一般的なプログラミング言語処理系の作成にも応用できる。 すなわち,同構造体を字句解析器として使うことで処理系作成のステップを一つ省くことができる。 構文解析器は再帰下降法で半機械的に構成できる。 Go 言語プログラムはネイティブ・コードへとコンパイルされるから,処理系をインタープリタとして構成した場合でもそこそこの速度を達成できる見込みが高い。 したがって,例えば DSL (Domain-Specific Language) 作成のツールとして Go 言語は有望な候補である。

作例で示したように1個のトークンを先読みして再帰下降で解析するには言語の構文が LL(1) に属さなければいけません。 しかし,実用上はこのクラスでも十分に強力です。 複雑な構文規則は人間が正確かつ短期間に習得することを困難にしますから,しがらみなく新規に設計する DSL でわざわざ採用することはありません。

Copyright (c) 2013 OKI Software Co., Ltd.