Geekly Articles each Day

LLVMを使用したプログラミング言語の作成。 パート1：はじめにと字句解析

チュートリアル「LLVMを使用したプログラミング言語の作成」へようこそ。 このチュートリアルでは、簡単なプログラミング言語の作成方法を紹介すると同時に、それがいかに簡単で興味深いものであるかを示します。また、他のプログラミング言語に適用できる基本的な知識も提供します。 このチュートリアルのコードは、LLVMを使用して作成するための起動パッドとしても使用できます。

この教科書の目的は、段階的な作成の説明である言語を徐々に紹介することです。 これにより、言語設計とLLVMの使用に関するかなり広範な問題をカバーし、大量の不必要な詳細なしにコードを同時に表示および説明することができます。

このチュートリアルは、いくつかのコンパイル手法とLLVMの詳細を教えているが、最新のソフトウェア開発の原則は教えていないことをあらかじめ知っておくと便利です。 実際には、これは、プレゼンテーションを簡素化するために最も単純化および縮小化されたソリューションを使用することを意味します。 したがって、たとえば、どこでもメモリを操作するコードは、 Visitorなどの優れたデザインパターンを使用せずにグローバル変数を使用します。これは最良の方法ではありませんが、非常にシンプルで明確です。 コードを理解し、将来のプロジェクトの基礎として使用する場合、そのような欠点を修正することは問題ではありません。

このチュートリアルは、すでに知っている部分や興味のない部分を簡単にスキップできるように作成しようとしました。 教科書の構造は次のとおりです。
チュートリアルの終わりまでに、コメントと空白行を考慮せずに700行弱のコードを記述しました。 この少量のコードを使用して、手書きの字句解析プログラム、パーサー、AST、JITによるコード生成のサポートなど、重要なプログラミング言語用の非常に優れたコンパイラーを作成しました。 他のシステムにはHello、World-styleチュートリアルがありますが、このチュートリアルの幅はLLVMの力を示す素晴らしい証拠です。 言語とコンパイラの構築に興味がある場合は、このチュートリアルを必ずお読みください。

そしてもう1つ、私たちはあなたが言語を拡張し、私たちの裁量でそれで遊ぶことを期待しています。 コードを取り、必死にプログラミングを開始し、夢中になります。コンパイラはあなたを怖がらせるべきではありません-言語で遊ぶのはとても楽しいです！

舌の万華鏡

このチュートリアルでは、「 カレイドスコープ 」と呼ばれるおもちゃのプログラミング言語を説明します（名前はギリシャ語の3つの単語「美しい」、「見える」、「見える、見る」に由来します）。 カレイドスコープは、関数の定義、条件の使用、数学などを可能にする手続き型言語です。 調査中に、万華鏡を拡張してif / then / elseの構成、ループ、ユーザーステートメント、シンプルなコンソールインターフェイスを使用したJITコンパイルなどをサポートします。

簡単にするために、Kaleidoscopeにはデータタイプが1つだけあります。64ビットの浮動小数点数（Cの「double」など）です。 したがって、すべての値は倍精度の実数であり、言語は型宣言を必要としません。 これにより、言語が非常に美しくなり、構文が簡素化されます。 たとえば、次の簡単な例ではフィボナッチ数を計算します 。

#  x-   def fib(x) if x < 3 then 1 else fib(x-1)+fib(x-2) #    40- . fib(40)

また、Kaleidoscopeが標準ライブラリ関数を呼び出すことを許可しました（LLVM JITはこれを非常に簡単にします）。 これは、externキーワードを使用して関数を使用する前に宣言できることを意味します（これは相互に再帰的な関数にも役立ちます）。 例：

 extern sin(arg); extern cos(arg); extern atan2(arg1 arg2); atan2(sin(.4), cos(42))

より興味深い例は第6章にあります。そこでは、マンデルブロ集合をさまざまな近似度で表示する万華鏡の小さなアプリケーションを作成します。

そして今、この言語の実装に飛び込みましょう！

字句解析器

