编译原理实验报告实验三
编译原理实验报告
题目对下面的文法对象使用c语言构造它的预测分析程序并任意给一算术表达式题目进行分析测试分析对象对象定义如下算术表达式项算术表达式项算术表达式项项因式项因式项因式因式变量算术表达式变量字母字母ABCDEFGHIJKLMNOPQRSTUVWXYZ实验日期指导教师实验日期2005615至2005630日期指导教师吴取劲班级计算机029班学号20029440913姓名陈强班级学号姓名
一分析
语法分析部分我们我们采用ll1方法实现采用ll1方法实现语法发分析要求文法满足以下要求一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关当有右部能ε时则与其左部非终结符的后跟符号集合也有关此外在产生式中不存在左递归即经过压缩无左递归无回溯它的基本思想是从左到右扫描源程序同时从识别符号开始生成句子的最左推导并只向前查看一个输入符号便能唯一确定应选择的规则下面将确切地定义满足确定的自顶向下分析条件的文法即LL1文法及LL1文法的判别并介绍如何对非LL1文法进行等价变换问题也就是消除一个文法中的左递归和左公共因子注意注意一个文法中含有左递归和左公共因子绝对不是LL1文法所以也就不可能用确定的自顶向下分析法对此结论可以证明然而某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为LL1文法但需要用LL1文法的定义判别也就是说文法中不含左递归和左公共因子只是LL1文法的必要条件LL1文法的定义5种定义一个文法符号串的开始符号集合定义如下定义1设GVTVNSP是上下文无关文法α是任意的文法符号串FIRSTα是从α推导出的串的开始符号的终结符集合FIRSTαaαaβa∈VTαβ∈V若αε则规定ε∈FIRSTα当一个文法中相同左部非终结符的右部存在能ε的情况则必须知道该非终结符的后跟符号的集合中是否含有其它右部开始符号集合的元素为此我们定义一个文法非终结符的后跟符号的集合如下定义2设GVTVNSP是上下文无关文法A∈VNS是开始符号
编译原理实验报告1
f编译原理实验报告实验三
FOLLOWAaSμAβ且a∈VTa∈FIRSTβμ∈VTβ∈V若SμAβ且βε则∈FOLLOWA也可定义为FOLLOWAaS…Aa…a∈VT若有S…A则规定∈FOLLOWA这里我们用作为输入串的结束符或称为句子括号如输入串定义3给定上下文无关文法的产生式A→αA∈VNα∈Vr