Python コンパイラを作ろう : コンパイラ基礎講座第一回 (理論編 1)

まえがき

この記事は投稿者(NokonoKotlin)の個人サイトの記事から Qiita 用に移植 & 加筆したものです。
(この文言は記事が剽窃でないことを周知するためのものであり、個人サイトの宣伝ではないことをあらかじめご了承ください。)

はじめに

みなさんはスマブラの勉強をしてゲーム制作の勉強ができると思いますか？

プログラミング学習といえば文法やライブラリの学習を想像されるかもしれません。これはその通りなのですが、プログラミングをさらに理解するためには、プログラムが動く裏側で何が起こっているのかを知る必要があります。

インタープリタとコンパイラ

みなさん Python はよくご存知のことだと思いますが、今一度 Python が何かを考えてみませんか。ご存知の通り、Python はプログラミング言語であり、インタープリタを介して Python 文で書かれたプログラムを実行します。

処理をインタープリタに任せるプログラミング言語をスクリプト言語と呼びます。Python のようなスクリプト言語はプログラム実行中にリアルタイムに文を解釈しながらプログラムを処理します。スクリプト言語は解釈と実行を同時進行で行うのでプログラムの実行のたびに文を解釈するコストがかかり、その分だけ実行時間が傘増しされてしまいます。

プログラムのソースコードをあらかじめ全て機械語に翻訳しておく操作をコンパイルと言います。また、そのようにして実行される言語をコンパイラ言語と言います。C++ や Java がコンパイラ言語の例です。コンパイラ言語の実行はあらかじめ機械語に翻訳された命令をコンピュータに読ませて実行するだけなので、スクリプト言語と比べてプログラム実行のコストが軽いのがコンパイラ言語の利点です。

ある言語のソースコードを機械語に翻訳するプログラムをコンパイラと言います。リッチな高級言語を $1$ 度で直接機械語までコンパイルするのは大変なので、コンパイラは、ある言語から別の言語をいくつか経由して機械語まで翻訳を行うことがあります。

ある言語を別の言語に翻訳するシステムを変換系と言い、言語 $X$ で記述されたプログラムを用いて言語 $A$ を言語 $B$ に変換することを $A {\rightarrow\over{X}}B$ と表記することにします。

ある言語 $A$ のコンパイラを自作したい場合、言語 $A$ を直接機械語まで翻訳するプログラムを作ることは非常に難しいですが、すでにコンパイラが存在する言語 $B$ を適当に見つけて、$A {\rightarrow\over{X}}B$ を行う言語 $X$ のプログラムを作ることができれば、実質的に言語 $A$ のコンパイラを作ったと言えます。

インタープリタにおいては、インタープリタがすでに機械語に翻訳されて実行されることを利用して、言語 $A$ から他の言語を介さず直接機械語で実行することが可能です。インタープリタは言語 $A$ のプログラムを解析し、解析したプログラムに書かれている命令を言語 $B$ に翻訳せず、それらの命令の処理をインタープリタの内部に実装することで、言語 $A$ の命令の処理を直接機械語で実行できます。

Python コンパイラを作ろう

本シリーズの目的は、Python 言語をインタープリタではなくコンパイラによって実行できるようになることです。先に述べた通り、コンパイラで言語を翻訳できるようになれば実行コストを削減することができ、遅い Python 言語の実行コストを下げることができます。

今回の目次

• オートマトン
• 字句解析
• 構文
  • 言語
  • 文脈自由言語
• 構文解析
  • 構文の特定
  • 導出過程の特定
  • 上昇型構文解析
  • 下降型構文解析
• 付録
  • Python を実行する C++ プログラム
  • 使用例

オートマトン

あるオートマトン $D$ を以下のパラメータを用いて定義します。

• $Q := $ 全ての状態の集合。グラフの頂点に対応。
• $s := $ 初期状態
• $F := $ 受理状態 (終了状態) の集合
• $\sum := $ 辺ラベルとして登場する記号の集合。アルファベット。
• $\delta := $ グラフにおける遷移の集合。グラフの辺に対応。特に、状態 $q$ と辺ラベル $l$ に対して、$\delta(u,l)$ は状態 $u$ から $l$ を読み込んだ場合の遷移先の集合を表す。

オートマトンは何らかの状態間の遷移関係を表現するグラフであり、以下のように表現されます。

このグラフの辺 $e$ に対して、$u(e)$ を始点、$v(e)$ を終点、$l(e)$ を辺ラベルとします。このグラフは、$u(e)$ の状態で $l(e)$ を読み込むことで $v(e)$ の状態に遷移するということを表します。例えば、状態 $q_2$ から文字 l を読み込むことで状態 $q_6$ に遷移します。

