当前课程知识点:软件理论基础 >  第八章 CFG的应用与文法的二义性 >  8.3 文法二义性 >  Video

返回《软件理论基础》慕课在线视频课程列表

Video在线视频

Video

下一节:Video

返回《软件理论基础》慕课在线视频列表

Video课程教案、知识点、字幕

欢迎同学们来到《软件理论基础》的MOOC课堂

现在介绍上下无关文法应用

与文学二义性的第三节

文法的二义性

我们首先看一个例子

这是一个上下无关文法

实际上跟我们之前介绍的上下无关文法

是一样的

这是第一个产生式 第二个产生式

第三个产生式 第四个产生式

从这个文法

我现在要推 W等于a+a×a

这个推导采用上一讲里面介绍的

最左推导

第一次用第一个产生式得到它

再用第四个产生式得到它

再用第二个产生式得到它

再用第四个产生式得到它

最后你用第四个产生式得到它

这样你用最左推导 就推导出这个字符串

这个最左推导

它对应的唯一的一个语法分析式树

这个语法分析树就是这种形式

同样对这个字符串

这里面我们首先利用第二个产生式

然后利用第一个产生式

再用第四个产生式

再用第四个产生式

再用第四个产生式

这样同样也推出a+a×a

这样同样一个字符串

在这个文法里面

它有这样一个最左推导

它对应的语法分析树是最左形式

它跟这个最左推导也是一一对应的

这说明对同样一个字符串

它就有两个

这个不同的语法分析树

对这样的字符串

有两个不同的语法分析树

我们把它这样的文法称为它叫二义的

也可以用另外一种表示

这个文法里面它只有某一个字符串

有两种不同的最左推导或者最右推导

它也是说叫二义的

就像刚才这个文法

第一次我们得到的是这个最左推导

而第二次我们得到的

是另外的一种最左推导

这两个最左推导 大家看

它们的形式是完全不一样的

这说明这个文法它是叫二义的

文法的二义到底怎么定义的

我们的概念是这样给的

给了一个上下无关文法

如果有一个字符串W

从开始变量到这个字符串

有两个不同的语法分析树

那我们就说这类文法是二义的

如果一个文法对任何一个字符串

它只有一棵语法分析树

那这类文法是叫无二义的

可以证明这一个定理

这个定理就是说给了一个上下无关文法W

就是这个字符串

它有两颗不同的语法分析树

当前仅当

它有两个不同的从S到W的最左推导

这个证明大家可以自己证明

我们说文法它的定义

是从两个不同的语法分析树来定义的

那么有了这个定义之后

我们可以给出二义性的

它的另外一种定义

这个定义就是说一个上下无关文法

它称为二义的

如果有一个字符串

它有两个不同的

从S到W不同的最左推导

那我们就称这个文法是二义的

这样的一种定义

跟我们刚才的用语法分析树来定义

我们从这个定理看 它们是等价的

那有时候从这种定义

是更容易去判别一个文法是不是二义的

我们想为什么要去讨论文法的二义

我们看看刚才给了这个字符串

在我们给出的那个上下无关文法里面

它有两个不同的语法分析树

但这两个不同的语法分析树

赋值的时候

我们推出a等于2

这里a等于2

这个里面a也等于2

从这里2赋值 再赋值 再乘4

这2赋值

这里加等于6

所以这个结果是等于6

这样的一个赋值2,2

它们相加的结果是等于4

4这个2赋值到2

2跟4相乘等于8

所以这个结果是等于8

一个结果是等于6

一个结果是等于8

这里正确的结果应该是等于6

所以这种结果是错的

这就说明刚才的文法对这样一个字符串

就是它有两个不同的一个结果

有一个正确结果

有一个错误结果

那错误的作为我们软件来说

是不希望看到的

怎么样去判定这个文法是没二义的

能够判定有这么一个算法

能够判定一个文法是没二义的

那当然是最好的

当然我们后面我们要证明

上下无关文法

它是不是二义这个问题

是没有算法的

也就是说它是不可判定的

虽然上下无关文法

它是不是二义是不可判定的

但是我们在后面也介绍

对一些特定的一些上下无关文法

我们还是有一些改进的措施

好 这节内容介绍完毕

谢谢大家

软件理论基础课程列表:

第一章 基础知识

-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

-习题--作业

第六章 正则语言的性质与DFA优化

-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

-习题--作业

第八章 CFG的应用与文法的二义性

-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

-习题--作业

第十章 下推自动机与CFG化简规范

-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

-习题--作业

第十二章 Turing机

-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

-习题--作业

期中考试

-期中考试

Video笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。