从零开始写个编译器吧 - 分析非终结符

java 5 2016-02-29 13:03
女装

tao 语言的 Parser 的语法分析是不带回溯的,自顶向下的。文法选用 LL(1),这种文法虽然略显薄弱,但还尚可用。

回顾上一章提到的 LL(1) 的定义,可以得出如下结论。

在不考虑 ε 时,对于一个非终结符,它的每一个产生式都有一个FIRST 集与之对应。而这些 FIRST 集彼此不相交。

这个特征很有用,因为这个特征很容易得出以下结论。

对于某个非终结符的所有产生式而言,任取一个终结符,该终结符……

  • 要么不属于任何一个 FIRST 集;

  • 要么仅属于某一个FIRST集,从而找到唯一的一个产生式与之对应。

基于这个结论,Parser 对某个非终结符展开形式的判定就变得明了起来。将从 Tokenizer 处读取到的 Token(即非终结符)递归的与非终结符产生式的 FIRST集做比较,一旦找到一个 FIRST 包含该 Token,即挑选该 FIRST 集对应的产生式。

整个过程可一气呵成,不需要进行任何回溯。

但这么做之前,我们必须知道每一个非终结符的所有产生式的 FIRST 集。嗯,这是必要的,赶紧记在小本子上吧,在将来的章节中我们必须要写求 FIRST 集的程序。

好,假设我们已经求出所有非终结符产生式的 FIRST 集了,是不是就可以开始写 Parser 了呢?非也,之前的结论是建立在“不考虑 ε”的前提下。

所以,让我们来讨论允许 ε 的情况。

如果产生式中可能出现 ε,那么每一个产生式中的非终结符都有可能导出 ε 的嫌疑。但 LL(1) 严格的要求一个非终结符最多只能有一个产生式可以导出 ε。这意味着我们必须明确知道每一个非终结符能不能导出 ε。好在这并非难事,让我们观察,对于。

A → α | β | ε

而言,不用说 A 肯定能导出 ε,我都抓到现行了你还说没有?!不解释,它就可以导出 ε。

对于,

B → abide

可以肯定,不能导出 ε,因为产生式右边全是终结符,终结符是不可能再展开的,因此我眼睛没看到 ε,它就导不出 ε。

但是,这种情况就比较暧昧了,

C → αβγ

因为 α、β、γ 三个是式子,能不能导出 ε 真说不准。不过可以肯定的是,只要有一个式子不能导出 ε,那么 C 一定无法导出 ε。因为那个导不出 ε 的式子永远不会“消失掉”,它霸占的位置最终会变成一组终结符串,故 C 绝不可能为空。反过来,只有当所有的式子都能导出 ε 的时候,C 才能导出 ε。

于是,判断式子是否可以导出 ε 的条件呼之欲出。

  • 终结符一定不能导出 ε。

  • 如果存在产生式 A → ε,则非终结符 A 能导出 ε。

  • 如果 A 的一个产生式 A → αβγ... 右侧所有符号都可以导出 ε,则 A 可以导出 ε。

当某个非终结符可以导出 ε 时,Parser 在发现一个终结符的时候,在与其所有产生式的 FIRST 集比较过一次无果后,还可以与 FOLLOW 集比较。如果FOLLOW 集包含这个终结符,则表明该非终结符需要导出 ε。

至此,看来我们不但要事先求出每个非终结符的所有产生式的 FIRST 集,还要判断每一个非终结符是否能导出 ε。这样,我又要在笔记本上多记一条了。

嗯,到这里我已经连续讲了3章理论了,虽然我原本打算尽量少讲理论的,但是现在发现这些东西似乎避免不了。因为之后我要写的东西全部来自这里头。不过,下一章我还会继续讲理论,然后开始写 Parser。

女装
文章评论