C++ 自作物

言語処理系をつくろう(第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をそれに置き換えています。primarynumと並列で括弧付きのaddを定義しているため、「括弧付きの計算が一番深い=一番優先度が高い」という規則になっています。

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

括弧付きの計算に対応(47d1b06)

単項演算子(+と-)

括弧付きの計算は実行できるようになりましたが、これだけでは-5+31++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();
	}
};

+については特に何もしなくてOKですが、-については0からの引き算として実装しています。全実装は以下をご覧ください。

単項演算子の実装

これで、整数レベルの四則演算はすべてカバーできるようになりました。簡単な電卓レベルまで進化したことになるので、ちょっと嬉しいですね。

次回からはもう少し言語処理系っぽい機能を入れ込んでいこうと思います。

ではでは

広告の表示がブロックされています。
広告の表示がブロックされています。

関連記事

C言語 自作物 Linux プログラミング

wordleもどきのCUIアプリをつくってみた

最近、wordleという英単語当てゲームで遊んでいます。シンプルなゲームながら、通勤時間の暇つぶしや友人とのスコア比べなど意外と中毒性があり面白いです。 普通に英単語の勉強にもなるので、もっとたくさん ...

RaspberryPi Linux

Raspberry Pi4+Ubuntu ServerでGitLabを動かしてみる

お仕事でGitLabに触れる機会があったので、学習用に自宅にもGitLabが欲しくなりました。 手元にあるRaspberry Pi4+Dockerならお手軽に立ち上げられるはずと着手したものの、意外と ...

Flutter プログラミング

【Flutter】アプリ内の設定値を実装する方法

アプリ内で独自の設定を作る場合、そのデータを保持する方法を考える必要があります。 SQL、テキストファイルなど選択肢は多々ありますが、shared_preferencesというパッケージを使えば簡単に ...

RaspberryPi Linux

YoctoでRaspberryPi4のイメージをビルドしてみた

昨今、様々なデバイスでLinuxが動くようになっている中、組み込みLinuxのデファクトスタンダードとなりつつあるのが「Yocto」と呼ばれるビルドシステムです。 組み込みの現場ではその名前を聞くこと ...

C++ 自作物

言語処理系をつくろう(第7回):比較演算子を実装する

自作の言語処理系開発日記の第7回です。前回までで変数の実装が終わったので、ここからはいよいよ制御構文を実装…と思ったのですが、制御のためには比較演算子を実装する必要がありました。 ということで、今回は ...

Ryo Yoneyama

とある会社でソフトウェアエンジニアをしています。技術的な備忘録を中心にまとめてます。ネタがあれば日記も書きます。

    -C++, 自作物