C++ 自作物

言語処理系をつくろう(第5回):連続した式の実行

自作の言語処理系開発日記の第5回です。

前回までで括弧を含んだ四則演算ができるようになりましたが、このままでは単なる電卓止まりです。ということで、今回は複数の式を連続して実行できる仕組みを実装していきたいと思います。

生成規則を考える

これまでは入力全体を1つの式として解釈していましたが、今回は式の区切りを定義して複数の式として解釈できるようにします。

C言語だと「;」や「,」が区切り文字として使われますが、開発中の言語(rook)では「,」と「\n(改行)」を区切り文字とします。それを踏まえて生成規則を考えると、こんな感じになります。

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

programの生成規則を修正しただけです。addが「,」または「\n」区切りで連続して現れる形にしています。

実装してみる

入力が複数の式になったので、実装も各所を修正する必要があります。具体的には、

  • 構文解析の結果はノードのリストとする
  • コード生成は各ノードに対して順に生成するようにする

という修正が必要です。

構文解析器

構文解析器は、先述したようにノードのリストとして解析結果を返すようにします。programの生成規則に対応した処理の中で、解析結果を詰めていくようにすればOKです。

vector<Node*> Parser::program(void)
{
	vector<Node*> nodes;

	nodes.push_back(add());

	while(consume(",") || consume("\n")){
		nodes.push_back(add());
	}

	return nodes;
};

コード生成

コード生成は構文解析器の結果(ノード)を1つ1つ処理していけばよいだけですが、1つだけ注意が必要なことがあります。

スタックマシンでは、1つの式の評価結果がスタックトップに残されます。そのため、複数の式を連続して実行したときには、その分だけスタックに評価結果が残されてしまいます。

これを避けるために、1つの式(ノード)に対応した命令列の最後に、スタックから値をポップする命令を追加するようにします(下記コードの8行目)。今回は汎用レジスタ(GR0)に結果を退避するようにしました。

vector<Operation> Generator::codegen(vector<Node*> &nodes)
{
	vector<Node*>::iterator node;

	for(node = nodes.begin(); node != nodes.end(); node++){
		gen(*node);
		operations.push_back( Operation{ OP_POP, REG_GR0 } );
	}

	return operations;
};

これで連続した式を実行できるようになったため、

1+1, 2+2, 3+3

のようなカンマ区切りの式や

1+1
2+2
3+3

のような改行区切りの入力が扱えるようになりました。まだ変数が扱えないのでプログラムっぽくはないですが、電卓止まりからちょっとステップアップしましたね(・∀・)。今回の実装のコミットは以下になります。

連続した式の実行に対応(95c14f7)

いよいよ、次回は変数に対応させていきたいと思います。

ではでは

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

関連記事

Flutter プログラミング

2021/8/2

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

アプリ内で独自の設定を作る場合、そのデータを保持する方法を考える必要があります。 SQL、テキストファイルなど選択肢は多々ありますが、shared_preferencesというパッケージを使えば簡単に実装することができます。 Dart packages  2 Users 40 Pocketsshared_preferences | Flutter PackageFlutter plugin for reading and writing simple key-value pairs. Wraps ...

この記事を読む

RaspberryPi Linux

2021/4/18

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

昨今、様々なデバイスでLinuxが動くようになっている中、組み込みLinuxのデファクトスタンダードとなりつつあるのが「Yocto」と呼ばれるビルドシステムです。 組み込みの現場ではその名前を聞くことが増えましたが、まだまだ日本ではドキュメントも乏しくイマイチ掴み所がありません。そこで、まずは使ってみようということでRaspberry Pi4のイメージをビルドしてみることにしました。 目次1 Yoctoとは?2 Raspberry Pi4のイメージを作ってみる2.1 下準備2.2 Yocto本体+ラズパイ ...

この記事を読む

C++ 自作物

2021/8/1

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

自作の言語処理系開発日記の第7回です。前回までで変数の実装が終わったので、ここからはいよいよ制御構文を実装…と思ったのですが、制御のためには比較演算子を実装する必要がありました。 ということで、今回は比較演算子を実装していきます。基本的には四則演算と変わりないのであまり難しくはありません。 目次1 比較演算子の仕様2 実装してみる2.1 トークナイザ2.2 構文解析器2.3 コード生成器2.4 実行系(仮想マシン) 比較演算子の仕様 比較演算子を実装する前に、その仕様について少し考えておきます。 比較演算 ...

この記事を読む

C++ 自作物

2021/8/1

言語処理系をつくろう(第6回):変数を実装する

自作の言語処理系開発日記、第6回です。 これまでは四則演算など、電卓レベルの機能実装に取り組んでいましたが、いよいよ変数を扱えるようにしていきたいと思います。これでかなりプログラミング言語っぽくなるかも(・∀・) 今回は新しい仕組みを入れたりと、割と修正がごちゃごちゃしてしまったので、うまくまとめきれていません。ごめんなさい…。 目次1 変数の実装について2 実装してみる2.1 トークナイザ2.2 構文解析器2.3 コード生成器2.4 実行系(仮想マシン) 変数の実装について これまでは即値しか扱っていな ...

この記事を読む

C++ 自作物

2021/8/1

言語処理系をつくろう(第5回):連続した式の実行

自作の言語処理系開発日記の第5回です。 前回までで括弧を含んだ四則演算ができるようになりましたが、このままでは単なる電卓止まりです。ということで、今回は複数の式を連続して実行できる仕組みを実装していきたいと思います。 目次1 生成規則を考える2 実装してみる2.1 構文解析器2.2 コード生成 生成規則を考える これまでは入力全体を1つの式として解釈していましたが、今回は式の区切りを定義して複数の式として解釈できるようにします。 C言語だと「;」や「,」が区切り文字として使われますが、開発中の言語(roo ...

この記事を読む

  • このブログの中の人

Ryo Yoneyama

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

-C++, 自作物

© 2021 Corgi Lab. ~備忘録のための技術ブログ~