编译原理上机报告.doc

编译原理基础上机报告册班级： xxxxxx 学号： xxxxxxxx 姓名： xxxxxx 目录第一次上机题目：词法分析器的构造3一、 任务与目的31.任务32.目的3二、 软件设计31.软件的总体结构与模块划分32.java软件包的设计73.软件中关键的算法7三、 测试例程设计与测试结果分析101.例程1102.例程211四、总结、体会及其他12第二次上机题目：语法分析器的构造13一、任务与目的131.任务132.目的13二、软件设计131.java软件包的设计132.适合编写递归下降子程序的文法133.表达式的语法树164.语法分析器主程序流程图195.语法分析器的递归下降子程序19三、测试例程设计与测试结果分析201.例程1202.例程2213.例程322四、总结、体会及其他24附录：源代码25一、analyser中的代码251.token_type中的代码252.token中的代码253.mytokentab中的代码264.scanner2中的代码275.viewer中代码36二、parser中的代码381.exprnode中的代码382.parser中的代码403.parsermain中的代码52第一次上机题目：词法分析器的构造1、 任务与目的1. 任务词法分析器的构造一般有以下几大步骤：（1） 用正规式对模式进行描述（2） 由正规式构造nfa（3） 由nfa转化为dfa且最小化（4） 根据最小dfa编写程序并进行测试为函数绘图语言编写一个解释器解释器接受用绘图语言编写的源程序，经语法和语义分析之后，将源程序所规定的图形显示在显示屏（或窗口）中。2. 目的源程序实际上是一个字符序列，词法分析器读取该序列并根据构成规则将其转换为记号流。词法分析器至少需要完成以下几个任务：（1） 滤掉源程序中的注释和无用成分（空格、tab等）（2） 输出记号，供语法分析器使用（3） 识别非法输入，并将非法输入作为出错记号提供给语法分析器，以便进行出错处理通过自己动手编写解释器，掌握语言翻译特别是语言识别的基本方法。2、 软件设计1. 软件的总体结构与模块划分（1） 记号的设计为了以后引用方便，笔者将记号单独写成了一个类。记号一般由类别和属性两部分组成。根据函数绘图语言的特点，为记号设计如下的类，其中记号的类别type和第一个属性lexeme是每个记号都必须有的信息，而后两个属性value和funptr，则分别是专门为常数和函数设计的。需要特别注意的是，这里的lexeme笔者没有选择使用string，而是选择了stringbuffer类。因为笔者在后面的编程中发现lexeme属性在后面长度可能会改变，而string并不能符合这一特征，故将其定义为stringbuffer类。二来stringbuffer类和string类之间的转换是相当方便的。另一个值得一提的应该是c中的函数指针，java中为了避免指针的滥用不再采用它，但是还是提供了一些可以替代的解决方法。比如用映射机制就替代了函数指针。public class token public token_type type;public stringbuffer lexeme;public double value;public method funptr;public token() throws exceptiontype = token_type.errtoken;lexeme = new stringbuffer();value = 0.0;funptr = null;token(token_type a, string b, double c, method d) type = a;lexeme = new stringbuffer(b);value = c;funptr = d;根据对记号的分析，可以将函数绘图语言的记号类别进行如下划分，且用枚举类型表示他们： public enum token_type / 记号的类别origin, scale, rot, is, / 保留字to, step, draw, for, from, / 保留字t, / 参数semico, l_bracket, r_bracket, comma, / 分隔符plus, minus, mul, div, power, / 运算符func, / 函数const_id, / 常数nontoken, / 空记号errtoken/ 出错记号（2） 模式中的正规式表示函数绘图语言的词法可用下述正规式集合表示，其中的letter和digit是辅助定义。描述词法的正规式-letter=a-za-zdigit=0-9comment=/|- -white_space=( |t|n)+semico=;l_bracket=(r_bracket=)comma=,plus=+minus=-mul=*div=/power=*const_id=digit+(.digit*)?id=letter+(letter|digit)*/为了简单化，笔者这里符号表的组成进行了简化，规定它只能用字母组成-（3） 区分记号中的符号表符号表是一个数组，记录了所有符合id模式的保留字、常量名、参数名和函数名等。这里由于java中类机制，笔者只能在类中定义变量。public class mytokentab token tokentab = new token18;/ 切记类中要进行初始化必须在函数中mytokentab() throws exceptiontokentab0 = new token(token_type.const_id, pi, 3.1415926, null);tokentab1 = new token(token_type.const_id, e, 2.71828, null);tokentab2 = new token(token_type.t, t, 0.0, null);tokentab3 = new token(token_type.func, sin, 0.0, math.class.getmethod(sin, double.class);tokentab4 = new token(token_type.func, cos, 0.0, math.class.getmethod(cos, double.class);tokentab5 = new token(token_type.func, tan, 0.0, math.class.getmethod(tan, double.class);tokentab6 = new token(token_type.func, ln, 0.0, math.class.getmethod(log, double.class);tokentab7 = new token(token_type.func, exp, 0.0, math.class.getmethod(exp, double.class);tokentab8 = new token(token_type.func, sqrt, 0.0, math.class.getmethod(sqrt, double.class);tokentab9 = new token(token_type.origin, origin, 0.0, null);tokentab10 = new token(token_type.scale, scale, 0.0, null);tokentab11 = new token(token_type.rot, rot, 0.0, null);tokentab12 = new token(token_type.is, is, 0.0, null);tokentab13 = new token(token_type.for, for, 0.0, null);tokentab14 = new token(token_type.from, from, 0.0, null);tokentab15 = new token(token_type.to, to, 0.0, null);tokentab16 = new token(token_type.step, step, 0.0, null);tokentab17 = new token(token_type.draw, draw, 0.0, null);（4） 正规式的dfa根据正规式和dfa的构造算法，可以得到最终的简化dfa如下图所示：（5） 词法分析器的执行流程（6） 与语法分析器的接口词法分析器提供记号给语法分析器，它们之间的关系如下图所示：2. java软件包的设计3. 软件中关键的算法 为了能够在其他的函数中调用gettoken()函数，笔者将该函数定义为public。这个函数中和c或者c+的不同之处主要在于c中unread函数的实现。为了实现字符的回退，笔者利用了java中的pushbackreader。原因笔者将在后面进行详细叙述。public token gettoken() throws exception/ in order to make it visible,we define it publictoken token;int char;char ch;token = new token();/ 初始化为semicoemptytokenstring();token.lexeme = tokenbuffer;for (;) char = getchar();if (char = -1) token.type = token_type.nontoken;return token; elsech = (char) char;if (char = 13)lineno+;if (!isspace(char) char) break;addchartokenstring(char) char);if (isletter(char) char)/ int char之间的转换需要测试for (;) char = getchar();if (isalnum(char) char)addchartokenstring(char) char);else break;backchar(char) char);token = judgekeytoken(tokenbuffer.tostring();token.lexeme = tokenbuffer;return token; else if (isdigit(char) char) for (;) char = getchar();if (isdigit(char) char)addchartokenstring(char) char);elsebreak;if (char) char = .) addchartokenstring(char) char);for (;) char = getchar();if (isdigit(char) char)addchartokenstring(char) char);elsebreak;/ end of if(char)char = .)backchar(char) char);token.type = token_type.const_id;token.lexeme = tokenbuffer;token.value = double.valueof(tokenbuffer.tostring();/ 如此实现atof的功能return token; else switch (char) char) case ;:token.type = token_type.semico;break;case (:token.type = token_type.l_bracket;break;case ):token.type = token_type.r_bracket;break;case ,:token.type = token_type.comma;break;case +:token.type = token_type.plus;break;case -:char = getchar();if (char = -) while (char != n & char != -1)char = getchar();backchar(char) char);return gettoken(); else backchar(char) char);token.type = token_type.minus;break;case /:char = getchar();if (char = /) while (char != n & char != -1)char = getchar();backchar(char) char);return gettoken(); else backchar(char) char);token.type = token_type.div;break;case *:char = getchar();if (char) char = *) token.type = token_type.power;break; else backchar(char) char);token.type = token_type.mul;break;default:token.type = token_type.errtoken;break;/ end of switch(char)char)/ end of elsereturn token;3、 测试例程设计与测试结果分析1. 例程1（1） 测试例程设计为了测试词法分析器是否能够正确地分析输入序列和识别记号，而由于笔者刚刚着手java且时间有限，故只能用java的控制台进行输入输出。笔者可以在java中的run - run configurations - arguments - program arguments中给main主函数传递参数。（2） 测试结果test1.txt文件内容如下：origin is (100, pi+300);-here are notes.for t from 0 to 120 step 1 draw (t, -t);在这里，笔者特意加了行表示注释，而且其中的还用的是小写的表示符，因为根据笔者程序的设计，不仅可以调过注释，而且还可以使得程序对大小写不敏感，这样无论是from，还是from，亦或from，均可以被正确识别。测试结果如下图所示：2. 例程2（1）测试例程设计但是在实际中，笔者发现有时文本文档不能正确地检查到.txt文件的结尾标志。故设计如下用例。且在该用例中，笔者自行设计了出错记号errtoken。（2）测试结果test2.txt文件内容如下：lsfjlaks;origin is (100, 300);-here are notesrot is 0;throw is测试结果如下图所示：四、总结、体会及其他整体来说这次用java来实现词法分析器对我来说确实存在这不小的挑战，而且我写的程序还或多或少的存在着这样或那样的瑕疵，但我收获了许多。而这收获既包括技术方面的，也包括非技术层面的。现将我的收获列举如下：1. 现在突然开始明白为什么强人能够在很短的时间内学会一种语言，并能够灵活运用。那是因为他们目标明确。然后只看跟自己有关的部分，有侧重点，而不是胡子眉毛一起抓。2. 起初根本不知道java到底怎么调试，可是等到会了之后，会发现其实和其他的任何语言一样，用java的printf，学会如何进行调试让我至少在心理上对java不再那么的害怕。3. “java中没有指针” 这句话其实是骗人的，所谓的没有，只不过是换了个名字而已。java的指针一般都是用类进行包装的，而指针函数则是用java.lang.reflect进行实现的。4. c中的将预读的字符退回到文件输入流中，回退函数ungetc，在java中我们用了java.io.pushbackreader来进行实现。由于平时java中用到的关于输入输出流的函数一般是java.io.inputstream、java.io.outputstream，以及java.io.file，而至于pushbackreader之类的退回函数则用的比较少了。学习它着实费了一番力气。5. 还有对于某些.txt文件不能识别其结束标志，这个确实比较麻烦。6. 词法分析中lineno，即跟踪记号所在源文件行号，由于java中并不识别unsigned类型，故只得将其定义为int。第二次上机题目：语法分析器的构造一、任务与目的1. 任务语法分析是语法制导翻译的基础，语法分析器是函数绘图语言解释器的核心，因此语法分析器的构造是整个解释器构造的关键。语法分析器的构造分为两个重要步骤：规定语言的文法和根据文法编写程序。由于我们采用递归下降子程序方法，因此在文法的设计上的要求是ll(1)文法。同时语法分析时要构造出语言结构的语法树，以便于后边的语法知道翻译。具体到此绘图语言，需要构造语法树的语言结构仅限于表达式，从而为语义做铺垫。语法分析器的任务：（1） 为句子构造语法树（2） 检查输入序列中的错误故主要的工作如下：（1） 设计函数绘图语言的文法，使其适合递归下降分析（2） 设计语法树的节点，用于存放表达式的语法树（3） 设计递归下降子程序，分析句子并构造表达式的语法树（4） 设计测试程序和测试用例，检验分析器是否正确2. 目的编写一个语法分析器，不限语言二、软件设计1. java软件包的设计由于涉及到语法分析器要调用词法分析器的内容，故现将java中的包组织如下所示：2. 适合编写递归下降子程序的文法包含了左递归和公共左因子的文法g1如下所示：其中$代表空。-program - statement semico | $statement - originstatement | scalestatement | rotstatement | forstatementoriginstatement - origin is l_bracket expression comma expression r_bracketscalestatement - scale is l_bracket expression comma expression r_bracketrotstatement - rot is expressionforstatement - for t from expression to expression step expression draw l_bracket expression comma expression r_bracketexpression - expression plus term| expression minus term| termterm - term mul factor| term div factor| factorfactor - plus factor| minus factor | componentcomponent - atom power component | atomatom - const_id| t| func l_bracket expression r_bracket| l_bracket expression r_bracket-消除了左递归和公共左因子的文法g3如下所示：其中$代表空。-program - statement semico | $statement - originstatement | scalestatement | rotstatement | forstatementoriginstatement - origin is l_bracket expression comma expression r_bracketscalestatement - scale is l_bracket expression comma expression r_bracketrotstatement - rot is expressionforstatement - for t from expression to expression step expression draw l_bracket expression comma expression r_bracketexpression - term expressionexpression - plus | term expression | minus term expression | $term - factor termterm - mul factor term| div factor term | $factor - plus factor | minus factor | componentcomponent - atom power component | atomatom - const_id| t| func l_bracket expression r_bracket| l_bracket expression r_bracket-对term进行了转换的文法g4如下所示：-program - statement semico statement - originstatement | scalestatement | rotstatement | forstatementoriginstatement - origin is l_bracket expression comma expression r_bracketscalestatement - scale is l_bracket expression comma expression r_bracketrotstatement - rot is expressionforstatement - for t from expression to expression step expression draw l_bracket expression comma expression r_bracketexpression - term ( plus | minus ) term term - factor ( mul | div ) factor factor - plus factor | minus factor | componentcomponent - atom power component | atomatom - const_id| t| func l_bracket expression r_bracket| l_bracket expression r_bracket-3. 表达式的语法树（1）语法树的节点表达式的语法树的节点可以分为以下三类：叶节点：用于存放原子表达式，如常数或参数t。两个孩子的内部节点：用于存放二元运算如plus、mul等构成的表达式。一个孩子的内部节点：用于存放函数调用如sin(t)等构成的表达式。可以用下面的一个类统一表示，根据当前记号的类别分配对应的属性，未分配到的属性为默认构造函数初始化时为其赋的值。语法树（表达式-16+5*3/cos(t)）的存储如下所示：在这里，java和c不同的是不再提供类似于联合union的结构体，也就是说不再提供非此即彼的功能。本来打算使用一个类，然后将所有的属性都放在里面，用到的则进行赋值，没有用到的则不用理睬。但后来为了使条理更清晰，我们对它进行了改造。在这里，我们使用了内置子类的方法。 public class exprnode public token_type opcode;public content content;public class content public caseop caseoperator;public casefunc casefunc;public double caseconst;public double caseparmptr;/ 在初始化函数中，我们将它初始化为0/ public double caseparmptr = new double1;/ here is very important!/* * double类型是double的包装类，在jdk1.5以后， 二者可以直接相互赋值，称为自动拆箱和自动装箱。 * 看你的提示，我推测你的jdk版本在1.5以前。 如果是这样，可以用double中的方法，将包装类转为 基本数据类型，如： double * amount = rec.getamount().doublevalue() ; * * */ 我们用数组来代替指针public class caseop public exprnode left;public exprnode right;public caseop() left = null;right = null;/ end of class caseoppublic class casefunc public exprnode child;public method mathfunptr;public casefunc() child = null;mathfunptr = null;/ end of class casefuncpublic content() caseoperator = new caseop();casefunc = new casefunc();caseconst = 0.0;caseparmptr = new double(0);public exprnode()/ system.out.println(we are in exprnode);opcode = token_type.errtoken;/ system.out.println(we are in exprnode444);/ 和词法分析一致，最开始初始化为token_type.errortokencontent = new content();/ system.out.println(we below the content);/ end of class exprnode（2） 语法树的建立为了简化语法树的建立过程，我们将待缺省值的函数用参数不同的重载函数来代替，通过传给函数不同类型或者个数的参数进行动态调用，而这也正是c+或者说java与c的不同之处。相关代码如下所示： /-生成语法树的一个节点-/* * every time,we need to allocate new node,and * return it! * */叶节点，用于存放参数tprotected exprnode makeexprnode(token_type opcode)/texprnode exprptr = new exprnode();exprptr.opcode = opcode;exprptr.content.caseparmptr = parameter;return exprptr;/叶节点，用于存放常数const_idprotected exprnode makeexprnode(token_type opcode,double value)/const_id/need to modify the type of token,and the value.exprnode exprptr = new exprnode();exprptr.opcode = opcode;exprptr.content.caseconst = value;return exprptr;/一个孩子的内部节点，用于存放函数调用protected exprnode makeexprnode(token_type opcode,method func,exprnode exprnode)/functionexprnode exprptr = new exprnode();exprptr.opcode = opcode;exprptr.content.casefunc.mathfunptr = func;exprptr.content.casefunc.child = exprnode;return exprptr;/ 两个孩子的内部节点，用于存放二元运算protected exprnode makeexprnode(token_type opcode,exprnode left,exprnode right)/case operationexprnode exprptr = new exprnode();exprptr.opcode = opcode;exprptr.content.caseoperator.left = left;exprptr.content.caseoperator.right = right;return exprptr;4. 语法分析器主程序流程图5. 语法分析器的递归下降子程序首先，语法分析器以下的几个函数中需要用到词法分析为其提供的内容： public void fetchtoken(); public void matchtoken(token_type atoken);public void syntaxerror(int case_of);词法分析器为其提供的内容如下所示：函数public gettoken();记号类型tokentype;全局变量行号int lineno;词法分析器、语法分析器、语义分析器三者之间的调用关系如下所示（1） 主要产生式的递归子程序递归下降子程序分为两类，返回值为void类型的函数实现相应的产生式，返回值为exprnode类型的函数对表达式进行语法分析的同时为其构造语法树。-产生式函数- public void program(); public void statement(); public void originstatement(); public void scalestatement(); public void rotstatement(); public void forstatement();-语法树构造函数- public exprnode expression(); public exprnode term(); public exprnode factor(); public exprnode component(); public exprnode atom();三、测试例程设计与测试结果分析1. 例程1（1） 测试用例分析首先，我们来做一个最简单的测试用例，用它实现语法分析器的各项基本要求。（2） 测试结果在test1.txt中内容如下：-here are notes.for t from 0 to 120 step 1 draw (t, -t);测试结果如下：2. 例程2（1） 测试用例分析在这个例子中，我们着重检验我们的语法树是否正确。（2） 测试结果在test2.txt中内容如下：-here are notes.for t from 0 to 120 step 1 draw (t, -t);测试结果如下：3. 例程3（1） 测试用例分析这第三个用例我们用来对词法分析器中的反射机制进行测试。而在这里，我们需要在类parser中添加下面的两个函数：public static void myprint(string n) system.out.println(n);public static void printtable(double from, double to, int n, method f) system.out.println(f);double dx = (to - from) / (n - 1);for (double x = from; x = to; x += dx) try double y = (double) f.invoke(null, x);system.out.printf(%10.4f | %10.4f%n, x, y); catch (exception e) e.printstacktrace();接着，我们需要在函数public void printsyntaxtree(exprnode root,int indent)中switch语句 else if (root.opcode = token_type.func)中增加如下测试代码：try system.out.println(=);system.out.println(=look here=);system.out.println(=);method sp = parser.class.getmethod(myprint, string.class);sp.invoke(null, args);printtable(1, 10, 10, root.content.casefunc.mathfunptr); catch (exception e) syste