【编译原理笔记06】语法分析，移入-归约分析：自底向上的分析，LR(0)分析法，LR(0)分析表的构建（基于自动机）-低调大师

【编译原理笔记06】语法分析，移入-归约分析：自底向上的分析，LR(0)分析法，LR(0)分析表的构建（基于自动机）

2021-06-22 517

本次笔记内容：
4-8 自底向上的分析概述
4-9 LR分析法概述
4-10 LR0分析
4-11 LR0分析表构造

本节课幻灯片，见于我的 GitHub 仓库：第6讲语法分析_3.pdf

本节课介绍了自底向上的分析，并且举了例子，发现移入-归约分析存在问题，因此引出了LR分析法,以LR(0)分析法为例。在LR(0)分析法中，最重要的就是构建LR(0)分析表，基于自动机。这个解决方案不错。但是有时，造表时可能出现一些冲突，导致这个LR(0)分析法用不了，未来将讲解LSR和LR(1)分析法是如何消解冲突的。

文章目录

自底向上的语法分析

从分析树的底部(叶节点)向顶部(根节点)方向构造分析树
可以看成是将输入串w归约为文法开始符号S的过程
自顶向下的语法分析采用最左推导方式
自底向上的语法分析采用最左归约方式（反向构造最右推导）
自底向上语法分析的通用框架：移入-归约分析(Shift-Reduce Parsing)

例：移入-规约分析

逐步分析如图右侧“动作”，很明确；个人理解是从闻法得右侧向左推导。

注意到，每一个蓝色虚线划分的区域中，栈+剩余输入的内容，总是构成一个相同的“规范句型”。

移入-归约分析的工作过程

在对输入串的一次从左到右扫描过程中，语法分析器将零个或多个输入符号移入到栈的顶端，直到它可以对栈顶的一个文法符号串β进行归约为止；

然后，它将β归约为某个产生式的左部；
语法分析器不断地重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空(当进入这样的格局时，语法分析器停止运行，并宣称成功完成了语法分析)为止。

移入-归约分析器可采取的4种动作

移入：将下一个输入符号移到栈的顶端；
归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串；
接收：宣布语法分析过程成功完成；
报错：发现一个语法错误，并调用错误恢复子例程。

移入-归约分析中存在的问题

如图，对一个语句 var iA , iB : real 进行分析，最后剩余输入中已经没有任何符号了，而栈中并没有归约出文法的开始符号<S>，因此分析失败。

但是，这个文法其实是合法的句子，那么问题出在：错误地识别了句柄，如上图；应该如下图一样进行分析。

那么，如何避免这种错误？正确识别句柄呢？

将在接下来地LR分析技术中详细介绍。

LR分析法

LR文法(Knuth, 1963) 是最大的、可以构造出相应移入-归约语法分析器的文法类
- L: 对输入进行从左到右的扫描
- R: 反向构造出一个最右推导序列
LR(k)分析
- 需要向前查看k个输入符号的LR分析
- k = 0 和 k = 1 这两种情况具有实践意义；当省略(k)时，表示k =1

LR分析法的基本原理

自底向上分析的关键问题是什么？

如何正确地识别句柄

句柄是逐步形成的，用“状态”表示句柄识别的进展程度。

LR分析器（自动机）的总体结构

与移入规约不同的是，LR分析器还包含一个与符号栈平行的状态栈。

LR分析表的结构

sn表示，将符号a、状态n压入栈；
rn表示，用第n个产生式进行归约（r是reduce的缩写）
GOTO中表示，在某一状态，遇到某一非终结符，进入到后继状态。
acc是成功接收的意思。

LR分析表的结构：应用例子

还是上面的分析表，现在输入 b a b ；下面的表格将阐述栈与剩余输入的快照（分析过程）。

状态栈	符号栈	剩余输入
0	$	bab$

0号状态遇到b，移入动作，入栈。

状态栈	符号栈	剩余输入
04	$b	ab$

查表得，4号状态与b，对应动作r3，用第3个产生式进行归约，也就是说b出栈，B进栈。

状态栈	符号栈	剩余输入
0	$B	ab$

差表得，0号状态与B，对应GOTO 2，则2号状态进栈。

状态栈	符号栈	剩余输入
02	$B	ab$

状态栈	符号栈	剩余输入
023	$Ba	b$

状态栈	符号栈	剩余输入
0234	$Bab	$

状态栈	符号栈	剩余输入
023	$BaB	$

状态栈	符号栈	剩余输入
0236	$BaB	$

状态栈	符号栈	剩余输入
02	$BB	$

状态栈	符号栈	剩余输入
025	$BB	$

状态栈	符号栈	剩余输入
0	$S	$

状态栈	符号栈	剩余输入
01	$S	$

1$对应的acc代表成功接收。

LR 分析器的工作过程

