LR 解析

LR 解析はトークンを左から右へ読み取り、シフトとリダクションによって右端導出の逆過程を構築する。まず既に見た構造を蓄積し、その後、それらの記号がどの生成規則に属するかを決定する。素朴な再帰下降パーサとは異なり、決定論的 LR は多くの左再帰文法を直接処理できる。

ランタイムでは通常、状態スタックとテーブル参照ループのみで構成される；複雑な部分はテーブルの生成、競合の理解、およびセマンティックアクションの設計にある。小さな文法であれば手動で構築できるが、実務では通常ツールによって生成される。

シフト、リダクション、および状態スタック

E → E + n | n および入力 n + n を例とする：まず n をシフトし、次にそれを E にリダクションする。その後、プラス記号と2番目の n をシフトし、最後に E + n を E にリダクションする。リダクション時には AST ノードを同時に構築できる。

状態スタックとセマンティック値スタックを別々に管理する場合、右辺の長さが r のリダクションではそれぞれ r 項目ポップされ、状態スタックの底には開始状態が残る。状態と文法記号を交互に格納する場合、ポップされる項目数に関する記述は異なる。空の生成規則では 0 項目ポップされるが、GOTO によってリダクション後の状態へ遷移する必要がある。

プロジェクト：ドットが生成規則のどこまで認識されたかを示す

プロジェクト E → E · + n は、E がすでに認識されており、次にプラス記号と n を認識できることを示す。E → E + n · は右辺が完全に整っており、リダクションを検討できることを示す。

1つの状態には多くのプロジェクトが含まれることが多く、これは現在の接頭辞が複数の文脈にある可能性があることを表す。これは実行可能接頭辞の情報を記録しており、1つのソースコードトークンにのみ対応しているわけではない。

LR(0) プロジェクト集合において、closure は A → α · B β に遭遇すると、B のすべての生成規則 B → · γ を追加し、再帰的に拡張する。goto(I, X) はまず I 内のドットの前の記号が X のプロジェクトを1つ右に移動し、次にクロージャを取る。新しい集合に対して goto を繰り返し実行することで、プロジェクト集合オートマトンを構築できる。

終端記号上のエッジはシフトアクションを形成し、非終端記号上のエッジは GOTO を形成する。完成プロジェクトがどの先読みでリダクションするかは、LR の各変体の重要な違いである。

5つの状態で n+n を完了：リダクション後はまず古い状態に戻り、GOTO を参照する

冒頭の文法に番号を振る：規則1は E→E+n、規則2は E→n。以下の状態番号を採用する。これらは本例で手動指定されたもので、生成ツールの出力と一致する必要はない。

状態0のクロージャには E→·E+n と E→·n が含まれる。E を認識すると状態1へ遷移し、プラス記号または終了を待つ。n を認識すると状態2へ遷移し、E→n にリダクションできる。状態3は E→E+·n を表し、状態4は E→E+n· が完了したことを表す。FOLLOW(E)={+, $} であるため、これらの2つの先読みに対応するリダクションを記載する。

ACTION = {
    (0, "n"): ("shift", 2), (1, "+"): ("shift", 3),
    (1, "$"): ("accept", 0), (2, "+"): ("reduce", 2),
    (2, "$"): ("reduce", 2), (3, "n"): ("shift", 4),
    (4, "+"): ("reduce", 1), (4, "$"): ("reduce", 1),
}
GOTO = {(0, "E"): 1}


def parse(tokens):
    if any(t not in ("n", "+") for t in tokens):
        raise SyntaxError("invalid token")
    source = list(tokens) + ["$"]
    states, values, pos, trace = [0], [], 0, []
    while True:
        action = ACTION.get((states[-1], source[pos]))
        if action is None:
            raise SyntaxError(f"unexpected {source[pos]} at token {pos}")
        kind, number = action
        trace.append((tuple(states), pos, kind))
        if kind == "shift":
            states.append(number)
            values.append(("n",) if source[pos] == "n" else "+")
            pos += 1
        elif kind == "reduce":
            length = 3 if number == 1 else 1
            rhs = values[-length:]
            value = ("+", rhs[0], rhs[2]) if number == 1 else rhs[0]
            del values[-length:]
            del states[-length:]
            states.append(GOTO[(states[-1], "E")])
            values.append(value)
        else:
            assert len(values) == 1 and pos == len(tokens)
            return values[0], trace


