编译原理实验报告
—LL(1)分析法程序
实验2.2 LL(1)分析法
一、实验目的：
1.根据某一文法编制调试LL（1）分析程序，以便对任意输入的符号串进行分析。
2.本次实验的目的主要是加深对预测分析LL（1）分析法的理解。
二、实验平台
Windows + VC++6.0 程序: “3-LL1.cpp”
三、实验内容
1.对下列文法，用LL(1)分析法对任意输入的符号串进行分析：
（1）E→TG
（2）G→+TG|-TG （3）G→ε （4）T→FS （5）S→*FS|/FS （6）S→ε （7）F→(E) （8）F→i 程序功能:
输入: 一个以 # 结束的符号串(包括 + - * /（ ）i # )：例如：i+i*i-i/i# 输出: 经完善程序目前能对所有输入串进行正确的分析.
算法思想：栈用于存放文法符号，分析开始时，栈底先放一个‘#’，然后，放进文法开始符号。同时，假定输入串之后也总有一个‘#’，标志输入串结束。现设置一个文法分析表（见表1），矩阵M[A,a]中存放着一条关于A的产生式，指出当A面临符号a时所采用的侯选。
对任何（X,a）其中X为栈顶符号,程序每次都执行下述动作之一： ? 如果X=a=‘#’，则输出分析成功，停止分析过程；
? 如果X=a且不等于‘#’，则把X从栈顶逐出，让a指向下一个输入符号；
? 如果X是一个非终结符，则查看分析表M.若M[A,a]中存放着关于X的一个产生式，那么首先把X从栈顶逐出，然后，把产生式的右部符号串按反序一一推进栈内，若右部符号为ε，则就什么都不进栈。把产生式推进栈内的同时应做这个产生式相应的语义动作，例如字符i匹配成功，字符出错，相应的产生式等。
输出如下: 输出每一步骤分析栈和剩余串的变化情况, 及每一步所用
的产生式都明确显示出来。
运行步骤：
? 首先在相同的路径下建一文本文档例如11.txt,将表达式写入文档内如i+i*i-i/i#；
? 运行程序，显示界面如下，输入相应的文件名字，（输入输出文件名是自行定义）
? 打开pp.txt文件，文法分析结果如下：
步骤 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 分析栈 #E #GT #GSF #GSi #GS #G #GT+ #GT #GSF #GSi #GS #GSF* #GSF #GSi #GS #G #GT- #GT #GSF #GSi #GS #GSF/ #GSF #GSi #GS #G # 剩余输入串 i+i*i-i/i# i+i*i-i/i# i+i*i-i/i# i+i*i-i/i# +i*i-i/i# +i*i-i/i# +i*i-i/i# i*i-i/i# i*i-i/i# i*i-i/i# *i-i/i# *i-i/i# i-i/i# i-i/i# -i/i# -i/i# -i/i# i/i# i/i# i/i# /i# /i# i# i# # # # 使用的产生式或匹配 E->TG T->FS F->i i匹配! S->^ G->+TG +匹配! T->FS F->i i匹配! S->*FS *匹配！ F->i i匹配! S->^ G->-TG -匹配! T->FS F->i i匹配! S->/FS /匹配！ F->i i匹配! S->^ G->^ 分析成功
错误提示：
1>.输入i++i*i#，结果如下
步骤 1 2 3 4 5 6 7 8 分析栈 #E #GT #GSF #GSi #GS #G #GT+ #GT 剩余输入串 i++i*i# i++i*i# i++i*i# i++i*i# ++i*i# ++i*i# ++i*i# +i*i# 使用的产生式或匹配 E->TG T->FS F->i i匹配! S->^ G->+TG +匹配! T出错! 存在的问题：现在只能是遇到错误就停止，而没能实现同步符号ll(1)分析。 2>.输入非法字符i+a#结果如下:
文法分析如下
输入串中有非法字符
2.完善的功能:
(1) 输出完整的分析过程。即详细输出每一步骤分析栈和剩余串的变化情况, 及每一步所用的产生式.
(2) 输出最终的分析结果, 即输入串 “合法”或 “非法”.
(3)示例程序只能完成 + 、* 、（、）的语法分析,现在的程序加入了 - 和 / 的语法分析
(4)将测试用的表达式事先放在文本文件中，一行存放一个表达式，以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；
3.备注：
1. 在“所用产生式”一列中，
如果对应有推导，则写出所用产生式；如果为匹配终结符，则写明匹配的终结符；
如分析异常出错则，写为“分析出错”；如成功结束则写为“分析成功”。 4.文法分析表
表1
E G T S F
i E->TG T->FS F->i + G->+TG S->ε * S->*FS ( E->TG T->FS F->(E) ) - / # G->ε G->ε G->-TG S->ε S->ε S->/FS S->ε 2. 对一个新的文法实现LL(1)分析
2.1利用上次作业中的新闻法进行改善，文法如下
S->aH H->aMd H->d M->Ab M->ε A->aM A->ε
（1）程序代码：WDM.cpp的文件 （2）输入: 一个以 # 结束的符号串：
例如： aaabd# （3）输出： 步骤：
第一步，首先判断是否有非法字符，如有则提示“输入非法字符”，若无则进行字符串分析；
第二步，将# S 进分析栈 即分析从S开始，S为开始符，首先使用产生式S->aH，分析串a,分析字符为a,剩余字符串aabd#，
第三步，分析第二个字符a,对S->aH中的非终结符H进行分析,使用H->aMd， 反序将符号一一推进栈中，字符a匹配成功，剩余字符串abd#； 第四步，使用产生式M->Ab,以‘bA’s顺序进栈，剩余字符串abd#;
第五步，对非终结符A分析，再将产生式A->aM,进栈同时将A推出栈；第三个a匹配成功，剩余串bd#;
第六步，使用产生式M->ε,此时什么都不用进栈；剩余串bd#; 第七步，栈内剩余两个终结符，最后以#结束； 第八步，分析到栈底，代表分析成功最后以#结束。 （4）分析表M:
产生式S->aH，H->aMd，M->Ab, A->aM不能推出空，所以select集
Select(S->aH)=first(aH)={a} Select(H->aMd)=first(aMd)={a} Select(M->Ab)=first(Ab)={a, ε} Select(A->aM)=first(aM)={a, ε}
产生式M->ε，A->ε能推出空，所以select集
Select(M->ε)=(first(ε)-{ ε})∪follow(M)={ b,d,#}
Select(A->ε)= (first(ε)-{ ε})∪follow(A)={b,#}
S H M A a S->aH H->aMd M->Ab A-
步骤 1 2 3 4 5 6 7 8 9 10 11 分析栈 #S #Ha #H #dMa #dM #dbA #dbMa #dbM #db #d # 剩余输入串 aaabd# aaabd# aabd# aabd# abd# abd# abd# bd# bd# d# # 推导用产生式或是匹配 S->aH a匹配! H->aMd a匹配! M->Ab A->aM a匹配! M->^ b匹配! d匹配! 分析成功
四．心得体会
通过这次试验，我们对LL(1)有了更深的理解，更加理解LL(1)文法的分析过程及实现方法。学会了设计，编制，调试语法及语义分析程序，对程序进行改善处理以达到更好的实现效果。当然，时间原因，还有好多东西没有学习到，在以后的学习过程中，就要多查资料，多问老师或同学，提高自己的能力。