实验三 LR(1)分析法
实验学时：4
实验类型：验证
实验要求：必修
一、实验目的
构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。
二、实验内容
对下列文法，用LR（1）分析法对任意输入的符号串进行分析：(产生式有误，进行修改)
（1）E- E+T
（2）E- E—T（E->T）
（3）T- T*F
（4）T- T/F(T->F)
（5）大事小事F- (E)
（6）F- i
三、实验目的
1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。
2、如果遇到错误的表达式，应输出错误提示信息。
3、程序输入/输出实例：
输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串
输出过程如下：
步骤 状态栈 符号栈 剩余输入串 动 作
1 0 # i+i*i# 移进
i+i*i的LR分析过程 |
步骤 | 状态栈 | 符号栈 | 输入串 | 动作说明 |
1 | 0 | # | i+i*i# | ACTION[0,i]=S5,状态5入栈 |
2 | 05 | #i | +i*i# | r6: F→i归约,GOTO(0,F)=3入栈 |
3 | 03 | #F | +i*i# | r4: T→F归约,GOTO(0,T)=3入栈 |
4 | 02 | #T | +i*i# | r2: E→T归约,GOTO(0,E)=1入栈 |
5 | 01 | #E | +i*i# | ACTION[1,+]=S6,状态6入栈 |
6 | 016 | #E+ | i*i# | ACTION[6,i]=S5,状态5入栈 |
7 | 0165 | #E+i | *i# | r6: F→i归约,GOTO(6,F)=3入栈 |
8 | 0163 | #E+F | *i# | r4: T→F归约,GOTO(6,T)=9入栈 |
9 | 0169 | #E+T | *i# | ACTION[9,*]=S7,状态7入栈 |
10 | 01697 | #E+T* | i# | ACTION[7,i]=S5,状态5入栈 |
11 | 016975 | #E+T*i | # | r6:F→i归约,GOTO(7,F)=10入栈 |
12 | 0169710 | #E+T*F | # | r3: T→T*F归约,GOTO(6,T)=9入栈 |
13 | 0169 | #E+T | # | r1:E→E+T,GOTO(0,E)=1入栈 |
14 | 01 | #E | # | Acc：分析成功 |
| | | | |
实验报告正文的内容：
◆描述LR(1)语法分析程序的设计思想:
◆定义项目的一般形式是[A→·, a1a2…ak] ，这样的一个项目称为一个LR(k)项目。项目中的 a1a2…ak 称为它的向前搜索符串(或展望串)，令K=1,即为LR(1)语法分析程序。在此，重新定义CLOSURE(I)的算法：
项目集I 的闭包CLOSURE(I)构造方法：
1. I的任何项目都属于CLOSURE(I)。
2. 若项目[A→·B, a]属于CLOSURE(I)，B→ 是一个产生式，那么，对于FIRST(a) 中的每个终结符b，如果[B→·, b]原来不在CLOSURE(I)中，则把它加进去。
3. 重复执行步骤2，直至CLOSURE(I)不再增大为止。
GO()的算法保持与LR语法分析程序一样，通过以下方法构造文法分析表：
动作ACTION和状态转换GOTO构造如下：
1. 若项目[A→·a, b]属于Ik且GO(Ik, a)＝Ij， a为终结符，则置ACTION[k, a]为 “sj”。
2. 若项目[A→·，a]属于Ik，则置ACTION[k, a]为 “rj”；其中假定A→undefined为文法Gundefined的第j个产生式。
3. 若项目[S→S·, #]属于Ik，则置ACTION[k, #]为 “acc”。
4. 若GO(Ik，A)＝Ij，则置GOTO[k, A]=j。
5. 分析表中凡不能用规则1至4填入信息的空白栏均填上“出错标志”。
当具体面对输入串时，通过查表进行分析该进行何种动作。
◆程序结构描述：函数调用格式、参数含义、返回值描述、函数功能均在程序源代码出注释出来，在此不再赘述，详细含义请参照源代码cpp文件。
◆详细的算法描述（程序执行流程图）:
(1)总控程序，也可以称为驱动程序。对所有的肉穗花序LR分析器总控程序都是相同的。
(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。
(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。
分析器的动作就是由栈顶状态和当前输入符号所决定。
◆LR分析器由三个部分组成：
◆其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。
◆ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：
(1)移进：
action[i，a]= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。
(2)归约：
action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A- B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。
(3)接受acc:
当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符
是'#'，则为分析成功。
(4)报错:
当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。
四、实验要求
本程序原本的设计思想与实验二相仿，但由于此种设计思想会导致程序灵活性大大降低，故对设计思想进行优化，在此，不在对原程序设计思想进行阐述，仅对改良后的程序设计思想进行阐述。
该文法的LR(1)分析表：
算术表达式文法的LR分析表 |
状 态 | ACTION | GOTO |
i | + | * | ( | ) | # | E | T | F |
0 | 人生真谛S5 | | | S4 | | | 1 | 2 | 3 |
1 | | S6 | | | | acc | | | |
2 | | r2 | S7 | | r2 | r2 | | | |
3 | | r4 | r4 | | r4 | r4 | | | |
4 | S5 | | | S4 | | | 8 | 2 | 3 |
虾怎么洗5 | | 那双眼睛 r6 | r6 | | r6 | r6 | | | |
6 | S5 | | | S4 | | | | 9 | 3 | 中国历史书
7 | S5 | | | S4 | | | | | 10 |
8 | | S6 | | | S11 | | | | |
9 | | r1 | S7 | | r1 | r1 | | | |
10 | | r3 | r3 | | r3 | r3 | | | |
11 | | r5 | r5 | | r宝宝图片大全可爱5 | r5 | | | |
| | | | | | | | | |
咽的读音
本程序根据给出的LR(1)文法分析表，构造string 类的action[12][6]={"S5","0","0","S4","0","0", //ACTION表
