集美大学计算机工程学院编译原理课程设计报告
选题名称: LL（1）文法分析
院（系）:计算机工程学院
专业:计算机科学与技术
班级:计算1412 指导教师:付永刚
学年学期:2016 ~ 2017 学年第 2 学期
2017年06月29日
摘要：选题要求：根据某一文法编制调试LL(1) 文法语法分分析程序，以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。具体如下：1、对语法规则有明确的定义；2、编写的分析程序能够对给定文法进行正确的语法分析；3、对输入给定的文法，手工计算FIRST、FOLLOW集合和select集合，应能判断识别是否为给定文法的句子，并给出推导过程。4、对输入给定的文法，由程序自动构造FIRST、FOLLOW集合。5、对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程。
关键词：语法分析；FIRST集合；FOLLOW集合；分析表
一、设计内容及要求
(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∈V T ，则First(X)={X}
(2) 若X∈V N ，且有产生式X→a…, a∈V T则First(X)={X}
(3) 若X∈V N ，且有产生式X→ε,则First(X)={X}
(4) 若X，Y1 ，Y2 ，…，Y n 都∈V N，而由产生式X→Y1 Y2 …Y n 。当Y1 ，Y2 ，…，Y i-1都能推导出ε时，（其中1≤i≤n），则First(Y1)-{ε}, First(Y2)-{ε},…, First(Y i)都包含在First(X)中
(5)当(4)中所有Y i都能推导出ε，（i=1，2，…，n），则First(X)=First(Y1)∪First(Y2)∪…First(Y n)∪{ε}
反复使用上述步骤直到每个符合的First集合不再增大为止。
3. 计算Follow集
对文法中的每个A∈V N，计算Follw(A)：
(1) 设S为文法的开始符合，把{#}加入Follow(S)中；
(2) 若A→αBβ是一个产生式，则把First(β)的非空元素加入Follow(B)中，如果β能推导出ε，则把Follow(A)也加入(B)中；
(3) 反复使用以上步骤直到每个非终结符号的Follow集不再增大为止。
4. 预测分析方法
预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成：预测分析程序；先进后出栈；预测分析表。
预测分析程序的框图如下：
目录
1系统分析 (1)
1.1选题要求 (1)
1.2预期目标 (1)
2.程序流程图 (1)
2.1总流程图 (1)
2.2F IRST集和F OLLOW集 (2)
2.3预测分析表流程 (3)
3.代码编写 (3)
3.1检查左递归 (3)
3.2FIRST集合 (5)
3.3FOLLOW集合 (6)
3.4分析表输出 (8)
4.程序调试 (10)
5.总结 (11)
6.指导教师评语 (12)
7.源码 (13)
正文：
1.系统分析
1.1选题要求
根据某一文法编制调试LL(1) 文法语法分分析程序，以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。
1.2预期目标
构造LL(1)文法语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合（编译出错），则输出错误信息。
2.程序流程图
2．1.总流程图
