课程设计任务书学生姓名：辛波专业班级：计算机0707班指导教师：彭德巍工作单位：计算机科学与技术学院题目: FOR循环语句的翻译程序设计（递归下降法、输出四元式）初始条件：理论：学完编译课程，掌握一种计算机高级语言的使用。

实践：计算机实验室提供计算机及软件环境。

如果自己有计算机可以在其上进行设计。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1）写出符合给定的语法分析方法的文法及属性文法。

（2）完成题目要求的中间代码四元式的描述。

（3）写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。

（4）编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。

（5）设计报告格式按附件要求书写。

课程设计报告书正文的内容应包括：1 系统描述（问题域描述）；2 文法及属性文法的描述；3 语法分析方法描述及语法分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码）；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等）；9 参考文献（按公开发表的规范书写）。

时间安排：设计安排一周：周1、周2：完成系统分析及设计。

周3、周4：完成程序调试及测试。

周5：撰写课程设计报告。

设计验收安排：设计周的星期五第1节课开始到实验室进行上机验收。

设计报告书收取时间：设计周的次周星期一上午10点。

指导教师签名： 2010年 01月 08日系主任（或责任教师）签名： 2010年 01月 08日FOR循环语句的翻译程序设计----递归下降法、输出四元式1 系统描述1．1目的通过设计、编制、调试一个FOR循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词法检查和分析。

1．2设计内容及步骤对循环语句： FOR（表达式1；表达式2；表达式3） {赋值语句}(1)写出递归下降语法分析方法要求的文法和属性文法描述。

(2)描述递归下降语法分析方法的思想。

(3)给出中间代码序列的结构设计。

(4)完成相应的词法分析、语法分析和语义分析程序设计。

1．2．1 词法分析将词法分析程序设计成一个子程序，每当语法分析程序需要一个单词时，则调用该子程序。

词法分析程序每调用一次，便从源程序文件中读入一些字符，直到识别出一个单词。

1．2．2 语法分析采用递归下降方法，为对应文法中的每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串。

若输入串是给定文法的句子，则从文法的开始符号出发一定能推导出与输入的单词串完全相同的句子。

1．2．3 语义分析在语法分析的同时可由语法分析程序调用相应的语义子程序进行语义处理，完成附加在所使用的产生式上的语义规则描述，并生成四元式的中间代码形式。

1．2．4 测试用例和测试结果设计不同的测试用例以显示程序的各种功能，包括简单的for循环和for循环的嵌套。

并记录测试结果。

2 文法及属性文法的描述2．1文法描述本系统中所使用FOR循环语句的文法包括FOR语句本身，赋值表达式和布尔表达式。

具体文法产生式如下：2．1．1 FOR语句相关的产生式：1)S->for(W)Sx 2)W->A;W13)W1->B;W2 4)W2->A5)Sx->Ax 6)Sx->{Am}7)Am->AmAx 8)Am->Ax2．1．2 布尔表达式：9）B->B||L 10)B->L11)L->L&&M 12)L->M13)M->!M 14)M->K15)K->(B) 16)K->false17)K->true 18)K->id19)K->idScid 20)Sc-> !=21)Sc-> == 22)Sc-> <=23)Sc-> >= 24)Sc-> <25)Sc-> >2．1．3 赋值表达式：26)Ax->A; 27)A->id=E28)E->E+T 29)E->E-T30)E->T 31)T->T*F32)T->T/F 33)T->F34)F->id 35)F->(E)36)F->num2．2属性文法的描述3 语法分析方法描述及语法分析表设计3．1语法分析方法描述递归下降分析方法是一种自顶向下语法分析方法，其目的是从文法的开始符号开始，根据输入字符串进行最左推导，试图推导出给定的字符串。

或者说，从根节点（文法开始符号）开始，自上而下，从左到右地为输入字符串建立一棵语法树，并以预先确定的顺序创建语法树的节点。

递归下降分析法可能需要回溯，即需要重复地扫描输入。

递归子程序法的实现思想是对应每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，能够按照LL（1）形式唯一地确定选择某个候选式进行推导，因此首先要消除左递归。

其文法及属性文法如图1和图2所示。

由于递归下降法对每个过程可能存在直接或间接的递归调用，所以对某个过程在退出之前可能又要被调用，因此有些信息需要保留，通常在入口时需保留某些信息，出口时需恢复。

由于递归过程是遵循先进后出规律，通常开辟栈来处理。

3．2操作符优先级在对for循环语句进行翻译时，涉及到对赋值表达式和布尔表达式语句的翻译。

在文法的描述中给出了算术运算符、关系运算符和逻辑运算符之间的优先级关系，其结合性由下表所示：图3操作符优先级4 给出中间代码形式的描述及中间代码序列的结构设计4．1中间代码形式的描述常见的中间代码形式有逆波兰记号，三元式，四元式和树形表示。

