はじめに

これは構文解析手法に関するまとめの第2回です.
用語や記号、関数などは第1回の導入編を参照してください.

一応簡単な正常系を使って動くことだけは確認していますが、重大な誤りを含むコードを掲載している可能性はあります. ご注意ください.

再帰降下法 (recursive descent parsing) の例

構文解析の最も初歩的なアルゴリズムとして、再帰降下法というものが知られている. まずはここから始めることとしよう.

例として、次の文法を用いる. 開始記号は $E$ である.

\text{文法}\ G = \left\{\begin{align*}
  E  & \rightarrow T      \ E'     \\
  E' & \rightarrow {+}    \ T \ E' \\
  E' & \rightarrow \epsilon        \\
  T  & \rightarrow F      \ T'     \\
  T' & \rightarrow \times \ F \ T' \\
  T' & \rightarrow \epsilon        \\
  F  & \rightarrow (      \ E \ )  \\
  F  & \rightarrow a \\
\end{align*}\right\}

$L(G)$ は $a,\ a+a,\ a \times a,\ (a+a) \times (a \times (a + a))$ などを含む.

アルゴリズムのイメージ

文 $a \times a$ を再帰降下法によって解析するとは次のようなことである.

再帰降下法のイメージ

1.
文全体が開始記号 E から導出されると仮定する.
すると、適用されるべき規則は E → T E' である.
文の先頭からいくつかの記号は T に還元されることが期待される.
E
┣━┓
T E'
? ? ?
a x a

1-1.
文の先頭からいくつかの記号は T から導出されると仮定する.
すると、適用されるべき規則は T → F T' である.
文の先頭からいくつかの記号は F に還元されることが期待される.
E
┣━━━━━┓
T     E'
┣━┓   ?
F T'
? ? ?
a x a

1-1-1.
文の先頭からいくつかの記号は F から導出されると仮定する.
すると、適用されるべき規則は F → (E) または F → a である.
文の先頭の記号を見ると a であった.
つまり、実際には F → a が適用されたと考えるべきだろう.
実際に F へと還元する.
E
┣━━━━━┓
T     E'
┣━┓   ?
F T'
┃ ? ?
a x a

1-2.
文の先頭からいくつかの記号は T から導出されると考えて、適用されるべき規則は T → F T' であるとしていた.
実際に F は還元できた.
文の残り部分について先頭からいくつかの記号は T' に還元されることが期待される.

1-2-1.
文の残り部分について先頭からいくつかの記号は T' から導出されると仮定する.
すると、適用されるべき規則は T' → x F T' または T' → ε である.
文の残り部分について先頭の記号を見ると x であった.
つまり、実際には T' → x F T' が適用されたと考えるべきだろう.

E
┣━━━━━┓
T     E'
┣━┓   ?
F T'
┃ ┣━┳━┓
┃ ┃ F T'
┃ ┃ ? ?
a x a

長いので後半は折りたたみ

再帰降下法のイメージ

1-2-2.
文の残り部分について先頭からいくつかの記号は T' から導出されると考えて、適用されるべき規則は T' → x F T' であるとしていた.
実際に x までは一致していた.
文の残り部分について先頭からいくつかの記号は F に還元されることが期待される.

1-2-2-1.
文の先頭からいくつかの記号は F から導出されると仮定する.
すると、適用されるべき規則は F → (E) または F → a である.
文の先頭の記号を見ると a であった.
つまり、実際には F → a が適用されたと考えるべきだろう.
実際に F へと還元する.

E
┣━━━━━┓
T     E'
┣━┓   ?
F T'
┃ ┣━┳━┓
┃ ┃ F T'
┃ ┃ ┃ ?
a x a

1-2-3.
文の残り部分について先頭からいくつかの記号は T' から導出されると考えて、適用されるべき規則は T' → x F T' であるとしていた.
実際に x F までは一致していた.
文の残り部分について先頭からいくつかの記号は T' に還元されることが期待される.

1-2-3-1.
文の残り部分について先頭からいくつかの記号は T' から導出されると仮定する.
すると、適用されるべき規則は T' → x F T' または T' → ε である.
文の残り部分について先頭の記号を見ようとすると、もはや文の末尾であった.
つまり、実際には T' → ε が適用されたと考えるべきだろう.
実際に T' へと還元する.

E
┣━━━━━┓
T     E'
┣━┓   ?
F T'
┃ ┣━┳━┓
┃ ┃ F T'
┃ ┃ ┃ ┗ ε
a x a

1-2-4.
文の残り部分について先頭からいくつかの記号は T' から導出されると考えて、適用されるべき規則は T' → x F T' であるとしていた.
実際に x F T' まで一致した.
実際に T' へと還元する.

1-3.
文の先頭からいくつかの記号は T から導出されると考えて、適用されるべき規則は T → F T' であるとしていた.
実際に F T' は還元できた.
実際に T へと還元する.

2.
文の先頭からいくつかの記号は E から導出されると考えて、適用されるべき規則は E → T E' であるとしていた.
実際に T は還元できた.
文の残り部分について先頭からいくつかの記号は E' に還元されることが期待される.

2-1.
文の残り部分について先頭からいくつかの記号は E' から導出されると仮定する.
すると、適用されるべき規則は E' → + T E' または E' → ε である.
文の残り部分について先頭の記号を見ようとすると、もはや文の末尾であった.
つまり、実際には T' → ε が適用されたと考えるべきだろう.
実際に E' へと還元する.

E
┣━━━━━┓
T     E'
┣━┓   ┗ ε
F T'
┃ ┣━┳━┓
┃ ┃ F T'
┃ ┃ ┃ ┗ ε
a x a

3.
文の先頭からいくつかの記号は E から導出されると考えて、適用されるべき規則は E → T E' であるとしていた.
実際に T E' は還元できた.
実際に E へと還元する.

4.
文全体が E から導出できることが示せた. □

E
┣━━━━━┓
T     E'
┣━┓   ┗ ε
F T'
┃ ┣━┳━┓
┃ ┃ F T'
┃ ┃ ┃ ┗ ε
a x a

このように開始記号から出発して、与えられた文を導出できるか調べる手法を下向き構文解析 (top-down parsing) と呼ぶ.

再帰降下法は、各非終端記号に対応する手続きを用意し、その中で入力の先頭を確認しながら適切な生成規則を選んで再帰的に呼び出していく手法である.
このとき、選択する生成規則は、次に読むべき入力記号を先読みすることによって一意に決められるようになっていなければならない.

文法がこの条件(後述する LL(k) 文法であること)を満たしていることが保証されているならば、再帰降下法は理解しやすく実装も簡単である. それゆえ、教育的な題材や小規模な言語処理系の実装によく使われる印象だ.

構文解析をよく学んだ人ならば、例に挙げた数式の文法は見飽きているし、再帰降下法のコードも諳で書けることだろう.

再帰降下法のコード例

再帰降下法のコーディングは、ほとんど文法そのままに書き綴っていくことで完了する.

非終端記号の数だけ関数を書く.
input.len() <= *position であるとき、$A \rightarrow \epsilon$ があれば空のノードを、そうでなければ Err を返す.
非終端記号 $A$ がひとつの規則 $A \rightarrow \alpha$ だけを持つならば、$\alpha$ 部分に対応する関数を順に呼び出していく.
非終端記号 $A$ が複数の規則を持つならば、先読みによって規則を選択する.
終端記号を読んだ場合は入力を消費する. (*position += 1)

コードを見てもらえれば、文法との対応、ならびにアルゴリズムの簡潔さが分かってもらえることと思う.

今回は入力を Vec とし、*position += 1 で消費していったが、入力を VecDeque にして input.pop_front() で消費することもできる. 大きな入力をストリームで処理する場合は後者のスタイルがより自然だろう. (実用的には、入力としてトークン列ではなくレキサ(トークンを返すイテレータ)を使う方が自然である)

recursive_descent.rs

use crate::{tree::Tree, util::{Nonterminal, ParseNode, Token}};

pub fn parse_expr(input: &Vec<Token<&'static str>>) -> Result<Tree<ParseNode<&'static str>>, String> {
  let mut position = 0;
  let tree = expr(input, &mut position)?;
  if position != input.len() {
    Err(format!("入力の長さ {len} に対し、{position} 時点で解析が終わってしまいました", len = input.len()))
  } else {
    Ok(tree)
  }
}

// E  -> T E'
fn expr(input: &Vec<Token<&'static str>>, position: &mut usize) -> Result<Tree<ParseNode<&'static str>>, String> {
  if input.len() <= *position {
    return Err("all of input is consumed.".to_string());
  }
  let t = term(input, position)?;
  let ep = expr_tail(input, position)?;
  Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "E", variant: 0 }), vec![t, ep]))
}

// E' -> + T E'
// E' -> ε
fn expr_tail(input: &Vec<Token<&'static str>>, position: &mut usize) -> Result<Tree<ParseNode<&'static str>>, String> {
  if *position < input.len() && input[*position].kind == "+" {
    // E' -> + T E'
    let add = try_consume(input, position, "+")?;
    let t = term(input, position)?;
    let ep = expr_tail(input, position)?;
    return Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "E", variant: 1 }), vec![add, t, ep]));
  } else {
    // E' -> ε
    return Ok(Tree::new(ParseNode::Reduction(Nonterminal { kind: "E", variant: 1 })));
  }
}
// T  -> F T'
fn term(input: &Vec<Token<&'static str>>, position: &mut usize) -> Result<Tree<ParseNode<&'static str>>, String> {
  if input.len() <= *position {
    return Err("all of input is consumed.".to_string());
  }
  let f = factor(input, position)?;
  let tp = term_tail(input, position)?;
  Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "T", variant: 0 }), vec![f, tp]))
}
// T' -> x F T'
// T' -> ε
fn term_tail(input: &Vec<Token<&'static str>>, position: &mut usize) -> Result<Tree<ParseNode<&'static str>>, String> {
  if *position < input.len() && input[*position].kind == "x" {
    // T' -> x F T'
    let mul = try_consume(input, position, "x")?;
    let f = factor(input, position)?;
    let tp = term_tail(input, position)?;
    return Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "T", variant: 1 }), vec![mul, f, tp]));
  } else {
    // T' -> ε
    return Ok(Tree::new(ParseNode::Reduction(Nonterminal { kind: "T", variant: 1 })));
  }
}
// F  -> ( E )
// F  -> a
fn factor(input: &Vec<Token<&'static str>>, position: &mut usize) -> Result<Tree<ParseNode<&'static str>>, String> {
  if *position < input.len() {
    if input[*position].kind == "(" {
      // F  -> ( E )
      let open = try_consume(input, position, "(")?;
      let e = expr(input, position)?;
      let close = try_consume(input, position, ")")?;
      Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "F", variant: 0 }), vec![open, e, close]))
    } else if input[*position].kind == "a" {
      // F  -> a
      let a = try_consume(input, position, "a")?;
      Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "F", variant: 0 }), vec![a]))
    } else {
      Err(format!("unexpected token: {actual}", actual = input[*position].kind))
    }
  } else {
    Err("all of input is consumed.".to_string())
  }
}

fn try_consume(input: &Vec<Token<&'static str>>, position: &mut usize, expected_token_kind: &'static str) -> Result<Tree<ParseNode<&'static str>>, String> {
  if input.len() <= *position {
    Err("all of input is consumed.".to_string())
  } else if input[*position].kind == expected_token_kind {
    let leaf = Tree::new(ParseNode::Input(input[*position].clone()));
    *position = *position + 1;
    Ok(leaf)
  } else {
    Err(format!("expected {expected_token_kind}, but found {actual}", actual = input[*position].kind))
  }
}

テストコード(簡単な正常系確認)

recursive_descent.rs

#[cfg(test)]
mod tests {
  use super::*;
  use crate::{tok, util::{TextPosition}};

