当前课程知识点：软件理论基础 > 第八章 CFG的应用与文法的二义性 > 8.1 CFG的应用 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
我是清华大学的教师罗贵明
今天我们介绍内容是
上下无关文法的应用与文法的二义性
这个内容包括有上下无关文法
也就是CFG的应用 CFG的转换
文法的二义性 二义性的消除方法
CFG的构造方法
最后我们介绍CFG的构造实例
首先我们介绍上下无关文法的应用
在上一讲里面我们介绍了上下无关文法
以及上下无关文法的推导
和上下无关文法的语言
上下无关文法在我们实际的
软件和编程当中有哪些应用呢
这一讲里面我们介绍第一个应用就是
程序设计语言它的语法的描述和分析
接着我们介绍文档格式的描述和处理
在我们通常给的程序
到最后我们看到的效果
整个的过程是这样的
编程是给的是源程序
能看到的是目标程序
而这中间这个过程
是用编译和解释这个来完成的
那整个的这个文法实际上
就是在中间这个步骤
这个步骤要用到的
是词法分析器和语法解析器
也就是从源程序经过这个词法分析器
得到单词 再到语法的解析之后
再到目标程序
这个词法的分析器
我们通常用到的是词法的这个生成器
生成这个词法得到单词
而这个文法的解析器
通常是把这个单词经过合理的文法
最后得到句子结构
那在这个词法分析器里面用到的是Lex
这是一个词法的生成器
文法里面 解析器里面 我们用的Yacc
通过Yacc 文法最后得到语法的结构
这个Yacc 它的构造过程
首先它有声明节
声明节这里面通常用一个这个%号
后面再加上它的token
来描述你这里面的一些相关的代码的说明
接下来是一个语法规则节
语法规则节就是
定义你这里面的语法规则以及语义的动作
这个Yacc里面它的产生式
实际上这次变量也是非终结符
这个箭头它这里面
我们是用一个冒号表示的
后面是一个字符串
这个括号里面是对一些动作做些说明
之后我们可能要用到一些函数的调用
以及支撑函数节
下面我们看一个具体的一个文法事例
这是我们上一讲里面介绍过的
一个算术文法
我们通过刚才介绍的文法的
三个构成部分
前面这一块这是变量和数据
这里使用的声明节
介绍这里面我们用到的
这里面有终结符 有变量和数据
也就是v和d
那接下来这一部分就是我们的语法部分
这些就是语法规则节
那这里面我们第一个E也是Exp
它产生EOE
这里面它是用这个表示的
而这个就是动作说明
第二个产生式 就是E产生了
这个左括号
在这里是终结符
终结符我们用单引号把它标注出来
再这是Exp 后面这是个右括号 也是终结符
我们也用单引号表示
后面是动作
E产生是变量variable
那变量
在这里就说明它是一个终结符
所以它用单引号标注
E产生d也是δ
δ它也是终结符
我们也用单引号把它标记
这是E的它的产生部分
接下来是O operation
O产生它有这里+
+是终结符 也用单引号标注
O产生乘
乘也是终结符 用单引号标注
这里同样有些动作
这就是它的语法部分
接下来 这里面我们没有函数调用
一些支撑函数节
所以这里你如果要用的话
我们在这一部分再描述
另外介绍标记语言
在我们实际的这种程序编程当中
大面积用的标记语言
首先在超文本这个语言里面
超文本标记语言
这是我们经常在网页里面可以看到的
我们看这么一个例子
这是一个标记 后面这是文字
这是文字 这里做标记
在接下来这里做标记
标记这是个列表部分
这是第一个列表
这是第二个列表
这一个标记它给出的这是我们的源程序
经过它这个标记生成的目标程序
我们看实际上是得到了是这样一个效果
这就是我们通过标记文法
得到的标记语言
另外的SGML这是一类标记语言
这个标记语言 国际的标准是ISO8879
其中里面一个非常重要的 用的很多的是XML
也就是扩展的标记语言
在扩展标记语言里面 用的很多的就是DTD
也就是我们的文档类型定义语言
程序文档用的非常多
下面看这个DTD格式
DTD格式实际上它有这个DTD它的名字
这个名字里面它有一些说明
就是说我们的元素的定义
这里元素定义的列表
而这个元素element
它包含了元素的名字和这个元素的描述
关于这个元素的表述实际上
它可以看作是一个正则表示
而这里面这些基本表示
可以是一些元素的名字
还有一些特殊的表示
你比如我们后面要用到的
表示一些数据的一些说明
还有一些表示是类似于用UNIX
它的正则表示
这是我们DTD的基本的描述
在下一节里面
我们要给出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
-习题--作业
-期中考试
