编译原理课程设计(语法分析程序).doc

编译原理实验报告
题目:对下面的文法对象,使用c语言构造它的预测分析程序;并任意给一算术表达式进行分析测试.
分析对象对象定义如下:
算术表达式è 项| 算术表达式+ 项| 算术表达式- 项
项è 因式| 项* 因式| 项/ 因式
因式è 变量| (算术表达式)
变量è 字母
字母è A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
实验日期:2005-6-15至2005-6-30 指导教师: 吴取劲
班级:计算机029班学号:20029440913 姓名:陈强
一、分析

语法分析部分我们我们采用ll(1)方法实现,采用ll(1)方法实现语法发分析要求文法满足以下要求:
一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关,当有右部能=*=>ε时则与其左部非终结符的后跟符号集合也有关,此外在产生式中不存在左递归即经过压缩,无左递归,无回溯。它的基本思想是从左到右扫描源程序,同时从识别符号开始生成句子的最左推导,并只向前查看一个输入符号,便能唯一确定应选择的规则。
下面将确切地定义满足确定的自顶向下分析条件的文法即LL(1)文法及LL(1)文法的判别并介绍如何对非LL(1)文法进行等价变换问题,也就是消除一个文法中的左递归和左公共因子。
注意:
一个文法中含有左递归和左公共因子绝对不是LL(1)文法,所以也就不可能用确定的自顶向下分析法,对此结论可以证明。然而,某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为LL(1)文法,但需要用LL(1)文法的定义判别,也就是说文法中不含左递归和左公共因子,只是LL(1)文法的必要条件。
LL(1) 文法的定义(5种定义):
一个文法符号串的开始符号集合定义如下:
定义1. 设G=(VT,VN,S,P)是上下文无关文法,α是任意的文法符号串,FIRST(α)是从α推导出的串的开始符号的终结符集合。。。。
FIRST(α)={a|α=*=>aβ,a∈VT,α,β∈V*}若α=*=>ε,则规定ε∈FIRST(α).
当一个文法中相同左部非终结符的右部存在能=*=>ε的情况则必须知道该非终结符的后跟符号的集合中是否含有其它右部开始符号集合的元素。为此,我们定义一个文法非终结符的后跟符号的集合如下:
    定义2. 设 G=(VT,VN,S,P)是上下文无关文法,A∈VN,S是开始符号
FOLLOW(A)={a|S=*=>μAβ,且a∈VT,a∈FIRST(β),μ∈VT* ,β∈V+}
若S=*=>μAβ,且βε, 则#∈FOLLOW(A)。也可定义为:FOLLOW(A)={a|S=*=> …Aa…,a ∈VT}
若有S=*=> …A,则规定#∈FOLLOW(A)
这里我们用'#'作为输入串的结束符,或称为句子括号,如:#输入串#。
定义3. 给定上下文无关文法的产生式A→α, A∈VN,α∈V*, 若α==>ε,则SELECT(A→α)=FIRST(α)
如果α=*=>ε,则SELECT(A→α)=FIRST(αε)∪FOLLOW(A)。FIRST(αε)表示FIRST(α)的非{ε}元素。
更进一步可以看出能够使用自顶向下分析技术必须使文法满足如下条件,我们称满足条件的文法为LL(1)文法,其定义为:
  定义4. 一个上下文无关文法是LL(1)文法的充分必要条件是:
 对每个非终结符A的两个不同产生式,A→α, A→β,满足SELECT(A→α)∩SELECT(A→β)=空,其中α,β不同时能ε.
定义5. LL(1)文法也可定义为:
一个文法G是LL(1)的,当且仅当对于G的每一个非终结符A的任何两个不同产生式 A→α|β,下面的条件成立:
① FIRST(α)∩FIRST(β)= 空,也就是α和β推导不出以某个相同的终结符a为首的符号串;它们不应该都能推出空字ε.
②假若βε那么,FIRST(α)∩ FOLLOW(A)= 空也就是,若βε则α所能推出的串的首符号不应在FOLLOW(A)中。
二、算法
该程序可分为如下几步:
(1)读入文法
(2)判断正误
(3)若无误,判断是否为LL(1)文法
(4)若是,构造分析表;
(5)由总控算法判断输入符号串是否

是LL(1)文法?
结束
报错
判断句型

为该文法的句型。
根据下面LL(1)文法,对输入串w: (i+i)*(i+i)+i*i进行LL(1)分析,要求如下:
1、先手工建立LL(1)分析表;
2、分析输入串,判断是否是语法上正确的句子,并输出整个分