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

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

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

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

今回は拙作のPEGライブラリ cpp-peglib を使って，次のような「変数付き計算機」を作ってみます。

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

開発環境

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

実装を始める前にプロジェクト用のディレクトリを作成して，そこに linenoise.hpp と peglib.h をダウンロードしておきます。

REPLの作成

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

#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）生成機能を有効にします。

#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 変数に構文木が渡されます。

typedef shared_ptr<peg::Ast> AST;

...

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

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

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

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

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

ビルドして実行してみます。（ソースコード / 差分）

> 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 ）が構文解析の開始ルールとなります。

ソースコードをビルドして実行してみます。（ソースコード / 差分）

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

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

足し算・引き算式の評価

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

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

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 ）

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

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 関数を使って構文木を評価し、その結果を表示します。

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

ビルドして実行してみます。（ソースコード / 差分）

> 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]);

ビルドして実行してみます。（ソースコード / 差分）

>  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 の二項演算のコードを修正して、乗算・除算のコードを加えます。除算の場合は、０で割ろうとする場合に例外を送出します。

  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 で囲みます。

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

        ...

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

ビルドして実行してみます。（ソースコード / 差分）

> 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 ')' _

ビルドして実行してみます。（ソースコード / 差分）

> (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 を使ってこれを抑制してみます。

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

          // ASTの表示

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

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

ビルドして実行してみます。（ソースコード / 差分）

> (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 ルールを新たに導入しました。

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

map<string, double> variables;

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

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

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

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

    return val;

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

  } 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 ルールを最適化の対象から外します。

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

ビルドして実行してみます。（ソースコード / 差分）

> 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

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

#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;
    }
  }
}