编译原理课程设计-For语句的翻译程序设计（简单优 先法、输出三地址码）

1、.武汉理工大学编译原理课内实践说明书学 号： 0121410870922课 程 设 计课 程编译原理题 目For语句的翻译程序设计（简单优先法、输出三地址码）学 院计算机科学与技术学院专 业计算机科学与技术班 级计算机1404姓 名王承禹指导教师林泓2016年12月27日;目录1 系统描述21.1设计目的21.2设计内容描述22 文法及属性文法的描述23 语法分析方法描述及语法分析表设计33.1语法分析方法描述33.2分析法操作步骤43.3优先关系矩阵54 中间代码形式的描述及中间代码序列的结构设计54.1中间代码形式55 编译系统的概要设计65.1数据结构65.2模块设计65.2.1词法分析

2、模块75.2.2语法、语义分析模块75.2.3主控模块116 详细的算法描述116.1词法分析算法116.2语法分析算法126.3语义分析算法127 软件的测试方法和测试结果138 本设计的评价、特点、149 收获与体会1410 核心代码16成绩评定表273For语句的翻译程序设计（简单优先法、输出三地址码）1 系统描述1.1设计目的 通过学习编译原理的相关内容，设计并编写FOR循环语句的翻译程序，使用简单优先法，按三地址码输出，能够实现词法分析，语法和语义的分析，加深对所学知识的理解，并且能够熟练运用到实际当中。1.2设计内容描述FOR循环语句的基本格式如下：FOR i=E step E u

3、ntil E do Stmt根据所给题目要求，设计出符合FOR循环语句的文法及属性文法的描述，语法分析方法以及三地址码的输出方式，罗列出词法分析和语法分析的流程，根据语法规则设计输入输出方法，简单优先法中的优先关系表格。设计好并且进行编译，设计若干输入输出用例（包括正确的输入和错误的输入，用来检查程序的完整性）。 2 文法及属性文法的描述根据For语句的特点，制定的产生式规则及由产生式对应的语义动作如下：F1 -> for i = E1emit(entry(i) , ' = ' , E1.place);F1.place = entry(i);/*保存控制变量在符号表中的位

4、置*/F1.chain = nextstat;emit('goto'-);/*goto OVER*/F1.codebegin = nextstat;/*保存AGAIN的地址*/F2 -> F1 step E2F2.codebegin = F1.codebegin;F2.place = F1.place;emit(F1.place '=' E2.place '+' F1.place);backatch(F1.chain,nextstat);F3 -> F2 until E3F3.codebegin = F2.codebegin;q =

5、nextstat;emit('if' F2.place, '<=' E3.place, 'goto' q+2);/*若i<=E3 转去执行循环体的第一个三地址码*/F3.chain = nextstat;emit('goto'-)/*转离循环*/S -> F3 do Stmtemit ('goto' F3.codebegin)/*goto AGAIN*/backpatch(Stmt.chain,F3.codebegin);Stmt.chain = F3.chain/*转离循环的转移目标留待外层S时

6、再回填*/3 语法分析方法描述及语法分析表设计3.1语法分析方法描述本次课内实践要求使用简单优先关系方法。简单优先分析法的基本思想史对一个文法按照一定原则求出该文法所有符号即包括终结符和非终结符之间的优先关系确定归约过程中的句柄，它的归约实际上是一种规范归约。一个文法是简单优先文法必须满足以下条件（1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立；（2）在文法中任意两个产生式没有相同的右部。三种优先关系及其判定方法如下所示：（1）X=Y 表示X和Y的优先关系相等，当且仅当G中存在产生式规则AXY；（2）X<Y表示X的优先性比Y的优先性小，当且仅当G中存在产生式规则 AXB，

7、且BY；（3）X>Y表示X的优先性比Y的优先性大，当且仅当G中存在产生式规则 ABD，且BX和DY；（4）对任何X，若文法开始符号SX，则#<X，若SX则X>#。3.2分析法操作步骤（1）由简单优先分析法的基本思想设计的如下算法，首先要构造优先关系矩阵（如3.3所示），并将文法产生式保存，设置符号数组S：（2）将输入符号串a1a2an # 依次逐个保存符号数组S中，直到遇到数组中第一个符号ai的优先性>下一个待输入符号aj为止。（3）数组当前符号ai为句柄尾，由此向左在数组中找句柄的头符号ak，即找到ak-1<ak为止。由句柄akai在文法的产生式中查找右部为ak

