编译原理实验报告实验三
编 译 原 理 实 验 报 告
题目：对下面的文法对象，使用 语言构造它的预测分析程序；并任意给一算术表达
式进行分析测试．
分析对象对象定义如下：
算术表达式 项 ｜ 算术表达式 项 ｜ 算术表达式 － 项
项 因式 ｜ 项 因式 ｜项 ／ 因式
因式 变量 ｜ （算术表达式）
变量 字母
字母
实验日期： 指导教师：
班级： 学号： 姓名：
一、分析
语法分析部分我们我们采用ｌｌ（１）方法实现，采用ｌｌ（１）方法实现语法发分
析要求文法满足以下要求：
一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号
集合有关，当有右部能!!"#时则与其左部非终结符的后跟符号集合也有关，此外在产生
式中不存在左递归即经过压缩，无左递归，无回溯。它的基本思想是从左到右扫描源程序，
同时从识别符号开始生成句子的最左推导，并只向前查看一个输入符号，便能唯一确定应
选择的规则。
下面将确切地定义满足确定的自顶向下分析条件的文法即$%&文法及$%&文法的判别
并介绍如何对非$%&文法进行等价变换问题，也就是消除一个文法中的左递归和左公共因
子。
注意：
一个文法中含有左递归和左公共因子绝对不是$%&文法，所以也就不可能用确定的自顶
向下分析法，对此结论可以证明。然而，某些含有左递归和左公共因子的文法在通过等价
变换把它们消除以后可能变为$%&文法，但需要用$%&文法的定义判别，也就是说文法
中不含左递归和左公共因子，只是$%&文法的必要条件。
$%&文法的定义（' 种定义）：
一个文法符号串的开始符号集合定义如下：
定义 1.设 !$，，，&是上下文无关文法() 是任意的文法符号串($)&是
从 ) 推导出的串的开始符号的终结符集合。。。。
$)&!*+)!!"+,(+∈，)(,∈-若 )!!"#(则规定 #∈$)&．
当一个文法中相同左部非终结符的右部存在能!!"# 的情况则必须知道该非终结符的后
跟符号的集合中是否含有其它右部开始符号集合的元素。为此，我们定义一个文法非终结
符的后跟符号的集合如下：
编译原理实验报告
%
