**Pratt パーサーを直感的に把握する**

2026‑03‑26

既にご存知のように、

a + b * c + d

は

a + (b * c) + d

と計算されます。しかし、その規則を機械が正確に理解できるように、どのように表現すればよいのでしょうか？

コンパイラで最も一般的に使われている解決策は 抽象構文木（AST） です。
AST では演算子がそのオペランドより上に位置し、評価は下から上へと行われます：子ノードを先に計算し、その後で演算子を適用します。

     +
    / \
   +   d
  / \
 a   *
    / \
   b   c

この木構造は

(a + (b * c)) + d

の所望の評価順序を、プログラムで扱いやすい形式にエンコードしています。

パース（字句解析）

パースは平坦なテキストからこの構造を導き出します。
計算機科学の研究対象として数十年もの間注目されており、多くの場合過剰に複雑化されています。

1. 混在する優先順位

パースの難点は「混在する優先順位」― 優先順位が方向を変えるケース ― にあります。
利用者が書くプログラムが増加（左から右へ優先度が上がる）か減少（左から右へ優先度が下がる）のいずれかであると仮定した場合、木構造はどうなるでしょう？

減少優先順位: もっとも左側の演算子を最初に評価します。
つまり掛け算より足し算が高く、足し算より比較が高い等です。
最初の演算子は木の一番深い位置に配置され、最後の演算子は浅い位置になります。
結果として得られる木は 左寄り（left‑leaning）です。

       <
      / \
     +   d
    / \
   *   c
  / \
 a   b

増加優先順位: 今回は左側の演算子が浅く、右側の演算子が深くなります。
各演算子は右側の結果に依存するためです。
木は 右寄り（right‑leaning）になります。

2. 等しい優先順位

等しい優先順位をどうエンコードするのが妥当でしょうか？
算術では左から右への評価（左結合）が慣例です。一方、C の代入演算子は右結合です。

すべての演算子が左結合であると仮定すると、左寄りの木で表現します。
演算子列に対し、(x_i) を i 番目 の演算子の優先順位とすると：

減少 : 弱い減少 – x_i ≥ x_{i+1}  （等しい場合も含む）
増加   : 強い増加   – x_i < x_{i+1}

したがって、同じ優先順位の演算子二つは「減少」ケースとまったく同じようにエンコードされます。

3. 方向転換が一度だけある場合

増加 → 減少 の方向転換（逆も同様）を持つ式を考えます。
例として

I = (a > b + c * d)

を取り上げ、以下の木で表します。

この木は右寄りです。
今度、

と同じかそれ以下の優先順位を持つ新しい演算子で

を拡張するとします。
増加性が失われるので、単に右寄りの木を続けても正しくエンコードできません。

そこで必要なのは 左寄り のサブツリーです。どこに配置すべきか？
新演算子の各優先順位レベルを可視化するとパターンが見えてきます：

[I] * e:
       >
      / \
     a   +
        / \
       b   *
          / \
         *   e
        / \
       c   d

[I] + e:
       >
      / \
     a   +
        / \
       +   e
      / \
     b   *
        / \
       c   d

[I] == e:
       ==
      /  \
     >    e
    / \
   a   +
      / \
     b   *
        / \
       c   d

左寄りの木は 等しいかそれ以下の優先順位を持つ最初の演算子 で始まります。
その低い優先順位の演算子は、少なくとも現在の演算子より後に評価される必要がありますが、さらに前にある複数の演算子も同様です。
それらは右寄りの木の「背骨（spine）」上にあります。

結論: 方向転換演算子に出会ったときには、背骨を逆さまに歩いて「最初に評価されるべきすべての演算子」を集めます。
この集まり―右寄りの部分木―が新しい演算子の左子ノードとなります。そしてその左側で独自の左寄りサブツリーが始まります。

これが「Pratt パース」の歩き戻し（walk‑back）手順です。
すべての式はこうした転換の列に過ぎないので、これだけで十分です。

パース – 擬似コード

1. 右寄りケース

右寄り木は再帰を使い、下から上へ構築できます：

def parse():
    left = leaf()

    if peek() is not None:
        op = advance()
        right = parse()
        return Node(op, left, right)

    return left

parse()

はまず

leaf()

を呼び出してリテラル（例：

）を処理し、トークンストリームから消費します。その後

peek()

で次のトークン（演算子）があるか確認。
有効なプログラムなら演算子が来るので

advance()