  #[test]
  fn test_simple_mul() {
    let source = vec![
      tok!("a"),
      tok!("x"),
      tok!("a"),
    ];
    let result = parse_expr(&source);
    match result {
      Ok(tree) => {
        // Reduction(Nonterminal { kind: "E", variant: 0 })
        // |`-- Reduction(Nonterminal { kind: "T", variant: 0 })
        // |    |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |    |    `--- Input(Token { kind: "a", ... })
        // |    `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // |         |`-- Input(Token { kind: "x", ... })
        // |         |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |         |    `--- Input(Token { kind: "a", ... })
        // |         `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // `--- Reduction(Nonterminal { kind: "E", variant: 1 })
        // E -> T E'
        assert_eq!(tree.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 0 }));
        assert_eq!(tree.children.len(), 2);
        // T -> F T'
        let et = &tree.children[0];
        assert_eq!(et.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 0 }));
        assert_eq!(et.children.len(), 2);
        // F -> a
        let etf = &et.children[0];
        assert_eq!(etf.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(etf.children.len(), 1);
        // a
        let etfa = &etf.children[0];
        assert_eq!(etfa.label, ParseNode::Input(tok!("a")));
        assert!(etfa.children.is_empty());
        // T -> x F T'
        let ett1 = &et.children[1];
        assert_eq!(ett1.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert_eq!(ett1.children.len(), 3);
        // x
        let ett1x = &ett1.children[0];
        assert_eq!(ett1x.label, ParseNode::Input(tok!("x")));
        assert!(ett1x.children.is_empty());
        // F -> a
        let ett1f = &ett1.children[1];
        assert_eq!(ett1f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(ett1f.children.len(), 1);
        // a
        let ett1fa = &ett1f.children[0];
        assert_eq!(ett1fa.label, ParseNode::Input(tok!("a")));
        assert!(ett1fa.children.is_empty());
        // T' -> ε
        let ett1t1 = &ett1.children[2];
        assert_eq!(ett1t1.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert!(ett1t1.children.is_empty());
        // E' -> ε
        let ee1 = &tree.children[1];
        assert_eq!(ee1.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 1 }));
        assert!(ee1.children.is_empty());
      },
      Err(message) => panic!("パース失敗: {message}"),
    }
  }

  #[test]
  fn test_complex() {
    let source = vec![
      tok!("a"),
      tok!("x"),
      tok!("("),
      tok!("a"),
      tok!("+"),
      tok!("a"),
      tok!(")"),
    ];
    let result = parse_expr(&source);
    match result {
      Ok(tree) => {
        // Reduction(Nonterminal { kind: "E", variant: 0 })
        // |`-- Reduction(Nonterminal { kind: "T", variant: 0 })
        // |    |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |    |    `--- Input(Token { kind: "a", ... })
        // |    `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // |         |`-- Input(Token { kind: "x", ... })
        // |         |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |         |    |`-- Input(Token { kind: "(", ... })
        // |         |    |`-- Reduction(Nonterminal { kind: "E", variant: 0 })
        // |         |    |    |`-- Reduction(Nonterminal { kind: "T", variant: 0 })
        // |         |    |    |    |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |         |    |    |    |    `--- Input(Token { kind: "a", ... })
        // |         |    |    |    `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // |         |    |    `--- Reduction(Nonterminal { kind: "E", variant: 1 })
        // |         |    |         |`-- Input(Token { kind: "+", ... })
        // |         |    |         |`-- Reduction(Nonterminal { kind: "T", variant: 0 })
        // |         |    |         |    |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |         |    |         |    |    `--- Input(Token { kind: "a", ... })
        // |         |    |         |    `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // |         |    |         `--- Reduction(Nonterminal { kind: "E", variant: 1 })
        // |         |    `--- Input(Token { kind: ")", ... })
        // |         `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // `--- Reduction(Nonterminal { kind: "E", variant: 1 })
        // ルート: E -> T E'
        assert_eq!(tree.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 0 }));
        assert_eq!(tree.children.len(), 2);

        let t = &tree.children[0]; // T -> F T'
        let ep = &tree.children[1]; // E' -> ε

        assert_eq!(t.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 0 }));
        assert_eq!(t.children.len(), 2);

        // F -> a
        let f = &t.children[0];
        assert_eq!(f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(f.children.len(), 1);
        assert_eq!(f.children[0].label, ParseNode::Input(tok!("a")));
        assert!(f.children[0].children.is_empty());

        // T' -> x F T'
        let tp = &t.children[1];
        assert_eq!(tp.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert_eq!(tp.children.len(), 3);

        // x
        let tp_x = &tp.children[0];
        assert_eq!(tp_x.label, ParseNode::Input(tok!("x")));
        assert!(tp_x.children.is_empty());

        // F -> ( E )
        let tp_f = &tp.children[1];
        assert_eq!(tp_f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(tp_f.children.len(), 3);

        // '('
        assert_eq!(tp_f.children[0].label, ParseNode::Input(tok!("(")));
        assert!(tp_f.children[0].children.is_empty());

        // E -> T E' (中の a + a)
        let inner_e = &tp_f.children[1];
        assert_eq!(inner_e.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 0 }));
        assert_eq!(inner_e.children.len(), 2);

        let inner_t = &inner_e.children[0];
        let inner_ep = &inner_e.children[1];

        assert_eq!(inner_t.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 0 }));
        assert_eq!(inner_t.children.len(), 2);

        // F -> a
        let inner_f = &inner_t.children[0];
        assert_eq!(inner_f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(inner_f.children.len(), 1);
        assert_eq!(inner_f.children[0].label, ParseNode::Input(tok!("a")));

        // T' -> ε
        let inner_tp = &inner_t.children[1];
        assert_eq!(inner_tp.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert!(inner_tp.children.is_empty());

        // E' -> + T E'
        assert_eq!(inner_ep.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 1 }));
        assert_eq!(inner_ep.children.len(), 3);

        // '+'
        assert_eq!(inner_ep.children[0].label, ParseNode::Input(tok!("+")));
        assert!(inner_ep.children[0].children.is_empty());

        // T -> F T' の F -> a
        let inner_ep_t = &inner_ep.children[1];
        assert_eq!(inner_ep_t.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 0 }));
        assert_eq!(inner_ep_t.children.len(), 2);
        let inner_ep_t_f = &inner_ep_t.children[0];
        assert_eq!(inner_ep_t_f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(inner_ep_t_f.children[0].label, ParseNode::Input(tok!("a")));

        // T' -> ε
        let inner_ep_t_tp = &inner_ep_t.children[1];
        assert_eq!(inner_ep_t_tp.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert!(inner_ep_t_tp.children.is_empty());

        // ')' の確認
        assert_eq!(tp_f.children[2].label, ParseNode::Input(tok!(")")));
        assert!(tp_f.children[2].children.is_empty());

        // T' -> ε
        let tp_tp = &tp.children[2];
        assert_eq!(tp_tp.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert!(tp_tp.children.is_empty());

        // E' -> ε
        assert_eq!(ep.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 1 }));
        assert!(ep.children.is_empty());
      },
      Err(message) => panic!("パース失敗: {message}"),
    }
  }
}

再帰降下法で利用できる文法の条件

FIRST(α)

注意すべき文法

新しく、次の文法を使って再帰降下法を考えてみよう. 開始記号は $\text{PRGM}$ である.

\text{文法}\ G = \left\{\begin{align*}
\text{PRGM}  & \rightarrow \text{STMTS} \\
\text{STMTS} & \rightarrow \text{STMT}\;\> \text{sep} \\
\text{STMTS} & \rightarrow \text{STMT}\;\> \text{sep} \;\> \text{STMTS} \\
\text{STMT}  & \rightarrow \text{DECL}\;\> \text{eq}  \;\> \text{VAL} \\
\text{STMT}  & \rightarrow \text{id}  \;\> \text{eq}  \;\> \text{VAL} \\
\text{DECL}  & \rightarrow \text{MOD} \;\> \text{type}\;\> \text{id} \\
\text{VAL}   & \rightarrow \text{id}  \\
\text{VAL}   & \rightarrow \text{num} \\
\text{MOD}   & \rightarrow \text{mod} \\
\text{MOD}   & \rightarrow \epsilon
\end{align*}\right\}

$L(G)$ に含まれる文の例をいくつか出しておこう.
適宜改行や空白を入れ、MOD として const、type として int、id として適当なアルファベット、num として適当な数字、その他適当な記号を使っている.

L(G) に含まれる文の例

e.g. 1:
const int x = 42;
const int y = 23;

e.g. 2:
foo = 1;
const int bar = baz;
baz = foo;

この文法で表現したい言語は伝わっただろうか. VAL の部分を上で書いた E にすれば、(そして字句解析から意味解析などまで実装すれば、)ちょっとした電卓言語になるだろう.

この文法 $G$ に基づく再帰降下法を実装できるだろうか？
ありそうなものとして、関数 stmt を次のように実装する人があるかもしれない.

recursive_descent_prgm.rs

// STMT -> DECL eq VAL
// STMT -> id eq VAL
fn stmt(input: &Vec<Token<&'static str>>, position: &mut usize) -> Result<Tree<ParseNode<&'static str>>, String> {
  if input.len() <= *position {
    return Err("all of input is consumed.".to_string());
  }
  if input[*position].kind == "mod" {
    // STMT -> DECL eq VAL
    // 先頭が mod ならば STMT -> DECL eq VAL. なぜなら、DECL -> MOD type id であるため
    let decl = decl(input, position)?;
    let eq = try_consume(input, position, "eq")?;
    let val = val(input, position)?;
    Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "STMT", variant: 0 }), vec![decl, eq, val]))
  } else if input[*position].kind == "id" {
    // STMT -> id eq VAL
    let id = try_consume(input, position, "id")?;
    let eq = try_consume(input, position, "eq")?;
    let val = val(input, position)?;
    Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "STMT", variant: 0 }), vec![id, eq, val]))
  } else {
    Err(format!("unexpected token: {actual}", actual = input[*position].kind))
  }
}

これは、規則 $\text{STMT} \rightarrow \text{DECL}\ \text{eq}\ \text{VAL}$ を適用するための条件が間違えている.
MOD は $\epsilon$ になりうるのだった.
つまり、int foo = 97 を受理する必要があり、先読みが mod のときに加えて type のときにも規則 $\text{STMT} \rightarrow \text{DECL}\ \text{eq}\ \text{VAL}$ が適用されなければならない.

考慮すべきだったもの

では、適用する生成規則の分岐条件はどのようにして決定できるのだろうか？
その答えは、一般に FIRST 関数と呼ばれるものにある. これは次のように定義される.

\begin{align*}
  \text{FIRST}(\epsilon) =&\ \{\epsilon\} \\
  \text{FIRST}(a \alpha) =&\ \{ a \} \\
  \text{FIRST}(A \; \alpha) =&\ \begin{cases}
    L(G|_A):1 & \text{if}\ \epsilon \notin L(G|_A):1 \\
    (L(G|_A):1 \setminus \{ \epsilon \}) \cup \text{FIRST}(\alpha) & \text{otherwise}
  \end{cases}
\end{align*}

見ての通り、文法記号列を引数に取り、それを $P$ によって還元したとき先頭にある記号からなる集合である(空列を生成する場合は $\epsilon$ を含む).
この集合は FIRST 集合と呼ばれる.

これを使うと、上の例の stmt 関数の正しい姿を求められる.

$\text{STMT} \rightarrow \text{DECL}\ \text{eq}\ \text{VAL}$ を適用すべき条件について:
これは、input[*position] $\in \text{FIRST}(\text{DECL}\ \text{eq}\ \text{VAL})$ であればよい.
$\text{FIRST}(\text{DECL}\ \text{eq}\ \text{VAL})$ を考えるにはまず $\text{FIRST}(\text{DECL})$ を求める必要がある.
$\text{FIRST}(DECL) = \text{FIRST}(\text{MOD} \ \text{type}\ \text{id})$ である.
$\text{FIRST}(\text{MOD} \ \text{type}\ \text{id})$ を考えるにはまず $\text{FIRST}(\text{MOD})$ を求める必要がある.
$\text{FIRST}(MOD) = \text{FIRST}(\text{mod}) \cup \text{FIRST}(\epsilon) = {\text{mod}, \epsilon}$ である.
$\epsilon \in \text{FIRST}(MOD)$ であるから、$\text{FIRST}(DECL) = \text{FIRST}(\text{MOD}) \cup \text{FIRST}(\text{type}\ \text{id}) = {\text{mod}, \text{type}}$ である.
$\epsilon \notin \text{FIRST}(DECL)$ であるから、$\text{FIRST}(\text{DECL}\ \text{eq}\ \text{VAL}) = \text{FIRST}(\text{DECL}) = {\text{mod}, \text{type}}$ である. $\square$
$\text{STMT} \rightarrow \text{id}\ \text{eq}\ \text{VAL}$ 条件について:
これは、input[*position] $\in \text{FIRST}(\text{id})$ であればよい.
したがって、$\text{FIRST}(\text{id}) = {\text{id}}$ である. $\square$
その他の場合について:
エラーを返せばよい.

丁寧に定義通り手計算していくのは面倒だが、確実に答えが得られる分心強いと考えるべきだろう.

結局、関数 stmt のあるべき姿は以下の形であることが分かった.

recursive_descent_prgm.rs

