再帰降下と LL 解析

再帰降下は、関数間の呼び出しによって文法構造を表現します。式関数は部分式の関数を呼び出し、文関数は式関数を呼び出します。LL 解析は、有限の先読みだけで生成規則を選択できるタイミングを説明します。Pratt パーサは、式演算子の決定を結合強度（バインディングパワー）に基づいて整理します。

手書きの再帰降下が LL(1) であるとは限りません。実装では、複数トークンの先読み、バックトラック、または意味解析判断を使用することもできます。各メカニズムを追加するたびに、複雑さ、エラー回復、副作用を再検討する必要があります。

文法から関数へ

以下に、EBNF の繰り返し記法を用いて四則演算を記述します。

expr   = term, { ("+" | "-"), term } ;
term   = factor, { ("*" | "/"), factor } ;
factor = NUMBER | "(", expr, ")" ;

expr はまず term を解析し、その後 + または - と次の項をループで消費します。term は同様に * と / を処理します。factor は数値と括弧を処理します。より高い優先度の演算子はより深い呼び出し層に位置するため、2 + 3 * 4 では、乗法が加法の右子ツリーとして扱われます。

解析関数は、何を消費し、どのトークンの前で停止し、成功と失敗でそれぞれ何を返すかという規約を定めるべきです。完全な式の入口では、EOF（ファイル終端）をチェックする必要があります。そうしないと、1 2 が誤って成功した 1 として解析されてしまう可能性があります。

左再帰の除去と左結合は同一ではない

素朴な再帰降下で E → E - T | T を直接実装すると、入力を消費する前に E を再度呼び出すことになり、無限再帰を引き起こします。直接左再帰は E → T E'、E' → - T E' | ε に書き換えることができます。間接左再帰は、非終端記号間の依存関係に応じて別途処理する必要があります。一部の拡張パーサアルゴリズムは、左再帰を专门的にサポートすることもあります。

書き換えた後の右再帰の末尾は、減算が右結合であることを意味するものではありません。AST（構文木）を構築する際、現在の結果を新しいノードの左子として使用し、順に折りたたみます。8 を読み終えると Number になり、- 3 を読み終えると Sub(8,3) になり、さらに - 2 を読み終えると Sub(Sub(8,3),2) になります。

FIRST、FOLLOW、および予測集合

FIRST(α) は、α が導出可能な文字列の先頭終端記号の集合です。α が空文字列を導出できる場合、ε も含まれます。FOLLOW(A) は、ある文脈で A の直後に現れることができる終端記号の集合です。開始記号の FOLLOW には、入力終端記号 $ が含まれます。

FIRST を計算する際は、生成規則の左から右へ伝播させます。前の記号が空の場合にのみ、次の記号を確認します。A → α B β に対して、FIRST(β) − {ε} を FOLLOW(B) に追加します。β が空の場合、FOLLOW(A) も追加します。循環する文法では、集合が変化しなくなるまで反復処理を行います。

簡略化された文法を考えます。

E  → T E'
E' → + T E' | ε
T  → id

生成規則 A → α に対する予測集合は FIRST(α) − {ε} です。α が空の場合、FOLLOW(A) も併合します。⁠同じ非終端記号の候補間の予測集合が互いに素でなければ、衝突のない LL(1) の選択を確立できません。 FIRST 同士の不交性のみをチェックすると、空の生成規則に関する衝突を見逃す可能性があります。

例では、E' は + が見えると継続を選択し、$ が見えると ε を選択し、id が見えるとエラーを報告すべきです。無条件に ε を選択してはいけません。予測表はこれらの決定をテーブル化するだけで、再帰降下はそれらを関数の分岐として記述します。

空の生成規則がなぜ通常候補と同じトークンを争うのか

S → A a、A → a | ε を再考します。小文字の a は終端記号です。A の2つの右辺の FIRST はそれぞれ {a} と {ε} で、一見すると不交に見えます。しかし、FOLLOW(A) は a を含むため、空の生成規則の予測集合も {a} になります。パーサが A で a を見たとき、このトークンを消費すべきか、S の末尾に残すべきかを、このトークンだけでは判断できません。

長さが 1 の入力 a では A→ε を選択し、長さが 2 の入力 aa では A→a を選択すべきです。この小さな文法は曖昧ではありませんが、その文法に対する LL(1) の予測条件を満たしていません。言語に対応する文法を書き換えるか、より多くの先読みを使用する必要があります。予測表の衝突を直接言語の曖昧性と同一視してはいけません。

