M.Hiroi's Home Page

お気楽 Go 言語プログラミング入門

電卓プログラムの作成 (5)


Copyright (C) 2014-2021 Makoto Hiroi
All rights reserved.

はじめに

今回は複数の式を順番に実行する begin 式、処理を繰り返し実行する while 式、局所変数を定義する let 式を追加してみましょう。

●begin, while. let の構文

最初に、begin, while, let の構文を示します。 

begin 式1, 式2, ..., 式n end
while 条件式 do 式1, ..., 式n end
let 変数1 = 式1, ..., 変数n = 式n in 式1, ..., 式n end

begin は複数の式を順番に評価し、最後に評価した式の返り値が begin の値になります。機能は Scheme の begin と同じです。while は条件式を評価して、その値が真であれば本体の式を繰り返し評価します。条件式が偽の場合は本体の式を評価しないで 0 を返します。let は let ... in の間に定義された変数を局所変数として扱います。

また、関数の本体、while 式の本体、let 式の本体では、複数の式をカンマで区切って指定できるように拡張します。つまり、暗黙のうちに begin 式で囲まれていると考えてください。式の値は begin 式と同様に、最後に評価した式の値とします。

文法を EBNF で表すと次のようになります。 

[EBNF]
   文    = 関数定義 | 式.
関数定義 = "def", 関数, "(", [仮引数リスト], ")", 式, { ",", 式 }, "end".
   式    = 代入式 | 式１.
 代入式  = 変数, "=", 式.
  式１   = 式２, { ("and" | "or"), 式２}.
  式２   = 式３, ("==" | "!=" | "<" | "<=" | ">" | ">="), 式３.
  式３   = 項, { ("+" | "-"), 項 }.
   項    = 因子, { ("*" | "/"), 因子 }.
  因子   = 数値 | ("+" | "-" | "not"), 因子 | "(", 式, ")" | 変数 | 関数, "(", [引数リスト], ")" |
           if式 | begin式 | while式 | let 式.
  if式   = "if", 式, "then", 式, ["else", 式], "end".
 begin式 = "begin", 式, { ",", 式 }, "end".
 while式 = "while", 式, "do", 式, { ",", 式 }, "end".
  let式  = "let", 代入式, { ",", 代入式}, "in", 式, {",", 式}, "end".
  変数   = 識別子
  関数   = 識別子

仮引数リスト = 変数, { ",", 変数 }.
引数リスト   = 式, { ",", 式 }.

[注意] 数値と識別子の定義は省略

●データ型の定義

最初に、begin, while, let を表すデータ型を定義します。 

リスト : データ型の定義

// キーワード
const (
    DEF = -(iota+10)
    END
    IF
    THEN
    ELSE
    NOT
    AND
    OR
    EQ
    NE
    LT
    GT
    LE
    GE
    BGN
    WHL
    DO
    LET
    IN
)

// キーワード表
var keyTable = make(map[string]rune)

func initKeyTable() {
    keyTable["def"]  = DEF
    keyTable["end"]  = END
    keyTable["if"]   = IF
    keyTable["then"] = THEN
    keyTable["else"] = ELSE
    keyTable["and"]  = AND
    keyTable["or"]   = OR
    keyTable["not"]  = NOT
    keyTable["begin"] = BGN
    keyTable["while"] = WHL
    keyTable["do"]   = DO
    keyTable["let"]  = LET
    keyTable["in"]   = IN
}

// begin
type Bgn struct {
    body []Expr
}

func newBgn(xs []Expr) *Bgn {
    return &Bgn{xs}
}

// while
type Whl struct {
    testForm, body Expr
}

func newWhl(testForm, body Expr) *Whl {
    return &Whl{testForm, body}
}

// let 
type Let struct {
    vars []Variable
    vals []Expr
    body Expr
}

func newLet(vars []Variable, vals []Expr, body Expr) *Let {
    return &Let{vars, vals, body}
}

トークンに while 式を表す WHL と DO を、begin 式を表す BGN を、let 式を表す LET と IN を追加します。そして、keyTable に while, do, begin, let, in を追加します。

