Zenn
⚙️

作って学ぶLR(1)構文解析

に公開
Rust
構文解析
zennfes2025free
tech

はじめに

構文解析できる人ってかっこいいですよね（要出典）。
皆さんが普段使っているプログラミング言語も、どこかの「かっこいい人」がコンパイラやインタプリタを作ってくれたから実行できるわけです。この記事が、あなたが「かっこいい人」の仲間入りをする助けになれば幸いです。

作るもの

LR(0)、LR(1)、LALRパーサーをRustで実装します。Lexerの実装はやるだけなので賢明な読者への課題とします。
Rustでパーサーを作るとなればnomなどのパーサージェネレータやpestなどのPEGベースのパーサーを用いるのが一般的ですが、今回は構文解析の仕組みを理解するため標準ライブラリのみ使用します。

LRという名前は、左（Left）から入力を読んでいき、右（Right）端から解析をするという挙動に由来します（入力は左から右に読む横書きで書かれているとします）。カッコ内の文字は先読みの文字数を表します。LR(0)であれば先読みせずこれまでに読んだ文字列のみを元に次のアクションを決め、LR(1)ならそれに加えて次に来る1文字（1トークン）も参照できます。当然LR(1)の方がLR(0)より幅広い文法を扱えますがその分実装が複雑になるため、まずはLR(0)パーサーを実装し、それを応用してLR(1)パーサーをつくります。

文脈自由文法

構文解析をするためにはまず文法を定義する必要があります。LR(1)文法は文脈自由文法の一種なのでまずは文脈自由文法の気持ちを理解しましょう。
いきなりですが例を示します。

S     = IDENT "=" BOOL OP BOOL
IDENT = "x"
BOOL  = "true" | "false"
OP    = "and" | "or" | "xor"

これはx = true and falseとかx = false xor falseとかいった文字列を受容する文法です。
SやOPのように、左辺に登場する記号を非終端記号といいます。それに対し、trueやandのように解析対象の文字列にそのまま現れるものを終端記号といいます。
もう一つ例を出します。

S = M
M = ""
M = "x" M "y"

これは0個以上のxに同じ個数のyが続く文字列を「正しい」とする文法です。3行目の右辺に左辺と同じMが含まれるので面食らうかもしれませんが、例えばxxyyという文字列は以下のような構文木で表されることを考えると、こういうパターンもあるかと納得できるのではないでしょうか。

さて、上記の文法はどちらもSという記号が根っこにありますね。これを開始記号といいます。

文脈自由文法は、

  • 非終端記号の集合
  • 終端記号の集合
  • 開始記号
  • 導出ルールの集合

によって定義されます。
ここまでの知識をコードに落とし込んでおきます。文脈自由文法を、非終端記号と終端記号はジェネリクスに、開始記号と導出ルールの集合は構造体のフィールドに含めることで定義します。

src/lib.rs
pub mod grammar;
src/grammar/mod.rs
mod rule;
mod symbol;

pub use symbol::{NonTerminalSymbol, Symbol, TerminalSymbol};

#[derive(Debug)]
pub struct Grammar<T: TerminalSymbol, N: NonTerminalSymbol> {
    start_symbol: N,
    derivations: Vec<Rule<T, N>>,
}
impl<T: TerminalSymbol, N: NonTerminalSymbol> Grammar<T, N> {
    pub fn new(start_symbol: N, derivations: Vec<Rule<T, N>>) -> Self {
        Self {
            start_symbol,
            derivations,
        }
    }

    pub fn start_symbol(&self) -> N {
        self.start_symbol
    }

    pub fn iter(&self) -> impl Iterator<Item = &Rule<T, N>> {
        self.derivations.iter()
    }

    pub fn at(&self, idx: usize) -> Option<&Rule<T, N>> {
        self.derivations.get(idx)
    }

    pub fn nonterminals(&self) -> std::collections::BTreeSet<N> {
        self.derivations.iter().map(|rule| rule.variable).collect()
    }

    pub fn rules_for(&self, n: &N) -> impl Iterator<Item = &Rule<T, N>> {
        self.iter().filter(|rule| rule.variable == *n)
    }

    pub fn entry_points(&self) -> impl Iterator<Item = &Rule<T, N>> {
        self.iter()
            .filter(|rule| rule.variable == self.start_symbol)
    }
}
src/grammar/symbol.rs
pub trait TerminalSymbol: Copy + std::cmp::Ord {
    type NonTerminal: NonTerminalSymbol;
    fn into_symbol(self) -> Symbol<Self, Self::NonTerminal>;
}

pub trait NonTerminalSymbol: Copy + std::cmp::Ord {
    type Terminal: TerminalSymbol;
    fn into_symbol(self) -> Symbol<Self::Terminal, Self>;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum Symbol<T: TerminalSymbol, N: NonTerminalSymbol> {
    /// 非終端記号
    NonTerminal(N),
    /// 終端記号
    Terminal(T),
    /// 入力の終端
    Eof,
}
src/grammar/rule.rs
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct Rule<T: crate::grammar::TerminalSymbol, N: crate::grammar::NonTerminalSymbol> {
    pub variable: N,
    pub derivation: Vec<crate::grammar::Symbol<T, N>>,
}

TerminalSymbolやNonTerminalSymbolは実はCopyではなくCloneで十分なのですが、Copyを要求しておく方が後々実装が楽になるのでこうしておきます。

LR(0)解析表

LRパーサーは読んだ文字列をスタックに積んでいき、然るべきタイミングでスタックからポップした文字列を然るべき文法規則で還元することで解析を進めます。百聞は一見に如かず、具体例を見てみましょう。開始記号はEです。

E = "[" L "]"
E = V
L = E
L = L "," E
V = "x"

この文法定義から、後述のアルゴリズムで以下のような解析表が作成されます。

"[" "]" "x" "," $ E L V
状態0 s1 s2 9 3
状態1 s1 s2 4 5 3
状態2 V = "x" 同左 同左 同左 同左
状態3 E = V 同左 同左 同左 同左
状態4 L = E 同左 同左 同左 同左
状態5 s6 s7
状態6 E = "[" L "]" 同左 同左 同左 同左
状態7 s1 s2 8 3
状態8 L = L "," E 同左 同左 同左 同左
状態9 acc

解析表の使い方

解析表の作り方を説明する前に、これに沿って文字列[x,x]を解析する方法を見ておきましょう。
初期状態（状態0）では空のスタックを用意します。
まずは1文字目の[を読みます。状態0の行、[の列には「s1」と書いてあるので("[", 1)をスタックに積みます。s1は「読んだ文字を状態1とともにShiftせよ」という意味です。スタックに積むことをここではShiftすると言います。
次に2文字目のxを読みます。スタックのトップの状態1の行でxの列を見ると「s2」と書いてあるので、("x", 2)をスタックに積みます。ここまででスタックは

[("[", 1), ("x", 2)]

のようになっています。
状態2ではV = "x"で還元することになっているので、スタックから("x", 2)をpopし、残りのトップの状態（状態1）の行、新しくできたシンボルVの列を見て3とあるので(V, 3)をスタックに積みます。スタックのトップを還元しつつ異なる状態に遷移する、ということでこれをGotoと呼びます。
続きは以下のようになります。

スタックの状態 残りの入力 アクション
[("[", 1), (V, 3)] ,x] E = Vで還元
[("[", 1), (E, 4)] ,x] L = Eで還元
[("[", 1), (L, 5)] ,x] Shift 7
[("[", 1), (L, 5), (",", 7)] x] Shift 2
[("[", 1), (L, 5), (",", 7), ("x", 2)] ] V = "x"で還元
[("[", 1), (L, 5), (",", 7), (V, 3)] ] E = Vで還元
[("[", 1), (L, 5), (",", 7), (E, 8)] ] L = L "," Eで還元
[("[", 1), (L, 5)] ] Shift 6
[("[", 1), (L, 5), ("]", 6)] E = "[" L "]"で還元
[(E, 9)] Accept

