一、实验目的首先能让用户输入一个文法,然后让计算机自动判断是否是一个LL(1)文法,通过实验教学,加深学生对所学的关于编译的理论知识的理解,增强学生对所学知识的综合应用能力,并通过实践达到对所学的知识进行验证。二、实验环境供Windows系统的PC机,可用C++/C#/Java等编程工具编写三、实验内容1、让计算机接受一个文法,示例如:G[S]为:S→ABS→bCA→εA→bB→εB→aDC→ADC→bD→aSD→c1.2、编程实现对上述文法是否是LL(1)文法的判断,是则给出肯定回答,否则给出否定回答。2.判别是否是LL(1)文法实验
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
图如下:以链表或数组等数据结构保存文法.求出能推出ε的非终结符.计算FIRST集,FOLLOW集和SELECT集是SELECT(A→α)∩S输出肯定ELECT(A→β)=Φ?回答否输出否定回答四、概要设计(1)、LL(1)文法的定义LL(1)
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
法属于确定的自顶向下分析
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
。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退栈并将输入流指针向前移动一位,否则报错。接受:当格局为(#,空#)时
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
分析成功。报错:出错后,停止分析。并给出相应的错误提示信息。五、详细设计【
流程图
破产流程图 免费下载数据库流程图下载数据库流程图下载研究框架流程图下载流程图下载word
】1.总体思路分析及流程图给定一个正规文法G,在LL(1)预测分析中,必须先求出First集和Follow集,然后求出Select集,通过Select集判断是否是LL1文法,如果是的话,构造预测分析表。求出预测分析表之后,再输入一个字符串,依据LL1分析表单步输出字符串的分析过程。读取正规文法求文法的First集求文法的Follow集求文法的Select集键盘输入字符串字符串分析功能模块分解图(1)主程序流程图开始输入文法判断文法是否为LL(1)文法YN构造预测分析表输入要分析的符号串出错处理 出错处理N 判断该符号串是否可被该文法识别Y提示i*i+i#为可接受的字符串结束(2)核心算法流程图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不再增大为止。开始读取一个非终结符V遍历所有产生式,查找左部是V的产生式 添加一个删除空的标志为true 取出得到的一条产生式 V*是不是有推导规则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不再增大为止。开始取得一个非终结符V查找产生式的右部含有V的产生式Y V是不是最后一个字符N V后一个字符V*是否为终结符Y Y 添加#到V的Follow集中YN 是否遍历完所有右部含有V的产生式 添加V*到V的Follow中Y将V*的First集加入到V的Follow集中 是否有未求解过的非终结符 N完成六、结果分析七、实验感想本次实验用C语言操作判断LL1型文法,判断LL1型文法实验最主要的地方在于需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。由于代码的精确性造成了前几次操作结果的误差,不过在分析之后,对代码内的冗余进行了删除,纠正了实验结果。本次实验收货颇多。