// STMT -> DECL eq VAL
// STMT -> id eq VAL
fn stmt(input: &Vec<Token<&'static str>>, position: &mut usize) -> Result<Tree<ParseNode<&'static str>>, String> {
  if input.len() <= *position {
    return Err("all of input is consumed.".to_string());
  }
  if input[*position].kind == "mod" || input[*position].kind == "type" {
    // STMT -> DECL eq VAL
    // n.b. FIRST(DECL eq VAL) = { mod, type }
    let decl = decl(input, position)?;
    let eq = try_consume(input, position, "eq")?;
    let val = val(input, position)?;
    Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "STMT", variant: 0 }), vec![decl, eq, val]))
  } else if input[*position].kind == "id" {
    // STMT -> id eq VAL
    // n.b. FIRST(id eq VAL) = { id }
    let id = try_consume(input, position, "id")?;
    let eq = try_consume(input, position, "eq")?;
    let val = val(input, position)?;
    Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "STMT", variant: 0 }), vec![id, eq, val]))
  } else {
    Err(format!("unexpected token: {actual}", actual = input[*position].kind))
  }
}

再帰降下法の限界 - LL(1) 文法の条件①

ここまでに見てきたような、再帰降下法が書ける文法を LL(1) 文法という.
FIRST 関数の定義とその使われ方を見て、再帰降下法が使えない文法の条件がひとつ分かっただろうか.
相異なる規則 $A \rightarrow \alpha$、$A \rightarrow \beta$ があるとき、先読みした記号が $\text{FIRST}(\alpha) \cap \text{FIRST}(\beta)$ に含まれていると、どちらの規則を適用すべきかが判断できなくなってしまうのだ.
つまり、LL(1) 文法であるためにはここで $\text{FIRST}(\alpha) \cap \text{FIRST}(\beta) = \varnothing$ である必要がある.
任意の非終端記号 $A$ について、これが満たされていなければ(ここで紹介している形の)再帰降下法は使えない.

この条件に対する違反を、first/first conflict と言う.

左再帰

問題のある文法

最初の例で挙げた数式文法と同じ言語を表現する、次の文法を考えてみよう. 開始記号は $\text{E}$ である.

\text{文法}\ G = \left\{\begin{align*}
  E & \rightarrow E\ {+}\ T \\
  T & \rightarrow T\ {\times}\ F \\
  F & \rightarrow (\ E\ )  \\
  F & \rightarrow a \\
\end{align*}\right\}

これは再帰降下法で解析可能だろうか？
関数 expr を書いてみれば、その問題はたちどころに明らかとなるだろう.

recursive_descent_left_recursive.rs

// E -> E + T
fn expr(input: &Vec<Token<&'static str>>, position: &mut usize) -> Result<Tree<ParseNode<&'static str>>, String> {
  if input.len() <= *position {
    return Err("all of input is consumed.".to_string());
  }
  if input[*position].kind == "(" || input[*position].kind == "a" {
    let e = expr(input, position)?;
    let add = try_consume(input, position, "+")?;
    let t = term(input, position)?;
    Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "E", variant: 0 }), vec![e, add, t]))
  } else {
    Err(format!("expected (, or a, but found {actual}", actual = input[*position].kind))
  }
}

たとえばここに a が入力されてきたとしよう.
すると、if 文を抜けて let e = expr(input, position)?; を実行することになる.
ここまで position は進んでいないので、まったく同じ引数で呼び出された expr もまた同じように expr を呼び出す.
呼び出された expr もまた同じように expr を呼び出す.
呼び出された expr もまた同じように expr を呼び出す.
: : :
やがてはメモリを食いつぶしてスタックオーバーフローする.

再帰降下法の天敵 - LL(1) 文法の条件②

