C++ 自作物

言語処理系をつくろう(第1回):数値を読み込む

前回からはじめた自作の言語処理系開発日記の第1回目です。今回から実際のコードを書いていきたいと思います。

前回の記事でも紹介したとおり、全体の構成は以下のような感じです。

今回は、それぞれの仕組みの骨格と簡単な機能の実装を進めていくことにします。

今回の目標

はじめの1歩として実装するのは、数値の読み込みです。1つの数字を読み込んでそれを実行結果とするだけの機能を実装します。機能としてはシンプルですが、中身自体はしっかりトークナイズ→構文解析→命令生成→実行の流れを踏みます。

ちなみにですが、リポジトリ名は「rook」としました。私のGitHubのアイコンにもしている愛犬の名前です笑

実装してみる

トークナイザ

まずは入力文字列をトークンに分解するトークナイザです。最初にトークンを以下のような構造体で定義します。

トークンはその意味や役割に応じて種類が分かれるので、トークン種別(kind)を持たせます。現時点では数値の入力しか考えないので「数値トークン」のみです。strは入力文字列に対するトークンの開始位置、lenはその長さです。

トークナイズ本体の処理は以下のような感じです。欲しいのはトークン列なので、Tokenvectorとして結果を返します(とはいえ、いまは1つのトークンだけ)。ここでも現時点では数値だけを読み取れれば良いので、数字以外はすべてエラー扱いです。

構文解析器

続いて構文解析器です。ここでは実装の前に、この言語処理系の構文を決めます。構文定義にはBNF記法というものが使われますが、厳密な書き方は特に気にしません。実装に落とし込める形であれば何でもOKとします。

今回は「1つの数字を読み込む」だけなので、現時点での構文は「数値1つだけ」となります。これを表現してみるとこんな感じになります。

program = num

programは入力ソースそのもの、numは数値を表します。つまり「入力ソースは数値である」となります。このようなものを生成規則と呼んだりするそうです。

実装ですが、まずは構文解析の結果を表現するためのノードを定義します。

ここでもノードの種類を定義していますが、現時点では数値だけです。木構造を表現するために、左木(left)と右木(right)を持たせます。また、数値も1つのノードとして扱う必要があるので、その値(val)も用意します。

続いて構文解析の処理ですが、ここではさきほど定義した構文に対応させる形で実装します。そのため、numというメソッドを実装し、それをprogramというメソッド内で呼び出すようにします。構文が複雑になってきても、この方法であれば比較的素直に実装に落とし込むことができ、再帰的に処理しやすくなるというメリットがあります。

コード生成器

お次はコード生成器です。ここでは、入力として構文解析の結果(Nodeの木)を受け取って実際の命令に変換します。

今回は「数値を受け取ってそれを実行結果とする」という処理が実現できればOKですが、作成する処理系は「実行結果=スタック」のトップなので、「数値をスタックに積む」という命令1つで事足ります。

まず、命令については以下のような構造体で表現します。本来の命令はバイナリ列ですが、ここでは簡単のためにこうしました。

命令の種類はPUSHだけ、命令の中身もオペコード+オペランドだけです。これを使ってコード生成の処理を書くとこんな感じになります。最終的な出力は命令列(Operationvector)です。

ここでも、現時点では数値1つ(ノードが1つだけ)しか入ってこない想定なので、左右の木の存在は気にしていません。

仮想マシン(実行系)

最後に仮想マシンです。今回はスタックマシンとして実装するので、内部的にスタック用のメモリと、スタックトップを示すポインタ1つを用意しておきます。

あとは、入力された命令列を読みながら、各命令に対応した処理を行うだけです。

一応、これで数値を読み込んでそれを実行結果とする処理系が実装できました。現時点では言語処理系と言い張るのは無理がありますが、ここから少しづつ育てていきたいと思います。

実装コード全体

今回の実装のコミットは以下のハッシュになります。全体はそちらをご覧くださいm(_ _)m

数値の読み込みを実装

ではでは

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

関連記事

C++ 自作物

2020/8/14

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

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

この記事を読む

C++ 自作物

2020/8/14

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

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

この記事を読む

C++ 自作物

2020/8/14

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

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

この記事を読む

C++ 自作物

2020/8/14

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

自作の言語処理系開発日記の第4回です。前回までで乗除算を実装できたので、この調子でもう少し複雑な計算に対応したいと思います。今回はそれぞれの実装が少ないので、一気に2つのステップを進めます。 目次1 括弧を含む計算1.1 生成規則をいじる2 単項演算子(+と-)2.1 生成規則をいじる 括弧を含む計算 これまでの実装では、乗除算は必ず加減算に先立って実行されます。しかし、それでは不十分なので、括弧を含む計算(例:(1+2)*3)を実行できるようにします。 生成規則をいじる 今回も構文解析器の生成規則を修正 ...

この記事を読む

C++ 自作物

2020/8/14

言語処理系をつくろう(第3回):乗除算を実装する

自作の言語処理系開発日記の第3回です。前回は加減算を実装したので、今回は乗除算の実装にチャレンジしていきます。 目次1 実装してみる1.1 構文解析器 実装してみる 今回の実装において、トークナイザ・コード生成器・実行系(仮想マシン)については加減算のときと変わりません。単純に各種定義を追加して、それを扱えるようにしてあげるだけです。 一方、構文解析器についてはちょっとややこしいので、そこだけ解説します。 構文解析器 加減算では演算の優先順位がなかったので、単純に左結合(=左から順に計算していく)で処理し ...

この記事を読む

  • このブログの中の人
アバター

Ryo Yoneyama

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

-C++, 自作物

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