1、编译原理课程设计LL(1) 语法分析 课题综述 算法介绍 人员分工 程序流程目 录课题综述语法分析是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定的文法的正确句子。目前语法分析常用的方法右自顶向下分析和自底向上分析两大类。 确定的自顶向下方法，是从文法的开始符号，考虑如何根据当前的输入符号（单词）唯一的确定选用哪个产生式替换相应非终结符往下推导。 LL(1)文法是一种确定的自顶向下的分析方法。LL(1)的含义是：第一个 L表明自顶向下分析从左向右扫描输入串，第二个 L表明分析过程中将用最左推导， 1表明只需向右看一个符号便可以决定如何推导即选择哪个产生式（即规则
2、）进行推导。算法介绍1、在对输入序列进行 LL(1)文法分析之前，首先要对文法进行判别，看文法是不是 LL(1)文法。 这个文法应该满足无二义性，无左递归，无公因子 。 具体的判别过程是，求出能推出 的非终结符，求出 FIRST集，求出 FOLLOW集，求出 SELLECT集，看相同左部的产生式的 SELLECT集是否有交集，有就不是 LL（ 1）文法。2、如果输入文法不是 LL(1)文法，可以进行转换，转换一般有两种方法：提取左公因子法和消除左递归法。3、构造预测分析表，设二维矩阵 M。4、预测分析。人员分工 负责 MFC界面制作，程序总控，各个非终结符能否推出 的计算 ,判断是否 LL(1
3、),以及人员分工。 消除左递归的实现 提取公因子的实现 求 FIRST集 求 FOLLOW集 求 SELLECT集 构造预测分析表，分析输入的句子程序流程程序开始InitAndConvertPt(); /读入文法、消除左递归、提取公因子InitArray(); /初始化 N 数组VnRefresh(Pt);/构造非终结符集VtRefresh(Pt);/构造终结符集Create_N_Table(); /判断哪些非终结符可以推出空 ,存入 N FirstVt();/求 FIRST集FollowVt();/求 Follow集SelectVt();/求 Select集是不是 LL(1)输出不是 LL（
4、 1）文法NOyes构造预测分析表分析表达式界面输出提取公因子使产生式右部没有公共因子。若产生式右部有左公因子，则反复提取，直到引进的新非终结符的有关的产生式再无左公共因子为止。消除左递归左递归分为直接左递归和间接左递归。（ 1）直接左递归的处理我们利用引入新非终结符的方法来消除 左递归 ：如：U Ux|y（其中 x,y V+ ， y不以 U开头），引入一个新的非终结符 U 后，可以等价地改写成为：UyU Ux U| （ 2）间接左递归的处理对于间接左递归的消除需要通过产生式非终结符置换，将间接左递归变为直接左递归，然后按直接左递归消除。终结符推出 的计算分为三步：1、将数组 N中对应每一非终结符的标记置初值为 “未定 ”2、扫描文法中的产生式。1）删除所有右部含有终结符的产生式，若这使得以某一非终结符为左部的所有产生式都被删除，则将数组中对应该非终结符的标记值改为 “否 ”，说明该非终结符不能推出 。2）若某一非终结符的某一产生式右部为 ，则将数组中对应该非终结符的标志置为 “是 ”，并从文法中删除该非终结符的所有产生式。