通常のオートマトンは、何らかの記号列 $T$ を入力として受け取り、$T$ に対して 受理か非受理かを判定します。記号列 $T$ が受理されるのは、初期状態 $s$ から記号列 $T$ の記号を先頭から読み込んでいったとき、全ての記号を読むことができて、なおかつ最終的に到達した状態が受理状態(終了状態)である場合に限ります。

例えば、記号列 nokonokotolin は $q_0$$\rightarrow q_4$$\rightarrow q_1$$\rightarrow q_0$$\rightarrow q_1$$\rightarrow q_4$$\rightarrow q_1$$\rightarrow q_0$$\rightarrow q_1$$\rightarrow q_2$$\rightarrow q_6$$\rightarrow q_5$$\rightarrow q_4$ と遷移し、最終的に到達する $q_4$ が受理状態なので 記号列 nokonokotolin は受理されます。対して、記号列 okoteiyu は状態 $q_3$ から永遠に抜け出せないため受理されず、記号列 okota は状態 $q_2$ から遷移できないので最後まで読まれず、受理されません。

このオートマトン $D$ のパラメータは以下の通りです。

• $Q = {q_0,q_1,q_2,q_3,q_4,q_5,q_6}$
• $s = q_0$
• $F = {q_4}$
• $\sum = {n,o,k,t,e,l,i}$
• $\delta$ は以下からなる。
  • $\delta(q_0,o) = q_1$
  • $\delta(q_0,n) = q_4$
  • $\delta(q_1,k) = q_0$
  • $\delta(q_1,n) = q_4$
  • $\delta(q_1,t) = q_2$
  • $\delta(q_2,e) = q_3$
  • $\delta(q_2,l) = q_6$
  • $\delta(q_4,o) = q_1$
  • $\delta(q_5,n) = q_4$
  • $\delta(q_6,i) = q_5$

このオートマトンにおいて遷移 $\delta$ のいずれもが単一の状態からなる集合なので、入力で与えられる記号列に対してオートマトンにおける遷移方法が一意に定まります。このようなオートマトンを決定性オートマトンと言います。

非決定性オートマトン

先ほどのオートマトンに少し状態と遷移を追加してみます。

すると、$q_1,q_2$ の遷移が以下のようになります。

• $\delta(q_1,t) = {q_2,q_7}$
• $\delta(q_2,l) = {q_2,q_6}$

遷移先の集合サイズが $2$ 以上なので、このオートマトンの遷移方法は一意でなくなります。このようなオートマトンを非決定性オートマトンと言います。

非決定性オートマトンにおいては、入力の記号列を読み込んで遷移する方法のうち、$1$ つでも受理状態に遷移する方法があれば入力は受理されます。

非決定性オートマトンは、Subset 構成法というアルゴリズムによって決定性オートマトンに変換できます。具体的な手法については割愛しますが、今後オートマトンの構築の際に決定的か非決定的かを考える必要はありません。

字句解析

ソースコードを読んで、次に紹介する構文解析で用いるトークン列 (記号の列)に分解する手順です。例えば、x:int = 2*9; という Python 命令は、トークン列 $T$ = { ID(x) : INT = NUM(2) * NUM(9) ; } に変換されます。またこの時、識別子として認識されたトークンは記号表に、名前,種類,宣言されたスコープの深さなどを持つ 1 つのレコードとして記録されます。今回の例では ID(x) の部分で x という名前(識別子)が記号表に記録されます。

構文

字句解析で得たトークン列は、何もない状態ではただの記号の列でしかありません。

プログラミング言語に定められた構文は先の字句解析で得られたトークン列の構造を解析し、そのトークン列がプログラミングの構文に従うか、従うならどのように規則が適用された文なのかを特定します。

言語

まずはプログラミングにおける言語が何かを今一度定義します。

ある規則に従って生成される文の集合を言語と言います。また、言語 $L$ の文に登場する記号の集合をアルファベットと言い、ここではアルファベットを $\sum$ と表記します。$\sum$ の記号を $0$ 個以上繋げてできる文の集合を $\sum^{*}$ とすると、当然言語 $L$ の文 $\in \sum^{*}$ です。コンパイラが構文を考えるステップでは、字句解析によって得られたトークン列を文としているので、$\sum = $ [トークンの集合] です。

文脈自由文法

