当前课程知识点:编译技术 >  第三章 语法分析 >  3.1 上下文无关文法 >  3.1.2 上下文无关文法定义

返回《编译技术》慕课在线视频课程列表

3.1.2 上下文无关文法定义在线视频

下一节:3.1.3 推导

返回《编译技术》慕课在线视频列表

3.1.2 上下文无关文法定义课程教案、知识点、字幕

各位同学大家好

欢迎大家来学习语法分析这一课

我们就正式进入到

上下文无关文法的学习

上下无关文法当中

我们重点学习三个方面的内容

首先是它的定义

我们来看一下正规式

它可以来定一些简单的语言

可以表示给定结构的

固定次数的重复

或者你没有指定次数的重复

正规式也是可以完成的

比如说在这里边

a(ba) 5次幂 (表示:)

以 a 开头

后边跟着5个 ba 这样一个串

或者 a 开头

后边跟着零个或者 n 个 ba 这样的串

正规式都可以来进行描述

但是,正规式不能用来描述配对的

或者嵌套的结构

我们在程序当中

有非常多的配对的结构

比如说

我们在程序中

常常会写的

括号的串

那么你像下面这里边表示的wcw

w它用来表示 a、b 的串

而 c 前后的 w 是一致的

w它要配对

但是正规式

就没有办法去描述

这个 w 是一个什么样的 w

没有办法把 c 的前后 w 是一致的

这就是我们为什么要学习上下文无关文法

我们来看一下上下文无关文法的定义

上下文无关文法是一个4元组

我们把它写成 (VT, VN, S, P) 这样的形式

那么这是从数学上去定义它

VT表示的是终结符的集合

终结符就是那些记号名

记号的集合

非空有限集合

VN是非终结符的集合

当然VN也是一个非空的有限集合

非终结符的集合

和终结符的集合相交等于空

也就是说一个符号

要么是终结符

要么是非终结符

如果一个符号是终结符

它就肯定不是非终结符

然后S用来表示开始符号

P用来表示产生式的集合

产生式的形式

我们把它写成 A → α

这个箭头 → 可以读作产生

也就是A产生α

A是属于VN

也就是A是一个非终结符的集合

产生式的左部是非终结符

而 α 是属于VN和VT的并集括起来的闭包

也就是 α 是一个串

是一个终结符和非终结符混合的

这样的一个串

我们来看一个具体的例子

一个上下文无关文法

具体的例子是什么样呢

我们写成上面的形式

仍然是包括4个部分

前面首先

是终结符的集合 { id, +, *, -, (, ) } 结束

然后是非终结符的集合

包括 expr (expression) op (operator)

op是操作符

然后他得开始符号是expr

产生式的集合

我们记成 P

那么P是什么呢

P就是下面写的这6条产生式

我们来看一下这6条产生式

第一条产生式 expr → expr op expr

第二条产生式 expr → (expr)

第三条产生式 expr → - expr

第4条产生式 expr → id

第5条产生式 op → +

第6条产生式 op → *

那么在这里

我们会观察到

expr

这个符号

可以在多个产生式当中去出现

这些产生式之间

是没有强制的顺序关系的

这和正规式是不一样的

正规式是有顺序关系的

接下来是只在产生

右部不出现的这些符号

( ) - id + *

这几个符号我们观察到

它只在产生式的右部出现

那么我们就把它叫做终结符

也就是说终结符

只在产生式的右部出现

我们观察一下

产生时的左部出现的是非终结符

刚才写的

大家看起来

就觉得很麻烦了

所以我们提供一下

上下文文法的一些简化的表示

写起来会更简单一些

首先是终结符的简化表示

在终结符当中

字母表前面的那些小写字母

比如说a b c

你就可以直接用了

用它去表示终结符

第二个黑体的串

比如说 id 或者 while

它是来表示终结符的

因为 id 或者 while 一般是指关键字这些

是终结符

第3个 数字0、1、2、3一直到9

这些是终结符

第4个 标点符号

比如说 , ( ) 这些都是终结符

第5个运算符号+ - * 除

这些也通常是终结符

我们再来看一下非终结符

针对非终结符

我们使用字母表当中

前面的那些大写字母去表示

比如说ABCD

还有一个特殊的

就是字母表当中的S

通常我们用它来表示开始符号

第三个

小写字母的名字

比如说 expr 或者 stmt (statement)

这些我们通常也用来表示非终结符

那么还有一些常用的

其他的简化表示

比如说

首先字母表当中

后面的那些大写字母

XYZ等等

可以用来表示非终结符

或者是终结符

第二字母表当中

后边的那些小写字母

u, v, w, z 这些一般用来表示终结符对应的串