node, trace = parse(["n", "+", "n"])
assert node == ("+", ("n",), ("n",))
assert [p for stack, p, action in trace] == [0, 1, 1, 2, 3, 3]
assert parse(["n", "+", "n", "+", "n"])[0] == ("+", node, ("n",))
assert parse(["n"])[0] == ("n",)
for tokens in ([], ["+", "n"], ["n", "n"], ["n", "+"], ["n", "$"]):
    try:
        parse(tokens)
    except SyntaxError:
        pass
    else:
        raise AssertionError("invalid input accepted")

2番目の n を読み終えた後、スタックは [0,1,3,4] である。リダクション長3で [0] に戻り、GOTO(0,E)=1 を参照する。この時点での先読みは依然として $ であり、次のステップで初めて accept する。リダクション前のスタックトップ4で GOTO を参照することはできず、リダクションを実行したからといって $ を勝手に消費してはならない。

本例には空規則がないため、コードの length は常に0より大きい。ε に拡張する場合は、長さ0のケースを特別に処理する必要がある。Python の del stack[-0:] はスタック全体を空にするものであり、「何もポップしない」ことではない。これはアルゴリズムの説明をそのままスライスコードにコピーする際に見過ごされがちな境界条件である。

リダクションはスタックを変更したが、なぜ先読みは進まないのか？

リダクションの観察時には、ポップ前とポップ後の状態の両方を保持する必要がある。図中の先読みには独自の位置があり、シフトのみがそれを移動させる。reduce はまず右辺を除去し、残ったスタックトップで GOTO を参照する。任意のアクションを直接選択したり、スタック変化の全体を再生したりできる。無効な入力でも実際のテーブル参照フローに従い、テーブルエントリがない場所で停止し、デモを完遂するためにエラーをスキップすることはない。

SLR、LR(1)、LALR はどの程度の文脈を保持するか

LR(1) プロジェクト [A → α · B β, a] のクロージャでは、B の生成規則に対して FIRST(βa) 内の終端記号を先読みとして使用する。a は A の完了後に何が許可されるかを示し、単にドットの直後に読む文字と単純に理解してはならない。

正規 LR(1) は LALR(1) より多くの文法を処理できるが、依然としてすべての文脈自由文法を処理できるわけではない。曖昧な文法は、曖昧性解消ルールなしには決定論的 LR テーブルによって一意な解析を与えることができない。

LR(1) だが LALR(1) ではない例

S → a A d | b A e | a B e | b B d
A → c
B → c

この文法は acd、bce、ace、bcd の4つの文字列のみを生成し、それぞれに一意な導出がある。ac を読み終えた後、d が続く場合は c を A にリダクションし、e が続く場合は B にリダクションする。bc を読み終えた場合はちょうど逆になる。

これは、競合がテーブル構築における文脈の圧縮に起因する可能性があることを示しており、reduce/reduce 競合が見られたからといって、すぐに原文法に曖昧性があると断定してはならない⁠。SLR のグローバル FOLLOW も同様の精度の問題を引き起こす。Bison マニュアルでは、この LALR 制限による競合および IELR や正規 LR を採用する方法について特に議論している。Mysterious Conflicts

生成器を使って「文法競合」と「マージによる競合」を区別する

上記の4文字列文法を conflict.y として記述し、文字終端記号にはシングルクォートを使用する：

%start S
%%
S: 'a' A 'd' | 'b' A 'e' | 'a' B 'e' | 'b' B 'd';
A: 'c';
B: 'c';
%%

bison -Dlr.type=lalr --report=states,lookaheads -o lalr.c conflict.y
bison -Dlr.type=canonical-lr --report=states,lookaheads -o canonical.c conflict.y

このステップではテーブルとレポートのみを生成し、lexer は不要であり、まだ実行可能プログラムではない。LALR では2つの reduce/reduce 競合が発生するはずだが、正規 LR では ac および bc 後の異なる文脈を保持し、このような競合は発生しない。レポートを確認する際は、完成プロジェクト A→c· および B→c· の先読みを特定し、状態の総数だけを比較しないように注意する。

