编译原理LL(1)文法课程设计报告1111111

集美大学计算机工程学院编译原理课程设计报告选题名称:LL（1）文法分析院（系）:计算机工程学院专业:计算机科学与技术班级:指导教师:付永刚学年学期:2014~2015学年第1学期2015年1月8日选题一LL（1）语法分析一、设计内容及要求(1)基于PL/0语言，通过编程判断该文法是否为LL(1)文法；(2)计算出文法的First()Follow()(3)构造相应文法的预测分析表(4)对某个输入句子进行语法分析二、实现原理1．LL(1)文法LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。就是要求描述语言的文法是无左递归的和无回溯的。根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式A:=a和A:=b，都要满足：SELECT(A：=a)∩SELECT(A:=b)=Ø。（1）文法的左递归当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。所以采用自顶向下语法分析需要消除文法的左递归性。文法的左递归是指若文法中对任一非终结符A有推导AA…，则称该文法是左递归的。左递归又可以分为直接左递归和间接左递归。●直接左递归若文法中的某一产生式形如A→Aα，α∈V*，则称该文法是直接左递归的。消除直接左递归的方法：设有产生式是关于非终结符A的直接左递归：A→Aα|β（α,β∈V*，且β不以A开头）对A引入一个新的非终结符A′，把上式改写为：A→βA′A′→αA′|ε●间接左递归若文法中存在某一非终结符A，使得AA…至少需要两步推导，则称该文法是间接左递归的。消除间接左递归的方法：【方法一】采用代入法把间接左递归变成直接左递归。【方法二】直接改写文法：设有文法G10[S]：S→Aα|β⑴A→Sγ⑵因为SAαSγα，所以S是一个间接递归的非终结符。为了消除这种间接左递归，将⑵式代入⑴式，即可得到与原文法等价的文法（可以证明）：S→Sγα|β⑶⑶式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法：S→βS′S′→γαS′|ε2.计算First集(1)若X∈VT，则First(X)={X}(2)若X∈VN，且有产生式X→a…,a∈VT则First(X)={X}(3)若X∈VN，且有产生式X→ε,则First(X)={X}(4)若X，Y1，Y2，…，Yn都∈VN，而由产生式X→Y1Y2…Yn。当Y1，Y2，…，Yi-1都能推导出ε时，（其中1≤i≤n），则First(Y1)-{ε},First(Y2)-{ε},…,First(Yi)都包含在First(X)中(5)当(4)中所有Yi都能推导出ε，（i=1，2，…，n），则First(X)=First(Y1)∪First(Y2)∪…First(Yn)∪{ε}反复使用上述步骤直到每个符合的First集合不再增大为止。3.计算Follow集对文法中的每个A∈VN，计算Follw(A)：(1)设S为文法的开始符合，把{#}加入Follow(S)中；(2)若A→αBβ是一个产生式，则把First(β)的非空元素加入Follow(B)中，如果β能推导出ε，则把Follow(A)也加入(B)中；(3)反复使用以上步骤直到每个非终结符号的Follow集不再增大为止。4.预测分析方法预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成：预测分析程序；先进后出栈；预测分析表。预测分析程序的框图如下：摘要：选题要求：根据某一文法编制调试LL(1)文法语法分分析程序，以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。具体如下：1、对语法规则有明确的定义；2、编写的分析程序能够对给定文法进行正确的语法分析；3、对输入给定的文法，手工计算FIRST、FOLLOW集合和select集合，应能判断识别是否为给定文法的句子，并给出推导过程。4、对输入给定的文法，由程序自动构造FIRST、FOLLOW集合和select集合。5、对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程。【关键词】语法分析FIRST集合FOLLOW集合分析表堆栈信息目录1系统分析---------------------------------------------错误!未定义书签。1.1选题要求--------------------------------------------------------------------61.2预期目标--------------------------------------------------------------------62系统设计---------------------------------------------错误!未定义书签。2.1程序流程图-----------------------------------------------------------------63系统实现---------------------------------------------错误!未定义书签。3.1上机编程----------------------------------------------------错误!未定义书签。3.2运行结果----------------------------------------------------错误!未定义书签。3.2.1判断LL(1)文法----------------------------------------错误!未定义书签。3.2.2找出各终结符的FIRST和FOLLOW集------------------------错误!未定义书签。3.2.3填写分析表-------------------------------------------错误!未定义书签。3.2.4堆栈信息模拟-----------------------------------------错误!未定义书签。3.2.5完成-------------------------------------------------错误!未定义书签。3.2.5程序调试-------------------------------------------------------------144总结------------------------------------------------------------------------------------------错误!未定义书签。参考文献----------------------------------------------------------------------------------------------------------30老师评语----------------------------------------------------------------------------------------------------------------正文：1.系统分析1.1选题要求根据某一文法编制调试LL(1)文法语法分分析程序，以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。1.2预期目标构造LL(1)文法语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合（编译出错），则输出错误信息。2.程序流程图总流程图开始判断是否为LL(1)文法输入文法计算该文法的First集和Follow集是提示输入文法不是LL(1)文法否根据First集和Follow集构造分析表输入句子进行自上而下的语法分析Judge流程图：开始判断文法是否有左递归输入文法否提示输入文法含有左递归,不是LL(1)文法是判断文法是否有回溯提示输入文法含有回溯,不是LL(1)文法是对该文法进行分析,计算First集和Follow集并构造分析表否First集和Follow集的流程图开始读取字符S遍历所有产生式，查找左部是S的产生式取出得到的一条产生式产生式右部第一个符号A是否是终结符？将该终结符A加入S的First集中去除重复的字符是否结束将该非终结符A读取开始读取非终结符S遍历所有产生式，查找右部分含有S的产生式取出得到的产生式S是否为产生式右部最后一个字符？添加#到S的Follow集中去除重复的字符是否结束求S后的字符串的Fisrt集合,并将该集合加入到Follow中S后的字符串是否能推出@将该产生式左部的非终结符的Follow集加入到S的Follw集中是否预测分析表流程：开始输入要分析的字符串‘#’’E’进栈，并将’#’加入到句子末尾,再将当前终结符号送入a显示分析步骤将产生式按逆序入栈读入下一符号显示栈中内容显示剩余输入串A是否是终结符产生式右部是否为空否是A是否为#?产生式是否存在？显示产生式错误处理匹配字符串？接受A和a是否相等?是是是否否是否否3.代码编写3.2.1文法检查（judge.java）importjava.util.*;publicclassJudge{publicstaticvoidRecursion(RulesgRules,Stringstr,ListCharacterleft){if(gRules.getTerminators().contains(str.charAt(0))){return;}if(left.contains(str.charAt(0))){left.add(str.charAt(0));return;}else{left.add(str.charAt(0));}if(gRules.getRules().containsKey(str.charAt(0))){for(Stringrule:gRules.getRules().get(str.charAt(0))){Recursion(gRules,rule,left);}}}publicstaticbooleanLeftRecursion(RulesgRules){ListCharacterleft=null;for(Characterch:gRules.getNonterminators()){left=newArrayListCharacter();Recursion(gRules,String.valueOf(ch),left);HashSetCharacterhashset=newHashSetCharacter(left);if(hashset.size()!=left.size()){returnfalse;}}returntrue;}publicstaticbooleancheckBack(Followfollow,RulesgRules){MapCharacter,ListStringrules=gRules.getRules();for(Characterch:gRules.getNonterminators()){ListStringruleRights=rules.get(ch);ListListCharacterallRights=newArrayListListCharacter();//同一个非终结字符的所有规则的右部可能产生的first集合for(Stringrule:ruleRights){if(rule.equals(@)){//忽略“@”ListCharacterlist=newArrayListCharacter();list.add('@');allRights.add(list);}else{allRights.add(follow.generateFirs