head集合の作成 🔗

nullable集合を元に規則の先頭に来うる記号を集約する。これをhead集合とする。
非終端記号の場合は、非終端記号のhead集合を集約する。

start : a b
      | c
a : 'A'
b : 'B'
c : 'C'

↓

startのhead集合は 'A'、'C' となる
aのhead集合は 'A' となる
bのhead集合は 'B' となる
cのhead集合は 'C' となる

head集合の作成は次の疑似コードで表す。
これをなくなるまで全ての行に対し行う。

head_first = 行頭を抽出

foreach (x in head_first)
    if (xの規則の先頭が終端記号であれば)
        head集合[xの左辺]にxの規則の先頭を追加

foreach (x in head_first)
    if (xの規則の先頭が非終端記号であれば)
        foreach (y in head_first[xの規則の先頭])
            head_first[xの左辺]にyを追加