開始記号の後に入力の終端$に出会ったら正しい入力であったと判断します（Accept）。めでたしめでたし。
LR構文解析がどのように進むか、だいたいの流れが掴めたでしょうか。残る問題は、解析表をどうやって組み立てるかです。

解析表の作り方

状態0だけがある表からスタートして表を少しずつ埋めることで解析表を完成させます。

"[" "]" "x" "," $ E L V
状態0 ? ? ? ? ? ? ? ?

状態0を

状態0
E = . "[" L "]"
E = . V

と表すことにします。ここで.は「ここまで読みました」という印です。つまりこれは「これから読む文字列は"[" L "]"またはVとなっているはずであり、これはいずれEに還元されるだろう」という状態です。ところで、これからVを読むということは、「これから読む文字列は"x"となっているはずであり、これはいずれVに還元されるだろう」という状態でもありますね。そこで、

V = . "x"

という行を状態0に追加します。

状態0
E = . "[" L "]"
E = . V
V = . "x"

より一般的に、.の直後に非終端記号が来ていたら、それが左辺にあるような文法規則を探してきて、右辺の最初に.を付けて追記します。
このように、不完全な「状態」からスタートして行を追加していく手続きをRustのコードに落とし込みます。ちなみに、今まで「状態」と読んできたものは正しくはClosureと呼ばれます。Closureに含まれる各行はClosureItemという構造体で表すことにします。

src/lib.rs
pub mod common;
pub mod lr0; // 追加
src/lr0/mod.rs
mod closure;
src/lr0/closure.rs
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct ClosureItem<
    'grammar,
    T: crate::grammar::TerminalSymbol,
    N: crate::grammar::NonTerminalSymbol,
> {
    rule: &'grammar crate::grammar::Rule<T, N>,
    /// 何個目のシンボルまで読んだか
    pos: usize,
}

impl<
    'grammar,
    T: crate::grammar::TerminalSymbol<NonTerminal = N>,
    N: crate::grammar::NonTerminalSymbol<Terminal = T>,