言語における構文とは、その言語において許容される文を生成するためのルールのことです。例えば英語の SVO 構文は 主語 動詞 目的語 . という記号の列を生成するルールのことです。

構文が文 (トークン列) を生成する過程を記述するために、構文と文 (トークン列) をどちらも記号の列として考えます。構文が文 $T$ (トークン列) を生成するとは、ある記号 $S$ が存在して、$S$ に対して「ある記号を記号列に変換する操作」を繰り返すことで最終的に記号列 $T$ に変換されることを指します。また、$S$ から記号の変換を始める構文を単に構文 $S$ と表記することにします。

記号から記号列への変換ルールを生成規則と言い、生成規則を $\rightarrow$ を用いて記述したものを文脈自由文法と言います。文脈自由とは文の生成のルールが $\rightarrow$ にのみ依存し、他のメタ的な要素を考慮しないという意味です。

例 : SVO 構文

構文 <SVO 構文> は以下の生成規則に従って変換され、英単語の列を生成します。

• <SVO 構文> $\rightarrow$ 主語 動詞 目的語 .

記号の種類

文脈自由文法に登場する記号は以下の $2$ 種類に分類されます。

• 終端記号 := 最終的に生成される記号列 $T$ に登場する記号。字句解析におけるトークンであり、終端記号の集合はアルファベット $\sum$ と一致する。
• 非終端記号 := $\sum$ に属しない記号であり、構文が $T$ を生成する過程を表すために用いられる記号。

非終端記号が別の記号列に変換される (遷移する) ことを導出と言います。非終端記号 $A$ から記号列 $\beta$ への導出を $A \rightarrow \beta$ と表記し、記号列 $S$ から記号列 $T$ に $0$ 回以上の導出を経て変換することを、$S\rightarrow ^{*} T$ と表記します。

言語は文脈自由文法で記述した構文から導出される文の集合のことなので、文脈自由文法を決めることが言語を決定することと同義です。これはプログラミング言語の場合も同じです。多くの高級言語は文脈自由ではありませんが、この記事では文脈自由である言語に限定して議論することにします。

例 : Python の変数宣言の構文

Python における変数宣言の構文 $S$ を記号 <変数宣言> として定めます。Python の変数宣言は、識別子:型アノテーション = 式 ; という構文を持ちます。この構文に登場するパーツをさらに記号としておくことで、構文 $S$ の生成規則を以下で記述できます。

• <変数宣言> $\rightarrow$ ID : <型名> = <式> ;
• <型名> $\rightarrow$ 保留
• <式> $\rightarrow$ 保留

< > で囲われた記号が非終端記号で、そのほかが終端記号です。

定義と正規言語

構文の文脈自由文法 $G$ ないし $G$ によって生成される言語 $L_G$ は、以下の $4$ つのパラメータによって定義することができます。

• $\sum := $ 生成規則に登場する終端記号の集合。アルファベット。
• $N := $ 生成規則に登場する非終端記号の集合。
• $s := $ 構文の開始記号。文脈自由文法で表す構文自身を表す記号。
• $P := $ 生成規則。生成規則に含まれる導出の集合。

特に、言語 $L$ が以下を満たす文法によって定義されるとき、言語 $L$ を正規言語(正則言語)と言います。

• 記号から導出される記号列には、$1$ つ以下の非終端記号とちょうど $1$ つの終端記号が含まれる

正規言語 $L$ に属する全ての文を受理する決定性オートマトンは必ず存在することが知られています。

構文解析

構文解析の目的は、字句解析によって得られたトークン列 $T$ がどのような構成になっているのかを特定することです。また、関数呼び出しや変数宣言などのように、プログラミング言語を構成する構文は複数存在します。よって、構文解析では以下の $2$ つのステップを達成する必要があります。

• $T$ がどの構文から生成されるのかを特定する。
• $T$ を生成する構文を $S$ としたとき、$S$ からどのような導出を経て $T$ を得ることができるかを特定する。

T がどの構文から生成されるのかを特定する。

$T$ を生成する構文が何かを、何らかの方法で特定しなければなりません。メタ的な方法で特定できるのであれば、それで特定してよいです。例えば、Python の変数宣言のトークン列にはアノテーションの : ,初期化の = , 文末の ; が登場するので、トークン列にこの $3$ つが存在すればこれは変数宣言の構文によって生成されると判断できます。

そのようなメタ的な判断ができないのであれば、言語を構成する全ての構文に対して、$T$ が従う構文が見つかるまで一つずつチェックし、見つかればその構文が $T$ を生成する構文であるとします。逆にそのようなものが一つも見つからなければ、$T$ は間違った文であると言えます。

