编译原理上机报告.doc_三一办公31ppt.com

资源描述

《编译原理上机报告.doc》由会员分享，可在线阅读，更多相关《编译原理上机报告.doc（52页珍藏版）》请在三一办公上搜索。

1、编译原理基础上机报告册班级： 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三、测

2、试例程设计与测试结果分析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）用正规式对模式进行描述（2）由正规式构造NFA（3）由NFA转化为DFA

3、且最小化（4）根据最小DFA编写程序并进行测试为函数绘图语言编写一个解释器解释器接受用绘图语言编写的源程序，经语法和语义分析之后，将源程序所规定的图形显示在显示屏（或窗口）中。2. 目的源程序实际上是一个字符序列，词法分析器读取该序列并根据构成规则将其转换为记号流。词法分析器至少需要完成以下几个任务：（1）滤掉源程序中的注释和无用成分（空格、TAB等）（2）输出记号，供语法分析器使用（3）识别非法输入，并将非法输入作为出错记号提供给语法分析器，以便进行出错处理通过自己动手编写解释器，掌握语言翻译特别是语言识别的基本方法。二、软件设计1. 软件的总体结构与模块划分（1）记号的设计为了

4、以后引用方便，笔者将记号单独写成了一个类。记号一般由类别和属性两部分组成。根据函数绘图语言的特点，为记号设计如下的类，其中记号的类别type和第一个属性lexeme是每个记号都必须有的信息，而后两个属性value和FunPtr，则分别是专门为常数和函数设计的。需要特别注意的是，这里的lexeme笔者没有选择使用String，而是选择了StringBuffer类。因为笔者在后面的编程中发现lexeme属性在后面长度可能会改变，而String并不能符合这一特征，故将其定义为StringBuffer类。二来StringBuffer类和String类之间的转换是相当方便的。另一个值得一提的应该是C中的

5、函数指针，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

6、, 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, POWE

7、R, / 运算符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)*/为了

8、简单化，笔者这里符号表的组成进行了简化，规定它只能用字母组成-（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_T

9、ype.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, T

10、AN, 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(sqr

11、t, 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);T

12、okenTab14 = 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）与语法分析器的接口词法分析器提

13、供记号给语法分析器，它们之间的关系如下图所示：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 =

14、 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之间的

15、转换需要测试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(c

16、har) 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(Tok

17、enBuffer.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

18、-: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 GetTo

19、ken(); 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

20、 token;三、测试例程设计与测试结果分析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);在这里，笔者特意加了

21、行表示注释，而且其中的还用的是小写的表示符，因为根据笔者程序的设计，不仅可以调过注释，而且还可以使得程序对大小写不敏感，这样无论是FROM，还是from，亦或FrOm，均可以被正确识别。测试结果如下图所示：2. 例程2（1）测试例程设计但是在实际中，笔者发现有时文本文档不能正确地检查到.txt文件的结尾标志。故设计如下用例。且在该用例中，笔者自行设计了出错记号ERRTOKEN。（2）测试结果test2.txt文件内容如下：lsfjlaks;origin is (100, 300);-here are notesrot is 0;throw is测试结果如下图所示：四、总结、体会及其他整体来说这

22、次用Java来实现词法分析器对我来说确实存在这不小的挑战，而且我写的程序还或多或少的存在着这样或那样的瑕疵，但我收获了许多。而这收获既包括技术方面的，也包括非技术层面的。现将我的收获列举如下：1. 现在突然开始明白为什么强人能够在很短的时间内学会一种语言，并能够灵活运用。那是因为他们目标明确。然后只看跟自己有关的部分，有侧重点，而不是胡子眉毛一起抓。2. 起初根本不知道Java到底怎么调试，可是等到会了之后，会发现其实和其他的任何语言一样，用Java的printf，学会如何进行调试让我至少在心理上对Java不再那么的害怕。3. “Java中没有指针” 这句话其实是骗人的，所谓的没有，只不过是换

23、了个名字而已。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. 词法分析中LineN

24、o，即跟踪记号所在源文件行号，由于Java中并不识别unsigned类型，故只得将其定义为int。第二次上机题目：语法分析器的构造一、任务与目的1. 任务语法分析是语法制导翻译的基础，语法分析器是函数绘图语言解释器的核心，因此语法分析器的构造是整个解释器构造的关键。语法分析器的构造分为两个重要步骤：规定语言的文法和根据文法编写程序。由于我们采用递归下降子程序方法，因此在文法的设计上的要求是LL(1)文法。同时语法分析时要构造出语言结构的语法树，以便于后边的语法知道翻译。具体到此绘图语言，需要构造语法树的语言结构仅限于表达式，从而为语义做铺垫。语法分析器的任务：（1）为句子构造语法树（2）检

25、查输入序列中的错误故主要的工作如下：（1）设计函数绘图语言的文法，使其适合递归下降分析（2）设计语法树的节点，用于存放表达式的语法树（3）设计递归下降子程序，分析句子并构造表达式的语法树（4）设计测试程序和测试用例，检验分析器是否正确2. 目的编写一个语法分析器，不限语言二、软件设计1. Java软件包的设计由于涉及到语法分析器要调用词法分析器的内容，故现将Java中的包组织如下所示：2. 适合编写递归下降子程序的文法包含了左递归和公共左因子的文法G1如下所示：其中$代表空。-Program - Statement SEMICO | $Statement - OriginStateme

26、nt | 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

28、_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 Expressi

29、on 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

31、orStatementOriginStatement - 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

33、：用于存放原子表达式，如常数或参数T。两个孩子的内部节点：用于存放二元运算如PlUS、MUL等构成的表达式。一个孩子的内部节点：用于存放函数调用如sin(t)等构成的表达式。可以用下面的一个类统一表示，根据当前记号的类别分配对应的属性，未分配到的属性为默认构造函数初始化时为其赋的值。语法树（表达式-16+5*3/cos(T)）的存储如下所示：在这里，Java和C不同的是不再提供类似于联合union的结构体，也就是说不再提供非此即彼的功能。本来打算使用一个类，然后将所有的属性都放在里面，用到的则进行赋值，没有用到的则不用理睬。但后来为了使条理更清晰，我们对它进行了改造。在这里，我们使用了内置子类

34、的方法。 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类型是do

35、uble的包装类，在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 caseOpp

36、ublic 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

37、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与

38、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 v

展开阅读全文