广义左,右线性递归规则组改写

本文从左，右线性递归规则组的定义出发，提出了广义左，右线性递归规则组的定义，放宽了左，右线性递归规则组寻规则形式的限制，扩展了Ｕｌｌｍａｎ提出的左，右线性递归规则组改写方法的适用范围。本文证明了由广义左，右线性递归规则组向左，右线性规则组转换的相容性，并给出了具体的转换算法。

RULE TRANSFORMATION FOR GENERAL RIGHT-AND LEFT-LINEAR RECURSIVE RULES

This paper gives the definitions of general right-linear and left-linear recursive rules. The definitions weaken the restriction, imposed by the definition ofright-linear and left-linear recursive rules, on the form of linear recursive rule. It is proved that any general right-linear and left-linear recursive rule can be rewritteninto a set of right-linear and left-linear recursive rules with same semantics, and the algorithm of the transformation is presented in this paper. Therefore, the optimization strategy for right-linear and left-linear recursive rules proposed by Ullman canbe used in a wider range of linear recursive rules.