はじめに
これは構文解析手法に関するまとめの第4回です.
用語や記号、関数などは第1回の導入編を参照してください.
一応簡単な正常系を使って動くことだけは確認していますが、重大な誤りを含むコードを掲載している可能性はあります. ご注意ください.
LR(0) 構文解析とオートマトン を書いた辺りで記事には図が必要だと考えてビジュアライザを作り始めてしまい、執筆が全く進まなくなってしまいました.
ビジュアライザの方も含めて、これ以上置いておいても書き進めることはなさそうなので、中途半端かとは思いますがここで公開します.
この記事とビジュアライザが LR 構文解析を学ぶ方の一助となりましたならば幸いです.
LR 構文解析ビジュアライザ: (https://parsing-visualiser.pages.dev/)
上向き構文解析
CYK やアーリー法を使えば曖昧な文法も扱うことができる. しかし自然言語処理であればともかく、曖昧さを排して正確な表現することが求められるデータの記述やプログラミング言語などでは曖昧な文を必要としない. そうなると、コンパイラなどでアーリー法なぞを使うのは大袈裟なのだろう.
しかし一方で、LL(1) では左再帰を扱えないことを始めとして制約が大きい. そのような中で実用的なアルゴリズムとして発展したものが LR 系の構文解析だ (もっとも、アーリー法の発表は LR(k) のそれより遅い).
再帰降下法ではまず非終端記号 S を用意し、そこに連なる子を探し求めていたため下向き構文解析と呼ばれるのだが、LR は反対に(アーリー法に似て)、入力された記号列を都度還元しながら読み進めていく.
このことから、このカテゴリは上向き構文解析と呼ばれている. (構文木の根が上、葉/終端記号が下、という計算機科学の慣習による.)
LR(0)
LR 系の構文解析アルゴリズムで最も単純なものが LR(0) である. LR(k) の k は先読みする記号の数を意味するから、LR(0) は先読みをしないということになる.
先読みなしで構文解析をするというのは奇妙に思われるかもしれないが、これだけでも LL(1) で扱えない文法を扱いうる能力を持っている.
まずは簡単にその動きを眺めてみよう.
発想
LR(0) 構文解析の例として、以下の文法 $G$ を考える. 開始記号は $S$ である.
G = \left\lbrace\begin{align*}
S \to& S S \\
S \to& A \\
A \to& (\ S\ ) \\
A \to& [\ S\ ] \\
A \to& (\ ) \\
A \to& [\ ] \\
\end{align*}\right\rbrace
記号列 $w = (\ (\ )\ )\ (\ [\ [\ ]\ ]\ )$ がこの文法から生成できるかどうかを調べてみよう.
# i = 1
w[0..1) => ( について、
これは還元することができない. 先に進む.
# i = 2
w[0..2) => ( ( について、
これは還元することができない. 先に進む.
# i = 3
w[0..3) => ( ( ) について、
これは A -> ( ) によって還元することができる.
w[0..3) => ( A を得る.
これはさらに、S -> A によって還元することができる.
w[0..3) => ( S を得る.
これ以上は還元することができない. 先に進む.
# i = 4
w[0..4) => ( S ) について、
これは A -> ( S ) によって還元することができる.
w[0..4) => A を得る.
これはさらに、S -> A によって還元することができる.
w[0..4) => S を得る.
これ以上は還元することができない. 先に進む.
# i = 5
w[0..5) => S ( について、
これは還元することができない. 先に進む.
: : : (中略)
# i = 8
w[0..8) => S ( [ [ ] について、
これは A -> [ ] によって還元することができる.
w[0..8) => S ( [ A を得る.
これはさらに、S -> A によって還元することができる.
w[0..8) => S ( [ S を得る.
これ以上は還元することができない. 先に進む.
# i = 9
w[0..9) => S ( [ S ] について、
これは A -> [ S ] によって還元することができる.
w[0..9) => S ( A を得る.
これはさらに、S -> A によって還元することができる.
w[0..9) => S ( S を得る.
これ以上は還元することができない. 先に進む.
# i = 10
w[0..10) => S ( S ) について、
これは A -> ( S ) によって還元することができる.
w[0..10) => S A を得る.
これはさらに、S -> A によって還元することができる.
w[0..10) => S S を得る.
これはさらに、S -> S S によって還元することができる.
w[0..10) => S を得る.
これ以上は還元することができない. 先に進む.
# 入力の終端
入力の終端に到達し、W[0..10) は非終端記号 S に還元できることが判明している.
つまり、w は文法 G から生成することができる. これが示すべきことであった. □
手順は長いが、やっていることの単純さは伝わることだろう.
還元の過程を再度示すとこうなる.
\begin{align*}
(\ \underline{(\ )}\ )\ (\ [\ [\ ]\ ]\ ) &\Leftarrow (\ \underline{A}\ )\ (\ [\ [\ ]\ ]\ ) \\
&\Leftarrow \underline{(\ S\ )}\ (\ [\ [\ ]\ ]\ ) \\
&\Leftarrow \underline{A}\ (\ [\ [\ ]\ ]\ ) \\
&\Leftarrow S\ (\ [\ \underline{[\ ]}\ ]\ ) \\
&\Leftarrow S\ (\ [\ \underline{A}\ ]\ ) \\
&\Leftarrow S\ (\ \underline{[\ S\ ]}\ ) \\
&\Leftarrow S\ (\ \underline{A}\ ) \\
&\Leftarrow S\ \underline{(\ S\ )} \\
&\Leftarrow S\ \underline{A} \\
&\Leftarrow \underline{S\ S} \\
&\Leftarrow S
\end{align*}
逆順、つまり導出の過程として書くとこうだ.
\begin{align*}
S &\Rightarrow S\ \underline{S} \\
&\Rightarrow S\ \underline{A} \\
&\Rightarrow S\ (\ \underline{S}\ ) \\
&\Rightarrow S\ (\ \underline{A}\ ) \\
&\Rightarrow S\ (\ [\ \underline{S}\ ]\ ) \\
&\Rightarrow S\ (\ [\ \underline{A}\ ]\ ) \\
&\Rightarrow \underline{S}\ (\ [\ [\ ]\ ]\ ) \\
&\Rightarrow \underline{A}\ (\ [\ [\ ]\ ]\ ) \\
&\Rightarrow (\ \underline{S}\ )\ (\ [\ [\ ]\ ]\ ) \\
&\Rightarrow (\ \underline{A}\ )\ (\ [\ [\ ]\ ]\ ) \\
&\Rightarrow (\ (\ )\ )\ (\ [\ [\ ]\ ]\ ) = w
\end{align*}
文法記号列の内、最も右にあるものから順に適用していることが分かるだろう.
このような導出列を、最右導出 (rightmost derivation) と呼ぶ.
LR(0) 構文解析は、左 (Left) から順に入力を読んでいき、最右導出 (Rightmost derivation) を逆にたどるアルゴリズムなのだ.
この素朴でさえあるようなアイデアは、形式言語理論を巧妙に適用することによって、極めて実用的なアルゴリズムへと昇華されている. 驚嘆すべき洗練であるが、洗練された結果を見て過程を理解することは難しい. 泥臭く行くこととしよう.
ナイーブな実装
上で書いたものをそのまま実装すると、例えば次のようになる (parse_lr0_naive).
fn matches_at_end<T>(sequence: &Vec<Tree<ParseNode<T>>>, expected: &Vec<Symbol<T>>)
-> bool
where T: Hash + Eq + Clone
{
let n = sequence.len();
let m = expected.len();
if n < m {
false
} else {
// return sequence[n-m..n) == expected
for i in 1..=m {
let x = &sequence[n-i].label;
let y = &expected[m-i];
match (x, y) {
(ParseNode::Input(xx), Symbol::Terminal(yy)) => if xx.kind != yy.kind { return false; },
(ParseNode::Reduction(xx), Symbol::Nonterminal(yy)) => if xx != yy { return false; },
_ => return false,
};
}
true
}
}
pub fn parse_lr0_naive<T>(
input: &Vec<Token<T>>,
grammar: &CFG<T>
) -> Result<Tree<ParseNode<T>>, String>
where T: Hash + Eq + Clone
{
let mut stack = Vec::new();
for token in input.iter() {
stack.push(Tree::new(ParseNode::Input(token.clone())));
loop {
let mut changed = false;
for rule in &grammar.rules {
if matches_at_end(&stack, &rule.body) {
let mut children = Vec::new();
for _ in 0..rule.body.len() {
children.push(stack.pop().unwrap());
}
children.reverse();
stack.push(Tree::with_children(ParseNode::Reduction(rule.head.clone()), children));
changed = true;
}
}
if !changed { break; }
}
}
if stack.len() != 1 {
return Err("Fail to parse".to_string());
}
stack.pop()
.filter(|t| if let Tree { label: ParseNode::Reduction(root), .. } = t {
*root == grammar.start
} else {
false
}).ok_or_else(|| "Fail to parse".to_string())
}
NFA に基づく非効率なアルゴリズム
上で示したナイーブな実装では、記号をひとつ読み込む度すべての生成規則を使って比較していたが、これは非効率極まる.
どのような考察と対応によって改善できるだろうか？
先ほどの実装は最右導出を強調するためのものであったが、一度これを捨てて、やや後退した非効率な、しかし単純な、別のアルゴリズムについて考えるところから再度始めよう.
入力: 記号列 $w$、文法 $G$
出力: $G$ が $w$ を生成するか. i.e. $w \in L(G)$ であるか.
- 空のスタックを用意する.
- 入力された記号列の先頭から記号ひとつずつ順に次の処理を繰り返す.
- 現在の記号をスタックに積む.
- 現在のスタックの状態が正当であるかを確認する. もしも還元可能であれば、繰り返し還元する. (下で示す実装では関数
naive_lr0_internal)
- スタックが開始記号ひとつのみを含んでいれば、$w \in L(G)$
処理 2-2 の中身を説明する前に、前回の記事と同じ説明ではあるが、次のように文法アイテムを導入する.
生成規則に従って読み進めている途中の状態を表すことについて考えよう. 現在の栞の位置をドット ($.$ もしくは $\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$ は現れたその瞬間に還元されている.
この、本体にドットを持つ生成規則を文法アイテムという.
これを踏まえて処理 2-2 を説明する. これは可能な導出過程を幅優先探索しているに過ぎないことが伝われば幸いだ.
- 現在の状態を ${ S' \to .\ S\ \text{EOS} }$ とする. (${ S' \to .\ S }$ であったり、${ S \to .\ \alpha \mid S \to \alpha \in G }$ としてもよい.)
- 現在の状態が $A \to \alpha\ .\ B\ \beta$ を含むとき、$B \to .\ \gamma$ という形のイテムをすべて追加する. これは可能な限り繰り返す.
n.b. これは Earley 法における predict と同様の処理である. - スタックの底にある記号から順に次の処理を繰り返す. 現在見ているスタック上の記号を $X$ と呼ぶことにしよう.
- 状態を、${ A \to \alpha\ X\ .\ \beta \mid A \to \alpha\ .\ X\ \beta \in \text{現在の状態} }$ に更新する.
- 処理 1-2 と同じようにして、状態を追加する.
- 状態が空であるとき、スタックが不正な状態であるとして終了する.
- 状態が空でないとき、ドットが末尾に到達しているアイテムが存在しなければ正当な状態であるとして終了する.
- 状態が空でないとき、ドットが末尾に到達しているアイテムが存在すればスタックの末尾を還元し、処理 1 から再度繰り返す.
アルゴリズムのトレース
最初に見たものと同じ例で実行してみよう.
再掲:
以下の文法 $G$ を考える. 開始記号は $S$ である.
G = \left\lbrace\begin{align*}
S \to& S S \\
S \to& A \\
A \to& (\ S\ ) \\
A \to& [\ S\ ] \\
A \to& (\ ) \\
A \to& [\ ] \\
\end{align*}\right\rbrace
記号列 $w = (\ (\ )\ )\ (\ [\ [\ ]\ ]\ )$ がこの文法から生成できるかどうかを調べてみる.
上の説明や下にある実装例の補足となることを願って載せるが、長大であるから読み飛ばしてくれてもよい.
# i = 0: スタックに ( を積む.
## ループ 1 回目
### スタック = { ( }
### 初期状態 = { S -> . A, S -> . S S, S' -> . S $, A -> . [ ], A -> . ( S ), A -> . [ S ], A -> . ( ) }
#### X = (
#### 新しい状態 = { A -> ( . S ), A -> ( . ), S -> . S S, A -> . ( ), A -> . ( S ), A -> . [ ], S -> . A, A -> . [ S ] }
### 状態が空でないため正当なスタックであることが分かった. 還元できないため終了.
# i = 1: スタックに ( を積む.
## ループ 1 回目
### スタック = { ( ( }
### 初期状態 = { S -> . S S, S' -> . S $, A -> . [ ], A -> . ( ), S -> . A, A -> . [ S ], A -> . ( S ) }
#### X = (
#### 新しい状態 = { A -> ( . S ), A -> . [ S ], A -> ( . ), S -> . A, A -> . ( ), A -> . [ ], A -> . ( S ), S -> . S S }
#### X = (
#### 新しい状態 = { A -> ( . ), A -> ( . S ), A -> . ( S ), S -> . S S, A -> . [ S ], S -> . A, A -> . ( ), A -> . [ ] }
### 状態が空でないため正当なスタックであることが分かった. 還元できないため終了.
# i = 2: スタックに ) を積む.
## ループ 1 回目
### スタック = { ( ( ) }
### 初期状態 = { S -> . A, S -> . S S, S' -> . S $, A -> . [ S ], A -> . ( S ), A -> . ( ), A -> . [ ] }
#### X = (
#### 新しい状態 = { S -> . A, A -> . [ S ], A -> . ( S ), S -> . S S, A -> . [ ], A -> ( . S ), A -> ( . ), A -> . ( ) }
#### X = (
#### 新しい状態 = { A -> ( . ), S -> . A, A -> ( . S ), A -> . [ S ], S -> . S S, A -> . ( S ), A -> . [ ], A -> . ( ) }
#### X = )
#### 新しい状態 = { A -> ( ) . }
### 状態が空でないため正当なスタックであることが分かった. 還元できるため続行.
長いので中盤は折り畳み
## ループ 2 回目
### スタック = { ( A }
### 初期状態 = { S -> . A, S' -> . S $, S -> . S S, A -> . ( ), A -> . [ ], A -> . ( S ), A -> . [ S ] }
#### X = (
#### 新しい状態 = { S -> . A, A -> . ( ), A -> . [ ], S -> . S S, A -> . ( S ), A -> ( . S ), A -> ( . ), A -> . [ S ] }
#### X = A
#### 新しい状態 = { S -> A . }
### 状態が空でないため正当なスタックであることが分かった. 還元できるため続行.
## ループ 3 回目
### スタック = { ( S }
### 初期状態 = { A -> . [ S ], S -> . S S, S' -> . S $, A -> . [ ], S -> . A, A -> . ( ), A -> . ( S ) }
#### X = (
#### 新しい状態 = { A -> ( . ), A -> ( . S ), A -> . [ S ], A -> . ( ), S -> . S S, A -> . ( S ), S -> . A, A -> . [ ] }
#### X = S
#### 新しい状態 = { S -> . A, A -> . [ ], A -> . ( ), S -> . S S, S -> S . S, A -> . ( S ), A -> . [ S ], A -> ( S . ) }
### 状態が空でないため正当なスタックであることが分かった. 還元できないため終了.
# i = 3: スタックに ) を積む.
## ループ 1 回目
### スタック = { ( S ) }
### 初期状態 = { S -> . S S, S -> . A, A -> . [ ], A -> . [ S ], A -> . ( S ), S' -> . S $, A -> . ( ) }
#### X = (
#### 新しい状態 = { S -> . S S, A -> . ( ), A -> ( . ), A -> . [ S ], A -> . ( S ), S -> . A, A -> ( . S ), A -> . [ ] }
#### X = S
#### 新しい状態 = { A -> . [ S ], A -> ( S . ), A -> . ( ), A -> . [ ], A -> . ( S ), S -> S . S, S -> . A, S -> . S S }
#### X = )
#### 新しい状態 = { A -> ( S ) . }
### 状態が空でないため正当なスタックであることが分かった. 還元できるため続行.
## ループ 2 回目
### スタック = { A }
### 初期状態 = { A -> . ( S ), A -> . [ ], S' -> . S $, A -> . [ S ], S -> . A, S -> . S S, A -> . ( ) }
#### X = A
#### 新しい状態 = { S -> A . }
### 状態が空でないため正当なスタックであることが分かった. 還元できるため続行.
## ループ 3 回目
### スタック = { S }
### 初期状態 = { A -> . [ S ], A -> . [ ], S -> . S S, A -> . ( ), S -> . A, S' -> . S $, A -> . ( S ) }
#### X = S
#### 新しい状態 = { S -> . S S, S -> S . S, S' -> S . $, A -> . [ S ], A -> . ( ), S -> . A, A -> . [ ], A -> . ( S ) }
### 状態が空でないため正当なスタックであることが分かった. 還元できないため終了.
# i = 4: スタックに ( を積む.
## ループ 1 回目
### スタック = { S ( }
### 初期状態 = { S' -> . S $, A -> . [ S ], S -> . S S, A -> . ( S ), A -> . ( ), S -> . A, A -> . [ ] }
#### X = S
#### 新しい状態 = { S -> S . S, S' -> S . $, A -> . ( ), A -> . [ ], S -> . A, A -> . ( S ), S -> . S S, A -> . [ S ] }
#### X = (
#### 新しい状態 = { S -> . S S, A -> ( . ), A -> . [ ], A -> . ( ), A -> . ( S ), A -> ( . S ), S -> . A, A -> . [ S ] }
### 状態が空でないため正当なスタックであることが分かった. 還元できないため終了.
# i = 5: スタックに [ を積む.
## ループ 1 回目
### スタック = { S ( [ }
### 初期状態 = { S' -> . S $, A -> . ( ), A -> . ( S ), S -> . S S, S -> . A, A -> . [ S ], A -> . [ ] }
#### X = S
#### 新しい状態 = { S -> . S S, S -> . A, A -> . [ ], S' -> S . $, S -> S . S, A -> . ( ), A -> . [ S ], A -> . ( S ) }
#### X = (
#### 新しい状態 = { A -> . [ S ], A -> . ( ), A -> . [ ], A -> . ( S ), S -> . S S, S -> . A, A -> ( . ), A -> ( . S ) }
#### X = [
#### 新しい状態 = { S -> . A, A -> . ( ), A -> [ . ], A -> . ( S ), A -> . [ ], S -> . S S, A -> [ . S ], A -> . [ S ] }
### 状態が空でないため正当なスタックであることが分かった. 還元できないため終了.
# i = 6: スタックに [ を積む.
## ループ 1 回目
### スタック = { S ( [ [ }
### 初期状態 = { S' -> . S $, A -> . [ ], A -> . ( ), A -> . ( S ), S -> . S S, S -> . A, A -> . [ S ] }
#### X = S
#### 新しい状態 = { S' -> S . $, A -> . ( ), S -> S . S, A -> . [ S ], A -> . [ ], A -> . ( S ), S -> . A, S -> . S S }
#### X = (
#### 新しい状態 = { A -> . [ ], A -> . [ S ], A -> . ( S ), A -> ( . ), A -> ( . S ), S -> . S S, S -> . A, A -> . ( ) }
#### X = [
#### 新しい状態 = { S -> . A, A -> [ . S ], A -> [ . ], A -> . [ S ], A -> . [ ], S -> . S S, A -> . ( ), A -> . ( S ) }
#### X = [
#### 新しい状態 = { S -> . S S, A -> . [ S ], A -> . [ ], S -> . A, A -> [ . ], A -> . ( S ), A -> . ( ), A -> [ . S ] }
### 状態が空でないため正当なスタックであることが分かった. 還元できないため終了.
# i = 7: スタックに ] を積む.
## ループ 1 回目
### スタック = { S ( [ [ ] }
### 初期状態 = { A -> . ( S ), A -> . ( ), S' -> . S $, A -> . [ S ], S -> . S S, A -> . [ ], S -> . A }
#### X = S
#### 新しい状態 = { S' -> S . $, S -> . S S, A -> . [ ], A -> . [ S ], S -> S . S, A -> . ( S ), S -> . A, A -> . ( ) }
#### X = (
#### 新しい状態 = { A -> ( . S ), A -> . ( ), A -> . ( S ), A -> . [ ], A -> ( . ), A -> . [ S ], S -> . S S, S -> . A }
#### X = [
#### 新しい状態 = { A -> . [ ], A -> . ( S ), A -> . ( ), S -> . S S, S -> . A, A -> [ . S ], A -> [ . ], A -> . [ S ] }
#### X = [
#### 新しい状態 = { A -> [ . ], A -> . [ S ], S -> . S S, A -> . [ ], S -> . A, A -> [ . S ], A -> . ( ), A -> . ( S ) }
#### X = ]
#### 新しい状態 = { A -> [ ] . }
### 状態が空でないため正当なスタックであることが分かった. 還元できるため続行.
## ループ 2 回目
### スタック = { S ( [ A }
### 初期状態 = { S' -> . S $, A -> . [ S ], A -> . ( ), S -> . A, A -> . ( S ), A -> . [ ], S -> . S S }
#### X = S
#### 新しい状態 = { S -> S . S, S -> . S S, A -> . [ S ], A -> . [ ], S' -> S . $, A -> . ( ), S -> . A, A -> . ( S ) }
#### X = (
#### 新しい状態 = { A -> . [ S ], A -> ( . ), A -> ( . S ), A -> . ( S ), A -> . ( ), S -> . S S, A -> . [ ], S -> . A }
#### X = [
#### 新しい状態 = { A -> [ . ], A -> [ . S ], A -> . ( ), A -> . [ S ], S -> . S S, A -> . ( S ), S -> . A, A -> . [ ] }
#### X = A
#### 新しい状態 = { S -> A . }
### 状態が空でないため正当なスタックであることが分かった. 還元できるため続行.
## ループ 3 回目
### スタック = { S ( [ S }
### 初期状態 = { S -> . S S, A -> . ( S ), A -> . [ ], S' -> . S $, A -> . ( ), A -> . [ S ], S -> . A }
#### X = S
#### 新しい状態 = { A -> . ( S ), A -> . [ S ], A -> . [ ], S -> S . S, A -> . ( ), S -> . A, S' -> S . $, S -> . S S }
#### X = (
#### 新しい状態 = { A -> ( . ), A -> . ( S ), A -> ( . S ), A -> . [ S ], A -> . [ ], S -> . A, A -> . ( ), S -> . S S }
#### X = [
#### 新しい状態 = { S -> . S S, A -> [ . S ], A -> . [ S ], A -> . [ ], S -> . A, A -> . ( ), A -> . ( S ), A -> [ . ] }
#### X = S
#### 新しい状態 = { A -> . [ S ], A -> . [ ], S -> . S S, A -> . ( S ), S -> S . S, S -> . A, A -> . ( ), A -> [ S . ] }
### 状態が空でないため正当なスタックであることが分かった. 還元できないため終了.
# i = 8: スタックに ] を積む.
## ループ 1 回目
### スタック = { S ( [ S ] }
### 初期状態 = { S -> . S S, S' -> . S $, A -> . ( S ), A -> . ( ), S -> . A, A -> . [ ], A -> . [ S ] }
#### X = S
#### 新しい状態 = { A -> . ( S ), A -> . [ ], S -> . S S, S' -> S . $, A -> . [ S ], S -> S . S, S -> . A, A -> . ( ) }
#### X = (
#### 新しい状態 = { S -> . S S, A -> . ( S ), A -> ( . ), A -> ( . S ), A -> . [ S ], A -> . [ ], S -> . A, A -> . ( ) }
#### X = [
#### 新しい状態 = { A -> . ( S ), A -> [ . S ], A -> [ . ], S -> . A, A -> . [ ], S -> . S S, A -> . ( ), A -> . [ S ] }
#### X = S
#### 新しい状態 = { S -> . S S, S -> . A, A -> . [ S ], A -> [ S . ], A -> . ( ), A -> . ( S ), A -> . [ ], S -> S . S }
#### X = ]
#### 新しい状態 = { A -> [ S ] . }
### 状態が空でないため正当なスタックであることが分かった. 還元できるため続行.
## ループ 2 回目
### スタック = { S ( A }
### 初期状態 = { A -> . [ S ], S' -> . S $, A -> . ( S ), S -> . A, S -> . S S, A -> . [ ], A -> . ( ) }
#### X = S
#### 新しい状態 = { S' -> S . $, A -> . [ ], A -> . ( S ), A -> . ( ), S -> . A, A -> . [ S ], S -> S . S, S -> . S S }
#### X = (
#### 新しい状態 = { S -> . S S, S -> . A, A -> . ( ), A -> ( . ), A -> . ( S ), A -> . [ ], A -> . [ S ], A -> ( . S ) }
#### X = A
#### 新しい状態 = { S -> A . }
### 状態が空でないため正当なスタックであることが分かった. 還元できるため続行.
## ループ 3 回目
### スタック = { S ( S }
### 初期状態 = { S -> . A, S' -> . S $, A -> . [ S ], S -> . S S, A -> . [ ], A -> . ( ), A -> . ( S ) }
#### X = S
#### 新しい状態 = { A -> . ( S ), S -> S . S, S' -> S . $, A -> . ( ), S -> . S S, S -> . A, A -> . [ S ], A -> . [ ] }
#### X = (
#### 新しい状態 = { A -> ( . ), A -> ( . S ), A -> . ( S ), S -> . A, A -> . ( ), S -> . S S, A -> . [ S ], A -> . [ ] }
#### X = S
#### 新しい状態 = { A -> ( S . ), S -> S . S, S -> . A, A -> . [ ], S -> . S S, A -> . ( S ), A -> . [ S ], A -> . ( ) }
### 状態が空でないため正当なスタックであることが分かった. 還元できないため終了.
# i = 9: スタックに ) を積む.
## ループ 1 回目
### スタック = { S ( S ) }
### 初期状態 = { A -> . [ S ], A -> . ( ), S -> . S S, A -> . ( S ), S' -> . S $, S -> . A, A -> . [ ] }
#### X = S
#### 新しい状態 = { S -> . S S, A -> . [ ], A -> . [ S ], S -> . A, A -> . ( S ), A -> . ( ), S' -> S . $, S -> S . S }
#### X = (
#### 新しい状態 = { A -> . [ S ], S -> . S S, S -> . A, A -> . ( S ), A -> ( . ), A -> . [ ], A -> . ( ), A -> ( . S ) }
#### X = S
#### 新しい状態 = { A -> ( S . ), A -> . ( ), A -> . [ S ], A -> . ( S ), S -> . A, A -> . [ ], S -> S . S, S -> . S S }
#### X = )
#### 新しい状態 = { A -> ( S ) . }
### 状態が空でないため正当なスタックであることが分かった. 還元できるため続行.
## ループ 2 回目
### スタック = { S A }
### 初期状態 = { S -> . S S, A -> . [ ], A -> . [ S ], S' -> . S $, A -> . ( S ), S -> . A, A -> . ( ) }
#### X = S
#### 新しい状態 = { A -> . ( S ), S -> S . S, A -> . ( ), S -> . S S, S -> . A, A -> . [ ], A -> . [ S ], S' -> S . $ }
#### X = A
#### 新しい状態 = { S -> A . }
### 状態が空でないため正当なスタックであることが分かった. 還元できるため続行.
## ループ 3 回目
### スタック = { S S }
### 初期状態 = { S' -> . S $, A -> . [ S ], S -> . S S, A -> . ( ), A -> . ( S ), S -> . A, A -> . [ ] }
#### X = S
#### 新しい状態 = { S -> . A, S' -> S . $, A -> . ( S ), A -> . ( ), S -> S . S, S -> . S S, A -> . [ ], A -> . [ S ] }
#### X = S
#### 新しい状態 = { S -> S . S, S -> . S S, A -> . ( S ), A -> . [ ], A -> . ( ), S -> . A, S -> S S ., A -> . [ S ] }
### 状態が空でないため正当なスタックであることが分かった. 還元できるため続行.
## ループ 4 回目
### スタック = { S }
### 初期状態 = { S' -> . S $, S -> . A, A -> . [ ], S -> . S S, A -> . [ S ], A -> . ( ), A -> . ( S ) }
#### X = S
#### 新しい状態 = { S -> . A, S -> S . S, A -> . ( ), A -> . [ S ], S -> . S S, S' -> S . $, A -> . [ ], A -> . ( S ) }
### 状態が空でないため正当なスタックであることが分かった. 還元できないため終了.
実装例
所属判定のみを行う例 (naive_lr0) を示す.
処理 2-2 でスタックの正当性を確かめるときには前回の記事で Earley 法 (アーリー法) のときに定義した GrammarItem を使用している.
type AugmentedProductionRule<T> = crate::grammar::general::ProductionRule<AugmentedTerminal<T>, T>;
type AugmentedGrammarItem<T> = GrammarItem<AugmentedTerminal<T>, T>;
fn naive_lr0<T>(input: &Vec<Token<T>>, grammar: &CFG<T>) -> bool
where T: Hash + Eq + Clone
{
let mut stack = Vec::new();
for a in input {
stack.push(ParseNode::Input(a.clone()));
if !naive_lr0_internal(&mut stack, grammar) {
return false;
}
}// loop for a in input
stack.len() == 1 && match &stack[0] {
ParseNode::Reduction(nonterminal) => *nonterminal == grammar.start,
_ => false
}
}
fn naive_lr0_internal<T>(
stack: &mut Vec<ParseNode<T>>,
grammar: &CFG<T>
) -> bool
where T: Hash + Eq + Clone
{
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 };
// S' -> S $
let augmented_rule = AugmentedProductionRule {
head: s_prime.clone(),
body: vec![AugmentedSymbol::Nonterminal(grammar.start.clone()), AugmentedSymbol::Terminal(Terminal { kind: AugmentedTerminal::EOS })]
};
loop {
let mut states = HashSet::new();
states.insert(AugmentedGrammarItem {
rule: augmented_rule.clone(),
dot_position: 0
});
predict(&mut states, grammar);
// スタックの状態を検証する
for symbol in stack.iter() {
// new_states = { A -> alpha symbol . beta | A -> alpha . symbol beta in old_states }
states = states.iter()
.filter(|item| match (symbol, item.next_symbol()) {
(ParseNode::Input(token), Some(AugmentedSymbol::Terminal(Terminal { kind: AugmentedTerminal::Terminal(terminal) }))) => token.kind == *terminal,
(ParseNode::Reduction(actual), Some(AugmentedSymbol::Nonterminal(predicted))) => actual == predicted,
_ => false,
}).filter_map(|item| item.advance())
.collect::<HashSet<_>>();
// states join= { B -> . gamma | A -> alpha . B beta in states, B -> gamma in grammar }
predict(&mut states, grammar);
}// loop for symbol in stack.iter()
if states.is_empty() {
// states が空になってしまった場合は終了
return false;
} else if let Some(completed) = states.iter().find(|item| item.is_completed()) {
// 還元できる状態で止まった場合は還元してもう一度
for _ in 0..completed.rule.body.len() { stack.pop(); }
stack.push(ParseNode::Reduction(completed.rule.head.clone()));
} else {
// states は空にならなかったが、還元もできない場合は終了
return true;
}
}
}
fn predict<T: Hash + Eq + Clone>(states: &mut HashSet<GrammarItem<AugmentedTerminal<T>, T>>, grammar: &CFG<T>) {
loop {
// イテレータ使用中は states に要素を追加できないので、一旦 new_items に溜める.
let mut new_items = HashSet::new();
for item in states.iter() {
if let Some(general::Symbol::Nonterminal(predicted)) = &item.next_symbol() {
for rule in &grammar.rules {
if rule.head == *predicted {
new_items.insert(AugmentedGrammarItem { rule: rule_to_augmented(rule), dot_position: 0 });
}
}// 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 rule_to_augmented<T>(rule: &ProductionRule<T>)
-> AugmentedProductionRule<T>
where T: Clone
{
AugmentedProductionRule {
head: rule.head.clone(),
body: rule.body.iter().map(|symbol| match symbol {
general::Symbol::Terminal(terminal) => general::Symbol::Terminal(Terminal { kind: AugmentedTerminal::Terminal(terminal.kind.clone()) }),
general::Symbol::Nonterminal(nonterminal) => general::Symbol::Nonterminal(nonterminal.clone()),
}).collect::<Vec<_>>()
}
}
アルゴリズムの図示
コード中の naive_lr0_internal ではスタック上の記号をひとつずつ読みながら状態を書き換えていくのだが、この遷移を図に起こしたものを示す.
赤い矢印が predict によって追加されるもの、青い矢印が非終端記号を読んだ時のもの、黒い矢印が終端記号を読んだ時のものである.
二重に囲まれている頂点はドットが末尾にあるもの、つまり、そこで還元が発生する状態を意味している.
DFA に基づく改良
LR(0) 構文解析とオートマトン
前の見出しの時点でネタバレではあったのだけれど、実は、スタックの状態を検証として実行していたものは、ある種の非決定性有限オートマトン (Nondeterministic Finite Automaton, NFA) によってスタック上の列が受理されるかどうかを確かめることであった.
この言語は、つまり (文脈自由文法による) この構文解析が成功する場合に stack の状態としてあり得るものは、次の集合によって表現できる.
L_{\text{viable}}(G) = \set{
\alpha\ \beta
\mid
S \stackrel{\text{rm}\quad} {\Longrightarrow^\ast}
\alpha\ A\ w \stackrel{\text{rm}} {\Longrightarrow}
\alpha\ \beta\ w }
ここで、記号 $S \stackrel{\text{rm}}{\Longrightarrow} \alpha$ は最右導出を意味する.
(rm は下付きにする方が多いように思うが、TeX に不慣れできれいに表示できなかった.)
この集合 $L_{\text{viable}}(G)$ は文脈自由文法 $G$ の viable prefix (可延頭部) と呼ばれ、実は、これが (任意の文脈自由文法 $G$ に対して) 正規言語となることが知られている. (証明は大堀淳「LR構文解析の原理」などを参照のこと. この記事では $L_{\text{viable}}(G)$ としているが、大堀の PDF では $C_G$ と呼ばれている.)
詳しくは形式言語理論のテキストを読んでもらえればよいと思うが、任意の正規言語にはその言語における文を (そしてそれらの文のみを) 受理するような NFA が存在する. この言語を受理するオートマトンが、あとで見るが、ある条件を満たすときに LR(0) 構文解析が行え、この条件を満たす文法を LR(0) 文法と呼ぶ.
所で任意の NFA には、弱等価な決定性有限オートマトン (Deterministic Finite Automaton, DFA) が存在することが知られている. 通常 NFA よりは状態数の少ない DFA の方が効率的に動作するから、naive_lr0_internal は DFA を使うようにするだけで改良できる.
また、スタックに記号が追加されるたび NFA を構築して一から動作させる代わりに、現在の状態を保持したままで追加された記号による遷移を考えるようにすればなおよい. 還元が起きた場合も同様に、再度オートマトンを構築するのではなく、適当な所まで状態を巻き戻すようにすれば構築を最初の一度に限定することができる. こうして得られるアルゴリズムこそが LR(0) 構文解析だ.
$L_{\text{viable}}(G)$ が正規言語であることが LR(0) 構文解析を実現する上で如何に大きな働きをしていることか. LR(0) 構文解析でスタックの状態として現れるこれが正規言語であり、DFA によって効率的な検証が可能であるという基礎の上にすべてが成り立っているのだ. この事実が LR(0) 構文解析を成立させる理論的支柱であり、同時に難しさの源泉でもある.
DFA に基づく動作のイメージ
LR(0) 構文解析表の構築 / 冪集合構成法
NFA から(弱-)等価な DFA を得るアルゴリズムとして冪集合構成法 (powerset construction、あるいは部分集合構成法 (subset construction)) と呼ばれるものがあるのだった.
実行コストは NFA よりも DFA の方がよいから、通常は DFA を利用する. また、NFA を構築してから冪集合構成法を適用するのではなく、文法アイテムを上手く駆使して最初から DFA を構築する方が一般的である. こうして作られる DFA をこの記事では LR(0) オートマトンと呼ぶこととする.
具体的な構築手法はビジュアライザを参照されたし.
LR(0) 構文解析の動作
DFA が構築できたとすると、LR(0) 構文解析は次のような擬似コードで表現できるだろう.
INPUT: 文法 grammar、記号列 tokens
OUTPUT: Ok(構文解析木)、または Err(())
PROCEDURE:
{
start, // 開始記号. S' -> . S を含む状態
transition, // 遷移関数. Map<状態, Map<記号, 状態>>
final_states, // オートマトンにおける最終状態の集合. Set<状態>. ドットが末尾に存在するアイテムを含んでいる状態の集合.
// states,
// symbols,
rule_to_reduce, // Map<状態, 生成規則>. その状態に含まれていてドットが末尾に存在するアイテム A -> α . に用がある. DFA の定義は上の 5 つだが、構文解析はそれに加えてこのマップを必要とする.
} = build_dfa(grammar);
symbol_stack = new Stack();
state_stack = new Stack();
state_stack.push(start);
pos = 0;
loop {
// TRY REDUCE (A -> ε のような生成規則を考慮して SHIFT の前)
loop {
current_state = state_stack.peek();
if current_state が final_states に含まれない {
// 今はまだ還元するときではない
break;
}
A -> alpha = rule_to_reduce[current_state];
if A == S' {
// S' -> S の還元が発生
return Ok(symbol_stack.pop());
}
// REWIND. alpha を読み込んでいた部分を巻き戻す.
children = symbol_stack から |alpha| の数だけ pop (して逆順にする);
state_stack から |alpha| の数だけ pop;
// REDUCE. 還元する.
new_root = Tree:new(A, children);
symbol_stack.push(new_root);
// ADVANCE. 記号 A によって遷移する.
new_state = transition[current_state][A];
if new_state (curren_state からの A による遷移先) が存在しない {
return Err(());
}
state_stack.push(new_state);
}
// SHIFT
if pos == tokens.length {
// 記号を読み切ったにもかかわらず終了していない場合はエラー
return Err(());
}
current_state = state_stack.peek();
current_symbol = tokens[pos];
symbol_stack.push(current_symbol);
new_state = transition[current_state][current_symbol];
if new_state (curren_state からの current_symbol による遷移先) が存在しない {
// 未知のトークンなり期待に反する記号なりが現れたのでエラー
return Err(());
}
state_stack.push(new_state);
++pos;
}
標準的な LR(0) 構文解析の動作
上では
{
start, // 開始記号. S' -> . S を含む状態
transition, // 遷移関数. Map<状態, Map<記号, 状態>>
final_states, // オートマトンにおける最終状態の集合. Set<状態>. ドットが末尾に存在するアイテムを含んでいる状態の集合.
// states,
// symbols,
rule_to_reduce, // Map<状態, 生成規則>. その状態に含まれていてドットが末尾に存在するアイテム A -> α . に用がある. DFA の定義は上の 5 つだが、構文解析はそれに加えてこのマップを必要とする.
} = build_dfa(grammar);
としてこれらを使っていたが、一般的には shift-reduce 構文解析の文脈に寄せて ACTION/GOTO というふたつの構文解析表を使って実装される. ただし、LR(0) 構文解析では ACTION の意義が分かりにくいだろうから、SLR(1) の所で改めて説明する.
SLR(1)
次のような文法を考える.
G = \left\lbrace\begin{align*}
S \to\ & a\ A\ c \\
S \to\ & a\ B\ d \\
A \to\ & z \\
B \to\ & z
\end{align*}\right\rbrace
これから作られる LR(0) オートマトンは次のようになる.
状態 5 に注目すると、ドットが末尾に到達しているアイテムは A → z .、B → z . のふたつが存在して、どちらで還元するべきかが決定できない. そのため、構文解析の過程を一意に定めることができないから構文解析は失敗とされる. このような状況を reduce/reduce conflict と言う.
この問題は、z の次の文字が何であるかを見ることによって解消できる場合がある. 今回で言えば、azc は S → aAc → azc のように生成され、azd は S → aBd → azd のように生成されるから、z の次が c であるか d であるかまで考慮することで解決できる.
SLR(1) 構文解析は、この先読みで期待される記号として、FOLLOW 集合を使用する.
(FOLLOW 集合については以前 LL(1) 構文解析の解説で説明した.)
つまり、SLR(1) 構文解析では LR(0) オートマトンを利用しつつ、$N \to \alpha .$ による還元が、その文法アイテムを含む状態にあって、先読み記号が $\text{FOLLOW}(N)$ である場合に限り発生するようにする.
上の文法で言えば、
\begin{align*}
\text{FOLLOW}(S') &= \{ \text{EOS} \} \\
\text{FOLLOW}(S) &= \{ \text{EOS} \} \\
\text{FOLLOW}(A) &= \{ \text{c} \} \\
\text{FOLLOW}(B) &= \{ \text{d} \}
\end{align*}
であることに注意して、次のような SLR(1) オートマトンを構築することができる.
ここで、[ ] の中にある記号はそのアイテムで還元を発生させる先読み記号を表すものとしている.
DFA に基づく構文解析動作のイメージ
DFA に基づいて SLR(1) 構文解析を実施する擬似コードを示す. ここで説明する方法は LR(1)、LALR(1) でも同じように動作する.
INPUT: 文法 grammar、拡張された記号列 tokens
OUTPUT: Ok(構文解析木)、または Err(())
PROCEDURE:
{
start, // 開始記号. S' -> . S を含む状態
transition, // 遷移関数. Map<状態, Map<記号, 状態>>
final_states, // オートマトンにおける最終状態の集合. Set<状態>. ドットが末尾に存在するアイテムを含んでいる状態の集合.
// states,
// symbols,
rule_to_reduce, // Map<状態, Map<先読み記号, 生成規則>>. その状態に含まれていてドットが末尾に存在するアイテム A -> α . [a] に用がある. DFA の定義は上の 5 つだが、構文解析はそれに加えてこのマップを必要とする.
} = build_dfa(grammar);
symbol_stack = new Stack();
state_stack = new Stack();
state_stack.push(start);
pos = 0;
loop {
if pos == tokens.length {
// 記号を読み切ったにもかかわらず終了していない場合はエラー
return Err(());
}
lookahead = tokens[pos];// LR(0) とは異なり先読みを利用する.
// TRY REDUCE (A -> ε のような生成規則を考慮して SHIFT の前)
loop {
current_state = state_stack.peek();
if current_state が final_states に含まれない {
// 今はまだ還元するときではない
break;
}
A -> alpha = rule_to_reduce[current_state][lookahead];
if A -> alpha が存在しない {
// 先読み記号が lookahead である場合は還元を見送る
break;
}
if A == S' {
// S' -> S の還元が発生
return Ok(symbol_stack.pop());
}
// REWIND. alpha を読み込んでいた部分を巻き戻す.
children = symbol_stack から |alpha| の数だけ pop (して逆順にする);
state_stack から |alpha| の数だけ pop;
// REDUCE. 還元する.
new_root = Tree:new(A, children);
symbol_stack.push(new_root);
// ADVANCE. 記号 A によって遷移する.
new_state = transition[current_state][A];
if new_state (curren_state からの A による遷移先) が存在しない {
return Err(());
}
state_stack.push(new_state);
}
// SHIFT
current_state = state_stack.peek();
current_symbol = lookahead;// 先読み記号として使っていたものをここで実際に読み込む
symbol_stack.push(current_symbol);
new_state = transition[current_state][current_symbol];
if new_state (curren_state からの current_symbol による遷移先) が存在しない {
// 未知のトークンなり期待に反する記号なりが現れたのでエラー
return Err(());
}
state_stack.push(new_state);
++pos;
}
標準的な構文解析動作のイメージ
上では
{
start, // 開始記号. S' -> . S を含む状態
transition, // 遷移関数. Map<状態, Map<記号, 状態>>
final_states, // オートマトンにおける最終状態の集合. Set<状態>. ドットが末尾に存在するアイテムを含んでいる状態の集合.
// states,
// symbols,
rule_to_reduce, // Map<状態, Map<先読み記号, 生成規則>>. その状態に含まれていてドットが末尾に存在するアイテム A -> α . [a] に用がある. DFA の定義は上の 5 つだが、構文解析はそれに加えてこのマップを必要とする.
} = build_dfa(grammar);
としてこれらを使っていたが、一般的には shift-reduce 構文解析の文脈に寄せて ACTION/GOTO というふたつの構文解析表を使って実装される. ここで説明する方法は LR(1)、LALR(1) でも同じように動作する. ここでははっきり DFA と ACTION/GOTO 表とを区別し作成しているが、どの程度分離するかは実装に拠るだろう.
{
start, // 開始記号. S' -> . S を含む状態
transition, // 遷移関数. Map<状態, Map<記号, 状態>>
final_states, // オートマトンにおける最終状態の集合. Set<状態>. ドットが末尾に存在するアイテムを含んでいる状態の集合.
// states,
// symbols,
rule_to_reduce, // Map<状態, Map<先読み記号, 生成規則>>. その状態に含まれていてドットが末尾に存在するアイテム A -> α . [a] に用がある. DFA の定義は上の 5 つだが、構文解析はそれに加えてこのマップを必要とする.
} = build_dfa(grammar);
enum Action {
Shift(destination),
Reduce(n, A),
// Accept, // 必要に応じて定義する
// Error
}
// transition は、終端記号による遷移が ACTION 内の Shift 動作として、非終端記号による遷移は GOTO 表へと分割される.
// final_states/rule_to_reduce は ACTION 内の Reduce 動作に変換される.
ACTION = new Map<状態, Map<記号, Action>>();
GOTO = new Map<状態, Map<非終端記号, 状態>>();
for (state, moves) in transition {
for (symbol, destination) in moves {
if symbol が終端記号 {
if ACTION[state][symbol] に何かが設定されている {
// shift/reduce conflict
return Err(());
}
ACTION[state][symbol] = Shift(destination);
} else /* if symbol が非終端記号 */ {
GOTO[state][symbol] = destination;
}
}
if state が final_states に含まれない {
// この状態は還元に関わらない
continue;
}
for (lookahead, A -> alpha) in rule_to_reduce[state] {
if ACTION[state][symbol] に何かが設定されている {
// shift/reduce conflict または reduce/reduce conflict
return Err(());
}
ACTION[state][lookahead] = Reduce(|alpha|, A);
// A -> alpha == S' -> S であるとき、Reduce ではなく Accept を設定してもよい
}
}
// スタックを分けない実装もあるが、流石に分けた方がよいと思う.
// (分けない説明が多いのは、Knuth[1965] が分けなかったからだろうか？)
symbol_stack = new Stack();
state_stack = new Stack();
state_stack.push(start);
pos = 0;
loop {
current_state = state_stack.peek();
current_symbol = tokens[pos];
action = ACTION[current_state][current_symbol];
match action {
Shift(destination) => {
// current_symbol は読み込まれるべき記号として機能する
symbol_stack.push(current_symbol);
state_stack.push(destination);
++pos;
}, Reduce(n, A) => {
// current_symbol は先読み記号として機能する
// A -> alpha による還元
// n = |alpha|
if A == S' {
// S' -> S の還元が発生
// これを Reduce ではなく Accept にしておけばこの if 文はいらない (match 文に置き換えられる)
return Ok(symbol_stack.pop());
}
// REWIND. alpha を読み込んでいた部分を巻き戻す.
children = symbol_stack から n(=|alpha|) の数だけ pop (して逆順にする);
state_stack から n(=|alpha|) の数だけ pop;
// REDUCE. 還元する.
new_root = Tree:new(A, children);
symbol_stack.push(new_root);
// ADVANCE. 記号 A によって遷移する.
new_state = GOTO[current_state][A];
if new_state (curren_state からの A による遷移先) が存在しない {
// 作り方からして存在しないことはないはず
return Err(());
}
state_stack.push(new_state);
}, _ /* Error/None */ => {
// 未知のトークンなり期待に反する記号なりが現れたのでエラー
return Err(());
}
}
}
current_symbol が action の種類に応じて二種類の意味で使われるので読みにくいようにも思われるが、ACTION 表を作成することで shift/reduce conflict を検出しやすくする意味があるのかもしれない.
LR(1)
次の文法とそれから作られる SLR(1) オートマトンについて考える.
G = \left\lbrace\begin{align*}
S \to\ & L\ =\ R \\
S \to\ & R\ \\
L \to\ & *\ R \\
L \to\ & \text{id} \\
R \to\ & L \\
\end{align*}\right\rbrace
状態 2 に注目すると、$R \to L . [\text{EOS}, =]$ を持つから、先読み記号が = である場合に還元することができる. しかし、記号 = は状態 6 への遷移を引き起こすものでものある.
従って、状態 2 にあり先読み記号が = である場合二種類の選択肢がある.
- $R \to L . [\text{EOS}, =]$ に従って還元する.
- 還元を見送り記号
=を読み込むことによって、状態 6 へ遷移する.
SLR(1) ではこの曖昧さを解消できないから、構文解析に失敗する (どちらかを優先するものとすることで無理やり構文解析できる場合もあるが、言語 $L(G)$ であるにもかかわらず構文木に対応付けることができない文もまた存在してしまうことだろう).
これは、SLR(1) 構文解析が先読み記号として FOLLOW 集合のみに頼っていた点に問題があったと言える.
SLR(1) では LR(0) オートマトンをそのまま流用していたが、LR(1) 構文解析ではここから見直す. (n.b. アルゴリズム発表の時系列的には (LR(0) → ) LR(1) → SLR(1))
LR(1) 構文解析に対応する NFA は次のように構築できる.
- 開始状態は $S' \to S\ [\text{EOS}]$. これを状態集合 $Q$ に追加する.
- $Q$ に変化がある限り次を繰り返す.
- $A \to\ \alpha\ .\ X\ \beta\ [a] \in Q$ があるとき、次のアイテム/遷移を追加する.
- $A \to\ \alpha\ X\ .\ \beta\ [a]$ への $X$ による遷移.
- $X$ が非終端記号であるとき、$X \to\ \gamma\ [b]$ への $\epsilon$ による遷移. ただしここで、$b \in \text{FIRST}(\beta\ a)$
- $A \to\ \alpha\ .\ X\ \beta\ [a] \in Q$ があるとき、次のアイテム/遷移を追加する.
通常は LR(0) オートマトンと同様に DFA を構築して使用する.
LALR(1)
LR(1) 構文解析は強力だが、構文解析表 (ないしオートマトンの状態数) が増大しがちであって、計算資源に乏しい時代では扱いにくいものであった. そこで、より実用的な構文解析手法として編み出されたものが LALR(1) (と SLR(1)) である.
n.b. 構文解析手法としての強力さは $\text{LR}(0) < \text{SLR}(1) < \text{LALR}(1) < \text{LR}(1)$.
LALR(1) via LR(1) オートマトン
LALR(1) オートマトンの構築には大きくふたつのアプローチが存在する.
まずは LR(1) オートマトンを加工して作る方法を見ていこう.
次の文法から作られる LR(1) オートマトンを出す.
G = \left\lbrace\begin{align*}
S \to\ & L\ =\ R \\
S \to\ & R\ \\
L \to\ & *\ R \\
L \to\ & \text{id} \\
R \to\ & L \\
\end{align*}\right\rbrace
この LR(1) オートマトンを眺めると、状態 4 と状態 11 はよく似ている. 先読み記号部分を無視すると、どちらも同じアイテムからなる状態である. 5 と 12、7 と 13、8 と 10 もそれぞれ同様だ. そこで、それらをひとつの状態と見なしてまとめてみよう.
こうして作られたオートマトンを使って構文解析を実施するのが LALR(1) である.
LALR(1) via LR(0) オートマトン
LALR(1) オートマトンは LR(0) オートマトンを加工して構築することもできる.
同じ文法から作られた LR(0) オートマトンを表示する.
上の LALR(1) オートマトンと LR(0) オートマトンをそれぞれ見比べると、先読み記号の違いを除いて全く同じオートマトンであることが分かるだろう. それもそのはずで、LR(1)、LR(0) どちらのオートマトンでも同じ状態に含まれるアイテムは NFA 上で ε-遷移によって到達できるアイテムの集合である. どちらもアイテム $A \to\ \alpha\ . B\ \beta$ を含めば $B \to\ .\ \gamma$ も含むのだから、先読みの違いを無視して状態を併合していく LALR(1) via LR(1) の結果は先読みの違いを無視して LR(0) オートマトンに一致する.
ゆえに、LALR(1) via LR(1) の状態で先読み記号として何が入っているかを理解できれば、巨大な LR(1) オートマトンを構築する労なくして LALR(1) オートマトンが手に入るというわけだ.
$A \to\ \alpha\ .\ X\ \beta\ [a]$ を含む状態から $X \to\ \gamma\ [b]$ を含む状態への 遷移があるとき $b \in \text{FIRST}(\beta\ a)$ であるから、いわばこれは生成規則単位の FOLLOW 集合だと見なせるだろう.
(LR(0) オートマトンが手に入っていればあえて FIRST 関数を持ち出す必要もないから、標準的な説明では $\text{FOLLOW}_\text{rulewise}$ みたいな関数があえて定義されることはない)
参考文献
①導入で書いたものの他に、以下を参照しました.
- 大堀淳、「LR構文解析の原理」、2013
- LR(0) 構文解析とオートマトンの関係について詳しい
- Knuth, D. E.、「On the translation of langages from left to right」
- LR(k) 構文解析に関する歴史的論文. 読む場合は、末尾記号として
$ではなく $\dashv$ (\dashv) を使っていたり、文法アイテムではなく生成規則の番号p、ドットの位置j、先読み記号(の列) $\alpha$ の組 $[p, j; \alpha]$ を使っていたりと記号の使い方を把握するところから始めなくてはならない.
- LR(k) 構文解析に関する歴史的論文. 読む場合は、末尾記号として