> ClosureItem<'grammar, T, N>
{
    fn new(rule: &'grammar crate::grammar::Rule<T, N>) -> Self {
        Self { rule, pos: 0 }
    }

    fn consumed(&self) -> &[crate::grammar::Symbol<T, N>] {
        &self.rule.derivation[..self.pos]
    }

    fn remaining(&self) -> &[crate::grammar::Symbol<T, N>] {
        &self.rule.derivation[self.pos..]
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Closure<
    'grammar,
    T: crate::grammar::TerminalSymbol,
    N: crate::grammar::NonTerminalSymbol,
> {
    pub items: std::collections::BTreeSet<ClosureItem<'grammar, T, N>>,
}

impl<
    'grammar,
    T: crate::grammar::TerminalSymbol<NonTerminal = N>,
    N: crate::grammar::NonTerminalSymbol<Terminal = T>,
> Closure<'grammar, T, N>
{
    pub fn new(
        kernel: std::collections::BTreeSet<ClosureItem<'grammar, T, N>>,
        grammar: &'grammar crate::grammar::Grammar<T, N>,
    ) -> Self {
        todo!()
    }
}

Closure::new()の実装方針ですが、簡単のため、変化がなくなるまでループを回すという素朴なアルゴリズムを使います。

impl<
    'grammar,
    T: crate::grammar::TerminalSymbol<NonTerminal = N>,
    N: crate::grammar::NonTerminalSymbol<Terminal = T>,
> Closure<'grammar, T, N>
{
    pub fn new(
        kernel: std::collections::BTreeSet<ClosureItem<'grammar, T, N>>,
        grammar: &'grammar crate::grammar::Grammar<T, N>,
    ) -> Self {
        let mut items = kernel;
        loop {
            // items内のアイテムから生まれるアイテム
            let new_items = items
                .iter()
                .filter_map(|item| match item.remaining().first() {
                    Some(crate::grammar::Symbol::NonTerminal(nt)) => Some(nt),
                    _ => None,
                })
                .flat_map(|nt| grammar.rules_for(nt).map(ClosureItem::new))
                .collect::<std::collections::BTreeSet<_>>();

            // new_itemsの追加により変化があったか
            let changed = new_items
                .into_iter()
                .map(|item| items.insert(item))
                .reduce(|changed, inserted| changed || inserted)
                .unwrap_or(false);

            // 変化がなければループ終了
            if !changed {
                break;
            }
        }
        Closure { items }
    }
}

後のためにいくつか便利関数を定義しておきます。Closure構造体にentry_point、next、reduceメソッドを実装します。

impl<
    'grammar,
    T: crate::grammar::TerminalSymbol<NonTerminal = N>,
    N: crate::grammar::NonTerminalSymbol<Terminal = T>,
> Closure<'grammar, T, N>
{
    pub fn new(
        kernel: std::collections::BTreeSet<ClosureItem<'grammar, T, N>>,
        grammar: &'grammar crate::grammar::Grammar<T, N>,
    ) -> Self {
        // 中略
    }

    /// 初期状態となるClosureを生成する
    pub fn entry_point(grammar: &'grammar crate::grammar::Grammar<T, N>) -> Self {
        let kernel = grammar.entry_points().map(ClosureItem::new).collect();
        Self::new(kernel, grammar)
    }

    /// `.`の直後に来るシンボルをキーとし、遷移先のアイテム集合を値とするマップを返す
    pub fn next(
        &self,
    ) -> std::collections::BTreeMap<
        crate::grammar::Symbol<T, N>,
        std::collections::BTreeSet<ClosureItem<'grammar, T, N>>,
    > {
        self.items
            .iter()
            .filter_map(|item| match item.remaining().first() {
                Some(crate::grammar::Symbol::Eof) => unreachable!(),
                Some(first) => {
                    let new_item = ClosureItem {
                        rule: item.rule,
                        pos: item.pos + 1,
                    };
                    Some((*first, new_item))
                }
                _ => None,
            })
            .fold(
                std::collections::BTreeMap::new(),
                |mut map, (symbol, item)| {
                    map.entry(symbol).or_default().insert(item);
                    map
                },
            )
    }

    // 還元できるアイテムがあれば返す
    pub fn reduce(
        &self,
        grammar: &'grammar crate::grammar::Grammar<T, N>,
    ) -> Option<&'grammar crate::grammar::Rule<T, N>> {
        self.items
            .iter()
            .find(|item| item.remaining().is_empty())
            .map(|item| (item.rule.variable, item.consumed()))
            .and_then(|(variable, derivation)| {
                grammar
                    .iter()
                    .find(|rule| variable == rule.variable && derivation == rule.derivation)
            })
    }
}

さて、状態0を作るコードができたので今度は遷移先の状態を順に作っていきます。状態0の.の直後にはVか"["か"x"があるので、次に読むトークンはこのどれかです。裏を返せば"]"や,が来たら文法エラーです。"["を読んだらどうなるでしょうか？以下のような状態が生まれます。

E = "[" . L "]"

.の直後に非終端記号Lがあるので、先述の規則に従い行を追加します。

E = "[" . L "]"
L = . E
L = . L "," E

.の直後に非終端記号Eがあるので、先述の規則に従い行を追加します。以下同様に繰り返します。

状態1
E = "[" . L "]"
L = . E
L = . L "," E
E = . "[" L "]"
E = . V
V = . "x"

これが状態1です。
状態0から"x"を読んだ場合は以下の状態2に移ります。

状態2
V = "x" .

状態0から Vを読んだ場合は以下の状態3に移ります。

状態3
E = V .

状態0から"["を読むと状態1に、"x"を読むと状態2に、Vを読むと状態3になるので解析表は以下のようになります。

"[" "]" "x" "," $ E L V
状態0 s1 s2 3
状態1 ? ? ? ? ? ? ? ?
状態2 ? ? ? ? ? ? ? ?
状態3 ? ? ? ? ? ? ? ?

状態1の.の直後には"[", "x", E, L, Vのいずれかが来ます。それ以外が来たら文法エラーです。
"["を読むと

E = "[" . L "]"

となり、.の直後にLがあるので規則に従って処理を行うと状態1と全く同じものができます。したがって状態1で"["を読んだら状態1に移ります。
"x"を読むと状態2と同じになります。Eを読むと

状態4
L = E .

に移り、Lを読むと

状態5
E = "[" L . "]"
L = L . "," E

に移り、Vを読むと状態3と同じになります。

"[" "]" "x" "," $ E L V
状態0 s1 s2 3
状態1 s1 s2 4 5 3
状態2 ? ? ? ? ? ? ? ?
状態3 ? ? ? ? ? ? ? ?
状態4 ? ? ? ? ? ? ? ?
状態5 ? ? ? ? ? ? ? ?

さて、状態2は

V = "x" .

でした。.が右端にある場合、次のトークンが何であるかに関係なく.より左側の文法規則V = "x"で還元します。終端記号の列全てにこの文法規則を書き込みます。.が最右端ということは続きのトークンはないはずなので、Eなどの列（非終端記号の列）には何も書きません。
状態3、4も同様です。

"[" "]" "x" "," $ E L V
状態0 s1 s2 3
状態1 s1 s2 4 5 3
状態2 V = "x" 同左 同左 同左 同左
状態3 E = V 同左 同左 同左 同左
状態4 L = E 同左 同左 同左 同左
状態5 ? ? ? ? ? ? ? ?

状態5では"]"か","を読みます。"]"を読むと

状態6
E = "[" L "]" .

","を読むと

状態7
L = L "," . E
E = . "[" L "]"
E = . V
V = . "x"

に移ります。状態6はE = "[" L "]"で還元し、状態7からEを読むと

状態8
L = L "," E .

に、"["を読むと状態1に、Vを読むと状態3に、"x"を読むと状態2に移ります。
状態8ではL = L "," Eで還元します。

また、初期状態（状態0）から開始記号を読み、その後入力の終端が来たら受理したいので、状態9を追加して状態0からEを読んだら状態9に移り、状態9で入力の終端$を読んだらAcceptすることにします。

"[" "]" "x" "," $ E L V
状態0 s1 s2 9 3
状態1 s1 s2 4 5 3
状態2 V = "x" 同左 同左 同左 同左
状態3 E = V 同左 同左 同左 同左
状態4 L = E 同左 同左 同左 同左
状態5 s6 s7
状態6 E = "[" L "]" 同左 同左 同左 同左
状態7 s1 s2 8 3
状態8 L = L "," E 同左 同左 同左 同左
状態9 acc

順番にClosureを作成し、表を埋めるアルゴリズムをRustに落とし込みます。整理すると

  1. S = A B Cのような形式の文法ルールからclosureのアイテムS = . A B Cを作り、さらにそれを核にしてclosureを拡張し、完全なclosureを得る。
  2. closureアイテムから.の直後の記号を1文字読んだ状態（.を1つ右にずらした状態）を作り、それを核にして新たなclosureを作る。読んだ記号が終端記号ならその列にShift操作を書き込み、非終端記号ならGoto操作を書き込む。変化がなくなるまで、全てのclosureに対してこの手続きを繰り返す。
  3. 各closureについて、右端に.があるアイテムがあれば全ての終端記号の列に対応する文法規則での還元を書き込む。

となります。
解析表をRustでどう表現するかですが、空欄も多いので2次元Vecのような形式でデータを持つのはメモリ効率が悪いです。以下のように、終端記号のShiftと非終端記号のGotoだけセルごとに持ち、Reduce（還元）は行ごとに情報を持つことにします。
ClosureIndexはただのusizeでもいいのですが、より意味が分かりやすくなるように構造体を定義しています。

src/lr0/mod.rs
mod closure;
pub mod parse_table; // 追加
src/lr0/parse_table.rs
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
#[repr(transparent)]
pub struct ClosureIndex(usize);

impl ClosureIndex {
    pub fn new(idx: usize) -> Self {
        Self(idx)
    }

    pub fn as_usize(self) -> usize {
        self.0
    }
}

impl<'grammar, T: crate::grammar::TerminalSymbol, N: crate::grammar::NonTerminalSymbol>
    std::ops::Index<ClosureIndex> for Vec<super::closure::Closure<'grammar, T, N>>
{
    type Output = super::closure::Closure<'grammar, T, N>;

    fn index(&self, index: ClosureIndex) -> &Self::Output {
        &self[index.as_usize()]
    }
}

#[derive(Debug)]
pub enum ParseTableError<
    'grammar,
    T: crate::grammar::TerminalSymbol,
    N: crate::grammar::NonTerminalSymbol,
> {
    ShiftReduceConflict {
        state: super::closure::Closure<'grammar, T, N>,
        token: T,
        rule: &'grammar crate::grammar::Rule<T, N>,
    },
    ReducesConflict {
        state: super::closure::Closure<'grammar, T, N>,
        rule1: &'grammar crate::grammar::Rule<T, N>,
        rule2: &'grammar crate::grammar::Rule<T, N>,
    },
}

#[derive(Debug)]
pub struct ParseTable<
    'grammar,
    T: crate::grammar::TerminalSymbol,
    N: crate::grammar::NonTerminalSymbol,
> {
    states: Vec<super::closure::Closure<'grammar, T, N>>,
    shift: std::collections::BTreeMap<(ClosureIndex, T), ClosureIndex>,
    reductions: std::collections::BTreeMap<ClosureIndex, &'grammar crate::grammar::Rule<T, N>>,
    goto: std::collections::BTreeMap<(ClosureIndex, N), ClosureIndex>,
    accept: ClosureIndex,
}

文法定義から解析表を作成する関数を実装していきます。まず初めに初期状態を作成し、各種フィールドを初期化します。

impl<
    'grammar,
    T: crate::grammar::TerminalSymbol<NonTerminal = N>,
    N: crate::grammar::NonTerminalSymbol<Terminal = T>,
> ParseTable<'grammar, T, N>
{
    pub fn new(
        grammar: &'grammar crate::grammar::Grammar<T, N>,
    ) -> Result<Self, super::closure::Closure<'grammar, T, N>> {
        let mut states = vec![super::closure::Closure::entry_point(grammar)];
        let mut goto = std::collections::BTreeMap::new();
        let mut shift = std::collections::BTreeMap::new();

        todo!()
    }
}

0番目のclosureから順に、遷移先になりうるclosureを生成していきます。

for cls_from_idx in 0.. {
    // 遷移元のclosure
    let Some(cls_from) = states.get(cls_from_idx) else {
        break;
    };
    cls_from
        .next()
        .into_iter()
        .for_each(|(symbol, new_kernel)| {
            // 遷移先のclosure
            let cls_to = super::closure::Closure::new(new_kernel, grammar);
            // 遷移先のclosureがstatesの何番目か
            let cls_to_idx =
                states.iter().position(|c| c == &cls_to).unwrap_or_else(|| {
                    states.push(cls_to);
                    states.len() - 1
                });
            let cls_from_idx = ClosureIndex::new(cls_from_idx);
            let cls_to_idx = ClosureIndex::new(cls_to_idx);
            match symbol {
                crate::grammar::Symbol::NonTerminal(nt) => {
                    goto.insert((cls_from_idx, nt), cls_to_idx);
                }
                crate::grammar::Symbol::Terminal(tt) => {
                    shift.insert((cls_from_idx, tt), cls_to_idx);
                }
                crate::grammar::Symbol::Eof => unreachable!(),
            }
        });
}

ここまでで解析表に登場する全てのclosureを列挙し終わり、ついでにShiftとGotoも計算できました。あとはReduceを計算します。Closure::reduceメソッドを利用し、ClosureがReduceできるかどうか、可能ならどのルールが該当するのかを調べます。Reduce-Reduce衝突をきちんとチェックしておきましょう。

