拓广的左线性递归变换算法及其正确性

摘要

本文给出拓广的左线性递归变换算法并证明其正确性。拓广的左线性递归中可以包含一个或多个ＩＤＢ谓词，它是左线性递归的一般化和左线性递归计算算法一样，本文提供的算法遵循魔集的模式：首先改写规则，然后用半扑质的自底向上算法计算新规则，算法的有效性也在本文作简略讨论。