当前课程知识点：编译技术 > 第三章 语法分析 > 3.5 LR分析器 > 3.5.2 活前缀
各位同学大家好
这节课我们来学习语法分析中活前缀的概念
活前缀
我们首先学习一下它的定义
我们观察到
右句型的活前缀
是指这个前缀它不超过最右句柄的右端
那么首先我们要知道
右句型是使我们在进行推导的时候
进行最右推导所形成的句型
那么前缀的意思是指
一个符号串的前缀
从第一个符号开始连续的若干个符号构成的一个子串
我们把它用数学的形式来表示出来
假设从S开始进行最右推导
我们得到了γAω
然后在下一步
我们仍然进行最右推导
假设ω全部都是终结符的串
那么我们需要推导的A
假设存在着A产生β这样的产生式
我们将A推导为β
也就是在下一步
我们得到了γβω
在这种情况下，β是句柄
那么γβ的任何前缀
它都是一个活前缀
因为β是句柄
我们只要不超过 β 的最右端
它都是我们所认为的活前缀
也就是包括空串、γβ本身以及γ本身都是活前缀
如果参照活前缀的定义的话
我们根据一个具体的例子来讲一下
到底哪些符号是活前缀呢？
仍然是用文法S产生aABe
A产生Abc或者b
B产生d
我们只要知道哪些是句柄
只要在自下而上的分析中
我们把句柄分析出来
然后每一次我们找出来
所有不超过句柄最右端的那些前缀
就是我们所要的活前缀
我们先看一下
自下而上的分析中
可能出现的一些串
包括
a、ab、aA、aAb、aAbc、aAd、
aAB、aABe以及S
我们知道这些符号
是在自下而上的分析中
在栈中可能出现的一些串
我们再继续分析一下
有如下的几个情况
首先如果一个活禽缀
已经包含了这个句柄的全部的符号
那么我们应该想到
句柄整个出现了
它在活前缀中
最终整个句柄都出现了
如果这样的话
我们应该参照它对应的产生式
来进行归约
比如说ab
它已经出现在栈里边
我们观察到b是一个句柄
如果b是句柄
我们需要按照A产生b这个产生式来进行归约
再比如说栈里边的aAbc
如果是串的话
我们仍然发现是已经出现了句柄
A可以产生Abc
那么需要按照产生式来进行归约
还有aAd
这个时候d作为句柄出现
我们需要将 d 归约为B
接下来的一个串aABe
我们可以认为
它已经出现了整个句柄
我们需要将它归为S
接下来我们来看一下第2个情况
在栈里边没有出现整个句柄
而是出现了句柄的一部分
比如说我们有一个产生式
A可以产生β1β2
在栈里边β1已经出现了
接下来我们期待的是β2的出现
我们来看一下
这种情况的例子
比如说栈中出现了一个串aA
我们发现其实没有形成句柄
但是根据产生式A可以产生Abc
我们期待在A之后能看到b和c
再比如说
栈中如果出现了aAb
我们接下来希望看到的是c
如果栈中出现的串aAB
我们接下来期待出现的是e
第3个情况
活前缀当中不含有任何的符号
在这种情况下
我们期望着可以通过产生式A产生β的右部
所推导出来的符号
我们也就是期待着β的出现
比如说第1个情况
栈里边是a这个符号
我们接下来期待A的出现
而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
