5.6 左正则语言

在左正则语法中,所有规则都是A→aA→Ba(其中a非终结符,AB为非终结符)形式。图Fig5.22给出了与图Fig5.6等效的左正则语法。

左正则语法经常被作为右正则语法的变体放在一边,但不论是形式还是给人的感觉都是截然不同的。例如,从语法中生成一个字符串。假设我们要生成5.3节中的句子abcba。为此,我们首先需要确定即将访问的所有状态,并且只有当最后一个状态也确定之后,才能生成第一个令牌:

图1

一旦第一个令牌可用了,那么其他都可以了,并且我们也不再有别的选择了;这与右正则语法的生成过程大相径庭。

解析左正则语法同样很奇特。很容易看到,我们有了所有状态的集合 {S,A,B,C},但如果我们看到在输入中有一个a,我们可以在两个规则B->aA->a中互移a。假设我们使用规则A->a;我们将会处于什么状态呢?规则不指定除A以外的任何状态;那这样的移动有什么作用呢?

简单的方法是将语法转换为右正则语法(见下文),但尝试寻找A->a中移动a的意义也是非常有意思的。在这样一个操作之后我们唯一知道的就是,我们刚刚完成了A的生成,因此我们所处的状态可以描述为“A完成”;我们将这种状态写作Af。同样的,图Fig5.22的第一条规则表示,我们处于状态Cf并移动a时,我们的状态会是Sf;这就是一个转换Cf$$\overset{a}{\rightarrow}$$Sf。然后我们就知道“S完成”意味着我们已经解析了S的一个完整生成;因此状态**Sf**就是可接受状态♦,我们可以在图Fig5.7看到最右侧转换。

现在,我们看到规则A → Bt对应于转换Bf$$\overset{t}{\rightarrow}$$Af,规则SS→Bt对应Bf$$\overset{t}{\rightarrow}\lozenge$$,那A → t形式的规则呢?结束t的转换之后,我们就处于状态Af,但我们是从哪开始的呢?答案是我们还没看到任何一个终结符产生,因此我们处于状态εf,这就是起始符号!因此规则A->aB->a对应的转换是 εf$$\overset{a}{\rightarrow}$$Afεf$$\overset{a}{\rightarrow}$$Bf ,图Fig5.7的另外两个部分。接下来我们通过修改状态名称,继续快速重建图Fig5.7的转换图:

图2

这暴露的初始状态和可接受状态之间的不对称,与初始状态不同,可接受状态对应于语法中的一个符号。这种不对称,可以通过替换为一个更中性的符号部分消除,例如$$\square$$。然后我们就获得了下面介于左正则和右正则之间的语法:

图3

从左正则语法中获取一个正则表达式很简单:5.4.2节中的大多数算法都可以在最小代价下被接管。只需要将转换方式由递归变成重复:

图4

必须被替换为:

图5

其中β'由所有α的备选项组成,每个都附加上 (R) 。这是因为A->aA|b产生a* b,而A->Aa|b产生ba*