从零开始写个编译器吧 - 数量词符号

360 查看

式子中的符号,我还允许使用数量词来修饰。
考虑一个非终结符 A,如果对于另一个符号 α,存在如下产生式。

α → αA | ε

则对于 α 而言,它可以表示非终结符 A 重复 0 、1、多次的各种形式。

现在稍稍改变这个式子,使之变成:

α → αA | A

这时,α 不再可能产生空,此时它只能表示非终结符 A 重复 1次或多次。
当然还有这个式子。

α → A | ε

这个α 表示 A 出现 0 次 或 1 次。

以上三个式子展现了将任意非终结符 A 关于重复次数的多种形式。这些形式很有用,至少对于我写 Parser 很有用。因此,可以使用数量词符号来描述。

  • A* (重复 0、1 次或多次)

  • A+ (重复 1 次或多次)

  • A? (出现 0 次或 1 次)

至此,我们已经得到了写一个 Parser 所需的所有理论工具了。但是,等等,其实我们还可以深入的探讨一下某些特别的东西。

我在上一章提及,对于每一个非终结符而言,它是否能导出 ε 是必须被判断清楚的。特别的,当然某个非终结符 A 可以导出 ε 时,我可以发现有如下等式。

A = A?
A+ = A*

严格意义上说,等号左右的式子还有是有区别的,他们虽然展开的最终结果完全相同,但展开的形式却有所差别。但对于我而言,我只关心结果,我将它们视作相等一点都不影响我的 Parser 正常运行。

这两个等式令我写程序更加方便,试想我该在程序中如何表现 ε ?我只需写一个 A? 就行了,因为 A? 一定可以导出 ε。