C++ 自作物

言語処理系をつくろう(第0回):イントロ編

今回から連載企画として、自作の言語処理系の開発日記を書いていこうと思います。

以前、プログラミング言語もどきとして「particle」というものを作ったのですが、進めていく内に手詰まりになって頓挫してしまいました。

しかし、最近「低レイヤを知りたい人のためのCコンパイラ作成入門」というオンラインブックを見て「作りたい欲」が高まってきたので、あらためて挑戦してみることにしました。

開発過程のコードはGithubでオープンにしていくつもりです。モチベーション維持のためにも、その詳細をこのブログで紹介しながら進められればと思います。

全体の構成案

過去に作った「particle」はスクリプト言語のように、ユーザーからの入力を逐一解析して処理する仕組みでした。しかし、今回はコンパイラ型言語のように、ソースコードから独自の命令列を吐き、それを独自の実行系で動かすという形にしたいと思います。

全体のイメージはこんな感じです。大きく分けて4つの仕組みを作る必要があります。

トークナイザ

入力文字列をトークンという意味を持った記号に分解する仕組みです。例えば「num = 1 + 3」という文字列が入力された場合、それをトークンに分解した結果は以下のようになります。

入力文字列を部品に分けて、それらに意味づけをしていくイメージです。トークナイザの入力は文字列、出力はトークン列となります。

構文解析器

トークナイザで生成されたトークン列を、その言語の文法に従って解析し構造化する仕組みです。一般的に、解析結果は木構造で表現されます。先で例に挙げたトークン列を構造化すると以下のようになります。

このように、代入や加算を木構造で表現することで、式全体を1つのノードを頂点とする構文木で表すことができます。構文解析器の入力はトークン列、出力は構文木になります。

コード生成器

構文解析器で生成した構文木を辿りながら、実行系が処理するための命令列を吐き出す仕組みです。左優先で木を辿りながら、各ノードに対応する命令列を吐き出すのが一般的(?)かと思います。

各命令は基本的にはオペコード+オペランドの組み合わせで定義されます。オペコードで処理の内容、オペランドで処理対象のデータを指定します。

今回は実行系も自作なので、それに合わせた命令セットも自分で決めちゃえばOKです。

仮想マシン

コード生成器が吐いた命令列を処理する実行系です。カッコよく「仮想マシン」と呼びますが大層なことはせず、シンプルにスタックマシンとして実装することにします。スタックマシンとは、スタックに対するデータの出し入れによって計算を行う仕組みです。例えば「1+3」という計算を行うときには、

  1. 数値の1をスタックに積む
  2. 数値の3をスタックに積む
  3. スタックから数値を2つ取り出して、その加算結果をスタックに積む

という流れを踏みます。図で表すとこんな感じです。この場合「最終的にスタックの一番上に積まれている値=式の計算結果」となります。

進め方と環境

今回の開発については、

  • 最初から性能面や設計のキレイさはあまり考えない
  • 1つ1つ機能を追加する形でつくる

という方針で進めます。あくまでも趣味の個人開発なので「間違っていてもOK」がモットーです。最初から正しい姿を求めてしまうと疲れてしまうので、トライ&エラーでコツコツと育てていこうと思います。

開発環境はLinux、言語はC++です。こちらも特に意味はなく、単純にC++を使って何かを作ってみたかったという理由だけです。

ということで、次回から実際のコードを書きつつブログも更新していこうと思います。コードや記事の中身は私のような素人が書く内容なので、実際の言語処理系で使われる用語や設計とは異なっている可能性が大です。その点、ご容赦いただき期待せずお待ちください 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. ~備忘録のための技術ブログ~