この問題は入力を消費しないまま同じ非終端記号を処理しようとしたこと、つまり $A \rightarrow A\ \alpha$ という形をした規則があることに起因している.
こうなると、再帰降下法では逆立ちしてもこの文法を扱うことはできない.
しかし幸いにして(?) この言語を扱うことはできる. 実際最初の例で出した文法から生成される言語 $L(G)$ と先ほど見た文法から生成される言語 $L(G)$ は同一である(さぼって同じ名前 $G$ を使いまわしたせいで分かりにくいが).
一般に、左再帰を含む文脈自由文法 $H$ があるとき、$L(H) = L(H')$ であるような、左再帰を含まない文法 $H'$ があることが知られている.
(実際にこの $H'$ を構成するアルゴリズムについてはドラゴンブックか何かを参照されたし.)
文法が変われば構文木も変わるが、項書き換えを頑張るなどすればよいだろう.
再帰降下法の天敵ではあるが、迂回路があるタイプの困難であるから、比較的御しやすいとも言える.

FOLLOW(A)

問題のある文法

数式を表現する新しい文法を使って再帰降下法を考えてみよう.
開始記号は同じく $\text{E}$ である.

\text{文法}\ G = \left\{\begin{align*}
  E  & \rightarrow E'     \ T      \\
  E' & \rightarrow T \ {+}    \ E' \\
  E' & \rightarrow \epsilon        \\
  T  & \rightarrow T'     \ F      \\
  T' & \rightarrow F \ \times \ T' \\
  T' & \rightarrow \epsilon        \\
  F  & \rightarrow (      \ E \ )  \\
  F  & \rightarrow a \\
\end{align*}\right\}

最初に見た文法の $E'$ や $T'$ は expr_tail、term_tail を表していたが、今度は expr_head、term_head といった感じだ.
この $L(G)$ も前と同じく $a,\ a+a,\ a \times a,\ (a+a) \times (a \times (a + a))$ などを含む.

これは再帰降下法で解析可能だろうか？
実は、できない.

例えば、入力として a が与えられたとしよう. 正しい導出列は次のようなものだ.

\begin{align*}
            & E     & \text{// }&\text{開始記号} \\
\Rightarrow \; & E'\ T & \text{// }&E \rightarrow E' \ T \\
\Rightarrow \; & \epsilon \ T & \text{// }& E' \rightarrow \epsilon \\
\Rightarrow \; & T'\ F & \text{// }& T \rightarrow T' \ F \\
\Rightarrow \; & \epsilon \ F & \text{// }& T' \rightarrow \epsilon \\
\Rightarrow \; & a & \text{// }& F \rightarrow a \\
\end{align*}

しかし、再帰降下法を上で紹介したとおりに書くと、

recursive_descent_conflict.rs

// E' -> T + E'
// E' -> ε
fn expr_head(input: &Vec<Token<&'static str>>, position: &mut usize) -> Result<Tree<ParseNode<&'static str>>, String> {
  if *position < input.len() && (input[*position].kind == "a" || input[*position].kind == "(") {
    // E' -> T + E'
    // n.b. FIRST(T + E') = { a, open }
    let t = term(input, position)?;
    let add = try_consume(input, position, "+")?;
    let ep = expr_head(input, position)?;
    return Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "E", variant: 1 }), vec![t, add, ep]));
  } else {
    // E' -> ε
    return Ok(Tree::new(ParseNode::Reduction(Nonterminal { kind: "E", variant: 1 })));
  }
}

のようになり、$E' \rightarrow \epsilon$ ではなく $E' \rightarrow T + E'$ が選択されてしまい失敗する.

問題の本質

同じ問題を引き起こす次の文法で、失敗の理由を考えてみよう. 開始記号は LIST である.

\text{文法}\ G = \left\{\begin{align*}
  \text{LIST} & \rightarrow \text{HEAD} \;\> \text{id} \\
  \text{HEAD} & \rightarrow \text{id} \;\> \text{sep} \;\> \text{HEAD} \\
  \text{HEAD} & \rightarrow \epsilon
\end{align*}\right\}

これは foo、foo, bar、foo, bar, baz, qux などを生成する.

この文法を再帰降下法で扱おうとした場合何が問題になるのかと言えば、LIST が最後に消費しようとしている id を、HEAD が先に消費してしまう点にある.
HEAD は id を食い尽くすのではなく、最後の最後で自制して $\epsilon$ を導出すべきなのだが、(1トークン先読みの) 再帰降下法ではこの自制が効かない.

正規表現で表そうとすれば、a?a や (ab)*a に相当するような文法が問題となる.
この事実を形式的に表すため、次の関数 FOLLOW を導入しよう.

\text{FOLLOW}(A) = \{ a \in \Sigma \mid S \Rightarrow^\star \alpha\, A\, a\, \beta \}

日本語にすれば、S からの導出の中で、A の直後に現れうる非終端記号からなる集合が FOLLOW(A) であり、これを A の FOLLOW 集合と呼ぶ.

上の文法で言えば、

\begin{align*}
\text{FOLLOW}(\text{LIST}) =& \varnothing \\
\text{FOLLOW}(\text{HEAD}) =& \{ \text{id} \} \\
\end{align*}

となる (この位の文法であれば定義通りに整理していくだけで手計算できるだろう. アルゴリズム的な計算方法は後で見る).
ここで、文法 $G$ を拡張して $\text{LIST}' \rightarrow \text{LIST}\ \text{EOS} $ という規則が存在すれば、$\text{FOLLOW}(\text{LIST}) = \lbrace \text{EOS} \rbrace$ となる.
LL(1) 構文解析ではこちらの方が扱いやすいことも多い.
($ を使おうとしたが、Qiita ではうまく表示できなかったため EOS としている.)

FIRST 集合も示しておこう.

\begin{align*}
\text{FIRST}(\text{LIST}) =& \{ \text{id} \} \\
\text{FIRST}(\text{HEAD}) =& \{ \text{id} \} \\
\end{align*}

今回の問題は、先読みした記号が id であるときに、$\text{FIRST}(\text{HEAD}) = { \text{id} }$ に従ってこれを消費するか、$\text{HEAD} \rightarrow \epsilon$ を選択して id を次の規則のために残しておくかで混乱が生じた点にある.

再帰降下法の限界 - LL(1) 文法の条件③

一般に、$A \rightarrow \epsilon$ を選択すると、現在先読みしている記号 $a$ について $a \in \text{FOLLOW}(A)$ である場合 $a$ は別の規則によって還元されることとなる.
このとき、$a \in \text{FIRST}(A)$ でもあると、別の規則のために残されるべき $a$ まで $A$ に還元されてしまう.
従って、LL(1) 文法の条件には次が付け加えられなければならない.

\text{生成規則}\; A \rightarrow \alpha \;\text{が存在し}\; \epsilon \in \text{FIRST}(\alpha)\; \text{であるとき、} \\
\text{FIRST}(\alpha) \cap \text{FOLLOW}(A) = \varnothing \quad \text{if}\ \epsilon \in \text{FIRST}(\alpha)

n.b. $\alpha \Rightarrow^\star \epsilon \Leftrightarrow \epsilon \in \text{FIRST}(\alpha)$

この条件に対する違反を、first/follow conflict と言う.

LL(1) 構文解析

再帰降下法では特定の文法のみを扱い、各非終端記号に対応する関数を直接書いていた.
そうする代わりに、文法をパラメータとしたものを LL(1) 構文解析と言う.

FOLLOW 集合を使わない手抜き LL(1) 構文解析

受け取る文法が LL(1) であると保証されているならば、FOLLOW 集合を計算する必要がない.
まずは FOLLOW 集合を使わない手抜き LL(1) 構文解析から考え、徐々に真の LL(1) へと近づいて行こう.

FIRST 集合の計算

FIRST (関数|集合) の定義を再度示す.

\begin{align*}
  \text{FIRST}(\epsilon) =&\ \{\epsilon\} \\
  \text{FIRST}(a \alpha) =&\ \{ a \} \\
  \text{FIRST}(A \; \alpha) =&\ \begin{cases}
    L(G|_A):1 & \text{if}\ \epsilon \notin L(G|_A):1 \\
    (L(G|_A):1 \setminus \{ \epsilon \}) \cup \text{FIRST}(\alpha) & \text{otherwise}
  \end{cases}
\end{align*}

再帰降下法では、文法 $G$ における $\forall A \in N$ について、$\text{FIRST}(A)$ を求める必要があるのだった.

そのアルゴリズムを以下に日本語で書くとこうなる.

すべての $A \in N$ について、$\text{FIRST}(A) = \varnothing$ で初期化する.
以下を、収束するまで繰り返す.
1. 各生成規則 $A \rightarrow X_1\ X_2\ \cdots\ X_n \in P$ について、
  1. $X_i$ を 0 から順に見る
    1. $X_i \in \Sigma$ であるとき
      1. $\text{FIRST}(A) = \text{FIRST}(A) \cup {X_i}$
      2. この生成規則については一旦終了
    2. $X_i \in N$ であるとき
      1. $\text{FIRST}(A) = \text{FIRST}(A) \cup (\text{FIRST}(X_i) \setminus {\epsilon})$
      2. $\epsilon \in \text{FIRST}(X_i)$ であれば、この生成規則については一旦終了
  2. $X_n$ まで見た上に、$\epsilon \in \text{FIRST}(X_n)$ であった場合、$\text{FIRST}(A) = \text{FIRST}(A) \cup {\epsilon}$
変化がなくなれば終了

$X_i \in \Sigma$ と $X_i \in N$ の場合分けをしたくない場合、$\forall X \in (N \cup \Sigma)$ について $\text{FIRST}(X)$ を求めてもよい.
定義より $\forall a \in \Sigma$ について $\text{FIRST}(a) = {a}$ であるから、「$X_i \in N$ であるとき」の処理で統一できる.

以下には、場合分けありの実装例を示す.

ll1_tenuki.rs

fn first_sets_for<T>(grammar: &CFG<T>) -> HashMap<Nonterminal<T>, HashSet<NullableTerminal<T>>>
where T: Hash + Eq + Clone
{
  // init.
  let mut map = HashMap::new();
  for nonterminal in &grammar.nonterminals {
    map.insert(nonterminal.clone(), HashSet::new());
  }

  // 変化がなくなるまで反復
  let mut changed = true;
  while changed {
    changed = false;// これを忘れると無限ループ (1敗)
    for rule in &grammar.rules {
      let head = &rule.head;
      let mut nullable = true;// rule が ε を生成しうるか？
      // 各生成規則 head -> body について、FIRST(body) を求める
      for symbol in &rule.body {
        match symbol {
            Symbol::Terminal(terminal) => {
              // 終端記号が直接現れた場合、それを FIRST(head) (⊃ FIRST(body))に追加する.
              changed |= map.get_mut(head).unwrap().insert(NullableTerminal::Terminal(terminal.clone()));
              // ε ∉ FIRST(body) であることが分かる.
              nullable = false;
              // FIRST(body) の計算はここで打ち切ってよい.
              break;
            },// symbol is a Symbol::Terminal(terminal)
            Symbol::Nonterminal(nonterminal) => {
              // 非終端記号が現れた場合、FIRST(nonterminal) を FIRST(head) (⊃ FIRST(body))に追加する.
              // for sub_first in &map[&nonterminal] { ... } と書きたいが、不変参照を使うと map.get_mut(head) ができないので clone している. 多分もっときれいな書き方がある.
              let sub_first_set: Vec<NullableTerminal<T>> = map[&nonterminal].iter().cloned().collect();
              for sub_first in sub_first_set {
                // ただしこのとき、ε は除く.
                if !matches!(sub_first, NullableTerminal::Epsilon) {
                  changed |= map.get_mut(head).unwrap().insert(sub_first.clone());
                }
              }
              if !map[&nonterminal].contains(&NullableTerminal::Epsilon) {
                // もしも FIRST(nonterminal) が ε を含んでいなければ、
                // ε ∉ FIRST(body) であることが分かる.
                nullable = false;
                // FIRST(body) の計算はここで打ち切ってよい.
                break;
              } else /* if epsilon not-in map[nonterminal] */ {
                // もしも FIRST(nonterminal) が ε を含んでいれば、
                // ε ∈ FIRST(body) の疑いを晴らすことができないため、計算を続行する.
              }
            },// symbol is a Symbol::Nonterminal(nonterminal)
        }// match symbol
      }// loop for symbol in &rule.body
      if nullable {
        // ε ∈ FIRST(body) ならば、ε ∈ FIRST(head)
        changed |= map.get_mut(head).unwrap().insert(NullableTerminal::Epsilon);
      }
    }// loop for rule in &grammar.rules
  }// loop while changed

  map
}

簡単な確認用テスト

ll1_tenuki.rs

#[cfg(test)]
mod tests {
  use crate::grammar::ProductionRule;
  use super::*;

  #[test]
  fn test_first_sets_parens() {
    // S -> ( )
    // S -> { }
    // S -> ( S )
    // S -> { S }
    let s = Nonterminal { kind: "S", variant: 0 };
    let open_paren = Terminal { kind: "(" };
    let close_paren = Terminal { kind: ")" };
    let open_brace = Terminal { kind: "{" };
    let close_brace = Terminal { kind: "}" };
    let grammar = CFG::new(s.clone(), vec![
      ProductionRule { head: s.clone(), body: vec![Symbol::Terminal(open_paren.clone()), Symbol::Terminal(close_paren.clone())] },
      ProductionRule { head: s.clone(), body: vec![Symbol::Terminal(open_brace.clone()), Symbol::Terminal(close_brace.clone())] },
      ProductionRule { head: s.clone(), body: vec![Symbol::Terminal(open_paren.clone()), Symbol::Nonterminal(s.clone()), Symbol::Terminal(close_paren.clone())] },
      ProductionRule { head: s.clone(), body: vec![Symbol::Terminal(open_brace.clone()), Symbol::Nonterminal(s.clone()), Symbol::Terminal(close_brace.clone())] },
    ]);
    let first_sets = first_sets_for(&grammar);
    let first_set_s = &first_sets[&s];
    assert_eq!(first_set_s.len(), 2);
    assert!(first_set_s.contains(&NullableTerminal::Terminal(Terminal { kind: "(" })));
    assert!(first_set_s.contains(&NullableTerminal::Terminal(Terminal { kind: "{" })));
  }
  #[test]
  fn test_first_sets_expr() {
    // E  -> T E'
    // E' -> + T E'
    // E' -> e
    // T  -> F T'
    // T' -> x F T'
    // T' -> e
    // F  -> ( E )
    // F  -> a
    let expr = Nonterminal { kind: "E", variant: 0 };
    let expr_tail = Nonterminal { kind: "E", variant: 1 };
    let term = Nonterminal { kind: "T", variant: 0 };
    let term_tail = Nonterminal { kind: "T", variant: 1 };
    let factor = Nonterminal { kind: "F", variant: 0 };
    let open = Terminal { kind: "(" };
    let close = Terminal { kind: ")" };
    let add = Terminal { kind: "+" };
    let mul = Terminal { kind: "x" };
    let a = Terminal { kind: "a" };
    let grammar = CFG::new(expr.clone(), vec![
      // E  -> T E'
      ProductionRule { head: expr.clone(), body: vec![Symbol::Nonterminal(term.clone()), Symbol::Nonterminal(expr_tail.clone())] },
      // E' -> + T E'
      ProductionRule { head: expr_tail.clone(), body: vec![Symbol::Terminal(add.clone()), Symbol::Nonterminal(term.clone()), Symbol::Nonterminal(expr_tail.clone())] },
      // E' -> e
      ProductionRule { head: expr_tail.clone(), body: vec![] },
      // T  -> F T'
      ProductionRule { head: term.clone(), body: vec![Symbol::Nonterminal(factor.clone()), Symbol::Nonterminal(term_tail.clone())] },
      // T' -> x F T'
      ProductionRule { head: term_tail.clone(), body: vec![Symbol::Terminal(mul.clone()), Symbol::Nonterminal(factor.clone()), Symbol::Nonterminal(term_tail.clone())] },
      // T' -> e
      ProductionRule { head: term_tail.clone(), body: vec![] },
      // F  -> ( E )
      ProductionRule { head: factor.clone(), body: vec![Symbol::Terminal(open.clone()), Symbol::Nonterminal(expr.clone()), Symbol::Terminal(close.clone())] },
      // F  -> a
      ProductionRule { head: factor.clone(), body: vec![Symbol::Terminal(a.clone())] },
    ]);
    let first_sets = first_sets_for(&grammar);

    let first_set_expr = &first_sets[&expr];
    assert_eq!(first_set_expr.len(), 2);
    assert!(first_set_expr.contains(&NullableTerminal::Terminal(Terminal { kind: "a" })));
    assert!(first_set_expr.contains(&NullableTerminal::Terminal(Terminal { kind: "(" })));

    let first_set_expr_tail = &first_sets[&expr_tail];
    assert_eq!(first_set_expr_tail.len(), 2);
    assert!(first_set_expr_tail.contains(&NullableTerminal::Terminal(Terminal { kind: "+" })));
    assert!(first_set_expr_tail.contains(&NullableTerminal::Epsilon));

    let first_set_term = &first_sets[&term];
    assert_eq!(first_set_term.len(), 2);
    assert!(first_set_term.contains(&NullableTerminal::Terminal(Terminal { kind: "a" })));
    assert!(first_set_term.contains(&NullableTerminal::Terminal(Terminal { kind: "(" })));

    let first_set_term_tail = &first_sets[&term_tail];
    assert_eq!(first_set_term_tail.len(), 2);
    assert!(first_set_term_tail.contains(&NullableTerminal::Terminal(Terminal { kind: "x" })));
    assert!(first_set_term_tail.contains(&NullableTerminal::Epsilon));

    let first_set_factor = &first_sets[&factor];
    assert_eq!(first_set_factor.len(), 2);
    assert!(first_set_factor.contains(&NullableTerminal::Terminal(Terminal { kind: "a" })));
    assert!(first_set_factor.contains(&NullableTerminal::Terminal(Terminal { kind: "(" })));
 }
}

構文解析表の作成

再帰降下法では、現在還元しようとしている非終端記号と、先読みした記号ひとつを元に、適用する生成規則を決定しているのだった. そのためには、現在還元しようとしている非終端記号 A -> 先読みした非終端記号ひとつ a -> 生成規則 (A -> α) という形をした関数があると便利だ. 通常表形式で説明されるため、これを構文解析表という.

以下に、この手抜き LL(1) 用構文解析表を計算する関数の実装例を示す (create_rule_selector).
構文解析表の型は HashMap<Nonterminal<T>, HashMap<NullableTerminal<T>, &ProductionRule<T>>> としている.
n.b. 引数の first_sets は、上記 first_sets_for の返り値を期待している.

ll1_tenuki.rs

// A -> a -> rule であるようなテーブルを作成する
fn create_rule_selector<'a, T>(
  grammar: &'a CFG<T>,
  first_sets: &HashMap<Nonterminal<T>, HashSet<NullableTerminal<T>>>
) -> HashMap<Nonterminal<T>, HashMap<NullableTerminal<T>, &'a ProductionRule<T>>>
where T: Hash + Eq + Clone
{
  let mut table = HashMap::new();
  for nonterminal in &grammar.nonterminals {
    let inner = HashMap::new();
    table.insert(nonterminal.clone(), inner);
  }// loop for nt in &grammar.nonterminals

  for rule in &grammar.rules {
    for first in first_seq(&rule.body, first_sets) {
      // 今回は grammar が LL(1) 文法であることを前提にしているためチェックしないが、
      // もしもここで、すでに生成規則が格納されていた場合 first/first conflict
      table.get_mut(&rule.head.clone()).unwrap().insert(first, rule);
    }
  }// loop for rule in &grammar.rules

  table
}

fn first_seq<T>(
  symbols: &[Symbol<T>],
  first_sets: &HashMap<Nonterminal<T>, HashSet<NullableTerminal<T>>>
) -> HashSet<NullableTerminal<T>>
where T: Hash + Eq + Clone
{
  // first_sets_for の中では head -> body について FIRST(body) を求めていた.
  // それと同じようにして、FIRST(symbols) を求める. 多分処理を整理する余地が大きくある.

  let mut result = HashSet::new();
  let mut nullable = true;

  for symbol in symbols {
    match symbol {
      Symbol::Terminal(terminal) => {
        result.insert(NullableTerminal::Terminal(terminal.clone()));
        nullable = false;
        break;
      },
      Symbol::Nonterminal(nonterminal) => {
        let sub_first_set: Vec<NullableTerminal<T>> = first_sets[&nonterminal].iter().cloned().collect();
        for sub_first in sub_first_set {
          if let NullableTerminal::Terminal(t) = &sub_first {
            result.insert(NullableTerminal::Terminal(t.clone()));
          }
        }
        if !first_sets[&nonterminal].contains(&NullableTerminal::Epsilon) {
          nullable = false;
          break;
        } else /* if epsilon not-in map[nonterminal] */ {
          // 続行
        }
      },
    }// match symbol
  }// loop for symbol in symbols

  if nullable {
    result.insert(NullableTerminal::Epsilon);
  }

  result
}

再帰による実装例

構文解析表の作成まで出来れば、あとは単純である. 再帰降下法をほとんどそのまま書けばよい.
以下に実装例を示す. 処理の入り口は ll1_tenuki_recursive である.

ll1_tenuki.rs

pub fn ll1_tenuki_recursive<T>(input: &Vec<Token<T>>, grammar: &CFG<T>)
-> Result<Tree<ParseNode<T>>, String>
where T: Hash + Eq + Clone + Debug
{
  let rule_selctor = create_rule_selector(grammar, &first_sets_for(grammar));
  let mut position= 0;
  let tree = ll1_tenuki_recursive0(input, grammar.start.clone(), &rule_selctor, &mut position)?;
  if position == input.len() {
    Ok(tree)
  } else {
    // 入力が余っているのに終了してしまった
    Err("verbose input".to_string())
  }
}

fn ll1_tenuki_recursive0<T>(
  input: &Vec<Token<T>>,
  current_state: Nonterminal<T>,
  rule_selctor: &HashMap<Nonterminal<T>, HashMap<NullableTerminal<T>, &ProductionRule<T>>>,
  position: &mut usize
) -> Result<Tree<ParseNode<T>>, String>
where T: Hash + Eq + Clone + Debug
{
  // expr や term などの再帰降下法における関数名に相当するものを、current_state が表現している.
  if *position < input.len() {
    let mut tree = Tree::new(ParseNode::Reduction(current_state.clone()));
    let lookahead = NullableTerminal::Terminal(Terminal { kind: input[*position].kind.clone() });
    if let Some(&rule) = rule_selctor[&current_state].get(&lookahead)
                         .or(rule_selctor[&current_state].get(&NullableTerminal::Epsilon)) {
      // lookahead または ε が FIRST(current_state) に含まれている場合、対応する rule の適用を試みる
      for symbol in &rule.body {
        match symbol {
            Symbol::Terminal(terminal) => {
              let child = try_consume(input, position, &terminal.kind)?;
              tree.append(child);
            },
            Symbol::Nonterminal(next_state) => {
              let child = ll1_tenuki_recursive0(input, next_state.clone(), rule_selctor, position)?;
              tree.append(child);
            },
        }
      }
      Ok(tree)
    } else {
      // lookahead も ε も FIRST(current_state) に含まれていない場合エラー
      Err(format!("unexpected token for {current_state:?}: {actual:?}", actual = input[*position]))
    }
  } else /* input.len() <= *position */{
    // もしも拡張された文法を使っていれば *position と input.len() の比較が不要
    if let Some(&rule) = rule_selctor[&current_state].get(&NullableTerminal::Epsilon) {
      // 文の末尾が ε になりうる文法も考えられるため処理しなければならない
      let mut tree = Tree::new(ParseNode::Reduction(current_state.clone()));
      for symbol in &rule.body {
        match symbol {
            Symbol::Terminal(terminal) => {
              let child = try_consume(input, position, &terminal.kind)?;
              tree.append(child);
            },
            Symbol::Nonterminal(next_state) => {
              let child = ll1_tenuki_recursive0(input, next_state.clone(), rule_selctor, position)?;
              tree.append(child);
            },
        }
      }
      Ok(tree)
    } else {
      Err("expect remaining, but all of input is consumed.".to_string())
    }
  }
}

// 再帰降下法で使用していたものと同じ
fn try_consume<T>(input: &Vec<Token<T>>, position: &mut usize, expected_token_kind: &T)
-> Result<Tree<ParseNode<T>>, String>
where T: Hash + Eq + Clone + Debug
{
  if input.len() <= *position {
    Err("all of input is consumed.".to_string())
  } else if input[*position].kind == *expected_token_kind {
    let leaf = Tree::new(ParseNode::Input(input[*position].clone()));
    *position = *position + 1;
    Ok(leaf)
  } else {
    Err(format!("expected {expected_token_kind:?}, but found {actual:?}", actual = input[*position].kind))
  }
}

簡単な正常系で動作確認

ll1_tenuki.rs

#[cfg(test)]
mod tests {
  use super::*;
  use crate::grammar::ProductionRule;
  use crate::{tok, util::{TextPosition}};

  #[test]
  fn test_simple_mul() {
    let source = vec![
      tok!("a"),
      tok!("x"),
      tok!("a"),
    ];
    let expr = Nonterminal { kind: "E", variant: 0 };
    let expr_tail = Nonterminal { kind: "E", variant: 1 };
    let term = Nonterminal { kind: "T", variant: 0 };
    let term_tail = Nonterminal { kind: "T", variant: 1 };
    let factor = Nonterminal { kind: "F", variant: 0 };
    let open = Terminal { kind: "(" };
    let close = Terminal { kind: ")" };
    let add = Terminal { kind: "+" };
    let mul = Terminal { kind: "x" };
    let a = Terminal { kind: "a" };
    let grammar = CFG::new(expr.clone(), vec![
      // E  -> T E'
      ProductionRule { head: expr.clone(), body: vec![Symbol::Nonterminal(term.clone()), Symbol::Nonterminal(expr_tail.clone())] },
      // E' -> + T E'
      ProductionRule { head: expr_tail.clone(), body: vec![Symbol::Terminal(add.clone()), Symbol::Nonterminal(term.clone()), Symbol::Nonterminal(expr_tail.clone())] },
      // E' -> e
      ProductionRule { head: expr_tail.clone(), body: vec![] },
      // T  -> F T'
      ProductionRule { head: term.clone(), body: vec![Symbol::Nonterminal(factor.clone()), Symbol::Nonterminal(term_tail.clone())] },
      // T' -> x F T'
      ProductionRule { head: term_tail.clone(), body: vec![Symbol::Terminal(mul.clone()), Symbol::Nonterminal(factor.clone()), Symbol::Nonterminal(term_tail.clone())] },
      // T' -> e
      ProductionRule { head: term_tail.clone(), body: vec![] },
      // F  -> ( E )
      ProductionRule { head: factor.clone(), body: vec![Symbol::Terminal(open.clone()), Symbol::Nonterminal(expr.clone()), Symbol::Terminal(close.clone())] },
      // F  -> a
      ProductionRule { head: factor.clone(), body: vec![Symbol::Terminal(a.clone())] },
    ]);
    let result = ll1_tenuki_recursive(&source, &grammar);
    match result {
      Ok(tree) => {
        // Reduction(Nonterminal { kind: "E", variant: 0 })
        // |`-- Reduction(Nonterminal { kind: "T", variant: 0 })
        // |    |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |    |    `--- Input(Token { kind: "a", ... })
        // |    `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // |         |`-- Input(Token { kind: "x", ... })
        // |         |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |         |    `--- Input(Token { kind: "a", ... })
        // |         `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // `--- Reduction(Nonterminal { kind: "E", variant: 1 })
        // E -> T E'
        assert_eq!(tree.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 0 }));
        assert_eq!(tree.children.len(), 2);
        // T -> F T'
        let et = &tree.children[0];
        assert_eq!(et.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 0 }));
        assert_eq!(et.children.len(), 2);
        // F -> a
        let etf = &et.children[0];
        assert_eq!(etf.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(etf.children.len(), 1);
        // a
        let etfa = &etf.children[0];
        assert_eq!(etfa.label, ParseNode::Input(tok!("a")));
        assert!(etfa.children.is_empty());
        // T -> x F T'
        let ett1 = &et.children[1];
        assert_eq!(ett1.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert_eq!(ett1.children.len(), 3);
        // x
        let ett1x = &ett1.children[0];
        assert_eq!(ett1x.label, ParseNode::Input(tok!("x")));
        assert!(ett1x.children.is_empty());
        // F -> a
        let ett1f = &ett1.children[1];
        assert_eq!(ett1f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(ett1f.children.len(), 1);
        // a
        let ett1fa = &ett1f.children[0];
        assert_eq!(ett1fa.label, ParseNode::Input(tok!("a")));
        assert!(ett1fa.children.is_empty());
        // T' -> epsilon
        let ett1t1 = &ett1.children[2];
        assert_eq!(ett1t1.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert!(ett1t1.children.is_empty());
        // E' -> epsilon
        let ee1 = &tree.children[1];
        assert_eq!(ee1.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 1 }));
        assert!(ee1.children.is_empty());
      },
      Err(message) => panic!("パース失敗: {message}"),
    }
  }

  #[test]
  fn test_complex() {
    let source = vec![
      tok!("a"),
      tok!("x"),
      tok!("("),
      tok!("a"),
      tok!("+"),
      tok!("a"),
      tok!(")"),
    ];
    let expr = Nonterminal { kind: "E", variant: 0 };
    let expr_tail = Nonterminal { kind: "E", variant: 1 };
    let term = Nonterminal { kind: "T", variant: 0 };
    let term_tail = Nonterminal { kind: "T", variant: 1 };
    let factor = Nonterminal { kind: "F", variant: 0 };
    let open = Terminal { kind: "(" };
    let close = Terminal { kind: ")" };
    let add = Terminal { kind: "+" };
    let mul = Terminal { kind: "x" };
    let a = Terminal { kind: "a" };
    let grammar = CFG::new(expr.clone(), vec![
      // E  -> T E'
      ProductionRule { head: expr.clone(), body: vec![Symbol::Nonterminal(term.clone()), Symbol::Nonterminal(expr_tail.clone())] },
      // E' -> + T E'
      ProductionRule { head: expr_tail.clone(), body: vec![Symbol::Terminal(add.clone()), Symbol::Nonterminal(term.clone()), Symbol::Nonterminal(expr_tail.clone())] },
      // E' -> e
      ProductionRule { head: expr_tail.clone(), body: vec![] },
      // T  -> F T'
      ProductionRule { head: term.clone(), body: vec![Symbol::Nonterminal(factor.clone()), Symbol::Nonterminal(term_tail.clone())] },
      // T' -> x F T'
      ProductionRule { head: term_tail.clone(), body: vec![Symbol::Terminal(mul.clone()), Symbol::Nonterminal(factor.clone()), Symbol::Nonterminal(term_tail.clone())] },
      // T' -> e
      ProductionRule { head: term_tail.clone(), body: vec![] },
      // F  -> ( E )
      ProductionRule { head: factor.clone(), body: vec![Symbol::Terminal(open.clone()), Symbol::Nonterminal(expr.clone()), Symbol::Terminal(close.clone())] },
      // F  -> a
      ProductionRule { head: factor.clone(), body: vec![Symbol::Terminal(a.clone())] },
    ]);
    let result = ll1_tenuki_recursive(&source, &grammar);
    match result {
      Ok(tree) => {
        // Reduction(Nonterminal { kind: "E", variant: 0 })
        // |`-- Reduction(Nonterminal { kind: "T", variant: 0 })
        // |    |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |    |    `--- Input(Token { kind: "a", ... })
        // |    `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // |         |`-- Input(Token { kind: "x", ... })
        // |         |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |         |    |`-- Input(Token { kind: "(", ... })
        // |         |    |`-- Reduction(Nonterminal { kind: "E", variant: 0 })
        // |         |    |    |`-- Reduction(Nonterminal { kind: "T", variant: 0 })
        // |         |    |    |    |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |         |    |    |    |    `--- Input(Token { kind: "a", ... })
        // |         |    |    |    `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // |         |    |    `--- Reduction(Nonterminal { kind: "E", variant: 1 })
        // |         |    |         |`-- Input(Token { kind: "+", ... })
        // |         |    |         |`-- Reduction(Nonterminal { kind: "T", variant: 0 })
        // |         |    |         |    |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |         |    |         |    |    `--- Input(Token { kind: "a", ... })
        // |         |    |         |    `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // |         |    |         `--- Reduction(Nonterminal { kind: "E", variant: 1 })
        // |         |    `--- Input(Token { kind: ")", ... })
        // |         `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // `--- Reduction(Nonterminal { kind: "E", variant: 1 })
        // ルート: E -> T E'
        assert_eq!(tree.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 0 }));
        assert_eq!(tree.children.len(), 2);

        let t = &tree.children[0]; // T -> F T'
        let ep = &tree.children[1]; // E' -> ε

        assert_eq!(t.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 0 }));
        assert_eq!(t.children.len(), 2);

        // F -> a
        let f = &t.children[0];
        assert_eq!(f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(f.children.len(), 1);
        assert_eq!(f.children[0].label, ParseNode::Input(tok!("a")));
        assert!(f.children[0].children.is_empty());

        // T' -> x F T'
        let tp = &t.children[1];
        assert_eq!(tp.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert_eq!(tp.children.len(), 3);

        // x
        let tp_x = &tp.children[0];
        assert_eq!(tp_x.label, ParseNode::Input(tok!("x")));
        assert!(tp_x.children.is_empty());

        // F -> ( E )
        let tp_f = &tp.children[1];
        assert_eq!(tp_f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(tp_f.children.len(), 3);

        // '('
        assert_eq!(tp_f.children[0].label, ParseNode::Input(tok!("(")));
        assert!(tp_f.children[0].children.is_empty());

        // E -> T E' (中の a + a)
        let inner_e = &tp_f.children[1];
        assert_eq!(inner_e.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 0 }));
        assert_eq!(inner_e.children.len(), 2);

        let inner_t = &inner_e.children[0];
        let inner_ep = &inner_e.children[1];

        assert_eq!(inner_t.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 0 }));
        assert_eq!(inner_t.children.len(), 2);

        // F -> a
        let inner_f = &inner_t.children[0];
        assert_eq!(inner_f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(inner_f.children.len(), 1);
        assert_eq!(inner_f.children[0].label, ParseNode::Input(tok!("a")));

        // T' -> ε
        let inner_tp = &inner_t.children[1];
        assert_eq!(inner_tp.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert!(inner_tp.children.is_empty());

        // E' -> + T E'
        assert_eq!(inner_ep.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 1 }));
        assert_eq!(inner_ep.children.len(), 3);

        // '+'
        assert_eq!(inner_ep.children[0].label, ParseNode::Input(tok!("+")));
        assert!(inner_ep.children[0].children.is_empty());

        // T -> F T' の F -> a
        let inner_ep_t = &inner_ep.children[1];
        assert_eq!(inner_ep_t.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 0 }));
        assert_eq!(inner_ep_t.children.len(), 2);
        let inner_ep_t_f = &inner_ep_t.children[0];
        assert_eq!(inner_ep_t_f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(inner_ep_t_f.children[0].label, ParseNode::Input(tok!("a")));

        // T' -> ε
        let inner_ep_t_tp = &inner_ep_t.children[1];
        assert_eq!(inner_ep_t_tp.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert!(inner_ep_t_tp.children.is_empty());

        // ')' の確認
        assert_eq!(tp_f.children[2].label, ParseNode::Input(tok!(")")));
        assert!(tp_f.children[2].children.is_empty());

        // T' -> ε
        let tp_tp = &tp.children[2];
        assert_eq!(tp_tp.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert!(tp_tp.children.is_empty());

        // E' -> ε
        assert_eq!(ep.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 1 }));
        assert!(ep.children.is_empty());
      },
      Err(message) => panic!("パース失敗: {message}"),
    }
  }
}