let reductions = states
    .iter()
    .enumerate()
    .filter_map(|(cls_idx, cls)| {
        cls.reduce(grammar)
            .map(|rule| (ClosureIndex::new(cls_idx), rule))
    })
    .try_fold(
        std::collections::BTreeMap::<ClosureIndex, &'grammar crate::grammar::Rule<_, _>>::new(),
        |mut map, (idx, rule)| match map.entry(idx) {
            std::collections::btree_map::Entry::Occupied(e) => {
                Err(ParseTableError::ReducesConflict {
                    state: states[idx].clone(),
                    rule1: e.get(),
                    rule2: rule,
                })
            }
            std::collections::btree_map::Entry::Vacant(e) => {
                e.insert(rule);
                Ok(map)
            }
        },
    )?;

Shift-Reduce衝突もチェックが必要です。

S = A
A = "a"
A = "a" "b"

という文法で初期状態から"a"を読んだ先は

A = "a" .
A = "a" . "b"

であり、先読みができないLR(0)文法では次の"b"を読んでShiftすべきかA = "a"によってReduceすべきか判断できません。
以下のようにしてShift-Reduce衝突がないかチェックしておきます。

let reduction_cls = reductions.keys().collect::<std::collections::BTreeSet<_>>();
let shift_reduce_conflict = shift
    .keys()
    .find(|(cls_idx, _)| reduction_cls.contains(cls_idx));
if let Some((idx, token)) = shift_reduce_conflict {
    return Err(ParseTableError::ShiftReduceConflict {
        state: states[*idx].clone(),
        token: *token,
        rule: reductions[idx],
    });
};

さらに、入力の終端に出会った時にAcceptできる状態を求め、なければ作ります。

let accept = goto
    .get(&(ClosureIndex(0), grammar.start_symbol()))
    .copied()
    .unwrap_or_else(|| {
        let acc_cls = super::closure::Closure::new(Default::default(), grammar);
        let acc_cls_idx = ClosureIndex(states.len());
        states.push(acc_cls);
        goto.insert((ClosureIndex(0), grammar.start_symbol()), acc_cls_idx);
        acc_cls_idx
    });

全体像は次のようになります。

ParseTable::new の全体像
impl<
    'grammar,
    T: crate::grammar::TerminalSymbol<NonTerminal = N>,
    N: crate::grammar::NonTerminalSymbol<Terminal = T>,
> ParseTable<'grammar, T, N>
{
    pub fn new(
        grammar: &'grammar crate::grammar::Grammar<T, N>,
    ) -> Result<Self, ParseTableError<'grammar, T, N>> {
        let mut states = vec![super::closure::Closure::entry_point(grammar)];
        let mut goto = std::collections::BTreeMap::new();
        let mut shift = std::collections::BTreeMap::new();

        for cls_from_idx in 0.. {
            // 遷移元のclosure
            let Some(cls_from) = states.get(cls_from_idx) else {
                break;
            };
            cls_from
                .next()
                .into_iter()
                .for_each(|(symbol, new_kernel)| {
                    // 遷移先のclosure
                    let cls_to = super::closure::Closure::new(new_kernel, grammar);
                    // 遷移先のclosureがstatesの何番目か
                    let cls_to_idx =
                        states.iter().position(|c| c == &cls_to).unwrap_or_else(|| {
                            states.push(cls_to);
                            states.len() - 1
                        });
                    let cls_from_idx = ClosureIndex::new(cls_from_idx);
                    let cls_to_idx = ClosureIndex::new(cls_to_idx);
                    match symbol {
                        crate::grammar::Symbol::NonTerminal(nt) => {
                            goto.insert((cls_from_idx, nt), cls_to_idx);
                        }
                        crate::grammar::Symbol::Terminal(tt) => {
                            shift.insert((cls_from_idx, tt), cls_to_idx);
                        }
                        crate::grammar::Symbol::Eof => unreachable!(),
                    }
                });
        }

        // 各状態でreduceできる導出規則を調べる
        let reductions = states
            .iter()
            .enumerate()
            .filter_map(|(cls_idx, cls)| {
                cls.reduce(grammar)
                    .map(|rule| (ClosureIndex::new(cls_idx), rule))
            })
            .try_fold(
                std::collections::BTreeMap::<ClosureIndex, &'grammar crate::grammar::Rule<_, _>>::new(),
                |mut map, (idx, rule)| match map.entry(idx) {
                    std::collections::btree_map::Entry::Occupied(e) => {
                        Err(ParseTableError::ReducesConflict {
                            state: states[idx].clone(),
                            rule1: e.get(),
                            rule2: rule,
                        })
                    }
                    std::collections::btree_map::Entry::Vacant(e) => {
                        e.insert(rule);
                        Ok(map)
                    }
                },
            )?;

        // Shift-Reduce衝突の検出
        let reduction_cls = reductions.keys().collect::<std::collections::BTreeSet<_>>();
        let shift_reduce_conflict = shift
            .keys()
            .find(|(cls_idx, _)| reduction_cls.contains(cls_idx));
        if let Some((idx, token)) = shift_reduce_conflict {
            return Err(ParseTableError::ShiftReduceConflict {
                state: states[*idx].clone(),
                token: *token,
                rule: reductions[idx],
            });
        };

        // 入力の終端に出会った時にAcceptできる状態を求め、なければ作る
        let accept = goto
            .get(&(ClosureIndex(0), grammar.start_symbol()))
            .copied()
            .unwrap_or_else(|| {
                let acc_cls = super::closure::Closure::new(Default::default(), grammar);
                let acc_cls_idx = ClosureIndex(states.len());
                states.push(acc_cls);
                goto.insert((ClosureIndex(0), grammar.start_symbol()), acc_cls_idx);
                acc_cls_idx
            });

        Ok(Self {
            states,
            goto,
            shift,
            reductions,
            accept,
        })
    }
}

これでLR(0)解析表ができました。続けてLR(1)解析表を作ります。

LR(1)解析表

LR(1)文法では、LR(0)と違って1文字だけ先読みができます。そのため次に来るトークンによってShiftするかReduceするかを決められます。

nullableおよびFIRST集合

LR(1)解析表を作成するにあたり、nullable、FIRST集合という概念を知っておく必要があります。

nullableとは、与えられた非終端記号が空文字列を導出しうるかどうかを判定する関数です。文法を定義した段階で全ての非終端記号に対して値を計算し、結果をキャッシュしておくことにします。
新たにnullableだと判明した非終端記号があればそれを導出に含む全ての非終端記号を判定し直し、変化がなくなるまで繰り返します。なお、便宜上、終端記号は全てnullableでないということにしておきます。

src/grammar/mod.rs
mod first; // 追加
mod nullable; // 追加

// 中略

impl<T: TerminalSymbol, N: NonTerminalSymbol> Grammar<T, N> {
    // 中略

    /// 非終端記号をキーとし、導出結果にその非終端記号を含み得る非終端記号の集合を値とするマップ
    pub fn reverse_lookup(&self) -> std::collections::BTreeMap<N, std::collections::BTreeSet<N>> {
        self.iter()
            .flat_map(|rule| {
                rule.derivation
                    .iter()
                    .filter_map(|t| match t {
                        Symbol::NonTerminal(n) => Some(*n),
                        _ => None,
                    })
                    .map(move |n| (n, rule.variable))
            })
            .fold(
                std::collections::BTreeMap::<_, std::collections::BTreeSet<_>>::new(),
                |mut map, (key, value)| {
                    map.entry(key).or_default().insert(value);
                    map
                },
            )
    }
}
src/grammar/nullable.rs
#[derive(Debug)]
pub struct Nullable<N: super::NonTerminalSymbol> {
    inner: std::collections::BTreeSet<N>,
}

impl<N: super::NonTerminalSymbol> Nullable<N> {
    pub fn new<T: super::TerminalSymbol>(grammar: &super::Grammar<T, N>) -> Self {
        // nullableな非終端記号の集合
        let mut inner = std::collections::BTreeSet::new();
        // 処理中のシンボルのキュー
        let mut symbols = std::collections::VecDeque::from_iter(grammar.nonterminals());
        let lookup = grammar.reverse_lookup();

        while let Some(nt) = symbols.pop_front() {
            let nullable = grammar.rules_for(&nt).any(|rule| {
                use super::Symbol;
                rule.derivation.iter().all(|symbol| match symbol {
                    Symbol::Eof | Symbol::Terminal(_) => false,
                    Symbol::NonTerminal(n) => inner.contains(n),
                })
            });
            if nullable {
                let inserted = inner.insert(nt);
                if inserted && let Some(set) = lookup.get(&nt) {
                    set.iter().for_each(|n| {
                        if !symbols.contains(n) {
                            symbols.push_back(*n);
                        }
                    });
                }
            }
        }

        Self { inner }
    }

