自作プログラム言語を作成した話 (1) Lexer編

今回セキュリティキャンプ全国大会2019にて、自作の言語を作成しました。

今回言語を自作するに当たって多くの資料をもとにしましたが、
`yacc`などライブラリを使っているものが多く、言語作成の本質を調べるのに苦労したので、
今回は一切外部ライブラリを使わずプログラム言語を作成する手法をご紹介したいと思います。

また、今回の自作言語では汎用的なパーサコンビネータを作成するので、
私が作成した言語とは文法が異なっていても同じ手法で作成できると思います。

記事は`C++`で記述していますが、`C++`特有の記述は可能な限り省いてあるので、
`c++`への理解がなくても記事は理解できると思います。
場合によっては分かりやすさを重視し不正な`c++`コードとなっている場合があります。
実際の動作は[GitHub](https://github.com/ObuchiYuki/WorkFlow)を参照ください。

## 目次

- 言語仕様 **(本記事)**

- Lexer作成 **(本記事)**

- パーサコンビネータ作成 

- AST構築

- インタプリタ実行

- 型チェック＋型推論

- コンパイラ実行

  

長いので複数記事に分けます。

## 言語仕様



今回作成した言語は
**Shell + 静的型付け + オブジェクト指向 + 型推論**という言語です。

シェルのパイプは好きなのですが、複雑なことはシェルではやりにくいので、
ある程度複雑なこともできるシェルとして作成しました。

軽く説明すると以下のような仕様です。

```
def a = 1 // 変数
def b = 5 // 変数
mut c = 3 // 定数

print(a + b + c) // 9

a = 2 // コンパイルエラー
c = 2 // OK

class Person {
	def name: String
	mut age: Int
	
	mut gainAge() {
		self.age += 1
	} 
	
	init(name:String, age:Int) {
		self.name = name
		self.age = age
	}
}

extension Person {
	def sayName() {
		if age < 20 {
			print(self.name)
		}
	}
}
 
def alice = Person("Alice", 16)
def bob = Person("Bob", 24)

alice.sayName()  // "Alice"
bob.sayName()		 // 出力なし

// パイプ使用
find(from: .desktop, named: "*.swift")
	|> count
	|> reduce(+)
```



今回のコードは [https://github.com/ObuchiYuki/WorkFlow](https://github.com/ObuchiYuki/WorkFlow) に上げてあるので良ければご覧ください。



## Lexer 作成

まず、言語を解析するためには入力された文字をトークンに分割しなければいけません。例えば、

```
if name == "Alice" {
	print("Alice!")
}
```

なら、

```
[
　"if", "name", "==", "Alice", "{", "改行",
 　　 "print", "(", "Alice", ")", "改行",
  "}"
]
```

というトークンに分解する必要があります。また、これ以外にもそのトークンがなんであるのかのメタデータが必要となります。

```
[
  ("if", 識別子),
  ("name", 識別子),
  ("==", 演算子),
  ("Alice", 文字列),
  ("{", 記号),
  ...
]
```

のように、文字＋タイプが一区切りのトークンとなります。これを行うのが**Lexer**です。**Lexer**は正規表現で行うのが一般的ですが、今回はもう少し原始的な方法で作成してみようと思います。



### 実装

分かりやすさのためにいくつか(名前空間・コンストラクタなど)省略しています。
実際の実装は GitHub を参照ください。

#### Tokenクラス

まず分割した結果となる、`Token ` クラスです。

```C++
/// トークンの種類
enum TokenType {
  EndFile     // ファイルの終端
  EndLine     // 行の終端
  Identifier  // 識別子
  Symbol      // 記号
  Operator    // 演算子
  Integer     // 整数リテラル
  String      // 文字列リテラル 
};

// トークン本体
class Token {
  TokenType type;
  string value;
}

/// ファイル終端をあらわすToken
auto EOFToken = ...
/// 行終端をあらわすToken
auto EOLToken = ...
  
/// トークンのポインタ型
typedef std::shared_ptr<Token> TokenPtr;
```



#### Lexer

次に`Token`列を生成する`Lexer`です。

Lexerを使う際に重要となってくるのが、`readNext` と `peek` というメソッドです。
メモリを抑えるため `readNext` では読み終わったトークンは捨てる仕様になっています。
しかし、これでは文法に応じた先読みができません。

なので、`peek ` (= 覗き見る) メソッドで先を見ることができるようにします。
`peek`で覗き見た`Token`も捨てずに`queue`にとっておくことで次の読み込みが高速になります。



`C++` ではクラスの定義と実装を分ける流儀であり、
記事としても見やすいと考えたのでファイルを分割して解説します。

##### `Lexer.hpp` 定義

```c++
class Lexer {
  // -- プロパティ --
private: 

  // ファイル読み取り用Reader (&は参照にするため　)
  ifstream& reader; 
  
  // 現在のTokenのIndex (後で使います。)
  int tokenIndex = 0;		 
  // 次の行があるか　(ifstreamの都合上必要)
  bool hasMoreLine = true;	
  // 読込済みのToken列
  vector<TokenPtr> queue = {};　
  
  // -- メソッド --
private:  
	/// 先を読み込みます。読み込みができたらtrueできなかったらfalseを返します。　
  auto loadNext(int stride) -> bool; 
  
public:
  // 次のTokenを読みます。読んだところからメモリから消します。
  auto readNext() -> TokenPtr;　
	// stride分、次のQueueを先読みします。メモリから消すことはありません。
  auto peek(int stride) -> TokenPtr;
  // 絶対Indexを返します。（後で使います。）
  auto absIndex(int gap) -> int; 
  
private:
  // 次の行を読み込む
  auto readLine() -> void; 
}
```



##### `Lexer.cpp ` 実装

`loadNext`

```c++
/// 先を読み込みます。
/// 読み込みができたら(=ファイルがまだあるなら) true
/// できなかったらfalseを返します。　
auto Lexer::loadNext(int stride) -> bool {
	  // strideの分が保存済みTokenに存在しない間
    while (stride >= queue.size()) { 
	      // 次の行があるならば、
        if (hasMoreLine) {
	          // 1行読み込み
            readLine(); 
        }else{
            return false;
        }
    }
    
    return true;
};
```

`readNext`

```c++
// 次のTokenを読みます。読んだところからメモリから消します。
auto Lexer::readNext() -> TokenPtr {
  	// 一個先が読み込み可能ならば
    if (loadNext(0)){
      	// 先頭の一個を取り出し
				auto removedToken = queue[0]; 
      	// 先頭の一個を消す
        queue.erase(queue.begin(), queue.begin() + 1);
        index += 1;
        return removedToken;
    } else { // 読み込めない = ファイル終端 なので EOFTokenを返す。

        return EOFToken;
    }
}
```

`peek`

```c++
auto Lexer::peek(int stride) -> TokenPtr {
  	// stride個先が読み込み可能ならば
    if (loadNext(stride)){
        return queue[stride];
    } else { // 読み込めない = ファイル終端 なので EOFTokenを返す。
        return wf::token::EOFToken;
    }
}
```



次の `readLine`メソッドなのですが、かなり長いので分割して解説します。　

まず、ファイルの読み込みについてです。
バッファーを作りそこに1行読み込みます。

```c++
auto Lexer::readLine() -> void {
  	//　バッファー作成
    auto lineBuffer = std::string();
    // 1行読み込み（成功したか）
  	auto success = getline(reader, lineBuffer)
      
    if (!success) { // 失敗(ファイル終端)ならば
        hasMoreLine = false;
        return;
    }
    
  	// 終端場所
    let endPos = lineBuffer->size();
    if (endPos == 0) { // 空行ならば
        return;
    }
  	
  	// 読み込み環境 (説明は以下)
  	auto env = ReadingEnvironment(lineBuffer);
```

#### `ReadingEnvironment`

次に `ReadingEnvironment` というクラスを作成します。
これは解釈を行う際に読み込み場所、現在の行などをまとめて扱うためです。

`ReadingEnvironment`

```c++
class ReadingEnvironment {
    /// 現在読んでいる行
		string line;
        
    /// 今読んでいる行の場所です。読み込みに応じて変化します。
    int columun;
    
    /// 先の文字を返す
  	auto next(int gap) -> char {
        return line[columun + gap];
    }
};

```

##### `readLine`の続き

`env`の`columun`が行終端に達するまで、読み込みます。
行端に達したら行端記号を挿入します。

その際に多くの条件分岐があるので、その中身を解説していきます。

```c++
		while (env.columun < endPos) {
      	// 最初の文字を読み込み
        auto c = env.top(); 
        
        if(isLineComment(env)){ // コメントならば
	          // コメントを飛ばす
            skipComment(env);   
            
        }else if (isWhiteSpace(c)){ // 空白ならば
            // 空白を飛ばす
            skipWhiteSpace(env);
            
        }else if (c == '\"') {  // 引用符 (") ならば
          	// 文字列を読み込み queue に追加
            queue.push_back(readStringLiteral(env));
            
        }else if (isNumber(c)) { //　数字ならば
          	// 数字を読み込み
            queue.push_back(readIntergerLiteral(env));
            
        }else if (isSymbol(c)) { // 記号ならば
          	// 記号を読み込み
            queue.push_back(readSymbol(env));
            
        }else if (isOperatorMember(c)) { // 演算子ならば
          	// 演算子を読み込み
            queue.push_back(readOperator(env));
            
        }else { // それ以外は識別子とみなし
            // 識別子を追加
            queue.push_back(readName(env));
        }
        /// 最後に行端記号を挿入
	      queue.push_back(wf::token::EOLToken);
    }
```



`isLineComment` & `skipComment`

コメントは `// `で始まり`//` 以降の行は全て読み飛ばしていいので、
`//`を見つけたら、`env.columun`を行端まで移動します。

```c++
auto isLineComment(ReadingEnvironment& env) -> bool {
  	// 現在の行が // ならば true
    return (env.next(0) == '/' and env.next(1) == '/');       
}

auto skipComment(ReadingEnvironment& env) -> void {
  	// 行端まで読み飛ばす
    env.columun = (int)env.line.size();
}
```



`isWhiteSpace` & `skipWhiteSpace`

空白も読み飛ばしていいので、空白を見つけたら空白が続くだけ読み飛ばします。　

```c++
auto isWhiteSpace(char c) -> bool {
  	// 現在の文字が ' ' or '\t' ならば
    return c == ' ' or c == '\t';
}

auto skipWhiteSpace(ReadingEnvironment& env) -> void {
  	// 空白を読み飛ばす
		auto c = env.next(0);
    while (isWhiteSpace(c)){
        env.columun += 1;
        c = env.next(0);
    }
    env.columun -= 1;
}
```



`readStringLiteral`

文字列リテラルを読み込みます。
まだエスケープ(`\"`) には対応していないので、次の引用符が見つかるまで読み込みます。

```c++
/// 引数に渡された環境をもとに、StringLiteralをのTokenを構成し返します。
auto readStringLiteral(ReadingEnvironment& env) -> TokenPtr{
  // 最初の引用符を読み飛ばす
  env.columun += 1;
  
  auto buffer = string();
  // 次の引用符が見つかるまで
  while (env.line[env.columun] != '\"') {
    buffer += env.next(0);
    env.columun += 1;
  }
  return TokenPtr(new Token(TokenType::String, buffer)); 
}
```



`isNumber` & `readIntergerLiteral` 、

`isOperatorMember` & `readOperator` 

の実装は`readStringLiteral`とほぼ同じなので省略
要素が`isNumber`or `isOperatorMember`に当てはまるうちはずっと読んで行きます。



`isSymbol` & `readSymbol`

記号 (= `;,:()[]{}`のどれか)を見つけたら一文字だけ読み込みます。

```c++
auto isSymbol(char c) -> bool {
    return strchr(";,:()[]{}", c);
}
auto readSymbol(ReadingEnvironment& env) -> TokenPtr {
	auto s = std::string{env.next(0)};  
  
  return TokenPtr(new Token(TokenType::Symbol, s));
}
```



`readName` & `isNameElement`

`readName`はマルチバイト文字に対応するため少し特殊な仕様となっています。
マルチバイト文字 (= 🐱 日本語)  とは言ってもただのバイト列であることに変わりはないので、
`isNameElement`の判定が少し特殊なだけです。



```c++
/// 引数に渡された環境をもとに、NameのTokenを構成し返します。
auto readName(ReadingEnvironment& env) -> TokenPtr {
	auto buffer = new std::string();
  
  // isNameElementであるうちは読み込み
 	while (isNameElement(env.next(0))) {
		buffer += env.next(0);
		env.columun += 1;
	}
	env.columun -= 1;
  
	return TokenPtr(new Token(TokenType::Identifier, buffer));
}

/// 引数がNameの文字になれるか
auto isNameElement(char c) -> bool {
    return !(isWhiteSpace(c) or isOperatorMember(c) or isSymbol(c));
}
```

いわゆる `not` 判定ですw 意外とこれで十分に動いてくれます。



## まとめ

以上で`Lexer`は完成です。思ったより簡単だったのではないでしょうか？
以上のコードは[https://github.com/ObuchiYuki/WorkFlow/tree/master/WorkFlow/Lexer](https://github.com/ObuchiYuki/WorkFlow/tree/master/WorkFlow/Lexer)に上げてあります。ご覧ください。

次回は実際にコードの意味を解釈するパーサーを作成していきます。