当前课程知识点：软件理论基础 > 第八章 CFG的应用与文法的二义性 > 8.2 CFG的转化 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在介绍上下无关文法应用
与文法的二义性的第二部分
也就是上下无关文法的转换
在上节里面我们介绍了
上下无关文法它的应用
特别是介绍了叫标记语言
标记语言里面我们介绍了一个DTD的格式
像DTD里面它的格式
就分一个是它的DTD的名字
和它里面的元素的列表
在元素里面
也包括元素的名字和元素的它的描述
下面我们介绍一个实际的一个例子
这是一个计算机的一个D端
这里是DTD的它的名字是（01：18）
就是PC的说明
它是从这里到下面这一部分
这就是它的元素Element的列表
第一个Element这里面名字它是PCS
表示的是有多个PC
说明的是PC*这是一个正则表示了
这里表示有多个PC
那下面只选一个PC
这个PC PC里面也包含有Model
就是型号 价格 处理器 内存和盘
这个盘这一块 也是一个正则表示
下面我们说的 我们对这里面的说明
实际上每一个
只要是前面没有出现过的
我们下面的Element里面
都要做一些解释了
像型号Element 这个Model
它这里面就给了一些数据
这个数据就相当于是终结符了
再接着是价格
价格这给出了这也是一个数据
再解释处理器
处理器这里Element里面
我们就给出了
它就包含有Manufacturer制造商 型号 速度
这三个部分
制造商 前面没出现过
所以我们下面Element
在制造商里面要做一个说明
这个说明也是给了一些数据了
再是型号
型号实际上我们说了
前面它已经给出一定的解释了
它可以用速度描述
速度前面出现过
那接下来Element
速度 速度实际上它也是用数据来描述的
这里是处理器已经接受完毕
下面就是内存RAM
RAM它也是用一个数据来描述的
再接着是这个Disk 盘
这个盘里面
我们有硬盘 CD盘 DVD盘
这里有三种盘 前面都没出现过
我们要逐个进行定义了
首先是Element硬盘
硬盘它包括有制造商 型号 大小
制造商在前面已经说过
型号前面也提过
只是这个Size前面没有介绍过
就是大小也有一个说明
这是一个终结符数据
再接下来CD
CD它涉及的是速度
速度在前面也出现过
我们也是用一个终结符串描述的
再还有DVD
DVD它也是用速度来描述的
这个就是一个计算机
它的定单的一个DTD格式
下面我们看真实的一个计算机定单
它编程的是这样一个表示
这个表示跟我们刚才介绍的
这个DTD的格式
好像它们之间有一些区别
但这个区别大家可以看
实际上它们是对应的
它这个直接给的名字
从这里到这里
这个标记给出了
是这样的一个过程
而接下来Element
Element这里面呢
我们这里给出的是PC
PC里面包含了有型号 价格 处理器
再内存 还有这个盘
这里对应的是这一串
而这一串里面它的标记
是用这个不同的下面的说明来表示的
这就是我们的有XML来表示的DTD文件
我们刚才介绍了标记语言 实际上有两类
一个是超文本的 一个是XML
从这两类文件
大家看它们都是标记语言
但是它们之间有差异
这个差异在于前面讲的超文本
它的标记跟我们的数据库
是没有多大关系的
这个XML这个标记
是跟数据库查找形式是有关系的
所以它们之间既有联系也有区别
我们再看怎么去
跟我们的上下无关文法有联系呢
超文本里面的给的一个语言程序
它是一个标记语言
这个标记语言 它可以转化为
上下无关文法
这个转换 你像这里面的字母
它有小写的有大写的
文本 有这里面空串 再字母 还有文本
就是跟你这个标记是对应的
还有文件是有空串
Element这里是文件
Element元素
它包括文本 这里它这是标记串
还有这里面 这个标记的 这里列表等等
这个是用到我们超文本里面的
它的标记语言
实际上它们转化为
上下无关文法是这种表示
那我们再看DTD
DTD实际上也是一个上下无关文法
把它的表示形式可以转化为
我们上下无关文法的它的产生式
这给了这一种是DTD的格式
这是处理器
处理器它包含有制造商 型号 速度
Processor这个处理器
这看作一个变量
制造商Manufacturer 这里看作一个变量
Model看作一个变量
Speed 这个速度也看作一个变量
实际上这里有这一个变量
产生出这三个非终结符的一个串
下面我们再看看这个Element这个盘
包含有硬盘 CD盘 DVD盘
Disk这个看作是一个变量
我们转化成文法
那它是产生了是硬盘
这个Disk还可以产生CD
Disk还可以产生DVD
得到的三个产生式
这种表示 这个ElementPC里面
它说明有型号 价格 处理器 内存
这个Disk它有个+
前面这一块的表示
跟我们这里是类似的
现在这里有一个Disk+
实际上这个是一个正则表示
它是表示一个和多个
把这里看作一个变量PC
接下来是型号 价格 处理器 内存
这一个变量修改了一下
这里用Disks
它就表示一个新的变量
而Disks它又可以产生一个或多个Disk
用这种形式就描述出
这个Element 它这个表示
实际上我们这样就可以把
任何一个DTD
转化为一个上下无关文法
好 这节内容介绍完毕
谢谢大家
-1.1 概要
--第一节
-1.2 数学基础
--Video
-1.3 图
--Video
-1.4 证明方法
--Video
-1.5 语言基础
--Video
-1.6 语言运算
--Video
-习题--作业
-2.1 确定有限自动机的概念
--Video
-2.2 确定有限自动机的定义
--Video
-2.3 扩展转移函数
--Video
-2.4 正则语言
--Video
-2.5 DFA构造
--Video
-习题--作业
-3.1 非确定有限自动机的概念
--Video
-3.2 e转移
--Video
-3.3 非确定有限自动机的定义
--Video
-3.4 扩展转移函数
--Video
-3.5 等价性证明
--Video
-3.6 文本搜索
--Video
-习题--作业
-4.1 单一终结状态的NFA
--Video
-4.2 正则语言的运算性质
--Video
-4.3 正则表示和语言
--Video
-4.4 正则表示和正则语言
--Video
-4.5 正则语言的同态
--Video
-4.6 正则表示的代数定律
--Video
-习题--作业
-5.1 文法
--Video
-5.2 线性文法
--Video
-5.3 正则文法与正则语言
--Video
-5.4 自动机的积
--Video
-习题--作业
-6.1 基本问题
--Video
-6.2 泵引理
--Video
-6.3 非正则语言的判定 1
--Video
-6.4 非正则语言的判定 2
--Video
-6.5 DFA的优化 1
--Video
-6.6 DFA的优化 2
--Video
-习题--作业
-7.1 上下文无关文法
--Video
-7.2 规约和推导
--Video
-7.3 语法分析树
--Video
-7.4 规约、推导和语法分析树之间的关系
--Video
-7.5 上下文无关语言
--Video
-习题--作业
-8.1 CFG的应用
--Video
-8.2 CFG的转化
--Video
-8.3 文法二义性
--Video
-8.4 二义性的消除方法
--Video
-8.5 CFG的构造方法
--Video
-8.6 CFG的构造实例
--Video
-第八章 CFG的应用与文法的二义性--习题
-9.1 PDA介绍
--Video
-9.2 PDA的定义
--Video
-9.3 PDA的即时描述
--Video
-9.4 PDA的语言
--Video
-9.5 PDA与CFG的关系
--Video
-习题--作业
-10.1 确定下推自动机
--Video
-10.2 DPDA与其他语言的关系
--Video
-10.3 终态型DPDA和空栈型DPDA
--Video
-10.4 消除无用符号
--Video
-10.5 消除e产生式
--Video
-10.6 消除单一产生式
--Video
-10.7 CFG的化简与Chomsky范式
--Video
-习题--作业
-11.1 CFL的必要条件
--Video
-11.2 CFL的Pumping引理
--Video
-11.3 CFL的闭运算性质
--Video
-11.4 CFL的同态性质
--Video
-11.5 CFL的交运算
--Video
-11.6 CFL的判定性质
--Video
-习题--作业
-12.1 图灵机的介绍
--Video
-12.2 图灵机的定义
--Video
-12.3 图灵机的即时描述
--Video
-12.4 图灵机的计算
--Video
-12.5 图灵机的编程技术
--Video
-习题--作业
-13.1 Turing理论
--Video
-13.2 图灵机带的扩展
--Video
-13.3 图灵机移动的扩展
--Video
-13.4 受限图灵机
--Video
-13.5 图灵机与其他自动机
--Video
-习题--作业
-14.1 图灵机编码
--Video
-14.2 对角线语言与通用语言
--Video
-14.3 图灵机语言的性质
--Video
-14.4 判定问题和语言
--Video
-14.5 计算复杂性问题
--Video
-第十四章 不可判定问题--习题
-15.1 时间自动机
--Video
-15.2 Buchi自动机
--Video
-15.3 软件形式化验证
--Video
-15.4 模型检测方法
--Video
-15.5 M3C模型检测系统
--Video
-习题--作业
-期中考试
