当前课程知识点：软件理论基础 > 第七章 上下文无关文法和推导 > 7.1 上下文无关文法 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
我是清华大学的教师 罗贵明
今天我们介绍第七章内容
上下文无关文法和推导
我们内容包括上下文无关文法
规约和推导
语法分析树
规约 推导 语法分析树
它们之间的关系
最后介绍上下文无关语言
首先 我们介绍上下文无关文法
文法我们在之前已经介绍过
特别是我们讲正则文法的时候
我们讲了文法它是一个四元组
我们讲什么是上下无关文法
上下无关文法实际上也是一个四元组
这个四元组包括有变量V
还有终结符T
这当然这是集合
在一个开始变量S
最重要就是产生式P
这里面V变量的集合和终结符这个集合
它们是不交的
变量用大写的字母ABCD来表示
终结符用小写的
你像a啊 小写的b 小写c等等表示终结符
S开始变量是变量当中的一个变量
这个产生式 上下无关文法的产生式
它是A产生α
左边这个A只是一个变量
右边它是由变量和终结符构成的E的有限串
这就是我们的上下无关文法的特点
下面我们看一个例子
这里是一个上下文法
首先终结符
在这里面终结符有哪些呢
有像这个左括号 右括号vd+x
这些都是终结符
再看非终结符已知变量
在这个文法里面
变量有这个E
你看这里面EEEOOEEE等等
这些都是变量
实际上也就是E和O两个变量
开始变量或者开始符号
在这个文法里面开始符号
就是第一个产生式最左边的一个变量 就是E
就是我们的开始变量
那最重要的就是产生式
产生式它是一个集合
产生式它的构造实际上
它是有head和boby这个形式
左边表示叫head
实际上是一个变量
右边boby实际上就是一个串
在这里这个产生式就是有这个文法的
所有的这个产生式构成
对刚才的构成的文法
变量集合
终结符的集合
开始变量P
这就是我们刚才这样给的算术文法
它的四元组
我们一般的不会用这个箭头
来表示这个文法的形式
用什么东西
用这样的形式来表示它的定义
另外我们原来在文法里也讲了
像这类文法还可以用一个简化的形式
左边它的变量都相同的话
我们可以用这种形式
表示这样若干个产生式
用这样的表示下面这样的产生式
我们原来介绍过这类文法
这个文法有两个产生式
它的变量就是S
终结符有a有b
那对这个文法我们采用之前的那个推导
实际上我们就可以推导出一些终结符的串
这个终结符的串
实际上就构成了这个文法的语言
那这个文法它的语言是什么呢
实际上就是a的n次方 b的n次方
我们在正则语言里面
就证明过这个语言不是正则语言
但是用最简单的文法
实际上就可以构造出来
刚才我们给出了上下文无关文法的定义
以及上下文无关文法的表示
从这个例子看
上下文无关文法还可以表示成句子
还有它推导的形式
那至于怎么推导
这就是我们下一节要介绍的内容
好 这节内容介绍完毕
谢谢大家
-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
-习题--作业
-期中考试