また、$T$ が従う構文が存在するならちょうど $1$ つであることを仮定します (そのように構文を設計する必要があります)。

構文による導出過程を特定する。

トークン列 $T$ の構成を特定するためには、構文 $S$ からの導出 $S \rightarrow ^{*} T$ が何かを特定する必要があります。そのような導出 $\rightarrow^{*}$ が存在しなければ、$T$ は構文 $S$ に従わないということになります。

構文の導出を復元する方法は主に二種類あります。

上昇型構文解析

一般に、記号列 $w$ は [ 非終端記号 $A$ ] と [ 空列を含む記号列 $p$ ] と [ 空列を含む終端記号列 $s$ ] の $3$ つを用いて $w = pAs$ と表すことができます。導出 $A \rightarrow \beta$ によって $w$ が $pAs \rightarrow p\beta s $ と遷移するとき、これを最右導出 $pAs \rightarrow_{rm} p\beta s $ と言います。記号列 $w$ の最右導出は、$w$ に登場する記号のうち、最も右に登場する非終端記号を導出によって記号列に変換する操作を意味します。

特に、記号列 $S$ から最右導出を $0$ 回以上繰り返して記号列 $T$ を導出することを $S {\rightarrow}_{rm}^{*} T$ と表記します。

$S \rightarrow_{rm}^{*} T$ を通して $n$ ステップの導出が行われるとすると、最右導出において考えるべきことは、各 $1 \leq i \leq n$ に対して $i$ 番目のステップで適用される導出 $(A_i \rightarrow_{rm} \beta_i)$ が何かを特定することです。

また、記号列 $\beta$ を導出する非終端記号 $A$ を特定することを還元と言い、還元関係を $\beta \rightarrow^{-1} A$ と表記することにします。同様に、記号列 $Y = p\beta s$ に登場する記号 $\beta$ を還元して記号列 $X = pAs$ に遷移することも還元関係 $Y \rightarrow^{-1} X$ で表記します。特に $X\rightarrow Y$ が最右導出であるとき、$Y \rightarrow^{-1} X$ を最右還元と言い、$Y \rightarrow_{rm}^{-1} X$ と表記します。

視覚的な理解

$S {\rightarrow}^{*}_{rm} T$ に適用される $n$ 個の最右導出 $(A_1 \rightarrow \beta_1) , $ $(A_2 \rightarrow \beta_2) , $ $\dots , (A_n \rightarrow \beta_n)$ に対して、記号列全体の最右導出と最右還元の過程を視覚化したものを以下に例示します。

図 A

導出の過程を下から逆向き (上向き) にたどったものは還元の過程と対応します。よって、還元の過程を特定することは導出の過程を特定することと等しいことがわかります。上昇型構文解析では初期状態であるトークン列 $T$ に対して最右還元を繰り返し、最終的に $S$ を得る還元の過程を特定します。

還元の特定

記号列 $pAs$ から最右導出で得られる記号列 $ t = p \beta s $ を最右還元するためには、まずは $t$ のうち還元が行われる記号列である $\beta$ の登場箇所を特定しなければなりません ($p$ は空列を含む記号列、$s$ は空列を含む終端記号列とします)。

ここで、$\beta$ の登場箇所を特定するために以下で定められる正規言語 $L$ を導入します ($L$ が正規言語である説明は割愛)。

• $L = {\space p \beta \space |\space S \rightarrow_{rm}^* \space p A s \rightarrow_{rm}\space p \beta s ,\space p \in (\sum \cup N)^* ,\space s \in \sum^* }$ : 「$S$ から最右導出される記号列の、最後の導出による遷移で変化があった部分までの接頭辞」としてあり得る記号列の集合。

$L$ は正規言語なので、$L$ に属する記号列を受理する決定性オートマトン $D$ を構築することができます。このオートマトン $D$ の目的は、最右還元 $p \beta s \rightarrow_{rm}^{-1} pAs$ において還元が発生する記号 $\beta$ の位置の特定 (記号列 $p\beta$ の特定 ) と、どの還元が適用されたかの特定です (どの還元が適用されたかがわかれば、$p\beta$ から還元を適用すべき $\beta$ と、その登場位置の両方を特定できます)。

ここで、オートマトン $D$ に新たに性質 : 「受理状態に到達すれば、入力途中であっても受理して終了する」を加えます。$D$ の定義より、$D$ が受理するまでに読み込んだ記号列は 「$S$ から最右導出される記号列の、最後の導出による遷移で変化があった部分までの接頭辞」としてあり得るもののいずれかです。さて、このオートマトン $D$ は、$ t = p \beta s $ の最右還元箇所 $p\beta$ を一意に特定して、さらに還元を行う記号列 $\beta$ を特定できるでしょうか。

