编译原理 第四章&第五章:语法分析 LR(0)分析器 SLR(1)分析器

第三章学习了词法分析，本章来学习语法分析的其中一种方法，语法分析大体上分为两类，一种是自顶向下分析法，一种是自底向上分析方法。

本章，主要讲解的是自顶向下的分析方法

第四章 语法分析

4.1语法分析-自顶向下分析法

4.1.1 概念

首先明确：

1. 输入：单词序列
2. 输出：语法树
3. 语法规则：2型文法
4. 单词为语法规则中的终结符号

语法分析的任务：

检查源程序语法上是否正确，识别语法成分，并生成语法树供下一个阶段使用。

出现错误处理要求：

• 尽快发现错误，准确定位。
• 可能时进行恢复处理，继续语法分析

自顶向下的语法分析和自底向上的语法分析的区别：

自顶向下的语法分析：从文法识别符号开始，构造句子的最左推导

自底向上的语法分析：构造句子的最左规约，规约到文法识别符号。

自顶向下分析方面临的问题：

自顶向下语法分析面临的问题-回溯问题，回溯大大降低效率。

自顶向下分析法（不带回溯方法）中的LL(K)分析法和递归下降法不在考察范围之内。

故本节重点放在如何求first集和follow集

4.1.2 求first集和follow集合

不带回溯的分析方法：first集合和follow集合

关于first集和follow集的求法已经放到了另一篇博客中编译原理必考大题:first集和follow集的求法

5. 语法分析-自底向上分析法

5.1 规范推导,规范句型和规范规约

自底向上也称移进归约法,关键问题在于如何找到当前句柄.

其实就是把一个语法的句柄,一步一步规约.

5.2 LR分析法

作为自底向上分析方法的一个重要的方法,需要熟练掌握

LR(k)分析方法:

L:从左到右扫描所给定的输入串.

R:以相反的方向构造该输入串的最右推导

k:做出分析决定需要向前看的输入符号的个数.

5.2.1 LR分析表的构成

1. 移进(S~n~):将输入符号移进符号栈，将状态ns移透状态桃，输入指针指向下一个输入符号。
2. 归约(R~I~):用第i条产生式左侧的非终结符替换栈顶的句柄.
3. 接受(A):输入符号达到右界符#时、且符号栈只有文法的开始符号。则分析成功结束。
4. 报错(E):在状态栈顶状态，输入符号为不应该遇到的符号时，则报错。

练习:给定LR分析表和文法,分析((a))

方法步骤:

1. 初始化,状态栈为0,符号栈为#,输入符号串为(题目待分析字符串,以#结束)
2. 紧盯状态栈和输入符号串栈顶,通过状态栈和符号串栈顶来查表
3. 一般来说查表结果有三个S或R或ACC,当查表是S什么时,需要进行移进操作,将输入符号串栈顶元素放入符号栈中,将S的下标数字压入状态栈,再进行下一步.若是R,就是规约操作,规约操作需要我们填写goto这一项,根据R下标的值,看对应的文法,对应文法将什么规约成什么,状态栈删去右部规约文法的符号个数,然后将当前状态栈栈顶的元素和文法左部规约后的符号进行查表,确定goto值,然后将goto值压入状态栈.把符号栈中的文法规约填好,再进行下一步,若是ACC,则得出分析已经完毕.

5.2.2 LR文法项目集规范族

本小节，作为必考大题的一部分，为单独撰写在编译原理必考大题:构造项目集规范族

5.3 LR(0)分析器

拓广文法: 使文法只有一个以识别符号作为左部的产生式,从而构造出来的分析器有唯一的接受状态.

活前缀和可归活前缀:

一个句型的可归活前缀就是句柄,活前缀是句柄从删除一个或若干个符号,保证>=1个.

例如一个句型的句柄是abcd,那么他的活前缀就是a,ab,abc,abcd,可规活前缀就是abcd

5.4 SLR(1)分析器

当项目集中存在移进-规约冲突和归约-归约冲突,可以避免无法构造出分析表的问题.

从本质上来说:通过向前查看一个输入符号来协助解决冲突,该文法就是SLR(1)文法.

简单来说,就是求非终结符号的follow集,然后在又移进又规约的时候,或者出现多次规约的时候,根据R规约成的非终结符号,确定该非终结符号的follow集,它的follow集合里面有哪些终结符号,就在哪些终结符号的下面写r几,而LR(0)文法是整行去写.

简单来说，SLR（1）和LR（1）在项目集规范族的构造角度上来说一样，只是之后的处理不一样，前者需要求follow集，再构造SLR(1)分析表，后者直接就能写出分析表，

综上就避免了冲突

5.4.1 题目实战

题目一

证明下列的文法是SLR(1)文法

证明文法是SLR(1)文法,就是写出项目集规范族，之后，发现存在规约与规约之间的冲突或者规约和移进之间的冲突，就说明他不是LR(0)型文法，而是SLR(1)型文法。

简言之，有冲突就是SLR(1)型文法

5.5 LR(1)分析器

本节并非重点，重点在于讲述原理。

LR(1)文法能进一步解决SLR(1)文法仍解决不掉的问题。

5.5.1 LR(1)项目集规范族的闭包运算

必须掌握

方法：

1. 闭包运算通过树状图的形式进行
2. 求解过程就是不断深入，每一个结点不重复，点的位置是不变的，他后面的数改变，盯着结点的左部a，它父结点a的位置后方的终结符号就是新结点的逗号后的符号，如没有，父结点逗号后是什么符号，原结点就是什么符号。

例题一

例题二

5.6 LALR(1)分析器

本节也非重点，但是复习要全面，掌握目的，分析能力，局限性即可。

目的：化简LR(1)分析，减少资源开销

分析能力：高于SLR(1)分析

局限性：合并中不出现归约归约冲突。

5.7 语法分析自动生成工具-YACC

YACC源程序是用YACC语言编写的语法说明规则，

Y_tab.c是该语言的语法分析器

YACC生成LALR(1)分析器