はじめに
これは構文解析手法に関するまとめの第3回です.
用語や記号、関数などは第1回の導入編を参照してください.
一応簡単な正常系を使って動くことだけは確認していますが、重大な誤りを含むコードを掲載している可能性はあります. ご注意ください.
一般の文脈自由言語
LL(1) 構文解析では LL(1) 文法しか扱えないのだった. しかし一般の文脈自由言語の中には、LL(1) 文法で表せないものもある.
そのような言語ないし文法を扱えるようなアルゴリズムについても考える必要がある場面もだろう. しかしまずは、そうしたものが持つ曖昧さについて見ていかなければならない.
言語ないし文法の曖昧さ
生成規則 $E \rightarrow E + E$ から文法記号列 $E + E + E$ を導出することを考える.
このとき、構文木としては次の二種類があり得る.
$(E + E) + E$ に相当する木:
$E + (E + E)$ に相当する木:
$L(G)$ がこのように複数の構文木を持つ文を持つとき、文法 $G$ は曖昧であるという.
特に、任意の弱等価な文法が曖昧であるとき、言語 $L(G)$ は(本質的に)曖昧な言語であるという.
前回見た再帰降下法ないし LL(1) はそもそも曖昧な文法を扱えないから問題とならなかったが、曖昧な文法を用いて構文解析をした結果は複数の木になりうる. これを構文森などと言う. Vec<Tree<ParseNode>> でもいいのだが冗長であるため、通常は非巡回有向グラフ (Acyclic Directed Graph, DAG) を使う. 実用的には後の処理での扱いやすさを考え、Shared Packed Parse Tree (共有圧縮構文森？, SPPF) として表現されることも多い.
今回の関心はアルゴリズムであってデータ構造ではないから、単純な DAG を使用する.
SPPF に関心がある場合は、Lark のサイトにある解説 (ここ) などを参照されたい.
DAG で表された $E+E+E$ の構文森:
そこで、DAG の簡単な実装を書いておこう.
DAG の実装例
DAG を使う理由を奪うようではあるが、木のリストに変換できるようにもしている.
DAG 上で入次数が 0 である頂点を根と呼んでいいものかは分からないが、フィールド名は roots としている.
dag.rs
use std::rc::Rc;
use crate::tree::Tree;
#[derive(Debug)]
pub struct Node<T> {
pub label: T,
pub nexts: Vec<Rc<Node<T>>>,
}
impl<T> Node<T> {
pub fn new(label: T) -> Self {
Node {
label,
nexts: Vec::new(),
}
}
}
#[derive(Debug)]
pub struct DAG<T> {
pub roots: Vec<Rc<Node<T>>>,
}
impl<T> DAG<T> {
pub fn new() -> Self {
DAG { roots: Vec::new() }
}
pub fn to_trees(&self) -> Vec<Tree<&T>> {
fn dfs<T>(node: &Rc<Node<T>>) -> Tree<&T> {
let mut children = Vec::new();
for ch in &node.nexts {
children.push(dfs(ch));
}
Tree::with_children(&node.label, children)
}
let mut trees = Vec::new();
for root in &self.roots {
trees.push(dfs(root));
}
trees
}
}
CYK 構文解析
CYK は、J. Cocke と Younger[1967]、またそれとは独立に嵩[1967] によって発明された単純な構文解析手法である.
それは、チョムスキー標準形 (Chomsky Normal Form, CNF) というものを利用するから、まずはこれについて見ていこう.
チョムスキー標準形 (Chomsky Normal Form, CNF)
CNF は、(現代的な) 生成文法の生みの親である N. Chomsky によって定められた.
文法 $G = (N, \Sigma, S, P)$ が以下を満たすとき、チョムスキー標準形であると言う.
- すべての生成規則 $A \rightarrow \alpha \in P$ が次のいずれかの形である.
ここで、$S \rightarrow \epsilon \in P$ であるならば、$B \ne S \wedge C \ne S$- $A \rightarrow B C$
- $A \rightarrow a$
- $S \rightarrow \epsilon$
- (導入で話した通りこの記事では全体的に前提としているが、) 無用な文法記号を含まない.
より狭めて、$\epsilon{-}\text{free}$ である (i.e. $S$ を含むすべての非終端記号 $A$ について、$A \rightarrow \epsilon$ が $P$ に含まれない) ことを加える定義もあるが、ここでは上の定義を採用する.
任意の文脈自由文法 $G$ に対して、弱等価な (i.e. $L(G) = L(G')$ であるような) チョムスキー標準形の文法 $G'$ が存在することが知られている.
この記事では入力がチョムスキー標準形であることを前提に CYK を書くため、一般の文脈自由文法 $G$ から 弱等価なチョムスキー標準形 $G'$ を得るアルゴリズムについては扱わない. 関心がある場合は『オートマトン 言語理論 計算論 I [第二版]』などを参照してほしい.
コード例
CNF を表現するためのコード例を以下に示す.
cyk.rs
// CNF への変換処理は書かないが、CNF を表現するクラスは作っておく
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Single<'a, T> { head: &'a Nonterminal<T>, body: &'a Terminal<T> }
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Pair<'a, T> { head: &'a Nonterminal<T>, body: (&'a Nonterminal<T>, &'a Nonterminal<T>) }
#[derive(Debug, Clone, PartialEq, Eq)]
struct CNF<'a, T>
where T: Hash + Eq + Clone
{
grammar: &'a CFG<T>,
singles: Vec<Single<'a, T>>,
pairs: Vec<Pair<'a, T>>,
nullable: bool,
}
impl<'a, T> CNF<'a, T>
where T: Hash + Eq + Clone + Debug
{
fn try_new(grammar: &'a CFG<T>) -> Result<Self, String> {
let mut nullable = false;
let mut singles = Vec::new();
let mut pairs = Vec::new();
let mut s_in_body = false;// S が生成規則の本体に現れるか
for rule in &grammar.rules {
match rule.body.as_slice() {
[] => {
if rule.head != grammar.start {
return Err(format!("grammar is not cnf. vaiolating rule = {rule:?}"));
}
nullable = true;
},
[Symbol::Terminal(terminal)] => {
singles.push(Single { head: &rule.head, body: &terminal });
},
[Symbol::Nonterminal(b), Symbol::Nonterminal(c)] => {
pairs.push(Pair { head: &rule.head, body: (&b, &c) });
s_in_body |= *b == grammar.start || *c == grammar.start;
},
_ => return Err(format!("grammar is not cnf. vaiolating rule = {rule:?}"))
}
}
if nullable && s_in_body {
return Err(format!("grammar is not cnf. L(G) is nullable, S appears in a rule body"));
}
Ok(CNF { grammar, singles, pairs, nullable })
}
}
所属問題 (membership problem)
構文解析の目的は、記号列 $w$ が文法 $G$ から生成できる場合に、対応する構文木を構築することにある.
しかしまずは、より簡単な問題、つまり記号列 $w$ が文法 $G$ から生成できるかどうかという問題を考えよう.
これを所属問題 (membership problem)、あるいは決定問題 (decision problem) と言う.
所属問題と CYK
文法が CNF で与えられることを前提にすれば、CYK は、(主として競技プログラミングの文脈で) 俗に区間 DP などと呼ばれる動的計画法に過ぎない.
空でない記号列 $w$ が CNF である文法 $G$ から生成できるかどうかは、次の漸化式を考えることによって確かめられる.
\begin{align*}
\text{DP}_{l,r,A} =& w[l..r) \in L(G|_A) \\
=& \begin{cases}
A \rightarrow w_l \in P & \text{if $r = l + 1$} \\
\bigvee_{m \in (l..r) } \bigvee_{ A \rightarrow B\ C } ( \text{DP}_{l,m,B} \wedge \text{DP}_{m,r,C} ) & \text{otherwise}
\end{cases}
\end{align*}
ここで最終的な結果は、$w \in L(G) \Leftrightarrow \text{DP}_{0, |w|, S}$ である.
ただしここで、$(a .. b) = \lbrace n \mid a \lt n \lt b, n \in \mathbb{N} \rbrace$, $w_i = w[i..i+1)$
また同じことだが、次のように定めることもできる.
\begin{align*}
\text{DP}_{l,r} =& \{ A \mid w[l..r) \in L(G|_A) \} \\
=& \begin{cases}
\{ A \mid A \rightarrow w_l \in P\} & \text{if $r = l + 1$} \\
\bigcup_{m \in (l..r) } \{ A \mid A \rightarrow B\ C \in P, B \in \text{DP}_{l,m}, C \in \text{DP}_{m,r} \} & \text{otherwise}
\end{cases}
\end{align*}
ここで最終的な結果は、$w \in L(G) \Leftrightarrow S \in \text{DP}_{0, |w|}$ である.
n.b. $w = \epsilon$ である場合、計算をすることなく、生成規則 $S \to \epsilon$ があるかどうかを見ればよい.
簡単に数式のイメージを書くと次のようなことだ.
CYK で使用する漸化式のイメージ
長さ 1 の記号列 w[i..i+1) が生成規則 A -> a によって生成されるかを調べたい場合は、単純にその終端記号同士を比較すればよい.
長さ 2 以上の記号列の例として w = a b c d e が生成規則 S -> A B によって生成されるかを調べたい場合、次のすべての可能性を考慮すればよい.
w[0..1) が A に還元され、かつ w[1..5) が B に還元される.
w[0..2) が A に還元され、かつ w[2..5) が B に還元される.
w[0..3) が A に還元され、かつ w[3..5) が B に還元される.
w[0..4) が A に還元され、かつ w[4..5) が B に還元される.
より一般に、長さ 2 以上の記号列 w[l..r) が生成規則 A -> B C によって生成されるかを調べたい場合はこうだ.
n.b. 1 (いち) と l (エル) の違いに注意
w[l..l+1) が B に還元され、かつ w[l+1..r) が C に還元される.
w[l..l+2) が B に還元され、かつ w[l+2..r) が C に還元される.
: : :
w[l..r-2) が B に還元され、かつ w[r-2..r) が C に還元される.
w[l..r-1) が B に還元され、かつ w[r-1..r) が C に還元される.
CNF の場合すべての生成規則の本体は丁度ひとつの終端記号、あるいは丁度ふたつの非終端記号を持つから、考慮すべきものは上に書いたものですべてである.
CYK のアルゴリズムは、これらを適切な順序で (i.e. 区間の長さが短いものから順に) 調べていくものである.
- 長さ 1 の区間について、
- $w[0..1)$ がどの非終端記号に還元されるかを調べる
- $w[1..2)$ がどの非終端記号に還元されるかを調べる
- : : :
- $w[|w|-2..|w|-1)$ がどの非終端記号に還元されるかを調べる
- $w[|w|-1..|w|)$ がどの非終端記号に還元されるかを調べる
- 長さ 2 の区間について、
- $w[0..2)$ がどの非終端記号に還元されるかを調べる
- $w[1..3)$ がどの非終端記号に還元されるかを調べる
- : : :
- $w[|w|-3..|w|-1)$ がどの非終端記号に還元されるかを調べる
- $w[|w|-2..|w|)$ がどの非終端記号に還元されるかを調べる
- : : :
- 長さ $|w|$ の区間について、
- $w = w[0..|w|)$ がどの非終端記号に還元されるかを調べる
時間計算量を雑に考えると、組 $(l, r)$ は $\Theta(|w|^2)$、その各組に対して $m$ は $\Theta(|w|)$、それを生成規則の数 $\Theta(|P|)$ だけ計算するから、すべて掛け合わせて $\Theta(|w|^3 \ |P|)$ となる.
実装例
集合を使う方法で実装した例を示す.
cyk.rs
// 入力は一般の(i.e. S ⇒* epsilon であり得る) CNF であるものとする
fn membership_cyk<'a, T>(
input: &Vec<Token<T>>,
grammar: &CNF<'a, T>
) -> bool
where T: Hash + Eq + Clone + Debug,
{
let n = input.len();
if n == 0 {
return grammar.nullable;
}
// dp[l, r] := { A | L(G|_A) contains input[l..r) }
// n.b. dp table size: n x (n+1)
let mut dp: HashMap<usize, HashMap<usize, HashSet<&Nonterminal<T>>>> = HashMap::new();
// 列が左から右へ伸びることを前提とした変数名だが、妥当だろうか？
// けれどこの文自体が左から右への横書きだし、start, end みたいにするほどでもないように思う.
// でも LL や LR みたいな命名は、右から左へ書いたり専ら縦書きを使う文化圏でどう思われているのだろう... .
// CYK を書きながら考えることではないな.
// span = 1
for left in 0..n {
let mut row= HashMap::new();
let mut cell = HashSet::new();
let right = left + 1;
for &Single { head, body } in &grammar.singles {
if input[left].kind == body.kind {
cell.insert(head);
}
}
row.insert(right, cell);
dp.insert(left, row);
}
// span in [2..n]
for span in 2..=n {
for left in 0..=(n-span) {
let mut cell = HashSet::new();
let right = left + span;
for mid in (left+1)..right {
for &Pair { head: a, body: (b, c) } in &grammar.pairs {
if dp[&left][&mid].contains(b) && dp[&mid][&right].contains(c) {
cell.insert(a);
}
}// loop for Pair { head: a, body: (b, c) } in &grammar.pairs
}// loop for mid in (left..right)
dp.get_mut(&left).unwrap().insert(right, cell);
}// loop for left in [0..(n-span)]
}// loop for span in [2..n]
dp[&0][&n].contains(&grammar.grammar.start)
}
テストコード(簡単な動作確認)
cyk.rs
#[cfg(test)]
mod tests {
use super::*;
use crate::grammar::ProductionRule;
use crate::{tok, util::{TextPosition}};
#[test]
fn accept_test_balanced_parens() {
// L(G) = { a^n b^n | n >= 1 }
// S -> A B
// A -> a
// B -> A C | b
// C -> B b
let s = Nonterminal { kind: "S", variant: 0 };
let a = Nonterminal { kind: "A", variant: 0 };
let b = Nonterminal { kind: "B", variant: 0 };
let c = Nonterminal { kind: "C", variant: 0 };
let sm_a = Terminal { kind: "a" };
let sm_b = Terminal { kind: "b" };
let grammar = CFG::new(s.clone(), vec![
// S -> A B
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(a.clone()), Symbol::Nonterminal(b.clone())] },
// A -> a
ProductionRule { head: a.clone(), body: vec![Symbol::Terminal(sm_a)] },
// B -> A C
ProductionRule { head: b.clone(), body: vec![Symbol::Nonterminal(a.clone()), Symbol::Nonterminal(c.clone())] },
// B -> b
ProductionRule { head: b.clone(), body: vec![Symbol::Terminal(sm_b.clone())] },
// C -> B B
ProductionRule { head: c.clone(), body: vec![Symbol::Nonterminal(b.clone()), Symbol::Nonterminal(b.clone())] },
]);
let cnf = CNF::try_new(&grammar).unwrap();
assert!(cyk_test_accept(&vec![
tok!("a"),
tok!("b"),
], &cnf));
assert!(cyk_test_accept(&vec![
tok!("a"),
tok!("a"),
tok!("b"),
tok!("b"),
], &cnf));
assert!(cyk_test_accept(&vec![
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("b"),
tok!("b"),
tok!("b"),
tok!("b"),
tok!("b"),
tok!("b"),
], &cnf));
assert!(!cyk_test_accept(&vec![// shall be NOT accepted
tok!("a"),// 0
tok!("a"),// 1
tok!("a"),// 2
tok!("a"),// 3
tok!("a"),// 4
tok!("a"),// 5
tok!("b"),// 5
tok!("b"),// 4
tok!("b"),// 3
tok!("b"),// 2
tok!("b"),// 1
// tok!("b"),// 0
], &cnf));
assert!(!cyk_test_accept(&vec![// shall be NOT accepted
// tok!("a"),// 0
tok!("a"),// 1
tok!("a"),// 2
tok!("a"),// 3
tok!("a"),// 4
tok!("a"),// 5
tok!("b"),// 5
tok!("b"),// 4
tok!("b"),// 3
tok!("b"),// 2
tok!("b"),// 1
tok!("b"),// 0
], &cnf));
}
#[test]
fn accept_test_palindrome() {
// L(G) = { w w^R | w in Sigma^+ }
// S -> A A
// S -> B B
// S -> S1 A
// S -> S2 B
// S1 -> A S
// S2 -> B S
// A -> a
// B -> b
let s = Nonterminal { kind: "S", variant: 0 };
let s1 = Nonterminal { kind: "S", variant: 1 };
let s2 = Nonterminal { kind: "S", variant: 2 };
let a = Nonterminal { kind: "A", variant: 0 };
let b = Nonterminal { kind: "B", variant: 0 };
let sm_a = Terminal { kind: "a" };
let sm_b = Terminal { kind: "b" };
let grammar = CFG::new(s.clone(), vec![
// S -> A A
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(a.clone()), Symbol::Nonterminal(a.clone())] },
// S -> B B
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(b.clone()), Symbol::Nonterminal(b.clone())] },
// S -> S1 A
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(s1.clone()), Symbol::Nonterminal(a.clone())] },
// S -> S2 B
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(s2.clone()), Symbol::Nonterminal(b.clone())] },
// S1 -> A S
ProductionRule { head: s1.clone(), body: vec![Symbol::Nonterminal(a.clone()), Symbol::Nonterminal(s.clone())] },
// S2 -> B S
ProductionRule { head: s2.clone(), body: vec![Symbol::Nonterminal(b.clone()), Symbol::Nonterminal(s.clone())] },
// A -> a
ProductionRule { head: a.clone(), body: vec![Symbol::Terminal(sm_a)] },
// B -> b
ProductionRule { head: b.clone(), body: vec![Symbol::Terminal(sm_b.clone())] },
]);
let cnf = CNF::try_new(&grammar).unwrap();
assert!(cyk_test_accept(&vec![
tok!("a"),
tok!("a"),
], &cnf));
assert!(cyk_test_accept(&vec![
tok!("b"),
tok!("b"),
], &cnf));
assert!(cyk_test_accept(&vec![
tok!("a"),// 0
tok!("b"),// 1
tok!("b"),// 2
tok!("b"),// 3
tok!("a"),// 4
tok!("a"),// 5
tok!("a"),// 5
tok!("a"),// 4
tok!("b"),// 3
tok!("b"),// 2
tok!("b"),// 1
tok!("a"),// 0
], &cnf));
assert!(!cyk_test_accept(&vec![// shall be NOT accepted
tok!("a"),// 0
tok!("b"),// 1
tok!("b"),// 2
tok!("b"),// 3
tok!("a"),// 4
tok!("a"),// 5
tok!("a"),// 5
tok!("a"),// 4
tok!("b"),// 3
tok!("b"),// 2
tok!("b"),// 1
// tok!("a"),// 0
], &cnf));
assert!(!cyk_test_accept(&vec![// shall be NOT accepted
// tok!("a"),// 0
tok!("b"),// 1
tok!("b"),// 2
tok!("b"),// 3
tok!("a"),// 4
tok!("a"),// 5
tok!("a"),// 5
tok!("a"),// 4
tok!("b"),// 3
tok!("b"),// 2
tok!("b"),// 1
tok!("a"),// 0
], &cnf));
}
#[test]
fn accept_test_nullable() {
// L(G) = { a^n | n >= 0 }
// S -> epsilon
// S -> A T
// S -> a
// T -> T A
// T -> a
// A -> a
let s = Nonterminal { kind: "S", variant: 0 };
let t = Nonterminal { kind: "T", variant: 0 };
let a = Nonterminal { kind: "A", variant: 0 };
let sm_a = Terminal { kind: "a" };
let grammar = CFG::new(s.clone(), vec![
// S -> epsilon
ProductionRule { head: s.clone(), body: vec![] },
// S -> A T
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(a.clone()), Symbol::Nonterminal(t.clone())] },
// S -> a
ProductionRule { head: s.clone(), body: vec![Symbol::Terminal(sm_a.clone())] },
// T -> T A
ProductionRule { head: t.clone(), body: vec![Symbol::Nonterminal(t.clone()), Symbol::Nonterminal(a.clone())] },
// T -> a
ProductionRule { head: t.clone(), body: vec![Symbol::Terminal(sm_a.clone())] },
// A -> a
ProductionRule { head: a.clone(), body: vec![Symbol::Terminal(sm_a.clone())] },
]);
let cnf = CNF::try_new(&grammar).unwrap();
assert!(membership_cyk(&vec![], &cnf));
assert!(membership_cyk(&vec![
tok!("a"),
], &cnf));
assert!(membership_cyk(&vec![
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
], &cnf));
assert!(!membership_cyk(&vec![// shall be NOT accepted
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("b"),// unexpected token
tok!("a"),
tok!("a"),
tok!("a"),
], &cnf));
}
}
CYK と構文木
CYK は所属問題のためのアルゴリズムであるが、ついでに構文木(あるいは構文森)を構築することもできる.
構文森を返す実装を示そう.
HashSet<&Nonterminal<T>> を HashMap<&Nonterminal<T>, Vec<Rc<Node<ParseNode<T>>>>> に置き換えて各所をそれに合わせた位で、上で書いた membership_cyk と大きくは変わっていない.
cyk.rs
// 入力は一般の(i.e. S ⇒* epsilon であり得る) CNF であるものとする
pub fn parse_cyk<'a, T>(
input: &Vec<Token<T>>,
grammar: &CNF<'a, T>
) -> Option<DAG<ParseNode<T>>>
where T: Hash + Eq + Clone + Debug,
{
let n = input.len();
if n == 0 {
if grammar.nullable {
let mut dag = DAG::new();
let node = Node::new(ParseNode::Reduction(grammar.grammar.start.clone()));
dag.roots.push(Rc::new(node));
return Some(dag);
} else {
return None;
}
}
// dp[l, r] := { A | L(G|_A) contains input[l..r) }
// n.b. dp table size: n x (n+1)
let mut dp: HashMap<usize, HashMap<usize, HashMap<&Nonterminal<T>, Vec<Rc<Node<ParseNode<T>>>>>>> = HashMap::new();
// span = 1
for left in 0..n {
let mut row= HashMap::new();
let mut cell = HashMap::new();
let right = left + 1;
for &Single { head, body } in &grammar.singles {
if input[left].kind == body.kind {
let node = Node::new(ParseNode::Input(input[left].clone()));
cell.insert(head, vec![Rc::new(node)]);
}
}
row.insert(right, cell);
dp.insert(left, row);
}
// span in [2..n]
for span in 2..=n {
for left in 0..=(n-span) {
let mut cell = HashMap::new();
let right = left + span;
for mid in (left+1)..right {
for &Pair { head: a, body: (b, c) } in &grammar.pairs {
if let Some(lchs) = dp[&left][&mid].get(b) {
if let Some(rchs) = dp[&mid][&right].get(c) {
for lch in lchs {
for rch in rchs {
let mut node = Node::new(ParseNode::Reduction(a.clone()));
node.nexts.push(Rc::clone(lch));
node.nexts.push(Rc::clone(rch));
cell.entry(a).or_insert_with(Vec::default).push(Rc::new(node));
}// for rch in rchs
}// for lch in lchs
}
}
}// loop for Pair { head: a, body: (b, c) } in &grammar.pairs
}// loop for mid in (left..right)
dp.get_mut(&left).unwrap().insert(right, cell);
}// loop for left in [0..(n-span)]
}// loop for span in [2..n]
dp[&0][&n].get(&grammar.grammar.start).map(|roots| {
let mut dag = DAG::new();
for r in roots {
dag.roots.push(Rc::clone(r));
}
dag
})
}
Earley 構文解析
CYK 法は実質的に任意の文脈自由言語に関する所属問題を解決できる重要なアルゴリズムだが、しかし任意の文脈自由文法を扱えるわけではない. 使いたいときには CNF という (クセのある) 文法に変換しなければならない. 加えて、区間DP である以上避けられないのだが、どんなに単純な文法であっても律儀に4重ループ (上の実装例で言えば、区間の幅 span、調べる区間の左端 left、区間の区切り位置 mid、そして生成規則 Pair { head: a, body: (b, c) } からなる) を回さなければならない.
CYK の簡潔さは魅力的だが、より汎用的で、最良時間計算量のオーダーがより優秀な手法があればなおよい. その古典的な例が Earley 法である.
Earley 法の発想
CYK 法が CNF を要求していたのはなぜか？ 部分列を左右ふたつに分けることによって区間DP (あるいは分割統治法) を機能させるためだ.
しかし、$A \to B\ C$ から $B$ と $C$ を得ることだけが分割だろうか？ CYK 法でも入力 $w$ の任意の部分列 $w[l..r)$ について任意の分割点 $m$ を考えたではないか.
例えば、記号列を先頭から末尾にかけて順に読んでいく場合、「既に読んだ部分」と「まだ読んでいない」部分のふたつに分けられるのではないか？
文法アイテム、Earley アイテム
そこで、生成規則に従って読み進めている途中の状態を表すことについて考えよう. 現在の栞の位置をドット ($.$ もしくは $\cdot$) で表すこととする.
例えば $A \to B\ .\ C\ D\ E$ は、現在 $A$ に還元できそうな部分を読んでいて、$B$ までは還元できた、次は $C$ が還元されるはずだ、という状態を表している.
$A \to B \ C\ D\ E\ .$ は、現在 $A$ に還元できそうな部分を読んでいて、$E$ までは還元できた、つまり結局 $A$ は見事還元されるのだ、という状態を表している.
生成規則 $A \to \epsilon$ については $A \to .$ という状態しか存在しないものとする. つまり、$\epsilon$ は現れたその瞬間に還元されている.
この、本体にドットを持つ生成規則を文法アイテムという. Earley 法では、文法アイテムに加えて、入力された記号列上の位置を組合せた Earley アイテムというものを使うこととなる.
例えば、$(A \to B\ .\ C\ D\ E, 12)$ というタプルは、非終端記号 $A$ に還元できるかどうか読み進めている途中で、$w[12..]$ の接頭辞が $C$ に還元されることを期待している、という状態を表現する.
util.rs
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct GrammarItem<T>
where T: Clone
{
pub rule: ProductionRule<T>,
pub dot_position: usize
}
impl<T> GrammarItem<T>
where T: Clone
{
pub fn next_symbol(&self) -> Option<&Symbol<T>> {
self.rule.body.get(self.dot_position)
}
pub fn is_completed(&self) -> bool {
self.rule.body.len() == self.dot_position
}
pub fn advance(&self) -> Option<Self> {
// None を返す代わりに panic! してもよい.
if self.is_completed() { return None; }
Some(GrammarItem { rule: self.rule.clone(), dot_position: self.dot_position + 1 })
}
}
earley.rs
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct EarleyItem<T>
where T: Clone
{
pub item: GrammarItem<T>,
pub pivot: usize
}
予測、読込、完了
Earley 法では、この Earley アイテムによって状態を記録しながら記号列を読み進めていく.
その過程で必要な操作は予測(predict)、読込(scan)、完了(complete)の三種類である(各単語に関する定訳があるものかは知らない).
- 予測 (predict)
現在入力を $w_{11}$ まで読み込み、$(A \to B\ .\ C\ D\ E, 6)$ という状態を持っているとしよう. たった今、$B$ が還元されたところだ.
このとき、現在位置から先、つまり $w[12..]$ の接頭辞は $C$ に還元されることが期待されるから、$(C \to \alpha, 12)$ という状態を追加しなければならない. - 読込 (scan)
現在入力を $w_{11}$ まで読み込み、$(A \to B\ .\ a\ C\ D, 6)$ という状態を持っているとしよう. たった今、$B$ が還元されたところだ.
このとき、現在位置から先、つまり $w[12..]$ の接頭辞は $a$ であることが期待されるから、もしも $w_{12} = a$ であれば、$w_{12}$ まで読み込んだ際の状態として、$(A \to B\ a\ .\ C\ D, 6)$ を追加しなければならない. - 完了 (complete)
現在入力を $w_{18}$ まで読み込み、$(C \to \beta\ ., 12)$ という状態を持っているとしよう. 今まさに、$C$ を還元しなければならない.
このとき、Earley アイテムで持っている位置、つまり $w_{12}$ まで読み込んだ際の状態の中に、$(A \to \alpha\ .\ C\ \beta, 6)$ というものがあれば、ドットをひとつ進めて $(A \to \alpha\ C\ .\ \beta, 6)$ を追加しなければならない.
ここでは上の呼び名を使うが、scan、complete はそれぞれ、LR 系で使われる用語に合わせるためか shift、reduce と呼ばれていることもあるようだ.
また、Earley による原典 (An efficient context-free parsing algorithm) ではそれぞれ predictor、scanner、completer とされている. 操作の名前が名詞である違和感に耐えられず動詞形にしているが、この命名が重要であったのであれば申し訳ない.
デモンストレーション
長さが偶数である回文を生成する次の文法 $G$ と、入力 $w = abba$ を使って Earley 法をトレースしてみよう. 開始記号は $S'$ である.
\text{文法}\ G = \left\{\begin{align*}
S' \to&\ S \\
S \to&\ a\ a \\
S \to&\ b\ b \\
S \to&\ a\ S\ a \\
S \to&\ b\ S\ b
\end{align*}\right\}
入力 $w_i$ を読んでいる最中の状態からなる集合を $E[i]$ と書くことにしよう.
- (現在位置 = 0) 予測. $(S' \to .\ S, 0)$ から予測する.
$E[0] \cup = { (S \to .\ a\ S\ a, 0), (S \to .\ b\ S\ b, 0), (S \to .\ a\ a, 0), (S \to .\ b\ b, 0) }$ - 予測でも完了でも状態が変化しない. 現在の状態:
$E[0] = { (S' \to .\ S, 0), (S \to .\ a\ a, 0), (S \to .\ a\ S\ a, 0), (S \to .\ b\ S\ b, 0), (S \to .\ b\ b, 0) }$
$E[1] = E[2] = E[3] = E[4] = \varnothing$ - (現在位置 = 0) 読込. $w_{0} = a$ であることに注意して、
$E[1] \cup = { (S \to a\ .\ a, 0) }$ - (現在位置 = 0) 読込. $w_{0} = a$ であることに注意して、
$E[1] \cup = { (S \to a\ .\ S\ a, 0), (S \to a\ .\ a, 0) }$ - (現在位置 = 1) 予測. $(S \to a\ .\ S\ a, 0)$ から予測する.
$E[1] \cup = { (S \to .\ b\ S\ b, 1), (S \to .\ b\ b, 1), (S \to .\ a\ a, 1), (S \to .\ a\ S\ a, 1) }$ - 予測でも完了でも状態が変化しない. 現在の状態:
$E[0] = { (S' \to .\ S, 0), (S \to .\ a\ a, 0), (S \to .\ a\ S\ a, 0), (S \to .\ b\ S\ b, 0), (S \to .\ b\ b, 0) }$
$E[1] = { (S \to .\ a\ S\ a, 1), (S \to a\ .\ S\ a, 0), (S \to .\ b\ b, 1), (S \to .\ a\ a, 1), (S \to .\ b\ S\ b, 1), (S \to a\ .\ a, 0) }$
$E[2] = E[3] = E[4] = \varnothing$
長いので途中は折りたたみ
- (現在位置 = 1) 読込. $w_{1} = b$ であることに注意して、
$E[2] \cup = { (S \to b\ .\ b, 1) }$ - (現在位置 = 1) 読込. $w_{1} = b$ であることに注意して、
$E[2] \cup = { (S \to b\ .\ S\ b, 1), (S \to b\ .\ b, 1) }$ - (現在位置 = 2) 予測. $(S \to b\ .\ S\ b, 1)$ から予測する.
$E[2] \cup = { (S \to .\ b\ S\ b, 2), (S \to .\ b\ b, 2), (S \to .\ a\ a, 2), (S \to .\ a\ S\ a, 2) }$ - 予測でも完了でも状態が変化しない. 現在の状態:
$E[0] = { (S' \to .\ S, 0), (S \to .\ a\ a, 0), (S \to .\ a\ S\ a, 0), (S \to .\ b\ S\ b, 0), (S \to .\ b\ b, 0) }$
$E[1] = { (S \to .\ a\ S\ a, 1), (S \to a\ .\ S\ a, 0), (S \to .\ b\ b, 1), (S \to .\ a\ a, 1), (S \to .\ b\ S\ b, 1), (S \to a\ .\ a, 0) }$
$E[2] = { (S \to .\ a\ a, 2), (S \to .\ b\ S\ b, 2), (S \to b\ .\ S\ b, 1), (S \to b\ .\ b, 1), (S \to .\ b\ b, 2), (S \to .\ a\ S\ a, 2) }$
$E[3] = E[4] = \varnothing$ - (現在位置 = 2) 読込. $w_{2} = b$ であることに注意して、
$E[3] \cup = { (S \to b\ .\ S\ b, 2) }$ - (現在位置 = 2) 読込. $w_{2} = b$ であることに注意して、
$E[3] \cup = { (S \to b\ b\ ., 1), (S \to b\ .\ S\ b, 2) }$ - (現在位置 = 2) 読込. $w_{2} = b$ であることに注意して、
$E[3] \cup = { (S \to b\ b\ ., 1), (S \to b\ .\ b, 2), (S \to b\ .\ S\ b, 2) }$ - (現在位置 = 3) 完了. $(S \to b\ b\ ., 1)$ を完了する. $E[1]$ から $(A \to \alpha\ .\ S\ \beta, i)$ を探し、($A \to \alpha\ S\ .\ \beta, i)$ として追加する.
$E[3] \cup = { (S \to a\ S\ .\ a, 0) }$ - (現在位置 = 3) 予測. $(S \to b\ .\ S\ b, 2)$ から予測する.
$E[3] \cup = { (S \to .\ a\ a, 3), (S \to .\ b\ S\ b, 3), (S \to .\ a\ S\ a, 3), (S \to .\ b\ b, 3) }$ - 予測でも完了でも状態が変化しない. 現在の状態:
$E[0] = { (S' \to .\ S, 0), (S \to .\ a\ a, 0), (S \to .\ a\ S\ a, 0), (S \to .\ b\ S\ b, 0), (S \to .\ b\ b, 0) }$
$E[1] = { (S \to .\ a\ S\ a, 1), (S \to a\ .\ S\ a, 0), (S \to .\ b\ b, 1), (S \to .\ a\ a, 1), (S \to .\ b\ S\ b, 1), (S \to a\ .\ a, 0) }$
$E[2] = { (S \to .\ a\ a, 2), (S \to .\ b\ S\ b, 2), (S \to b\ .\ S\ b, 1), (S \to b\ .\ b, 1), (S \to .\ b\ b, 2), (S \to .\ a\ S\ a, 2) }$
$E[3] = { (S \to a\ S\ .\ a, 0), (S \to .\ b\ S\ b, 3), (S \to b\ .\ b, 2), (S \to b\ .\ S\ b, 2), (S \to b\ b\ ., 1), (S \to .\ a\ S\ a, 3), (S \to .\ a\ a, 3), (S \to .\ b\ b, 3) }$
$E[4] = \varnothing$ - (現在位置 = 3) 読込. $w_{3} = a$ であることに注意して、
$E[4] \cup = { (S \to a\ S\ a\ ., 0) }$ - (現在位置 = 3) 読込. $w_{3} = a$ であることに注意して、
$E[4] \cup = { (S \to a\ .\ S\ a, 3), (S \to a\ S\ a\ ., 0) }$ - (現在位置 = 3) 読込. $w_{3} = a$ であることに注意して、
$E[4] \cup = { (S \to a\ .\ S\ a, 3), (S \to a\ .\ a, 3), (S \to a\ S\ a\ ., 0) }$
- (現在位置 = 4) 予測. $(S \to a\ .\ S\ a, 3)$ から予測する.
$E[4] \cup = { (S \to .\ a\ a, 4), (S \to .\ a\ S\ a, 4), (S \to .\ b\ S\ b, 4), (S \to .\ b\ b, 4) }$ - (現在位置 = 4) 完了. $(S \to a\ S\ a\ ., 0)$ を完了する. $E[0]$ から $(A \to \alpha\ .\ S\ \beta, i)$ を探し、($A \to \alpha\ S\ .\ \beta, i)$ として追加する.
$E[4] \cup = { (S' \to S\ ., 0) }$ - 最終状態:
$E[0] = { (S' \to .\ S, 0), (S \to .\ a\ a, 0), (S \to .\ a\ S\ a, 0), (S \to .\ b\ S\ b, 0), (S \to .\ b\ b, 0) }$
$E[1] = { (S \to .\ a\ S\ a, 1), (S \to a\ .\ S\ a, 0), (S \to .\ b\ b, 1), (S \to .\ a\ a, 1), (S \to .\ b\ S\ b, 1), (S \to a\ .\ a, 0) }$
$E[2] = { (S \to .\ a\ a, 2), (S \to .\ b\ S\ b, 2), (S \to b\ .\ S\ b, 1), (S \to b\ .\ b, 1), (S \to .\ b\ b, 2), (S \to .\ a\ S\ a, 2) }$
$E[3] = { (S \to a\ S\ .\ a, 0), (S \to .\ b\ S\ b, 3), (S \to b\ .\ b, 2), (S \to b\ .\ S\ b, 2), (S \to b\ b\ ., 1), (S \to .\ a\ S\ a, 3), (S \to .\ a\ a, 3), (S \to .\ b\ b, 3) }$
$E[4] = { (S \to a\ S\ a\ ., 0), (S \to .\ b\ b, 4), (S \to a\ .\ a, 3), (S' \to S\ ., 0), (S \to .\ a\ S\ a, 4), (S \to .\ a\ a, 4), (S \to a\ .\ S\ a, 3), (S \to .\ b\ S\ b, 4) }$ - $(S' \to S\ ., 0) \in E[4]$ であるから、$w \in L(G)$ であることが分かった.
所属問題に対する Earley 法
まずは構文木のことを考えず、所属問題を解決することだけを考える.
疑似コード例
生成規則に $S' \to S$ を追加するか、 $S' \to S\ \text{EOS}$ を追加するか、などというところでいくつか別れるだろうが、ここでは $S' \to S$ を追加し、EOS は使わないこととする.
入力: 文法 $G = (N, \Sigma, S, P)$、記号列 $w$
出力: $w \in L(G)$ であるかどうか
- 状態表 $E$ を $[0..|w|] \to \text{「EarleyItem の集合」}$ を初期化する.
- $E[0] = { (S' \to .\ S, 0) }$ とする.
- カーソル $\text{i} \in [0..|w|)$ にわたって以下の処理を行う.
- $E[i]$ が収束するまで、
predictとcompleteを実行する. -
scanを実行する.
- $E[i]$ が収束するまで、
- $E[n]$ が収束するまで、
predictとcompleteを実行する. - $w \in L(G) \iff (S' \to S\ ., 0) \in E[n]$
-
predict:
入力: 状態表 $E$、文法 $G$、カーソル $i$、アイテム $(A \to \alpha\ .\ B\ \beta, j) \in E[i]$
処理: すべての $B \to \gamma \in P$ について、$E[i]$ にアイテム $(B \to .\ \gamma, i)$ を追加する. -
complete:
入力: 状態表 $E$、文法 $G$、カーソル $i$、アイテム $(A \to \alpha\ ., j) \in E[i]$
処理: すべての $(B \to \beta\ .\ A\ \gamma, k) \in E[j]$ について、$E[i]$ にアイテム $(B \to \beta\ A\ .\ \gamma, k)$ を追加する. -
scan:
入力: 状態表 $E$、文法 $G$、カーソル $i$、終端記号 $w_i$
処理: すべての $(A \to \alpha\ .\ w_i\ \beta, k) \in E[j]$ について、$E[i+1]$ にアイテム $(A \to \alpha\ w_i\ .\ \beta, k)$ を追加する.
リファクタリングの余地は大きいが、Earley 法の要点は以上であると理解している.
特に注意すべきバグとしては、手順 1. の初期化で状態表の大きさを間違える、手順 3. で i の範囲を間違えるか、手順 4. を抜かす、といったところだろう.
手順 1. ないし 3. でのバグは、scan で $E[i+1]$ にアクセスする際に範囲外エラーを引き起こす.
手順 4. でのバグは、$(S \to \alpha\ ., 0) \in E[|w|]$ から $(S' \to S\ ., 0)$ が作られないせいで、結果が常に false となってしまう.
後者についてはまた、$S'$ を使わない場合であっても、入力が $P = { S \to A, A \to \epsilon }$、$w = \epsilon$ であるような場合にも同様の問題を引き起こすから、忘れてはならない(自戒).
あとは$w$ 上の位置である pivot と $\alpha$ 上の位置である dot_position を混同しない、というのも注意点である.
手順 4. については complete だけでよいように思われるかもしれないが、入力が $P = { S \to A, A \to \epsilon }$、$w = \epsilon$ であるような場合にはここで predict を実行しなければならない.
アクセスするインデックスのイメージ
E[0] で予測、完了．→ E[0] に書き込み <-- 処理の書き方によってはここが漏れることもある
E[0] で読込．→ E[1] に書き込み
E[1] で予測、完了．→ E[1] に書き込み
E[1] で読込．→ E[2] に書き込み
: : :
E[|w|-2] で予測、完了．→ E[|w|-2] に書き込み
E[|w|-2] で読込．→ E[|w|-1] に書き込み
E[|w|-1] で予測、完了．→ E[|w|-1] に書き込み
E[|w|-1] で読込．→ E[|w|] に書き込み <-- E の大きさを |w| にしているとここで範囲外アクセス
E[|w|] で完了．→ E[|w|] に書き込み <-- これを忘れると正しく判定できない
// <-- ここで「E[|w|] で読込．→ E[|w|+1] に書き込み」を実行しようとすると範囲外アクセス
E[|w|] を使って判定
実装例
earley.rs
pub fn membership_earley<T>(
input: &Vec<Token<T>>,
grammar: &CFG<T>
) -> bool
where T: Hash + Eq + Clone,
{
let n = input.len();
let dummy_variant = grammar.nonterminals.iter()
.filter(|n| n.kind == grammar.start.kind)
.map(|n| n.variant)
.max()
.unwrap() + 1;
let s_prime = Nonterminal { kind: grammar.start.kind.clone(), variant: dummy_variant };
// 状態集合を初期化
let mut table = vec![HashSet::new(); n+1];
table[0].insert(EarleyItem {
item: GrammarItem {
rule: ProductionRule {
head: s_prime.clone(),
body: vec![Symbol::Nonterminal(grammar.start.clone())]
},
dot_position: 0
},
pivot: 0,
});
// 順に読み進めていく
for (i, cur) in input.iter().enumerate() {
predict_and_complete(&mut table, grammar, i);
scan(&mut table, i, cur);
}
predict_and_complete(&mut table, grammar, n);
return table[n].iter()
.filter(|&s| s.item.is_completed())
.any(|s| s.item.rule.head == s_prime);
fn predict_and_complete<T: Hash + Eq + Clone>(table: &mut Vec<HashSet<EarleyItem<T>>>, grammar: &CFG<T>, i: usize) {
loop {
let before_length = table[i].len();
predict(&mut table[i], grammar, i);
complete(table, i);
let after_lenth = table[i].len();
if before_length == after_lenth { break; }
}
}
fn predict<T: Hash + Eq + Clone>(states: &mut HashSet<EarleyItem<T>>, grammar: &CFG<T>, i: usize) {
loop {
// イテレータ使用中は states に要素を追加できないので、一旦 new_items に溜める.
let mut new_items = HashSet::new();
for item in states.iter() {
if let Some(Symbol::Nonterminal(predicted)) = &item.item.next_symbol() {
for rule in &grammar.rules {
if rule.head == *predicted {
new_items.insert(EarleyItem {
item: GrammarItem { rule: rule.clone(), dot_position: 0 },
pivot: i
});
}
}// loop for rule in &grammar.rules
}
}// for item in states.iter()
// new_items の要素を states に入れる.
let before_length = states.len();
states.extend(new_items);
let after_length = states.len();
// 追加前後で大きさが同じであれば収束.
if before_length == after_length { break; }
}// loop while changed
}
fn complete<T: Hash + Eq + Clone>(table: &mut Vec<HashSet<EarleyItem<T>>>, i: usize) {
loop {
// イテレータ使用中は table に要素を追加できないので、一旦 new_items に溜める.
let mut new_items = HashSet::new();
for item in &table[i] {
if item.item.is_completed() {
for item_to_advance in &table[item.pivot] {// table[i] などと書かないように
if let Some(Symbol::Nonterminal(predicted)) = item_to_advance.item.next_symbol() {
if *predicted == item.item.rule.head {
new_items.insert(EarleyItem {
item: item_to_advance.item.advance().unwrap(),
pivot: item_to_advance.pivot
});
}
}
}// loop for item_to_advance in &table[item.pivot]
}
}// loop for item in &table[i]
// new_items の要素を table[i] に入れる.
let before_length = table[i].len();
table[i].extend(new_items);
let after_length = table[i].len();
// 追加前後で大きさが同じであれば収束.
if before_length == after_length { break; }
}// loop while changed
}
fn scan<T: Hash + Eq + Clone>(table: &mut Vec<HashSet<EarleyItem<T>>>, i: usize, symbol: &Token<T>) {
// イテレータ使用中は table に要素を追加できないので、一旦 new_items に溜める.
let mut new_items = HashSet::new();
for item in &table[i] {
if let Some(Symbol::Terminal(expected)) = item.item.next_symbol() {
if expected.kind == symbol.kind {
new_items.insert(EarleyItem {
item: item.item.advance().unwrap(),
pivot: item.pivot
});
}
}
}// loop for item in &table[i]
// new_items の要素を table[i+1] に入れる.
table[i+1].extend(new_items);// table[i] ではないことに注意
}
}
テストコード(簡単な動作確認)
earley.rs
#[cfg(test)]
mod tests {
use super::*;
use crate::grammar::ProductionRule;
use crate::{tok, util::{TextPosition}};
#[test]
fn accept_test_balanced_parens() {
// L(G) = { a^n b^n | n >= 1 }
// S -> A B
// A -> a
// B -> A C | b
// C -> B b
let s = Nonterminal { kind: "S", variant: 0 };
let a = Nonterminal { kind: "A", variant: 0 };
let b = Nonterminal { kind: "B", variant: 0 };
let c = Nonterminal { kind: "C", variant: 0 };
let sm_a = Terminal { kind: "a" };
let sm_b = Terminal { kind: "b" };
let grammar = CFG::new(s.clone(), vec![
// S -> A B
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(a.clone()), Symbol::Nonterminal(b.clone())] },
// A -> a
ProductionRule { head: a.clone(), body: vec![Symbol::Terminal(sm_a)] },
// B -> A C
ProductionRule { head: b.clone(), body: vec![Symbol::Nonterminal(a.clone()), Symbol::Nonterminal(c.clone())] },
// B -> b
ProductionRule { head: b.clone(), body: vec![Symbol::Terminal(sm_b.clone())] },
// C -> B B
ProductionRule { head: c.clone(), body: vec![Symbol::Nonterminal(b.clone()), Symbol::Nonterminal(b.clone())] },
]);
assert!(membership_earley(&vec![
tok!("a"),
tok!("b"),
], &grammar));
assert!(membership_earley(&vec![
tok!("a"),
tok!("a"),
tok!("b"),
tok!("b"),
], &grammar));
assert!(membership_earley(&vec![
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("b"),
tok!("b"),
tok!("b"),
tok!("b"),
tok!("b"),
tok!("b"),
], &grammar));
assert!(!membership_earley(&vec![// shall be NOT accepted
tok!("a"),// 0
tok!("a"),// 1
tok!("a"),// 2
tok!("a"),// 3
tok!("a"),// 4
tok!("a"),// 5
tok!("b"),// 5
tok!("b"),// 4
tok!("b"),// 3
tok!("b"),// 2
tok!("b"),// 1
// tok!("b"),// 0
], &grammar));
assert!(!membership_earley(&vec![// shall be NOT accepted
// tok!("a"),// 0
tok!("a"),// 1
tok!("a"),// 2
tok!("a"),// 3
tok!("a"),// 4
tok!("a"),// 5
tok!("b"),// 5
tok!("b"),// 4
tok!("b"),// 3
tok!("b"),// 2
tok!("b"),// 1
tok!("b"),// 0
], &grammar));
}
#[test]
fn accept_test_palindrome() {
// L(G) = { w w^R | w in Sigma^+ }
// S -> A A
// S -> B B
// S -> S1 A
// S -> S2 B
// S1 -> A S
// S2 -> B S
// A -> a
// B -> b
let s = Nonterminal { kind: "S", variant: 0 };
let s1 = Nonterminal { kind: "S", variant: 1 };
let s2 = Nonterminal { kind: "S", variant: 2 };
let a = Nonterminal { kind: "A", variant: 0 };
let b = Nonterminal { kind: "B", variant: 0 };
let sm_a = Terminal { kind: "a" };
let sm_b = Terminal { kind: "b" };
let grammar = CFG::new(s.clone(), vec![
// S -> A A
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(a.clone()), Symbol::Nonterminal(a.clone())] },
// S -> B B
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(b.clone()), Symbol::Nonterminal(b.clone())] },
// S -> S1 A
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(s1.clone()), Symbol::Nonterminal(a.clone())] },
// S -> S2 B
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(s2.clone()), Symbol::Nonterminal(b.clone())] },
// S1 -> A S
ProductionRule { head: s1.clone(), body: vec![Symbol::Nonterminal(a.clone()), Symbol::Nonterminal(s.clone())] },
// S2 -> B S
ProductionRule { head: s2.clone(), body: vec![Symbol::Nonterminal(b.clone()), Symbol::Nonterminal(s.clone())] },
// A -> a
ProductionRule { head: a.clone(), body: vec![Symbol::Terminal(sm_a)] },
// B -> b
ProductionRule { head: b.clone(), body: vec![Symbol::Terminal(sm_b.clone())] },
]);
assert!(membership_earley(&vec![
tok!("a"),
tok!("a"),
], &grammar));
assert!(membership_earley(&vec![
tok!("b"),
tok!("b"),
], &grammar));
assert!(membership_earley(&vec![
tok!("a"),// 0
tok!("b"),// 1
tok!("b"),// 2
tok!("b"),// 3
tok!("a"),// 4
tok!("a"),// 5
tok!("a"),// 5
tok!("a"),// 4
tok!("b"),// 3
tok!("b"),// 2
tok!("b"),// 1
tok!("a"),// 0
], &grammar));
assert!(!membership_earley(&vec![// shall be NOT accepted
tok!("a"),// 0
tok!("b"),// 1
tok!("b"),// 2
tok!("b"),// 3
tok!("a"),// 4
tok!("a"),// 5
tok!("a"),// 5
tok!("a"),// 4
tok!("b"),// 3
tok!("b"),// 2
tok!("b"),// 1
// tok!("a"),// 0
], &grammar));
assert!(!membership_earley(&vec![// shall be NOT accepted
// tok!("a"),// 0
tok!("b"),// 1
tok!("b"),// 2
tok!("b"),// 3
tok!("a"),// 4
tok!("a"),// 5
tok!("a"),// 5
tok!("a"),// 4
tok!("b"),// 3
tok!("b"),// 2
tok!("b"),// 1
tok!("a"),// 0
], &grammar));
}
#[test]
fn accept_test_nullable() {
// L(G) = { a^n | n >= 0 }
// S -> epsilon
// S -> A T
// S -> a
// T -> T A
// T -> a
// A -> a
let s = Nonterminal { kind: "S", variant: 0 };
let t = Nonterminal { kind: "T", variant: 0 };
let a = Nonterminal { kind: "A", variant: 0 };
let sm_a = Terminal { kind: "a" };
let grammar = CFG::new(s.clone(), vec![
// S -> epsilon
ProductionRule { head: s.clone(), body: vec![] },
// S -> A T
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(a.clone()), Symbol::Nonterminal(t.clone())] },
// S -> a
ProductionRule { head: s.clone(), body: vec![Symbol::Terminal(sm_a.clone())] },
// T -> T A
ProductionRule { head: t.clone(), body: vec![Symbol::Nonterminal(t.clone()), Symbol::Nonterminal(a.clone())] },
// T -> a
ProductionRule { head: t.clone(), body: vec![Symbol::Terminal(sm_a.clone())] },
// A -> a
ProductionRule { head: a.clone(), body: vec![Symbol::Terminal(sm_a.clone())] },
]);
assert!(membership_earley(&vec![], &grammar));
assert!(membership_earley(&vec![
tok!("a"),
], &grammar));
assert!(membership_earley(&vec![
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
], &grammar));
assert!(!membership_earley(&vec![// shall be NOT accepted
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("a"),
tok!("b"),// unexpected token
tok!("a"),
tok!("a"),
tok!("a"),
], &grammar));
}
#[test]
fn accept_test_expr_cnf() {
// L(G) = { a(+a)^n | n >= 0 }
let e = Nonterminal { kind: "E", variant: 0 };
let p = Nonterminal { kind: "P", variant: 0 };
let t = Nonterminal { kind: "T", variant: 0 };
let sm_a = Terminal { kind: "a" };
let sm_p = Terminal { kind: "+" };
let grammar = CFG::new(e.clone(), vec![
// E -> E T
ProductionRule { head: e.clone(), body: vec![Symbol::Nonterminal(e.clone()), Symbol::Nonterminal(t.clone())] },
// E -> a
ProductionRule { head: e.clone(), body: vec![Symbol::Terminal(sm_a.clone())] },
// T -> P E
ProductionRule { head: t.clone(), body: vec![Symbol::Nonterminal(p.clone()), Symbol::Nonterminal(e.clone())] },
// P -> +
ProductionRule { head: p.clone(), body: vec![Symbol::Terminal(sm_p.clone())] },
]);
assert!(membership_earley(&vec![
tok!("a"),
], &grammar));
assert!(membership_earley(&vec![
tok!("a"),
tok!("+"),
tok!("a"),
], &grammar));
assert!(membership_earley(&vec![
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
], &grammar));
assert!(membership_earley(&vec![
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
], &grammar));
assert!(!membership_earley(&vec![// shall be NOT accepted
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
tok!("a"),// verbose
], &grammar));
}
#[test]
fn accept_test_even_palindrome() {
let s = Nonterminal { kind: "S", variant: 0 };
let sm_a = Terminal { kind: "a" };
let sm_b = Terminal { kind: "b" };
let grammar = CFG::new(s.clone(), vec![
// S -> a a
ProductionRule { head: s.clone(), body: vec![Symbol::Terminal(sm_a.clone()), Symbol::Terminal(sm_a.clone())] },
// S -> b b
ProductionRule { head: s.clone(), body: vec![Symbol::Terminal(sm_b.clone()), Symbol::Terminal(sm_b.clone())] },
// S -> a S a
ProductionRule { head: s.clone(), body: vec![Symbol::Terminal(sm_a.clone()), Symbol::Nonterminal(s.clone()), Symbol::Terminal(sm_a.clone())] },
// S -> b S b
ProductionRule { head: s.clone(), body: vec![Symbol::Terminal(sm_b.clone()), Symbol::Nonterminal(s.clone()), Symbol::Terminal(sm_b.clone())] },
]);
assert!(membership_earley(&vec![
tok!("a"),
tok!("b"),
tok!("b"),
tok!("a"),
], &grammar));
assert!(membership_earley(&vec![
tok!("a"),
tok!("b"),
tok!("b"),
tok!("b"),
tok!("b"),
tok!("b"),
tok!("b"),
tok!("a"),
], &grammar));
assert!(membership_earley(&vec![
tok!("a"),
tok!("b"),
tok!("a"),
tok!("b"),
tok!("a"),
tok!("a"),
tok!("b"),
tok!("b"),
tok!("a"),
tok!("a"),
tok!("b"),
tok!("a"),
tok!("b"),
tok!("a"),
], &grammar));
assert!(!membership_earley(&vec![// shall be NOT accepted
tok!("a"),
tok!("b"),
tok!("b"),
tok!("b"),
tok!("b"),// odd length palindrome
tok!("b"),
tok!("b"),
tok!("b"),
tok!("a"),
], &grammar));
assert!(!membership_earley(&vec![// shall be NOT accepted
tok!("a"),
tok!("b"),
tok!("a"),
tok!("b"),
tok!("a"),
tok!("a"),
tok!("b"),
tok!("b"),
tok!("a"),
tok!("a"),
tok!("b"),
tok!("a"),
tok!("b"),
tok!("b"),// verbose
], &grammar));
}
#[test]
fn accept_test_expr() {
// L(G) = { a(+a)^n | n >= 0 }
let e = Nonterminal { kind: "E", variant: 0 };
let sm_a = Terminal { kind: "a" };
let sm_p = Terminal { kind: "+" };
let grammar = CFG::new(e.clone(), vec![
// E -> E + E
ProductionRule { head: e.clone(), body: vec![Symbol::Nonterminal(e.clone()), Symbol::Terminal(sm_p.clone()), Symbol::Nonterminal(e.clone())] },
// E -> a
ProductionRule { head: e.clone(), body: vec![Symbol::Terminal(sm_a.clone())] },
]);
assert!(membership_earley(&vec![
tok!("a"),
], &grammar));
assert!(membership_earley(&vec![
tok!("a"),
tok!("+"),
tok!("a"),
], &grammar));
assert!(membership_earley(&vec![
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
], &grammar));
assert!(membership_earley(&vec![
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
], &grammar));
assert!(!membership_earley(&vec![// shall be NOT accepted
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
tok!("a"),// verbose
], &grammar));
}
}
Earley 法と構文森
Earley の論文、'An efficient context-free parsing algorithm' では、完了操作ごとに原因となった状態へのポインタを付与することによって構文森が得られるとしている.
しかし、Tomita の論文 'An Efficient Context-free Parsing Algorithm For Natural Languages' で指摘されているように、これは (単純に実装すると？) 存在しない解析木まで過剰に含んでしまう欠陥を持つ.
そのため実際には、E. Scott & A Johnstone の論文 'Recognition is not parsing — SPPF-style parsing from cubic recognisers' に書かれている SPPF のような方法が使われている1.
しかし SPPF もそれはそれで複雑であるから、ここでは Earley の方法で構築してから、ノードを共有する森を DAG で、そこから最終的には木の集合を得る方法を見る.
先に挙げた論文の方法はどれもよく分からなかったので、ここに書くのは半分独自の手法であって、標準の方法であるかは私自身判断できていないことを先に断っておく.
二重連鎖木
構文解析中に木の構築を並行して進めることもできるだろうがここでは、所属問題の判定の後、その手順を逆にたどることで構文森を復元することとする. 前半部分で復元用の情報を仕込むのだが、単純な方法で仕込める構造は二重連鎖木に似るから、ここから始めよう.
二重連鎖木の構造自体は Wikipedia などを読めばいいのだが、2025年9月現在これを多分木に変換する方法がペルシャ語版にしかない. それは木の上の方から構築しているが、ノードを可変で持ちたくないので、下から構築するコード例を示す.
chain_tree.rs
struct ChainTree<T> {
label: T,
first_child: Option<Rc<ChainTree<T>>>,
next_sibling: Option<Rc<ChainTree<T>>>,
}
fn chain_tree_to_tree<T: Clone>(node: Rc<ChainTree<T>>) -> Tree<T> {
let children: Vec<Tree<T>> = build_children(node.first_child.clone());
Tree {
label: node.label.clone(),
children: children
}
}
fn build_children<T: Clone>(opt: Option<Rc<ChainTree<T>>>) -> Vec<Tree<T>> {
let mut siblings = Vec::new();
let mut opt = opt;
while let Some(node) = &opt {
siblings.push(chain_tree_to_tree(Rc::clone(node)));
opt = opt.as_ref().and_then(|n| n.next_sibling.as_ref().map(|k| Rc::clone(k)));
}
siblings
}
二重連鎖森
二重連鎖木では高々ひとつの子 (と高々ひとつの兄弟) を持っていたが、今回は森を表現したいので複数の子を持てるようにする.
標準的な呼び方が存在するものかは知らないが、ここでは仮に二重連鎖森と呼ぶこととする.
以下に実装例を示すが、木 A では葉だけれど木 B では内部ノードであるようなノードの存在は考慮していない.
chain_forest.rs
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ChainForest<T> {
pub label: T,
pub first_children: Vec<Rc<ChainForest<T>>>,
pub next_sibling: Option<Rc<ChainForest<T>>>
}
pub fn chain_forest_to_forest<T>(node: Rc<ChainForest<T>>)
-> DAG<T>
where T: Hash + Eq + Clone
{
let mut memo = HashMap::new();
let roots = chain_forest_to_forest0(node, &mut memo);
DAG { roots }
}
fn chain_forest_to_forest0<T: Hash + Eq + Clone>(node: Rc<ChainForest<T>>, memo: &mut HashMap<T, Vec<Rc<Node<T>>>>)
-> Vec<Rc<Node<T>>>
where T: Hash + Eq + Clone
{
if memo.contains_key(&node.label) {
return memo.get(&node.label)
.unwrap()
.iter()
.map(|n| Rc::clone(n))
.collect();
}
if node.first_children.is_empty() {
let new_node = Node {
label: node.label.clone(),
nexts: vec![]
};
memo.insert(node.label.clone(), vec![Rc::new(new_node)]);
return memo.get(&node.label)
.unwrap()
.iter()
.map(|n| Rc::clone(n))
.collect();
}
let mut nodes = Vec::new();
for child in &node.first_children {
let childrens = chain_forest_to_children(Rc::clone(child), memo);
for children in childrens {
nodes.push(Rc::new(Node { label: node.label.clone(), nexts: children }));
}// loop for children in siblings
}// loop for child in &node.first_children
memo.insert(node.label.clone(), nodes);
memo.get(&node.label)
.unwrap()
.iter()
.map(|n| Rc::clone(n))
.collect()
}
fn chain_forest_to_children<T: Hash + Eq + Clone>(node: Rc<ChainForest<T>>, memo: &mut HashMap<T, Vec<Rc<Node<T>>>>)
-> Vec<Vec<Rc<Node<T>>>>
where T: Hash + Eq + Clone
{
// 横に a -- b -- c とつながっているとき、b に b(d) と b(e) ふたつのバリエーションがあったとする.
// このとき結果は、
// [a, b(d), c], [a, b(e), c] の二種類
let mut siblings = Vec::new();
let mut opt = Some(node);
while let Some(node) = &opt {
let variations = chain_forest_to_forest0(Rc::clone(node), memo);
if siblings.is_empty() {
// variations = [ a(b), a(c), a(d) ] だとする.
// このとき、siblings = [ [a(b)], [a(c)], [a(d)] ]
siblings.extend(variations.iter().map(|n| vec![Rc::clone(n)]));
} else {
// siblings = [ [a(b)], [a(c)], [a(d)] ]
// variations = [ b(e), b(f) ] だとする.
// このとき、new_siblings = [ [a(b), b(e)], [a(b), b(f)], [a(c), b(e)], [a(c), b(f)], [a(d), b(e)], [a(d), b(f)] ]
let mut new_siblings = Vec::new();
for xs in &siblings {
for y in &variations {
let mut zs = xs.clone();
zs.push(Rc::clone(y));
new_siblings.push(zs);
}
}
siblings = new_siblings;
}
opt = opt.as_ref().and_then(|n| n.next_sibling.as_ref().map(|k| Rc::clone(k)));
}
siblings
}
動作確認
tree.show の結果をコンソールで見て確認している.
chain_forest.rs
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn trivial_forest() {
let root = ChainForest {
label: "root",
first_children: vec![],
next_sibling: None,
};
let dag = chain_forest_to_forest(Rc::new(root));
let trees = dag.to_trees();
for tree in &trees {
tree.show(|s| s.to_string());
}
}
#[test]
fn single_binary_tree() {
let b = ChainForest {
label: "b",
first_children: vec![],
next_sibling: None,
};
let a = ChainForest {
label: "a",
first_children: vec![],
next_sibling: Some(Rc::new(b)),
};
let d = ChainForest {
label: "d",
first_children: vec![],
next_sibling: None,
};
let c = ChainForest {
label: "c",
first_children: vec![],
next_sibling: Some(Rc::new(d)),
};
let f = ChainForest {
label: "f",
first_children: vec![Rc::new(c)],
next_sibling: None,
};
let e = ChainForest {
label: "e",
first_children: vec![Rc::new(a)],
next_sibling: Some(Rc::new(f)),
};
let root = ChainForest {
label: "root",
first_children: vec![Rc::new(e)],
next_sibling: None,
};
let dag = chain_forest_to_forest(Rc::new(root));
let trees = dag.to_trees();
assert_eq!(trees.len(), 1);
for tree in &trees {
tree.show(|s| s.to_string());
}
}
#[test]
fn double_binary_trees() {
let b = ChainForest {
label: "b",
first_children: vec![],
next_sibling: None,
};
let a = ChainForest {
label: "a",
first_children: vec![],
next_sibling: Some(Rc::new(b)),
};
let d = ChainForest {
label: "d",
first_children: vec![],
next_sibling: None,
};
let c = ChainForest {
label: "c",
first_children: vec![],
next_sibling: Some(Rc::new(d)),
};
let f = ChainForest {
label: "f",
first_children: vec![Rc::new(c)],
next_sibling: None,
};
let e = ChainForest {
label: "e",
first_children: vec![Rc::new(a)],
next_sibling: Some(Rc::new(f)),
};
let b2 = ChainForest {
label: "b2",
first_children: vec![],
next_sibling: None,
};
let a2 = ChainForest {
label: "a2",
first_children: vec![],
next_sibling: Some(Rc::new(b2)),
};
let d2 = ChainForest {
label: "d2",
first_children: vec![],
next_sibling: None,
};
let c2 = ChainForest {
label: "c2",
first_children: vec![],
next_sibling: Some(Rc::new(d2)),
};
let f2 = ChainForest {
label: "f2",
first_children: vec![Rc::new(c2)],
next_sibling: None,
};
let e2 = ChainForest {
label: "e2",
first_children: vec![Rc::new(a2)],
next_sibling: Some(Rc::new(f2)),
};
let root = ChainForest {
label: "root",
first_children: vec![Rc::new(e), Rc::new(e2)],
next_sibling: None,
};
let dag = chain_forest_to_forest(Rc::new(root));
let trees = dag.to_trees();
assert_eq!(trees.len(), 2);
for tree in &trees {
tree.show(|s| s.to_string());
}
}
#[test]
fn two_trees() {
let a = ChainForest {
label: "a",
first_children: vec![],
next_sibling: None,
};
let b = ChainForest {
label: "b",
first_children: vec![],
next_sibling: None,
};
let root = ChainForest {
label: "root",
first_children: vec![Rc::new(a), Rc::new(b)],
next_sibling: None,
};
let dag = chain_forest_to_forest(Rc::new(root));
let trees = dag.to_trees();
assert_eq!(trees.len(), 2);
for tree in &trees {
// root -- a
// root -- b
tree.show(|s| s.to_string());
}
}
#[test]
fn three_binary_trees() {
let g = ChainForest {
label: "g",
first_children: vec![],
next_sibling: None,
};
let h = ChainForest {
label: "h",
first_children: vec![],
next_sibling: None,
};
let b = ChainForest {
label: "b",
first_children: vec![Rc::new(g), Rc::new(h)],
next_sibling: None,
};
let a = ChainForest {
label: "a",
first_children: vec![],
next_sibling: Some(Rc::new(b)),
};
let d = ChainForest {
label: "d",
first_children: vec![],
next_sibling: None,
};
let c = ChainForest {
label: "c",
first_children: vec![],
next_sibling: Some(Rc::new(d)),
};
let f = ChainForest {
label: "f",
first_children: vec![Rc::new(c)],
next_sibling: None,
};
let e = ChainForest {
label: "e",
first_children: vec![Rc::new(a)],
next_sibling: Some(Rc::new(f)),
};
let b2 = ChainForest {
label: "b2",
first_children: vec![],
next_sibling: None,
};
let a2 = ChainForest {
label: "a2",
first_children: vec![],
next_sibling: Some(Rc::new(b2)),
};
let d2 = ChainForest {
label: "d2",
first_children: vec![],
next_sibling: None,
};
let c2 = ChainForest {
label: "c2",
first_children: vec![],
next_sibling: Some(Rc::new(d2)),
};
let f2 = ChainForest {
label: "f2",
first_children: vec![Rc::new(c2)],
next_sibling: None,
};
let e2 = ChainForest {
label: "e2",
first_children: vec![Rc::new(a2)],
next_sibling: Some(Rc::new(f2)),
};
let root = ChainForest {
label: "root",
first_children: vec![Rc::new(e), Rc::new(e2)],
next_sibling: None,
};
let dag = chain_forest_to_forest(Rc::new(root));
let trees = dag.to_trees();
assert_eq!(trees.len(), 3);
for tree in &trees {
tree.show(|s| s.to_string());
}
}
}
Earley 法と二重連鎖森
complete のタイミングで単純にリンクを張ると、どのような構造が作れるかを確認する.
所属判定だけであれば、Vec<HashSet<EarleyItem<T>>> という表を使っていればよかったのだった.
この HashSet<EarleyItem<T>> を HashMap<EarleyItem<T>, HashSet<EarleyItem<T>>> とすることによってリンクを表現する.
元の complete とリンクを張るようにした complete_linking をそれぞれ示す.
earley.rs
fn complete<T: Hash + Eq + Clone>(table: &mut Vec<HashSet<EarleyItem<T>>>, i: usize) {
loop {
// イテレータ使用中は table に要素を追加できないので、一旦 new_items に溜める.
let mut new_items = HashSet::new();
for item in &table[i] {
if item.item.is_completed() {
for item_to_advance in &table[item.pivot] {// table[i] などと書かないように
if let Some(Symbol::Nonterminal(predicted)) = item_to_advance.item.next_symbol() {
if *predicted == item.item.rule.head {
new_items.insert(EarleyItem {
item: item_to_advance.item.advance().unwrap(),
pivot: item_to_advance.pivot
});
}
}
}// loop for item_to_advance in &table[item.pivot]
}
}// loop for item in &table[i]
// new_items の要素を table[i] に入れる.
let before_length = table[i].len();
table[i].extend(new_items);
let after_length = table[i].len();
// 追加前後で大きさが同じであれば収束.
if before_length == after_length { break; }
}// loop while changed
}
earley.rs
fn complete_linking<T: Hash + Eq + Clone>(
table: &mut Vec<HashMap<EarleyItem<T>, HashSet<EarleyItem<T>>>>,
i: usize
) {
loop {
// イテレータ使用中は table に要素を追加できないので、一旦 new_items に溜める.
let mut new_items = HashMap::new();
for item in table[i].keys() {
if item.item.is_completed() {
for item_to_advance in table[item.pivot].keys() {// table[i] などと書かないように
if let Some(Symbol::Nonterminal(predicted)) = item_to_advance.item.next_symbol() {
if *predicted == item.item.rule.head {
new_items.entry(EarleyItem {
item: item_to_advance.item.advance().unwrap(),
pivot: item_to_advance.pivot
}).or_insert_with(|| HashSet::new())
.insert(item.clone());// クローンではなく参照を持たせられるとなおよい
}
}
}// loop for item_to_advance in &table[item.pivot]
}
}// loop for item in &table[i]
// new_items の要素を table[i] に入れる.
let before_length = table[i].len();
for (new_item, new_nodes) in new_items {
table[i].entry(new_item)
.and_modify(|old| old.extend(new_nodes.iter().cloned()))
.or_insert(new_nodes);
}
let after_length = table[i].len();
// 追加前後で大きさが同じであれば収束.
if before_length == after_length { break; }
}// loop while changed
}
このようにデータを持つと、ChainForest と同様に扱える. ただし、last_children、prev_sibling の方が計算しやすいのでそのようにする.
-
label:
EarleyItem { item: GrammarItem { rule, dot_position }, pivot }の内、dot_positionの違いを無視したもの -
last_children:
table[i][item]. ただしここで、item は $(A \to \alpha\ ., j)$ -
prev_sibling:
table[i][item]. ただしここで、item は $(A \to \alpha\ B\ .\ \beta, j)$
あるいは、input[i]. ただしここで、item は $(A \to \alpha\ a\ .\ \beta, j)$
dot_position の違いを無視する、というのが面倒であるが、概ねこれで計算できる.
complete のタイミングでだけリンクを張っても構築は可能だが、scan のタイミングでもリンクを張るとより扱いやすいため以降はそうする.
曖昧でない文の解析で構築される構造は下図のようになる.
下向きの赤い矢印が complete ないし scan の操作ごとに張ったリンクであり、左向きの緑の矢印が dot_position をひとつ巻き戻すことで得られるアイテムである.
@n と書いてあるのは、その complete ないし scan を行ったときのカーソル位置を示している.
台形ひとつひとつが、二重連鎖木のノードに相当する.
構文森を構築する Earley 法の実装例
earley.rs
pub fn parse_earley<T>(
input: &Vec<Token<T>>,
grammar: &CFG<T>
) -> Option<DAG<ParseNode<T>>>
where T: Hash + Eq + Clone
{
let n = input.len();
let dummy_variant = grammar.nonterminals.iter()
.filter(|n| n.kind == grammar.start.kind)
.map(|n| n.variant)
.max()
.unwrap() + 1;
let s_prime = Nonterminal { kind: grammar.start.kind.clone(), variant: dummy_variant };
// 状態集合を初期化
let mut table = vec![HashMap::new(); n+1];
table[0].insert(EarleyItem {
item: GrammarItem {
rule: ProductionRule {
head: s_prime.clone(),
body: vec![Symbol::Nonterminal(grammar.start.clone())]
},
dot_position: 0
},
pivot: 0,
}, HashSet::new());
// 順に読み進めていく
for (i, cur) in input.iter().enumerate() {
predict_and_complete(&mut table, grammar, i);
scan(&mut table, i, cur);
}
predict_and_complete(&mut table, grammar, n);
let ok = table[n].keys()
.filter(|&s| s.item.is_completed())
.any(|s| s.item.rule.head == s_prime);
if !ok {
return None;
}
return Some(build(&EarleyItem {
item: GrammarItem {
rule: ProductionRule {
head: s_prime.clone(),
body: vec![Symbol::Nonterminal(grammar.start.clone())]
},
dot_position: 1// completed
},
pivot: 0,
}, &table, grammar, n, input));
fn predict_and_complete<T: Hash + Eq + Clone>(table: &mut Vec<HashMap<EarleyItem<T>, HashSet<ChildPointer<T>>>>, grammar: &CFG<T>, i: usize) {
loop {
let before_length = table[i].len();
predict(&mut table[i], grammar, i);
complete(table, i);
let after_lenth = table[i].len();
if before_length == after_lenth { break; }
}
}
fn predict<T: Hash + Eq + Clone>(states: &mut HashMap<EarleyItem<T>, HashSet<ChildPointer<T>>>, grammar: &CFG<T>, i: usize) {
loop {
// イテレータ使用中は states に要素を追加できないので、一旦 new_items に溜める.
let mut new_items = HashMap::new();
for item in states.keys() {
if let Some(Symbol::Nonterminal(predicted)) = &item.item.next_symbol() {
for rule in &grammar.rules {
if rule.head == *predicted {
new_items.entry(EarleyItem {
item: GrammarItem { rule: rule.clone(), dot_position: 0 },
pivot: i
}).or_insert_with(|| HashSet::new());
}
}// loop for rule in &grammar.rules
}
}// for item in states.iter()
// new_items の要素を states に入れる.
let before_length = states.len();
states.extend(new_items);
let after_length = states.len();
// 追加前後で大きさが同じであれば収束.
if before_length == after_length { break; }
}// loop while changed
}
fn complete<T: Hash + Eq + Clone>(table: &mut Vec<HashMap<EarleyItem<T>, HashSet<ChildPointer<T>>>>, i: usize) {
loop {
// イテレータ使用中は table に要素を追加できないので、一旦 new_items に溜める.
let mut new_items = HashMap::new();
for item in table[i].keys() {
if item.item.is_completed() {
for item_to_advance in table[item.pivot].keys() {// table[i] などと書かないように
if let Some(Symbol::Nonterminal(predicted)) = item_to_advance.item.next_symbol() {
if *predicted == item.item.rule.head {
new_items.entry(EarleyItem {
item: item_to_advance.item.advance().unwrap(),
pivot: item_to_advance.pivot
}).or_insert_with(|| HashSet::new())
.insert(ChildPointer::Complete(item.clone()));// クローンではなく参照を持たせられるとなおよい
}
}
}// loop for item_to_advance in &table[item.pivot]
}
}// loop for item in &table[i]
// new_items の要素を table[i] に入れる.
let before_length = table[i].len();
table[i].extend(new_items);
let after_length = table[i].len();
// 追加前後で大きさが同じであれば収束.
if before_length == after_length { break; }
}// loop while changed
}
fn scan<T: Hash + Eq + Clone>(table: &mut Vec<HashMap<EarleyItem<T>, HashSet<ChildPointer<T>>>>, i: usize, symbol: &Token<T>) {
// イテレータ使用中は table に要素を追加できないので、一旦 new_items に溜める.
let mut new_items = HashMap::new();
for item in table[i].keys() {
if let Some(Symbol::Terminal(expected)) = item.item.next_symbol() {
if expected.kind == symbol.kind {
new_items.entry(EarleyItem {
item: item.item.advance().unwrap(),
pivot: item.pivot
}).or_insert_with(|| HashSet::new())
.insert(ChildPointer::Token);
}
}
}// loop for item in &table[i]
// new_items の要素を table[i+1] に入れる.
table[i+1].extend(new_items);// table[i] ではないことに注意
}
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
enum ChildPointer<T: Clone> {
Complete(EarleyItem<T>),
Token
}
fn last_children_of<'a, T>(parent: &EarleyItem<T>, cursor: usize, table: &'a Vec<HashMap<EarleyItem<T>,HashSet<ChildPointer<T>>>>)
-> &'a HashSet<ChildPointer<T>>
where T: Hash + Eq + Clone
{
&table[cursor][parent]
}
fn previous_siblings_of<'a, T>(parent: &EarleyItem<T>, current: &ChildPointer<T>, cursor: usize, table: &'a Vec<HashMap<EarleyItem<T>,HashSet<ChildPointer<T>>>>)
-> Option<(EarleyItem<T>, usize)>
where T: Hash + Eq + Clone
{
let EarleyItem { item: GrammarItem { rule, dot_position }, pivot } = parent;
if *dot_position <= 1 {
return None;
}
let prev_item = EarleyItem { item: GrammarItem { rule: rule.clone(), dot_position: *dot_position - 1 }, pivot: *pivot };
let prev_cursor = match ¤t {
ChildPointer::Token => cursor - 1,
ChildPointer::Complete(cur) => cur.pivot
};
Some((prev_item, prev_cursor))
}
fn build<T>(
goal_item: &EarleyItem<T>,
table: &Vec<HashMap<EarleyItem<T>,HashSet<ChildPointer<T>>>>,
grammar: &CFG<T>,
n: usize,
input: &Vec<Token<T>>
)
-> DAG<ParseNode<T>>
where T: Hash + Eq + Clone
{
let mut memo = vec![HashMap::new(); n+1];
let root_keys = last_children_of(goal_item, n, table);
let roots = root_keys.iter()
.flat_map(|ch| build_node(ch, table, grammar, n, input, &mut memo))
.collect::<Vec<_>>();
DAG { roots }
}
fn label_for<T>(
pointer: &ChildPointer<T>,
cursor: usize,
input: &Vec<Token<T>>,)
-> ParseNode<T>
where T: Hash + Eq + Clone
{
match pointer {
ChildPointer::Complete(earley_item) => ParseNode::Reduction(earley_item.item.rule.head.clone()),
ChildPointer::Token => ParseNode::Input(input[cursor-1].clone()),
}
}
fn build_node<T>(
pointer: &ChildPointer<T>,
table: &Vec<HashMap<EarleyItem<T>,HashSet<ChildPointer<T>>>>,
grammar: &CFG<T>,
cursor: usize,
input: &Vec<Token<T>>,
memo: &mut Vec<HashMap<ChildPointer<T>, Vec<Rc<Node<ParseNode<T>>>>>>,
)
-> Vec<Rc<Node<ParseNode<T>>>>
where T: Hash + Eq + Clone
{
if memo[cursor].contains_key(pointer) {
return memo[cursor][pointer].clone();
}
match pointer {
ChildPointer::Token => {
memo[cursor].insert(pointer.clone(), vec![
Rc::new(Node {
label: label_for(pointer, cursor, input),
nexts: Vec::new()
})
]);
},
ChildPointer::Complete(item) => {
let last_children = last_children_of(item, cursor, table);
let nodes = if last_children.is_empty() {
vec![Rc::new(Node {
label: label_for(pointer, cursor, input),
nexts: Vec::new()
})]
} else {
last_children.iter()
.flat_map(|ch| build_siblings(item, ch, table, grammar, cursor, input, memo))
.map(|chs| Rc::new(
Node {
label: label_for(pointer, cursor, input),
nexts: chs.clone()
}
)).collect::<Vec<_>>()
};
memo[cursor].insert(pointer.clone(), nodes);
},
}
return memo[cursor][pointer].clone();
}
// earley_item の兄たちを構築する
fn build_siblings<T>(
parent: &EarleyItem<T>,
current: &ChildPointer<T>,
table: &Vec<HashMap<EarleyItem<T>,HashSet<ChildPointer<T>>>>,
grammar: &CFG<T>,
cursor: usize,
input: &Vec<Token<T>>,
memo: &mut Vec<HashMap<ChildPointer<T>, Vec<Rc<Node<ParseNode<T>>>>>>,
)
-> Vec<Vec<Rc<Node<ParseNode<T>>>>>
where T: Hash + Eq + Clone
{
let prev = previous_siblings_of(parent, current, cursor, table);
let current_nodes = build_node(current, table, grammar, cursor, input, memo);
match &prev {
None => {
return current_nodes.iter().map(|node| vec![Rc::clone(node)]).collect();
},
Some((prev_item, prev_cursor)) => {
let elders = last_children_of(prev_item, *prev_cursor, table);
if elders.is_empty() {
return vec![current_nodes];
}
let elder_siblings = elders.iter()
.flat_map(|ch| build_siblings(prev_item, ch, table, grammar, *prev_cursor, input, memo))
.collect::<Vec<_>>();
return product(&elder_siblings, ¤t_nodes);
},
}
}
fn product<T>(xss: &Vec<Vec<T>>, ys: &Vec<T>) -> Vec<Vec<T>>
where T: Clone,
{
let mut result = Vec::new();
for xs in xss {
for y in ys {
let mut new_vec = xs.clone();
new_vec.push(y.clone());
result.push(new_vec);
}
}
result
}
テストコード(簡単な動作確認)
earley.rs
#[cfg(test)]
mod tests {
use super::*;
use crate::grammar::ProductionRule;
use crate::{tok, util::{TextPosition}};
#[test]
fn parse_test_expr() {
// L(G) = { a(+a)^n | n >= 0 }
let e = Nonterminal { kind: "E", variant: 0 };
let sm_a = Terminal { kind: "a" };
let sm_p = Terminal { kind: "+" };
let grammar = CFG::new(e.clone(), vec![
// E -> E + E
ProductionRule { head: e.clone(), body: vec![Symbol::Nonterminal(e.clone()), Symbol::Terminal(sm_p.clone()), Symbol::Nonterminal(e.clone())] },
// E -> a
ProductionRule { head: e.clone(), body: vec![Symbol::Terminal(sm_a.clone())] },
]);
let result = parse_earley(&vec![
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
tok!("+"),
tok!("a"),
], &grammar);
match result {
Some(forest) => {
let trees = forest.to_trees();
assert_eq!(trees.len(), 14);
println!("-- show results ------------");
for tree in trees {
tree.show(|x| node_to_string(x));
println!("<<");
}
},
None => {
panic!("result must be Some(_)");
},
};
}
#[test]
fn parse_test_tomita_g1() {
// Tomita[85] に例として出ているもの
// L(G) = ???
// S -> epsilon
// S -> S J
// J -> F
// J -> I
// F -> x
// I -> x
let s = Nonterminal { kind: "S", variant: 0 };
let j = Nonterminal { kind: "J", variant: 0 };
let f = Nonterminal { kind: "F", variant: 0 };
let i = Nonterminal { kind: "I", variant: 0 };
let sm_x = Terminal { kind: "x" };
let grammar = CFG::new(s.clone(), vec![
// S -> epsilon
ProductionRule { head: s.clone(), body: vec![] },
// S -> S J
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(s.clone()), Symbol::Nonterminal(j.clone())] },
// J -> F
ProductionRule { head: j.clone(), body: vec![Symbol::Nonterminal(f.clone())] },
// J -> I
ProductionRule { head: j.clone(), body: vec![Symbol::Nonterminal(i.clone())] },
// F -> x
ProductionRule { head: f.clone(), body: vec![Symbol::Terminal(sm_x.clone())] },
// I -> x
ProductionRule { head: i.clone(), body: vec![Symbol::Terminal(sm_x.clone())] },
]);
let result = parse_earley(&vec![
tok!("x"),
tok!("x"),
], &grammar);
match result {
Some(forest) => {
let trees = forest.to_trees();
assert_eq!(trees.len(), 4);
println!("-- show results ------------");
for tree in trees {
tree.show(|x| node_to_string(x));
println!("<<");
}
},
None => {
panic!("result must be Some(_)");
},
};
}
#[test]
fn parse_test_left_recursive() {
// L(G) = ???
// S -> epsilon
// S -> S A
// A -> B
// B -> x
let s = Nonterminal { kind: "S", variant: 0 };
let a = Nonterminal { kind: "A", variant: 0 };
let b = Nonterminal { kind: "B", variant: 0 };
let sm_x = Terminal { kind: "x" };
let grammar = CFG::new(s.clone(), vec![
// S -> epsilon
ProductionRule { head: s.clone(), body: vec![] },
// S -> S A
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(s.clone()), Symbol::Nonterminal(a.clone())] },
// A -> B
ProductionRule { head: a.clone(), body: vec![Symbol::Nonterminal(b.clone())] },
// B -> x
ProductionRule { head: b.clone(), body: vec![Symbol::Terminal(sm_x.clone())] },
]);
let result = parse_earley(&vec![
tok!("x"),
tok!("x"),
tok!("x"),
], &grammar);
match result {
Some(forest) => {
let trees = forest.to_trees();
assert_eq!(trees.len(), 1);
println!("-- show results ------------");
for tree in trees {
tree.show(|x| node_to_string(x));
println!("<<");
}
},
None => {
panic!("result must be Some(_)");
},
};
}
#[test]
fn parse_test_null() {
// L(G) = { }
// S -> epsilon
let s = Nonterminal { kind: "S", variant: 0 };
let grammar = CFG::new(s.clone(), vec![
// S -> epsilon
ProductionRule { head: s.clone(), body: vec![] },
]);
let result = parse_earley(&vec![
], &grammar);
match result {
Some(forest) => {
let trees = forest.to_trees();
assert_eq!(trees.len(), 1);
println!("-- show results ------------");
for tree in trees {
tree.show(|x| node_to_string(x));
println!("<<");
}
},
None => {
panic!("result must be Some(_)");
},
};
}
#[test]
fn parse_test_tomita_g2() {
// Tomita[85] に例として出ているもの
// L(G) = { x^n | n >= 2 }
let s = Nonterminal { kind: "S", variant: 0 };
let sm_x = Terminal { kind: "x" };
let grammar = CFG::new(s.clone(), vec![
// S -> S S
ProductionRule { head: s.clone(), body: vec![Symbol::Nonterminal(s.clone()), Symbol::Nonterminal(s.clone())] },
// S -> x
ProductionRule { head: s.clone(), body: vec![Symbol::Terminal(sm_x.clone())] },
]);
let result = parse_earley(&vec![
tok!("x"),
tok!("x"),
tok!("x"),
], &grammar);
match result {
Some(forest) => {
let trees = forest.to_trees();
assert_eq!(trees.len(), 2);
println!("-- show results ------------");
for tree in trees {
tree.show(|x| node_to_string(x));
println!("<<");
}
},
None => {
panic!("result must be Some(_)");
},
};
}
fn symbol_to_string<T: Display>(symbol: &Symbol<T>) -> String {
match symbol {
Symbol::Terminal(Terminal { kind }) => format!("{}", kind),
Symbol::Nonterminal(Nonterminal { kind, variant }) => format!("{}{}", kind, variant),
}
}
fn item_to_string<T: Display + Clone>(item: &EarleyItem<T>) -> String {
let EarleyItem { item: GrammarItem { rule, dot_position }, pivot } = item;
let head = symbol_to_string(&Symbol::Nonterminal(rule.head.clone()));
let first = &rule.body[..*dot_position].iter().map(symbol_to_string).collect::<Vec<_>>().join(" ");
let second = &rule.body[*dot_position..].iter().map(symbol_to_string).collect::<Vec<_>>().join(" ");
let dot = if !first.is_empty() {
if !second.is_empty() {
" . "
} else {
" ."
}
} else if !second.is_empty() {
". "
} else {
"."
};
format!("({head} -> {first}{dot}{second}, {pivot})")
}
fn pointer_to_string<T: Display + Clone>(pointer: &ChildPointer<T>) -> String {
match pointer {
ChildPointer::Complete(earley_item) => format!("{}", item_to_string(earley_item)),
ChildPointer::Token => "Token".to_string(),
}
}
fn node_to_string<T: Display + Display + Clone>(node: &ParseNode<T>) -> String {
match node {
ParseNode::Input(token) => format!("Token[{}]", token.kind),
ParseNode::Reduction(nonterminal) => format!("{}", symbol_to_string(&Symbol::Nonterminal(nonterminal.clone()))),
}
}
}
素直に SPPF を勉強するべきではなかったか、という気持ちには蓋をしておく.
-
論文の名前をみっつ挙げはしましたが、基礎知識と英語力の不足によって私は一部を斜め読みしただけであることを白状しておきます. ↩