C++ 自作物

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

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

これまでは四則演算など、電卓レベルの機能実装に取り組んでいましたが、いよいよ変数を扱えるようにしていきたいと思います。これでかなりプログラミング言語っぽくなるかも(・∀・)

今回は新しい仕組みを入れたりと、割と修正がごちゃごちゃしてしまったので、うまくまとめきれていません。ごめんなさい…。

変数の実装について

これまでは即値しか扱っていなかったので、「値が登場すればそれをスタックに積む」という単純な仕組みで事足りていました。しかし、変数を扱うためには、どこかに値を覚えておいて、それを読み書きする仕組みが必要になります。

まず、変数の保存場所ですが、今回はスタックを使います。ただ、変数自体をPush/Popするのではなく、スタックの先頭領域を変数置き場として間借りします(下図)。

「C言語のローカル変数はスタックにある」なんていう話を聞きますが、それとほぼ同等の仕組みです。読み書きについては、各変数のスタック中のアドレスに対して行うようにします。

実装してみる

トークナイザ

この処理系では、変数名のルールを以下のようにします。

  • 開始文字がa~z, A~Z, _のいずれかであること
  • 途中の文字はa~z, A~Z, 0~9, _のいずれかであること
  • 他の予約語と一致しないこと

実装自体は難しくないので割愛します。「他の予約語と一致しないこと」というルールがあるので、変数は最後にトークナイズするように注意します。

構文解析器

今回は変数の宣言と代入を実現したいので、生成規則は以下のようにしました。

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

変数を表すidentという記号を定義して、exprという新しい生成規則を追加しました。これで、変数=式という代入式を扱えるようになります。

実装としては、変数そのものを表すノード(ND_IDENT)と、代入を表すノード(ND_ASSIGN)の2つを新規に定義します。

あとは生成規則に従って解析処理を実装すればOK。ここまでは割と単純です。

コード生成器

コード生成に関しては、変数の扱いがややこしいです。というのも、変数は置き場所(式の左辺 or 右辺)や、前後の文脈次第でその意味が変わります。

例えば、num=1という式の場合、numは代入先として解釈されるので、その評価値はアドレスです。一方、ret = num+1という式の場合は、numの評価値はそれが保持する値になります。

いま現在の生成規則では、代入式の左辺に来たときだけ変数をアドレスとして解釈すれば良さそうです。それ以外は全て値として解釈します。

ここからは実装です。まず、変数を表す構造体を以下のように定義します。変数名とその長さに加え、その変数のスタック上での位置(アドレス相当)を持たせました。そして、同一変数に対しては同じアドレスでアクセスできるように、変数のリストも定義しておきます。

また、変数に対する読み書きを実現するために、新しい命令としてLOADとSTOREを定義します。LOADはメモリ(スタック中)からレジスタへの値コピー、STOREはその逆です。

そして、代入と識別子に対するコード生成を抜き出すと以下のようになります。

途中に登場するgen_varという関数は識別子ノード専用の関数です。そのノードが示す変数のアドレスをスタックに積みます。

それ以降は、代入式であればアドレスに対するSTORE、それ以外であればアドレスからの値のLOADという形で命令列を出力します。

実行系(仮想マシン)

最後に実行系ですが、今回はスタックを変数領域とそれ以外で分けることにしたので、その境目を示す値が必要です。そこで、その値をベースポインタという名前で扱うことにし、いまは固定でスタックの先頭から16個先としました。つまり、使える変数は最大で16個までです。

途中、解説をかなり端折ったところもありますが、これで変数を扱うことができるようになりました。まだまだ実装は粗いですが、これで1つのチェックポイントは通過できたかなと思います。

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

変数の実装(dd7ed9e)

次回以降は制御構文の実装を視野に機能を追加していく予定です。

ではでは

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

関連記事

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. ~備忘録のための技術ブログ~