编译原理课程设计报告毕业论文

1、 . . . 编译原理课程设计报告一、 课程设计目的通过课程设计进一步理解高级语言在计算机中的执行过程，了解现代编译器的运作机制，加深对编译原理中重点算法和编译技术的理解，提高自己自学和理解的能力。学会如何利用已有软件JFLex、Java_cup对词法分析器与语法分析器的构造。二、 设计概述本tiger语言编译器的编译过程涉与到编译五个阶段中的二个，即词法分析器、语法分析器。其中语法分析后还完成了语法树的打印的构造以与类型检查。词法分析器由JFLex编译正则式生成，词法分析器编译产生式生成，语法分析器由CUP生成。结果通过GUI界面呈现在使用者面前。编译程序需要在单词级别上来分析和翻译源程序，

2、所以首先要识别出单词，而词法分析部分的任务是：从左至右扫描源程序的字符串，按照词法规则（正则文法规则）识别出一个个正确的单词，并转换成该单词相应的二元式（种别码、属性值）交给语法分析使用。因此，词法分析是编译的基础。执行词法分析的程序称为词法分析器。语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作。三、 设计过程(一) 设计构思程序主要完成三大功能模块：词法分析器、语法分析器、GUI人机交互界面。词法分析器由JFLex编译正则式生成，其中必须为外界提供一个获取记号流的接口，实验中定为java_cup.runtime.Symbol

3、next_token。语法分析器是建立在词法分析器上的，故必须包含词法分析器以便获得记号流，next_token为语法分析器提供TOKEN，语法分析器的对外接口是：java_cup.runtime.Symbol debug_parse()，同时返回语法树的根节点。GUI界面是提供人机交互的，它能够依次显示词法分析阶段分析得到的所有TOKEN的信息，语法阶段生成的语法树，另外对于词法和语法阶段出现的错误在“错误提示”文本框中一一列举出来，提供用户改进代码的信息。流程图：GUI界面词法错误程序输入流记号流词法分析器TOKEN语法树语法分析器语法、类型错误类与文件说明：包AbsynPrint.jav

4、a/print out the syntax tree/The abstract syntax classes for Tiger包errormsgErrorMsg.java/used to produce error messages with detail information包java_cup.runtime/Support for CUP parser包parseGrm.java/Parser analyserMainInterface.java/GUI interfaceSym.java/tokens decimal representationYylex.java/Lexer a

5、nalyser包SemantEntry.java/for bindings in value environmentEnv.java/holds a value ,type environment and an error printerExpTy.java/holds the result of translating and type-checkingFunEntry.java/for function bindingsSemant.java/the main type-checking moduleVarEntry.java/for variable bindings包SymbolSym

6、bol.java/makes strings into unique Symbol objectsTable.java/does environments with Scopes包Translate包Types/describes Tiger_language types(二) 词法分析器 这部分的工作主要是熟悉JFLex的使用以与正确书写正则式，通过正则式的书写，生成相应的词法分析器。1. JFLex的使用 修改jflex-1.4.2bin中的jflex.bat文件中的参数，JAVA_HOME=%JAVA_HOME%libclasses.zip; JFLEX_HOME=%JFLEX_HOME

7、%libJFlex.jar；运行jflex.bat 并给选择输入文件（tiger.jlex），在没有错误的情况下，它在输出目录下生成一个Yylex.java的词法分析器。tiger.jlex文件开始部分的书写格式如下：package parse;/将词法分析器打包在Parse下import errormsg.ErrorMsg;/导入类%cup/支持与cup的关联%line/支持yyline()调用%column /支持yycolumn()调用%char%state COMMENT,STRING/声明两个新的状态%/设置所有可能的词法错误类型StringBuffer str = new Stri

8、ngBuffer();private static final String errorM = Error: Unmatched end-of-comment punctuation., Error: Unmatched start-of-comment punctuation., Error: Unclosed string., Error: Illegal character.;private void newline() /保持errormsg里的行数记录变量的正确性 errorMsg.newline(yychar);private void err(String s) /通过error

