始和结束符号的标记符（比如和），就像括号匹配一样，是我们已知的非正则的。

5.3.4 XML和文档类型定义

能用文法来描述HTML倒不算什么，事实上所有的编程语言都可以用和它们相应的CFG来描述，因此如果不能描述HTML的话反倒令人惊讶了。然而，当我们考虑另外一类重要的标记语言XML（eXtensible Markup Language 可扩展标记语言）时，将会发现在使用这个语言的过程中，CFG扮演着至关重要的角色。

XML的目的不是描述文档的格式——那是HTML的工作，而是试着描述文本的“语义”。比如，像“枫树大街12号”这样的文本看上去像一个地址，但是它是吗？在XML中，代表一个地址的短语往往用标记符围起来，例如：

枫树大街12号

然而，对于是否意味着一幢建筑这件事情并不是很清楚。例如，如果这个文档是关于内存分配的，那么标记符可能会表示一个内存地址。为了把这些不同类型的标记符区别开来，人们希望开发一个标准，该标准采用DTD（Document-Type Definition 文档类型定义）的形式。

一个DTD本质上就是一个上下文无关文法，不过有着它自己的用来描述变元和产生式的表示法。下面的例子将会展示一个简单的DTD，并且会介绍用来描述DTD的语言的一部分。DTD语言本身有一个上下文无关的文法，但它并不是我们感兴趣和要描述的。然而，用来描述DTD的语言本质上是用一个CFG表示的，我们想知道在这个语言中CFG是怎样表达出来的。

一个DTD的定义是这样的

其中element是依次定义的，一个element定义是这样的

element的描述实质上是正则表达式。这些正则表达式的组成部分有：

1. 其它element的名字，表示一个类型的element可以出现在另一个类型的element里面，就像在HTML中一个文本列表里可以有强调的文本一样。 2. 特殊的术语 \\#PCDATA，代表任何不包含XML标记符的文本。这个术语和例5.22中变元Text的角色相同。 允许的操作符有：

1. | 代表合并，就像第3.3.1节中所介绍的UNIX的正则表达式的表示法中的那样。

element定义的列表

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形式的新的产生式了。