ループによる実装例

一般に、特に長大なデータを扱うアルゴリズムは、再帰よりループが相応しいと考えられている.
構文解析は長大なデータを扱う可能性を持つアルゴリズムの代表格であるから、そうしよう.

一気に書き換えすぎた気もするが、一例を示す.

ll1_tenuki.rs

pub fn ll1_tenuki_loop<T>(
  input: &Vec<Token<T>>,
  grammar: &CFG<T>
) -> Result<Tree<ParseNode<T>>, String>
where T: Hash + Eq + Clone + Debug,
{
  let rule_selector = create_rule_selector(grammar, &first_sets_for(grammar));
  let mut position = 0;

  // 管理用スタック
  let mut state_stack = Vec::new();
  let mut tree_stack = Vec::new();
  let mut rest_of_children_count_stack = Vec::new();

  let dummy_variant = grammar.nonterminals.iter()
             .filter(|n| n.kind == grammar.start.kind)
             .map(|n| n.variant)
             .max()
             .unwrap() + 1;
  // 開始記号をルートにする
  state_stack.push(Symbol::Nonterminal(grammar.start.clone()));
  tree_stack.push(Tree::new(ParseNode::Reduction(Nonterminal {
    kind: grammar.start.kind.clone(),
    variant: dummy_variant
  })));
  rest_of_children_count_stack.push(255_usize);// 適当に大きな値 (> 1) を入れる

  while let Some(current_state) = state_stack.pop() {
    match &current_state {
      Symbol::Terminal(terminal) => {
        let tree = try_consume(input, &mut position, &terminal.kind)?;
        tree_stack.push(tree);
        rest_of_children_count_stack.push(0);
      },// Symbol::Terminal(terminal)
      Symbol::Nonterminal(nonterminal) => {
        let lookahead = if position < input.len() {
          NullableTerminal::Terminal(Terminal { kind: input[position].kind.clone() })
        } else {
          NullableTerminal::Epsilon
        };
        let rule = rule_selector[nonterminal]
          .get(&lookahead)
          .or_else(|| rule_selector[nonterminal].get(&NullableTerminal::Epsilon))
          .ok_or_else(|| {
              if position < input.len() {
                format!("unexpected token for {current_state:?}: {:?}", input[position])
              } else {
                "expect remaining, but all of input is consumed.".to_string()
              }
          })?;
        tree_stack.push(Tree::new(ParseNode::Reduction(nonterminal.clone())));
        rest_of_children_count_stack.push(rule.body.len());
        for ch in rule.body.iter().rev() {
          state_stack.push(ch.clone());
        }
      }// Symbol::Nonterminal(nonterminal)
    }// match current_state
    while matches!(rest_of_children_count_stack.last().unwrap(), 0) {
      rest_of_children_count_stack.pop();
      let child = tree_stack.pop().unwrap();
      let parent = tree_stack.last_mut().unwrap();
      parent.append(child);
      if let Some(count) = rest_of_children_count_stack.last_mut() {
        *count -= 1;
      }
    }// loop while matches!(rest_of_children_count_stack.last().unwrap(), 0)
  }// loop while let Some(current_state) = state_stack.pop()

  debug_assert_eq!(tree_stack.len(), 1);

  let mut dummy = tree_stack.pop().unwrap();
  Ok(dummy.children.pop().unwrap())
}