でそれを取り込み、右辺の再帰呼び出しへ進みます。

以下は先ほどの

[I]

を処理する過程です：

-- 下に向かう（advance）

(1) parse(0)
    a > b + c * d

(2) parse('>')   →  a > b [+] c * d

(3) parse('+')   →  a > b + c [*] d

(4) parse('*')   →  a > b + c * d [None]

-- 上に向かう（構築）

(4)  d
(3)  [*]
     / \
    c   d
(2)  [+]
     / \
    b   *
       / \
      c   d
(1)  [>]
     / \
    a   +
       / \
      b   *
         / \
        c   d

減少優先順位を扱うには、再帰呼び出しに現在の優先順位を渡します：

def parse(prev_prec=0):
    left = leaf()

    if peek() is not None and prec(peek()) > prev_prec:
        op = advance()
        right = parse(prec(op))
        return Node(op, left, right)

    return left

エンドオブファイルを最低優先順位のトークンとみなせば、

peek()

が条件を自然に失敗させて

None

チェックを省略できます：

def parse(prev_prec=0):
    left = leaf()

    if prec(peek()) > prev_prec:
        op = advance()
        right = parse(prec(op))
        return Node(op, left, right)

    return left

2. 左寄りケース

parse()

が再帰するとき、スタックフレームに左子と最小優先順位をプッシュします。
この呼び出しスタックは常に 増加する 優先順位で構成されます。

そのため、戻る際には 減少順 で各レベルを訪れます。

peek()

がバインドできる最初のレベルが正しいレベルです：それより上はすべて低い優先順位（

parse()

がまだ返ってこない）で、深く進むことはありません。

したがって

if

を

while

に置き換えます：

def parse(prev_prec=0):
    left = leaf()

    while prec(peek()) > prev_prec:
        op = advance()
        right = parse(prec(op))
        left = Node(op, left, right)

    return left

これが Pratt パーサ の完成形です。

while

ループは先ほど説明した歩き戻し手順に相当します：転換演算子が現れると、呼び出しスタックを上へ戻り適切なレベルを見つけてからループで消費し、左寄りサブツリーを構築します。

例:

[I] * e

（
I = a > b + c * d
）のトレース

-- 下に向かう
(1) a [>] b  +  c  *  d  *  e
(2) a  >  b [+] c  *  d  *  e
(3) a  >  b  +  c [*] d  *  e
(4) a  >  b  +  c  *  d [*] e  FAIL

-- 上に向かう（構築）

(4)  d
(3) iteration 1:
     [*]
     / \
    c   d
iteration 2:
     [*]
     / \
    *   e
   / \
  c   d
(2) [+]
     / \
    b   *
       / \
      *   e
     / \
    c   d
(1) [>]
     / \
    a   +
       / \
      b   *
         / \
        *   e
       / \
      c   d

左寄りサブツリー

(c * d) * e

は完全にフレーム 3 の

while

内で構築されます。

右結合

実際にはすべての演算子は 左バインディングパワー（LBP） と 右バインディングパワー（RBP） を持ちます。
これまで扱ってきた演算子は LBP と RBP が同じでした。

LBP は「左側の式をどれだけ強く引き付けるか」を示し、

peek()

の

while

条件で判定します。
RBP は「右側の式をどれだけ強く引き付けるか」を示し、再帰呼び出しに渡す

prev_prec

に相当します。

左結合演算子では LBP と RBP が等しいため、2 つ目の

は

parse()

の再帰呼び出しを起こさず、同じレベルでループが続きます。
右結合演算子（例：代入）では逆にしたいので、RBP を LBP より低く設定します。これにより連続する

が再帰呼び出しに渡され、

a = (b = c)

のように構築されます。

def parse(prev_prec=0):
    left = leaf()

    while lbp(peek()) > prev_prec:
        op = advance()
        right = parse(rbp(op))
        left = Node(op, left, right)

    return left

左結合なら

rbp = lbp

、右結合なら

rbp = lbp - 1

と設定します。

まとめ

Pratt パースは巧妙に見えますが、本質は「木構造は優先順位によって左寄りか右寄りになる」という単純な幾何学的直感に基づいています。
優先順位が下がるときは背骨を逆さまに歩き、正しい位置で新しい演算子を配置します。

この視点からアルゴリズムは直感的になり、実装もコンパクトになります。

Pratt パーサーを直感的に把握する

Japanese Translation:

Text to translate