9、msg报错private java_cup.runtime.Symbol tok(int kind, Object value) return new java_cup.runtime.Symbol(kind, yychar, yychar+yylength(), value);/返回所识别的TOKENpublic Yylex(java.io.FileReader s, ErrorMsg e) this(s);/重载Yylex构造函数，方便错误输出 errorMsg = e;private ErrorMsg errorMsg;/ ErrorMsg对象声明private int comment_

10、count = 0;/变量，用于处理注释嵌套%eofval/到文件末尾时判断最后的状态是否是YYINITIAL,若不是则报相应的错误if(zzLexicalState!=0)switch(zzLexicalState)case 2:err(errorME_STARTCOMMENT);break;case 4:err(errorME_UNCLOSEDSTR);break;default: /*do nothing*/ return tok(sym.EOF, null);%eofval/一些基本类型简化表达式的定义ALPHA=A-Za-z/字母DIGIT=0-9/数字LINE_TERMINATOR

11、 = r|n|rn/换行符NONNEWLINE_WHITE_SPACE_CHAR= tfb012/非换行空白符WHITE_SPACE_CHAR =LINE_TERMINATOR | NONNEWLINE_WHITE_SPACE_CHAR/空白符%2. 正规表达式的书写 Tiger需要识别的变量和字符有：整型常量、字符常量、操作符、括符、分隔符、关键字、标识符、COMMENT。整型常量： 一个整形数字，即字母的任意组合。字符常量： 用双引号引起来的字符，可跨行但行尾必须以结尾，行首开始。字符常量中间可包含转义字符如：r n t f ” xyz x,y,z表示0127的整数。 操作符： + - *