begin 式を表す構造体が Bgn です。フィールド変数 body の型は []Expr で、このスライスが本体を表します。while 式を表す構造体が Whl です。フィールド変数 testFrom が条件式で body が本体です。body には Bgn をセットします。let 式を表す構造体が Let です。vars には変数名を、vals には初期値となる式を格納します。body が let 式の本体です。while 式と同様に Bgn をセットします。

●構文解析の修正

begin, while, let の構文解析は関数 factor で行います。 

リスト : 因子の処理

func factor(lex *Lex) Expr {
    switch lex.Token {

    ・・・省略・・・

    case IF:
        lex.getToken()
        return makeSel(lex)
    case BGN:
        lex.getToken()
        return makeBegin(lex)
    case WHL:
        lex.getToken()
        return makeWhile(lex)
    case LET:
        lex.getToken()
        return makeLet(lex)

    ・・・省略・・・

}

トークンが BGN の場合は関数 makeBegin を呼び出します。WHL の場合は関数 makeWhile を、LET の場合は関数 makeLet を呼び出します。

●begin 式の処理

次は関数 makeBegin を作ります。 

リスト : begin 式の処理

func getBody(lex *Lex) []Expr {
    body := make([]Expr, 0)
    for {
        body = append(body, expression(lex))
        switch lex.Token {
        case ',':
            lex.getToken()
        default:
            return body
        }
    }
}

func makeBegin(lex *Lex) Expr {
    if lex.Token == END {
        panic(fmt.Errorf("invalid begin form"))
    }
    body := getBody(lex)
    if lex.Token != END {
        panic(fmt.Errorf("'end' expected"))
    }
    lex.getToken()
    return newBgn(body)
}

makeBegin の処理は簡単です。最初に lex.Token が END かチェックして、本体がなければ panic でエラーを送出します。次に、カンマで区切られた式を関数 getBody で取得します。そして、トークンが END で終わっていることを確認して、newBgn(body) を返します。

●while 式の処理

次は関数 makeWhile を作ります。 

リスト : while 式の処理

func makeWhile(lex *Lex) Expr {
    testForm := expression(lex)
    if lex.Token == DO {
        lex.getToken()
        return newWhl(testForm, makeBegin(lex))
    } else {
        panic(fmt.Errorf("'do' expected"))
    }
}

最初に expression で条件式を取り出し、変数 testForm にセットします。そして、トークンが DO であることを確認したら、makeBegin で本体を取得して、newWhl で testForm と本体を構造体 Whl に格納して返すだけです。do がない場合はエラーを送出します。

●let 式の処理

次は let 式を処理する関数 makeLet を作ります。 

リスト : let 式の処理

func makeLet(lex *Lex) Expr {
    vars := make([]Variable, 0)
    vals := make([]Expr, 0)
    for {
        e := expression(lex)
        a, ok := e.(*Agn)
        if !ok {
            panic(fmt.Errorf("let: invalid assign form"))
        }
        vars = append(vars, a.name)
        vals = append(vals, a.expr)
        if lex.Token == IN {
            break
        } else if lex.Token != ',' {
            panic(fmt.Errorf("let: ',' expected"))
        }
        lex.getToken()
    }
    lex.getToken()
    return newLet(vars, vals, makeBegin(lex))
}

変数名と初期化式を格納するスライス vars と vals を用意します。次の for ループで、let と in の間にある代入式を expression で読み取ります。次に、expression の返り値 e の型が *Agn であることを型アサーションでチェックします。そうでなければ、panic でエラーを送出します。そして、a.name を vars に、a.expr を vals に追加します。

次にトークンが IN かチェックします。そうであれば、break で for ループを脱出します。トークンがカンマ ( , ) でなければ、panic でエラーを送出します。カンマの場合は次の代入式を読み取ります。最後に、本体を makeBegin で取り出して、newLet で構造体 Let に vars, vals, 本体を格納して返します。

●defineFunc の修正

次は、関数定義文を処理する関数 defineFunc を修正します。 

リスト : ユーザ関数の定義

func defineFunc(lex *Lex) {
    lex.getToken()
    if lex.Token != scanner.Ident {
        panic(fmt.Errorf("invalid define form"))
    }
    name := lex.TokenText()
    lex.getToken()
    xs := getParameter(lex)    
    v, ok := funcTable[name]
    if ok {
        switch f := v.(type) {
        case *FuncU:
            if len(f.xs) != len(xs) {
                panic(fmt.Errorf("wrong number of arguments: %v", name))
            }
            body := newBgn(getBody(lex))
            if lex.Token != END {
                panic(fmt.Errorf("'end' expected"))
            }
            f.xs = xs
            f.body = body
        default:
            panic(fmt.Errorf("%v is built-in function", name))
        }
    } else {
        // 再帰呼び出し対応
        f := newFuncU(name, xs, nil)
        funcTable[name] = f
        f.body = newBgn(getBody(lex))
        if lex.Token != END {
            delete(funcTable, name)
            panic(fmt.Errorf("'end' expected"))
        }
    }
    fmt.Println(name)
}

関数の本体を取得するとき、makeBegin を呼び出すと式として扱われるため、end のあとにセミコロンの入力が必要になります。これを避けるため、makeBegin を呼び出さずに newBgn(getBody(lex)) を呼び出し、その返り値を body にセットします。あとは end があることを確認するだけです。

●式の評価

最後に、式を評価するメソッド Eval を作ります。 

リスト : 式の評価

// begin の評価
func (e *Bgn) Eval(env *Env) Value {
    var r Value
    for _, expr := range e.body {
        r = expr.Eval(env)
    }
    return r
}

// while の評価
func (e *Whl) Eval(env *Env) Value {
    for isTrue(e.testForm.Eval(env)) {
        e.body.Eval(env)
    }
    return Value(0.0)
}

// 局所変数を環境に追加
func addBinding(xs []Variable, es []Expr, env *Env) *Env {
    for i := 0; i < len(xs); i++ {
        env = newEnv(xs[i], es[i].Eval(env), env)
    }
    return env
}

// let の評価
func (e *Let) Eval(env *Env) Value {
    return e.body.Eval(addBinding(e.vars, e.vals, env))
}

Bgn は for ループで body の式を順番に取り出して Eval で評価するだけです。このとき、最後の式の評価結果を返すことに注意してください。Whl の場合は Go 言語の for ループを使って簡単に実装できます。条件式 e.testForm を Eval で評価し、返り値が真ならば、本体を表す式 e.body を Eval で評価します。繰り返しを終了したら Value(0.0) を返します。

let の評価も簡単です。関数 addBinding で環境 env に e.vars, e.vals の変数束縛を追加して、その新しい環境で本体 body を評価するだけです。関数 addBinding は環境 env に新しい変数束縛を追加しながら式を評価することに注意してください。たとえば、let a = 10, b = a * 10 in ... end の場合、最初に局所変数 a が 10 に初期化され、それを追加した環境で b = a * 10 が評価されるので、b の値は 10 * 10 = 100 となります。

大きな修正はこれだけです。あとの修正は簡単なので説明は割愛します。プログラムの詳細はプログラムリストをお読みください。

●実行例

それでは簡単な実行例を示します。組み込み関数に値を表示する print を追加して試してみました。 

Calc> print(10);
10
10
Calc> begin print(1), print(2), print(3) end;
1
2
3
3
Calc> a = 0;
0
Calc> while a < 10 do print(a), a = a + 1 end;
0
1
2
3
4
5
6
7
8
9
0
Calc> a;
10
Calc> b = 20;
20
Calc> b;
20
Calc> let a = 100, b = 200 in a + b end;
300
Calc> a;
10
Calc> b;
20

print は引数を表示したあと、引数をそのまま返します。begin, while, let は正常に動作していますね。

次は while で階乗を計算する関数 fact を作ってみましょう。 

Calc> def fact(n) let a = 1 in while n > 0 do a = a * n, n = n - 1 end, a end end
fact
Calc> fact(9);
362880
Calc> fact(10);
3.6288e+06
Calc> fact(20);
2.43290200817664e+18

fact は局所変数 a を 1 に初期化し、n が 0 よりも大きければ、a = a * n を計算して n の値を -1 します。最後に a を返します。これで階乗を計算することができます。

もうひとつ簡単な例として、フィボナッチ関数を作ってみましょう。 

Calc> def fibo(n) let a = 0, b = 1, c = 0 in
while n > 0 do c = a, a = b, b = b + c, n = n - 1 end,
a end
end
fibo
Calc> fibo(0);
0
Calc> fibo(1);
1
Calc> fibo(2);
1
Calc> fibo(3);
2
Calc> fibo(4);
3
Calc> fibo(5);
5
Calc> fibo(6);
8
Calc> fibo(7);
13
Calc> fibo(10);
55

正常に動作していますね。

関数 fact と fibo を清書すると次のようになります。 

リスト : fibo と fact

def fact(n)
  let
    a = 1
  in
    while n > 0 do
      a = a * n,
      n = n - 1
    end,
    a
  end
end

def fibo(n)
  let
    a = 0,
    b = 1,
    c = 0
  in
    while n > 0 do
      c = a,
      a = b,
      b = b + c,
      n = n - 1
    end,
    a
  end
end

暗黙の begin の中では式をカンマで区切っているので、見た目はちょっと変わっていますが、雰囲気はずいぶんとプログラミング言語らしくなってきましたね。begin, if, while, let を「式」ではなく「文」として定義すると、もっとプログラミング言語らしくなると思います。興味のある方はプログラムを改造してみてください。

●参考文献

  1. 松田晋, 『実践アルゴリズム戦略 解法のテクニック 再帰降下型構文解析』, C MAGAZINE 1992 年 9 月号, ソフトバンク
  2. 水野順, 『スクリプト言語を作ろう』, C MAGAZINE 2000 年 5 月号, ソフトバンク
  3. 松浦健一郎, 『コンパイラの作成』, C MAGAZINE 2003 年 1 月号, ソフトバンク
  4. 高田昌之, 『インタプリタ進化論』, ＣＱ出版社, 1992
  5. 久野靖, 『言語プロセッサ』, 丸善株式会社, 1993

●プログラムリスト

//
// calc5.go : 電卓プログラム (begin, while, let の追加)
//
//            Copyright (C) 2014-2021 Makoto Hiroi
//
package main

import (
    "fmt"
    "os"
    "math"
    "text/scanner"
)

// キーワード
const (
    DEF = -(iota+10)
    END
    IF
    THEN
    ELSE
    NOT
    AND
    OR
    EQ
    NE
    LT
    GT
    LE
    GE
    BGN
    WHL
    DO
    LET
    IN
)

// キーワード表
var keyTable = make(map[string]rune)

func initKeyTable() {
    keyTable["def"]  = DEF
    keyTable["end"]  = END
    keyTable["if"]   = IF
    keyTable["then"] = THEN
    keyTable["else"] = ELSE
    keyTable["and"]  = AND
    keyTable["or"]   = OR
    keyTable["not"]  = NOT
    keyTable["begin"] = BGN
    keyTable["while"] = WHL
    keyTable["do"]   = DO
    keyTable["let"]  = LET
    keyTable["in"]   = IN
}

// 値
type Value float64

// 局所変数の環境
type Env struct {
    name Variable
    val  Value
    next *Env
}

func newEnv(name Variable, val Value, env *Env) *Env {
    return &Env{name, val, env}
}

// 構文木の型
type Expr interface {
    Eval(*Env) Value
}

// 環境の生成
func makeBinding(xs []Variable, es []Expr, env *Env) *Env {
    var env1 *Env
    for i := 0; i < len(xs); i++ {
        env1 = newEnv(xs[i], es[i].Eval(env), env1)
    }
    return env1
}

// 局所変数を環境に追加
func addBinding(xs []Variable, es []Expr, env *Env) *Env {
    for i := 0; i < len(xs); i++ {
        env = newEnv(xs[i], es[i].Eval(env), env)
    }
    return env
}

// 局所変数の探索
func lookup(name Variable, env *Env) (Value, bool) {
    for ; env != nil; env = env.next {
        if name == env.name {
            return env.val, true
        }
    }
    return 0.0, false
}

// 局所変数の更新
func update(name Variable, val Value, env *Env) bool {
    for ; env != nil; env = env.next {
        if name == env.name {
            env.val = val
            return true
        }
    }
    return false
}

// 値の評価
func (e Value) Eval(_ *Env) Value {
    return e
}

// 変数
type Variable string

// 大域的な環境
var globalEnv = make(map[Variable]Value)

func (v Variable) Eval(env *Env) Value {
    // 局所変数の探索
    val, ok := lookup(v, env)
    if ok {
        return val
    }
    // 大域変数の探索
    val, ok = globalEnv[v]
    if !ok {
        panic(fmt.Errorf("unbound variable: %v", v))
    }
    return val
}

// 単項演算子
type Op1 struct {
    code rune
    expr Expr
}

func newOp1(code rune, e Expr) Expr {
    return &Op1{code, e}
}

// bool を Value に変換する
func boolToValue(x bool) Value {
    if x {
        return 1.0
    } else {
        return 0.0
    }
}

// 真か
func isTrue(x Value) bool {
    return x != 0.0
}

// 偽か
func isFalse(x Value) bool {
    return x == 0.0
}

func (e *Op1) Eval(env *Env) Value {
    v := e.expr.Eval(env)
    switch e.code {
    case '-': return -v
    case '+': return v
    case NOT: return boolToValue(isFalse(v))
    default:
        panic(fmt.Errorf("invalid Op1 code"))
    }
}

// 二項演算子
type Op2 struct {
    code rune
    left, right Expr
}

func newOp2(code rune, left, right Expr) Expr {
    return &Op2{code, left, right}
}

func (e *Op2) Eval(env *Env) Value {
    x := e.left.Eval(env)
    y := e.right.Eval(env)
    switch e.code {
    case '+': return x + y
    case '-': return x - y
    case '*': return x * y
    case '/': return x / y
    case EQ: return boolToValue(x == y)
    case NE: return boolToValue(x != y)
    case LT: return boolToValue(x < y)
    case GT: return boolToValue(x > y)
    case LE: return boolToValue(x <= y)
    case GE: return boolToValue(x >= y)
    default:
        panic(fmt.Errorf("invalid Op2 code"))
    }
}

// 短絡演算子
type Ops struct {
    code rune
    left, right Expr
}

func newOps(code rune, left, right Expr) Expr {
    return &Ops{code, left, right}
}

func (e *Ops) Eval(env *Env) Value {
    x := e.left.Eval(env)
    switch e.code {
    case AND:
        if isTrue(x) {
            return e.right.Eval(env)
        }
        return x
    case OR:
        if isTrue(x) {
            return x
        }
        return e.right.Eval(env)
    default:
        panic(fmt.Errorf("invalid Ops code"))
    }
}

// if
type Sel struct {
    testForm, thenForm, elseForm Expr
}

func newSel(testForm, thenForm, elseForm Expr) *Sel {
    return &Sel{testForm, thenForm, elseForm}
}

func (e *Sel) Eval(env *Env) Value {
    if isTrue(e.testForm.Eval(env)) {
        return e.thenForm.Eval(env)
    }
    return e.elseForm.Eval(env)
}

// while
type Whl struct {
    testForm, body Expr
}

func newWhl(testForm, body Expr) *Whl {
    return &Whl{testForm, body}
}

func (e *Whl) Eval(env *Env) Value {
    for isTrue(e.testForm.Eval(env)) {
        e.body.Eval(env)
    }
    return Value(0.0)
}

// begin
type Bgn struct {
    body []Expr
}

func newBgn(xs []Expr) *Bgn {
    return &Bgn{xs}
}

func (e *Bgn) Eval(env *Env) Value {
    var r Value
    for _, expr := range e.body {
        r = expr.Eval(env)
    }
    return r
}

// let 
type Let struct {
    vars []Variable
    vals []Expr
    body Expr
}

func newLet(vars []Variable, vals []Expr, body Expr) *Let {
    return &Let{vars, vals, body}
}

func (e *Let) Eval(env *Env) Value {
    return e.body.Eval(addBinding(e.vars, e.vals, env))
}

// 代入演算子
type Agn struct {
    name Variable
    expr Expr
}

func newAgn(v Variable, e Expr) *Agn {
    return &Agn{v, e}
}

func (a *Agn) Eval(env *Env) Value {
    val := a.expr.Eval(env)
    if !update(a.name, val, env) {
        globalEnv[a.name] = val
    }
    return val
}

// 組み込み関数
type Func interface {
    Argc() int
}

type Func1 func(float64) float64

func (f Func1) Argc() int {
    return 1
}

type Func2 func(float64, float64) float64

func (f Func2) Argc() int {
    return 2
}

// ユーザ定義関数
type FuncU struct {
    name string
    xs   []Variable
    body Expr
}

func newFuncU(name string, xs []Variable, body Expr) *FuncU {
    return &FuncU{name, xs, body}
}

func (f *FuncU) Argc() int {
    return len(f.xs)
}


// 関数呼び出し
type App struct {
    fn Func
    xs []Expr
}

func newApp(fn Func, xs []Expr) *App {
    return &App{fn, xs}
}

func (a *App) Eval(env *Env) Value {
    switch f := a.fn.(type) {
    case Func1:
        x := float64(a.xs[0].Eval(env))
        return Value(f(x))
    case Func2:
        x := float64(a.xs[0].Eval(env))
        y := float64(a.xs[1].Eval(env))
        return Value(f(x, y))
    case *FuncU:
            return f.body.Eval(makeBinding(f.xs, a.xs, env))
    default:
        panic(fmt.Errorf("function Eval error"))
    }
}

// 組み込み関数の初期化
var funcTable = make(map[string]Func)

// 値の表示
func print(x float64) float64 {
    fmt.Println(x)
    return x
}

func initFunc() {
    funcTable["sqrt"]  = Func1(math.Sqrt)
    funcTable["sin"]   = Func1(math.Sin)
    funcTable["cos"]   = Func1(math.Cos)
    funcTable["tan"]   = Func1(math.Tan)
    funcTable["sinh"]  = Func1(math.Sinh)
    funcTable["cosh"]  = Func1(math.Cosh)
    funcTable["tanh"]  = Func1(math.Tanh)
    funcTable["asin"]  = Func1(math.Asin)
    funcTable["acos"]  = Func1(math.Acos)
    funcTable["atan"]  = Func1(math.Atan)
    funcTable["atan2"] = Func2(math.Atan2)
    funcTable["exp"]   = Func1(math.Exp)
    funcTable["pow"]   = Func2(math.Pow)
    funcTable["log"]   = Func1(math.Log)
    funcTable["log10"] = Func1(math.Log10)
    funcTable["log2"]  = Func1(math.Log2)
    funcTable["print"] = Func1(print)
}

// 字句解析
type Lex struct {
    scanner.Scanner
    Token rune
}

func (lex *Lex) getToken() {
    lex.Token = lex.Scan()
    switch lex.Token {
    case scanner.Ident:
        key, ok := keyTable[lex.TokenText()]
        if ok {
            lex.Token = key
        }
    case '=':
        if lex.Peek() == '=' {
            lex.Next()
            lex.Token = EQ
        }
    case '!':
        if lex.Peek() == '=' {
            lex.Next()
            lex.Token = NE
        } else {
            lex.Token = NOT
        }
    case '<':
        if lex.Peek() == '=' {
            lex.Next()
            lex.Token = LE
        } else {
            lex.Token = LT
        }
    case '>':
        if lex.Peek() == '=' {
            lex.Next()
            lex.Token = GE
        } else {
            lex.Token = GT
        }
    }
}

// 仮引数の取得
func getParameter(lex *Lex) []Variable {
    e := make([]Variable, 0)
    if lex.Token != '(' {
        panic(fmt.Errorf("'(' expected"))
    }
    lex.getToken()
    if lex.Token == ')' {
        lex.getToken()
        return e
    }
    for {
        if lex.Token == scanner.Ident {
            e = append(e, Variable(lex.TokenText()))
            lex.getToken()
            switch lex.Token {
            case ')':
                lex.getToken()
                return e
            case ',':
                lex.getToken()
            default:
                panic(fmt.Errorf("unexpected token in parameter list"))
            }
        } else {
            panic(fmt.Errorf("unexpected token in parameter list"))
        }
    }
}


// 引数の取得
func getArgs(lex *Lex) []Expr {
    e := make([]Expr, 0)
    if lex.Token != '(' {
        panic(fmt.Errorf("'(' expected"))
    }
    lex.getToken()
    if lex.Token == ')' {
        lex.getToken()
        return e
    }
    for {
        e = append(e, expression(lex))
        switch lex.Token {
        case ')':
            lex.getToken()
            return e
        case ',':
            lex.getToken()
        default:
            panic(fmt.Errorf("unexpected token in argument list"))
        }
    }
}

// if 式の解析
func makeSel(lex *Lex) Expr {
    testForm := expression(lex)
    if lex.Token == THEN {
        lex.getToken()
        thenForm := expression(lex)
        switch lex.Token {
        case ELSE:
            lex.getToken()
            elseForm := expression(lex)
            if lex.Token != END {
                panic(fmt.Errorf("'end' expected"))
            }
            lex.getToken()
            return newSel(testForm, thenForm, elseForm)
        case END:
            lex.getToken()
            return newSel(testForm, thenForm, Value(0.0))
        default:
            panic(fmt.Errorf("'else' or 'end' expected"))
        } 
    } else {
        panic(fmt.Errorf("'then' expected"))
    }
}

// begin 式の解析
func getBody(lex *Lex) []Expr {
    body := make([]Expr, 0)
    for {
        body = append(body, expression(lex))
        switch lex.Token {
        case ',':
            lex.getToken()
        default:
            return body
        }
    }
}

func makeBegin(lex *Lex) Expr {
    if lex.Token == END {
        panic(fmt.Errorf("invalid begin form"))
    }
    body := getBody(lex)
    if lex.Token != END {
        panic(fmt.Errorf("'end' expected"))
    }
    lex.getToken()
    return newBgn(body)
}

// while 式の解析
func makeWhile(lex *Lex) Expr {
    testForm := expression(lex)
    if lex.Token == DO {
        lex.getToken()
        return newWhl(testForm, makeBegin(lex))
    } else {
        panic(fmt.Errorf("'do' expected"))
    }
}

// let 式の解析
func makeLet(lex *Lex) Expr {
    vars := make([]Variable, 0)
    vals := make([]Expr, 0)
    for {
        e := expression(lex)
        a, ok := e.(*Agn)
        if !ok {
            panic(fmt.Errorf("let: invalid assign form"))
        }
        vars = append(vars, a.name)
        vals = append(vals, a.expr)
        if lex.Token == IN {
            break
        } else if lex.Token != ',' {
            panic(fmt.Errorf("let: 'in' or ',' expected"))
        }
        lex.getToken()
    }
    lex.getToken()
    return newLet(vars, vals, makeBegin(lex))
}

// 因子
func factor(lex *Lex) Expr {
    switch lex.Token {
    case '(':
        lex.getToken()
        e := expression(lex)
        if lex.Token != ')' {
            panic(fmt.Errorf("')' expected"))
        }
        lex.getToken()
        return e
    case '+':
        lex.getToken()
        return newOp1('+', factor(lex))
    case '-':
        lex.getToken()
        return newOp1('-', factor(lex))
    case NOT:
        lex.getToken()
        return newOp1(NOT, factor(lex))
    case IF:
        lex.getToken()
        return makeSel(lex)
    case BGN:
        lex.getToken()
        return makeBegin(lex)
    case WHL:
        lex.getToken()
        return makeWhile(lex)
    case LET:
        lex.getToken()
        return makeLet(lex)
    case scanner.Int, scanner.Float:
        var n float64
        fmt.Sscan(lex.TokenText(), &n)
        lex.getToken()
        return Value(n)
    case scanner.Ident:
        name := lex.TokenText()
        lex.getToken()
        if name == "quit" {
            panic(name)
        }
        v, ok := funcTable[name]
        if ok {
            xs := getArgs(lex)
            if len(xs) != v.Argc() {
                panic(fmt.Errorf("wrong number of arguments: %v", name))
            }
            return newApp(v, xs)
        } else {
            return Variable(name)
        }
    default:
        panic(fmt.Errorf("unexpected token: %v", lex.TokenText()))
    }
}

// 項
func term(lex *Lex) Expr {
    e := factor(lex)
    for {
        switch lex.Token {
        case '*':
            lex.getToken()
            e = newOp2('*', e, factor(lex))
        case '/':
            lex.getToken()
            e = newOp2('/', e, factor(lex))
        default:
            return e
        }
    }
}

// 式
func expr3(lex *Lex) Expr {
    e := term(lex)
    for {
        switch lex.Token {
        case '+':
            lex.getToken()
            e = newOp2('+', e, term(lex))
        case '-':
            lex.getToken()
            e = newOp2('-', e, term(lex))
        default:
            return e
        }
    }
}

// 比較演算子
func expr2(lex *Lex) Expr {
    e := expr3(lex)
    x := lex.Token
    switch x {
    case EQ, NE, LT, GT, LE, GE:
        lex.getToken()
        return newOp2(x, e, expr3(lex))
    default:
        return e
    }
}

// 論理演算子
func expr1(lex *Lex) Expr {
    e := expr2(lex)
    for {
        x := lex.Token
        switch x {
        case AND, OR:
            lex.getToken()
            e = newOps(x, e, expr2(lex))
        default:
            return e
        }
    }
}

func expression(lex *Lex) Expr {
    e := expr1(lex)
    if lex.Token == '=' {
        v, ok := e.(Variable)
        if ok {
            lex.getToken()
            return newAgn(v, expression(lex))
        } else {
            panic(fmt.Errorf("invalid assign form"))
        }
    }
    return e
}

// ユーザ関数の定義
func defineFunc(lex *Lex) {
    lex.getToken()
    if lex.Token != scanner.Ident {
        panic(fmt.Errorf("invalid define form"))
    }
    name := lex.TokenText()
    lex.getToken()
    xs := getParameter(lex)    
    v, ok := funcTable[name]
    if ok {
        switch f := v.(type) {
        case *FuncU:
            if len(f.xs) != len(xs) {
                panic(fmt.Errorf("wrong number of arguments: %v", name))
            }
            body := newBgn(getBody(lex))
            if lex.Token != END {
                panic(fmt.Errorf("'end' expected"))
            }
            f.xs = xs
            f.body = body
        default:
            panic(fmt.Errorf("%v is built-in function", name))
        }
    } else {
        // 再帰呼び出し対応
        f := newFuncU(name, xs, nil)
        funcTable[name] = f
        f.body = newBgn(getBody(lex))
        if lex.Token != END {
            delete(funcTable, name)
            panic(fmt.Errorf("'end' expected"))
        }
    }
    fmt.Println(name)
}

// 式の入力と評価
func toplevel(lex *Lex) (r bool) {
    r = false
    defer func(){
        err := recover()
        if err != nil {
            mes, ok := err.(string)
            if ok && mes == "quit" {
                r = true
            } else {
                fmt.Fprintln(os.Stderr, err)
                for {
                    c := lex.Peek()
                    if c == '\n' { break }
                    lex.Next()
                }
            }
        }
    }()
    for {
        fmt.Print("Calc> ")
        lex.getToken()
        if lex.Token == DEF {
            defineFunc(lex)
        } else {
            e := expression(lex)
            if lex.Token != ';' {
                panic(fmt.Errorf("invalid expression"))
            } else {
                fmt.Println(e.Eval(nil))
            }
        }
    }
    return r
}

func main() {
    var lex Lex
    lex.Init(os.Stdin)
    initKeyTable()
    initFunc()
    for {
        if toplevel(&lex) { break }
    }
}
初版 2014 年 5 月 10 日
改訂 2021 年 12 月 22 日