前回は四則演算を行う簡単な電卓プログラムを作りました。今回は電卓プログラムに「変数」と「関数」の機能を追加してみましょう。
前回作成した電卓は、計算結果を表示したあとそれを保持していないので、計算結果を再利用することができません。一般の電卓のように、計算結果を記憶しておくメモリ機能があると便利です。この機能を「変数 (variable)」として実現することにします。プログラミング言語で言えば、大域変数 (グローバル変数) と同じ機能になります。
変数を実装するのであれば、変数に値を代入する操作が必要になります。これには二つの方法があり、一つは文法に「文」を定義する、つまり「代入文」を追加する方法です。もう一つが代入演算子 "=" を用意して式の中で処理する方法です。前回作成したプログラムを改造するのであれば、代入文を追加するほうが簡単です。
文法は次のようになります。
[EBNF]
文 = 代入文 | 式.
代入文 = "set", 変数, 式.
式 = 項, { ("+" | "-"), 項 }.
項 = 因子, { ("*" | "/"), 因子 }.
因子 = 数値 | ("+" | "-"), 因子 | "(", 式, ")" | 変数.
変数 = 識別子
[注意] 数値と識別子の定義は省略
最初に「文」を 代入文 | 式 と定義します。式の定義は今までと同じです。代入文は "set", 変数, 式 とします。一般に、再帰降下法で構文解析を行う場合、一番左側のトークンをみるだけで処理を決定できるように文法を定義するのが普通です。もしも、代入文を 変数, "=", 式. と定義すると、一番左側の変数をみただけでは、それが代入文なのか因子なのか区別することができません。代入文と判定するには、トークンを先読みしないといけないのです。そこで、今回は識別子 set を使って代入文を実装することにします。
それから、因子に「変数」を追加します。変数の定義は「識別子」とし、識別子は先頭文字がアルファベットで、それ以降がアルファベット、数字、アンダーバーで構成されるものとします。今回の電卓プログラムでは識別子を表すデータ型を定義します。これを「シンボル (Symbol)」と呼ぶことにしましょう。シンボルには自分の名前と値を格納する領域を用意します。
次は文法に関数を追加しましょう。関数の処理は「因子」に追加します。
[EBNF]
文 = 代入文 | 式.
代入文 = "set", 変数, 式.
式 = 項, { ("+" | "-"), 項 }.
項 = 因子, { ("*" | "/"), 因子 }.
因子 = 数値 | ("+" | "-"), 因子 | "(", 式, ")" | 変数 | 関数, "(", 引数リスト, ")".
変数 = 識別子
関数 = 識別子
引数リスト = 式, { ",", 式 }.
[注意] 数値と識別子の定義は省略
関数の名前は識別子とし、そのあとに引数をカッコで囲んで渡します。カッコの中は「引数リスト」として定義します。これは「式」をカンマで区切って並べたもので、一般的な手続き型言語の関数呼び出しと同じ形式になります。
ただし、変数と関数は同じ識別子なので、このままでは区別することができません。そこで、シンボルに格納されているデータの種別を表すメンバ変数 type を用意することにします。たとえば、type の値が 0 ならば数値を保持していて、それ以外の場合は関数へのポインタを保持しているとします。
それではプログラムを作ります。最初に、シンボルを表すデータ型を定義します。
リスト : シンボルの定義
// 名前の最大長
#define SYM_NAME_SIZE 32
// シンボル
typedef struct {
char name[SYM_NAME_SIZE + 1];
int type;
union {
double val; // 数値
void *ref_val; // 参照型
};
} Symbol;
// シンボル表
#define SYM_TBL_SIZE 512
Symbol sym_table[SYM_TBL_SIZE];
int sym_count;
構造体 Symbol がシンボルを表します。メンバ変数 name がシンボル名で、最大長は 32 文字までとしました。メンバ変数 type でシンボルに格納されている値の種別を表します。0 が数値を格納する val、それ以外は ref_val にポインタをセットします。1 が 1 引数の関数へのポインタ、2 が 2 引数の関数へのポインタを表します。最新の規格 (C11) で導入された「無名の共用体」を使っていることに注意してください。シンボルは配列 sym_table に格納します。今回は簡単な電卓プログラムなので、シンボルの個数は最大で 512 としました。
なお、今回のプログラムではシンボルに格納するデータの種類が限られているので、シンボルは次のように定義したほうがわかりやすいかもしれません。
リスト : シンボルの定義 (2)
typedef struct {
char name[SYM_NAME_SIZE + 1];
int type;
union {
double val;
double (*func1)(double); // 1 引数の関数
double (*func2)(double, double); // 2 引数の関数
};
} Symbol;
次は必要となる外部変数とトークンを追加します。
リスト : 外部変数とトークン
// 外部変数
int ch; // 記号
int token; // トークン
double value; // 値
Symbol *symbol; // シンボル
jmp_buf err; // エラー脱出用
// トークン
enum {Eof, Number, Ident, Add, Sub, Mul, Div,
Lpar, Rpar, Semic, Comma, Others};
// トークン名
char *token_name[] = {
"EOF",
"Number",
"Ident",
"+",
"-",
"*",
"/",
"(",
")",
";",
",",
"Others",
};
トークン Ident が識別子で、Comma がカンマ ( , ) を表します。外部変数 symbol は、トークンが Ident のとき、それに対応するシンボルを格納します。
次は、シンボルの操作関数を作りましょう。配列 sym_table から同じ名前のシンボルを探す関数 lookup は次のようになります。
リスト : シンボルの探索
Symbol *lookup(const char *name)
{
for (int i = 0; i < sym_count; i++) {
Symbol *sym = &sym_table[i];
if (strcmp(sym->name, name) == 0) return sym;
}
return NULL;
}
lookup は配列 sym_table から引数 name と同じシンボルを線形探索します。見つからない場合は NULL を返します。今回は簡単な電卓プログラムなので線形探索にしましたが、二分探索木やハッシュ法を使うと高速に探索することができます。興味のある方はプログラムを改良してみてください。
次は新しいシンボルを生成する関数 gensym を作ります。
リスト : シンボルの生成
Symbol *gensym(const char *name)
{
if (sym_count >= SYM_TBL_SIZE) error("Symbol table is full");
Symbol *sym = &sym_table[sym_count++];
strcpy(sym->name, name);
sym->val = 0;
sym->type = 0;
return sym;
}
sym_count が SYM_TBL_SIZE 以上であれば、sym_table は満杯なので error でエラーを送出します。そうでなければ、sym_table から一つシンボルを取得して、name を sym->name にコピーして、sym->type と sym->val を 0 に初期化します。
次は組み込み関数を初期化する関数 init_func を作ります。
リスト : 組み込み関数の初期化
void init_func1(const char *name, double (*func)(double))
{
Symbol *sym = gensym(name);
sym->type = 1;
sym->ref_val = func;
}
void init_func2(const char *name, double (*func)(double, double))
{
Symbol *sym = gensym(name);
sym->type = 2;
sym->ref_val = func;
}
void init_func(void)
{
init_func1("sqrt", sqrt);
init_func2("fmod", fmod);
init_func2("pow", pow);
init_func1("exp", exp);
init_func1("log", log);
init_func1("log10", log10);
init_func1("fabs", fabs);
init_func1("ceil", ceil);
init_func1("floor", floor);
init_func1("sin", sin);
init_func1("cos", cos);
init_func1("tan", tan);
init_func1("asin", asin);
init_func1("acos", acos);
init_func1("atan", atan);
init_func2("atan2", atan2);
init_func1("sinh", sinh);
init_func1("cosh", cosh);
init_func1("tanh", tanh);
}
init_func1 は 1 引数の関数を、init_func2 は 2 引数の関数をシンボルにセットします。組み込み関数はＣ言語の標準ライブラリ (math.h) に定義されているものを使います。
次は関数 get_token を修正します。
リスト : 字句解析の修正
// シンボル (識別子) を取得する
Symbol *get_ident(void)
{
char name[SYM_NAME_SIZE + 1];
int i = 0;
name[i++] = getch();
nextch();
while (true) {
int c = getch();
if (!isalnum(c) && c != '_') break;
name[i++] = c;
if (i > SYM_NAME_SIZE)
error("symbol name is too long");
nextch();
}
name[i] = '\0';
Symbol *sym = lookup(name);
if (sym == NULL)
sym = gensym(name);
return sym;
}
// トークンの切り分け
void get_token(void)
{
// 空白文字の読み飛ばし
while (isspace(getch())) nextch();
if (isdigit(getch())) {
token = Number;
value = get_number();
} else if (isalpha(getch())) {
token = Ident;
symbol = get_ident();
} else {
switch(getch()){
case '+':
token = Add;
nextch();
break;
case '-':
token = Sub;
nextch();
break;
case '*':
token = Mul;
nextch();
break;
case '/':
token = Div;
nextch();
break;
case '(':
token = Lpar;
nextch();
break;
case ')':
token = Rpar;
nextch();
break;
case ';':
token = Semic;
nextch();
break;
case ',':
token = Comma;
nextch();
break;
case EOF:
token = Eof;
break;
default:
token = Others;
}
}
}
記号がアルファベットの場合は関数 get_ident で識別子を切り分けます。アルファベットは ctype.h の関数 isalpha で判定することができます。token にはトークン Ident をセットし、get_ident の返り値を外部変数 symbol にセットします。get_ident では、記号がアルファベット、数値、アンダーバーであれば配列 buff に格納します。アルファベットまたは数値の判定は ctype.h の関数 isalnum で判定することができます。名前が 32 文字よりも長い場合はエラーを送出します。
最後に buff をヌル文字で終端し、lookup で同じ名前のシンボルがないかチェックします。見つからない場合は gensym で新しいシンボルを生成して返します。あとは、カンマ ',' が入力された場合、それを表すトークン Comma を token にセットするだけです。
次は関数 factor を修正します。
リスト : 因子の修正
// 引数の取得
void get_argument(int argc, double *argv)
{
int i = 0;
get_token();
while (true) {
argv[i++] = expression();
if (token == Rpar) {
if (i < argc) error("wrong number of arguments");
get_token();
break;
} else if (token == Comma) {
if (i >= argc) error("wrong number of arguments");
get_token();
} else
error("unexpected token in argument list");
}
}
// 因子
double factor(void)
{
double val, args[2];
Symbol *sym;
switch (token) {
case Lpar:
get_token();
val = expression();
if (token == Rpar)
get_token();
else
error("')' expected");
return val;
case Number:
get_token();
return value;
case Add:
get_token();
return factor();
case Sub:
get_token();
return - factor();
case Ident:
sym = symbol;
get_token();
if (sym->type == 0)
// 変数の値を返す
return sym->val;
else if (sym->type > 0) {
// 関数呼び出し
if (token != Lpar) error("'(' expected");
get_argument(sym->type, args);
if (sym->type == 1) {
double (*func1)(double) = sym->ref_val;
return func1(args[0]);
} else {
double (*func2)(double, double) = sym->ref_val;
return func2(args[0], args[1]);
}
}
default:
error("unexpected token");
}
}
token が Ident の場合、外部変数 symbol の値を変数 sym にセットしてから get_token を呼び出します。それから sym->type の値をチェックし、0 ならば変数の値 sym->val を返します。sym->type の値が 0 より大きければ関数呼び出しの処理を行います。
まず、token が左カッコ (lpar) であることを確認します。そうでなければエラーを送出します。あとは、関数 get_argument で実引数を取得し、格納されている関数を呼び出します。get_argument はカンマで区切られた式を expression で評価し、それを配列 argv に格納します。そのあと token が右カッコ (Rpar) の場合、引数の個数をチェックして、不足していればエラーを送出します。
そうでなければ、break で while ループを脱出します。token が Comma の場合、引数の個数をチェックして、argc 以上であれば引数が多いのでエラーを送出します。そうでなければ get_token を呼び出して、次の引数を取得します。token がそれ以外の値であれば、式に誤りがあるのでエラーを送出します。
最後に、関数 toplevel を修正します。
リスト : 式の入力と評価
void toplevel(void)
{
double val;
if (token == Ident && strcmp(symbol->name, "set") == 0) {
// 代入文の処理
get_token();
if (token != Ident) error("invalid set form");
Symbol *sym = symbol;
get_token();
val = expression();
if (token != Semic) error("invalid token");
sym->val = val;
} else {
val = expression();
if (token != Semic) error("invalid token");
}
printf("=> %.14g\nCalc> ", val);
fflush(stdout);
}
token が Ident で symbol->name が set の場合、変数への代入処理を行います。そうでなければ「式」として評価します。代入処理の場合、get_token で次のトークンを求め、それが Ident でなければ識別子でないのでエラーを送出します。
次に、symbol の値を変数 sym にセットして、get_token で次のトークンを取り出してから expression で式を評価します。返り値は変数 val にセットします。そのあと token をチェックして、セミコロンでなければエラーを送出します。最後に、sym->val に val をセットします。これで変数に値を代入することができます。
あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト をお読みください。
それでは実行してみましょう。
Calc> set a 10; => 10 Calc> a; => 10 Calc> a * 10 + 20; => 120 Calc> set b a * 10 + 20; => 120 Calc> b; => 120 Calc> a + b; => 130 Calc> p; => 0 Calc> set q q + 1; => 1 Calc> q; => 1
変数に値を代入すると、その値を使って式を評価することができます。今回の電卓プログラムでは、新しい変数は 0 に初期化されます。たとえば、まだ値を代入していない変数 p の値は 0 になります。したがって、set q q + 1 のようなこともできます。
次は組み込み関数を実行してみましょう。
Calc> sqrt(2); => 1.4142135623731 Calc> pow(2, 32) - 1; => 4294967295 Calc> set PI asin(0.5) * 6; => 3.1415926535898 Calc> sin(0); => 0 Calc> sin(PI/2); => 1 Calc> sin(PI); => -3.2162452993533e-16
正常に動作していますね。興味のある方はいろいろ試してみてください。
//
// calc1.c : 電卓プログラム (変数と組み込み関数の追加)
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>
#include <setjmp.h>
#include <math.h>
// 名前の最大長
#define SYM_NAME_SIZE 32
// シンボル
typedef struct {
char name[SYM_NAME_SIZE + 1];
int type;
union {
double val; // 数値
void *ref_val; // 参照型
};
} Symbol;
// シンボル表
#define SYM_TBL_SIZE 512
Symbol sym_table[SYM_TBL_SIZE];
int sym_count;
// 外部変数
int ch; // 記号
int token; // トークン
double value; // 値
Symbol *symbol; // シンボル
jmp_buf err; // エラー脱出用
// トークン
enum {Eof, Number, Ident, Add, Sub, Mul, Div,
Lpar, Rpar, Semic, Comma, Others};
// トークン名
char *token_name[] = {
"EOF",
"Number",
"Ident",
"+",
"-",
"*",
"/",
"(",
")",
";",
",",
"Others",
};
// 記号の先読み
void nextch(void)
{
ch = getchar();
}
// 先読み記号の取得
int getch(void)
{
return ch;
}
// エラー
_Noreturn
void error(char *mes)
{
fprintf(stderr, "%s, %s\n", mes, token_name[token]);
longjmp(err, 1);
}
// シンボルの探索
Symbol *lookup(const char *name)
{
for (int i = 0; i < sym_count; i++) {
Symbol *sym = &sym_table[i];
if (strcmp(sym->name, name) == 0) return sym;
}
return NULL;
}
// シンボルの生成
Symbol *gensym(const char *name)
{
if (sym_count >= SYM_TBL_SIZE) error("Symbol table is full");
Symbol *sym = &sym_table[sym_count++];
strcpy(sym->name, name);
sym->val = 0;
sym->type = 0;
return sym;
}
// 組み込み関数の初期化
void init_func1(const char *name, double (*func)(double))
{
Symbol *sym = gensym(name);
sym->type = 1;
sym->ref_val = func;
}
void init_func2(const char *name, double (*func)(double, double))
{
Symbol *sym = gensym(name);
sym->type = 2;
sym->ref_val = func;
}
void init_func(void)
{
init_func1("sqrt", sqrt);
init_func2("fmod", fmod);
init_func2("pow", pow);
init_func1("exp", exp);
init_func1("log", log);
init_func1("log10", log10);
init_func1("fabs", fabs);
init_func1("ceil", ceil);
init_func1("floor", floor);
init_func1("sin", sin);
init_func1("cos", cos);
init_func1("tan", tan);
init_func1("asin", asin);
init_func1("acos", acos);
init_func1("atan", atan);
init_func2("atan2", atan2);
init_func1("sinh", sinh);
init_func1("cosh", cosh);
init_func1("tanh", tanh);
}
// シンボル (識別子) を取得する
Symbol *get_ident(void)
{
char name[SYM_NAME_SIZE + 1];
int i = 0;
name[i++] = getch();
nextch();
while (true) {
int c = getch();
if (!isalnum(c) && c != '_') break;
name[i++] = c;
if (i > SYM_NAME_SIZE)
error("symbol name is too long");
nextch();
}
name[i] = '\0';
Symbol *sym = lookup(name);
if (sym == NULL)
sym = gensym(name);
return sym;
}
#define SIZE 1024
// 整数部をバッファに格納する
int get_fixnum(char *buff, int i)
{
while (isdigit(getch())) {
buff[i++] = getch();
nextch();
}
return i;
}
// 数値を求める
double get_number(void)
{
char buff[SIZE + 1];
char *err;
int i = get_fixnum(buff, 0);
if (getch() == '.') {
buff[i++] = getch();
nextch();
i = get_fixnum(buff,i);
}
if (getch() == 'e' || getch() == 'E') {
buff[i++] = getch();
nextch();
if (getch() == '+' || getch() == '-') {
buff[i++] = getch();
nextch();
}
i = get_fixnum(buff, i);
}
buff[i] = '\0';
double val = strtod(buff, &err);
if (*err != '\0')
error("get_number: not Number\n");
return val;
}
// トークンの切り分け
void get_token(void)
{
// 空白文字の読み飛ばし
while (isspace(getch())) nextch();
if (isdigit(getch())) {
token = Number;
value = get_number();
} else if (isalpha(getch())) {
token = Ident;
symbol = get_ident();
} else {
switch(getch()){
case '+':
token = Add;
nextch();
break;
case '-':
token = Sub;
nextch();
break;
case '*':
token = Mul;
nextch();
break;
case '/':
token = Div;
nextch();
break;
case '(':
token = Lpar;
nextch();
break;
case ')':
token = Rpar;
nextch();
break;
case ';':
token = Semic;
nextch();
break;
case ',':
token = Comma;
nextch();
break;
case EOF:
token = Eof;
break;
default:
token = Others;
}
}
}
// 構文解析
double expression(void);
double term(void);
double factor(void);
double expression(void)
{
double val = term();
while (true) {
switch (token) {
case Add:
get_token();
val += term();;
break;
case Sub:
get_token();
val -= term();
break;
default:
return val;
}
}
}
double term(void)
{
double val = factor();
while (true) {
switch (token) {
case Mul:
get_token();
val *= factor();
break;
case Div:
get_token();
val /= factor();
break;
default:
return val;
}
}
}
// 引数の取得
void get_argument(int argc, double *argv)
{
int i = 0;
get_token();
while (true) {
argv[i++] = expression();
if (token == Rpar) {
if (i < argc) error("wrong number of arguments");
get_token();
break;
} else if (token == Comma) {
if (i >= argc) error("wrong number of arguments");
get_token();
} else
error("unexpected token in argument list");
}
}
// 因子
double factor(void)
{
double val, args[2];
Symbol *sym;
switch (token) {
case Lpar:
get_token();
val = expression();
if (token == Rpar)
get_token();
else
error("')' expected");
return val;
case Number:
get_token();
return value;
case Add:
get_token();
return factor();
case Sub:
get_token();
return - factor();
case Ident:
sym = symbol;
get_token();
if (sym->type == 0)
// 変数の値を返す
return sym->val;
else if (sym->type > 0) {
// 関数呼び出し
if (token != Lpar) error("'(' expected");
get_argument(sym->type, args);
if (sym->type == 1) {
double (*func1)(double) = sym->ref_val;
return func1(args[0]);
} else {
double (*func2)(double, double) = sym->ref_val;
return func2(args[0], args[1]);
}
}
default:
error("unexpected token");
}
}
void toplevel(void)
{
double val;
if (token == Ident && strcmp(symbol->name, "set") == 0) {
// 代入文の処理
get_token();
if (token != Ident) error("invalid set form");
Symbol *sym = symbol;
get_token();
val = expression();
if (token != Semic) error("invalid token");
sym->val = val;
} else {
val = expression();
if (token != Semic) error("invalid token");
}
printf("=> %.14g\nCalc> ", val);
fflush(stdout);
}
int main(void)
{
init_func(); // 組み込み関数の初期化
printf("Calc> ");
fflush(stdout);
nextch();
while (true) {
if (!setjmp(err)) {
get_token();
if (token == Eof) break;
toplevel();
} else {
// 入力のクリア
while (getch() != '\n') nextch();
printf("Calc> ");
fflush(stdout);
}
}
printf("bye\n");
return 0;
}