编译原理课程设计报告LL1分析过程模拟.doc

　 课程设计(论文)任务书　　　　　　(论文)题目　LL(1)分析过程模拟　 　　　 二、课程设计(论文)工作自 2010 年 6 月 22 日起至 2010 年 6 月 28 日止。　　 (论文) 地点: 　　　(论文)内容要求：　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　　　　　(论文)评审意见　　 （1）完成原理分析（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）； 　　 （2）设计分析　　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）； 　 （3）完成调试　　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）；　 （4）翻译能力　　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）；　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　 　 需求分析　 问题理解　 用数据库存储多行文法，用LIST控件显示算法，用GRID类依据算法进行作图。并实现算法与生成过程的关联。　　　　　　其实要知道一串符号是不是该文法的一个句子，只要判断是否能从文法的开始符号出发推导出这个输入串。语法分析可以分为两类，一类是自上而下的分析法，一类是自下而上的分析法。自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上而下的过程。　　　　　　在自上而下的分析法中，主要是研究LL(1)分析法。它的解决步骤是首先接收到用户输入的一个文法，对文法进行检测和处理，消除左递归，得到LL(1)文法，这个文法应该满足：无二义性，无左递归，无左公因子。当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈。　 FIRSTFIRST集使用以下四个步骤判定：　　　(1)若X∈VT?,则FIRST(X)={X}　 (2)若X∈VN,且有产生式X→a…，a∈VT 则把a加入到FIRST(X)中，即a∈FIRST(X)　 (3)若X∈VN,且有产生式X→$则把$也加到FIRST(X)中，即$∈FIRST(X)　　 (4)若X∈VN, Y1，Y2，…，Yi 都∈VN，且有产生式X→Y1Y2…Yn。当Y1，..Yi-1=$ (1≤i≤n)则FIRST(Y1)-{$}，…，FIRST(Yi-1)-{$}，FIRST(Yi)都包含在FIRST(X)中，即：　　　 FIRST(Yi-1)-{$} ∈FIRST(X)　 所有Y1,…Yn *= $ ，则把$加到FIRST(X)中, FIRST(Yi) ∈FIRST(X)　　　 FOLLOW　　　FOLLOW集使用以下个步骤判定：　 (1)如果 X 是开始符 那么把 # 加入到 FOLLOW(X)　 (2)若Ａ=αBβ是一个产生式,则把FIRST(β)－{$}加至FOLLOW(B)中　　　 (3)若Ａ=αB是一个产生式，或Ａ=αBβ是一个产生式而β*=$(即$FIRST(β)），则把 FOLLOW(A)加至FOLLOW(B)中　 FOLLOWFIRST集类似，但有不同的地方。FOLLOW集需要扫描每一个产生式。而FIRST集扫描的是产生式左部不同的产生式，然后扫描左部相同的产生式的每一个右部。FOLLOW集第一次扫描可以确定哪些FIRST集或FOLLOW集属于所求的FOLLOW集，由于FIRST集已经求出，所以第一次扫描就可以把相应的FIRST集加入到FOLLOW集中，设置FOLLOW集完成标记位，设置队列，把未完成的非终结符送入队列，依次取出队列元素，把求出FOLLOW集的非终结符的FOLLOW集加入到相应的FOLLOW集中，把未求出的送回队列。　　 FIRST集一样的方法处理就可以。　　 SELLECT集的确定　　　FIRST集＆FOLLOW集都已经求出来后SELLECT集就很好求了，扫描每一个产生式，使用以下三个步骤确定：　　 A→α A∈VN，α∈V*，　 (1)若α是终结符，那么SELLECT(A→α)={α}　 (2)若α是$，则SELECT(A→α)=FOLLOW(A)　　　(3)若α是非终结符那么　 若α*=$，则SELECT(A→α)=(FIRST(α)-$)∪FO