ComProcWorkshop/第4章：乗算に対応する
ここまでで加減算が計算できるようになった
この章では乗算に対応する
再帰下降型の構文解析を行う
ナイーブなやり方
CPUに乗算命令MULを追加する
MUL xx
reg0 *= xx
加算と同じように式の先頭から処理
ナイーブな例
例：ソースコード「1 + 2 * 3」
code:コンパイラ出力
MOV 1
ADD 2
MUL 3
OUT
出力が9になってしまう
正解は7
演算子の優先順位
「1+2*3」という式の解釈
(1+2)*3なのか1+(2*3)なのか
「+」より「*」の方が高優先
2*3を先に計算する必要がある
括弧が必要な例
「(1+2)*3」は「+」を先に実行する
中置記法は、演算子の優先順位を変えるために括弧を使う
後置記法による表現
「1+2*3」は中置記法
「1 2 3 * +」は後置記法
演算子を後ろに置くから
日本語記法、逆ポーランド記法とも
後置記法は括弧が不要
「(1+2)*3」は、後置記法で「1 2 + 3 *」
括弧を使わず、演算順を確定できる
後置記法は、先頭から順に計算できる→CPUの処理と相性が良い
後置記法の計算
式を先頭から読んでいく
整数ならスタックに積む
演算子なら値をスタックから取り出して計算し、結果をスタックに積む
スタックを用いた計算例
例：「1 2 3 * +」
code:計算手順
PUSH 1
PUSH 2
PUSH 3
MUL // POP→3; POP→2; PUSH 2*3
ADD // POP→6; POP→1; PUSH 1+6
スタックのトップに7が積まれた状態になる
https://gyazo.com/1dcc173cda1aa8246e9b79dd0c87d0ea/thumb/400#.jpg
スタック図は命令の実行後の状態を示す
スタックを用いた演算に対応したCPU
table:命令表
PUSH xx 01xx xxをスタックに積む
OUT 0200 スタックトップを出力
ADD 0300 加算
SUB 0400 減算
MUL 0500 乗算
この章の後半の目的
中置記法の式からスタックを用いた計算プログラムを生成すること
「1+2*3」から「PUSH 1; PUSH 2; ……」を作るということ
スタックを用いた計算プログラム≒後置記法の式なので、目的を「中置記法から後置記法への変換」と言い換えることも可能
中置記法の式と構文木
https://gyazo.com/7eb3646b1d96baafc905d0c4df9f402f/thumb/200.png
このような表現を「構文木」という
構文を木で表しているから
木で表すと演算子の優先順位がはっきりする
構文解析とは
「1+2*3」という文字列から構文木を作成する作業
構文木はデータ構造として作ることもあるし、明には作らないこともある
この後でやる再帰下降型構文解析は構文木を明には作らない
その代わり、関数の呼び出し関係で木を表現する
後置記法と構文木
https://gyazo.com/7eb3646b1d96baafc905d0c4df9f402f/thumb/200.png
以下の手順で木を（再帰的に）たどれば「1 2 3 * +」を得る
1. 演算子の左側を探索
2. 右側を探索
3. 最後にその演算子を出力
一般に、中置記法から構文木を作る方法の1つ
今回は、中置記法を計算する後置記法の機械語を出力するのに使う
関数を再帰的に呼び出すのでこの名前が付いている
準備として生成文法を定義する
加減算と乗算のための生成文法（の生成規則）
A→M
A→M+A
A→M-A
M→P
M→P*M
P→n（nは整数）
この生成規則の記号の意図
A：Additive expression（加算、減算の式）
M：Multiplicative expression（乗算、除算の式）
P：Primary expression（基本式）
今のところは「42」とか「-2」みたいな整数
記号の種類
終端記号：n
それ以上展開できない記号
非終端記号：A、M、P
生成規則により展開できる記号
生成規則の使い方
Aから出発し、数式を表す終端記号列を得られるまで生成規則を適用する
例：「1+2*3」（最終的に「n+n*n」を得たい）
table:生成規則の適用
記号列 適用する生成規則
A A→M+A
M+A M→P
P+A P→n
n+A A→M
n+M M→P*M
n+P*M P→n
n+n*M M→P
n+n*P P→n
n+n*n これ以上適用できないので終了
少しだけ複雑な構文木の例
https://gyazo.com/eb0b5fe106e1e827fe41bc8ccb103a43/thumb/350.png
生成規則は分かりやすい部分について省略している
再帰下降型構文解析の実装方法
各非終端記号に対応する関数を作る
以下ではA()、M()、P()とする
ソースコードを先頭から順に読み進めていく
ソースコードを格納した配列とポインタpを使う方法
標準入力からscanfなどで読み進める方法
再帰下降型構文解析の実装例
consume_char(文字)は、標準出力の先頭の1文字が指定した文字であれば、その文字を「消費」する
標準出力の先頭の1文字が指定した文字ではない場合、ungetc(文字, stdin)により文字を戻しておく
void Additive()の解説
「A→…」の生成規則に対応する関数
A→M
A→M+A
A→M-A
いずれの場合も、まず「M」を読み込む
先頭でMultiplicative()を呼び出すことに対応
次の文字が「+」なら「A→M+A」、「-」なら「A→M-A」、それ以外なら「A→M」であることが分かる
「+」か「-」なら、「A」に対応する関数Additive()を呼び出す
再帰下降型構文解析の動作例
https://gyazo.com/0470ccd7362e0195a40586c72e6872ce/thumb/300.png
長方形は、その関数が実行中の期間を表す
一番最初に呼ばれたA()はM()を呼び、その中でさらにP()が呼ばれる
P()が数式先頭の「1」を認識したらP()とM()の実行が終わるが、A()の実行は終わらない
サンプルコードの実行手順
$ echo "1 + 2 * 3" | ./a.out
やってみよう：括弧の対応
「(1+2)*3」を構文解析できるようにしたい
括弧は生成規則に「P→(A)」を追加することに対応する
ヒント：Primary()に(を読み込んだ場合の処理を追加する