第三

小写的希腊字母

通常代表文法的符号串

那么

第四

如果 A → a1

A → a2

我们就会简写

记作 A → a1 | a2

这是没有先后顺序的

我们再看一下

前面刚刚学过的上下无关文法

如果我们使用简化的表示

它会是什么样呢

简化表示之后

就非常的简单了

expr 我们用 E 去表示

op 我们用 A 表示

就变成了下边这个样子

E → E A E | (E) | -E | id

而 A 用来表示 + 或者 *

有了简化表示

我们就会发现

上下文无关文法

还是蛮简单的

我们再把上下无关文法和正规式

做个简单的比较

左边是我们刚刚学过的上下无关文法

右边是正规式的定义

你会观察到对于正规式来说

虽然也是用箭头来表示

但是这个箭头的左边

是正规式的名字

而针对上下无关文法

箭头的左边是它的非终结符

它可以进一步来进行扩展

进行了产生更多的符号

这一讲就介绍到这

谢谢大家

编译技术课程列表:

第一章 绪论

-1.1 编译技术绪论

--1.1 编译技术绪论

--编译原理介绍--作业

第二章 词法分析

-2.1  词法记号 串和语言

--2.1 词法记号 串和语言

--2.1  词法记号 串和语言--作业

-2.2  正规式 状态转换图

--2.2 正规式 状态转换图

--2.2  正规式 状态转换图--作业

-2.3  有限自动机

--2.3 有限自动机

--2.3  有限自动机--作业

-2.4  DFA构建 子集构造法 DAF化简

--2.4 DFA构建

-2.5 Lex

--2.5 词法分析工具Lex

第三章 语法分析

-3.1 上下文无关文法

--3.1.1 语法分析概述

--3.1.2 上下文无关文法定义

--3.1.3 推导

--3.1.4 二义性

-3.2 自上而分析中的文法

--3.2.1 消除左递归

--3.2.2 提取左因子

--3.2 上下文无关文法--作业

--3.2.3 语言和文法

--3.2.3 语言和文法--作业

-3.3 自上而下分析

--3.3.1 first follow

--3.3.2 LL(1)文法

--3.3.3 递归下降分析

--3.3.4 非递归下降分析的预测分析器

-3.4 自下而上分析

--3.4.1 归约句柄

--3.4.2 移进归约分析过程

--3.4 自下而上分析--作业

-3.5 LR分析器

--3.5.1 LR分析器

--3.5.2 活前缀

--3.5.3 SLR分析方法

--3.5.4 规范的LR分析方法

--3.5.5 LALR分析方法

--3.5.6 LR分析方法特点

--3.5.7 非二义且非LR的上下文无关文法

第四章 语法指导的翻译

-4.1 语法制导的定义

--4.1.1 属性文法

--4.1.2 属性依赖图和计算次序

--4.1 语法制导的定义--作业

-4.2 S属性的自下而上计算

--4.2.1 S属性的自下而上计算

--4.2.2 栈代码

-4.3 L属性定义

--4.3.1 L属性定义

--4.3.2 翻译方案

--4.3.3 预测翻译器的设计

--4.3 L属性定义--作业

-4.4 L属性的自下而上计算

--4.4.1 L属性的自下而上计算

--4.4.2 模拟继承属性的计算

--4.4 L属性的自下而上计算--作业

第五章 运行时存储空间的组织与管理

-5.1  概述

--5.1 概述

--概述-作业

-5.2  全局栈式存储分配

--5.2 全局栈式存储

-5.3  调用序列

--5.3 调用序列

-5.4 非局部名字的访问

--5.4 非局部名字

--5.4 非局部名字的访问--作业

第六章 中间代码生成

-6.1 中间代码生成

--6.1 中间代码生成概述

-6.2 作用域信息的保存

--6.2 声明语句-作用域信息的保存

第七章 代码生成

-7.1 代码生成器设计中的问题

--7.1 代码生成器的设计中的问题

-7.2 目标机器

--7.2 目标机器

--7.2  目标机器--作业

-7.3 基本块和流图

--7.3 基本块和流图

-7.4 一个简单的代码生成器

--7.4 一个简单的代码生成器

第八章 基于Python的编译器框架实现

-8.1 基于Python的编译器框架演示视频和代码

--8.1 基于Python的编译器框架演示

-8.2 代码介绍

--8.2.1 Scanner

--8.2.2 Parser -1LRItem

--8.2.3 Parser-2ActionGoto

--8.2.4 SA

-8.3 SimpleJava

--8.3 SimpleJava

3.1.2 上下文无关文法定义笔记与讨论

也许你还感兴趣的课程:

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