5.1.1 CF解析中的正则语言

​ 在一些CF文法的解析器中,一个子分析器会在处理正则文法的时候被识别。这样一个子分析器是隐式地明确地基于下列这种令人惊讶的现象。考虑到最左推导和最右推导两种句子形式,这种句子形式由两部分组成,一个是关闭(结束)的部分,包含终结符,和一个开放(未结束)的部分,包含非终结符。在最左推导中,开放的部分,开始于最左边的非终结符,然后向右扩展,在最右推导中,开放的部分,开始于最右的非终结符,然后向左扩展。

Fig.5.1

​ 显而易见的是,句中的开放部分在CF分析方法中其中非常重要的作用,能被正则文法描述,文法遵循CF文法。

​ 为了解释得更加清楚,我们首先来解决一个概念上的问题,依惯例,使用大写字母来表示非终结符,小写字母表示终结符,然后接下来,我们将书写能产生句子形式的文法,自此这些句子形式中能包含非终结符,我们的文法中也能产生非终结符。为了在这个过程中从“活”的非终结符中区分出“死”的非终结符,我们在字符上用一根短线来表示,就像这样,$\overline{x}$.

​ 伴随着上述提到的概念,我们来创建一个正则文法G,以一个开始符号R作为在2.4.3节中用到过的文法C的最左推导的开放部分。我们重复:

Fig.5.1

​ G中开始符号R的第一种可能是产生C的开始符号,所以我们得到R--->$\overline{S}$,这里$\overline{S}$只是一个标记(token),下一步是这个标记,成为句子形式中最左端的非终结符,它被转换成一个“活”的非终结符,从中我们将产生更多的句子形式,他们来自 R--->S。这里S是一个G中的非终结符,描述源于C中的S的句子形式中的开放部分。G中S的第一种可能是产生c中S的右边就像标记(tokens): S--->$\overline{L}$&$\overline{N}$,但是也可能是$\overline{N}$,成为句子最左侧的非终结符,L已经被激活: S--->L&$\overline{N}$,它甚至可能结束推导进程,因此,所有标记已经成为句子形式的关闭部分的一部分。开放部分&$\overline{N}$被留下,所以句子形式变为S--->&$\overline{N}$,接下来我们可以把&从开放部分移出去到关闭部分:S--->$\overline{N}$,又一次,这个$\overline{N}$变得能够产生句子,所以被激活:S--->N,就像上面的L,N最终完全消失: S--->ε。我们看到了原本的S--->$\overline{L}$&$\overline{N}$是怎样逐渐变为S--->ε,C中S的第二种选择是S--->N,推导过程的规则是S--->N¯, S--->N, 然后 S--->ε,这个推导我们上面已经做过了。

​ 上述过程介绍了G中的非终结符L和N。它们的规则可以用与S相同的方法导出;结果是图5.2中的左正则语法。我们已经看到这个过程能创建同一个规则的副本。我们现在知道它也能产生循环,例如规则 L--->L,在图中被标为×,因为这样的规则没有任何贡献,所以被拒绝了。

Fig.5.2

​ 相似地,在最右推导中一个右正则语法能构建句子形式的开放部分。这种文法有益于理解自顶向下和自底向上分析(第六章和第七章的内容),是一些解析器功能的基础(9.13.2和10.2.3节)。

results matching ""

    No results matching ""