もう少し面影の残る書き換えにしようと思ったのだが、がっつり行ってしまった.

一応説明しておくと:
tree_stack には最初ダミーの頂点を入れている.　これが、拡張された文法における S' として働く.
current_state として、非終端記号だけでなく、終端記号も含めるようにしている.
rest_of_children_count_stack の頂点が 0 であれば、tree_stack の天辺にある部分木が完成したことを示す.
current_state が終端記号であるとき、try_consume によって部分木を作成する. この部分木はその瞬間に完成している.
current_state が非終端記号であるとき、tree_stack に空の木を追加し、state_stack に子を積む. このとき、処理順序とスタックからの取得順序とが一致するようにするため逆順にしなければならない. state_stack に積んだ子がすべて処理されたとき、この部分木は完成する.
current_state を処理するたび、現在の部分木が完成しているかを確かめ、完成していれば親の子として追加する.
dummy に対応する rest_of_children_count を大きくとることで、完成しても未完成と言い張り、tree_stack に残るようにしている.

真の LL(1) 構文解析

親切な関数というものは、引数不正を正しく検出できなければならない.
真の LL(1) 構文解析は、文法が LL(1) でない場合にその事実を報告するため FOLLOW 集合も計算する.

FOLLOW 集合の計算

FOLLOW (関数|集合) の定義を再度示す.

\text{FOLLOW}(A) = \{ a \in \Sigma \mid S \Rightarrow^\star \alpha\, A\, a\, \beta \}

与えられた文法が LL(1) 文法であるには、

\text{生成規則}\; A \rightarrow \alpha \;\text{が存在し}\; \epsilon \in \text{FIRST}(\alpha)\; \text{であるとき、} \\
\text{FIRST}(\alpha) \cap \text{FOLLOW}(A) = \varnothing \quad \text{if}\ \epsilon \in \text{FIRST}(\alpha)

である必要があるから、確認のため $\text{FOLLOW}(A)$ を求めておかなければならない.

そのアルゴリズムを以下に日本語で書くとこうなる. ここで、FIRST 集合はあらかじめ計算済みであるものとする.

すべての $A \in N$ について、$\text{FOLLOW}(A) = \varnothing$ で初期化する.
(必要であれば、) 末尾記号 $$$ を $\text{FOLLOW}(S)$ に追加する.
以下を、収束するまで繰り返す.
1. 各生成規則 $A \rightarrow \alpha; B; \beta \in P$ について、
  1. $\text{FOLLOW}(B)$ に $\text{FIRST}(\beta) \setminus {\epsilon}$ を追加する.
  2. $\epsilon \in \text{FIRST}(\beta)$ であるとき、$\text{FOLLOW}(B)$ に $\text{FOLLOW}(A)$ を追加する.
    n.b. $\text{FIRST}(\epsilon) = {\epsilon}$;
変化がなくなれば終了

以下には、$$$ を使わない実装例を示す.

ll1.rs

fn follow_sets_for<T>(
  grammar: &CFG<T>,
  first_sets: &HashMap<Nonterminal<T>, HashSet<NullableTerminal<T>>>
) -> HashMap<Nonterminal<T>, HashSet<Terminal<T>>>
where T: Hash + Eq + Clone + Debug
{
  // init.
  let mut map = HashMap::new();
  for nonterminal in &grammar.nonterminals {
    map.insert(nonterminal.clone(), HashSet::new());
  }

  // 変化がなくなるまで反復
  let mut changed = true;
  while changed {
    changed = false;

    for rule in &grammar.rules {
      for i in 0..rule.body.len() {
        if let Symbol::Nonterminal(b) = &rule.body[i] {
          let beta = &rule.body[i + 1..];
          let first_beta = first_seq(beta, first_sets);
          let follow_b = map.get_mut(b).unwrap();
          // follow(B) に first(β) を追加する
          let before_len = follow_b.len();
          follow_b.extend(first_beta.iter()
              .filter_map(|a|
                if let NullableTerminal::Terminal(t) = a { Some(t.clone()) } else { None }
              ));
          changed |= before_len != follow_b.len();
          // first(β) contains ε であれば、follow(B) に follow(A) を追加する
          if first_beta.contains(&NullableTerminal::Epsilon) {
            let before_len = follow_b.len();
            let follow_a = map[&rule.head].clone();
            let follow_b = map.get_mut(b).unwrap();// follow_a を取るときに一度 map を手放してしまうので取得しなおす
            follow_b.extend(follow_a);
            changed |= before_len != follow_b.len();
          }
        } else {
          // 終端記号はスルー
          continue;
        }
      }// loop for i in 0..body.len()
    }// loop for rule in &grammar.rules
  }// loop while changed

  map
}

FOLLOW 集合を考慮した構文解析表の作成

あとは、$\alpha \Rightarrow^\star \epsilon$ であるような生成規則 $A \rightarrow \alpha$ が、$\text{FOLLOW}(A)$ を先読みした場合も使われるようにすればよい.
衝突がある (i.e. LL(1) でない) 文法に対してエラーを返すような実装例を示す.

ll1.rs

use std::collections::{hash_map::Entry, HashMap, HashSet};

// A -> a -> rule であるようなテーブルを作成する
fn create_rule_selector<'a, T>(
  grammar: &'a CFG<T>
) -> Result<HashMap<Nonterminal<T>, HashMap<NullableTerminal<T>, &'a ProductionRule<T>>>, String>
where T: Hash + Eq + Clone + Debug
{
  let first_sets = first_sets_for(grammar);
  let follow_sets = follow_sets_for(&grammar, &first_sets);

  let mut table = HashMap::new();
  for nonterminal in &grammar.nonterminals {
    let inner = HashMap::new();
    table.insert(nonterminal.clone(), inner);
  }// loop for nt in &grammar.nonterminals

  let mut nullable_rules = HashMap::new();

  for rule in &grammar.rules {
    let first_body = first_seq(&rule.body, &first_sets);
    // first(body) の中身をすべて追加する
    for first in &first_body {
      let row = table.get_mut(&rule.head.clone()).unwrap();
      let cell = row.entry(first.clone());
      if matches!(cell, Entry::Occupied(_)) {
        // 既に生成規則が格納されている場合、LL(1) 文法でない
        return Err("the grammar has first/first conflict".to_string());
      }
      cell.insert_entry(rule);
    }
    // rule が ε を生成する場合については後段で整理する
    if first_body.contains(&NullableTerminal::Epsilon) {
      nullable_rules.insert(&rule.head, rule);
    }// if first(body) contains epsilon
  }// loop for rule in &grammar.rules

  // A -> α が ε を生成しうる場合、follow(A) も考慮する
  for (nonterminal, rule) in nullable_rules {
    let follow_a = &follow_sets[nonterminal];

    for follow in follow_a {
      let row = table.get_mut(&rule.head.clone()).unwrap();
      let cell = row.entry(NullableTerminal::Terminal(follow.clone()));
      if matches!(cell, Entry::Occupied(_)) {
        // 既に生成規則が格納されている場合、LL(1) 文法でない
        return Err("the grammar has first/follow conflict".to_string());
      }
      cell.insert_entry(rule);
      // table.get_mut(&rule.head.clone()).unwrap().insert(first.clone(), rule);
    }
  }

  Ok(table)
}

実装

手抜き LL(1) 構文解析の構文解析表を差し替えるだけであるから省略する.

簡単なテスト

試験の対象は関数 ll1 である.

ll1.rs