    pub fn nullable<T: super::TerminalSymbol>(&self, symbol: super::Symbol<T, N>) -> bool {
        use super::Symbol;
        match symbol {
            Symbol::Eof | Symbol::Terminal(_) => false,
            Symbol::NonTerminal(nt) => self.inner.contains(&nt),
        }
    }
}

FIRST集合とは、与えられた記号列の最初の終端記号になりうる終端記号の集合です。これも非終端記号に対してのみ事前に計算しておきます。例えばA = B C Dのようなルールがあった時、

  • FIRST(A)はFIRST(B)を含む
  • BがnullableならFIRST(A)はFIRST(C)を含む
  • BおよびCがnullableならFIRST(A)はFIRST(D)を含む

のようなことが成り立ちます。また、終端記号のFIRST集合は自分自身です。したがって、それぞれの規則について右辺の記号のFIRST集合を先頭から順に左辺にマージし、nullableでないトークンに出会ったら中断するというアルゴリズムで計算できます。

src/grammar/first.rs
#[derive(Debug)]
pub struct First<'nullable, T: super::TerminalSymbol, N: super::NonTerminalSymbol> {
    inner: std::collections::BTreeMap<N, std::collections::BTreeSet<T>>,
    nullable: &'nullable super::Nullable<N>,
}

impl<'nullable, T: super::TerminalSymbol, N: super::NonTerminalSymbol> First<'nullable, T, N> {
    pub fn new(grammar: &super::Grammar<T, N>, nullable: &'nullable super::Nullable<N>) -> Self {
        let mut inner = std::collections::BTreeMap::<_, std::collections::BTreeSet<_>>::new();
        // 処理中のシンボルのキュー
        let mut symbols = std::collections::VecDeque::from_iter(grammar.nonterminals());
        let lookup = grammar.reverse_lookup();

        while let Some(nonterminal) = symbols.pop_front() {
            grammar.rules_for(&nonterminal).for_each(|rule| {
                for symbol in &rule.derivation {
                    let inserted = match symbol {
                        super::Symbol::Terminal(t) => {
                            inner.entry(nonterminal).or_default().insert(*t)
                        }
                        super::Symbol::NonTerminal(nt) => {
                            if let Some(rhs_first) = inner.get(nt).cloned() {
                                let ptr = inner.entry(nonterminal).or_default();
                                rhs_first
                                    .iter()
                                    .map(|t| ptr.insert(*t))
                                    .reduce(|inserted_any, inserted| inserted_any || inserted)
                                    .unwrap_or(false)
                            } else {
                                false
                            }
                        }
                        super::Symbol::Eof => false,
                    };
                    if inserted && let Some(set) = lookup.get(&nonterminal) {
                        set.iter().for_each(|n| {
                            if !symbols.contains(n) {
                                symbols.push_back(*n);
                            }
                        });
                    }
                    if !nullable.nullable(*symbol) {
                        break;
                    }
                }
            });
        }

        Self { inner, nullable }
    }

    pub fn first(
        &self,
        symbols: impl Iterator<Item = super::Symbol<T, N>>,
    ) -> std::collections::BTreeSet<super::LexicalToken<T>> {
        let mut first = std::collections::BTreeSet::new();
        for symbol in symbols {
            match symbol {
                super::Symbol::Terminal(t) => {
                    first.insert(super::LexicalToken::Terminal(t));
                    break;
                }
                super::Symbol::NonTerminal(nt) => {
                    if let Some(set) = self.inner.get(&nt) {
                        first.extend(set.iter().map(|&t| super::LexicalToken::Terminal(t)));
                    }
                    if !self.nullable.nullable(symbol) {
                        break;
                    }
                }
                super::Symbol::Eof => {
                    first.insert(super::LexicalToken::Eof);
                }
            };
        }
        first
    }
}

closureの実装

LR(1)構文解析のclosureのアイテムは、LR(0)のclosureのものに加えて先読みの文字の情報を持つ必要があります。すなわち、文法規則A = B Cに対し、次にどのような文字が来たらその規則で還元するのかという情報を付け加えます。これを

A = B C . , { a b }

のように表すことにします。これは「次にaかbが来る場合のみ、文法規則A = B Cで還元する」ということを表します。

以下の文法を例に用います。

S  = 
S  = X S Y
X = "x"
Y = "y"

nullable、FIRST集合は以下の通りです。

nullable(S) = true
nullable(X) = nullable(Y) = false
FIRST(S) = { "x" }
FIRST(X) = { "x" }
FIRST(Y) = { "y" }

状態0の出発点は

S = . X S Y , { $ }
S = . , { $ }

です。LR(0)であれば続いてX = . "x"というアイテムを追加していましたが、ここでは先読みも考慮する必要があります。X = . "x"に対応する先読みは、Xの後に続くトークン列のFIRST集合です。この場合（S = . X S Y , { $ }）はXの後にnullableなS、その次にnullableでないYが来るのでFIRST(SY) = FIRST(S) + FIRST(Y) = { "x", "y" }です。

状態0
S = . X S Y , { $ }
S = . , { $ }
X = . "x" , { "x" "y" }

まずはここまでを実装に落とし込みます。といっても案外難しくありません。LR(0)ではclosureはBTreeSet<ClosureItem>で表しましたが、BTreeSet<ClosureItem>は実質BTreeMap<ClosureItem, ()>のようなものです。()の部分を先読み集合に置き換えればOKです。すなわち、S = . X S Yなどの部分をキーとし、{ $ }などの部分をバリューとするmapをclosureのアイテムとすれば表現できます。

src/lr1/mod.rs
pub(crate) mod closure;
src/lr1/closure.rs
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct ClosureItemKey<
    'grammar,
    T: crate::grammar::TerminalSymbol,
    N: crate::grammar::NonTerminalSymbol,
> {
    rule: &'grammar crate::grammar::Rule<T, N>,
    /// 何個目のシンボルまで読んだか
    pos: usize,
}

impl<'grammar, T: crate::grammar::TerminalSymbol, N: crate::grammar::NonTerminalSymbol>
    ClosureItemKey<'grammar, T, N>
{
    fn new(rule: &'grammar crate::grammar::Rule<T, N>) -> Self {
        Self { rule, pos: 0 }
    }

    fn consumed(&self) -> &[crate::grammar::Symbol<T, N>] {
        &self.rule.derivation[..self.pos]
    }

    fn remaining(&self) -> &[crate::grammar::Symbol<T, N>] {
        &self.rule.derivation[self.pos..]
    }
}

pub type Lookaheads<T> = std::collections::BTreeSet<crate::grammar::LexicalToken<T>>;

pub type ClosureItems<'grammar, T, N> =
    std::collections::BTreeMap<ClosureItemKey<'grammar, T, N>, Lookaheads<T>>;

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Closure<
    'grammar,
    T: crate::grammar::TerminalSymbol,
    N: crate::grammar::NonTerminalSymbol,
> {
    pub items: ClosureItems<'grammar, T, N>,
}

Closure::new()関数はLR(0)の時と同様、変化がなくなるまでループさせて計算します。

src/lr1/closure.rs
// 中略

impl<
    'grammar,
    T: crate::grammar::TerminalSymbol<NonTerminal = N>,
    N: crate::grammar::NonTerminalSymbol<Terminal = T>,
