I have finish the report! so next time, I'll study a backend of language processor!
but, now for a computational intelligence programming, namely "prolog"!
because its deadline is coming soon! lol
目次
1. 入力文字列の構文規則
2. 電卓を設計した過程
3. ソースプログラムの説明
3.1 字句解析
3.2 構文解析
3.3 意味解析
3.4 誤り処理
3.5 main関数
4. 実行例
5. 設計した電卓のソースプログラム
(!!CAUTAION!!:some indents were omitted)
1. 入力文字列の構文規則
以下に、今回設計した電卓プログラム(以下、本プログラム)の構文規則を示す。
expression = [ '-' | '+' ] term { ( '+' | '-' ) term }
term = primary { ( '*' | '/' | '%' ) primary }
primary = character | figure | '(' expression ')' | '[' expression ']'
character = ID [ '=' expression ]
figure = {number} [ '.' {number}]
number = 0|1|2|3|4|5|6|7|8|9
ID = 英文字(大文字、小文字含む)
ただし、ID = expression1 * expression2のような入力文字列が与えられた場合、ID = (expression1 * expression2)としてIDへの代入処理が行われる。
ID にexpression1だけを代入して、その結果とexpression2を計算させたい場合は、
( ID = expression1 ) * expression2 のように、括弧を使って明示的に示す必要がある。
2. 電卓を設計した過程
電卓を設計する上でまず始めに考えたことは、与えられた仕様を満たすように入力文字列の構文規則を設計することである。このとき構文規則は、後の具現化の作業が容易になるように、再帰降下法が適用できる形にした。こうして出来上がった構文規則が1.で示した構文規則である。
次に、具体的な字句解析の方法を考えると同時に、具現化の作業を行った。このとき、WL言語や教材ページの簡易電卓で使われている字句解析を参考にして、設計を行った。
その後、変数の登録・代入の設計方針と誤り処理の設計方針についてはひとまず置いておき、まずはここまでの仕様を具現化した。しかしながら、誤りが起こったときの処理で関数errorを呼び出して扱うことは明白だったので、誤りが構文規則以外の文字を読み取ったときには、ひとまず関数errorを呼び出して置くようにした。
代入と誤り処理以外の仕様をすべて満たす電卓が完成したら、次に代入の設計方針を固める作業を行った。代入の設計方針としては、英字列を読み取ったとき、代入文とともに呼び出される場合と、そうでない場合の２通りがあることに留意しながら設計を行った。このとき、代入文とともに呼び出される場合は、英字列と値の同期付けを行い、その結果をなんらかの方法で表に登録する必要がある。今回設計した電卓では、登録、または登録された英字列を読み出す方法として、ハッシュ法を採用した。そして、これらの設計方針を基にして、代入の具現化を行った。
最後に、誤り処理の設計を行った。しかしながら、誤り処理については具体的な設計アルゴリズムが思いつかなかったので、出来るだけjavaやCコンパイラの誤り処理に近づけるようにして設計する、という方針を採用した。具体的な設計方針としては、入力文字列のどこの部分がどのように間違えているのかを出来るだけ明確にして出力する、また、誤りが複数ある場合は、その誤りの数だけ指摘できる誤り処理がする、という設計方針を立てた。これらの設計方針に基づき、誤り処理の具現を行い、今回設計した電卓が完成した。
3. ソースプログラムの説明
本項では本プログラムのソースプログラムを解説する。具体的には、ソースプログラムを字句解析部、構文解析部、代入の処理部、誤りの処理部、そしてmain関数部の5つの部分に分けて、各部分について一つずつ解説を行っていく。
3.1 字句解析
本プログラムは、WL言語と同様に1次先読みの字句解析を行うようにしている。以下は、本プログラムで使用する1次先読みの字句解析プログラムの解説である。
字句解析を行うにあたり、まずは入力文字列を読み込む必要があるので、入力文字列を読み込み、読み込んだ文字列を配列charsに格納する関数get_line()を作成した。この関数では、入力文字列を関数getchar()を用いて、’\n’が押されるまでの間、入力文字を読み取り続けている。関数get_char()が’\n’を読み取ったとき、入力文字列が空行であればFalseを、一文字以上存在していればTrueを返している。これにより、与えられた仕様の”からの行を入力すると終了する”という部分の具現が容易になる。
次に、配列charsに格納された入力文字列を、呼び出される度に一字読み取っていく関数get_token()を作成した。具体的には、変数cpを入力文字列のポインタとして扱い、字句を読み取った後、変数cpをインクリメントしていき、一字ずつ入力文字列を読み取っている。
ただし、読み取った文字が以下のケースに該当し場合は、例外的に以下に示す処理を行う。
（条件：処理）
・ 空白スペース：空白スペース以外の文字が出現するまで次の文字を読み取り続ける。
・ 英字：英字以外の文字が出現するまで次の文字を読み取り続ける。また、読み取った文字列を一つの単語として配列strに格納する。
また、関数get_token()では、配列charsから一字読み取ると同時に、読み取った文字をカテゴリ別に分類する作業も行うようにしている。分類した結果は変数tokenに反映させている。このときの分類作業は、以下の仕様に則って行われる。
(カテゴリ名：カテゴライズされる文字)
1. Value：0から9の数字
2. Character：aからz、またはAからZ
3. Decimal：’.’
4. Lbracket：’{‘
5. Lpar：’(‘
6. Plus：’+’
7. Minus：’-’
8. Times：’*’
9. Divide：’/’
10. Modulo：’%’
11. Rpar：’)’
12. Rbracket：’}’
13. Equal：’=’
14. EOL：’\n’
15. Error：上記以外の文字、または記号
上記に示した各カテゴリは、enum宣言で列挙した。列挙する順番は、カテゴリ名の左に書かれている番号に準拠している。
本プログラムの字句解析では、読み取った英字列に対しての名前の同定は行わず、その英字列を配列strに一時的に保存するだけにとどめている。これは、次に読み取る字句によって、読み取った英字列に対して行う処理が変わるためである。よって、読み取った英字列に対しての名前の同定処理は、構文解析の部分で行うことにしている。
本プログラムの字句解析部は、これらの関数を用いて具現化されている。
3.2 構文解析
次に、字句解析で得た情報を基に構文解析をするプログラムについて解説する。構文解析プログラムは、1.で示した構文規則に再帰降下法を適用したプログラムとなっている。よって、構文規則より、関数expression(), term(), primary(), figure(), character()を生成し、これらの関数を再帰的に用いて構文解析を行っている。
関数expression(), term, primary()については、特にこだわった点は無く、構文規則に従い単純に再帰降下法を適用しただけである。一方で、関数figure(), character()については、読み取った文字列の数値化や名前の同定作業、変数の登録作業を行っている。
まずは、関数figure()について解説を行う。関数figure()が呼び出されるとき、構文規則より、変数tokenには必ずValueが入っていることになる。つまり、これから読み取る文字が、1つ以上の連続した数字列であることが保証されていることになる。よって、文字列の数値化を具現化する方法として、while文を使って読み取った文字が数字である限り、以下の関数を呼び出す方法を使った。
value= value*10+(chars[cp-1]-'0');
get_token();
一行目に書かれている文は、変数valueに10をかけて1の位を0にしたあと、読み取った文字番号から’0’の文字番号を引いた値をvalueに加算する、という文である。その後、関数get_token()を用いて次の文字を読み取る。これらの式により、入力された数字の文字列を十進整数定数化することが可能になる。
しかしながら、構文規則では数字列の直後に小数点が来ることを許している。つまり、入力された文字列が小数点を含んだ十進定数であっても、数値化できなくてはいけない。この仕様を具現化する手段としては、小数点後に続く数字の数をカウントし、文字列の数値化が終了した時点でカウントした数だけ変数valueを10で除算する、という方法を用いている。このとき、文字列を数値化する方法は十進整数定数を具現化する方法と同じ方法を用いている。また、十進整数定数化後に読み取った文字列が小数点でなければ、この処理は行われない。
これらの動作により、関数figure()は文字列の数値化を具現化している。
3.3 意味解析
次に、関数character()について解説する。関数characterには、大きく分けて二つの処理方法があり、条件文によって必ずどちらか一方の処理が実行される。一つ目の処理方法は、英字列の後に’=’が付属した場合に実行される。この処理では、英字列を一つの変数として扱い、’=’後に続く式の結果をその変数に格納している。その後、その変数をハッシュ法で撒布させ、該当するハッシュ表に関数registerKeyword()を用いて登録する。このとき、撒布後の衝突を防ぐため、ハッシュ表の各要素はリスト構造を持たせている。これにより、ハッシュ法による衝突が生じた場合でもリストを用いて変数を登録することが出来る。
もう一つの処理方法は、英字列の後に’=’が付属していない場合の処理方法である。この処理では、読み取った英字列を既にハッシュ表に登録されている変数として扱う。よって、まずはその英字列を関数FindKeyWord()を用いてハッシュ表から検索する。検索に失敗した場合は関数error()を呼び出し、成功した場合は関数popKeyValue()を用いてその英字列の持っている数値を取り出す。
これらの動作により、関数character()は、名前の同定と変数の登録を具現化している。
3.4 誤り処理
本項では、本プログラムの構文解析において、予期せぬ字句を読み取ってしまった場合の対処方法について解説する。
本プログラムでは、構文解析時に構文規則を満たさない字句を読み取ってしまった場合、関数error()を呼び出すことにしている。関数error()は３つの引数をもっており、それぞれ以下のような特徴を持っている。
(引数名：役割)
Char message[]：コンソール画面にmessageに格納されている文字列を出力する。
Int procedure：変数procedureより優先度の低い字句を読み飛ばす。
Int position：構文規則を満たしていない文字の場所を変数positionで示す。
上記に示したように各引数はそれぞれ、誤りを是正するために必要な情報を出来るだけ詳細に示す役割を持っている。以下に、各引数が関数error()のどのような振る舞いと関係があるのかを具体的に解説する。
配列messageでは、エラーの内容を出来るだけ詳細に教えてくれる役割を持っている。例えば、左括弧’(‘を事前に入力文字列から読み取っていたが、それらに対応する’)’が入力文字列に含まれていなかった場合は、引数の配列messageに”missing ‘(‘”を入れることで、画面にエラーの原因が出力することが出来る。
変数procedureは、入力文字列に誤りが複数あったとき、その誤りを出来る限り多く検出する役割を持っている。3.1の字句解析で、分類されるカテゴリはEnum宣言で列挙されることを示した。これを利用して、Enum宣言で列挙するカテゴリの順番を、出現する頻度や演算子同士の優先度を考慮して配置することで、次に来るべき字句を特定することが出来る。これにより、’+’や’*’などの演算子を使うべき部分で何らかの誤りがあった場合でも、Valueや括弧が出てくるまで入力文字列を読み飛ばして再び構文解析を開始することが出来る。つまり、変数procedureで適宜読み飛ばす字句を指定してあげることで、複数のerrorを一度に検出することが出来ることになる。
変数positionは、入力文字列のどこの文字がerrorの原因になったかを特定する役割を持っている。文字の場所を特定する方法として、入力文字列ポインタ用の変数cpを使っている。なぜなら、関数error()は構文解析中に呼び出され、かつ変数cpは常に次の文字を指しているので、chars[cp-1]の場所にある文字がerrorの発生した文字と一致するからである。しかしながら、3.1字句解析の解説で示したように、英字を読み取った場合は例外的な処理を行っているため、errorの発生する場所が常にcp-1になるとは限らない。よって、この場合に限っては、現在cpの指している位置によって変数positionの値を変更し、変数positionの値が常に英字列の最後尾を指すように設計した。
この関数error()を用いて、本プログラムでは誤りの原因の特定を行っている。
3.5 main関数
最後に、本プログラムのmain関数について解説する。main関数では、まず入力文字列を格納する配列charsの初期化を行い、その後、関数get_line()を呼び出している。3.1の字句解析で解説したように、関数get_line()は空行が入力されたかどうかの結果を返すことにしている。これを利用して、while文の条件式を”while(get_line() != FALSE)”とすることで、空行が入力されたときに終了するプログラムにすることできる。
次に、while文の内側で実行される処理を解説する。関数get_line()で何らかの入力文字列を読み取ったら、関数get_token()を呼び出して字句解析を一度だけ行う。これは一字先読みのルールを遵守するためである。その後、構文解析プログラムを用いて入力文字列の計算を行い、その結果を変数resultに格納する。その後、構文解析中にerrorが発生していなければresultの内容を出力し、errorが1個以上発生していればerror発生したことを画面に出力している。しかしながら、誤り処理の関数error()も完璧に隙が無いわけではない。このため、誤りを検知出来なかった場合の例外も想定して、誤り検出に失敗したときは”unexpected error”を画面に出力するようにしている。その後、配列charsを再度初期化して、再びwhile文の先頭に戻る。
While文を抜けたら、ハッシュ法を使用する際に確保したメモリを解放し、プログラムを終了させる。
4. 実行例
yohei@YOHEI-note ~/wl/calc
$ gcc calc.c -o calc
yohei@YOHEI-note ~/wl/calc
$ ./calc
----- 小数点、各演算子、括弧、代入、終了の確認 -----
# +2-1
>> 1.000000
# -2-1
>> -3.000000
# 2+5*10
>> 52.000000
# 2*5+10
>> 20.000000
# 2*(5+10)
>> 30.000000
# 3/2
>> 1.500000
# 5.5/2.2
>> 2.500000
# [5.5/2.2]
>> 2.000000
# [5/(1+1)]
>> 2.000000
# 2/1+6%3
>> 2.000000
# 4.9%0.3
>> 0.100000
# two=2
two holds 2.000000
>> 2.000000
# five=5
five holds 5.000000
>> 5.000000
# ten=10
ten holds 10.000000
>> 10.000000
# hundred=100
hundred holds 100.000000
>> 100.000000
# -(ten+five/two)*two*hundred
>> -2500.000000
#
shut down this program...
yohei@YOHEI-note ~/wl/calc
$
----- 誤り処理 -----
# 1+ 2++ 4
error: incorrect position of symbol.
1+ 2++ 4
^
1 error was found.
# (1+3*4
error: missing ')'
(1+3*4
^
1 error was found.
# 1++[2*3**1
error: incorrect position of symbol.
1++[2*3**1
^
error: incorrect position of symbol.
1++[2*3**1
^
error: missing ']'
1++[2*3**1
^
3 errors were found.
# two+five*second+ten
error: not registered word is used.
two+five*second+ten
^
1 error was found.
# 1.3.4.5.6
unexpected error
5. 設計した電卓のソースプログラム
* see the following page.
https://github.com/yasulab/calculator-with-lp
0 件のコメント:
コメントを投稿