電卓プログラムの作成
今回は Go 言語の簡単な例題として、中置記法で書かれた数式を計算する電卓プログラムを作ってみましょう。数値は浮動小数点数 (float64) で、四則演算 (+, -, *, /) のほかにカッコを使用することができます。式の終わりにはセミコロン ( ; ) を入力するものとします。
●プログラミング言語処理系の基本的な構造
簡単な電卓プログラムといっても、基本的な構造はプログラミング言語の処理系 (インタプリタやコンパイラ) と大きな違いはありません。たとえばコンパイラの場合、次のような構造に分けることができます。
ソースコード -> [字句解析] -> [構文解析] -> [意味解析] -> [コード生成] -> 目的コード
図 : コンパイラの構造
字句解析は入力された文字を順番に調べて、名前、数値、予約語、演算子など、意味のある「かたまり (トークン : token)」に分解します。構文解析はトークンの並びが構文規則にあっているかチェックします。構文解析を行うプログラムのことを「パーサ (parser)」と呼びます。構文的には正しいプログラムでも、意味のうえでは間違っている場合があります。これをチェックするのが意味解析です。コード生成はターゲットマシンで実行するためのコード (機械語) を生成します。機械語ではなくアセンブリコードを出力するコンパイラも多いです。
インタプリタの場合、字句解析、構文解析、意味解析まではコンパイラとほとんど同じです。コードを生成するかわりに、プログラムを解釈して実行する処理が必要になります。最も原始的な方法は、ソースコートを読み込みながら逐次実行していくことです。この場合、字句解析、構文解析、意味解析を何度も繰り返し行うことになります。簡単な方法ですが、ループなどの繰り返しがある場合、無駄な処理が多くなるため実行速度は遅くなります。
もうひとつは、字句解析、構文解析、意味解析まで行った情報を何らかの形で保存しておき、それを解釈しながら実行していくことです。一般的には、解析して得られた情報は「構文木」という形で保存されます。また、プログラムを実行するための仮想マシンを用意し、そのマシンが直接実行できるコード (バイトコードなど) を生成する方法もあります。この場合、仮想マシンがコードを読み込みながら実行していくことになります。
今回作成する電卓プログラムは式を計算するだけの簡単なものなので、字句解析と構文解析ともに難しいところはほとんどありません。構文解析は「再帰降下法」を使うと簡単にプログラムできます。
●文法の表現
ほとんどのプログラミング言語は、「文脈自由文法 (context free grammer : CFG)」という方法で文法を定義することができます。文脈自由文法は「生成文法」と呼ばれる文法の一種で、文を生成する規則を定義し、その規則によって生成される文はその文法を満たしていると考えます。逆に、文法を満たしていない文は、その規則では生成することができない、ということになります。文脈自由文法は BNF (Backus Naur Form)、それを拡張した EBNF や構文図などで表すことができます。
ここで用語について簡単に説明します。「終端記号」は対象となるプログラミング言語で使用する記号のことで、BNF や EBNF では "..." で表します。「非端記号」は BNF や EBNF で用いる記号のことで、BNF では <...> で表します。
BNF の場合、構文規則は次の形式で表します。
非端記号 ::= 定義1 | 定義2 | ... | 定義n ただし、| は「または」を表す。定義は終端記号や非端記号からなる。
簡単な例を示しましょう。a がいくつか並んだあとに b がいくつか並んだ記号列 (aa...bb...) を BNF であらわすと次のようになります。
<SeqAB> ::= <SeqA> <SeqB> <SeqA> ::= "a" | "a" <SeqA> <SeqB> ::= "b" | "b" <SeqB>
記号列を <SeqAB> とすると、a が並んだ記号列 <SeqA> のあとに b が並んだ記号列 <SeqB> が続けばいいので、定義は <SeqA> <SeqB> になります。<SeqA> は記号 "a" だけではなく "a" のあとに <SeqA> が続くパターンがあります。定義は "a" | "a" <SeqA> となります。<SeqB> も同様です。ここで、<SeqA> と <SeqB> は再帰的に定義されていることに注意してください。
この規則を適用することで、<SeqAB> を満たす任意の記号列を生成することができます。次の例を見てください。
<SeqAB> => <SeqA> <SeqB> => "a" <SeqA> <SeqB> => "a" "a" <SeqA> <SeqB> => "a" "a" "a" <SeqB> => "a" "a" "a" "b" <SeqB> => "a" "a" "a" "b" "b"
<SeqA> に定義 "a" <SeqA> を適用すると、"a" が一つ多い <SeqA> を生成することができます。定義 "a" を適用すると、そこで <SeqA> の生成は終了します。同様に <SeqB> の定義を適用することで記号列 <SeqB> を生成し、最終的には記号列 <SeqAB> を生成することができます。
文法が複雑になると BNF では読みにくくなることがあります。このような場合、EBNF を使うと便利です。EBNF で用いられる主な規則を示します。
- 非端記号は <...> で囲まない
- ::= のかわりに = を使う
- 非端記号や終端記号を並べる場合はカンマ , で区切る
- 規則の最後に記号 (セミコロンやピリオドなど) を付加する
- { α } : αの 0 回以上の繰り返し
- [ α ] : αまたは空
- ( α ) : グループ化
EBNF で用いられる記号は正規表現と似ているので、正規表現がわかる方であれば EBNF を理解するのは難しくないでしょう。
<SeqAB> を EBNF で表すと次のようになります。
SeqAB = "a", { "a" }, "b", { "b" }.
BNF よりもわかりやすいと思います。
もうひとつ簡単な例を示しましょう。整数を EBNF で表すと、次のようになります。
整数 = ["+" | "-"], 無符号整数.
無符号整数 = 数字 | 非零数字, { 数字 }.
数字 = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "0".
非零数字 = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9".
図 : 整数の EBNF
整数は +, - の符号が付いた (または省略された) 無符号整数で表すことができます。無符号整数は数字が 1 桁の場合と、2 桁以上ある場合に分けられます。桁が複数ある場合、先頭が 0 以外の数字 (非零数字) で、そのあとに数字がいくつか続きます。あとは、非零数字 と 数字 を定義するだけです。
●式の構文
次は数値と演算子 +, - *, / とカッコ ( ) を使った数式の構文を考えてみましょう。式は数値と演算子をつないだものです。演算子には優先順位があり、+, - よりも *, / の計算を先に行わなければなりません。そこで、*, / でつながれたものを「項 (term)」として定義することにします。すると、式は項を演算子 +, - でつないだものとして定義することができます。
次に項の定義について考えます。数値と演算子 *, / だけならば簡単ですが、カッコが出てきたら、その中を式として計算しなければなりません。そこで、演算子 *, / でつながれるものを「因子 (factor)」として定義します。そうすると、項は因子を演算子 *, / でつないだものとして定義することができます。最後に、因子を定義します。これは数値またはカッコで囲まれた式となります。
なお、演算子 +, -, *, / は左結合なので、同じ優先順位の演算子は左から順番に計算していくことに注意してください。この規則を BNF と EBNF で表すと次のようになります。
[BNF]
<式> ::= <項> | <式> "+" <項> | <式> "-" <項>
<項> ::= <因子> | <項> "*" <因子> | <項> "/" <因子>
<因子> ::= <数値> | "(" <式> ")"
[EBNF]
式 = 項, { ("+" | "-"), 項 }.
項 = 因子, { ("*" | "/"), 因子 }.
因子 = 数値 | "(", 式, ")".
[注意] 数値の定義は省略
たとえば、式 12 + 34 + 56 * 78 と (12 + 34 + 56) * 78 を構文木であらわすと、次のようになります。
構文木の場合、BNF の定義にそって構築すると簡単でわかりやすいでしょう。プログラムを作る場合は、EBNF の定義にそって行うと簡単です。EBNF で表した規則の左辺 (非端記号) を関数に割り当てます。右辺に出現する非端記号は対応する関数を呼び出します。終端記号は、正しい記号が現れていることを確認してそれを返します。選択 | は if や cond などで、{ } は繰り返しで表すことができます。
EBNF の定義が再帰的な構造になっているので、プログラムも再帰呼び出しの形になります。このような構文解析を「再帰降下法」と呼びます。具体的な説明はプログラムを作るところで行います。
●単項演算子
単項演算子の + と - を追加する場合、文法は次のようになります。
[EBNF]
式 = 項 { ("+" | "-"), 項 }.
項 = 因子 { ("*" | "/"), 因子 }.
因子 = 数値 | ("+" | "-"), 因子 | "(" 式 ")".
[注意] 数値の定義は省略
因子の定義に ("+" | "-"), 因子 を追加するだけです。これで +3 や -5 を処理することができます。
●字句解析
それでは字句解析からプログラムを作っていきましょう。Go 言語のパッケージ text/scanner には字句解析を行う Scanner が用意されているので、今回は Scanner を使うことにします。Scanner は UTF-8 でエンコードされたテキストを Go 言語の文法に従って解析します。今回の電卓プログラムや簡易なプログラミング言語であれば、Scanner で字句解析することが可能です。
Sccanner の使い方は簡単です。基本的には次に示す 3 つの関数 (メソッド) で字句解析を行います。
func (s *Scanner) Init(src io.Reader) *Scanner func (s *Scanner) Scan() rune func (s *Scanner) TokenText() string
Scanner は字句解析を制御するための構造体です。メソッド Init は Scanner を初期化します。このとき、ソース (テキストファイル) として io.Reader を渡します。電卓プログラムであれば、標準入力 os.Stdin を渡せばいいでしょう。
メソッド Scan はソースから空白文字と Go 言語のコメントを読み飛ばしてトークンを切り出します。返り値の型 rune は int32 の別名で、UTF-8 の文字コードを表します。Scan はトークンの種別を負の整数で返し、+ や * などの記号はその文字コードを返します。切り分けたトークンはメソッド TokenText で取り出すことができます。
トークンの種別は次のように定義されています。
リスト : トークンの種別
const (
EOF = -(iota + 1)
Ident
Int
Float
Char
String
RawString
Comment
)
EOF はファイルの終了を表します。Ident は識別子、Int は整数、Float は実数、Char は文字 ('a', 'b' など)、String は文字列 ("foo", "bar" など) を表します。
それでは実際に scanner を使ってみましょう。次のリストを見てください。
リスト : scanner の使用例 (sample1601.go)
package main
import (
"fmt"
"os"
"text/scanner"
)
func main() {
var s scanner.Scanner
s.Init(os.Stdin)
for {
fmt.Print("> ")
x := s.Scan()
fmt.Println(x, s.TokenText())
}
}
変数 s に Scanner を用意します。s.Init(os.Stdin) で Scanner を初期化し、次の for ループで標準入力からのテキストを s.Scan() で字句解析します。その結果を fmt.Println で表示します。TokenText は Scan を実行したあと有効で、そのとき切り分けたトークンを文字列にして返します。
それでは実際に試してみましょう。
$ go run sample1601.go > for -2 for > if -2 if > foo -2 foo > 12345 -3 12345 > 1.234567 -4 1.234567 > 'a' -5 'a' > "hello, world" -6 "hello, world" > * 42 * > - 45 - > ( 40 ( > ) 41 )
Scanner の場合、for や if も識別子 (Ident) として認識されます。このように、Scanner を使えば字句解析を簡単に行うことができます。
実際には、次のような構造体とメソッドを定義して、切り分けたトークンを保存しておくと便利です。
リスト : 字句解析
type Lex struct {
scanner.Scanner
Token rune
}
func (lex *Lex) getToken() {
lex.Token = lex.Scan()
}
構造体 Lex は Scanner を埋め込み、切り分けたトークンをフィールド変数 Token に格納します。メソッド getToken は Scan を呼び出してトークンを切り出し、その結果を Token にセットします。
●構文解析
次は構文解析を作りましょう。字句解析と構文解析は別々に処理することも可能ですが、今回のプログラムでは構文解析を行う処理から getToken を呼び出し、そのつど字句解析を行うことにします。プログラムは次のようになります。
リスト : 構文解析 (1)
// 式
func expression(lex *Lex) float64 {
val := term(lex)
for {
switch lex.Token {
case '+':
lex.getToken()
val += term(lex)
case '-':
lex.getToken()
val -= term(lex)
default:
return val
}
}
}
非端記号「式」に対応する関数が expression、「項」に対応する関数が term、「因子」に対応する関数が factor です。式の定義は EBNF で 項, { ("+" | "-"), 項 } です。最初に term を呼び出して項の値を変数 val にセットします。{ } に対応するのが for ループによる繰り返しです。lex.Token が +, - の場合、getToken で次のトークンを求め、term を呼び出して次の項の値を求め、val と演算を行います。lex.Token が +, - 以外の場合は val を返します。
リスト : 構文解析 (2)
// 項
func term(lex *Lex) float64 {
val := factor(lex)
for {
switch lex.Token {
case '*':
lex.getToken()
val *= factor(lex)
case '/':
lex.getToken()
val /= factor(lex)
default:
return val
}
}
}
関数 term も EBNF の定義 因子, { ("*" | "/"), 因子} と同じ処理になります。最初に factor を呼び出して因子の値を変数 val にセットします。式の処理と同様に { } に対応するのが for ループによる繰り返しです。lex.Token が *, / の場合は、getToken で次のトークンを求め、factor を呼び出して次の因子の値を求め、val と演算を行います。let.Token が *, / 以外の場合は val を返します。
リスト : 構文解析 (3)
// 因子
func factor(lex *Lex) float64 {
switch lex.Token {
case '(':
lex.getToken()
val := expression(lex)
if lex.Token != ')' {
panic(fmt.Errorf("')' expected"))
}
lex.getToken()
return val
case '+':
lex.getToken()
return factor(lex)
case '-':
lex.getToken()
return (- factor(lex))
case scanner.Int, scanner.Float:
var n float64
fmt.Sscan(lex.TokenText(), &n)
lex.getToken()
return n
case scanner.Ident:
text := lex.TokenText()
if text == "quit" {
panic(text)
}
fallthrough
default:
panic(fmt.Errorf("unexpected token: %v", lex.TokenText()))
}
}
関数 factor も EBNF の定義 数値 | ("+" | "-"), 因子 | "(" 式 ")" と同じ処理になります。lex.Token が 左カッコ '(' の場合、getToken で次のトークンを求めてから、expression を再帰呼び出しして式の値を求めます。次に、let.Token の値が右カッコ ')' であることをチェックし、右カッコがない場合は panic でエラーを送出します。右カッコの場合は、getToken で次のトークンを求めてから val を返します。
lex.Token が '+', '-' の場合は単項演算子の処理を行います。'+' の場合は、getToken で次のトークンを求めて、factor を再帰呼び出しするだけです。'-' の場合は factor の返り値の符号を反転して返すだけです。lex.Token が Int, Float の場合は、TokenText で数値を表す文字列を求め、それを fmt.Sscan に渡して数値に変換します。
lex.Token が Ident の場合、TokenText で文字列を求め、それが "quit" であれば、panic に "quit" を渡してエラーを送出します。これは電卓を終了するコマンドとして使います。それ以外の場合は panic でエラーを送出します。
●式の入力と評価
最後に式を入力して expression を評価する処理を作ります。次のリストを見てください。
リスト : 式の入力と評価
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 lex.Token != ';' {
lex.getToken()
}
}
}
}()
for {
fmt.Print("Calc> ")
lex.getToken()
val := expression(lex)
if lex.Token != ';' {
panic(fmt.Errorf("invalid expression"))
} else {
fmt.Println(val)
}
}
return r
}
func main() {
var lex Lex
lex.Init(os.Stdin)
for {
if toplevel(&lex) { break }
}
}
関数 toplevel は数式の "入力 - 評価 - 表示" を繰り返し行います。最初にプロンプト "Calc> " を表示し、getToken でトークンを切り出します。それから、 expression を評価して入力された数式を計算します。そのあと、lex.Token がセミコロン ';' かチェックします。セミコロンであれば、expression の返り値 val を表示します。そうでなければ、入力された数式に誤りがあるのでエラーを送出します。
エラーは defer 文の recover で捕捉します。エラー err が文字列 "quit" の場合は返り値 r に true をセットして toplevel を終了します。そうでなければ、標準エラー出力 os.Stderr にエラーメッセージを表示します。そして、入力データをセミコロンまでスキップします。
関数 main は変数 lex に Lex 構造体を用意します。そして、lex.Init(os.Stdin) で Scxanner を初期化します。あとは for ループの中で toplevel を呼び出します。toplevel の返り値が true の場合は break で for ループを脱出して電卓プログラムを終了します。
●実行例
それでは簡単な実行例を示します。
$ go run calc0.go Calc> 1 + 2 * 3 - 4; 3 Calc> (1 + 2) * (3 - 4); -3 Calc> -2 * -3; 6 Calc> -2 - -3; 1 Calc> -(1 + 2 * 3); -7 Calc> 1.11111 * 1.11111; 1.2345654321000001 Calc> 1.11111 / 1.11111; 1 Calc> 1 + 2 * * 3; unexpected token: * Calc> (1 + 2 * 3; ')' expected Calc> 1 + 2 * 3); invalid expression Calc> quit; $
正常に動作しているようです。興味のある方はいろいろ試してみてください。
今回はここまでです。次回は変数と組込み関数の機能を追加してみましょう。
●参考文献, URL
- 松田晋, 『実践アルゴリズム戦略 解法のテクニック 再帰降下型構文解析』, C MAGAZINE 1992 年 9 月号, ソフトバンク
- 水野順, 『スクリプト言語を作ろう』, C MAGAZINE 2000 年 5 月号, ソフトバンク
- 松浦健一郎, 『コンパイラの作成』, C MAGAZINE 2003 年 1 月号, ソフトバンク
- 高田昌之, 『インタプリタ進化論』, ＣＱ出版社, 1992
- 久野靖, 『言語プロセッサ』, 丸善株式会社, 1993
●プログラムリスト
//
// calc0.go : 電卓プログラム
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import (
"fmt"
"os"
"text/scanner"
)
// 字句解析
type Lex struct {
scanner.Scanner
Token rune
}
// トークンを求める
func (lex *Lex) getToken() {
lex.Token = lex.Scan()
}
// 因子の処理
func factor(lex *Lex) float64 {
switch lex.Token {
case '(':
lex.getToken()
val := expression(lex)
if lex.Token != ')' {
panic(fmt.Errorf("')' expected"))
}
lex.getToken()
return val
case '+':
lex.getToken()
return factor(lex)
case '-':
lex.getToken()
return (- factor(lex))
case scanner.Int, scanner.Float:
var n float64
fmt.Sscan(lex.TokenText(), &n)
lex.getToken()
return n
case scanner.Ident:
text := lex.TokenText()
if text == "quit" {
panic(text)
}
fallthrough
default:
panic(fmt.Errorf("unexpected token: %v", lex.TokenText()))
}
}
// 項の処理
func term(lex *Lex) float64 {
val := factor(lex)
for {
switch lex.Token {
case '*':
lex.getToken()
val *= factor(lex)
case '/':
lex.getToken()
val /= factor(lex)
default:
return val
}
}
}
// 式の処理
func expression(lex *Lex) float64 {
val := term(lex)
for {
switch lex.Token {
case '+':
lex.getToken()
val += term(lex)
case '-':
lex.getToken()
val -= term(lex)
default:
return val
}
}
}
// 式の入力と評価
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 lex.Token != ';' {
lex.getToken()
}
}
}
}()
for {
fmt.Print("Calc> ")
lex.getToken()
val := expression(lex)
if lex.Token != ';' {
panic(fmt.Errorf("invalid expression"))
} else {
fmt.Println(val)
}
}
return r
}
func main() {
var lex Lex
lex.Init(os.Stdin)
for {
if toplevel(&lex) { break }
}
}
改訂 2021 年 12 月 22 日