結論、一般的には還元の特定は一意ではないですが、次回の記事で
紹介する $\mathrm{LR}(0)$ 構文と、$\mathrm{LR}$ 構文解析アルゴリズムを考えることでこれを解決できます。

上昇型構文解析のキーは $\mathrm{LR}(0)$ 構文を設計すること、ないし設計した構文を $\mathrm{LR}(0)$ 構文に上手く書き換えることであると言えます。詳細は次回以降の記事で説明します。

下降型構文解析

一般に、記号列 $w$ は [ 非終端記号 $A$ ] と [ 空列を含む終端記号列 $p$ ] と [ 空列を含む記号列 $s$ ] の $3$ つを用いて $w = pAs$ と表すことができます。導出 $A \rightarrow \beta$ によって $w$ が $pAs \rightarrow p\beta s $ と遷移するとき、これを最左導出 $pAs \rightarrow_{lm} p\beta s $ と言います。記号列 $w$ の最左導出は、$w$ に登場する記号のうち、最も左に登場する非終端記号を導出によって記号列に変換する操作を意味します。

文 $T$ を生成する構文が特定されている場合、下降型構文解析は非常に簡潔に $T$ の構造を解析できます。具体的な説明をするために、まずは簡潔な自前定義の Python 言語を定義する構文の例を紹介します。

Minimal Python

以下で定義する Minimal Python を、C++ を経由して機械語に翻訳する C++ プログラムを作ることを想定します。また、コンパイラ作成の Baby Step としてこの記事ではインタープリタを作ることにします。

構文解析の説明のための例として、独自に Minimal Python を定義します。Minimal Python が持つ構文は以下の $3$ つとします。

• 変数宣言 : 識別子 : int = 式 ;
• 代入 : 識別子 = 式 ;
• 出力 : print(式);

文脈自由文法における $\rightarrow$ の代わりに ::= を用いる BNF という記述方法があります。今回は BNF の右辺に正規表現を使用できる記述方法 : EBNF を用いて記述します。

これら $3$ つの構文に登場する終端記号をまとめたものが { ID , NUM , int , print , ( , ) , + , : , ; , = , + , - , * , 空文字 } です。

正規表現一覧

• 正規表現を含む記号列 $A$ に対して ${A} := $ 記号列 $A$ を一つの記号として見たもの
• 記号 $a,b$ に対して、$(a , b) := $ $a$ または $b$
• 記号列 $a,b$ に対して、$a\space\mathrm{OR}\space b := $ $a$ または $b$
• 記号 $a$ に対して、$a[*] :=$ $a$ を $0$ 回以上繰り返し連結
• 記号 $a$ に対して、$a[+] :=$ $a$ を $1$ 回以上繰り返し連結

変数宣言の構文

• <変数宣言> ::= ID : int = <式> ;
• <式> ::= 後述

代入の構文

• <代入> ::= ID = <式> ;
• <式> ::= 後述

出力の構文

• <出力> ::= print ( <式> ) ;
• <式> ::= 後述

式の構文

• <式> ::= <項>{( + , - ) <項>}$[*]$
• <項> ::= - <項> $\mathrm{OR}$ ( <式> ) $\mathrm{OR}$ NUM $\mathrm{OR}$ ID $\mathrm{OR}$ <項> <接尾辞項>
• <接尾辞項> ::= * <項> $\mathrm{OR}$ 空文字

再帰的パーサー (実行例)

今回作るインタープリタは、与えられたトークン列の先頭から読み込みを開始し、構文に従ってトークン列から「構造化されたトークンのまとまり」を再帰的に取り出します。取り出されたトークンのまとまりはインタープリタ内で解釈され、実行されます。

例えば Python ソースコードを解析して得られたトークン列 $T$ = ID : int = NUM + NUM * ( MUM - NUM ) ; があるとしましょう。$T$ には : , = , ; が登場するので、$T$ を生成する構文 $S$ は <変数宣言> であることがわかります。

構文 $S$ がわかっているので、降下型構文解析は $S$ に対して最左導出を繰り返します。<変数宣言> 構文は ID : int = <式> ; を導出するので、$T$ もまた ID : int = <式> ; であることがわかります。

