编译原理课程设计报告2.doc

编译原理课程设计报告 分析 通过设计，编制，调试一个语法及语义分析程序，加深对语法及语义分析原理的理解。 IF 〈布尔表达式〉 THEN 〈赋值语句〉 ELSE 〈赋值语句〉 其中 （1）、可以选择递归下降法、LL（1）、算符优先分析法、LR法完成以上任务，中间代码选用四元式。 （2）、 写出符合分析方法要求的文法，给出分析方法的思想，完成分析程序设计。 （3）、 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。 算法设计 程序要求有三部分组成，即词法分析、语法分析、以及语义分析。其中词法分析部分要求完成对输入程序的关键字、标识符、常数、运算符进行识别；并分析词法分析的结果，检查程序输入的关键字是否为符合设计文法的关键字，检查标志符是否是合法标志符，识别运算符的种类。语法分析部分主要是以算符优先文法的设计思想和步骤完成对词法分析结果的的语法分析工作，判断输入的程序是否符合设计的IF-THEN-ELSE文法。在语法分析通过的基础上进行语义分析，其主要任务是完成对语法分析后的程序的语义分析，根据语法制导翻译去翻译输入的程序，从而得到程序的中间代码表示形式——四元式。 词法分析、语法分析和语义分析的流程图如下： 词法分析 A 词法分析器的功能和输出形式 输入：所给文法的源程序字符串 输出：二元组（单词种别,单词符号的属性值）构成的序列 B. 待分析的简单语言的词法 因为是模拟简单编译器, 所以就以C语言的小型子集作为模拟编译器的词法. 模拟程序语言的单词符号可分为下列五种; 关键字: { (相当于Pascal语言中的begin) , if ,else , while , }(相当于Pascal语言中的end ) 所有的关键字都是小写字母 . 运算符: + , - , * , / , = , , = , == , , = , , ,|| , ! 界 符: 逗号 ,分号 ,左圆括号 , 右圆括号 , # 常 数: 在这里只涉及到int型常量 其他单词是标识符（ID）和整形常数（NUM），通过以下正规式定义： ID = letter（letter|digit）* NUM = digit digit * 空格由空白，制表符和换行符组成，空格一般用来分隔ID，NUM，运算符，界符和关键字，词法分析阶段通常会被过滤掉。 C.词法分析的设计思想: 算法的基本任务是从字符串表示的源程序中识别出其具有独立意义的单词符号, 其基本思想是根据扫描到的单词符号的第一个字符的种类, 拼出相应的单词符号。 （2）语法分析 语法分析要处理的输入是词法分析的输出即单词序列。该部分主要用到两个栈，一个用来保存单词标志号的状态栈另一是用来保存单词本身信息的符号栈。程序从词法分析输出的单词序列中读取一个单词，检查单词是否是合法单词，如果是合法的，则取符号栈的栈顶元素，和当前单词的标志号进行优先级比较，如果小于当前单词的优先级那么将当前单词压入符号栈，将其标志号压入状态栈；如果大于当前单词的优先级那么继续弹出状态栈的元素，和上一个符号栈弹出的元素进行比较，如果两优先级相等则继续弹，如果小于上一次弹出的元素的优先级，则弹的所有元素按先后弹的倒置顺序排列为一个句柄，查找产生式找到相应的产生式进行规约，把规约或的元素当多当前一的元素继续进行比较，直到词法分析输出结果全部遍历完。在规约的过程中记下规约的次数，和每次规约的元素，以便语义分析和中间代码生成。 （3） 语义分析 语义分析主要是将语义分析结果转化成三地址码表示的中间代码的过程。 在语法分析的过程中，在每次规约的过程中记录规约的类型和各个类型规约的次数。即当规约的语句是布尔表达式时每规约一次都将规约的语句转化成三地址码的形式保存在字符串E中并记录E中规约产生式的次数在m1.quad中；如果规约的产生式是第一个赋值语句块中的赋值语句，则将规约的产生式以三地址形式保存在字符串B1中并记录B1中规约产生式的次数在m2.quad中；如果规约的产生式是第二个赋值语句块中的赋值语句，则将规约的产生式以三地址形式保存在字符串B2中并记录B2中规约产生式的次数在 m3.quad中。最后控制将B1、B2和E中的内容输入。 LL（1）文法 LL(1)文法分析流程图： 构造不带回溯的自上而下分析的文法条件 1. 文法不含左递归， 2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若 A→a 1|a 2|…|a n 则 FIRST(a i)∩FIRST(a j)＝f (i1j) 3. 对文法中的每个非终结符A，若它存在某个候选首符集包含e，则 FIRST(A)∩FOLLO