上下文无关文法与语言(6)

2. 逗号代表连接

3. 闭包运算有三种，就是第3.3.1节中所介绍的。它们有：*，最常用的运算符表示“零次或多次出现”；+，表示“一次或多次出现”；?，表示“零次或一次出现”。

并且用括号把运算符和它们的参数组合起来，否则如果没有括号的话，就采用通常的正则表达式的优先级。

例5.23：考虑下面的情况：假设计算机销售商们凑到一起想要建立一套DTD的标准，这套标准是用来在Web上发布他们正在销售的各种PC的介绍。每种PC的介绍将会给出一个型号，以及这个型号的特性的细节描述。例如RAM的大小，DISK的数目和大小等等。图5.14展示了一个假想的、非常简单的刻画个人计算机的DTD。

]>

图5.14：一个刻画个人计算机的DTD

这个DTD的名字是PcSpecs。第一个element（就像CFG的开始符号）是PCS（关于PC规格的列表）。它的定义部分是PC*，是说一个PCS包含零个或多个条目，每个条目都是PC。

接下来的是element PC的定义，它由五部分连接而成。其中前四部分是其它的

element，分别对应着型号、价格、处理器类型和PC的RAM。由于逗号表示连接，因此这几部分必须刚好出现一次，并且还得按照顺序出现。最后一个组成部分是DISK+，表示一个PC中可以有一个或多个DISK。

很多组成部分都是简单的文本：型号，价格和RAM都是这样的。但是处理器是有结构的，从它的定义可以看出来它由生产厂家、型号和速度这三部分按顺序构成，这三部分都是简单的文本。

DISK的结构最为复杂。首先，一个DISK可以是一个硬盘、CD或者DVD，这从

element DISK的定义可以看出来，DISK定义为这三者的“或”。其次，硬盘也由三个部分按顺序构成，它们分别是生产厂家，型号和大小；而CD和DVD仅仅由它们的速度来代表。

图5.15是一个使用图5.14中的DTD的XML文档的例子。注意到在这个文档中，每个element都用两个标记符来表示，其中一个以它为名字，另一个在结束处和它对应。其中表示结束的标记符不过是在该element的名字前面加了一个斜杠而已，这和HTML中是一样的。从而，在图5.15中可以看到最外层的标记符是…。这个标记符里面是一系列的条目，每一个都是该生产商所销售的PC，这里仅展示出来其中的一个条目。

<型号>4560 <价格>$2295 <处理器>

<生产厂家>Intel <型号>Pentium <速度>800MHz

256 <硬盘>

<生产厂家>Maxtor <型号>Diamond <大小>30.5Gb

<速度>32x

…

图5.15：一个遵照图5.14中DTD结构的文档的一部分

通过例中的条目，我们可以很容易的看到机器的型号是4560，价格是$2295，处理器是800MHz Intel Pentium 处理器。它有256Mb的RAM，一个30.5Gb的Maxtor

Diamond硬盘和一个32x的CD-ROM驱动器。其实最重要的并不是我们能看到这些东西，而是程序能够读取这个文档，并且能够根据图5.14中的DTD的文法来正确的解释图5.15中所有的数字和名字。□

你可能已经注意到了，图5.14中这样的DTD中定义element的规则看上去和上下文无关文法的产生式并不是很像。这些规则中的一大部分已经是正确的形式了，例如

和下面这个产生式很类似

处理器 ? 生产厂家 型号 速度

然而，下面这条规则

其中定义DISK的部分并不像一个产生式的体。既然这样，推广的方法很简单：只要把这条规则解释成为三个产生式，它们拥有同样的头，而它们的体用竖杠连接起来，这里竖杠的作用和规则中的相同。因此，这条规则和下面的三个产生式等价

DISK ? 硬盘 | CD | DVD

最难转换的一种情况是

其中“体”里有一个闭包运算。解决的方法是把DISK+用一个新的变元Disks来代替，并且通过一对产生式来表示变元Disk的一个或多个实例。等价的产生式是

PC ? 型号 价格 处理器 RAM Disks Disks ? Disk | Disk Disks

有一个通用的方法能够把产生式体中包含正则表达式的CFG转换成普通的CFG。这里先非形式化的给出它的思想：你也许希望不仅仅把产生式体中包含正则表达式的CFG变成正规的CFG，并且能够证明经过这样的扩展变换之后并没有产生超出这个CFL之外的新的语言。下面将会归纳地给出把体中包含正则表达式的产生式变成一系列和它等价的普通的产生式。这个归纳是对产生式体中的正则表达式的大小来进行的。

基础：如果产生式的体是几个element的连接，那么这个产生式已经是合法的CFG的产生式的形式了，因此什么都不用做了。

归纳：否则，将根据最后使用的运算符来采取下面五种情况下的方案之一。

1. 该产生式是A?E1, E2的形式，其中E1和E2都是DTD语言中允许的表达式，这是

一个连接的情况。引进两个新的变元B和C，并且它们不能在该文法的其它地方出现。把A?E1, E2替换为下面的一组产生式：

A ? BC B ? E1 C ? E2

其中第一个产生式A?BC是合法的CFG的产生式，后面两个有可能并不是合法的（当然也可能是合法的）。然而它们的体要短于原来的产生式的体，因此只要继续应用归纳的过程来把它们转换为CFG的形式就行了。

2. 该产生式是A?E1 | E2的形式。对于并运算，把这个产生式用下面的一对产生式来

代替：

A ? E1 A ? E2

同样，这些产生式也可能是或者不是合法的CFG产生式，但是它们的体一定比原来的产生式的体要短。因此只要递归的应用转换规则就可以把它们编为符合CFG形式的新的产生式了。

3. 该产生式是A?(E1)*的形式。这时要引入一个新的变元B（同样，B不能在别处出

现）然后把这个产生式变为：

A ? BA A ? ε B ? E1

4. 该产生式是A?(E1)+的形式。这时要引入一个新的变元B（同样，B不能在别处出

现）然后把这个产生式变为：

A ? BA A ? B B ? E1

5. 该产生式是A?(E1)?的形式。把这个产生式变为：

A ? ε A ? E1

例5.24：下面来考虑 怎样把这条DTD的规则

转换为合法的CFG产生式。首先，这条规则的体可以看作两个表达式的连接，第一个是型号，价格，处理器，RAM，第二个是DISK+。因此引入两个变元A和B来分别代表这两个子表达式，就可以得到下面的产生式：

PC ? AB

A ? 型号 价格 处理器 RAM B ? DI …… 此处隐藏：2201字，全部文档内容请下载后查看。喜欢就下载吧 ……