#[cfg(test)]
mod tests {
  use super::*;
  use crate::grammar::ProductionRule;
  use crate::{tok, util::{TextPosition}};

  #[test]
  fn test_simple_mul() {
    let source = vec![
      tok!("a"),
      tok!("x"),
      tok!("a"),
    ];
    let expr = Nonterminal { kind: "E", variant: 0 };
    let expr_tail = Nonterminal { kind: "E", variant: 1 };
    let term = Nonterminal { kind: "T", variant: 0 };
    let term_tail = Nonterminal { kind: "T", variant: 1 };
    let factor = Nonterminal { kind: "F", variant: 0 };
    let open = Terminal { kind: "(" };
    let close = Terminal { kind: ")" };
    let add = Terminal { kind: "+" };
    let mul = Terminal { kind: "x" };
    let a = Terminal { kind: "a" };
    let grammar = CFG::new(expr.clone(), vec![
      // E  -> T E'
      ProductionRule { head: expr.clone(), body: vec![Symbol::Nonterminal(term.clone()), Symbol::Nonterminal(expr_tail.clone())] },
      // E' -> + T E'
      ProductionRule { head: expr_tail.clone(), body: vec![Symbol::Terminal(add.clone()), Symbol::Nonterminal(term.clone()), Symbol::Nonterminal(expr_tail.clone())] },
      // E' -> e
      ProductionRule { head: expr_tail.clone(), body: vec![] },
      // T  -> F T'
      ProductionRule { head: term.clone(), body: vec![Symbol::Nonterminal(factor.clone()), Symbol::Nonterminal(term_tail.clone())] },
      // T' -> x F T'
      ProductionRule { head: term_tail.clone(), body: vec![Symbol::Terminal(mul.clone()), Symbol::Nonterminal(factor.clone()), Symbol::Nonterminal(term_tail.clone())] },
      // T' -> e
      ProductionRule { head: term_tail.clone(), body: vec![] },
      // F  -> ( E )
      ProductionRule { head: factor.clone(), body: vec![Symbol::Terminal(open.clone()), Symbol::Nonterminal(expr.clone()), Symbol::Terminal(close.clone())] },
      // F  -> a
      ProductionRule { head: factor.clone(), body: vec![Symbol::Terminal(a.clone())] },
    ]);
    let result = ll1(&source, &grammar);
    match result {
      Ok(tree) => {
        // Reduction(Nonterminal { kind: "E", variant: 0 })
        // |`-- Reduction(Nonterminal { kind: "T", variant: 0 })
        // |    |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |    |    `--- Input(Token { kind: "a", ... })
        // |    `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // |         |`-- Input(Token { kind: "x", ... })
        // |         |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |         |    `--- Input(Token { kind: "a", ... })
        // |         `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // `--- Reduction(Nonterminal { kind: "E", variant: 1 })
        // E -> T E'
        assert_eq!(tree.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 0 }));
        assert_eq!(tree.children.len(), 2);
        // T -> F T'
        let et = &tree.children[0];
        assert_eq!(et.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 0 }));
        assert_eq!(et.children.len(), 2);
        // F -> a
        let etf = &et.children[0];
        assert_eq!(etf.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(etf.children.len(), 1);
        // a
        let etfa = &etf.children[0];
        assert_eq!(etfa.label, ParseNode::Input(tok!("a")));
        assert!(etfa.children.is_empty());
        // T -> x F T'
        let ett1 = &et.children[1];
        assert_eq!(ett1.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert_eq!(ett1.children.len(), 3);
        // x
        let ett1x = &ett1.children[0];
        assert_eq!(ett1x.label, ParseNode::Input(tok!("x")));
        assert!(ett1x.children.is_empty());
        // F -> a
        let ett1f = &ett1.children[1];
        assert_eq!(ett1f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(ett1f.children.len(), 1);
        // a
        let ett1fa = &ett1f.children[0];
        assert_eq!(ett1fa.label, ParseNode::Input(tok!("a")));
        assert!(ett1fa.children.is_empty());
        // T' -> epsilon
        let ett1t1 = &ett1.children[2];
        assert_eq!(ett1t1.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert!(ett1t1.children.is_empty());
        // E' -> epsilon
        let ee1 = &tree.children[1];
        assert_eq!(ee1.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 1 }));
        assert!(ee1.children.is_empty());
      },
      Err(message) => panic!("パース失敗: {message}"),
    }
  }

  #[test]
  fn test_complex() {
    let source = vec![
      tok!("a"),
      tok!("x"),
      tok!("("),
      tok!("a"),
      tok!("+"),
      tok!("a"),
      tok!(")"),
    ];
    let expr = Nonterminal { kind: "E", variant: 0 };
    let expr_tail = Nonterminal { kind: "E", variant: 1 };
    let term = Nonterminal { kind: "T", variant: 0 };
    let term_tail = Nonterminal { kind: "T", variant: 1 };
    let factor = Nonterminal { kind: "F", variant: 0 };
    let open = Terminal { kind: "(" };
    let close = Terminal { kind: ")" };
    let add = Terminal { kind: "+" };
    let mul = Terminal { kind: "x" };
    let a = Terminal { kind: "a" };
    let grammar = CFG::new(expr.clone(), vec![
      // E  -> T E'
      ProductionRule { head: expr.clone(), body: vec![Symbol::Nonterminal(term.clone()), Symbol::Nonterminal(expr_tail.clone())] },
      // E' -> + T E'
      ProductionRule { head: expr_tail.clone(), body: vec![Symbol::Terminal(add.clone()), Symbol::Nonterminal(term.clone()), Symbol::Nonterminal(expr_tail.clone())] },
      // E' -> e
      ProductionRule { head: expr_tail.clone(), body: vec![] },
      // T  -> F T'
      ProductionRule { head: term.clone(), body: vec![Symbol::Nonterminal(factor.clone()), Symbol::Nonterminal(term_tail.clone())] },
      // T' -> x F T'
      ProductionRule { head: term_tail.clone(), body: vec![Symbol::Terminal(mul.clone()), Symbol::Nonterminal(factor.clone()), Symbol::Nonterminal(term_tail.clone())] },
      // T' -> e
      ProductionRule { head: term_tail.clone(), body: vec![] },
      // F  -> ( E )
      ProductionRule { head: factor.clone(), body: vec![Symbol::Terminal(open.clone()), Symbol::Nonterminal(expr.clone()), Symbol::Terminal(close.clone())] },
      // F  -> a
      ProductionRule { head: factor.clone(), body: vec![Symbol::Terminal(a.clone())] },
    ]);
    let result = ll1(&source, &grammar);
    match result {
      Ok(tree) => {
        // Reduction(Nonterminal { kind: "E", variant: 0 })
        // |`-- Reduction(Nonterminal { kind: "T", variant: 0 })
        // |    |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |    |    `--- Input(Token { kind: "a", ... })
        // |    `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // |         |`-- Input(Token { kind: "x", ... })
        // |         |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |         |    |`-- Input(Token { kind: "(", ... })
        // |         |    |`-- Reduction(Nonterminal { kind: "E", variant: 0 })
        // |         |    |    |`-- Reduction(Nonterminal { kind: "T", variant: 0 })
        // |         |    |    |    |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |         |    |    |    |    `--- Input(Token { kind: "a", ... })
        // |         |    |    |    `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // |         |    |    `--- Reduction(Nonterminal { kind: "E", variant: 1 })
        // |         |    |         |`-- Input(Token { kind: "+", ... })
        // |         |    |         |`-- Reduction(Nonterminal { kind: "T", variant: 0 })
        // |         |    |         |    |`-- Reduction(Nonterminal { kind: "F", variant: 0 })
        // |         |    |         |    |    `--- Input(Token { kind: "a", ... })
        // |         |    |         |    `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // |         |    |         `--- Reduction(Nonterminal { kind: "E", variant: 1 })
        // |         |    `--- Input(Token { kind: ")", ... })
        // |         `--- Reduction(Nonterminal { kind: "T", variant: 1 })
        // `--- Reduction(Nonterminal { kind: "E", variant: 1 })
        // ルート: E -> T E'
        assert_eq!(tree.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 0 }));
        assert_eq!(tree.children.len(), 2);

        let t = &tree.children[0]; // T -> F T'
        let ep = &tree.children[1]; // E' -> ε

        assert_eq!(t.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 0 }));
        assert_eq!(t.children.len(), 2);

        // F -> a
        let f = &t.children[0];
        assert_eq!(f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(f.children.len(), 1);
        assert_eq!(f.children[0].label, ParseNode::Input(tok!("a")));
        assert!(f.children[0].children.is_empty());

        // T' -> x F T'
        let tp = &t.children[1];
        assert_eq!(tp.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert_eq!(tp.children.len(), 3);

        // x
        let tp_x = &tp.children[0];
        assert_eq!(tp_x.label, ParseNode::Input(tok!("x")));
        assert!(tp_x.children.is_empty());

        // F -> ( E )
        let tp_f = &tp.children[1];
        assert_eq!(tp_f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(tp_f.children.len(), 3);

        // '('
        assert_eq!(tp_f.children[0].label, ParseNode::Input(tok!("(")));
        assert!(tp_f.children[0].children.is_empty());

        // E -> T E' (中の a + a)
        let inner_e = &tp_f.children[1];
        assert_eq!(inner_e.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 0 }));
        assert_eq!(inner_e.children.len(), 2);

        let inner_t = &inner_e.children[0];
        let inner_ep = &inner_e.children[1];

        assert_eq!(inner_t.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 0 }));
        assert_eq!(inner_t.children.len(), 2);

        // F -> a
        let inner_f = &inner_t.children[0];
        assert_eq!(inner_f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(inner_f.children.len(), 1);
        assert_eq!(inner_f.children[0].label, ParseNode::Input(tok!("a")));

        // T' -> ε
        let inner_tp = &inner_t.children[1];
        assert_eq!(inner_tp.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert!(inner_tp.children.is_empty());

        // E' -> + T E'
        assert_eq!(inner_ep.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 1 }));
        assert_eq!(inner_ep.children.len(), 3);

        // '+'
        assert_eq!(inner_ep.children[0].label, ParseNode::Input(tok!("+")));
        assert!(inner_ep.children[0].children.is_empty());

        // T -> F T' の F -> a
        let inner_ep_t = &inner_ep.children[1];
        assert_eq!(inner_ep_t.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 0 }));
        assert_eq!(inner_ep_t.children.len(), 2);
        let inner_ep_t_f = &inner_ep_t.children[0];
        assert_eq!(inner_ep_t_f.label, ParseNode::Reduction(Nonterminal{ kind: "F", variant: 0 }));
        assert_eq!(inner_ep_t_f.children[0].label, ParseNode::Input(tok!("a")));

        // T' -> ε
        let inner_ep_t_tp = &inner_ep_t.children[1];
        assert_eq!(inner_ep_t_tp.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert!(inner_ep_t_tp.children.is_empty());

        // ')' の確認
        assert_eq!(tp_f.children[2].label, ParseNode::Input(tok!(")")));
        assert!(tp_f.children[2].children.is_empty());

        // T' -> ε
        let tp_tp = &tp.children[2];
        assert_eq!(tp_tp.label, ParseNode::Reduction(Nonterminal{ kind: "T", variant: 1 }));
        assert!(tp_tp.children.is_empty());

        // E' -> ε
        assert_eq!(ep.label, ParseNode::Reduction(Nonterminal{ kind: "E", variant: 1 }));
        assert!(ep.children.is_empty());
      },
      Err(message) => panic!("パース失敗: {message}"),
    }
  }

  #[test]
  fn test_first_first_conflict() {
    // PRGM  -> STMTS
    // STMTS -> STMT sep
    // STMTS -> STMT sep  STMTS
    // STMT  -> DECL eq   VAL
    // STMT  -> id   eq   VAL
    // DECL  -> MOD  type id
    // VAL   -> id
    // VAL   -> num
    // MOD   -> mod
    // MOD   -> epsilon
    let prgm = Nonterminal { kind: "PRGM", variant: 0 };
    let stmts = Nonterminal { kind: "STMTS", variant: 0 };
    let stmt = Nonterminal { kind: "STMT", variant: 0 };
    let decl = Nonterminal { kind: "DECL", variant: 0 };
    let val = Nonterminal { kind: "VAL", variant: 0 };
    let mod_nt = Nonterminal { kind: "MOD", variant: 0 };
    let sep = Terminal { kind: "sep" };
    let eq = Terminal { kind: "eq" };
    let id = Terminal { kind: "id" };
    let r#type = Terminal { kind: "type" };
    let num = Terminal { kind: "num" };
    let r#mod = Terminal { kind: "mod" };
    let grammar = CFG::new(prgm.clone(), vec![
      // PRGM  -> STMTS
      ProductionRule { head: prgm.clone(), body: vec![Symbol::Nonterminal(stmts.clone())] },
      // STMTS -> STMT sep
      ProductionRule { head: stmts.clone(), body: vec![Symbol::Nonterminal(stmt.clone()), Symbol::Terminal(sep.clone())] },
      // STMTS -> STMT sep  STMTS
      ProductionRule { head: stmts.clone(), body: vec![Symbol::Nonterminal(stmt.clone()), Symbol::Terminal(sep.clone()), Symbol::Nonterminal(stmts.clone())] },
      // STMT  -> DECL eq   VAL
      ProductionRule { head: stmt.clone(), body: vec![Symbol::Nonterminal(decl.clone()), Symbol::Terminal(eq.clone()), Symbol::Nonterminal(val.clone())] },
      // STMT  -> id   eq   VAL
      ProductionRule { head: stmt.clone(), body: vec![Symbol::Terminal(id.clone()), Symbol::Terminal(eq.clone()), Symbol::Nonterminal(val.clone())] },
      // DECL  -> MOD  type id
      ProductionRule { head: decl.clone(), body: vec![Symbol::Nonterminal(mod_nt.clone()), Symbol::Terminal(r#type.clone()), Symbol::Terminal(id.clone())] },
      // VAL   -> id
      ProductionRule { head: val.clone(), body: vec![Symbol::Terminal(id.clone())] },
      // VAL   -> num
      ProductionRule { head: val.clone(), body: vec![Symbol::Terminal(num.clone())] },
      // MOD   -> mod
      ProductionRule { head: mod_nt.clone(), body: vec![Symbol::Terminal(r#mod.clone())] },
      // MOD   -> epsilon
      ProductionRule { head: mod_nt.clone(), body: vec![] },
    ]);
    let table = create_rule_selector(&grammar);
    assert!(matches!(table, Err(_)));
    if let Err(message) = table {
      assert_eq!(message, "the grammar has first/first conflict".to_string());
    }
  }

  #[test]
  fn test_first_follow_conflict() {
     let expr = Nonterminal { kind: "E", variant: 0 };
    let expr_head = Nonterminal { kind: "E", variant: 1 };
    let term = Nonterminal { kind: "T", variant: 0 };
    let term_head = Nonterminal { kind: "T", variant: 1 };
    let factor = Nonterminal { kind: "F", variant: 0 };
    let open = Terminal { kind: "(" };
    let close = Terminal { kind: ")" };
    let add = Terminal { kind: "+" };
    let mul = Terminal { kind: "x" };
    let a = Terminal { kind: "a" };
    let grammar = CFG::new(expr.clone(), vec![
      // E  -> E' T
      ProductionRule { head: expr.clone(), body: vec![Symbol::Nonterminal(expr_head.clone()), Symbol::Nonterminal(term.clone())] },
      // E' -> T + E'
      ProductionRule { head: expr_head.clone(), body: vec![Symbol::Nonterminal(term.clone()), Symbol::Terminal(add.clone()), Symbol::Nonterminal(expr_head.clone())] },
      // E' -> e
      ProductionRule { head: expr_head.clone(), body: vec![] },
      // T  -> T' F
      ProductionRule { head: term.clone(), body: vec![Symbol::Nonterminal(term_head.clone()), Symbol::Nonterminal(factor.clone())] },
      // T' -> F x T'
      ProductionRule { head: term_head.clone(), body: vec![Symbol::Nonterminal(factor.clone()), Symbol::Terminal(mul.clone()), Symbol::Nonterminal(term_head.clone())] },
      // T' -> e
      ProductionRule { head: term_head.clone(), body: vec![] },
      // F  -> ( E )
      ProductionRule { head: factor.clone(), body: vec![Symbol::Terminal(open.clone()), Symbol::Nonterminal(expr.clone()), Symbol::Terminal(close.clone())] },
      // F  -> a
      ProductionRule { head: factor.clone(), body: vec![Symbol::Terminal(a.clone())] },
    ]);

    let first_sets = first_sets_for(&grammar);
    let first_set_expr = &first_sets[&expr];
    assert_eq!(first_set_expr.len(), 2);
    assert!(first_set_expr.contains(&NullableTerminal::Terminal(Terminal { kind: "a" })));
    assert!(first_set_expr.contains(&NullableTerminal::Terminal(Terminal { kind: "(" })));

    let first_set_expr_head = &first_sets[&expr_head];
    assert_eq!(first_set_expr_head.len(), 3);
    assert!(first_set_expr_head.contains(&NullableTerminal::Terminal(Terminal { kind: "a" })));
    assert!(first_set_expr_head.contains(&NullableTerminal::Terminal(Terminal { kind: "(" })));
    assert!(first_set_expr_head.contains(&NullableTerminal::Epsilon));

    let first_set_term = &first_sets[&term];
    assert_eq!(first_set_term.len(), 2);
    assert!(first_set_term.contains(&NullableTerminal::Terminal(Terminal { kind: "a" })));
    assert!(first_set_term.contains(&NullableTerminal::Terminal(Terminal { kind: "(" })));

    let first_set_term_head = &first_sets[&term_head];
    assert_eq!(first_set_term_head.len(), 3);
    assert!(first_set_term_head.contains(&NullableTerminal::Terminal(Terminal { kind: "a" })));
    assert!(first_set_term_head.contains(&NullableTerminal::Terminal(Terminal { kind: "(" })));
    assert!(first_set_term_head.contains(&NullableTerminal::Epsilon));

    let first_set_factor = &first_sets[&factor];
    assert_eq!(first_set_factor.len(), 2);
    assert!(first_set_factor.contains(&NullableTerminal::Terminal(Terminal { kind: "a" })));
    assert!(first_set_factor.contains(&NullableTerminal::Terminal(Terminal { kind: "(" })));

    let follow_sets = follow_sets_for(&grammar, &first_sets);
    let follow_set_expr = &follow_sets[&expr];
    assert_eq!(follow_set_expr.len(), 1, "actual={follow_set_expr:?}");
    assert!(follow_set_expr.contains(&Terminal{kind:")"}));

    let follow_set_expr_head = &follow_sets[&expr_head];
    assert_eq!(follow_set_expr_head.len(), 2);
    assert!(follow_set_expr_head.contains(&Terminal{kind:"("}), "follow_set_expr_head={follow_set_expr_head:?}");
    assert!(follow_set_expr_head.contains(&Terminal{kind:"a"}));

    let follow_set_term = &follow_sets[&term];
    assert_eq!(follow_set_term.len(), 2, "actual={follow_set_term:?}");
    assert!(follow_set_term.contains(&Terminal{kind:")"}));
    assert!(follow_set_term.contains(&Terminal{kind:"+"}));

    let follow_set_term_head = &follow_sets[&term_head];
    assert_eq!(follow_set_term_head.len(), 2);
    assert!(follow_set_term_head.contains(&Terminal{kind:"("}));
    assert!(follow_set_term_head.contains(&Terminal{kind:"a"}));

    let follow_set_factor = &follow_sets[&factor];
    assert_eq!(follow_set_factor.len(), 3);
    assert!(follow_set_factor.contains(&Terminal{kind:"+"}));
    assert!(follow_set_factor.contains(&Terminal{kind:"x"}));
    assert!(follow_set_factor.contains(&Terminal{kind:")"}));

    let body = vec![Symbol::Nonterminal(term.clone()), Symbol::Terminal(add.clone()), Symbol::Nonterminal(expr_head.clone())];
    let k = first_seq(&body, &first_sets);
    println!("first_seq(T + E') = {k:?}");

    let table = create_rule_selector(&grammar);
    if let Ok(tbl) = &table {
      for (nonterminal, hash_map) in tbl {
        println!("Nonterminal {nonterminal:?}:");
        for (nullable_terminal, production_rule) in hash_map {
          println!("    {nullable_terminal:?}: {production_rule:?}");
        }
      }
    }
    assert!(matches!(table, Err(_)));
    if let Err(message) = table {
      assert_eq!(message, "the grammar has first/follow conflict".to_string());
    }
  }
}

おまけ - バックトラックのある再帰降下法

ここまででは、形式文法に親しんでさえいれば簡単な、しかしお行儀のよいアルゴリズムを扱っていた.
つまり、入力を先頭から順に、ストリームとして読んでいくようなアルゴリズムだった. このようなものを予言的パーサ (predictive parser) と呼ぶ. (日本語訳は予測型パーサの方が一般的かもしれない)
一方で、入力を行きつ戻りつしながら処理する、よりナイーブな、力任せの再帰降下法も考えられる.
以下ではそれぞれ、予言的な再帰降下法、バックトラックのある再帰降下法と呼ぶことにしよう.
n.b. 以下で示すような、再帰で行きつ戻りつする様をバックトラックと呼ぶ.

まず上の方で書いた予言的な再帰降下法から一部を抜粋する.

予言的な再帰降下法(抜粋)

// F  -> ( E )
// F  -> a
fn factor(input: &Vec<Token<&'static str>>, position: &mut usize) -> Result<Tree<ParseNode<&'static str>>, String> {
  if *position < input.len() {
    if input[*position].kind == "(" {
      // F  -> ( E )
      let open = try_consume(input, position, "(")?;
      let e = expr(input, position)?;
      let close = try_consume(input, position, ")")?;
      Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "F", variant: 0 }), vec![open, e, close]))
    } else if input[*position].kind == "a" {
      // F  -> a
      let a = try_consume(input, position, "a")?;
      Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "F", variant: 0 }), vec![a]))
    } else {
      Err(format!("unexpected token: {actual}", actual = input[*position].kind))
    }
  } else {
    Err("all of input is consumed.".to_string())
  }
}

