CYK法
このアルゴリズムを、文が言語に含まれるかどうかを決定するだけでなく、構文木を構築するよう拡張するには、構文木のノードをブーリアンの代わりに配列の要素として格納すればよい。認識しようとする文法は曖昧な場合があるので、ノードのリストを格納する必要がある(可能な解釈からひとつだけ選べばよい場合はその限りではない)。従って、結果として複数の構文木が得られる。別の方式としては、backpointers と呼ばれる第二のテーブル B[n,n,r] を使う方式もある。
加重文脈自由文法や確率文脈自由文法を使って文字列の構文解析をするよう拡張することも可能である。この場合、加重や確率はテーブル P にブーリアンの代わりに格納される。すなわち、P[i,j,A] は i から長さ j の並びが A から生成される最小加重(または最大確率)を格納する。さらにアルゴリズムを拡張すれば、あらゆる加重(確率)の構文木を列挙できる。