> Closure<'grammar, T, N>
{
    pub fn new(
        kernel: ClosureItems<'grammar, T, N>,
        grammar: &'grammar crate::grammar::Grammar<T, N>,
        first: &'grammar crate::grammar::First<T, N>,
    ) -> Self {
        let mut items = kernel;

        loop {
            // 新たに生まれるアイテムを追加し、変化があったか
            let changed = new_items(&items, grammar, first)
                .into_iter()
                .map(|(key, lookaheads)| {
                    let ptr = items.entry(key).or_default();
                    if lookaheads.is_subset(ptr) {
                        false
                    } else {
                        ptr.extend(lookaheads);
                        true
                    }
                })
                .reduce(|changed, inserted| changed || inserted)
                .unwrap_or(false);

            // 変化がなければループ終了
            if !changed {
                break;
            }
        }

        Self { items }
    }
}

/// 既存のアイテムから新たに生まれるアイテムの集合を返す
fn new_items<'grammar, T: crate::grammar::TerminalSymbol, N: crate::grammar::NonTerminalSymbol>(
    items: &ClosureItems<'grammar, T, N>,
    grammar: &'grammar crate::grammar::Grammar<T, N>,
    first: &'grammar crate::grammar::First<T, N>,
) -> ClosureItems<'grammar, T, N> {
    items
        .iter()
        .filter_map(
            |(key, lookaheads)| match key.remaining().split_at_checked(1) {
                // まだ読んでいないシンボルがあり、その1つ目が非終端記号の場合だけを拾う
                Some(([crate::grammar::Symbol::NonTerminal(nt)], rest)) => {
                    let entries = grammar.rules_for(nt).map(|rule| {
                        let new_key = ClosureItemKey::new(rule);
                        let new_lookaheads = lookaheads
                            .iter()
                            .flat_map(|la| {
                                first.first(
                                    rest.iter()
                                        .copied()
                                        .chain(std::iter::once(crate::grammar::Symbol::from(*la))),
                                )
                            })
                            .collect::<std::collections::BTreeSet<_>>();
                        (new_key, new_lookaheads)
                    });
                    Some(entries)
                }
                _ => None,
            },
        )
        .flatten()
        .fold(Default::default(), |mut map, (key, lookaheads)| {
            map.entry(key).or_default().extend(lookaheads);
            map
        })
}

さて、closureを作る方法がわかったので、closureから遷移先のclosureを作っていきます。

状態0（再掲）
S = . X S Y , { $ }
S = . , { $ }
X = . "x" , { "x" "y" }

LR(0)では、例えばここからXを読んだら

S = X . S Y

という状態に移り、.の右側に非終端記号があるのを展開して

S = X . S Y
S = . X S Y
S = .
X = . "x"

のような状態を作っていました。LR(1)では先読みがありますが、これはただ単に同じものをクローンすればOKです。すなわち

S = X . S Y , { $ }

という不完全な状態をまず作り、.の右側に非終端記号があるのを上述のアルゴリズムで展開します。
これを踏まえ、LR(0)の時と同様Closureに便利関数を定義しておきます。

/// 初期状態となるClosureを生成する
pub fn entry_point(
    first: &'grammar crate::grammar::First<T, N>,
    grammar: &'grammar crate::grammar::Grammar<T, N>,
) -> Self {
    let kernel = grammar
        .entry_points()
        .map(|rule| {
            let key = ClosureItemKey::new(rule);
            let value = std::collections::BTreeSet::from([crate::grammar::LexicalToken::Eof]);
            (key, value)
        })
        .collect();
    Closure::new(kernel, grammar, first)
}

// `.`の直後に来るシンボルをキーとし、遷移先のアイテムの集合を値とするマップを返す
pub fn next(
    &self,
) -> std::collections::BTreeMap<crate::grammar::Symbol<T, N>, ClosureItems<'grammar, T, N>>
{
    self.items
        .iter()
        .filter_map(|(key, lookahead)| match key.remaining().first() {
            Some(next_symbol) => {
                let new_key = ClosureItemKey {
                    rule: key.rule,
                    pos: key.pos + 1,
                };
                Some((*next_symbol, (new_key, lookahead.clone())))
            }
            _ => None,
        })
        .fold(
            std::collections::BTreeMap::new(),
            |mut map, (symbol, (key, lookaheads))| {
                map.entry(symbol).or_default().insert(key, lookaheads);
                map
            },
        )
}

/// 次にどの終端記号が来たらどの導出規則で還元できるか、を列挙する
pub fn reduce(
    &self,
    grammar: &crate::grammar::Grammar<T, N>,
) -> impl Iterator<
    Item = (
        &std::collections::BTreeSet<crate::grammar::LexicalToken<T>>,
        usize,
    ),
> {
    self.items
        .iter()
        .filter(|(key, _)| key.remaining().is_empty())
        .map(|(key, lookaheads)| {
            let rule_idx = grammar
                .iter()
                .position(|rule| {
                    key.rule.variable == rule.variable && key.consumed() == rule.derivation
                })
                .unwrap();
            (lookaheads, rule_idx)
        })
}

続いて解析表を作ります。終端記号を読んだ時のアクションはShift/Reduce/Accpetのいずれかなので、これをenumで表します。

src/lr1/mod.rs
pub mod parse_table; // 追加
src/lr1/parse_table.rs
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
#[repr(transparent)]
pub struct ClosureIndex(usize);

impl ClosureIndex {
    pub fn new(idx: usize) -> Self {
        Self(idx)
    }

    pub fn as_usize(self) -> usize {
        self.0
    }
}