12、 / = = = := & | 括符： ( ) 分隔符： ； ： 关键字： while do for to if else then let in end type var array of break nil function 标识符：以字符开头，加上字符、数字、下划线的任意组合 评论： 以/*开头，以*/结尾中间可嵌套任意个但必须是封闭的。 一般的字符或者保留字只需返回它的名字就可以了，例如：在YYINITAIL的状态下识 别到最长匹配串为“array” ，则直接返回token，编号为sym.java中已经定义的数字 编号，书写的格式如下： array return tok(sym.ARR

13、AY,null); 下面着重谈一下对于字符串和注释的处理：字符串的处理：在YYINITIAL状态下遇到一个 ” 时表示识别字符常量的开始，此时就要进入先前声明的STRING 状态，先前声明的字符串str用来保存已识别的字符常量（初始化为空），代码如下： str.setLength(0); yybegin(STRING);当识别的过程中如果碰到转义字符n t ，在str后添加相应的字符，碰到非转移字符就直接添加到str后面，忽略两个反斜杠之间的所有空白字符，代码如下： nr+ str.append(yytext(); n str.append(n); str.append(); WHITE_SP

14、ACE_CHAR+ /*do nothing*/特别是当碰到跟上三位数字时，应该判断数值围是否在ASCII围中 0DIGITDIGIT|10-1DIGIT|120-7 str.append(char)Integer.valueOf(new String(yytext().getBytes(),1,3).intValue();当再次识别到时标志着字符串的识别结束，此时将str中的字符串容作为String的容返回，同时应该返回YYINITIAL状态，继续识别其他的TOKEN yybegin(YYINITIAL);return tok(sym.STRING,str.toString(); 识别到这些

15、token以外的其他字符，则直接报错 . err(errorME_ILLEGAL); 注释的处理：在YYINITIAL状态下遇到一个 /* 时表示识别注释的开始，此时就要进入先前声明的COMMENT状态，同时comment_count加1，以实现注释嵌套的实现。如果在COMMENT状态下又一次识别到/*表示另一个注释嵌套的开始，此时也需要对comment_count进行加1的操作，代码如下： /* yybegin(COMMENT); comment_count = comment_count + 1; /* comment_count = comment_count + 1; 但是如果在YYI

16、NITIAL状态下遇到一个 */则是一个错误，需要报出，代码如下： */ err(errorME_ENDCOMMENT); 在COMMENT状态下遇到*/则表示着一个嵌套中的注释结束，此时需要对comment_count进行减1的操作，如果操作之后其值为0，表示整个注释已经结束，回到YYINITIAL状态，如若不然则继续在COMMENT的状态下识别，代码如下： */ comment_count = comment_count - 1; if (comment_count = 0)yybegin(YYINITIAL)；识别到这些token以外的其他字符，则直接忽略 . /*do nothing*

17、/ 3. 词法分析器的结构 词法分析器实现了Lexer接口，也就是实现了Token next_token()这个方法，不断调用此方法就可以获得所有的记号流。使用词法分析器时需要指定输入流InputStream以与ErrorMsg，InputStream完成源程序的读取，ErrorMsg完成对错误信息的输出。 至此词法分析器的构造已经基本基本结束了。(三) 语法分析器完成语法分析器的主要步骤是cup文件的编写，由于语法树的数据结构已给出，所以产生式的编写可以直接参考tiger语言的语法模式，当然这其中产生了许多冲突，但是可以通过设置符号的优先级来解决移进和规约的冲突。1. CUP的使用CUP的使

18、用需要在命令行的环境下进行，打开命令提示符，输入如下所示的语句，既可以在当前目录下生成语法分析器Grm.java，Grm.cup的书写格式如下所示：Cup开始部分的书写格式如下：package parse;/产生在parse包里面import Absyn.*;import javax.swing.*;action code :static Symbol.Symbol sym(String s) /将字符串转化为Symbolreturn Symbol.Symbol.symbol(s);:;parser code : Yylex lexer;public static Exp parseResul

19、t;/记录语法树根节点的变量errormsg.ErrorMsg errorMsg;/输出语法错误的ErrorMsg对象声明public void syntax_error(java_cup.runtime.Symbol current) report_error(Syntax error ( + current.sym + ), (java_cup.runtime.Symbol)current);public void report_error(String message, java_cup.runtime.Symbol tok) errorMsg.error(tok.left, messa

20、ge);public Grm(errormsg.ErrorMsg err, JTextArea text) this();/语法分析器的构造errorMsg=err;textin=text;:;init with : /语法分析器初始化，从界面文本框中获取输入流 lexer = new Yylex( new java.io.StringBufferInputStream(textin.getText(),errorMsg);:;scan with : java_cup.runtime.Symbol symb= lexer.debug_next_token(); for(;(symb.sym=s

21、ym.error)&symb.sym!=sym.EOF;)symb= lexer.debug_next_token();return symb; :;/同过debug_next_token获取token并打印出token/终结符terminal String STRING;terminal Integer INT;terminal COMMA, COLON, SEMICOLON, LPAREN, RPAREN, LBRACK, RBRACK, LBRACE, RBRACE, DOT;terminal PLUS, MINUS, TIMES, DIVIDE, EQ, NEQ, LT, LE, GT

22、, GE, AND, OR, ASSIGN, UMINUS;terminal ARRAY, IF, THEN, ELSE, WHILE, FOR, TO, DO, LET, IN, END, OF, BREAK, NIL, FUNCTION, VAR, TYPE, ID;/终结符优先级次序precedence right DO, ELSE, THEN;precedence nonassoc ASSIGN;precedence left OR;precedence left AND;precedence nonassoc EQ, NEQ, LT, LE, GT, GE;precedence le

23、ft PLUS, MINUS;precedence left TIMES, DIVIDE;precedence left UMINUS;precedence left LBRACK;关于优先级次序的说明：由于在语法分析的过程中会产生许多移进和规约的冲突，通过设置终结符的优先级可以避免一些情况的发生。将PLUS、MINUS的优先级定义在TIMES、DIVIDE之前即可使乘除的优先级高于加减运算的优先级。另外通过设置比较运算符的有限次序，可以避免分析时的移进-归约冲突。此外在实际的cup生成过程中，还会出现一些其他的冲突，例如以下两个冲突的解决： .1出现冲突 between lvalue :=

24、ID (*) and lvalue := ID (*) LBRACK expr RBRACK and expr := ID (*) LBRACK expr RBRACK OF expr under symbol LBRACK 解决办法：把left LBRACK 设为最高优先级，这样的话当碰到是归约ID还是移进 LBRACK的冲突时，系统会自动根据优先级而去执行移进的动作。.2出现冲突 between expr := IF expr THEN expr (*) and expr := IF expr THEN expr (*) ELSE expr under symbol ELSE 解决办法：把

25、right DO,ELSE,THEN设为最低优先级,通过precedence right ELSE,THEN语句;定义为右结合的then将与else结合，故先移进。.3 负号和减号识别时有冲突，解决方案是重新定义一个终结符UMINUS算数运算符中最 高优先级，负号时重新赋予UMINUS的优先级。 2. 语法的书写按照Tiger Manual上的语法规则，将上面的语法一一写入cup文件的后面，必要的时候定义适当的非终结符来完成语法的结构。每一条语法规则都应该返回其相应的语句类型，这些类型都已经在Absyn包中定义好了，只要根据语句的类型按照定义返回即可。其中，要注意的是一些链表的连接，如ExpL

26、ist、FieldList等，需要保证这些对象的连接正确性。首先，在语法分析前完成非终结符的定义，定义如下：non terminal FieldListtype_fields, type_fields_n, type_fields_ex;non terminal FieldExpListfield_list, field_list_n, field_list_ex;non terminal ExpListexpr_list, expr_list_n, expr_list_ex, expr_seq, expr_seq_n, expr_seq_ex;non terminal DecListdecl

27、aration_list, declaration_list_ex;non terminal Tytype;non terminal Decdeclaration, type_declaration, variable_declaration, function_declaration;non terminal Exp expr, program;/文法开始符non terminal Var lvalue;其次在文法开始符的语法句的执行语句中，将第一个Exp传给先前定义的parseResul,代码如下：start with program;program := expr:e : parser.

28、parseResult = e; :;对于一些常规的语法，只需返回相应的语句类型即可，如赋值语句 expr := lvalue:l ASSIGN expr:e: RESULT = new AssignExp(lleft, l, e); :；对于需要连接起来的类型，如ExpList,FieldExpList,FieldList,DecList,可以通过消除左递归的方法来将多个具有向后指针的类型的语句相连，另外链表还可以为空，下面举ExpList的例子来说明处理的方法：expr_list := expr_list_n:l(1): RESULT = l; : | : RESULT = null; :

29、；expr_list_n := expr:e expr_list_ex:x(2): RESULT = new ExpList(e, x); :;expr_list_ex:=COMMA expr_list_n:l (3): RESULT = l; : | : RESULT = null; :；在（1）开始识别的时候先判断这个表达式是否为空，若空则直接返回null，否则进入（2），因为至少有一个Explist的存在，所以可以声明一个新的ExpList，并将它的tail指向下一个可能的ExpList，当然下一个ExpList可能为空，所以在处理expr_list_ex时需要判断其是否为空，如空则直接

30、返回null，否则可以将嵌套进行下去。3. 语法树的生成语法分析结束后，同时会返回整棵语法树的根结点，我们可以利用这个根节点进行语法树的打印，调用AbsynPrint.Java中的prExp(par.parseResult,2)，将整个语法树在屏幕上打印出来，同时还可以在Print.Java中定义一个string变量将需要的打印容储存起来，在屏幕上打印完之后在GUI界面的文本框显示出来。4. 类型检查类型检查运作思想语法分析结束后，我们还可以对整棵语法树进行类型检查，我们可以从语法树的根结点开始对每一个分支进行扫描，根据Tiger语言所所规定的语法类型规则进行判断这一条语句运算或者返回的类型是

31、否符合要求，如果类型不匹配立即报出类型错误。类型检查的关键是管理好符号表。整个检查过程维护一变量表，一类型表，都是Table类型的。Table是按键值方式存储，关键字是Symbol类型，值是Binder类型，Binder中变量value存储具体的信息。变量表的value存储Entry类型，Entry说明变量的类型以与其它信息。类型表的value存储的是Type类型，保存类型的具体信息。Binder类是一个链表结构，也就是说一个符号可以几个类型，如本地变量覆盖全局变量，本地类型覆盖全局类型等。类型检查所用到的类的关系可以从下图中看清：Envvenv: Tabletenv: TableerrorM

32、sg: ErrorMsgSemantFunEntry Entry VarEntryTabledic: Dictionarytop: Symbolmarks: BinderTypesBinder value: Objectprevtop: Symboltail: Binder每个变量或类型都有一个有效围，在function的声明过程中，其声明的变量只在它的函数体中有效，出了函数体就失去了它的作用围，成为了一个无效的变量。又如在in end中又嵌套了let in end 语句，则外面语句中声明的变量在里面的语句中仍然有效（重复声明会覆盖）。可以利用table中的beginscope()和endsc

33、ope()来确定变量的作用围。调用函数 beginScope() 添加一个标记，标记起始位置。当这个变量的作用域到底时用调用函数 endScope() 把先前的声明都删掉。遇到的实际问题与思考.1类型检查的过程中，还有一个递归调用的问题，如testcase6letfunction do_nothing1(a: int, b: string)=do_nothing2(a+1)function do_nothing2(d: int) =do_nothing1(d, str)indo_nothing1(0, str2)End其中do_nothing1函数的body需要调用do_nothing2,但是

34、按照函数按顺序声明的话，此时do_nothing2还没有被声明，因而不能够被识别，会报错。解决方法：在let语句检查declist之前将所有的dec（包括type_declaration，function_declaration）置入相应的表中，这样的话当检查上述的函数do_nothing1时就不会出现do_nothing2还未被声明的情况了。.2类型检查的过程中，还有一个循环定义的问题，如testcase16let type a=ctype b=atype c=dtype d=ainend解决方法：在这四个类型定义中，都用到了其他一起声明的类型，存在类似a-c-d-a的类型循环定义，到最后四

35、个四个变量的类型还是没有被实在定义，这是不允许的。解决的方法是在检查类型定义之前用bind(ExpTy)函数将新声明的类型的binding设为声明中将要被赋予的类型。这样在进入类型声明的检查中，只需通过isloop()函数判断是否是循环定义就可知道是否出错。在这样的设计之下，代码let type a=ctype b=atype c=dtype d=intinend就不会出现如上的错误了，a-c-d-int就会跳出检查，返回false.3在Declist中的声明中要求函数和类型的声明分别必须放在一起，如letfunction g(a:int):int = atype t = intfunctio

36、n g(a:int):int = ainend示例中说这是合法的，应为声明的时候是以类处理的，funcDec和后面的funcDec一起处理，typeDec和后面的typeDec一起处理，导致检查不出这个重复定义函数。我认为这里有点不太合理，我的想法是可以在let语句的检查中将所有的声明都放入环境变量中，这样的话既可以检查出是否重复定义，有可以使类型的前后调用不受阻碍。即在ExpTy transExp(LetExp e)中添加如下代码：ArrayList list =new ArrayList();for(DecList tmp=e.decs;tmp!=null;tmp=tmp.tail)Dec

37、 head=tmp.head;if(head instanceof TypeDec)/置入新的类型TypeDec td=(TypeDec)head;if(list.contains(.toString()env.errorMsg.error(td.pos,type++ has been already defined);list.add(.toString();env.tenv.put(,new NAME();if(head instanceof FunctionDec)/置入新的函数变量FunctionDec fd=(Fu

38、nctionDec)head;Type re=transTy(fd.result);RECORD rc=transTypeFields(fd.params);if(list.contains(.toString()env.errorMsg.error(fd.pos,function ++ already defined);elselist.add(.toString();env.venv.put(, new FunEntry(rc,re);list.clear();这样的处理过后，就会达到上述的效果，不过这只是我的个人意见，虽然与tiger语言的要求有矛盾，但我认为这不失为一种好的改进。处于这种改动，t