本课程设计输出的中间代码的表示方法是四元式。

它是带有四个域的记录结构，这四个域分别称为算符op，第一运算对象arg1，第二运算对象arg2及结果result。

域op包含一个代表运算符的内部码。

例如x = y op z的四元式表示为（op,y,z,x）,即将y置于arg1域，z置于arg2域，x置于result域，= 置于算符域op，如果op是单目运算符，例如非‘！’( x = !y )的四元式表示形式中不用填arg2。

通常，四元式中的arg1，arg2和result的内容都是一个指针，此指针指向有关名字的符号表入口。

这样，临时变量名也要填入符号表中。

4．2中间代码序列的结构设计型如for[ parse1;parse2;parse3]{list}的中间代码序列的结构设计如下：图4中间代码序列结构设计5 简要的分析和概要设计5．1简要的分析本程序采用递归下降的方法实现FOR循环语句的翻译，并以四元式的中间代码形式输出。

经过词法分析，语法分析，同时执行语法制导翻译将中间结果表达出来，然后通过一个函数转化成要求的四元式结构的中间代码。

上述的这个过程在一遍扫描过程中完成：在语法分析的过程中调用词法分析来不断的分解出下一个句柄；在用递归下降方法进行语法分析的同时进行中间形式数据的保存，在分析出操作符号的同时结合当前栈中的数据输出四元式。

程序中各阶段的功能如下：（1）词法分析阶段对源程序流进行扫描，每识别出一个单词，若是标识符，则到符号表中查找，如果符号表中没有此标识符的记录，那么将此标识符插入符号表。

最后按照单词其所属的类别，把类标识返回，作为语法分析阶段的输入。

（2）语法及语义分析阶段由文法开始符号对应的子程序控制 for循环语句各个模块的执行顺序，并由文法开始符号对应的子程序递归调用其他的子程序，对各个模块采用自顶向下，自左至右的推导方法完成对输入字符进行匹配的工作，试图推导出与输入符号串一致的文法的句子。

（3）中间代码生成阶段控制代码的输出形式，以四元式形式输出中间代码5．2概要设计5．2．1数据结构本程序使用符号表以及数组来存储长短不一的标识符。

将标识符的字符串放入一个单独的数组lexemes,每个字符串用一个字符串终结符EOS（\0）结束。

符号表采用结构体数组symtable来表示，每一个表项有两个域的记录：第一个域是指向数组lexemes中字符串的开始位置的指针域，另一个域是用来存放标识符记号的token域。

数组symtablelexptr token存储字符串的数组lexemes图5 符号表和存储字符串的数组定义符号表的数据结构如下：struct entry{char *lexptr; /*符号表的指针域*/int token; /*符号表的标识域*/};struct quadruples{int qt; /*保存将要输出的单词的标识*/int qtval; /*保存将要输出的单词的值*/};/*为符号表分配一个存储空间*/struct entry symtable[999];/*保存将要输出的四元式信息*/struct quadruples quadtable[38];5．2．2符号表初始化本程序要完成对FOR循环语句的翻译，所以首先要将for作为关键字插入到符号表中：struct entry keywords[] = {"for", KEY,0, 0};因此在遇到for这样的关键字时，函数直接返回关键字的标识号KEY，则程序不会把它们当作标识符插入到结构体数组中，而是将他们完整地归类到关键字集合中。

且这种设计很利于程序的扩展。

5．2．3多元操作符的处理在程序中使用到了‘!=’,‘||’,‘==’这样的多元操作符,由于不能像一元操作符一样直接匹配，所以通过C语言中进行#define预处理，如NE代表‘!=’,并在头文件中将这些多元操作符与整数之间建立映射关系，且存放在二维数组中。

若词法分析返回的标识号为相应的宏定义的变量，则在语法分析阶段switch-case语句中直接通过对相对位置的计算得到多元操作符在数组中的存储位置，从而得到相应的操作符。

通过这样的设计，使得在编写代码时要简单的多。

6 详细的算法描述6．1词法分析的数据结构设计与详细的流程图6.1.1初始化部分介绍在程序正确执行前要完成如下的初始化工作：1）完成语法分析所要查找的关键字和各种标识符编号的图的初始化。

2）读入源文件，对源文件进行初步的处理。

3）对源文件的正确读入进行判断，读入错误则进行报错。

4）初始化各种全局变量。

6.1.2数据结构的设计6.1.2.1 string Word[WordNum]存储所有的单词（标识符，关键字，运算符，界限符，数字（整型，实型）），WordNum为单词个数。

6.1.2.2map<string,int> WordMap存储所有单词和相应的类型码的map，用于识别单词类型时候方便查找，如能在表中找到，则能识别，如找不到，则报错处理。