集美大学计算机工程学院编译原理课程设计报告
选题名称
院（系）专业班级指导教师
LL（1）文法分析
计算机工程学院计算机科学与技术
计算1412付永刚
学年学期20162017学年第2学期
2017年06月29日
f摘要：选题要求：根据某一文法编制调试LL1文法语法分分析程序，以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL1文法语法分析法的理解。具体如下：1、对语法规则有明确的定义；2、编写的分析程序能够对给定文法进行正确的语法分析；3、对输入给定的文法，手工计算FIRST、FOLLOW集合和select集合，应能判断识别是否为给定文法的句子，并给出推导过程。4、对输入给定的文法，由程序自动构造FIRST、FOLLOW集合。5、对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程。关键词：语法分析；FIRST集合；FOLLOW集合；分析表
一、设计内容及要求
1基于PL0语言，通过编程判断该文法是否为LL1文法；2计算出文法的FirstFollow3构造相应文法的预测分析表4对某个输入句子进行语法分析
二、实现原理
1．LL1文法
LL1文法是一类可以进行确定的自顶向下语法分析的文法。就是要求描述语言的文法是无左
递归的和无回溯的。根据LL1文法的定义，对于同一非终结符A的任意两个产生式Aa和Ab，
都要满足：SELECTA：a∩SELECTAb。
（1）文法的左递归
当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。所以采
用自顶向下语法分析需要消除文法的左递归性。文法的左递归是指若文法中对任一非终结符A有
推导AA…，则称该文法是左递归的。
左递归又可以分为直接左递归和间接左递归。
●直接左递归
若文法中的某一产生式形如A→Aα，α∈V，则称该文法是直接左递归的。
消除直接左递归的方法：
设有产生式是关于非终结符A的直接左递归：A→Aαβ（αβ∈V，且β不以A开头）
对A引入一个新的非终结符A′，把上式改写为：
A→βA′
A′→αA′ε
●间接左递归
若文法中存在某一非终结符A，使得AA…至少需要两步推导，则称该文法是间接左递归
的。
消除间接左递归的方法：
【方法一】采用代入法把间接左递归变成直接左递归。
【方法二】直接改写文法：设有文法G10S：
S→Aαβ⑴
A→Sγ
⑵
f因为SAαSγα，所以S是一个间接递归的非终结符。为了消除这种间接左递归，将⑵式代入⑴式，即可得到与原文法等价的文法（可以证明）：
S→Sγαβ⑶⑶式是直接r