トークン列のある箇所から構文 $X$ で生成される文を取り出す手続きを $X$ パーサーと表記することにします。今、$T$ は構文 <変数宣言> から生成されることがわかっているので、$T$ の先頭から <変数宣言> パーサーを実行します。

<変数宣言> パーサーを呼んでいるので、$T$ の先頭からはトークン ID , : , int , = が一つずつ順取り出されます。このとき、パーサーが読んだ ID : int = の部分は、インタープリタ内に 変数の宣言/初期化の準備 などの処理を実装することで直接機械語に落とし込むことができます。

<変数宣言> パーサーは次に $T$ から <式> を取り出すのですが、<式> は非終端記号なので $T$ に直接登場することはありません。そこで、$T$ の続きの部分が <式> という構文から生成されるトークン列であると捉え、今度は $T$ の続きの部分から <式> パーサーを呼び出して <式> を取り出します。

<式> パーサーも同様に再帰的に <項> パーサーや <接尾辞項> パーサーを呼び出し、$T$ から <式> 構文の文 : NUM + NUM * ( MUM - NUM ) を取り出します。このとき、式として取り出した文の構造はパーサーの処理によって解明されるので、NUM + NUM * ( MUM - NUM ) に入る具体的な数値がわかっているはずです。

<式> パーサーを呼ぶ前の <変数宣言> パーサーで、これから変数に値を代入するという文 ID , : , int , = を呼んでいたので、<式> パーサー が取り出した値を変数に格納する処理を行います (実際は記号列に登場する全ての ID や NUM にはそれぞれ具体的な変数名や数値が割り当てられています)。

最後に <変数宣言> パーサーの続きで文末の ;を呼んで、変数の宣言と初期化が完了します。

付録

Minimal Python の下降型構文解析を行う C++ プログラムを書きました。なお、記事内の EBNF と若干異なる文法を採用しているので、この記事で学んだ知識を活かして解読してください。

Python を実行する C++ プログラム

Copyright (c) ©️ 2024 NokonoKotlin Released under the MIT license

#include<string>
#include<vector>
#include<iostream>
#include<unordered_map>
using std::string;
using std::vector;
using std::cout;
using std::cerr;
using std::endl;



/*
    
    記事で書いた EBNF と異なり、ID や NUM も字句解析せずに、パーサーによって具体的な値を取り出すことにする。

    EBNF : 
    token : {: , = , + , - , * , ( , ) , ;  , [0-9] , ASCII文字 , print , int}
    非終端 : {<初期化> , <代入> , <型> , <式> , <項> ,<接尾辞項> , <数> , <ID> , <出力> }
    正規表現 : { [*] : 0 度以上繰り返し , [+] : 1 度以上繰り返し , (a,b) : a または b }

    生成 : 
        <初期化> ::= ID:<型> = <式>; | ID:<型>;
        <代入> ::= ID = <式>;
        <型> ::= int
        <式> ::= <項>{(+,-)<項>}[*]
        <項> ::= -<項> | (<式>) | <数> | <ID> | <項><接尾辞項>
        <接尾辞項> ::= *<項> | 空文字列
        <数> ::= [1-9][0-9][*]
        <ID> ::= [a-z A-Z , _ ][a-z A-Z , _ , 0-9][*]
        <出力> ::= print(<式>);
*/


/*
    パーサ : パーサに渡すのは正常系のみ。以上な場合は内部エラーとして終了。
    例外 : 発生した最も深い例外をそのまま返す
*/

#define PARSE_ERROR(S,cur) "Reader Error occured on " + std::to_string((cur)) + ":" + S + "."


// パーサのプロトタイプ宣言
int parseDIGIT(string&  , int& );
int parseNUMBER(string&  , int& );
int parseSuffixTERM(string&  , int& );
int parseTERM(string&  , int& );
int parseEXPRESSION(string&  , int& );

std::unordered_map<string,bool> exist_int; // [id] := id が登録済みかどうか
std::unordered_map<string,int> value_int; // [id] := id に格納されている値


//　文の種類 : 初期化,代入,出力 
enum BNF_Token{INIT , ASSIGN , OUT};


// 空白をなくす
void shrinkspace(string& S , int &cur){
    while(cur < S.size() && S[cur] == ' '){cur++;}
}

// S の cur 以降の文の種類を特定する
BNF_Token Reader(string &S , int& cur){
    if(cur >= S.size())throw(string("invalid order ( no ; was found)."));
    std::unordered_map<char,bool> found;
    while(true){
        if(cur >= S.size())throw(string("invalid order ( no ; was found)."));
        if(S[cur] == ';'){
            cur++;
            break;
        }
        found[S[cur++]] = true;
    }
    // 要件が 3 種類だけなので場合分けするのだ
    if(found[':'])return INIT;
    if(found['='])return ASSIGN;
    return OUT;
}