def predict(first, nullable, follow):
    # first は ε を除外済み；nullable は空になり得るかどうかを個別に記録。
    return set(first) | (set(follow) if nullable else set())


def table(candidates):
    cells = {}
    for rule, lookaheads in candidates:
        for token in lookaheads:
            if token in cells:
                raise ValueError(f"conflict on {token}: {cells[token]} / {rule}")
            cells[token] = rule
    return cells


assert table([
    ("E' -> + T E'", predict({"+"}, False, {"$"})),
    ("E' -> empty", predict(set(), True, {"$"})),
]) == {"+": "E' -> + T E'", "$": "E' -> empty"}
try:
    table([
        ("A -> a", predict({"a"}, False, {"a"})),
        ("A -> empty", predict(set(), True, {"a"})),
    ])
except ValueError as error:
    assert "conflict on a" in str(error)
else:
    raise AssertionError("FIRST/FOLLOW conflict missed")

このコードは1つの非終端記号の予測表のみを構築し、完全な文法の FIRST/FOLLOW の計算は行いません。衝突する2つの生成規則の由来を保持し、後から候補が追加された際に既存の項目を静かに上書きしないようにします。実際のパーサジェネレータは、空文字列を生成する生成規則や FOLLOW 伝播に関連するパスを指摘し、文法の問題を特定するのに役立てるべきです。

ε は文字を消費しないのに、なぜ先読みを争うのか

まず候補 a が何を消費するか、次に空の候補が外側に何を残す必要があるかを見ます。S→Aa の場合、2つの候補とも先読み a に直面する可能性があります。短い文字列 a は外側に残す必要があり、長い文字列 aa はまず1つを消費する必要があります。S の末尾を b に変更すると、2つの予測集合は分離されます。ここで変更されているのは文法の予測条件であり、ε に文字を消費する動作を密かに追加しているわけではありません。

