ノードの作成 🔗

文法ファイルから構文規則を読み取ったのち、2つの操作を行う必要がある。
ACCEPTの付与と読み取り位置毎のノードへの分解である。

ACCEPTの付与 🔗

文法規則には末尾まで到達すると終了するという情報を付与しないといけない。
そのため、$ACCEPT : start $ENDという構文規則を自動で付与する。
$ACCEPTは開始の構文規則で、$ENDは末尾を表す。
$ENDは字句解析器によって与えられるが、おおむねファイル末尾などを表す。

$ACCEPT : start $END

start : FIRST SECOND THIRD

なお、本章以降は$ACCEPT : start $ENDが自動付与されたものとして説明は省略する。

ノードへの分解 🔗

構文規則の間に.を入れたデータ構造を作成し、ノードと呼ぶ。
ここでは単純に構文規則の間に.を入れただけのノード群を作成する。
構文規則の並び順が隣のノードに向かってNextというリンクリストを作成する。

$ACCEPT : start $END
start : FIRST SECOND THIRD

↓

ノード0 : $ACCEPT : . start $END
ノード1 : $ACCEPT : start . $END
ノード2 : $ACCEPT : start $END .
ノード3 : start : . FIRST SECOND THIRD
ノード4 : start : FIRST . SECOND THIRD
ノード5 : start : FIRST SECOND . THIRD
ノード6 : start : FIRST SECOND THIRD .

ここではノード0→1→2やノード3→4→5→6のようにつながっているのみである。