《0上下文无关语言》-课件.ppt

上下文无关文法的应用 用上下文无关文法描述语言 XML和文档类型定义 * * 用上下文无关文法描述语言 一般的程序设计语言都使用括号（圆括号，方括号，花括号等），并且都是嵌套地、匹配地使用。所谓匹配就是一个左括号必须有一个右括号和它对应，所谓嵌套就是括号可以多层出现（一对括号外面还有一对括号，依此类推）。不考虑其它符号，圆括号匹配和嵌套的正常情况如(()),()(),(()())等等，不匹配的情况如(()，())，)，()())等等。 可以用一个上下文无关文法G=({B},{( ,)},P,B)，产生所有匹配的圆括号串(包括空串，即没有括号的情况)。其中P包含以下的产生式： B→BB∣(B)∣ε * 用上下文无关文法描述语言 除了括号之外，程序设计语言中还包含许多其它的结构。 例如下面给出的文法G1： E→I∣E+E∣E*E∣(E) I→a∣b I→Ia∣Ib∣I0∣I1 它定义了很简单算术表达式E, 但L(G1)也不是正则语言。 * 用上下文无关文法描述语言 常用的程序设计语言中有许多结构和圆括号很相似。例如，一个代码块的开始和结束，就像 Pascal 语言中的 begin 和end，C 语言中的花括号“{”和“}”，它们在整个程序中也必须是匹配的。 在程序设计语言中，有时还会出现另外一种结构，这种结构和括号结构略有不同，匹配时可以不考虑“左括号”。 例如，在C语言中的 if 和 else 就是这样，一个 if 子句可以不和 else 子句匹配而单独存在，也可以和一个 else子句匹配。一个能产生所有可能的 if 和 else 序列的文法 G2 如下： S→ε∣SS∣ifS∣ifSelseS 其中if和else都做为终结符看待。例如，ifelseifelse，ififelse，ifelseifelse和ifif等都是由文法G2产生的序列，而elseif，ifelseelse等就不能由文法G2产生。 * XML和文档类型定义 XML的目的不是描述文档的格式，而是试着描述文本的“语义”。 例如，像“12 Maple St.”这样的文本看上去像一个地址。 在XML中，代表一个地址的短语要用标记符ADDR围起来，例如: ADDR 12 Maple St./ADDR 用ADDR标记是否意味着是一座建筑物的地址，那可不一定。 例如，如果这个文档是关于内存分配的，那么ADDR标记的可能是一个内存地址。 为了把这些不同类型的标记符区别开来，人们希望开发一个标准，该标准采用DTD的形式。 一个DTD(Document Type Defination的缩写)本质上就是一个上下文无关文法，不过它有着自己的用来描述变元和产生式的记号。 下面的例子将展示一个简单的DTD，并且介绍DTD语言的一些描述方法。用来描述DTD的语言本质上就是一种CFG记法。 * XML和文档类型定义 一个 DTD 的形式如下： !DOCTYPE DTD的名字[ 元素定义的列表 ] 其中，元素定义的形式是： !ELEMENT 元素的名字(元素的描述) 元素的描述实质上是正则表达式，这些正则表达式的基础是： 其他元素的名字， 特殊的术语 #PCDATA，代表任何不包含 XML 标记符的文本。 * XML和文档类型定义 允许的运算符有： “∣”代表并。 逗号“，”代表连接。 闭包运算有三种。 * —— 表示运算对象零次或多次出现 + —— 表示运算对象一次或多次出现 ? —— 表示运算对象零次或一次出现 可以用圆括号把运算符和它们的运算对象括起来，以示优先，否则就采用通常正则表达式构造的优先级。 * XML和文档类型定义 考虑以下的情况：假设计算机销售商们协商建立一套 DTD 的标准，这套标准是用来在 Web上发布他们正在销售的各种 PC的介绍。每种 PC的介绍中包含一个型号，以及这个型号的特性的细节描述。 例如，RAM的大小、磁盘的数目和大小等等。 右图展示出一个假想的、非常简单的刻画个人计算机的DTD。 * XML和文档类型定义 * XML和文档类型定义 图中写出的 DTD 中元素的规则看上去和 CFG 不是很像。其中有些和CFG 的产生式相似，例如： !ELEMENT PROCESSOR ( MANF,MODEL,SPEED) 和下面这条产生式 PROCESSOR →MANF MODEL SPEED 已经很像。 DTD 中的规则 !ELEMENT DISK ( HARDDISK∣CD∣DVD) 也容易转换成产生式组的缩写法： DISK →HARDDISK∣CD∣DVD * XML和文档类型定义 然而，DTD中比较难转换的一种规则是： !ELEMENT PC ( MODEL,PRICE,PROCESSOR