impl<'grammar, T: crate::grammar::TerminalSymbol, N: crate::grammar::NonTerminalSymbol>
    std::ops::Index<ClosureIndex> for Vec<super::closure::Closure<'grammar, T, N>>
{
    type Output = super::closure::Closure<'grammar, T, N>;

    fn index(&self, index: ClosureIndex) -> &Self::Output {
        &self[index.as_usize()]
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Action<'grammar, T: crate::grammar::TerminalSymbol, N: crate::grammar::NonTerminalSymbol> {
    Shift(ClosureIndex),
    Reduce(&'grammar crate::grammar::Rule<T, N>),
    Accept,
}

#[derive(Debug)]
pub struct ParseTableError<
    'grammar,
    T: crate::grammar::TerminalSymbol,
    N: crate::grammar::NonTerminalSymbol,
> {
    pub state: super::closure::Closure<'grammar, T, N>,
    pub trace: Vec<crate::grammar::Symbol<T, N>>,
    pub action1: Action<'grammar, T, N>,
    pub action2: Action<'grammar, T, N>,
}

これを用いて、解析表は次のように表現します。

src/lr1/parse_table.rs
// 中略
#[derive(Debug)]
pub struct ParseTable<
    'grammar,
    T: crate::grammar::TerminalSymbol,
    N: crate::grammar::NonTerminalSymbol,
> {
    pub states: Vec<super::closure::Closure<'grammar, T, N>>,
    pub actions: std::collections::BTreeMap<
        (ClosureIndex, crate::grammar::LexicalToken<T>),
        Action<'grammar, T, N>,
    >,
    pub goto: std::collections::BTreeMap<(ClosureIndex, N), ClosureIndex>,
}

これからParseTable::new関数を実装しますが、基本的な流れはLR(0)と同じで、

  1. Closureを生成しながらShiftとGotoを計算する
  2. Reduceを計算し、衝突がないかチェックする
  3. Acceptを計算する

という流れに沿っています。衝突があったときのエラー生成はやや長くなるので、一部を別の関数に切り出しています。

src/lr1/parse_table.rs
// 中略

impl<
    'grammar,
    T: crate::grammar::TerminalSymbol<NonTerminal = N>,
    N: crate::grammar::NonTerminalSymbol<Terminal = T>,
> ParseTable<'grammar, T, N>
{
    pub fn new(
        grammar: &'grammar crate::grammar::Grammar<T, N>,
        first: &'grammar crate::grammar::First<T, N>,
    ) -> Result<Self, ParseTableError<'grammar, T, N>> {
        let cls0 = super::closure::Closure::entry_point(first, grammar);
        let mut states = vec![cls0];
        let mut goto = std::collections::BTreeMap::new();
        let mut actions = std::collections::BTreeMap::new();

        // Closureを生成しながらShiftとGotoを計算する
        for cls_from_idx in 0.. {
            // 遷移元のClosure
            let Some(cls_from) = states.get(cls_from_idx) else {
                break;
            };
            cls_from
                .next()
                .into_iter()
                .for_each(|(symbol, new_kernel)| {
                    // 遷移先のClosure
                    let new_cls = super::closure::Closure::new(new_kernel, grammar, first);
                    // 遷移先のClosureが何番目か
                    let new_cls_idx =
                        states
                            .iter()
                            .position(|c| c == &new_cls)
                            .unwrap_or_else(|| {
                                states.push(new_cls);
                                states.len() - 1
                            });

                    match symbol {
                        crate::grammar::Symbol::NonTerminal(nt) => {
                            goto.insert(
                                (ClosureIndex(cls_from_idx), nt),
                                ClosureIndex(new_cls_idx),
                            );
                        }
                        crate::grammar::Symbol::Terminal(t) => {
                            actions.insert(
                                (
                                    ClosureIndex(cls_from_idx),
                                    crate::grammar::LexicalToken::Terminal(t),
                                ),
                                Action::Shift(ClosureIndex(new_cls_idx)),
                            );
                        }
                        // EOFはLookaheadでしか登場しない
                        crate::grammar::Symbol::Eof => unreachable!(),
                    }
                });
        }

        // reduceを計算する
        for (state_idx, c) in states.iter().enumerate() {
            let state_idx = ClosureIndex(state_idx);
            for (lookaheads, rule) in c.reduce(grammar) {
                for lookahead in lookaheads {
                    if let Some(another_action) =
                        actions.insert((state_idx, *lookahead), Action::Reduce(rule))
                    {
                        let trace = get_trace(state_idx, &actions, &goto, *lookahead);
                        return Err(ParseTableError {
                            state: c.clone(),
                            trace,
                            action1: another_action,
                            action2: Action::Reduce(rule),
                        });
                    }
                }
            }
        }

        // acceptを計算する
        let acc_state = goto
            .get(&(ClosureIndex(0), grammar.start_symbol()))
            .copied()
            .unwrap_or_else(|| {
                let acc_cls = super::closure::Closure::new(
                    // 入力の終端を読んでAcceptするだけのclosureなので中身は適当で良い
                    Default::default(),
                    grammar,
                    first,
                );
                let acc_cls_idx = ClosureIndex(states.len());
                states.push(acc_cls);
                goto.insert((ClosureIndex(0), grammar.start_symbol()), acc_cls_idx);
                acc_cls_idx
            });
        actions.insert(
            (acc_state, crate::grammar::LexicalToken::Eof),
            Action::Accept,
        );

        Ok(Self {
            states,
            actions,
            goto,
        })
    }
}

/// 初期状態から第一引数の状態に至るまでのシンボル列の例を返す
fn get_trace<'grammar, T: crate::grammar::TerminalSymbol, N: crate::grammar::NonTerminalSymbol>(
    state_idx: ClosureIndex,
    actions: &std::collections::BTreeMap<
        (ClosureIndex, crate::grammar::LexicalToken<T>),
        Action<'grammar, T, N>,
    >,
    goto: &std::collections::BTreeMap<(ClosureIndex, N), ClosureIndex>,
    lookahead: crate::grammar::LexicalToken<T>,
) -> Vec<crate::grammar::Symbol<T, N>> {
    let mut trace =
        std::collections::VecDeque::from([crate::grammar::Symbol::<T, N>::from(lookahead)]);
    let mut state = state_idx;
    while state != ClosureIndex(0) {
        let (prev_state_idx, prev_symbol) = actions
            .iter()
            .find_map(|((prev_state_idx, token), action)| match action {
                Action::Shift(s) if s == &state => {
                    Some((*prev_state_idx, crate::grammar::Symbol::from(*token)))
                }
                _ => None,
            })
            .or_else(|| {
                goto.iter().find_map(|((prev_state_idx, token), dst)| {
                    if *dst == state {
                        Some((*prev_state_idx, crate::grammar::Symbol::NonTerminal(*token)))
                    } else {
                        None
                    }
                })
            })
            .unwrap();
        trace.push_front(prev_symbol);
        state = prev_state_idx;
    }

    Vec::from(trace)
}

この解析表を使って入力をパースする関数を書きます。難しいことはないのでいきなり実装をお見せします。

src/lr1/parse_table.rs
// ParseTableに以下のメソッドを追加で実装
pub fn action(
    &self,
    state: ClosureIndex,
    token: crate::grammar::LexicalToken<T>,
) -> Option<Action<'grammar, T, N>> {
    self.actions.get(&(state, token)).copied()
}

pub fn goto(&self, state: ClosureIndex, nonterminal: N) -> Option<ClosureIndex> {
    self.goto.get(&(state, nonterminal)).copied()
}
src/lr1/mod.rs
pub mod parser; // 追加
src/lr1/parser.rs
#[derive(Debug)]
pub struct Node<T: crate::grammar::TerminalSymbol, N: crate::grammar::NonTerminalSymbol> {
    pub ty: crate::grammar::Symbol<T, N>,
    pub children: Option<Vec<Node<T, N>>>,
}

pub trait AsTerminal<T: crate::grammar::TerminalSymbol> {
    fn as_terminal(&self) -> T;
}

pub fn parse<
    T: crate::grammar::TerminalSymbol<NonTerminal = N> + std::fmt::Display + std::fmt::Debug,
    N: crate::grammar::NonTerminalSymbol<Terminal = T> + std::fmt::Display + std::fmt::Debug,
>(
    mut input: &[impl AsTerminal<T>],
    parse_table: &super::parse_table::ParseTable<T, N>,
) -> Result<Node<T, N>, String> {
    let mut stack = Vec::<(Node<T, N>, super::parse_table::ClosureIndex)>::new();

    loop {
        // スタックトップの状態
        let current_state = stack
            .last()
            .map_or(super::parse_table::ClosureIndex::new(0), |(_, state)| {
                *state
            });

        // 次に読むトークン
        let next_token = input
            .first()
            .map(|t| crate::grammar::LexicalToken::Terminal(t.as_terminal()))
            .unwrap_or(crate::grammar::LexicalToken::Eof);

        // 解析表からアクションを取得
        let action = parse_table
            .action(current_state, next_token)
            .ok_or_else(|| {
                format!(
                    "No action found for state {current_state} {} and token {next_token}",
                    parse_table.states[current_state]
                )
            })?;

        match action {
            super::parse_table::Action::Accept => {
                assert!(
                    stack.len() == 1,
                    "parse stack should contain exactly one node, found {stack:?}",
                );
                return Ok(stack.pop().unwrap().0);
            }
            super::parse_table::Action::Reduce(rule) => {
                let children = stack
                    .drain(stack.len() - rule.derivation.len()..)
                    .map(|(node, _)| node)
                    .collect::<Vec<_>>();

                let node = Node {
                    ty: rule.variable.into_symbol(),
                    children: Some(children),
                };
                let state = stack
                    .last()
                    .map(|(_, s)| *s)
                    .unwrap_or(super::parse_table::ClosureIndex::new(0));
                let new_state = parse_table.goto(state, rule.variable).ok_or_else(|| {
                    format!("unexpected variable: {} at state {state}", rule.variable)
                })?;
                stack.push((node, new_state));
            }
            super::parse_table::Action::Shift(s) => {
                let node = Node {
                    ty: next_token.into(),
                    children: None,
                };
                stack.push((node, s));
                input = &input[1..];
            }
        }
    }
}

お疲れ様でした。これでLR(1)パーサーの完成です。

実際に使ってみる

json.orgのWebサイトにはJSONの構文定義が載っています。これをLR(1)解析表にして実際に何かをパースしてみましょう。
ただし、そのままだとちょっと扱いづらいので、文字列リテラルはそれで一つの終端記号ということにします。
まず、構文定義を楽にするマクロを定義します。

src/grammar/mod.rs
// 中略

