再帰下降法にさよなら！Prattパーサーで式解析を簡単かつ効果的に！

2025-02-01
#compiler

今までコンパイラでの式のパーサーに再帰下降法を使ってたが、Crafting Interpretersという本（以降CI本）でPrattパーサーという手法があることを知った。 本では加えて直接バイトコードを生成しているため「文法に制限がある」みたいなことが書かれていたのを混同して不安があったが、 試しにC言語の式のパースに使ってみて問題なく使えることがわかったのでもう今後は再帰下降法を使うのはやめるようPrattパーサーを布教したい。

式のパースの難しさ

式をパースする際になにが問題かというと、演算子に優先度があって例えば1 + 2 * 3みたいな式の場合にトークンを「1, +, 2」と読んだ時点では判断できず、続く演算子によって結合を変更する必要がある。

また結合に左右があり、例えばa - b - cは(a - b) - cと左結合なのに対して、a = b = cはa = (b = c)と右結合にする必要がある。

Bisonなどのパーサージェネレータを使わないで手書きする場合再帰下降法という方法が一般的だと思う。 再帰下降法は演算子の優先度ごとに実装言語上で再帰関数呼出をすることで処理する。 処理的には問題ないが優先度の数の分だけ再帰呼出が必要なのでちょっと無駄が発生する。

Prattパーサー

CI本から入った口なのでPrattパーサーが正確になにを指すか詳しくはわかってないが、Vaughan Pratt氏の論文”Top Down Operator Precedence“＝演算子の優先度に基づいてトップダウンに式をパースする手法のことを言う。

中置演算子ごとの優先度を数値として持っていて、現在処理中の優先度以上の演算子が登場した場合にその演算子に応じた処理を行う。 呼び出された処理の関数側ではその高い優先度で式のパースを再帰で呼び出すことで、優先度に従って結合を処理できる。

中置演算子以外にも前置演算子（単項演算子）も扱える。

CI本のPrattパーサーの仕組み

CI本で紹介されるコードのexpression関数が式のパースの起点となる関数で、 そこから呼び出されるparsePrecedence関数がメインの処理をしている（コメントや筋に関係ないコードは省く）：

static void expression() {
  parsePrecedence(PREC_ASSIGNMENT);
}

static void parsePrecedence(Precedence precedence) {
  advance();
  ParseFn prefixRule = getRule(parser.previous.type)->prefix;
  if (prefixRule == NULL) {
    error("Expect expression.");
    return;
  }

  prefixRule();

  while (precedence <= getRule(parser.current.type)->precedence) {
    advance();
    ParseFn infixRule = getRule(parser.previous.type)->infix;
    infixRule();
  }
}

advanceでトークンを進めた上でparser.previousのトークンのルール(ParseRule)を取得することで、関数呼出時点でのトークンに対応するprefixを呼び出す。 その後は与えられたprecedence以上の優先度のトークンが続く間、infixを呼び出す。

例えば+などの単純な左結合の二項演算子のinfixとして呼び出されるbinary関数：

static void binary() {
  TokenType operatorType = parser.previous.type;
  ParseRule* rule = getRule(operatorType);
  parsePrecedence((Precedence)(rule->precedence + 1));

  switch (operatorType) {
    case TOKEN_PLUS:          emitByte(OP_ADD); break;
    case TOKEN_STAR:          emitByte(OP_MULTIPLY); break;
    ...
  }
}

この関数の中でparsePrecedence関数を再帰的に呼び出している。 rule->precedence + 1を渡しているので、+よりも高い優先度だけが処理されるようになる。

例

例えば1 + 2 * 3の場合、「1, +」でbinaryから+の優先度+1でparsePrecedenceが呼び出され、 「2, *」の*の優先度はそれ以上なので再度binaryが呼び出されて、結果的に「1 + (2 * 3)」になる。

1 + 2 + 3の場合は、「2, +」の+の優先度はそれ未満なのでwhileループから抜けて2だけが返されて、呼び出し元のwhileループ側で処理されて結果的に「(1 + 2) + 3」になる。

prefix演算子

