言語処理系をつくろう（第4回）：括弧付き計算と単項演算子

自作の言語処理系開発日記の第4回です。前回までで乗除算を実装できたので、この調子でもう少し複雑な計算に対応したいと思います。今回はそれぞれの実装が少ないので、一気に2つのステップを進めます。

括弧を含む計算

これまでの実装では、乗除算は必ず加減算に先立って実行されます。しかし、それでは不十分なので、括弧を含む計算（例：（1+2)*3）を実行できるようにします。

生成規則をいじる

今回も構文解析器の生成規則を修正することで、括弧付きの計算に対応させます。前回の乗除算を実装した際には、乗除算が加減算より深くで展開されるように生成規則を変えることで、計算の優先順位を表現しました。今回も考え方は同じです。

まず、前回までの生成規則はこちら。

program = add program = add
add = mul ("+" mul | "-" mul)*
mul = num ("*" num | "/" num)*

そして、括弧付きの計算に対応した生成規則が以下になります。

program = add
add = mul ("+" mul | "-" mul)*
mul = primary ("*" primary | "/" primary)*
primary = num | "(" add ")"

primaryという新しい生成規則を定義し、mulの中にあったnumをそれに置き換えています。primaryはnumと並列で括弧付きのaddを定義しているため、「括弧付きの計算が一番深い＝一番優先度が高い」という規則になっています。

実装はこれまでと変わらずなので割愛しますが、気になる方は以下のコミットをご覧ください。

括弧付きの計算に対応（47d1b06）

単項演算子（+と-）

括弧付きの計算は実行できるようになりましたが、これだけでは-5+3や1++3のような式が計算できません。これらを扱うためには単項演算子としての+と-を実装する必要があります。

生成規則をいじる

こちらも生成規則をいじることで解決したいのですが、ややこしいのが加減算の+と-との棲み分けです。文字は同じでも、式中の位置や文脈によって解釈が変わるので、それを上手に生成規則に落とし込む必要があります。

最初はこんな規則を考えましたが、結論から言うとダメでした。

program = add
add = mul ("+" mul | "-" mul)*
mul = primary ("*" primary | "/" primary)*
primary = num | "+" num | "-" num | "(" add ")"

括弧付きの計算で作ったprimaryの規則中、+付きのnumと-付きのnumを入れることでパッと見うまくいっていたのですが、-(1+3)のような式がパースできないことに気づき、ボツになりました(´・ω・)

括弧付きの計算にも対応しようと思うと、primaryの定義を

primary = num | "+" num | "-" num | "(" add ")" | "+(" add ")" | "-(" add ")"

とすれば良いのですが、ちょっと冗長です。そこで、unaryという定義を追加して以下のようにするとすっきりします。

program = add
add = mul ("+" mul | "-" mul)*
mul = unary ("*" unary | "/" unary)*
unary = ("+" | "-")? primary
primary = num | "(" add ")"

生成規則中の？は、直前の項目が0回または1回登場するという意味です。unaryだけを抜き出すと、実装はこんな感じになりました。

Node* Parser::unary(void)
{
	if(consume("+")){
		return primary();
	}
	else if(consume("-")){
		Node* zero = new Node();
		zero->kind = ND_NUM;
		zero->val = 0;
		Node* node = new Node{ ND_SUB, zero, primary() };
		return node;
	}
	else{
		return primary();
	}
};