LR 分析算法

输入：串w和LR语法分析表，该表描述了文法G的ACTION函数和GOTO函数。
输出：如果w在L(G)中，则输出w的自底向上语法分析过程中的归约步骤；否则给出一个错误指示。
方法：初始时，语法分析器栈中的内容为初始状态s0，输入缓冲区中的内容为w$。然后，语法分析器执行下面的程序。

可以看出，LR分析算法较为简单，重点在于如何构造LR分析表，包括四种，将在后面分别进行介绍：

LR(0)分析
SLR分析
LR(1)分析
LALR分析

LR(0) 分析法

LR(0) 项目

右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目）。
A → a 1 ⋅ a 2 A \rightarrow a_1 \cdot a_2 A→a1⋅a2

项目描述了句柄识别的状态；右侧有k个符号，则有k+1个项目。

增广文法(Augmented Grammar)

如果G是一个以S为开始符号的文法，则G的增广文法G’ 就是在G中加上新开始符号S’ 和产生式S’ → S而得到的文法。（我个人理解就是一句话，在开头）

引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态。

文法中得项目

后继项目（Successive Item）：

同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目；
A→α· Xβ的后继项目是A→αX·β

上面一共有15个项目，是否会有项目是等价的呢？

(0)和(2)是等价的；
(3)和(7)/(11)是等价的；
(5)和(13)是等价的。

当项目中圆点后面的符号是非终结符时，其存在等价项目。

可以把等价的项目组成一个项目集( I )，称为项目集闭包(Closure of Item Sets)，每个项目集闭包对应着自动机的一个状态。

例：LR(0)自动机

首先构造自动机，随后根据自动机画LR(0)分析表。

LR(0)分析表构造算法

如何实现上文的自动机？

首先定义两个函数。

CLOSURE() 函数

GOTO()函数

构造LR(0)自动机的状态集

LR(0)分析表构造算法

LR(0)自动机的形式化定义

LR(0)分析的基本原理，就是根据给定的文法，来构造对应的自动机M：

M的状态集就是C，符号表就是非终结符和终结符集合的并集，转换函数就是GOTO函数；
M的初始状态I0就是文法的初始项目的项目集闭包；
M的终止状态F就是文法的接收项目的项目集闭包。

LR(0)分析过程中的冲突

如图，是一个描述算术表达式的文法。

这里状态2、9存在冲突现象：存在移进/归约冲突。

此外，还有归约/归约冲突。

如果LR(0)分析表中没有语法分析动作冲突，那么给定的文法就称为LR(0)文法。

不是所有CFG都能用LR(0)方法进行分析，也就是说，CFG不总是LR(0)文法。

如何消解冲突？

在后面将介绍LSR和LR(1)分析法是如何消解冲突的。

微信关注我们

原文链接：https://blog.51cto.com/u_15279775/2938797

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

IDEA上面搭建一个SpringBoot的web-mvc项目

2 --> 这几天一直在研究IDEA上面怎么搭建一个web-mvc的SpringBoot项目，看网上的教程一步步的搭建，可是还是出现一堆的问题。想学习分布式、微服务、JVM、多线程、架构、java、python的童鞋，千万不要扫码，否则后果自负~ 为了让大家以后少走一些弯路，我在这里分享一下我这几天研究的成果，也希望对大家能有所帮助。这里先介绍一下各种环境的配置信息：idea2016.2.1 jdk1.8.0_31 因为SpringBoot中是内置tomcat的，所以也就不需要额外的tomcat配置了，现在开始讲如何在idea上面搭建SpringBoot web-mvc项目了步骤一：在IDEA中新建一个常规的maven项目，具体步骤请看看下面的图示：通过图上面的几个步骤，一个基本的maven项目就搭建完成了，接下来就是开始搭建SpringBoot中各种配置文件信息了。步骤二： 1.先复制以下代码到pox.xml中去 <?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://maven.ap...

2021-06-22

635

作者：wuzhu 校稿：木子 ------ **译者注** 今天，Rocky Linux正式发布啦！这是Rocky Linux第一个可用于生成环境的版本，使用者可以通过Rocky Linux社区获取免费的技术支持，也可通过CIQ获得付费的商业技术支持。[阅读原文](https://forums.rockylinux.org/t/rocky-linux-8-4-available-now/3015/1)。 **译文：** Rocky企业软件基金会（RESF）很高兴宣布，Rocky Linux 8.4可用于以下体系结构： | **Architecture** | **Minimal** | **DVD** | **Boot** | **Packages** | | ---------------- | ----------- | ------- | -------- | ------------ | | x86_64 | X | X | X | X | | ARM64 (aarch64) | X | X | X | X | 我们已经对其进行了充分的测试，因此对此发行版用于生产环境的稳定性我...

2021-06-22

729

资源下载

更多资源

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。