lr分析法

第讲LR分析法

LR分析法是一种常用的语法分析方法，可以用于生成语法树，它是自底向上的语法分析方法。在LR分析法中，L表示“自左向右扫描输入串的方式”，R表示“反向构建和规约的方式”。

LR分析法包括以下几个步骤：

1.构造LR(0)项目集规范族：LR(0)项目集是指在一些语法分析的过程中，每个项目表示对应的产生式的哪一部分已经被扫描过了，哪一部分还没有被扫描过。根据给定的文法，构造出所有可能的项目集，并将它们进行编号，得到项目集规范族。

2.构造LR(0)项目集规范族的DFA：根据构造出的LR(0)项目集规范族，可以构造出一个DFA（确定性有限自动机）来表示LR(0)语法分析的过程。DFA的每个状态表示一个项目集，每个转移表示在一个状态下扫描一些符号后转移到另一个状态。

3.构造LR(0)分析表：根据构造出的LR(0)项目集规范族的DFA，可以构造出一个分析表，即LR(0)分析表。分析表的行表示当前状态，列表示当前输入符号，表格中的每个元素表示下一步应该做的动作，可以是移进一些符号，也可以是规约一些项目。

4.进行LR(0)分析：根据构造出的LR(0)分析表，可以进行LR(0)语法分析。分析的过程是根据当前状态和输入符号，在分析表中查找对应的动作，并执行该动作。如果遇到移进动作，就将符号加入到解析栈中，同时移动输入指针；如果遇到规约动作，就从解析栈中弹出一些符号，然后根据规约产生式将新的非终结符加入到解析栈中。 5.构造SLR(1)分析表：LR(0)分析表中存在冲突的情况，无法完全正确地进行语法分析。为了解决这个问题，需要对LR(0)分析表进行优化，得到SLR(1)分析表。SLR(1)分析表与LR(0)分析表的结构类似，只是在一些冲突的情况下给出更加具体的动作指令。

6.进行SLR(1)分析：根据构造出的SLR(1)分析表，可以进行SLR(1)语法分析。与LR(0)分析类似，根据当前状态和输入符号，在分析表中查找对应的动作，并执行该动作。

LR（0）分析法

一．实验目的

熟练掌握自下而上的语法分析方法，会构建ACTION集和GOTO集，并能用程序实现对输入串的分析过程。

二．实验内容

对于一个给定的文法，如G[E]:

E->E+T|T

T->T*F|F

F->(E)|id

对于任意给定的输入串进行语法分析，利用移入-归约分析算法输出对应的动作部分。

三．实验步骤

1.先构造对应于文法G[E]的ACTION表和GOTO表:

ACTION表的S和r信息存放至sym中;

ACTION表的S和r的下表信息存放至snum中;

GOTO表中的信息存放至go2中。

2.调用action函数判断是按哪个式子进行归约的。

3.调用go函数对不同的非终结符进行判断，调用go2.

4.调用error函数对错误信息进行处理。

四、源代码：

#include

#include

using namespace std;

stack symbol;

stack state;

char sen[50];

char sym[12][6]={//符号表

{'s',' ',' ','s',' ',' '},

{' ','s',' ',' ',' ','a'},

{'r','r','s','r','r','r'},

{'r','r','r','r','r','r'},

{'s',' ',' ','s',' ',' '},

{'r','r','r','r','r','r'},

{'s',' ',' ','s',' ',' '},

{'s',' ',' ','s',' ',' '},

{' ','s',' ',' ','s',' '},

{'r','r','s','r','r','r'},

{'r','r','r','r','r','r'},

实验5---语法分析器（自下而上）：LR(1)分析法

一、实验目的

构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。

二、实验内容

程序输入/输出示例（以下仅供参考）：

对下列文法，用LR（1）分析法对任意输入的符号串进行分析：

（1）E->E+T

（2）E->E—T

（3）T->T*F

（4）T->T/F

（5）F-> (E)

（6）F->i

输出的格式如下：

(1)LR（1）分析程序，编制人：姓名，学号，班级

(2)输入一个以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串

(3)输出过程如下：

步骤 状态栈 符号栈 剩余输入串 动作

1 0 # i+i*i# 移进

备注：

1.在“所用产生式”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。

2.在此位置输入符号串为用户自行输入的符号串。

注意：

1.表达式中允许使用运算符（±*/）、分割符（括号）、字符i，结束符#；

2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照。

三、实验方法

1．实验采用C++程序语言进行设计，文法写入程序中，用户可以自定义输入语句；

2．实验开发工具为DEV C++。

四、实验步骤

1．定义LR(1)分析法实验设计思想及算法

①若ACTION[sm , ai] = s则将s移进状态栈，并把输入符号加入符号栈，则三元式变成为：(s0s1…sm s , #X1X2…Xm ai , ai+1…an#)；

计算机科学与技术系

实 验 报 告

专业名称 计算机科学与技术

课程名称 编译原理

项目名称 LR(1)分析法

班 级

学 号

姓 名

同组人员 无

实验日期 2016.11.4

一、实验目的与要求：

（简述本次实验要求达到的目的，涉及到的相关知识点，实验的具体要求。）

目的：掌握LR(1)分析法的基本原理

掌握LR(1)分析表的构造方法

掌握LR(1)驱动程序的构造方法

要求：

1. 对LR(1)语法规则有明确的定义；

2. 编写的分析程序能够对实验结果进行正确的语法分析；

3. 对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成。

二、实验内容

（根据本次实验项目的具体任务和要求，完成相关内容，可包括：实验目的、算法原理、实验仪器、设备选型及连线图、算法描述或流程图、源代码、实验运行步骤、关键技术分析、测试数据与实验结果、其他）

具体任务：构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。

对下列文法，用LR（1）分析法对任意输入的符号串进行分析：

（1）E-E+T

（2）E-E—T

（3）T-T*F

（4）T-T/F

（5）F-(E)

（6）F-i

输出的格式如下：

(1)LR（1）分析程序，编制人：姓名，学号，班级

(2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串

(3)输出过程如下：

步骤 状态栈 符号栈 剩余输入串 动作