2.6 生成空语言的语法

在印度当0被作为数字被数学家引入后的大约1500年后,这一概念依旧没有被计算机科学好好接受。许多编程语言不支持0字段的记录,0元素的数组,或0变量的变量定义;在一些编程语言中,调用0个参数协程的语法不同于调用一个或多个参数的协程的语法;许多编译器也无法编译定义0个名称的模块;这些例子还可以很轻松的扩展下去。更具体的说,我们不知道有什么解析器生成器可以生成一个空语言的解析器,这个空语言有0个字符串。

所有这一切都将我们引向一个问题,空语言的语法会是什么样的?首先注意,空语言不同于只包含空字符串的语言,空字符串只是包含0个字符。这种语言很容易由Ss--->ε生成,并且被普通lex-yacc流正确处理。注意,这个语法没有终结符,这意味着2.2节的VT是空集。

对一个语法来说不生成任何东西,那生成过程将不被允许终止。这就有了一个办法来获得这一一种语法:Ss--->S。然而这很令人不齿,有两个原因。从算法角度来说,生成过程只是在循环,而没有获得任何关于语言的空属性的信息;而且符号S的使用是任意的。

另一个方法就是迫使生成过程被卡住,通过让语法中没有任何生成规则。那么2.2节的R就也会是空的了,然后语法的形式就是({S}, {}, S, {})。这还不是很理想,因为我们由一个没有定义规则的非终结符;并且符号S还是任意的。

更好的方式是永远不要让生成过程开始:没有起始符号。这是可行的,通过在语法定义中允许出现一组起始符号而不是一个单一的起始符号。这么做还有其他很好的理由。举个例子,一个大型编程语言的语法,该语言的模块规格、模块定义等有着多重“根”。虽然在顶层这些是不同的,但它们在共同语法上有着大量的段(segment)。如果我们将一个CF语法定义扩展来使用一组起始符号,空语言的语法将获得优雅和令人满意的形式({}, {}, {}, {})。

关于0和空:考虑一下左侧是空的语法规则,可能是有帮助的。这种规则的右侧的最终生成物可能出现在输入的任何地方,因此模拟噪声和其他每天但外部的事件。

我们全神贯注于空字符串、空集、空语言等不是轻浮的,因为这是众所周知的,系统处理空实例的轻松是其洁净度和稳健性的一个衡量。

results matching ""

    No results matching ""