当前课程知识点:编译技术 > 第三章 语法分析 > 3.1 上下文无关文法 > 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 编译技术绪论
--编译原理介绍--作业
-2.1 词法记号 串和语言
--2.1 词法记号 串和语言--作业
-2.2 正规式 状态转换图
--2.2 正规式 状态转换图--作业
-2.3 有限自动机
--2.3 有限自动机--作业
-2.4 DFA构建 子集构造法 DAF化简
-2.5 Lex
-3.1 上下文无关文法
--3.1.3 推导
-3.2 自上而分析中的文法
--3.2 上下文无关文法--作业
--3.2.3 语言和文法--作业
-3.3 自上而下分析
-3.4 自下而上分析
--3.4 自下而上分析--作业
-3.5 LR分析器
-4.1 语法制导的定义
--4.1 语法制导的定义--作业
-4.2 S属性的自下而上计算
-4.3 L属性定义
--4.3 L属性定义--作业
-4.4 L属性的自下而上计算
--4.4 L属性的自下而上计算--作业
-5.1 概述
--5.1 概述
--概述-作业
-5.2 全局栈式存储分配
-5.3 调用序列
--5.3 调用序列
-5.4 非局部名字的访问
--5.4 非局部名字的访问--作业
-6.1 中间代码生成
-6.2 作用域信息的保存
-7.1 代码生成器设计中的问题
-7.2 目标机器
--7.2 目标机器
--7.2 目标机器--作业
-7.3 基本块和流图
-7.4 一个简单的代码生成器
-8.1 基于Python的编译器框架演示视频和代码
-8.2 代码介绍
--8.2.4 SA
-8.3 SimpleJava