// 文字列 S の cur 文字目から ID を抽出する
string parseID(string& S , int& cur){
    string ID = "";
    shrinkspace(S,cur);
    if(cur>=S.size() || isdigit(S[cur]))throw(PARSE_ERROR(S,cur));
    while(true){
        if(cur>=S.size())throw(PARSE_ERROR(S,cur));
        if(!isdigit(S[cur]) && !isupper(S[cur]) && !islower(S[cur]) && S[cur] != '_') break;
        ID += S[cur++];
    }
    if(ID.size() == 0)throw(PARSE_ERROR(S,cur));
    return ID;
}

// 文字列 S の cur 文字目から 型 を抽出する
string parseTYPE(string& S , int& cur){
    string ID = "";
    shrinkspace(S,cur);
    if(cur>=S.size() || isdigit(S[cur]))throw(PARSE_ERROR(S,cur));
    while(true){
        if(cur>=S.size())throw(PARSE_ERROR(S,cur));
        if(!isdigit(S[cur]) && !isupper(S[cur]) && !islower(S[cur]) && S[cur] != '_') break;
        ID += S[cur++];
    }
    if(ID.size() == 0)throw(PARSE_ERROR(S,cur));
    return ID;
}

// 数字を読んで返す
int parseDIGIT(string& S , int& cur){
    shrinkspace(S,cur);
    if(cur>=S.size() || !isdigit(S[cur]))throw(PARSE_ERROR(S,cur));
    return S[cur++] - '0';
}

// 数を読んで返す
int parseNUMBER(string& S , int& cur){
    int res = 0;
    shrinkspace(S,cur);
    if(cur>=S.size() || !isdigit(S[cur]))throw(PARSE_ERROR(S,cur));
    while(true){
        if(cur>=S.size() || !isdigit(S[cur]))break;
        res *= 10;
        res += parseDIGIT(S,cur);
    }
    return res;
}

// 接尾辞項
int parseSuffixTERM(string& S , int& cur){
    int res = 0;
    shrinkspace(S,cur);
    if(cur>=S.size())throw(PARSE_ERROR(S,cur));
    if(S[cur] != '*')return 1;// int 乗算の単位元
    cur++;
    return parseTERM(S,cur);
}

// 項
int parseTERM(string& S , int& cur){
    int res = 0;
    shrinkspace(S,cur);
    if(cur>=S.size())throw(PARSE_ERROR(S,cur));
    // <項> ::= <項><接尾辞項> の、右辺の<項> を特定する (-<項> or (<式>) or <数> or <ID> )
    if(S[cur]=='-'){
        // 負の項
        cur++;
        res = parseTERM(S,cur)*int(-1);
    }else if(S[cur]=='('){
        // () 付きの式
        cur++;
        res = parseEXPRESSION(S,cur);
        if(cur>=S.size() || S[cur] != ')')throw(PARSE_ERROR(S,cur));
        cur++;// ) の分
        return res;
    }else if(isdigit(S[cur])){
        // 数
        res = parseNUMBER(S,cur);
    }else if(isupper(S[cur]) || islower(S[cur]) || S[cur] == '_'){
        // 識別子
        string ID = parseID(S,cur);
        if(exist_int[ID] == false)throw(PARSE_ERROR(S,cur));
        res = value_int[ID];
    }else {
        throw(PARSE_ERROR(S,cur));
    }
    // 接尾辞項が空になれば勝手に再帰ループが終了する
    if(cur < S.size())res *= parseSuffixTERM(S,cur);
    return res;
}

// 式
int parseEXPRESSION(string& S , int& cur){
    shrinkspace(S,cur);
    if(cur>=S.size())throw(PARSE_ERROR(S,cur));
    int res = parseTERM(S,cur);

    while(cur < S.size()){
        shrinkspace(S,cur);
        if(S[cur] == '+') {cur++; res += parseTERM(S,cur);}
        else if(S[cur] == '-') {cur++; res -= parseTERM(S,cur);}
        else if(S[cur] == '*') {cur++; res *= parseTERM(S,cur);}
        else break;
    }
    return res;
}