/// Macro to define a grammar.
/// Each rule must be of the form `A = B1 | B2 | ... | Bn`.
/// The LHS of the first line becomes the start symbol of the grammar.
#[macro_export]
macro_rules! grammar {
    (
        $start_symbol:ident = $(
            $($start_derivation:ident)*
        )|+
    ) => {
        {
            use $crate::grammar::{NonTerminalSymbol, TerminalSymbol};
            let derivations = vec![
                $(
                    $crate::grammar::Rule {
                        variable: $start_symbol,
                        derivation: vec![$($start_derivation.into_symbol()),*]
                    }
                ),+
            ];
            $crate::grammar::Grammar::new($start_symbol, derivations)
        }
    };
    (
        $start_symbol:ident = $(
            $($start_derivation:ident)*
        )|+,
        $(
            $variable:ident = $(
                $($derivation:ident)*
            )|+
        ),*
        $(,)?
    ) => {
        {
            use $crate::grammar::{NonTerminalSymbol, TerminalSymbol};
            let derivations = vec![
                $(
                    $crate::grammar::Rule {
                        variable: $start_symbol,
                        derivation: vec![$($start_derivation.into_symbol()),*]
                    }
                ),+,
                $($(
                    $crate::grammar::Rule {
                        variable: $variable,
                        derivation: vec![$($derivation.into_symbol()),*]
                    }
                ),+),*
            ];
            $crate::grammar::Grammar::new($start_symbol, derivations)
        }
    }
}

lexerも含めた簡易実装を示します。エラーハンドリングはかなり適当です。

examples/json.rs
fn main() {
    use NonTerminalTokenImpl::*;
    use TerminalTokenImpl::*;

    let rules = lrs::grammar!(
        Json = Element,
        Value = Object | Array | String | Number | TrueLit | FalseLit | NullLit,
        Object = BraceOpen Whitespace BraceClose | BraceOpen Members BraceClose,
        Members = Member | Member Comma Members,
        Member = Whitespace String Whitespace Colon Element,
        Array = BracketOpen Whitespace BracketClose | BracketOpen Elements BracketClose,
        Elements = Element | Element Comma Elements,
        Element = Whitespace Value Whitespace,
        String = Quote Chars Quote,
        Number = Integer Fraction Exponent,
        Integer = Digit | OneNine Digits | Minus Digit | Minus OneNine Digits,
        Digits = Digit | Digit Digits,
        Digit = Zero | OneNine,
        Fraction = | Dot Digits,
        Exponent = | CapitalE Sign Digits | SmallE Sign Digits,
        Sign = | Plus | Minus,
        Whitespace = | U0020 Whitespace | U000A Whitespace | U000D Whitespace | U0009 Whitespace
    );

    let nullable = lrs::grammar::Nullable::new(&rules);
    let first = lrs::grammar::First::new(&rules, &nullable);
    let parse_table = lrs::lr1::parse_table::ParseTable::new(&rules, &first).unwrap();

    let input = r#"{"key": "value", "array": [1, 2, 3]}"#;
    let tokens = lexer(input);
    let result = lrs::lr1::parser::parse(&tokens, &parse_table).unwrap();
    println!("{result:?}");
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
enum NonTerminalTokenImpl {
    Json,
    Value,
    Object,
    Members,
    Member,
    Array,
    Elements,
    Element,
    Whitespace,
    String,
    Number,
    Integer,
    Fraction,
    Exponent,
    Digits,
    Digit,
    Sign,
}

impl lrs::grammar::NonTerminalSymbol for NonTerminalTokenImpl {
    type Terminal = TerminalTokenImpl;
    fn into_symbol(self) -> lrs::grammar::Symbol<Self::Terminal, Self> {
        lrs::grammar::Symbol::NonTerminal(self)
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
enum TerminalTokenImpl {
    BraceOpen,
    BraceClose,
    BracketOpen,
    BracketClose,
    Colon,
    Comma,
    Quote,
    U0020,
    U000A, // \n
    U000D, // \r
    U0009, // \t
    TrueLit,
    FalseLit,
    NullLit,
    Minus,
    Zero,
    OneNine,
    Dot,
    CapitalE,
    SmallE,
    Plus,
    Chars,
}

impl lrs::grammar::TerminalSymbol for TerminalTokenImpl {
    type NonTerminal = NonTerminalTokenImpl;
    fn into_symbol(self) -> lrs::grammar::Symbol<Self, NonTerminalTokenImpl> {
        lrs::grammar::Symbol::Terminal(self)
    }
}

#[derive(Debug)]
struct Word {
    pos: std::ops::Range<usize>,
    ty: TerminalTokenImpl,
}

impl lrs::lr1::parser::AsTerminal<TerminalTokenImpl> for Word {
    fn as_terminal(&self) -> TerminalTokenImpl {
        self.ty
    }
}

fn lexer(input: &str) -> Vec<Word> {
    let mut words = Vec::new();
    let mut start = 0;
    while let Some(c) = input[start..].chars().next() {
        let ty = match c {
            '{' => TerminalTokenImpl::BraceOpen,
            '}' => TerminalTokenImpl::BraceClose,
            '[' => TerminalTokenImpl::BracketOpen,
            ']' => TerminalTokenImpl::BracketClose,
            ':' => TerminalTokenImpl::Colon,
            ',' => TerminalTokenImpl::Comma,
            '"' => TerminalTokenImpl::Quote,
            ' ' => TerminalTokenImpl::U0020,
            '\n' => TerminalTokenImpl::U000A,
            '\r' => TerminalTokenImpl::U000D,
            '\t' => TerminalTokenImpl::U0009,
            '-' => TerminalTokenImpl::Minus,
            '0' => TerminalTokenImpl::Zero,
            '1'..='9' => TerminalTokenImpl::OneNine,
            '.' => TerminalTokenImpl::Dot,
            'E' => TerminalTokenImpl::CapitalE,
            'e' => TerminalTokenImpl::SmallE,
            '+' => TerminalTokenImpl::Plus,
            _ if input[start..].starts_with("true") => TerminalTokenImpl::TrueLit,
            _ if input[start..].starts_with("false") => TerminalTokenImpl::FalseLit,
            _ if input[start..].starts_with("null") => TerminalTokenImpl::NullLit,
            _ => unreachable!(),
        };
        let len = match ty {
            TerminalTokenImpl::TrueLit => 4,
            TerminalTokenImpl::FalseLit => 5,
            TerminalTokenImpl::NullLit => 4,
            _ => 1,
        };
        let start_string = matches!(ty, TerminalTokenImpl::Quote);
        words.push(Word {
            pos: start..start + len,
            ty,
        });
        start += len;
        if start_string {
            let mut len = 0;
            let mut chars = input[start..].chars();
            while let Some(c) = chars.next() {
                match c {
                    '"' => {
                        let end = start + len;
                        words.push(Word {
                            pos: start..end,
                            ty: TerminalTokenImpl::Chars,
                        });
                        start = end;
                        words.push(Word {
                            pos: start..start + 1,
                            ty: TerminalTokenImpl::Quote,
                        });
                        start += 1;
                        break;
                    }
                    '\\' => match chars.next() {
                        Some('"' | '\\' | '/' | 'b' | 'f' | 'n' | 'r' | 't') => len += 2,
                        Some('u') => {
                            for _ in 0..4 {
                                match chars.next() {
                                    Some(c) if c.is_ascii_hexdigit() => {}
                                    _ => panic!("Invalid unicode escape sequence"),
                                }
                            }
                            len += 6;
                        }
                        _ => panic!("Invalid escape sequence"),
                    },
                    ..' ' => panic!("Unexpected control character: {:x}", c as u16),
                    _ => len += c.len_utf8(),
                }
            }
        }
    }
    words
}

ここまで省略してきましたが、各種構造体にDisplayトレイトを実装するとより結果が見やすくなります。余力があれば試してみてください。

また、LR(1)解析表をもとにLALR解析表を作ることもできます。こちらは読者への課題とします。

最後に

長いことお付き合いいただきありがとうございました。これであなたも正々堂々「私、構文解析できます」と言えますね。

Discussion