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

秋风清，秋月明,落叶聚还散,寒鸦栖复惊。 编 译 原 理 实 验 报 告 题目：对下面的文法对象，使用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) 文法的定义 （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）＝ 空也就是，若βε则α所能推出 的串的首符号不应在FOLL