プログラミング言語の実装に関して、最初に必要なことは、テキストファイルを処理し、その中のコードを認識する機能です。 これを行う従来の方法は、「 字句解析器 」（または「スキャナー」）を使用して入力ストリームを「トークン」に分割することです。 字句解析プログラムによって返される各トークンには、コードのユニットと、場合によってはメタデータ（数値など）が含まれます。 まず、可能性を特定します。

 //     [0-255],   , //       enum Token { tok_eof = -1, //  ( ) tok_def = -2, tok_extern = -3, //  (, ) tok_identifier = -4, tok_number = -5, }; static std::string IdentifierStr; // ,  tok_identifier (  - ) static double NumVal; // ,  tok_number (  - )

字句解析ツールによって返される各トークンは、トークン列挙値のいずれか、またはASCII値として返される「+」文字のように「不明」になります。 現在のトークンが識別子の場合、グローバル変数IdentifierStrには識別子名が含まれます。 現在のトークンが数値リテラル（1.0など）の場合、NumValにはその値が含まれます。 簡単にするためにグローバル変数を使用していますが、これは実際の使用に最適な選択とはほど遠いことに注意してください。

実際、字句解析器はgettokと呼ばれる単一の関数によって実装されています。 Gettok関数は、呼び出されると、標準入力ストリームから次のトークンを返します。 彼女の定義は次のように始まります。

 /// gettok -       . static int gettok() { static int LastChar = ' '; //  . while (isspace(LastChar)) LastChar = getchar();

gettokはgetchar（）C関数を呼び出して、標準入力の1つから文字を読み取ります。 それらを認識し、LastCharに最後に読み取った文字を保存しますが、処理はしません。 彼女が最初にすべきことは、トークン間のスペースを無視することです。 これは上記のサイクルで達成されます。

次のgettokアクションは、識別子と「def」などの特別なキーワードを認識することです。 Kaleidoscopeは、次の単純なループでこれを行います。

 if (isalpha(LastChar)) { // : [a-zA-Z][a-zA-Z0-9]* IdentifierStr = LastChar; while (isalnum((LastChar = getchar()))) IdentifierStr += LastChar; if (IdentifierStr == "def") return tok_def; if (IdentifierStr == "extern") return tok_extern; return tok_identifier; }

このコードは、識別子の解析中にグローバル変数「IdentifierStr」を収集することに注意してください。 さらに、言語キーワードは同じサイクルでチェックされます。 数値の場合、すべてが類似しています：

 if (isdigit(LastChar) || LastChar == '.') { // : [0-9.]+ std::string NumStr; do { NumStr += LastChar; LastChar = getchar(); } while (isdigit(LastChar) || LastChar == '.'); NumVal = strtod(NumStr.c_str(), 0); return tok_number; }

これは、入力を処理するための非常に単純なコードです。 数値を読み取るときは、strtod C関数を使用して数値に変換し、NumValに保存します。 ここでは十分なエラーチェックが行われていないことに注意してください。値「1.23.45.67」は、「1.23」に入力したかのように読み取られて処理されます。 このようなエラーをチェックすることでコードを簡単に補完できます:)。 それではコメントに対処しましょう。

 if (LastChar == '#') { //    . do LastChar = getchar(); while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); if (LastChar != EOF) return gettok(); }

コメントを定義したら、行末までの文字をスキップして、次のトークンを返します。 次に、入力が上記のケースのいずれかと一致しない場合、これは「+」などの演算子またはファイルの終わりです。 これらはこのコードによって処理されます：

 //   . if (LastChar == EOF) return tok_eof; //         ASCII int ThisChar = LastChar; LastChar = getchar(); return ThisChar; }

同時に、Kaleidoscope言語用の完全な字句アナライザーがあります（字句アナライザーコードの完全なリストは 、チュートリアルの次の章にあります）。 次に、抽象構文ツリーの構築に使用する単純なパーサーを開発します。 その後、レキシカルとパーサーを一緒に使用できます。

UPD。
学習に役立つ便利なリンク：

Source: https://habr.com/ru/post/J119850/

More articles:


All Articles