次に、エラー情報を除いて同等の再帰降下法を示す.

よりナイーブな再帰降下法(一部)

// F  -> ( E )
// F  -> a
fn factor(input: &Vec<Token<&'static str>>, position: &mut usize) -> Result<Tree<ParseNode<&'static str>>, String> {
  let save = *position;
  if let Ok(tree) = factor_as_open_expr_close(input, position) {
    return Ok(tree);
  }
  *position = save;
  factor_as_a(input, position)
}

fn factor_as_open_expr_close(input: &Vec<Token<&'static str>>, position: &mut usize) -> Result<Tree<ParseNode<&'static str>>, String> {
  // F  -> ( E )
  let open = try_consume(input, position, "(")?;
  let e = expr(input, position)?;
  let close = try_consume(input, position, ")")?;
  Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "F", variant: 0 }), vec![open, e, close]))
}

fn factor_as_a(input: &Vec<Token<&'static str>>, position: &mut usize) -> Result<Tree<ParseNode<&'static str>>, String> {
  // F  -> a
  let a = try_consume(input, position, "a")?;
  Ok(Tree::with_children(ParseNode::Reduction(Nonterminal { kind: "F", variant: 0 }), vec![a]))
}

fn try_consume(input: &Vec<Token<&'static str>>, position: &mut usize, expected_token_kind: &'static str) -> Result<Tree<ParseNode<&'static str>>, String> {
  if input.len() <= *position {
    Err("all of input is consumed.".to_string())
  } else if input[*position].kind == expected_token_kind {
    let leaf = Tree::new(ParseNode::Input(input[*position].clone()));
    *position = *position + 1;
    Ok(leaf)
  } else {
    Err(format!("expected {expected_token_kind}, but found {actual}", actual = input[*position].kind))
  }
}

バックトラックのある再帰降下法では、factor の中で入力の先頭を確かめるようなことはしない.
まずは $F \rightarrow (\ E\ )$ が適用されるものと断定して、factor_as_open_expr_close を呼び出してしまう.
factor_as_open_expr_close がエラーになれば、position を元に戻して、素知らぬ顔で factor_as_a を呼び出す.
実際に input を参照するのは try_consume に限られるから、予言的な再帰降下法よりも書きやすいように思われるかもしれない.
それに、バックトラックのある再帰降下法では理論上左再帰のない任意の文法を解析できる(曖昧さを扱えるかは別として).
しかしながら、いくつかの難点ゆえに使われることはあまりない. 大きなところでは、

(packrat という処方薬があるにはあるが) バックトラックのあるアルゴリズムは基本的に遅い
(LL(k) でない文法や $\epsilon$ 規則を含む文法を扱うとき) それぞれの文法をどの順番で呼び出すかは自明でない
親切なエラー処理が難しい

などがある. 結局きちんと書く手間は予言的な再帰降下法とあまり変わらないし、バックトラックのある再帰降下法をきちんと説明するのはむしろ難しいため、おまけとした.