当前课程知识点：软件理论基础 > 第七章 上下文无关文法和推导 > 7.3 语法分析树 > Video
欢迎同学们来到《软件理论基础》的MOOC课堂
现在介绍上下文无关文法的第三节内容
也就是语法分析树
在上一节里面
我们介绍了上下文无关文法它的推导
从上下文无关文法它的推导
它的句型有两种方法
要么是规约 要么是推导
规约一个过程
我们说它是自下而上的
它可以构造一棵树
我们还是按我们之前的一个上下文法
看这么一个句子
（v+d）×d
它的规约过程
首先我们用到了第六个产生式
就是×规约到O
得到的是这样一个分支×规约到O
然后用第五个产生式+规约到O
得到的是+规约到O
第四个产生式 d规约到E
得到d规约到E
用的第四个产生式也是d规约到E
那得到的是d规约到E
用第三个产生式V规约到E
V规约到E
再用第一个产生式是EOE规约到E
这里有EOE规约到E
再用第二个产生式 这个（E）规约到E
那这是个E
这两个加括号规约到E
最后利用第一个产生式
这个EOE规约到E
就从（v+d）×d这么一个串
最后规约到这个文法的开始变量
那得到了从下面这一个串
我们最后规约到这个E这个过程
你看生成了一棵树了
这棵树的归结点就是E
就是规约过程 它可以构造一棵树
那同样推导
推导过程它是自上而下的
它也可以构造一棵树
我们还是对这个上下文法
还是对这个串
从开始变量开始
E第一次用的是第一个产生式E
产生EOE
那得到的是E产生EOE
再用第二个产生式E产生（E）
再E产生（E）
再用第一个产生式E产生EOE
这个E要产生EOE
再用第三个产生式E产生v
E产生v
再用第四个产生式E产生d
E产生d
还用第四个产生式E产生d
再用第五个产生式O产生+
这是O产生+
再用第六个产生式O产生×
这是O产生×
这样就得到了这个字符串（v+d）×d
这是从开始变量自上而下也得到一棵树
这个树就把它命一个名字
叫做语法分析树
那语法分析树它是这样定义的
这个树的内部结点都是变量
终结符不能做内部结点的
内部结点都是非终结符
而叶结点它可以是变量
也可以是终结符
还可以是空串ε
只不过它为ε的时候
它是父结点的唯一的一个子结点
在第三个特征时
假如有一个内部结点是A
它的子结点从左到右标记的是X1、X2、XK
那在这个文法当中
一定有这么一个产生式A产生X1、X2、XK
这两个是一一对应的
在这里面我们再强调一下叶结点
如果是空串的话
那它是它的父结点唯一的一个子结点
我们给了这样一个上下文无关文法
这个文法我们现在由这个推导
S推导AB
也是用第一个产生式
那我们可以得到这样的一个S对应的AB
我们再用这个产生式A产生abA
我们得到这个串
也就是这个A它可以产生出abA
再利用这个a产生空串
这是a产生空串
这个时候空串是它唯一的一个子结点
B B可以产生Ba
所以这个产生式就有一个Ba
那B还可以产生B
那这样得到B产生b
这样从这个文法
它就可以生成一个语法分析树
在语法分析树里面得到了从左到右
就给出了一个串
这个串叫做语法分析树的产物
产物这个串里面可以有变量
可以有终结符
如果这个树里面的产物
都是终结符的时候
那实际上就是一个句子
文法它就可以由这些句子构成它的语言
下面我们看刚才给了这个文法
得到了语法分析树
它的叶结点从左到右得到了这样一个串
ab空串ba
这个就是这个语法分析树的产物
也可以写成abba
因为空串 可以不需要
这是语法分析树
这也就是我们讨论的子树
你像再给了 用了这一个产生式
那它本身就可以看作是一个树
那这个看作是分析树的一个子树
这个A产生aba
这样得到一个子树
它构成了整个也是
算一个语法分析树的子树
得到了叶结点
从左到右排成了一个串
也是这个子树的一个句型
它们也可以是各种各样的句型
这节里面我们也介绍了
上下文无关文法里面的
另外的一种表示形式
就是语法分析树
语法分析树里面 我们可以看出
任何一个句型或者一个句子
它都对应文法当中的一棵语法分析树
这个在我们后面的推导
或者语法分析树它们之间
它们都有一种密切的关系
这就是我们下一节要讲的内容
这节内容介绍完毕
谢谢大家
-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
-习题--作业
-期中考试
