電卓を通じて、再帰下降構文解析を使った構文解析を行います。インタプリタ自作やコンパイラ自作の前段階として挑むとちょうど良いのではと思います。
ステップ1からステップ15まであり、最終的に括弧を使った式を解析できる電卓が出来上がります。各ステップは少しの書き換えだけで済むようになっています。
「大学に入ってからプログラミングを始めて、1年生でC言語を学んでいる」という人に向けて書きました。
「このステップは難しすぎる」「説明が分からない」「ここの説明は間違っている」等があれば、sou7まで連絡を頂けるとありがたいです。また、実装してみて「みてみて！電卓が実装できたよ！」というときにも連絡を頂けると嬉しいです。
参考実装はこちらにありますCommits · soukouki/c-calc · GitHub。ステップごとにコミットを分けてあるので、難しくて進められない場合は参考にしてください。
ステップ1
- 数字を受け取って、その数を出力します。
- scanfで数を受け取り、printfで表示します。
入出力例
1- ⇒
1
- ⇒
42- ⇒
42
- ⇒
ステップ2
- バッファの配列を宣言し、
scanf("%255s", buffer)のようにして標準入力から文字列を受け取る形に変更します。- 255の部分はバッファのサイズ-1にします。バッファを
char *buf[256]とした場合、バッファのサイズ-1は255になります。
- 255の部分はバッファのサイズ-1にします。バッファを
- 受け取った文字列に対して、先頭の1文字の数を取得します。
buf[0] - '0'とすると、先頭の1文字を文字から整数に変換できます。- ASCII文字列において、0から9までは連続して割り当てられています。
'5' - '0'というコードを計算すると、5になります。
- そうして出来上がった数をprintfで表示します。
- ステップ1より機能的には少し劣化しますが、次のステップを進めるための基礎になります。
- この段階ではmain関数にそのまま書いていきます。ステップ4で関数を分割します。
入出力例
1- ⇒
1
- ⇒
42- ⇒
4 - 先頭1文字しか読み込みません
- ⇒
ステップ3
- バッファの文字列の数字を読み込めるようにします。
- 実装の仕方
- 内部で「読み込んでいる数」と「読み込んでいる位置」を変数で持つようにします。
- 先頭の文字が
'0'以上'9'以下の場合は、次の操作を繰り返します。- 「読み込んでいる数」を10倍する。
- 「読み込んでいる数」に先頭の1文字の数を足す。
- 「読み込んでいる位置」を1足す。
- 数字でない文字が入ったら、そこで数を計算するのを打ち切るようにします。
入出力例
1- ⇒
1
- ⇒
42- ⇒
42
- ⇒
123- ⇒
123
- ⇒
12+34- ⇒
12 +は数字ではないので、そこで数を返すようにします。
- ⇒
ステップ4
- 数字を解析する処理を、今までmain関数に書いていたのを別の関数に分けてみます。
- 引数はなし、戻り値はint型にすると良いでしょう。
- 「入力された文字列」と「読み込んでいる位置」は、グローバル変数に保存します。
- 今回のプログラムでは、「読み込んだ結果」と「読み込んでいる位置」の2つの情報を呼び出し元に返す必要があります。それを簡単に実装するためにグローバル変数を使います。
- グローバル変数は使いすぎると良くないと言われますが、今回のプログラム程度であれば問題はないでしょう。
- 「読み込んだ結果」は関数の戻り値として返すようにします。
入出力例
1- ⇒
1
- ⇒
42- ⇒
42
- ⇒
12+34- ⇒
12
- ⇒
ステップ5
- 数・
+記号・数を受け取って、その数を計算して出力できるようにします。 - ステップ4で作った関数を2回呼び出して、値を2つ得られるようにします。
+記号を読み飛ばす処理は「読み込んでいる位置」を1足してあげることで実装できます。
入出力例
1+2- ⇒
3
- ⇒
12+34- ⇒
46
- ⇒
1+2+3- ⇒
3 - 数は2つまで計算できます。3つ目はまだ計算しません。
- ⇒
ステップ6
- 数・
+記号・数の他に、数だけの式を表示出来るようにします。 - 数を解析したあと、先頭の文字が
+記号なのか、そうでないのかを判定するようにします。- C言語の文字列は、文字の終端にヌル文字という文字が入っています。
- ヌル文字はASCIIにおいて数0で表されています。
- C言語では、
'\0'とするとヌル文字を表します。
- 先頭の文字が
+記号であれば、次の処理を行います。- 「読み込んでいる位置」に1を足して、次の文字に移ります。
- 数を解析し、結果を足します。
- 先頭の文字が
+記号でなければ、1つ目の数を返します。
入出力例
1- ⇒
1
- ⇒
1+2- ⇒
3
- ⇒
123+456- ⇒
579
- ⇒
579- ⇒
579
- ⇒
1+2+3- ⇒
3 - 数は2つまで計算できます。3つ目はまだ計算しません。
- ⇒
ステップ7
- 今まで数は1つか2つしか足し算出来ませんでした。
- ステップ7では、ループを使ってたくさんの数の足し算が出来るようにします。
- 最初に数を解析したあと、先頭の文字が
+記号である限り、次の処理を繰り返します。+記号を読み飛ばす。- 数を解析する。
- 最初に解析した数に対して、新しく解析した数を加算する。
入出力例
1- ⇒
1
- ⇒
1+2- ⇒
3
- ⇒
1+2+3- ⇒
6
- ⇒
1+2+3+4+5+6+7+8+9+10- ⇒
55
- ⇒
ステップ8
- これまで足し算だけを実装してきました。
- ステップ8では、引き算も出来るようにします。
- ループの判定条件を、「先頭の文字が
+記号である、または、先頭の文字が-記号である」という条件に変更します。 - 今まで
+記号を読み飛ばす処理を入れていたところに、+記号の場合と-記号の場合で条件分岐をするようにします。+記号の場合は足し算を、-記号の場合は引き算をするようにします。
入出力例
1- ⇒
1
- ⇒
1+2- ⇒
3
- ⇒
1-2- ⇒
-1
- ⇒
1+2+3- ⇒
6
- ⇒
1+2-3- ⇒
0
- ⇒
ステップ9
- これまで、足し算と引き算だけの式を解析する処理をmain関数に書いていましたが、これを分離して、新たな関数に切り分けてみます。
- scanfとprintfはmain関数に置いておいて、その間の処理を別の関数に切り分けます。
- 戻り値として、足し算と引き算を実行した結果を返すようにします。
入出力例
- ステップ8と同じ
ステップ10
- 一旦足し算と引き算を忘れて、掛け算と割り算の式を解析するようにしてみます。
- ステップ9で作った関数をコピーして、掛け算と割り算の処理に書き換えてみましょう。
- 注意 : 足し算と引き算だけの式を解析する関数は残しておきます。この後使います。
+記号を*記号に、-記号を/記号に書き換えます。- 足し算を掛け算に、引き算を割り算に書き換えます。
入出力例
1- ⇒
1
- ⇒
42- ⇒
42
- ⇒
1*2- ⇒
2
- ⇒
4/2- ⇒
2
- ⇒
2*3/5- ⇒
1
- ⇒
10/2*3- ⇒
15
- ⇒
12*34/56- ⇒
7
- ⇒
ステップ11
- main関数で呼び出す関数を「足し算と引き算の解析」に置き換えます。
- 「足し算と引き算の解析」内の、「数を解析」を呼び出す部分を「掛け算と割り算の解析」を呼び出すように置き換えます。
- すると、足し算と掛け算が混ざった式を解析できるようになります。
- 理論的なことを言うと、この式を読み込む処理は構文解析という処理になっていて、再帰下降構文解析というアルゴリズムを実装したことになります(まだ再帰してないけれど)。
- 再帰下降構文解析 - Wikipedia
- 内側で呼ばれる関数ほど優先順位が高い演算になります。
- 関数呼び出しは「足し算と引き算の解析」→「掛け算と割り算の解析」という順番になっています。
- 演算子の優先順位は(低)「足し算と引き算」<「掛け算と割り算」(高)という順番になっています。
- ここまで実装すると、括弧のない式を計算できる電卓として使えるようになります。
入出力例
1- ⇒
1
- ⇒
11-10- ⇒
1
- ⇒
1+2*3- ⇒
7 - 掛け算が先に計算されています！
- ⇒
1*2+3- ⇒
5
- ⇒
10+10/3- ⇒
13
- ⇒
ステップ12
- 一旦加減乗除ができる計算機を忘れて、数を解析する部分を改良します。
- main関数の「足し算と引き算の解析」の関数呼び出しの部分を「数の解析」の関数呼び出しに置き換えます。
- 「数の解析」部分に、文字列の先頭に
+記号と-記号がある場合の処理を書き加えます。 +記号があるときはそのまま、-記号があるときには結果の値を-1倍するようにします。
入出力例
42- ⇒
42
- ⇒
+42- ⇒
42
- ⇒
-42- ⇒
-42
- ⇒
ステップ13
- main関数の「数の解析」の関数呼び出しを「足し算と引き算の解析」の関数呼び出しに置き換えてみます。
- すると、
+10--5のような式が解析できるようになります。
入出力例
42- ⇒
42
- ⇒
4*10+2- ⇒
42
- ⇒
10*-4-2- ⇒
-42
- ⇒
40--2- ⇒
42
- ⇒
+40--2- ⇒
42
- ⇒
ステップ14
- 新たに「括弧に入った式もしくは数の解析」という関数を作り、main関数の「足し算と引き算の解析」の関数呼び出しを新たに作った関数に置き換えます。
- 「括弧に入った式もしくは数の解析」は、以下のような処理を行います。
- 先頭の文字が
(記号なら、以下の処理を行います。(記号を読み飛ばします。- 「足し算と引き算の解析」を呼び出します。
)記号を読み飛ばします。
- 先頭の文字が
(記号でないなら、「数の解析」を呼び出します。
- 先頭の文字が
入出力例
42- ⇒
42
- ⇒
(10*4+2)- ⇒
42
- ⇒
ステップ15
- main関数で呼び出す処理を「足し算と掛け算の解析」に戻します。
- 「掛け算と割り算の解析」の中の「数の解析」の部分を、「括弧に入った式もしくは数の解析」に置き換えます。
- これで、括弧のある四則演算がすべて実装できたことになります！
入出力例
42- ⇒
42
- ⇒
(42)- ⇒
42
- ⇒
((42))- ⇒
42
- ⇒
2*(10*2+1)- ⇒
42
- ⇒
次のステップ
これで電卓が完成しました。
ここからは、いくつか発展的な機能を紹介します。これらの中から選んで実装してみると良い経験になると思います。
基本的な追加機能
基本的な機能です。とりあえずこれを実装しておくと良いでしょう。
- 複数の式を解析できるようにする。
- 難易度 : 低
- main関数に無限ループを入れてみましょう。
- 終了させるための処理も入れましょう。判定の仕方は次の2つがあります。
- 入力された文字列が
quitやexitであるとき - scanfの戻り値が-1(
Ctrl+dを押したとき)であるとき
- 入力された文字列が
- 剰余算(
%)を追加する。- 難易度 : 低
- 掛け算・割り算と同じ優先順位なので、同じ関数で解析すると良いでしょう。
- ビット演算(
&,|,^,!)を追加する。- 難易度 : 低
- 演算子の優先順位に気をつけましょう。
- エラーを表示するようにする。
- 難易度 : 低
- 数字が来るべき箇所に数字が来ていなかったり、式を読み込んだ後に文字列が残っていたりするときにエラーを表示して、ユーザーに知らせてあげましょう。
- 空白を読み飛ばすようにする。
- 難易度 : 中
- 式の解析をする関数を呼び出す前に、式中の空白を削るような処理を入れる必要があります。
- これを発展させたものが字句解析と言われる処理になります。
- 変数の代入と参照を追加する。
- 難易度 : 中
- 変数名は1文字に制限すると、配列で管理できて楽でしょう。
- 先に複数の式を解析できるようにしましょう。
便利な電卓に向けた追加機能
電卓としての機能を突き詰めていく方向性です。後述するインタプリタに向けた機能とは干渉する部分も多いので、どちらかを選ぶと良いでしょう。
- 浮動小数点数 (double型)を使い、小数の計算が出来るようにしてみる。
- 難易度 : 低
- たくさんの箇所を置き換える必要があるので、そこが大変かもしれません。
sin(90.0)のように、関数の呼び出しが出来るようにする。- 難易度 : 低
- それぞれの関数ごとに構文を分けてあげると簡単に実装できるでしょう。
- ダイスロール(
2d6,1d100のようなもの)を追加する。- 難易度 : 低
- TRPGで使うダイスロールを出来るようにしましょう
- 計算の途中式を表示できるようにする。
- 難易度 : 高
- 「どのような式なのか」という情報を保持してやる必要があります。
- 「どのような式なのか」という情報のことを、構文木と言います。
- 詳しくはRui Ueyamaさんの低レイヤを知りたい人のためのCコンパイラ作成入門 - 木構造による文法構造の表現を参照してください。
- 連立1次方程式を解けるようにする。
プログラミング言語に向けた追加機能
よりプログラミング言語として使えるように進むことも出来ます。
- 複数文字の変数に対応する。
- 関数を定義できるようにする。
- 難易度 : めっちゃ高い
- 関数の中身である構文木を保持する必要があり、そのための修正箇所が結構あります。
- 文字列を追加する。
- 難易度 : 高
- 各処理の結果が「数」なのか「文字列」なのかを区別出来るようにする必要があります。
- 文字列を処理する関数も一緒に追加してみましょう。
- 条件分岐を追加する。
- 難易度 : 高
- 判定するための関数や演算子も同時に実装しましょう。
- C言語では真を0以外、偽を0にしています。これを踏襲すると実装しやすいでしょう。
- 電卓上で電卓を実装する。
- 難易度 : めちゃくちゃ高い
- これが出来たら凄いカッコいいです。
更にその先のステップ
電卓を発展させると、プログラム言語を処理できるようになります。プログラム言語の実装について書いてある本やサイトとして、次のようなものがあります。さらなるステップアップとして挑戦すると良いでしょう。
- Go言語で作るインタプリタ
- C言語ではなく、Go言語という言語でインタプリタを実装します。
- インタプリタの作り方 －言語設計／開発の基本と2つの方式による実装－
- 結構詳しい話までやるようです。
- 筆者は読んだことは無いのですが、評判は良いと聞きます。
- 低レイヤを知りたい人のためのCコンパイラ作成入門