のみが結果として残さ
れており, に含まれる記号から, 
を導出する過
程は残されていない. これを行なうためには 
を計算する時に, そ
れと並行して,
という集合を保持しておけばよい. つまり, 
には, 
なる各記号sに対して,
を導出するに当たって, 次に適用すべき
文法規則 
(または同じことだが解析木の左右の子供の
記号s'およびs''),
が生成され, s''から 
が生成されるとした時の, kの値.
の要素一つをエッジと呼ぶ. 定義
からわかるように の要素は, のsが等しいもの同士の重
複を取り除いたものになっており, したがって の要素数は通常
の要素数よりもずっと少ない. アルゴリズム中は が重要に
なることがないので記述から省略しているが, 実際には の生成コス
トは全計算時間中の大きな比重を占める. 上のアルゴリズムをエッジを生成す
る部分を含めて書くと, 図5.3のようになる.