8、ai的产生式，若找到则用相应左部代替句柄，找不到则为出错，这是可断定输入串不是该文法的句子。重复（1）（2）（3），直到归约完输入符号串，数组中只剩文法的开始符号为止。 3.3优先关系矩阵F1F2F3fori=EstepuntildoStmt#F1=F2=F3for=i=E>>>step=until=do<<<<Stmt#图3.3 优先关系矩阵4 中间代码形式的描述及中间代码序列的结构设计4.1中间代码形式三地址码是由下面一般形式的语句构成的序列： x:=y op z其中，xyz为名字、常数或变量；op代表运算符。对于本程序的具体三地址码输出，预计显示

9、结果如下：给定输入程序for i=0 step 1 until 10 do j=b+c;三地址码输出为<1> i=0<2> goto <5><3> i+<4> if i<10 goto<5> else goto<7><5> j=b+c<6> goto<3><7> end5 编译系统的概要设计5.1数据结构单词种别：struct Token/单词种别int num;/词素（单词的值）string lexeme;产生式结构：struct Term/1为状态，2为

10、产生式int kind;/如果是状态保存格子里的内容string action;5.2模块设计本系统分为四大模块：词法分析模块、语法分析模块、语义分析模块以及主控模块，其中主控模块负责协调前三个模块。词法分析模块为语法分析模块以及语义分析模块提供单词序列。5.2.1词法分析模块void LexicalScanner()/词法分析FILE *fp;char ch;errno_t _err2 = fopen_s(&fp, "d:123.txt", "rb");if (fp = NULL)/取当前目录下的tk.txt文件的第一个字符fprintf(st

11、derr, "error opening!n");/格式化输出到流/错误打印到屏幕上exit(1);doch = fgetc(fp);if (ch = '$')break;/作为文件结尾else if (ch = ' ')scanner(fp);/空格略过elsefseek(fp, -1, 1);scanner(fp);/扫描 while (ch != '$');stringsarrTop = "(1,$)"5.2.2语法、语义分析模块void Semantic()Token t1;t1.lexeme =

12、"#"t1.num = 100;tokenstokenTop = t1;for (int i = 0;i < 20;i+)cout << tokensi.lexeme << " "cout << endl;string product1 = "fori=E1"string product2 = "F1stepE2"string product3 = "F2untilE3"string product4 = "F3doS1"stack&

