look-a-headの作成 🔗

還元のタイミングで先読みを行いシフトか還元かを求める必要がある。
還元する規則のfollowable集合を先読み規則とする。

余談: GNU/bisonの場合 🔗

次のような構文規則で call: VAR '(' . args ')' の時に ';' という誤った先読み記号を読み取るとエラーになるが、
GNU/bisonで作成した構文解析器で実行すると、$default reduce using rule 8 (void) とある通りエラーになる前に void、args が還元してしまう。
これは void が文脈に関係なく還元するためである。
全体としてエラーにはなるので問題になる事はないが、余計な還元をしてしまう事態が起こる。

stmt : call ';'
     | void ';'
call : VAR '(' args ')'
args : void
     | argn
argn : VAR
     | argn ',' VAR
void :

---

state 5

    3 call: VAR '(' . args ')'

    VAR  shift, and go to state 9

    $default  reduce using rule 8 (void)

    args  go to state 10
    argn  go to state 11
    void  go to state 12

空規則以外のフォロー 🔗

空規則以外の先読み記号はfollow集合に頼らざるを得ない。
次のような構文規則において start : 'A' . bvoid 'C' | 'A' . bvoid 'D' から 'B' を読み込み bvoid : 'B' . となった際の先読み記号はfollow集合そのままの ['C', 'D', 'X'] となってしまう。
最初に 'A' を読み込んだ時点で 'X' の先読み記号は存在しないのは明白であるにもかかわらず、bvoid : 'B' . ['C', 'D', 'X'] としてしまうのである。

start : 'A' bvoid 'C'
      | 'A' bvoid 'D'
      | bvoid 'X'
bvoid : 'B'
      | void
void  :

原因はノードの作りが start : 'A' . bvoid 'C' | 'A' . bvoid 'D' から来たbvoidなのか、start : . bvoid 'X' から来たbvoidなのか区別していないため、ありえない先読み記号で還元を起こしてしまうのである。
ノード図を見ても 'B' の遷移先がまとめられてしまっていることが分かる。
状態毎にノードを増やしたり、実行時のスタックを見ることで先読み記号を絞ることができなくもないが、通常そこまでこだわる必要はないため許容する。

graph TD
	classDef default text-align:left
	classDef highlight color:red
	0["$ACCEPT : . start $END<br>start : . 'A' bvoid 'C'<br>start : . 'A' bvoid 'D'<br>start : . bvoid 'X'<br>bvoid : . 'B'<br>bvoid : . void<br>void : . ['X']"]
	1["$ACCEPT : start . $END"]
	2["$ACCEPT : start $END ."]
	3["start : 'A' . bvoid 'C'<br>bvoid : . 'B'<br>bvoid : . void<br>void : . ['C', 'D']<br>start : 'A' . bvoid 'D'"]
	4["bvoid : 'B' . ['C', 'D', 'X']"]:::highlight
	5["bvoid : void . ['C', 'D', 'X']"]
	6["start : 'A' bvoid . 'C'<br>start : 'A' bvoid . 'D'"]
	7["start : 'A' bvoid 'C' . [$END]"]
	8["start : 'A' bvoid 'D' . [$END]"]
	9["start : bvoid . 'X'"]
	10["start : bvoid 'X' . [$END]"]
	0 -- start --> 1
	0 -- 'A' --> 3
	0 -- bvoid --> 9
	0 -- 'B' --> 4
	0 -- void --> 5
	1 -- $END --> 2
	3 -- 'B' --> 4
	3 -- void --> 5
	3 -- bvoid --> 6
	6 -- 'C' --> 7
	6 -- 'D' --> 8
	9 -- 'X' --> 10