// 宣言/初期化 を実行
// ID:<型> = <式>; | ID:<型>; を読むだけ
void execute_init(string& S , int& cur){
    string ID = parseID(S,cur);
    if(ID == "print" || ID == "int")throw(ID + " is reserved as language support.");
    if(exist_int[ID] == true)throw(ID + " is already used.");
    shrinkspace(S,cur);
    if(cur>=S.size() || S[cur] != ':')throw(PARSE_ERROR(S,cur));
    cur++;// : のぶん
    string TYPE = parseTYPE(S,cur);
    shrinkspace(S,cur);
    if(cur>=S.size())throw(PARSE_ERROR(S,cur));
    // 型ごとに処理
    if(TYPE == "int"){
        if(S[cur] == '='){
            cur++;// = のぶん
            int val = parseEXPRESSION(S,cur);
            value_int[ID] = val;
        }
        exist_int[ID] = true;
    }else{
        throw(string("undefined type was used."));
    }
    shrinkspace(S,cur);
    if(cur>=S.size() || S[cur] != ';')throw(string("; must be put on end of order."));
    cur++;// ; のぶん
    return;
}

// 代入を実行
// ID = <式>; を読むだけ
void execute_assign(string& S , int& cur){
    string ID = parseID(S,cur);
    if(ID == "print" || ID == "int")throw(ID + " is already used.");
    if(exist_int[ID] == false)throw(ID + " is not declared.");
    shrinkspace(S,cur);
    if(cur>=S.size() || S[cur] != '=')throw(PARSE_ERROR(S,cur));
    cur++;// = のぶん
    int val = parseEXPRESSION(S,cur);
    value_int[ID] = val;
    shrinkspace(S,cur);
    if(cur>=S.size() || S[cur] != ';')throw(string("; must be put on end of order."));
    cur++;// ; のぶん
    return;
}

// 出力を実行
void execute_print(string& S , int& cur){
    string ID = parseID(S,cur);
    if(ID != "print")throw(string("undefined function."));
    shrinkspace(S,cur);
    if(cur>=S.size() || S[cur] != '(')throw(PARSE_ERROR(S,cur));
    cur++;
    int v = parseEXPRESSION(S,cur);
    shrinkspace(S,cur);
    if(cur>=S.size() || S[cur] != ')')throw(PARSE_ERROR(S,cur));
    cur++;// ) のぶん
    shrinkspace(S,cur);
    if(cur>=S.size() || S[cur] != ';')throw(string("; must be put on end of order."));
    cur++;// ; のぶん
    cout << "   >> " << v << endl;
    return;
}


// ソースコードを実行void execute(string source){
    vector<BNF_Token> order;
    int grobal_cursor = 0;// パースする位置 (左から)
    while(source.size() > grobal_cursor){
        try{
            order.push_back(Reader(source,grobal_cursor));    
        }catch(string es){
            cout << es << endl;
        }
    }
    grobal_cursor = 0;
    for(int o : order){
        try{
            if(o == INIT)execute_init(source,grobal_cursor);
            else if(o == ASSIGN)execute_assign(source,grobal_cursor);
            else if(o == OUT)execute_print(source,grobal_cursor);
            else throw("undefined order.");
        }catch(string es){
            cout << es << endl;
        }
    }
}


int main(){
    while(true){
        cout << "<< ";
        string code;
        getline(std::cin,code);
        if(code == "Q")break;
        execute(code);
    }
    return 0;
}

使用例

実行するとインタラクティブ Python のような CUI が出ます。

<<

試しに適当な命令を行ってみましょう。

<< b:int = 122;      
<< 

エラーが出なかったので、無事命令できたみたいです。さらに命令してみましょう。

<< b:int = 122;      
<< b:string = "okoyeiyu&NokonoKotlin";
b is already used.
<< 

今度はエラーが出ました。色々構文に違反してますが、最左導出で初めてヒットしたエラーが出力され、この命令は無かったことにされます。

<< b:int = 122;      
<< b:string = "okoyeiyu&NokonoKotlin";
b is already used.
<< print(-5+b*(b-22));
    >> 12195
<<

式の出力もできます。

<< b:int = 122;      
<< b:string = "okoyeiyu&NokonoKotlin";
b is already used.
<< print(-5+b*(b-22));
    >> 12195
<< c:int = b+2-4*(b+9);  
<<

新たに変数を宣言して。

<< b:int = 122;      
<< b:string = "okoyeiyu&NokonoKotlin";
b is already used.
<< print(-5+b*(b-22));
    >> 12195
<< c:int = b+2-4*(b+9);  
<< print(c*100);
    >> -40000
<<

出力できたところでこの記事を終わろうと思います。多分まだコンパイラの話の記事を書くと思うので、乞うご期待です。see you again.