3.编译课程设计报告模版.doc

课程设计报告 ( 2015--2016年度第一学期) 名 称： 编译技术课程设计 题 目： 符号串的最左推导和最右推导 院 系： 控制与计算机工程 班 级： 信安1302 学 号： 1131290221 学生姓名： 王啸松 指导教师： 徐欢 设计周数： 一周 成 绩： 日期：2016年 1 月1日 1.1 课程设计目的 本次设计的时间为1周，目的是通过使用高级语言实现部分算法加强对编译技术和理论的理解。设计的题目要求具有一定的规模，应涵盖本课程内容和实际应用相关的主要技术。 1.2 课程设计的要求 （1）理解和掌握LL(1)语法分析方法的基本原理；根据给出的LL(1)文法，掌握LL(1)分析表的构造及分析过程的实现。 （2）掌握预测分析程序如何使用分析表和栈联合控制实现LL(1)分析。 2 系统描述 　 选择实习环境为486以上CPU,4M内存,TURBO C2.0语言. 实现程序见附录. 具体的实现要求： （1）对输入文法，它能判断是否为LL(1)文法，若是，则转（2）；否则报错并终止； （2）输入已知文法，由程序自动生成它的LL(1)分析表； （3）对于给定的输入串，应能判断识别该串是否为给定文法的句型。 2.1 文法的描述 分析对象对象定义如下： 算术表达式　(　项　｜　算术表达式　+　项　｜ 　算术表达式　－　项 项　(　因式　｜　项　*　因式　｜ 项　／　因式 因式　(　变量　｜　（算术表达式） 变量　(　字母 字母　(　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 2.2 属性文法的描述 属性文法(也称属性翻译文法)是Knuth在1968年首先提出的。 3 概要设计 3.1概要设计 词法分析是编译过程中的第一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用 单词的分类（五类）： 1. 关键字：由程序语言定义的具有固定意义的标识符。也称为保留字或基本字。 2. 标识符：用来表示程序中各种名字的字符串。 3. 常 数：常数的类型一般有整型、实型、布尔型、文字型。 4. 运算符：如+、－ 、*、/ 等。 5. 界限符：如逗号、分号、括号等。 语法分析部分我们我们采用ｌｌ（１）方法实现，采用ｌｌ（１）方法实现语法发分析要求文法满足以下要求： 一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关，当有右部能=*=ε时则与其左部非终结符的后跟符号集合也有关，此外在产生式中不存在左递归即经过压缩，无左递归，无回溯。它的基本思想是从左到右扫描源程序，同时从识别符号开始生成句子的最左推导，并只向前查看一个输入符号，便能唯一确定应选择的规则。 下面将确切地定义满足确定的自顶向下分析条件的文法即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+｝