getRuleで得られるルールのprefixが指す関数は名前通り前置演算子を扱うが、それ以外にも数値などのリテラルや、括弧も処理する。

単項演算子-ではunary関数：

static void unary() {
  TokenType operatorType = parser.previous.type;

  parsePrecedence(PREC_UNARY);

  switch (operatorType) {
    case TOKEN_MINUS: emitByte(OP_NEGATE); break;
    ...
  }
}

で、同様にparsePrecedenceを呼び出すことで続く式を処理する。

1などの数値リテラルはnumber関数：

static void number() {
  double value = strtod(parser.previous.start, NULL);
  emitConstant(NUMBER_VAL(value));
}

となっていて、parsePrecedenceは呼び出さずにトークン自体から値を取り出すだけ。 これによってprefixが最終的にリテラルに前置演算子が適用されたものになる。

括弧のgrouping関数：

static void grouping() {
  expression();
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after expression.");
}

で、最低の優先度で再帰呼び出しすることですべての演算子の式を処理した上で、後に)が続くものとなる。

関数呼出

関数呼出は見た目的には中置演算子とは全然違うけど、処理的にはinfixで扱っている。 実のところinfixといっても中置演算子だけに限らず、prefixに続いて許される演算子であればよくて、関数呼出以外にも後置演算子でも同様に扱える。

call関数：

static void call() {
  uint8_t argCount = argumentList();
  emitBytes(OP_CALL, argCount);
}

static uint8_t argumentList() {
  uint8_t argCount = 0;
  if (!check(TOKEN_RIGHT_PAREN)) {
    do {
      expression();
      argCount++;
    } while (match(TOKEN_COMMA));
  }
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after arguments.");
  return argCount;
}

argumentList関数でカンマ区切りの式を受け付けて、)で閉じられる。

C言語の式パースに適用する

CI本で実装されたスクリプト言語と比べても、C言語の式ではいろいろ懸念点がある：

  • 前置でも中置でも使える演算子がある：+, -, *, &
  • 同様に、前置でも後置でも使える演算子がある：++, --
  • 代入式が右結合、また代入演算子もある
  • 三項演算子?:
  • カンマ演算子
  • 括弧()が式を括る・関数呼出に加えて、キャスト演算子、複合リテラル、gcc拡張のステートメント式にも使われる

これら全てをPrattパーサーで扱うことはできるのか？ 結論的には、式の前に扱うトークンはprefixで、後で扱うトークンはinfixと優先度を設定すれば問題なくすべて扱える。

  • (のprefixで、
    • {が続く場合はステートメント式
    • 型名が続く場合には)に続いて{なら複合リテラル、でなければキャスト演算子
    • それ以外はグルーピング
  • 後置演算子は最高の優先度を割り振る
  • 代入の右結合はparsePrecedenceの呼び出しに優先度を+1せずに呼び出すことで実現できる
  • 配列アクセス[]も関数呼出同様に扱える
  • カンマ演算子が一番低い優先度で、関数の引数はカンマで区切るのでそれより高い優先度で式のパースをする
  • 三項演算子は?の後をカンマ演算子も受け付け、:の後に右結合として再帰

行数の変化

再帰下降法に比べてPrattパーサーでは優先度の処理とループが共通化され、 また二項演算や単項演算での任意の処理を共通化できるので、たいていの場合コード量は減らせると思う。

自分のC言語の式パーサーでは、再帰下降法で917行だったものが、Prattパーサーに書き換えたところ811行に削減された（-11.6%）。

実行速度の変化

再帰下降法では不要に関数呼出がネストされるのが、Prattパーサーではトークンの種類によってネストが削減されるので、実行速度も改善されることが期待される。

ただいくつかのソースのコンパイル時間を比べたところ大差なかった。 これはコンパイル時間のうち式のパースがそんなに大きなパートを占めないからだと思う。

あとがき

Prattパーサーの動作の仕組みはちょっと難しいけど、再帰下降法に比べてそれほど難解なわけではなく、 それでいて効率的なので利用しない手はないと思う。

変更したソース：xcc/src/cc/frontend/parser_expr.c 　（変更コミット）

リンク

過去記事

関連記事

新着記事