$$\mathrm{PRED}(A\to \alpha )=(\mathrm{FIRST}(\alpha )\setminus \{\epsilon \})\cup \{\begin{array}{ll}\mathrm{FOLLOW}(A)& \epsilon \in \mathrm{FIRST}(\alpha )\\ \varnothing & \text{otherwise}\end{array}$$

共通接頭辞、曖昧性、およびバックトラック

左因子抽出は A → αβ | αγ を A → αA'、A' → β | γ に変更し、選択を共通接頭辞の後に遅らせます。しかし、これによって任意の文法が LL(1) になる保証はなく、曖昧性が自動的に解消されるわけでもありません。

「浮動 else」は、どのレベルの if に結合すべきかという問題に関与します。言語は、直近の未結合の if に一致することを規定するか、明示的な終了記子を要求するか、文法で一致済みと未結合の文を区別することができます。具体的なルールを説明する必要があり、単に「先読みが足りない」と呼び出すだけでは不十分です。

試行解析でバックトラックする場合、カーソル、一時的な診断、および他の可変状態を同時に復元する必要があります。頻繁な再試行は同じ接頭辞の再解析を引き起こす可能性があります。メモ化はメモリ増加を招き、結果がキャッシュキーに正しく組み込まれることを要求します。

Pratt：左右の結合強度が木構造を制御する

以下は、そのまま実行可能な Python の教育用実装です。入力はすでにトークンに分割されたリストです。数値は非負の10進整数であり、単項のマイナス記号は個別に解析されます。ここで ^ は、この例言語ではべき乗演算として定義されており、Python の ^ （排他的論理和）とは無関係です。

class Parser:
    # (左結合強度, 右側再帰の閾値)
    INFIX = {"+": (10, 11), "-": (10, 11),
             "*": (20, 21), "/": (20, 21), "^": (30, 30)}

    def __init__(self, tokens):
        self.tokens = list(tokens) + [None]
        self.pos = 0

    def peek(self):
        return self.tokens[self.pos]

    def take(self):
        token = self.peek()
        if token is None:
            raise SyntaxError("expected expression before EOF")
        self.pos += 1
        return token

    def expr(self, minimum=0):
        token = self.take()
        if token.isascii() and token.isdecimal():
            left = ("number", int(token))
        elif token == "-":
            left = ("negate", self.expr(30))
        elif token == "(":
            left = self.expr()
            if self.peek() != ")":
                raise SyntaxError("expected closing parenthesis")
            self.take()
        else:
            raise SyntaxError(f"expected expression, got {token!r}")

        while self.peek() in self.INFIX:
            op = self.peek()
            lbp, rbp = self.INFIX[op]
            if lbp < minimum:
                break
            self.take()
            left = (op, left, self.expr(rbp))
        return left

    def parse(self):
        result = self.expr()
        if self.peek() is not None:
            raise SyntaxError(f"unexpected trailing token {self.peek()!r}")
        return result

assert Parser(["8", "-", "3", "-", "2"]).parse() == (
    "-", ("-", ("number", 8), ("number", 3)), ("number", 2))

この実装では、lbp >= minimum の演算子が現在の呼び出しに入ることができます。左結合の減算では右側に 11 が使用されるため、右側は左結合強度が 10 の次のマイナス記号を消費せず、それは外側のループに残されます。右結合のべき乗では左右の閾値がともに 30 であるため、右側は次のべき乗を継続して吸収できます。

単項マイナス記号は、そのオペランドを 30 から開始させるため、- 2 ^ 2 は -(2^2) として解析されます。これは明確に選択された言語ルールです。閾値を変更することで、別のルールを定義することができます。括弧と EOF は中缀表中に含まれておらず、自然にループを終了させるため、それらに虚構の最低中缀優先度を割り当てるべきではありません。

完全な Pratt 実装では、トークンに接頭辞、後置、中缀プロセッサを設定でき、関数呼び出し、メンバーアクセス、または三項演算子を追加できます。この例では結合方向に焦点を当てており、ソースコードの位置、リソースの上限、エラー回復は含まれていません。深いネストは、実際の実装では呼び出しスタックの枯渇を避ける必要があります。著者のチュートリアルでは、トークンに基づいて式コンパイルを整理する方法が示されています。Crafting Interpreters 第 17 章

閾値を追跡し、トークンが実際にどの呼び出し層で消費されるかを確認する

8 - 3 - 2 に対して、外側は最初のマイナス記号を見て、閾値 11 で右側を再帰的に解析します。右側は 3 を読み、次に2番目のマイナス記号の左結合強度が 10 であることを確認し、11 よりも小さいため、マイナス記号を消費せずに戻ります。外側はまず 8−3 を構成し、その後2番目のマイナス記号を消費し続け、最終的に (8−3)−2 を得ます。

以下のアサーションを Parser 定義の直後に追加し、評価結果で木構造の違いを隠すことなく、AST を直接チェックします。

N = lambda x: ("number", x)
assert Parser(["2", "+", "3", "*", "4"]).parse() == ("+", N(2), ("*", N(3), N(4)))
assert Parser(["2", "^", "3", "^", "2"]).parse() == ("^", N(2), ("^", N(3), N(2)))
assert Parser(["-", "2", "^", "2"]).parse() == ("negate", ("^", N(2), N(2)))
assert Parser(["(", "-", "2", ")", "^", "2"]).parse() == ("^", ("negate", N(2)), N(2))
for tokens in ([], ["1", "2"], ["1", "+"], ["(", "1"], ["1", ")"], ["*", "2"]):
    try:
        Parser(tokens).parse()
    except SyntaxError:
        pass
    else:
        raise AssertionError(f"invalid input accepted: {tokens}")

空の入力、末尾のトークン、右オペランドの欠如、右括弧の欠如、および無効な接頭辞は、それぞれ異なる失敗位置から生じます。1つの式が正しい数値を得るかどうかを観察するだけでなく、これらの入口と出口条件をチェックすることで、パーサが入力を完全に消費しているかどうかをより明確に示すことができます。

結合閾値を1つ変更すると、なぜ木が変わってしまうのか？

結合強度は評価順序のアニメーション速度ではなく、現在の再帰呼び出しが演算子を消費し続けるかどうかの閾値です。以下では、制限付きの Pratt パーサを実際に実行し、得られた木から括弧形式と結果を生成します。減算の右閾値を変更すると結合方向が変わります。乗法の強度を加算より下に下げると、どちらの部分木が先に構成されるかが変わります。閾値の記録により、結果がなぜ変わったかを説明でき、単に2つの異なる答えを表示するだけで済みません。

選択と次のステップ

階層化された再帰降下は、言語ルールに直接対応するのに適しています。Pratt は、式演算子を集中的に管理するのに適しています。ジェネレータは優れた診断を提供できるかもしれませんが、手書きでも回復が不十分になる可能性があり、品質は実装への投資に依存します。より一般的な決定論的文法の処理が必要な場合は、LR 解析を参照してください。どのような木が生成されるかは、AST デザインとエラー回復を参照してください。

Keywords: 再帰降下, LL(1), FIRST, FOLLOW, 予測集合, 左再帰, 左因子抽出, Pratt パーサ, 結合強度, 結合性