競合のある LALR のデフォルト選択を引き続き使用すると、特定の文字列が誤ったリダクション経路をたどる可能性がある。したがって、「ツールが C ファイルを生成したからといって、言語が正しく実装されたわけではない」。実務では、適切な構築方法を明確に選択するか、文法を書き換えるべきであり、警告を無視してはならない。Bison マニュアルソース内のアルゴリズム説明

状態をマージする際、どの対応関係が失われるのか？

マージ前、2つの出所はそれぞれ「接頭辞、完成プロジェクト、許可される先読み」の対応関係を保持している。マージ後、A と B はそれぞれ先読みの和集合を得るが、d がどの接頭辞から持ってきたものなのかはもはやわからない。以下では、圧縮によって何が失われたかを見比べられるよう、元の2行を常に保持する。4つの入力文字列は原文法において依然としてそれぞれ一意な導出を持ち、テーブルの競合は曖昧性の証明に代わるものではない。

2種類の競合を区別し、解決の根拠とする

shift/reduce は、同じ状態と先読みにおいて、シフトもリダクションも可能なことを示す。例えば E → E + E | E * E | n は優先順位を表現しておらず、n + n * n に対して異なる木構造が生じる。階層化された文法に書き換えるか、ツールの優先順位・結合性宣言を使用して言語ルールを表現できる。

reduce/reduce は、同じ位置に複数の候補リダクションがあることを示す。これは真の曖昧性である場合もあれば、前述の文脈マージの結果である場合もある。警告を単に無視するのではなく、プロジェクト、先読み、最短トリガー入力、および反例を確認するべきである。

優先順位宣言はセマンティックな選択であり、任意の競合に対する正当性の証明ではない。特に2つのリダクションが異なるセマンティックアクションを実行する場合、デフォルトで特定のルールを選択すると、AST や副作用が変更される可能性がある。

Bison と LALRPOP：名前がアルゴリズムを意味しない

Bison は LALR、IELR、正規 LR、GLR などの設定をサポートしている。LALRPOP は名前に LALR を含むが、プロジェクトの説明におけるデフォルトアルゴリズムは LR(1) である。すべてのツールを一律に「デフォルト LALR」として扱うことはできず、正規 LR と LALR の状態数に固定の倍率を規定することもできない。Bison 文法と解析能力、LALRPOP プロジェクト説明

GLR は競合ポイントで複数の解析分岐を保持し、その後それらを淘汰またはマージできるが、曖昧なセマンティクスを定義する必要があり、最悪のコストも決定論的 LR とは異なる。セマンティックアクションの遅延、共有木表現、およびエラー処理には追加の設計が必要である。

エラーリカバリ：error は特殊なメカニズム

Bison では以下のようなリカバリ生成規則を記述できる：

statement: error ';' { yyerrok; };

error はパーサの特殊記号であり、lexer が返す「任意の文字」ルールではない。リカバリ時、パーサは error をシフトできる状態になるまでスタックをポップし、必要に応じて入力を破棄して継続可能なトークンを見つける。セミコロンへの同期は、このルールが提供する出口に過ぎず、すべてのエラーが自然にセミコロンで停止するわけではない。

破棄された記号のリソースは正しく解放する必要がある。リカバリ後のセマンティック値も明確な表現を持つべきであり、後続フェーズでエラー構造を正常なノードとして扱わないようにする。一部のリカバリは一時的にカスケード診断を抑制するため、「パーサが戻ってきたからといって、ソースコードが完全に正しいわけではない」。Bison エラーリカバリ

実務的判断

決定論的 LR のテーブル参照プロセスは、固定文法、循環する空リダクションの不在、および制御されたセマンティックアクションという前提の下、入力長に対して線形時間である。テーブルの構築とエラーリカバリのコストは別途計算される。インクリメンタル編集のサポートも、木構造、再利用戦略、および字句文脈に依存しており、LL/LR ラベルのみで判断できるものではない。

競合を理解する際は、まず「読み終えた接頭辞、現在の項目（item）、1つの先読み、候補アクション」を復元し、それが言語ルール、文法表現、またはアルゴリズムの精度の問題であるかを判断する。AST 設計とエラーリカバリ を続けて参照してください。

Keywords: LR, item, closure, goto, shift reduce, SLR, LALR, canonical LR, IELR, GLR, lookahead, conflict, Bison, LALRPOP