编译原理LL(一)语法分析实验报告要点.docx

学号20102798专业 软件工程姓名 薛建东实验日期2013.04.08教师签字成绩实 验 报 告【实验名称 】 LL（1）语法分析【实验目的 】通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系使了解语法分析的功能， 掌握语法分析程序设计的原理和构造方法， 训练掌握开发应用程序的基本方法实验内容 】根据某一文法编制调试 LL （ 1 ）分析程序，以便对任意输入的符号串进行分析构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序分析法的功能是利用 LL （ 1）控制程序根据显示栈栈顶内容、向前看符号以及 LL（ 1）分析表，对输入符号串自上而下的分析过程 设计思想 】（ 1）、LL（ 1）文法的定义LL(1) 分析法属于确定的自顶向下分析方法 LL(1) 的含义是： 第一个 L 表明自顶向下分析是从左向右扫描输入串，第 2 个 L 表明分析过程中将使用最左推导， 1 表明只需向右看一个符号便可决定如何推导，即选择哪个产生式 ( 规则 ) 进行推导LL(1) 文法的判别需要依次计算 FIRST 集、FOLLOW集和 SELLECT集 , 然后判断是否为 LL(1)文法 , 最后再进行句子分析。

需要预测分析器对所给句型进行识别即在 LL(1) 分析法中，每当在符号栈的栈顶出现非终极符时， 要预测用哪个产生式的右部去替换该非终极符； 当出现终结符时， 判断其与剩余输入串的第一个字符是否匹配，如果匹配，则继续分析，否则报错 LL(1) 分析方法要求文法满足如下条件： 对于任一非终极符 A 的两个不同产生式 A ,A ，都要满足下面条件：SELECT(A ) ∩ SELECT(A )=（ 2）、预测分析表构造LL(1) 分析表的作用是对当前非终极符和输入符号确定应该选择用哪个产生式进行推导它的行对应文法的非终极符，列对应终极符， 表中的值有两种：一是产生式的右部的字符串，一是 null 若用 M表示 LL(1) 分析表，则 M可表示如下：M: VN× VT P∪ {Error}M(A, t) = A α，当 t select(A α ) ，否则M(A, t) = Error其中 P 表示所有产生式的集合 3）、语法分析程序构造LL(1) 分析中 X 为符号栈栈顶元素， a 为输入流当前字符， E 为给定测试数据的开始符号，#为句子括号即输入串的括号 分析表用一个二位数组 M表示，数组元素 M[A，a] 中的下标 A表示非终结符， a 为终结符或句子括号 ‘ #’，二维数组中存放的是一条关于 A 的产生式， 表明当非终结符 A 向下推导时， 面临输入符 a 时，所采用的候选产生式， 当元素内容无产生式时，则表明用 A 的左部向下推导时出现了不该出现的符号，因此元素内容转向出错处理的信息。

LL(1) 分析过程主要包括以下四个动作：替换：当 X VN时选相应产生式的右部 去替换 X此时 X 出栈， 逆序入栈匹配：当 X VT时它与 a 进行匹配，其结果可能成功，也可能失败，如果成功则符号栈中将 X 退栈并将输入流指针向前移动一位，否则报错接受：当格局为（ #，空 #）时报告分析成功报错：出错后，停止分析并给出相应的错误提示信息实验要求】1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等2、如果遇到错误的表达式，应输出错误提示信息流程图】1. 总体思路分析及流程图给定一个正规文法 G，在 LL(1) 预测分析中， 必须先求出 First 集和 Follow 集，然后求出 Select 集，通过 Select 集判断是否是 LL1 文法，如果是的话，构造预测分析表 求出预测分析表之后，再输入一个字符串，依据 LL1 分析表单步输出字符串的分析过程1读取正规文法求文法的 First 集 求文法的 Follow 集求文法的 Select 集键盘输入字符串 字符串分析功能模块分解图（1）主程序流程图2开始输入文法判断文法是否为LL(1) 文法Y构造预测分析表输入要分析的符号串出错处理N判断该符号串是否可被该文法识别Y提示 i*i+i# 为可接受的字符串结束（ 2）核心算法流程图N出错处理1. 计算非终结符的 First 集的算法及流程：First 集合的构造算法：（ 1）若 X∈ VT，则 First （ X） ={X} 。

2）若 X∈ VN，且有产生式 X→ a⋯⋯，则把 a 加入到 First (X) 中；若 X→ ε 也是一条产生式，则把 ε 也加到 First (X) 中 3）若 X→ Y⋯⋯是一个产生式且 Y∈VN，则把 First (Y) 中的所有非 ε - 元素都加到First (X) 中；若 X→ Y1Y2⋯Yk 是一个产生式， Y1，⋯， Yi-1 都是非终结符，而且，对于任何 j ， 1≤ j ≤ i-1 ， First (Yj) 都含有 ε （即 Y1⋯ Yi-1* ε），则把 First (Yj) 中的所有非ε- 元素都加到 First (X) 中；特别是，若所有的 First (Yj) 均含有 ε ， j=1,2, ⋯， k，则把ε加到 First (X) 中连续使用上面的规则，直至每个集合 First 不再增大为止3开始读取一个非终结符 V遍历所有产生式，查找左部是 V的产生式添加一个删除取出得到的一空的标志为条产生式trueV* 是不是有推导规产生式右部第一个符则 V*-> 空号 V* 是终结符？将该终结符 V*加入 V 的 First 集中空标志为真删除空，得到V 的 First 集剩有非终结符？结束2. 计算非终结符的 Follow 集：Follow 集合的具体构造算法如下：（ 1）对于文法的开始符号 S，置 #于 Follow(S) 中；（ 2）若 A→ α Bβ 是一个产生式，则把 First( β )|{ ε } 加至 Follow(B) 中；（ 3）若 A→ α B 是一个产生式， 或 A→ αBβ 是一个产生式而 β ε（即 ε∈ First( β ) ），则把 Follow(A) 加至 Follow(B) 中。

连续使用上面的规则，直至每个集合Follow 不再增大为止4开始取得一个非终结符V查找产生式的右部含有 V 的产生式YV 后一个字符 V* 是V 是不是最后一个字符 N否为终结符Y添加 #到V 的 FollowY Y集中N是否遍历完所有右添加 V* 到V 的 Follow 中部含有 V 的产生式Y将V* 的First 集加入到 V 的Follow 集中是否有未求解过的N完成非终结符3. 预测分析控制程序的算法流程5输入要分析的字符串Y判断字符串是否正确N‘ #’’ E’进栈，当前终结符号送入 a若产生式为A→ A1A2⋯ An, 按逆序即 显示分析步骤[An ⋯ A2A1]入栈显示栈中内容N Y显示剩余输入串接受产生式右部为空？A∈ Vt?YYNA=‘#’？Y匹配字符串？NN显示产生式N产生式不存Y出错在？Y出错读入下一符号YA=‘ a’？N【源代码】#include#include#include6#includechar A[20];/* 分析栈 */char B[。