当前课程知识点:编译技术 >  第三章 语法分析 >  3.5 LR分析器 >  3.5.1 LR分析器

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

3.5.1 LR分析器在线视频

下一节:3.5.2 活前缀

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

3.5.1 LR分析器课程教案、知识点、字幕

各位同学大家好

这一节我们来学习语法分析中

自下而上分析当中

一类重要的文法,LR分析文法

以及LR分析器

LR分析器

可以处理的是一大类文法

这类文法我们将它称之为LR(K)文法

K是指我们每次在进行分析的时候

需要向前所查看的符号个数

K=1的时候

通常我们就省略掉

也就是LR(1)

我们可以将它直接称为LR(1)文法

或者LR(1)分析器我们将它直接称为LR分析器

LR分析器采取的是LR分析方法

LR分析方法是我们在进行编译处理的时候

也就是语法分析处理的时候

自下而上分析中的一种

也是我们最为有效、最为常用的一种分析方法

接下来我们来看一下

LR分析器的特点

LR分析器适用于LR文法

它能处理一大类的上下文无关文法

它所处理的文法

比LL1文法

所对应的文法要更多

它的效率同时也要更高一些

我们主要学习LR分析表的三种技术

一种我们将它称为简单的LR分析方法

也就是SLR分析方法

一种叫做规范的LR分析方法

通常我们就将它称为LR分析方法

还有一种是在之前的基础上

稍加改进

我们将它称为向前看的 LR分析方法

简称LALR分析方法

我们先来学习一下整个LR分析器的特点

也就是它的移进归约分析

具体的动作是什么样的

我们仍然来观察一下这个图

LR分析程序在中间的位置

在LR分析表当中

我们将整个表分为了两部分

一部分称为action表,也就是动作表

第二部分

我们将它称为goto表,也就是转移表

那么在栈里边

我们观察到

栈里边除了符号之外,还有对应的状态

在栈底是s0,也就是初始状态

在栈顶,如果符号是xm,对应的状态就是sm

而输入跟之前是一样的

从a1~aN我们仍然在输入末尾

加入$这个符号

为了描述LR语法分析的行为

我们引入了一个新的名词

我们将它称为格局

一个格局实际就是一个状态的意思

我们使用二元组来表示LR分析器所处的一个状态

我们观察一下

使用二元组的左边表示栈的内容

右边表示我们还没有处理的符号

栈的内容

我们将它从底向上写为s0 X1 s1 一直到Xm sm

也就是

除了初始状态s0之外

在每一次我们向栈里边压入一个符号之后

我们都需要在这个符号之上增加一个状态

后边是我们所没有处理的符号串

那么如果我们使用 Xi 来表示文法符号

si来表示状态

当前栈里边所处的

是一个移进归约分析的中间状态

也就是代表着一个右句型X1X2一直到xm,ai一直到an

那么我们把它从Xm和ai分开

也就是在左边是我们已经处理的部分

右边是我们需要处理的部分

我们观察到

在LR分析器中

比之前的分析器

它多了一个状态

那么实际上这个状态

会表示更多的含义

状态的含义比符号本身的含义要更多

接下来我们来观察一下

LR分析器的各种格局

也就是各种状态

那么我们从初始状态开始

我们看一下

在初始状态的时候

栈里只有一个初始状态s0

然后s0的上边没有任何的符号和状态

而输入指向第1个符号a1

同样的

我们需要决定下一步的动作

仍然要根据栈顶的状态

和输入去查表

去查表的时候

我们需要去分析

去查动作表还是去查选择表

那么当前是根据状态和输入来查动作表

也就是action表

如果动作表里写的是移进

我们就要进行移进的动作

如果写的是归约,就要进行归约

假设我们已经进行到一个中间的状态

下一步是要移进

那么当前的状态是这样的:

在栈顶的元素它是Xm

Xm这个符号之上对应的状态sm

然后输入我们假设处理到 ai 这个符号

那么根据栈顶的元素sm这个状态和输入符号

我们去查action表

也就是去查动作表

我们发现动作表中写的是移进

然后还有移进之后

进入到S这个状态

那么我们就将 ai 移入到栈中

然后再将表中写入的移入之后的状态压入到栈中

也就是现在栈顶变成了s

压入符号是ai

也就是在我们进行移进之后

我们将 ai 移入到栈里边

将我们的状态s放入到栈底

这个时候

整个LR分析器的指针指向栈顶的符号s

接下来我们仍然去查表

假设我们根据栈顶的符号sm和输入的符号ai

去查动作表的时候

发现动作表中写的是需要进行归约

那么它会写明是

按照哪一个产生式来进行归约

假设按照A→β这个产生式来进行归约

那么如果按照这个产生式归约的话

我们需要参照β长度的两倍来弹栈

因为我们的栈中

除了符号之外,还包括状态

同样需要把状态弹出栈

所以我们将β长度的两倍这些符号弹出栈

在弹出栈之后

我们需要将整个产生式的左部A移入到栈中

我们将A移入到栈中之后

需要在E之上

填加归约之后的状态

这个时候需要去查对应的动作表

我们观察到

对于当前的状态

s(m-r)这个状态所对应的行、A所对应的列

如果写的状态是S

那么我们就将S压入到A之上

我们再看第3个状态

也就是接受的状态

我们根据栈顶的符号S和输入的符号$

我们去查表

发现在这个情况下

动作表中写的是接受这个状态

那么整个的输入

也已经处理到最后一个符号

而我们的栈里边也只剩X1

那么它应该是文法的开始符号

这个情况下

在我们的动作表中

如果写的是接受

我们就认为当前已经成功结束

当然还有第4种状态

也就是我们在进行查表的时候

发现动作表中

没有任何定义

也就是一个空白

那么意味着出错了

也就是当前的输入串

不满足我们当前的文法

这一小节就到这

谢谢大家

编译技术课程列表:

第一章 绪论

-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.5.1 LR分析器笔记与讨论

也许你还感兴趣的课程:

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