5.6 左正则语言

在左正则语法中，所有规则都是A→a或A→Ba（其中a非终结符，A和B为非终结符）形式。图Fig5.22给出了与图Fig5.6等效的左正则语法。

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

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

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

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

现在，我们看到规则A → Bt对应于转换B_f$$\stackrel{t}{\to }$$A_f，规则S_S→Bt对应B_f$$\stackrel{t}{\to }◊$$，那A → t形式的规则呢？结束t的转换之后，我们就处于状态A_f，但我们是从哪开始的呢？答案是我们还没看到任何一个终结符产生，因此我们处于状态ε_f，这就是起始符号！因此规则A->a和B->a对应的转换是 ε_f$$\stackrel{\ast \ast a\ast \ast }{\to }$$A_f 和 ε_f$$\stackrel{\ast \ast a\ast \ast }{\to }$$B_f ，图Fig5.7的另外两个部分。接下来我们通过修改状态名称，继续快速重建图Fig5.7的转换图：

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

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

必须被替换为：

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