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

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

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

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

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

言語仕様

今回作成した言語は
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 に上げてあるので良ければご覧ください。

Lexer 作成

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

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

なら、

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

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

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

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

実装

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

Tokenクラス

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

/// トークンの種類
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` 定義

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

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

    return true;
};

readNext

// 次の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

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

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

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

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

class ReadingEnvironment {
    /// 現在読んでいる行
        string line;

    /// 今読んでいる行の場所です。読み込みに応じて変化します。
    int columun;

    /// 先の文字を返す
    auto next(int gap) -> char {
        return line[columun + gap];
    }
};

`readLine`の続き

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

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

        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を行端まで移動します。

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

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

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

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

/// 引数に渡された環境をもとに、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とほぼ同じなので省略
要素がisNumberor isOperatorMemberに当てはまるうちはずっと読んで行きます。

isSymbol & readSymbol

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

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の判定が少し特殊なだけです。

/// 引数に渡された環境をもとに、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に上げてあります。ご覧ください。

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

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

目次

言語仕様

Lexer 作成

実装

Tokenクラス

Lexer

Lexer.hpp 定義

Lexer.cpp 実装

ReadingEnvironment

readLineの続き

まとめ

`Lexer.hpp` 定義

`Lexer.cpp` 実装

`ReadingEnvironment`

`readLine`の続き