PEGとC++11で作る言語処理系

# PEGとC++11で作る言語処理系

言語処理系の作成と聞くと、難易度が高いと感じるかもしれません。しかしパーサージェネレータなどのツールを活用することによって，その敷居はぐっと低くなります。

この分野では、BNFからパーサーを生成するYaccが有名です。最近では [PEG（Parser Expression Grammar）](https://en.wikipedia.org/wiki/Parsing_expression_grammar)も知られるようになってきました。PEGの特徴の一つは，構文ルールだけでなく字句ルールも同時に定義できることです。現在、主要なプログラミング言語のほとんどにPEGパーサージェネレータが存在します。中には抽象構文木（AST）まで生成してくれるものもあります。

こうしたツールの助けを活用すると，言語処理系の作成はかなり容易になります。PEGで文法を定義し，ASTを実行する評価器を実装すれば，あとはPEGライブラリの助けを借りて言語処理系を完成させることができます。

今回は拙作のPEGライブラリ [cpp-peglib](https://github.com/yhirose/cpp-peglib) を使って，次のような「変数付き計算機」を作ってみます。

    > a = 0.5
    0.5
    > b = -2
    -2
    > (1 - a) * b
    -1

## 開発環境

開発言語はC++11です。（clang++やg++でコンパイルする際には「-std=c+11」オプションが必要になります。）

実装を始める前にプロジェクト用のディレクトリを作成して，そこに [linenoise.hpp](https://raw.githubusercontent.com/yhirose/cpp-linenoise/master/linenoise.hpp) と [peglib.h](https://raw.githubusercontent.com/yhirose/cpp-peglib/master/peglib.h) をダウンロードしておきます。

## REPLの作成

最初にテストに便利な対話型環境を作成します。REPLは「Read-eval-print loop」の略で、「入力、評価、表示」を繰り返すプログラムです。

```cpp
#include "linenoise.hpp"
using namespace std;

int main() {
  // REPL
  while (true) {
    // 行の入力
    string line;
    auto quit = linenoise::Readline("> ", line);

    // CTRL+C が押されたらループを抜ける
    if (quit) {
      break;
    }

    // 入力された文字列の表示
    cout << line << endl;

    // 入力された行を履歴に追加
    linenoise::AddHistory(line.c_str());
  }
}
```

上記のコードをビルドして実行すると、プロンプト `>` が表示されます。テキストを入力してリターンキーを押すと、その文字列がエコーされます。

    > hello world
    hello world
    > _

入力した文字列は履歴リストに保存され、カーソルキーの上下でアクセスできます。REPLを抜けるには、CTRL+Cを押します。

これから，このコードをベースにして言語処理系を少しずつ実装していきます。

## 数字のパース

数字をPEGで表現します。小数点やマイナス符号も扱えるようにします。

    NUMBER <- '-'? [0-9]+ ('.' [0-9]+)?

この文法を基にPEGパーサーを生成します。PEGライブラリのヘッダーファイル `peglib.h` をインクルードし，文法テキストを引数として `peg::parser` を生成します。そして抽象構文木（AST - Abstract Syntax Tree）生成機能を有効にします。

```cpp
#include "peglib.h"

...

const auto grammar = R"(
  NUMBER <- '-'? [0-9]+ ('.' [0-9]+)?
)";

...

  // パーサーの生成
  peg::parser parser(grammar);
  assert(parser);

  // 抽象構文木(AST)生成機能を使用する
  parser.enable_ast();
```

テキストを構文解析するには、`parse` メソッドを呼び出します。結果がbool値で返され、成功時には `ast` 変数に構文木が渡されます。

```cpp
typedef shared_ptr<peg::Ast> AST;

...

  // 入力行をパースし、ASTを生成
  AST ast;
  auto ret = parser.parse(line.c_str(), ast);
```

パース成功時には，構文木の内容を表示し，続いて入力文字列を履歴に登録します。

```cpp
  if (ret) {
    // ASTの表示
    cout << peg::ast_to_s(ast);

    // 入力された行を履歴に追加
    linenoise::AddHistory(line.c_str());
  } else {
    cout << "syntax error..." << endl;
  }
```

これで数字パーサーができました。

ビルドして実行してみます。（[ソースコード](https://github.com/yhirose/dds/blob/fd96e649e3904941f8fadb9b50c61973f9fe9d32/main.cpp) / [差分](https://github.com/yhirose/dds/commit/fd96e649e3904941f8fadb9b50c61973f9fe9d32)）

    > 1
    - NUMBER (1)
    > 0.123
    - NUMBER (0.123)
    > hello
    syntax error...
    > _

きちんと数字をパースできるようになりました。パース成功時には構文木の内容が表示されています。数字以外のテキストが入力された場合はエラーが表示されます。

## 足し算・引き算式のパース

続いて `+` と `-` 演算子をパースできるよう文法を拡張します。ルールを2行追加するだけです。

    ADITIVE          <- NUMBER (ADITIVE_OPERATOR NUMBER)*
    ADITIVE_OPERATOR <- [-+]
    NUMBER           <- '-'? [0-9]+ ('.' [0-9]+)?

重要な点として，cpp-peglibでは一番最初のルール（この場合は `ADITIVE` ）が構文解析の開始ルールとなります。

ソースコードをビルドして実行してみます。（[ソースコード](https://github.com/yhirose/dds/blob/2a32c1189524938e29a17a13f16e26429449a99a/main.cpp) / [差分](https://github.com/yhirose/dds/commit/2a32c1189524938e29a17a13f16e26429449a99a)）

    > 1+2-3.4
    + ADITIVE
      - NUMBER (1)
      - ADITIVE_OPERATOR (+)
      - NUMBER (2)
      - ADITIVE_OPERATOR (-)
      - NUMBER (3.4)
    > _

正しく動作していますね。

## 足し算・引き算式の評価

続いてパース時に取得した構文木を評価し，その結果を表示します。

その前にcpp-peglibの構文木について少し見てみます。構文木は `shared_ptr<AstBase>` ノードで構築されます。以下に `AstBase` クラスの主なプロパティを示します。

```cpp
string name // PEGルール名
string token // ークン文字列
vector<shared_ptr<AstBase>> nodes // 子ノードのリスト
```

例として次のような構文木の場合、

    + ADDITIVE
      - NUMBER (1)
      - ADDITIVE_OPERATOR (+)
      - NUMBER (2)
      - ADDITIVE_OPERATOR (-)
      - NUMBER (3.4)

節ノード `ADDITIVE` は，`nodes` プロパティに5つの子ノードを持ちます。

- `NUMBER` の時、`token` を `std::stod` 関数でdouble値に変換
- `ADDITIVE_OPERATOR` の時、何もしない。（`token` がそのまま親ノードに伝播される）
- `ADDITIVE` の時、`nodes` を計算する。（奇数ノードは `NUMBER` 、偶数ノードは `ADDITIVE_OPERATOR` ）

加算・減算の評価器の実装は，以下のようにしてみました。

```cpp
double eval(const AST& ast) {
  if (ast->name == "ADDITIVE") {
    // 二項演算子の計算
    auto result = eval(ast->nodes[0]);
    for (auto i = 1u; i < ast->nodes.size(); i += 2) {
      auto num = eval(ast->nodes[i + 1]);
      auto ope = ast->nodes[i]->token[0];
      switch (ope) {
        case '+': result += num; break;
        case '-': result -= num; break;
      }
    }
    return result;
  } else if (ast->name == "NUMBER") {
    // 数字文字列をdoubleに変換
    return stod(ast->token);
  }
  return 0;
}
```

`eval` 関数を使って構文木を評価し、その結果を表示します。

```cpp
    // ASTの評価
    auto result = eval(ast);
    cout << result << endl;
```

ビルドして実行してみます。（[ソースコード](https://github.com/yhirose/dds/blob/e1a57a1983bb4e74f86d2ae64d8514b0549b73c3/main.cpp) / [差分](https://github.com/yhirose/dds/commit/e1a57a1983bb4e74f86d2ae64d8514b0549b73c3)）

    > 1+2-3.4
    + ADDITIVE
      - NUMBER (1)
      - ADDITIVE_OPERATOR (+)
      - NUMBER (2)
      - ADDITIVE_OPERATOR (-)
      - NUMBER (3.4)
    -0.4
    > _

これで足し算・引き算ができるようになりました。

## 空白文字の読み飛ばし

現在の状態では、`1 + 2` の様に空白文字を入力してしまうとパースエラーとなります。これでは不便なので，空白を読み飛ばすように文法を拡張します。

    START             <- _ ADDITIVE
    ADDITIVE          <- NUMBER (ADDITIVE_OPERATOR NUMBER)*
    ADDITIVE_OPERATOR <- < [-+] > _
    NUMBER            <- < '-'? [0-9]+ ('.' [0-9]+)? > _
    ~_                <- [ \n\r\t]*

オリジナルのPEGだけでは表現力不足なので、cpp-peglibがサポートする拡張文法，`~`と`< … >`を使用します。

`~_` は空白文字ルールです。先頭の `~` は，構文木ノードの作成を抑制することを意味します。例えば `START` ノードの `nodes` リストには，`ADDITIVE` のノードのみ現れ，`_` のノードは生成されません。

`< … >` はトークン・オペレータ―です。`ADDITIVE_PERATOR` や `NUMBER` の例では，トークン・オペレーターで囲われた文字列のみがノードの `token` にセットされ，外側の文字列はみな無視されます。

文法の変更に合わせて評価器も修正します。`~_` ルールは構文木ノードを生成しないので、特に何もする必要はありません。`START` ルールの様に評価されずに残り、子ノードを一つだけ持つ場合、子ノードの評価値をそのまま親へ引き渡すようにします。

    -   return 0;
    +   assert(ast->nodes.size() == 1);
    +   return eval(ast->nodes[0]);

ビルドして実行してみます。（[ソースコード](https://github.com/yhirose/dds/blob/e496ead16a845eca6751966b00a20bbf7f33a4a4/main.cpp) / [差分](https://github.com/yhirose/dds/commit/e496ead16a845eca6751966b00a20bbf7f33a4a4)）

    >  1 + 2
    + START
      + ADDITIVE
        - NUMBER (1)
        - ADDITIVE_OPERATOR (+)
        - NUMBER (2)
    3
    > _

パーサーは空白文字を無視するようになりました。

## 掛け算・割り算

`*` と `/` 演算子を扱えるように文法を拡張します。加算・減算よりも優先順位が高くなるようにルールを定義します。また可読性を考慮して、コメントを入れ、一部のルール名を変更します。

    # ルール
    START              <- _ ADDITIVE
    ADDITIVE           <- MULTITIVE (ADDITIVE_OPERATOR MULTITIVE)*
    MULTITIVE          <- PRIMARY (MULTITIVE_OPERATOR PRIMARY)*
    PRIMARY            <- NUMBER
    
    # トークン
    ADDITIVE_OPERATOR  <- < [-+] > _
    MULTITIVE_OPERATOR <- < [/*] > _
    NUMBER             <- < '-'? [0-9]+ ('.' [0-9]+)? > _
    
    # 空白文字
    ~_                 <- [ \n\r\t]*

`eval` の二項演算のコードを修正して、乗算・除算のコードを加えます。除算の場合は、０で割ろうとする場合に例外を送出します。

```cpp
  if (ast->name == "ADDITIVE" || ast->name == "MULTITIVE") {
    // 二項演算子の計算
    ...
      switch (ope) {
        case '+': result += num; break;
        case '-': result -= num; break;
        case '*': result *= num; break;
        case '/':
          // ゼロ除算チェック
          if (num == 0) {
            throw std::runtime_error("divide by 0 error");
          }
          result /= num;
          break;
      }
```

`eval` 関数の呼び出しコードを `try-catch` で囲みます。

```cpp
      // ASTの評価
      try {
        auto result = eval(ast);

        ...

      } catch (const std::runtime_error& e) {
        cout << e.what() << endl;
      }
```

ビルドして実行してみます。（[ソースコード](https://github.com/yhirose/dds/blob/6349d74774534d2100ae8064db31e5c818cf11ea/main.cpp) / [差分](https://github.com/yhirose/dds/commit/6349d74774534d2100ae8064db31e5c818cf11ea)）

    > 1 + 2 * 3
    + START
      + ADDITIVE
        + MULTITIVE
          + PRIMARY
            - NUMBER (1)
        - ADDITIVE_OPERATOR (+)
        + MULTITIVE
          + PRIMARY
            - NUMBER (2)
          - MULTITIVE_OPERATOR (*)
          + PRIMARY
            - NUMBER (3)
    7
    > _

乗算が先に処理されていますね。

## 括弧

括弧に対応するため、`FACTOR` を変更します。評価器は変更する必要はありません。

    PRIMARY <- NUMBER / '(' _ ADDITIVE ')' _

ビルドして実行してみます。（[ソースコード](https://github.com/yhirose/dds/blob/af12eb4db30ddb95a42a4df6e5148f2518bc5181/main.cpp) / [差分](https://github.com/yhirose/dds/commit/af12eb4db30ddb95a42a4df6e5148f2518bc5181)）

    > (1 + 2) * 3
    + START
      + ADDITIVE
        + MULTITIVE
          + PRIMARY
            + ADDITIVE
              + MULTITIVE
                + PRIMARY
                  - NUMBER (1)
              - ADDITIVE_OPERATOR (+)
              + MULTITIVE
                + PRIMARY
                  - NUMBER (2)
          - MULTITIVE_OPERATOR (*)
          + PRIMARY
            - NUMBER (3)
    9
    > _

カッコ内の式が先に処理されています。

## 冗長なASTノードの除去

前節の実行結果を見ると、子を一つしか持たない冗長なノードが多数見受けられます。`peg::optimize_ast` を使ってこれを抑制してみます。

```cpp
        if (ret) {
+         // 冗長なASTノードを除去
+         ast = peg::optimize_ast(ast);

          // ASTの表示
```

`eval` 関数の最後の `return eval(ast->nodes[0]);` は、もう必要なくなります。

```cpp
-  assert(ast->nodes.size() == 1);
-  return eval(ast->nodes[0]);
+  // NOTREACHED
+  assert(false);
+  return 0;
```

ビルドして実行してみます。（[ソースコード](https://github.com/yhirose/dds/blob/801cf9add8e1eb207473453b53f2cc0b9b81053a/main.cpp) / [差分](https://github.com/yhirose/dds/commit/801cf9add8e1eb207473453b53f2cc0b9b81053a)）

    > (1 + 2) * 3
    + START[MULTITIVE]
      + PRIMARY[ADDITIVE]
        - MULTITIVE[NUMBER] (1)
        - ADDITIVE_OPERATOR (+)
        - MULTITIVE[NUMBER] (2)
      - MULTITIVE_OPERATOR (*)
      - PRIMARY[NUMBER] (3)
    9
    > _

冗長なノードが抑制され、構文木が随分すっきりしました。

## 変数

変数への代入と変数の参照を行えるように文法を修正します。

    # ルール
    START              <- _ EXPRESSION
    EXPRESSION         <- ASSIGNMENT / ADDITIVE
    ASSIGNMENT         <- IDENTIFIER '=' _ EXPRESSION
    ADDITIVE           <- MULTITIVE (ADDITIVE_OPERATOR MULTITIVE)*
    MULTITIVE          <- PRIMARY (MULTITIVE_OPERATOR PRIMARY)*
    PRIMARY            <- NUMBER / VARIABLE / '(' _ EXPRESSION ')' _
    VARIABLE           <- IDENTIFIER
    
    # トークン
    ADDITIVE_OPERATOR  <- < [-+] > _
    MULTITIVE_OPERATOR <- < [/*] > _
    NUMBER             <- < '-'? [0-9]+ ('.' [0-9]+)? > _
    IDENTIFIER         <- < [a-zA-Z][a-zA-Z0-9]* > _
    
    # 空白文字
    ~_                 <- [ \n\r\t]*

`EXPRESSION` 、`ASSIGNMENT` 、`VARIABLE` 、`IDENTIFIER` ルールを新たに導入しました。

変数を格納するためのグローバル変数を定義します。

```cpp
map<string, double> variables;
```

`eval` 関数に、`ASSIGNMENT` ルールのための処理を追加します。最初の子ノードから変数名を取得し、続く子ノードの評価値を変数表に設定します。この値は、`ASSIGNMENT` の評価値ともなります。

```cpp
  } else if (ast->name == "ASSIGNMENT") {
    // 変数名の取得
    auto sym = ast->nodes[0]->token;

    // 値の取得
    auto val = eval(ast->nodes[1]);

    // 変数表に設定
    variables[sym] = val;

    return val;
```

`eval` 関数に、`VARIABLE` のための処理を追加します。子ノードのトークンから変数名を取得し、変数表に値があるかをチェックします。値があればそれが評価値となり、なければ例外を送出します。

```cpp
  } else if (ast->name == "VARIABLE") {
    // 変数名の取得
    auto sym = ast->nodes[0]->token;

    // 変数が存在するかチェック
    auto it = variables.find(sym);
    if (it == variables.end()) {
      throw std::runtime_error("undefined variable: '" + sym + "'");
    }
    return it->second;
```

`peg::optimize_ast` を実行すると、子ノードを一つしか持たない `VARIABLE` ノードが除去されてしまいます。それで `VARIABLE` ルールを最適化の対象から外します。

```cpp
      if (ret) {
+       // 冗長なASTノードを除去 ('VARIABLE'ルールを除く)
~       ast = peg::optimize_ast(ast, { "VARIABLE" });
```

ビルドして実行してみます。（[ソースコード](https://github.com/yhirose/dds/blob/da60880434e80d5844955f243d3d43e9cb8c6c56/main.cpp) / [差分](https://github.com/yhirose/dds/commit/da60880434e80d5844955f243d3d43e9cb8c6c56)）

    > a = 1
    + START[ASSIGNMENT]
      - IDENTIFIER (a)
      - EXPRESSION[NUMBER] (1)
    1
    > b = 2
    + START[ASSIGNMENT]
      - IDENTIFIER (b)
      - EXPRESSION[NUMBER] (2)
    2
    > c = a + b
    + START[ASSIGNMENT]
      - IDENTIFIER (c)
      + EXPRESSION[ADDITIVE]
        + MULTITIVE[VARIABLE]
          - IDENTIFIER (a)
        - ADDITIVE_OPERATOR (+)
        + MULTITIVE[VARIABLE]
          - IDENTIFIER (b)
    3
    > _ 

上手く動いています。定義されていない変数を使おうとすると、

    > d
    + START[VARIABLE]
      - IDENTIFIER (d)
    undefined variable: 'd'
    > _ 

予想通り未定義エラーとなります。

## まとめ

無事「変数付き計算機」を完成することができました。PEGライブラリが「字句・構文解析」と「ASTの生成」を行なってくれたので，自分で実装する必要があったのは次の3つでした。

- PEG文法定義
- AST評価器
- REPL

最終的なコードは以下の通りです。

```cpp
#include "linenoise.hpp"
#include "peglib.h"
using namespace std;

typedef shared_ptr<peg::Ast> AST;

// 文法
const auto grammar = R"(
  # ルール
  START              <- _ EXPRESSION
  EXPRESSION         <- ASSIGNMENT / ADDITIVE
  ASSIGNMENT         <- IDENTIFIER '=' _ EXPRESSION
  ADDITIVE           <- MULTITIVE (ADDITIVE_OPERATOR MULTITIVE)*
  MULTITIVE          <- PRIMARY (MULTITIVE_OPERATOR PRIMARY)*
  PRIMARY            <- NUMBER / VARIABLE / '(' _ EXPRESSION ')' _
  VARIABLE           <- IDENTIFIER
  # トークン
  ADDITIVE_OPERATOR  <- < [-+] > _
  MULTITIVE_OPERATOR <- < [/*] > _
  NUMBER             <- < '-'? [0-9]+ ('.' [0-9]+)? > _
  IDENTIFIER         <- < [a-zA-Z][a-zA-Z0-9]* > _
  # 空白文字
  ~_                 <- [ \n\r\t]*
)";

// 変数表
map<string, double> variables;

// 評価器
double eval(const AST& ast) {
  if (ast->name == "ADDITIVE" ||
      ast->name == "MULTITIVE") {
    // 二項演算子の計算
    auto result = eval(ast->nodes[0]);
    for (auto i = 1u; i < ast->nodes.size(); i += 2) {
      auto num = eval(ast->nodes[i + 1]);
      auto ope = ast->nodes[i]->token[0];
      switch (ope) {
        case '+': result += num; break;
        case '-': result -= num; break;
        case '*': result *= num; break;
        case '/':
          // ゼロ除算チェック
          if (num == 0) {
            throw std::runtime_error("divide by 0 error");
          }
          result /= num;
          break;
      }
    }
    return result;
  } else if (ast->name == "ASSIGNMENT") {
    // 変数名の取得
    auto sym = ast->nodes[0]->token;

    // 値の取得
    auto val = eval(ast->nodes[1]);

    // 変数表に設定
    variables[sym] = val;

    return val;
  } else if (ast->name == "VARIABLE") {
    // 変数名の取得
    auto sym = ast->nodes[0]->token;

    // 変数が存在するかチェック
    auto it = variables.find(sym);
    if (it == variables.end()) {
      throw std::runtime_error("undefined variable: '" + sym + "'");
    }
    return it->second;
  } else if (ast->name == "NUMBER") {
    // 数字文字列をdoubleに変換
    return stod(ast->token);
  }

  // NOTREACHED
  assert(false);
  return 0;
}

int main() {
  // パーサーの生成
  peg::parser parser(grammar);
  assert(parser);

  // 抽象構文木(AST)生成機能を使用する
  parser.enable_ast();

  // REPL
  while (true) {
    // 行の入力
    string line;
    auto quit = linenoise::Readline("> ", line);

    // CTRL+C が押されたらループを抜ける
    if (quit) {
      break;
    }

    // 入力行をパースし、ASTを生成
    AST ast;
    auto ret = parser.parse(line.c_str(), ast);

    if (ret) {
      // 冗長なASTノードを除去 ('VARIABLE'ルールを除く)
      ast = peg::optimize_ast(ast, { "VARIABLE" });

      // ASTの表示
      cout << peg::ast_to_s(ast);

      // ASTの評価
      try {
        auto result = eval(ast);
        cout << result << endl;

        // 入力された行を履歴に追加
        linenoise::AddHistory(line.c_str());
      } catch (const std::runtime_error& e) {
        cout << e.what() << endl;
      }
    } else {
      cout << "syntax error..." << endl;
    }
  }
}
```