《96778997973编译原理实验指导书 .docx》由会员分享，可在线阅读，更多相关《96778997973编译原理实验指导书 .docx（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品名师归纳总结前言编译原理是运算机科学与技术、软件工程等专业的主干课和必修课，由于这门课程相对抽象且内容较复杂，始终是比较难学的一门课程。在编译原理的学习过程中，试验特殊重要，只有通过上机试验，才能使同学对比较抽象的课程内容产生一个详细的感性熟识。但是，目前国内市场上很少有较详细且比较适合我院实际的试验指导书，为此，我们特编了这份指导书，期望能对我院的编译原理教案工作有所帮忙。本书试验环境主要为C 环境 由于兼容性问题，建议使用Turboc2.0 及一个词法分析器自动生成工具 FLEX和一个语法分析器自动生成工具BISON。书中给出的参考源程序也是C源程序，但由于试验者熟识熟知的语言工具不尽
2、相同，因而强求接受统一的编程语言编程是不现实的。试验者在把握了编译程序各个阶段的功能和原理之后，不难借助使用其他自己熟识的语言实现相关功能。试验者在试验过程中应当侧重写出自己在算法分析、设计思路、实现功能或程序代码等方面的特色，写出设计和实现过程中遭受到的难点和解决方法，可以不拘泥于试验指导给出的参考性设计思路，尽可能在深度和广度上加以拓展。只有这种各具特色的试验报告，才将更有利于表达试验者在创新思维和动手才能上的差异。通过这些试验，能使同学对这些部份的工作机理有一个详细的明白，达到“知其然，且知其所以然”的目的。并可在C环境下对自动生成工具生成的词法、语法分析器进行编译调试。 由于手工生成词
3、法和语法分析器的工作量太大，在实际中常用自动生成工具来完成之。这些工具中最著名的当属贝尔试验室的词法分析器生成工具LEX 和语法分析器生成工具YACC。它们现已成为 UNIX 的标准应用程序同UNIX 一起发行。与此同时GNU推出与 LEX 完全兼容的 FLEX，与YACC完全兼容的 BISON。这两个程序都在Internet上以源代码的形式免费发行，所以很简洁在其它操作系统下重新编译安装。我们试验接受的就是for dos的 FLEX和 BISON。本书有关的编译工具及其源程序例子，可到BISON 的网站上下载。关于FLEX 和 BISON 的用法简介，参见附录， 如需更详细的介绍，请参阅编译
4、工具中帮忙文件。关于试验学时和支配，任课老师可依据实际情形，选做其中的一部份。由于这门课试验难度较大，所以期望任课老师在试验前支配好同学的预习工作。在上机前要求同学写好试验预习报告。本书中 c 程序均在 Turboc2.0下调试通过 .LEX 和 YACC源程序均在 FLEX和 BISON下调试通过 .由于编者水平有限，本书中必定存在着不少缺点，在此恳请大家赐予批判和指正，我们将尽力订正。在此特对关怀支持编写本书的院系领导表示感谢。本书中关于 LEX 和 YACC的部份大量参考引用了何炎祥老师主编，华中理工高校出版社出版的编译原理一书，在此表示诚意的感谢。周鹏杨亚会梅琴 赵榕2006 年 8
5、月目 录试验一词法分析器设计 0试验二熟识 FLEX使用方法 9可编辑资料 - - - 欢迎下载精品名师归纳总结试验三用 FLEX自动生成 PL/0 词法分析器 9试验四用递归下降法进行表达式分析 16试验五用算符优先法进行表达式分析 17试验六利用 BISON生成逆波兰表示运算器21 试验七利用 BISON生成中缀表示运算器 22 附录一词法分析器生成工具 FLEX简介 22附录二语法分析器生成工具 YACC简介 28可编辑资料 - - - 欢迎下载精品名师归纳总结试验一词法分析器设计【试验目的】1. 把握生成词法分析器的方法，加深对词法分析原理的懂得。2. 把握设计、编制并调试词法分析程序
6、的思想和方法。3. 本试验是高级语言程序设计、数据结构和编译原理中词法分析原理等学问的综合。【试验内容及要求】1. 选择一种熟识的高级语言 int x,a,b。float y,c,d。x = a + b。y=c / d。ifxyx = 10 。else y=100。将该源程序的源文件经词法分析后输出以二元组形式表示的单词符号序列。3. 编写的程序具有确定的查错才能。提交的试验报告中要有试验名称、试验目的、试验内容、试验程序清单、调试过程和运行结果，程序的主要部分作出功能说明，并有试验收成体会或改进看法等内容。4. 试验前请仔细阅读试验预习提示，提示中程序仅供参考。5. 本试验建议学时数为 4
7、学时。【试验预习提示】1. 词法分析器的功能和输出格式词法分析器的功能是输入以字符串表示的源程序，输出单词符号或单词符号序列。词法分析器的单词符号常常表示成以下的二元组 单词的种别码，单词符号的属性值。本试验中，接受的是一符一种种别码的方式。2. 调试程序文法的EBNF扩展巴科斯范式）表示如下:= main:= 。 :=|:= =:= ifthen:= while:= := +| := *|/:= |可编辑资料 - - - 欢迎下载精品名师归纳总结:= :=:= |:= |=|=|=|.=:= A|B|C| |Z|a|b|c| |z 要求不区分大小写 := 0|1|2|3|4|5|6|7|8|
8、93. “超前搜寻”方法词法分析时，常常会用到超前搜寻方法。如当前待分析字符串为“a+” , 当前字符为 ，此时，分析器倒底是将其分析为大于关系运算符仍是大于等于关系运算符了？显 然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符 +，这时可知应将 说明为大于运算符。但此时，超前读了一个字符+， 所以要回退一个字符，词法分析器才能正常运行。在分析标识符，无符号整数等时也有类似情形。4. 词法分析程序主程序的算法思想算法的基本思想是依据扫描到单词符号的第一个字符的种类，拼写出相应的单词符号，其实现的基本任务是从字符串表示的源程序中识别出相应的具有独立意义的单词符号。主程序示初始化并
9、设置初始值调用扫描子程序输出单词二元组N输入串终止了吗？Y终止意图如图 1.1 所示。图 1.1词法分析主程序示意图其中设置初始值包括两个方面：1）关键字表的初值关键字作为特殊标识符处理，把它们预先支配在一张表中，称这张表为关键字表，当扫描程序识别出标识符时，查关键字表，如能查找到匹配的单词，就该单词是关键字，否就为一般标识符。关键字表为一个字符串数组，其描述为：char*KEY_WORDS8=“main ”, ” int ” ,” char ” , ” if ” , ” else ” , ” while ” , ” for ” 。2）程序中需要用到的主要变量为syn ，token 和 sum
10、。可编辑资料 - - - 欢迎下载精品名师归纳总结5. 参考部分源程序1 globals.h /*本头文件定义分析器需要的一些数据结构和宏等*/ #ifndef _GLOBALS_H#define _GLOBALS_H#include #include #include#define _SYN_MAIN 1#define _SYN_INT2#define _SYN_CHAR3#define _SYN_IF 4#define _SYN_ELSE5#define _SYN_FOR6#define _SYN_WHILE7/* 以上为关键字的单词种别码*/#define _SYN_ID10 /*标识符
11、的单词种别码 */#define _SYN_NUM11 /*#define _SYN_PLUS13 /*整数的单词种别码 */算术运算符“ +”的单词种别码*/#define _SYN_MINUS14/*算术运算符“ - ”的单词种别码*/#define _SYN_TIMES15/*算术运算符“ * ”的单词种别码*/#define _SYN_DIVIDE16/*算术运算符“ / ”的单词种别码*/#define _SYN_ASSIGN17 /* = */#define _SYN_SEMICOLON18 /*。 */#define _SYN_LT20 /* */#define _SYN_NE2
12、1 /*！ = */#define _SYN_LE22 /* */#define _SYN_ME24 /* = */#define _SYN_EQ25 /* = */#define _SYN_LPAREN28 /* */#define _SYN_RPAREN29 /* */#define _SYN_OVER0 /* #即源程序终止标志 */#define MAXLENGTH 255/*一行答应的字符个数*/ union WORDCONTENT /*存放单词内容的联合 */char T1MAXLENGTH 。int T2。char T3。 。typedef struct WORD /*单词二元组
13、 */ int syn。union WORDCONTENT value。WORD。可编辑资料 - - - 欢迎下载精品名师归纳总结#endif2 scan.h/* 本头文件定义词法分析器的接口*/ #ifndef _SCAN_H#define _SCAN_H#define _TAB_LEGNTH4/*一个 TAB占用的空格数 */#define _KEY_WORD_ENDwaiting for expanding/*关键字终止标志 */ void Scanervoid。/*函数 scaner得到源程序里的下一个单词符号*/ #endif3Symbol.c#include basedata.h
14、#include symbol.h #include #include #include char *WORDWORDLEN=BEGIN,CALL,CONST,DO,END,IF,ODD,PROCEDURE,READ,THEN,VAR,WHILE, WRITE 。/ 保留字字符串表 , 用于将保留字种别码转为字符串输出SYMBOL WSYMWORDLEN=BEGINSYM,CALLSYM,CONSTSYM, DOSYM,ENDSYM,IFSYM,ODDSYM,PROCSYM,READSYM,THENSYM,可编辑资料 - - - 欢迎下载精品名师归纳总结VARSYM,WHILESYM,WRIT
15、ESY。M/ char* SNAMESYMBOLNUM=保留字种别码表可编辑资料 - - - 欢迎下载精品名师归纳总结NOL,IDENT,NUMBER,PLUS,MINUS,TIMES,SLASH,ODDSYM,EQL,NEQ,LSS,LEQ,GTR,GEQ,LPAREN,RPAREN,COMMA,SEMICOLON,PERIOD,BECOMES,BEGINSYM,ENDSYM,IFSYM, THENSYM,WHILESYM,WRITESYM,READSYM, DOSYM,CALLSYM,CONSTSYM,VARSYM,PROCSYM。/ 单词字符串表 , 用于将保留字种别码转为字符串输出SY
16、MBOL sym。 / 最近已识的单词种别码chartokenMAXIDLEN+1。/ 最近已识别的单词int num 。/ 最近已识别的数字值char ch 。/ 最近已识别的字符int col=1,row=1。/ 当前行和列值FILE *fd。/ 指向待编译文件extern FILE *fout。/ 指向存放结果文件可编辑资料 - - - 欢迎下载精品名师归纳总结void Getcharvoidch=fgetcfd。ifch.=EOF & ch.=ncol+ 。return。void Getbcvoidwhilech=SPACE |ch=TABLE |ch=nifch=n row+。col
17、=1 。 Getchar。/为空字符就始终读至不为空字符void Retractvoidfseekfd,-1l,SEEK_CUR。col-。void Concatvoidchar temp2。temp0=ch。temp1=0。strcattoken,temp。int Reservevoidint i,j。char temp60。j=strlentoken。fori=0。itempi=touppertokeni。/ 将当前 token 字以大写形式存入temp 中tempi=0。可编辑资料 - - - 欢迎下载精品名师归纳总结fori=0。i可编辑资料 - - - 欢迎下载精品名师归纳总结if.
18、strcmpWORDi,temp break 。/判定当前 token 是否是保留字ifi=WORDLEN i=-1。return i。void Errorsymvoidfprintffout,There is error row: %5d, col: %5d, row,col。int Getsymvoidint k。int flag=TRUE。Getchar。Getbc。/ 滤掉白字符strcpytoken,。ifisalphach/以字母开头就是标识符num=0 。Concat。Getchar。whileisalnumchConcat。Getchar。Retract。/ 由于超前搜寻了，所
19、以回退一个字符k=Reserve。/ 判定此标识符是否是保留字ifk.=-1可编辑资料 - - - 欢迎下载精品名师归纳总结elsesym=WSYMk 。/ 将保留字种别码存入sym中sym=IDENT 。/ 将一般标识符种别码存入sym中可编辑资料 - - - 欢迎下载精品名师归纳总结/end else k.=-1。/end of if isalpha else ifisdigitch可编辑资料 - - - 欢迎下载精品名师归纳总结/以数字开头就为无符号整数Concat 。Getchar 。whileisdigitchConcat。Getchar。ifisalphachflag=FALSE。
20、whileisalnumchConcat。Getchar。/end of flag=FALSE Retract。/ 回退ifflag/如是无符号整数，就将整数值存于num中sym=NUMBER。num=atoitoken。/end of if isdigit elsenum=0。switch chcase +:Concat。sym=PLUS。break 。 case -:Concat。sym=MINUS。break 。 case *:Concat。sym=TIMES。break 。 case /:Concat。sym=SLASH。break 。 case :Concat。sym=LPARE。N
21、 break 。case :Concat。sym=RPARE。N break 。case =:Concat。sym=EQL。break 。 case #:Concat。sym=NEQ。break 。/*ODDSYM,EQL,NEQ,LSS,LEQ,GTR,GEQ,LPAREN, RPAREN,COMMA,SEMICOLON,PERIOD,BECOMES,*/case ,:Concat。sym=COMM。Abreak 。 case .:Concat。sym=PERIOD。break 。 case 。:Concat。sym=SEMICOLO。Nbreak 。 case :Concat。Getcha
22、r 。ifch.=/如后不跟 =,就回退可编辑资料 - - - 欢迎下载精品名师归纳总结elsesym=GTR。Retract。Concat。sym=GEQ。可编辑资料 - - - 欢迎下载精品名师归纳总结break。case 。Getchar 。ifch.=sym=LSS。Retract。elseConcat。sym=LEQ。break。case :Concat。Getchar 。ifch.=flag=FALSE 。Retract。elseConcat。sym=BECOME。Sbreak。default :Concat。flag=FALSE 。break 。/end of switch el
23、se char/end of else char return flag。4Testsym.c #include basedata.h #include symbol.h #include extern char *WORDWORDLEN 。extern int WSYMWORDLEN 。 extern char* SNAMESYMBOLNUM。extern SYMBOL sym 。/last readed word type。extern chartokenMAXIDLEN+1。/last readed word extern int num。/last readed num。extern
24、char ch。/last readed char。extern int col,row。extern FILE *fd。FILE *fout。 void Initvoid。void Quitvoid。void main可编辑资料 - - - 欢迎下载精品名师归纳总结int flag。Init。fprintffout,nTOKENSYMNUM。doflag=Getsym。ifflagfprintffout,n%10s%10s%d,token,SNAMEsym,num。else ifch.=EOFfprintffout,n%10s,token。Errorsym。whilech.=EOF。/ 反复
25、调用 Getsym 识别单词，将输出结果存入fout中Quit 。/=void Initvoidchar temp30。printfnPlease input your file name:。getstemp。if fd = fopentemp,rt= NULLfprintfstderr, Cannot open input file %s.n,temp。getch。return。/将 fd 指针指向待分析源文件if fout = fopenmydata.dat, wt= NULLfprintfstderr, Cannot open input file.n。getch。return。/将 f
26、out指向文件 mydata.datvoid Quitvoid可编辑资料 - - - 欢迎下载精品名师归纳总结fclosefd。fclosefout。试验二熟识 FLEX使用方法【试验目的】1. 把握 FLEX基本使用方法2. 把握如何将通过 FLEX生成的 C 语言模块加入到自已的程序中【试验要求】1. 编制 FLEX 源程序 , 分别统计文本文件 a.txt 中显现的标识符和整数个数 , 并显示之。标识符定义为字母开头，后跟如干个字母，数字或下划线。整数可以带 +或- 号，也可不带，且不以 0 开头。非单词和非整数就忽视不记，将之滤掉不显示。2. 编制一 FLEX源程序 , 分别求出文件
27、hh.c 中字母 , 数字, 回车符的个数。3. 摸索：如 main 函数不在 FLEX中实现，应当如何实现？4. 本次试验建议学时 2 学时。【试验预习提示】参见附录一。在看懂的基础上将之调试通过。试验三用 FLEX自动生成 PL/0 词法分析器【试验目的】娴熟把握 FLEX，并通过其生成一个词法分析器【试验要求】1. 通过 FLEX 生成一词法分析器函数int Getsym，其功能同试验一中词法分析器函数类似。2. 生成一工程文件，调用1 中生成的函数 Getsym ，对一指定的文件进行词法分析， 要求分析出单词的类型和值。并将分析结果存入一文件Mydata.dat中。3. 本试验建议学时
28、 4 学时。【试验预习提示】FLEX可自动生成函数 int yylex，就 int Getsym可通过调用 yylex实现。1. 由于 FLEX 生成的 C 程序模块lex.yy.c过于复杂，基本不行读，所以不要直接修改它，可将它看成一个“黑箱”，即不需要清楚知道其内部结构，只需要知道其接口即可。可通过修改FLEX 源程序间接修改之。关于lex.yy.c中常用变量和函数，在附录中有详细说明。2. 编制一 FLEX 源程序，不妨取名为sym.l ，通过 FLEX 生成 lex.yy.c，并将之加入到工程文件中。3. 工程文件结构可编辑资料 - - - 欢迎下载精品名师归纳总结生成一工程文件，不妨
29、取名为test.prj，将文件 Symbol.c,lex.yy.c,testsym.c加入之。源程序参考如下：1Basedata.h同试验一中 Basedata.h 2Symbol.h#include #include #define WORDLEN13/*保留字个数 */ #define MAXIDLEN50/*标识符最长长度 */ #define SYMBOLNUM32/*种别码个数 */typedef enum SYMBOLNOL,IDENT,NUMBER,PLUS,MINUS,TIMES,SLASH, ODDSYM,EQL,NEQ,LSS,LEQ,GTR,GEQ,LPAREN, RPA
30、REN,COMMA,SEMICOLON,PERIOD,BECOMES, BEGINSYM,ENDSYM,IFSYM,THENSYM,WHILESYM, WRITESYM,READSYM,DOSYM,CALLSYM,CONSTSYM,VARSYM,PROCSYM SYMBO。L /* 定义种别码 */int Reservevoid。/* 判定 token 字中单词是否是保留字*/int Getsymvoid。/* 从当前文件中识别出一单词，并给出其类型和值*/void MyErrorvoid。/* 打印错误信息 */ #endif3symbol.c#include Basedata.h #inc
31、lude Symbol.h #include #include #include char *WORDWORDLEN=BEGIN,CALL,CONST,DO,END,IF,ODD,PROCEDURE,READ,THEN,VAR,WHILE, WRITE可编辑资料 - - - 欢迎下载精品名师归纳总结 。/* 保留字字符串表 , 用于将保留字种别码转为字符串输出 */可编辑资料 - - - 欢迎下载精品名师归纳总结SYMBOL WSYMWORDLEN=BEGINSYM,CALLSYM,CONSTSYM, DOSYM,ENDSYM,IFSYM,ODDSYM,PROCSYM,READSYM,THEN
32、SYM,VARSYM,WHILESYM,WRITESYM。/* 保留字种别可编辑资料 - - - 欢迎下载精品名师归纳总结码表 */char* SNAMESYMBOLNUM=NOL,IDENT,NUMBER,PLUS,MINUS,TIMES,SLASH,ODDSYM,EQL,NEQ,LSS,LEQ,GTR,GEQ,LPAREN,RPAREN,COMMA,SEMICOLON,PERIOD,BECOMES,BEGINSYM,ENDSYM,IFSYM, THENSYM,WHILESYM,WRITESYM,READSYM, DOSYM,CALLSYM,CONSTSYM,VARSYM,PROCSYM。/
33、* 单词字符串表 , 用于将保留字种别码转为字符串输出*/SYMBOL sym。/* 最近已识的单词种别码*/chartokenMAXIDLEN+1。/* 最近已识别的单词*/ int num 。/* 最近已识别的数字值 */char ch 。/* 最近已识别的字符 */int col=1,row=1。/* 当前行和列值 */ int k。int flag。extern FILE *yyin, *yyout。extern int yylexvoid。int Reservevoidint i,j。char temp60。j=strlentoken。fori=0。itempi=touppertok
34、eni。/* 将当前 token 字以大写形式存入temp 中*/tempi=0。fori=0。iif.strcmpWORDi,temp break 。/* 判定当前 token 是否是保留字 */ ifi=WORDLEN i=-1。return i。可编辑资料 - - - 欢迎下载精品名师归纳总结void MyErrorvoidfprintfyyout,There is error row: %5d, col: %5d, row,col。int Getsymvoidreturn yylex。4Testsym.c#include Basedata.h #include Symbol.h #in
35、clude extern char *WORD。extern SYMBOL WSYMWORDLE。Nextern char* SNAMESYMBOLNUM。extern SYMBOL sym 。extern chartokenMAXIDLEN+1。extern int num。extern char ch。extern int col,row。extern int k。 extern int flag。extern FILE *yyin,*yyout。void Initvoid。void Quitvoid。void mainint flag。Init。if.yyinreturn。fprintf
36、yyout,nTOKENSYMNUM。doflag=Getsym。可编辑资料 - - - 欢迎下载精品名师归纳总结ifflag=ENDFILEreturn。可编辑资料 - - - 欢迎下载精品名师归纳总结中*/ifflagfprintfyyout,n%10s%10s%d,token,SNAMEsym,num。elsefprintfyyout,n%10s,token。MyError。whilech.=EOF。/* 反复调用 Getsym 识别单词，将输出结果存入fout可编辑资料 - - - 欢迎下载精品名师归纳总结Quit 。/*=*/void Initvoidchar temp30。prin
37、tfnPlease input your file name:。getstemp。if yyin = fopentemp,rt= NULLfprintfstderr, Cannot open input file %s.n,temp。getch。return。/*将 fd 指针指向待分析源文件 */if yyout = fopenmydata.dat, wt= NULLfprintfstderr, Cannot open input file.n。getch。return。/*将 fout指向文件 mydata.dat*/可编辑资料 - - - 欢迎下载精品名师归纳总结void Quitvoidfcloseyyin。fcloseyyout。5FLEX源程序 sym.l%#include Basedata.h #include Symbol.h #include #include #include extern char *WORD。extern SYMBOL WSYMWORDLE。Nextern char* SNAMESYMBOLNUM。extern SYMBOL sym 。extern chartokenMAXIDLEN+1。exte