1、 编译原理课程设计报告编译原理课程设计报告 选题名称选题名称: LL（1）文法分析 院（系）院（系）: 计 算 机 工 程 学院 专专 业业: 计算机科学与技术 摘要：选题要求：根据某一文法编制调试 LL(1) 文法语法分分析程序，以便对任意输 入的符号串进行分析。 本次课程设计的目的主要是加深对预测分析 LL(1)文法语法分析 法的理解。具体如下：1、对语法规则有明确的定义；2、编写的分析程序能够对给定 文法进行正确的语法分析； 3、 对输入给定的文法， 手工计算FIRST、 FOLLOW集合和select 集合， 应能判断识别是否为给定文法的句子， 并给出推导过程。 4、 对输入给定的文法
2、， 由程序自动构造 FIRST、FOLLOW 集合。5、对于遇到的语法错误，能够做出简单的错误 处理，给出简单的错误提示，保证顺利完成语法分析过程。 关键词：语法分析；FIRST 集合；FOLLOW 集合；分析表 一、设计内容及要求 (1) 基于 PL/0 语言，通过编程判断该文法是否为 LL(1)文法； (2)计算出文法的 First() Follow() (3)构造相应文法的预测分析表 (4)对某个输入句子进行语法分析 二、实现原理 1LL(1)文法 LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。 就是要求描述语言的文法是无左递 归的和无回溯的。根据 LL(1)文法的定义，对于
3、同一非终结符 A 的任意两个产生式 A:=a 和 A:=b，都 要满足：SELECT(A：=a )SELECT(A:=b)=。 （1）文法的左递归 当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。所以采用 自顶向下语法分析需要消除文法的左递归性。 文法的左递归是指若文法中对任一非终结符 A 有推导 AA，则称该文法是左递归的。 左递归又可以分为直接左递归和间接左递归。 直接左递归 若文法中的某一产生式形如 AA，V*，则称该文法是直接左递归的。 消除直接左递归的方法： 设有产生式是关于非终结符 A 的直接左递归：AA| （,V*，且不以 A 开头） 对 A 引入一个新
4、的非终结符 A，把上式改写为： A A AA| 间接左递归 若文法中存在某一非终结符 A，使得 AA至少需要两步推导，则称该文法是间接左递归的。 消除间接左递归的方法： 【方法一】采用代入法把间接左递归变成直接左递归。 【方法二】直接改写文法：设有文法 G10S： SA| AS 因为 SAS，所以 S 是一个间接递归的非终结符。为了消除这种间接左递归，将式 代入式，即可得到与原文法等价的文法（可以证明） ： SS| 式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文 法：SS SS| 2. 计算 First 集 (1) 若 XVT ，则 First(X)=X (2
5、) 若 XVN ，且有产生式 Xa, aVT则 First(X)=X (3) 若 XVN ，且有产生式 X,则 First(X)=X (4) 若 X，Y1 ，Y2 ，Yn 都VN，而由产生式 XY1 Y2 Yn 。当 Y1 ，Y2 ，Yi-1都能推 导出时， （其中 1in） ，则 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. 计算 Fo
6、llow 集 对文法中的每个 AVN，计算 Follw(A)： (1) 设 S 为文法的开始符合，把#加入 Follow(S)中； (2) 若 AB是一个产生式， 则把 First()的非空元素加入 Follow(B)中， 如果能推导出， 则把 Follow(A)也加入(B)中； (3) 反复使用以上步骤直到每个非终结符号的 Follow 集不再增大为止。 4. 预测分析方法 预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成：预测分析程 序；先进后出栈；预测分析表。 预测分析程序的框图如下： 目录 1 系统分析 . 1 1.1 选题要求. 1 1.2 预期目标. 1 2.程序流程图 1 2.1 总流程图. 1 2.2FIRST集和 FOLLOW集. 2 2.3 预测分析表流程