13、lt;string> tokenStack;for (int i = 0;i < 15;i+)for (int j = 0;j < 15;j+)priorityTableij = 2;tokenStack.push("#");map_.insert(map<string, int>:value_type("S", 0);map_.insert(map<string, int>:value_type("F1", 1);map_.insert(map<string, int>:valu

14、e_type("F2", 2);map_.insert(map<string, int>:value_type("F3", 3);map_.insert(map<string, int>:value_type("for", 4);map_.insert(map<string, int>:value_type("step", 5);map_.insert(map<string, int>:value_type("until", 6);map_.ins

15、ert(map<string, int>:value_type("do", 7);map_.insert(map<string, int>:value_type("i", 8);map_.insert(map<string, int>:value_type("=", 9);map_.insert(map<string, int>:value_type("E1", 10);map_.insert(map<string, int>:value_type(&qu

16、ot;E2", 11);map_.insert(map<string, int>:value_type("E3", 12);/map_.insert(map<string, int>:value_type("#", 13);map_.insert(map<string, int>:value_type("S1", 13);map_.insert(map<string, int>:value_type("#", 14);priorityTablemap_&qu

17、ot;for"map_"i" = 0;priorityTablemap_"i"map_"=" = 0;priorityTablemap_"="map_"E1" = 0;priorityTablemap_"F1"map_"step" = 0;priorityTablemap_"step"map_"E2" = 0;priorityTablemap_"F2"map_"until&qu

18、ot; = 0;priorityTablemap_"until"map_"E3" = 0;priorityTablemap_"F3"map_"do" = 0;priorityTablemap_"do"map_"S1" = 0;priorityTablemap_"do"map_"F3" = -1;priorityTablemap_"do"map_"F2" = -1;priorityTablemap_

19、"do"map_"F1" = -1;priorityTablemap_"do"map_"for" = -1;priorityTablemap_"#"map_"S" = -1;priorityTablemap_"#"map_"F1" = -1;priorityTablemap_"#"map_"F2" = -1;priorityTablemap_"#"map_"F3&qu

20、ot; = -1;priorityTablemap_"#"map_"for" = -1;priorityTablemap_"E1"map_"step" = 1;priorityTablemap_"E2"map_"until" = 1;priorityTablemap_"E3"map_"do" = 1;priorityTablemap_"S"map_"#" = 1;for (int i = 0;i

21、< 15;i+)for (int j = 0;j < 15;j+)cout << priorityTableij<<" "cout << endl;int i = 0;while (strcmp("#",tokensi.lexeme.c_str()!=0)while (priorityTablemap_tokenStack.top()map_tokensi.lexeme.c_str()<1)tokenStack.push(tokensi.lexeme);/cout << tokenStac

22、k.top() << endl;i+;if (priorityTablemap_tokenStack.top()map_tokensi.lexeme.c_str()=2&&!strcmp(tokensi.lexeme.c_str()," ")cout << "error" << endl;system("pause");/errorelse/cout << "enter" << endl;string tempStr = "&qu

23、ot;string top = tokenStack.top();tempStr = tokenStack.top() + tempStr;tokenStack.pop();while (priorityTablemap_tokenStack.top()map_top=0)top = tokenStack.top();tempStr = top + tempStr;tokenStack.pop();/cout << tempStr << endl;if (priorityTablemap_tokenStack.top()map_top = 2)/errorcout &l

24、t;< "error2" << endl;system("pause");elseif (!strcmp(tempStr.c_str(), product1.c_str()tokenStack.push("F1");cout << "i=E1" << endl;cout << "goto OVER" << endl;if (!strcmp(tempStr.c_str(), product2.c_str()tokenStack.pu

25、sh("F2");cout << "AGAIN:i=i+E2" << endl;if (!strcmp(tempStr.c_str(), product3.c_str()tokenStack.push("F3");cout << "OVER: if i<E3 THEN" << endl;if (!strcmp(tempStr.c_str(), product4.c_str()tokenStack.push("S");cout <<

26、 "begin S1;" << endl <<"goto AGAIN end;" << endl;/cout << tempStr << endl;/tokenStack.push(tokensi.lexeme);/i+;5.2.3主控模块int main()File.open("d:1233.txt", ios:out);/词法分析LexicalScanner();/词法分析完成后会将Token序列输出到中间文件/语法分析SyntaxScanner();/语义分析Seman

27、tic();File.close();cout << translation << endl;return 0;6 详细的算法描述6.1词法分析算法6.2语法分析算法6.3语义分析算法语法分析与语义分析同步完成，在规约的过程中，每使用一个产生式则调用其对应的动作7 软件的测试方法和测试结果编译调试环境：Visual Studio 2015 Community程序语言：C+测试用例：采用如下形式双重循环作为测试用例之一首先输出的是词法分析结果： 然后是语法以及语义分析结果： 8 本设计的评价、特点、本系统可以完成Fortran语言的For语句的语法制导翻译，在词法分析的基

28、础上先后进行语法分析和语义分析。在完成这些功能的基础上，我认为此系统仍然不能算一个合格的产品，还有很多需要改进之处。例如，词法分析可以进一步改进成为词法分析器的自动生成器。语法分析和语义分析也应改为自动生成简单优先文法生成器。特点：本系统可以完成Fortran语言的子集（For语句）的制导翻译，但是没有优化过程，符号表的控制也很简单，很多代码采用了硬编的方法，改变文法将导致巨大的工作量。因此本系统的一大特点是不易扩展和变更。9 收获与体会经过这次课内实践，使我更加扎实的掌握了有关编译原理方面的知识，在编写程序的过程中遇到了许多问题，但经过一遍遍的调试终于使得程序可以顺利运行。但是程序中存在着很

29、大的不足：程序可扩展性差。过而能改，善莫大焉。在课内过程中，我不断发现错误，不断改正，不断领悟，不断获取。最终的检测调试环节，本身就是在践行“过而能改，善莫大焉”的知行观。这次课内实践终于顺利完成了，在设计中遇到了很多问题，最后终于游逆而解。在今后发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退，那样永远不可能收获成功，收获喜悦，也永远不可能得到社会及他人对你的认可！回顾这次课内实践，是一个痛并快乐的过程，在构造简单优先文法的矩阵时遇到了不少困难，花费了许

30、多时间，但是当成功构造出来时那种喜悦也是难以言表的。学习是个不断提升自我的过程。10 核心代码#include "stdafx.h"#include <stdio.h>#include <ctype.h>#include <string.h>#include <stdlib.h>#include <string>#include <iostream>#include <sstream>#include <fstream>#include <vector>#includ

31、e <stack>#include <map>using namespace std;/定义图，字符串与数字下表对应map <string, int> map_;/定义优先级表 -1为小于，0为等于，1为大于int priorityTable1515;/Token structurestruct Token/单词种别int num;/词素（单词的值）string lexeme;struct Term/1为状态，2为产生式int kind;/如果是状态保存格子里的内容string action;class SyntaxScannerpublic:SyntaxS

32、canner();SyntaxScanner();void createTable()/move to Product2DAF Machinebool Scanner()private:stack<Token, vector<Token>> TokenStack;stack<char, vector<char>>ChStack;Term ActionGoto2020;SyntaxScanner:SyntaxScanner()SyntaxScanner:SyntaxScanner()ofstream File;/保存结果的文件Token token

33、s100;/用数组代替储存token序列的中间文件int tokenTop = 0;/指向token序列的尾部char TOKEN30;/定义关键字char *table9 = " ","for","step","until","do","end","then","else","int" ;extern int lookup(char*);extern void out(int, char*);extern void

34、 report_error(void);string strings100;int arrTop = 0;/函数及全局变量声明/*extern可置于变量或者函数前，以表示变量或者函数的定义在别的文件中，提示编译器遇到此变量和函数时在其他模块中寻找其定义。另外，extern也可用来进行链接指定*/int lookup(char *TOKEN)int m, i;for (i = 1;i<8;i+)if (m = strcmp(TOKEN, tablei) = 0)/table中关键字匹配return i;return 0;/关键字匹配函数，返回关键字在表中的位置,空出空格/输出token的同

35、时，保存在中间文件中void out(int c, char *TOKEN)cout << "(" << c << "," << TOKEN << ")" << endl;File << "(" << c << "," << TOKEN << ")" << endl;/保存TokentokenstokenTop.num = c;tok

36、enstokenTop.lexeme = TOKEN;/tokenStack.push(tokenstokenTop);tokenTop+;void report_error()printf("error!n");/输出没有考虑的情况void scanner(FILE *fp)char TOKEN30 = '0' ;char ch;int i, c;ch = fgetc(fp);/获取字符，指针fp并自动指向下一个字符if (isalpha(ch)/判断该字符是否是字母TOKEN0 = ch;ch = fgetc(fp);i = 1;while (isaln

37、um(ch)/判断该字符是否是字母或数字TOKENi = ch;i+;ch = fgetc(fp);TOKENi = '0'fseek(fp, -1, 1);/回退一个字符c = lookup(TOKEN);if (c = 0)out(9, TOKEN);/输出标识符号,定编号为9elseout(c, TOKEN);/输出表中编号和关键字else if (isdigit(ch)/判断是否是数字TOKEN0 = ch;ch = fgetc(fp);i = 1;while (isdigit(ch)TOKENi = ch;i+;ch = fgetc(fp);/判断是否是连续数字if

38、(ch != '.')TOKENi = '0'fseek(fp, -1, 1);out(10, TOKEN);return;TOKENi = ch;i+;/将小数点放进TOKENfor (;)ch = fgetc(fp);if (!isdigit(ch)out(10, TOKEN);fseek(fp, -1, 1);break;TOKENi = ch;i+;/输出数字,定编号为10elseTOKEN0 = ch;switch (ch)case'':out(11, TOKEN);break;case'':out(12, TOKEN)

39、;break;case',':out(13, TOKEN);break;case'':out(14, TOKEN);break;case'<':ch = fgetc(fp);/读取下一个字符，判断<,<=,<>(空标签)if (ch = '=')TOKEN1 = ch;out(15, TOKEN);/判断<=else if (ch = '>')TOKEN1 = ch;out(17, TOKEN);/判断<>空标签elsefseek(fp, -1, 1);out(

40、16, TOKEN);/判断小于号<break;case'=':ch = fgetc(fp);if (ch = '=')TOKEN1 = ch;out(19, TOKEN);elsefseek(fp, -1, 1);out(18, TOKEN);break;/判断=,=case'>':ch = fgetc(fp);/读取下一个字符，判断>,>=if (ch = '=')TOKEN1 = ch;out(21, TOKEN);elsefseek(fp, -1, 1);out(20, TOKEN);break;c

41、ase':':ch = fgetc(fp);/读取下一个字符，判断:,:=,若是关键词写入case或者?：则必要if (ch = '=')TOKEN1 = ch;out(23, TOKEN);elsefseek(fp, -1, 1);out(22, TOKEN);break;case'+':ch = fgetc(fp);/读取下一个字符，判断+,+=if (ch = '=')TOKEN1 = ch;out(25, TOKEN);elsefseek(fp, -1, 1);out(24, TOKEN);break;case'-

42、':ch = fgetc(fp);/读取下一个字符，判断-,-=if (ch = '=')TOKEN1 = ch;out(27, TOKEN);elsefseek(fp, -1, 1);out(26, TOKEN);break;case'*':ch = fgetc(fp);/读取下一个字符，判断*,*=if (ch = '=')TOKEN1 = ch;out(29, TOKEN);elsefseek(fp, -1, 1);out(28, TOKEN);break;case'/':ch = fgetc(fp);/读取下一个字

43、符，判断/,/=if (ch = '=')TOKEN1 = ch;out(31, TOKEN);elsefseek(fp, -1, 1);out(30, TOKEN);break;case'#':out(32, TOKEN);break;case'(':out(33, TOKEN);break;case')':out(34, TOKEN);break;default:report_error();break;/词法分析器void LexicalScanner()/词法分析FILE *fp;char ch;errno_t _err2

44、 = fopen_s(&fp, "d:123.txt", "rb");if (fp = NULL)/取当前目录下的tk.txt文件的第一个字符fprintf(stderr, "error opening!n");exit(1);doch = fgetc(fp);if (ch = '$')break;/作为文件结尾else if (ch = ' ')scanner(fp);/空格略过elsefseek(fp, -1, 1);scanner(fp);/扫描 while (ch != '$&#

45、39;);stringsarrTop = "(1,$)"void SyntaxScanner();/语法分析器void Semantic()Token t1;t1.lexeme = "#"t1.num = 100;tokenstokenTop = t1;for (int i = 0;i < 20;i+)cout << tokensi.lexeme << " "cout << endl;string product1 = "fori=E1"string product2 =

46、"F1stepE2"string product3 = "F2untilE3"string product4 = "F3doS1"stack<string> tokenStack;for (int i = 0;i < 15;i+)for (int j = 0;j < 15;j+)priorityTableij = 2;tokenStack.push("#");map_.insert(map<string, int>:value_type("S", 0);map

47、_.insert(map<string, int>:value_type("F1", 1);map_.insert(map<string, int>:value_type("F2", 2);map_.insert(map<string, int>:value_type("F3", 3);map_.insert(map<string, int>:value_type("for", 4);map_.insert(map<string, int>:value_t

48、ype("step", 5);map_.insert(map<string, int>:value_type("until", 6);map_.insert(map<string, int>:value_type("do", 7);map_.insert(map<string, int>:value_type("i", 8);map_.insert(map<string, int>:value_type("=", 9);map_.insert(ma

49、p<string, int>:value_type("E1", 10);map_.insert(map<string, int>:value_type("E2", 11);map_.insert(map<string, int>:value_type("E3", 12);/map_.insert(map<string, int>:value_type("#", 13);map_.insert(map<string, int>:value_type(&quo

50、t;S1", 13);map_.insert(map<string, int>:value_type("#", 14);priorityTablemap_"for"map_"i" = 0;priorityTablemap_"i"map_"=" = 0;priorityTablemap_"="map_"E1" = 0;priorityTablemap_"F1"map_"step" = 0;prio

51、rityTablemap_"step"map_"E2" = 0;priorityTablemap_"F2"map_"until" = 0;priorityTablemap_"until"map_"E3" = 0;priorityTablemap_"F3"map_"do" = 0;priorityTablemap_"do"map_"S1" = 0;priorityTablemap_"do&

52、quot;map_"F3" = -1;priorityTablemap_"do"map_"F2" = -1;priorityTablemap_"do"map_"F1" = -1;priorityTablemap_"do"map_"for" = -1;priorityTablemap_"#"map_"S" = -1;priorityTablemap_"#"map_"F1" = -

53、1;priorityTablemap_"#"map_"F2" = -1;priorityTablemap_"#"map_"F3" = -1;priorityTablemap_"#"map_"for" = -1;priorityTablemap_"E1"map_"step" = 1;priorityTablemap_"E2"map_"until" = 1;priorityTablemap_"E3"