2014城市学院《编译原理》实验指导书

1、编译原理实验指导书适用实验课时：30适用对象：计算机科学与技术专业 网络工程专业 软件工程专业实验目的和内容编译原理实验的目的是使学生将编译理论运用到实际当中，实现一个简单语言集的词法分析程序、语法分析程序和简单语义处理程序，验证实际编译系统的实现方法，并加深对编译理论的认识。基本实验分为两个部分，实验一识别无符号数的词法分析器设计实现、实验二无符号数的算术四则运算LR语法分析器设计实现，总的实验学时为30课时。本实验还包括扩展实验，供编程能力较强的学生自愿进行。要求每个学生独立完成三个基本实验的设计和编程实现，并形成完整的实验报告。建议使用VC+编程工具。实验一 算术四则运算词法分析程序实现

2、一、实验目的与要求通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。二、实验内容选取无符号数的算术四则运算中的各类单词为识别对象，要求将其中的各个单词识别出来。输入：由无符号数和+，*，/, ( , ) 构成的算术表达式，如1.5E+2100。输出：对识别出的每一单词均单行输出其（类别码，值）。三、实现方法1、设计识别各类单词的状态转换图描述无符号常数的确定、最小化状态转换图如图1所示。其中编号0，1，2，6代表非终结符号、及， 1，2和6为终态，分别代表整数、小数和科学计数的识别结束状态。图1 文

3、法G的状态转换图其中编号0，1，2，6代表非终结符号、及， 1，2和6为终态，分别代表整数、小数和科学计数的识别结束状态。在一个程序设计语言中，一般都含有若干类单词符号，为此可首先为每类单词建立一张状态转换图，然后将这些状态转换图合并成一张统一的状态图，即得到了一个有限自动机，再进行必要的确定化和状态数最小化处理，最后据此构造词法分析程序。四则运算算术符号的识别很简单，直接在状态图的0状态分别引出相应标记的矢线至一个新的终态即可。根据自己的习惯，也可以将其转换为状态矩阵形式。2、词法分析程序编写(1)构造单词二元式列表类，实现单词二元式（class，value）的按序存取。(2)构造词法分析器

4、类，实现整数、小数、科学计数法数字的加减乘除括号组成的算数表达式输入串识别生成二元式序列。3、词法分析程序测试用于测试扫描器的实例源文件中应有词法正确的，也应有错误的字符串，对于输入的测试用例的源程序文件，以对照的形式将扫描器的分析结果信息在输出文件中表示出来。4、带有语义处理的词法分析程序编写参考以下表2和程序，对词法分析程序进行扩展，对识别的无符号数进行计值，并将输出形式改为（类别码，值）的二元式形式。四、参考资料实现无符号数识别的参考方法：将设计的状态转换图直接转化为一张程序流程图，并在外层再增加一个以EOF为循环终止条件的while循环，即形成能连续识别各类单词的词法分析程序。各类单词

5、的编码建议如表1。表1 单词的内部编码单词符号类别码（CLASS）单词值（VALUE）无符号数1数字值+2无值3无值*4无值/5无值(6无值)7无值与无符号数状态转换图对应的包含语义处理过程（据此可计算求得无符号数的数字值）的状态矩阵和参考程序如下所示。表2包含语义处理过程的识别无符号数的状态矩阵根据加入语义过程说明的状态转换图直接编写词法分析程序，部分实现代码如下：1 #include 2 #include 3 #include 4 #define LETTER 05 #define DIGIT 16 #define POINT 27 #define OTHER 38 #define POW

6、ER 49 #define PLUS 510 #define MINUS 611 #define UCON 7 /Suppose the class number of unsigned constant is 712 #define ClassOther 20013 #define EndState -114 int w,n,p,e,d;15 int Class; /Used to indicate class of the word16 int ICON;17 float FCON;18 static int CurrentState; /Used to present current s

7、tate, the initial value:01920 int GetChar (void);21 int EXCUTE (int,int)；22 int LEX (void)；23 int HandleOtherWord (void)24 return ClassOther;25 26 int HandleError (void)27 printf (Error!n); return 0;2829 int GetChar (void)30 31 int c;32 c=getchar ( );33 if(isdigit(c) d=c-0;return DIGIT;34 if (c=.) r

8、eturn POINT;35 if (c=E|c=e) return POWER;36 if (c=+) return PLUS;37 if (c=-) return MINUS;38 return OTHER;39 40 int EXCUTE (int state, int symbol)41 42 switch (state)43 44 case 0:switch (symbol)45 46 case DIGIT: n=0;p=0;e=1;w=d;CurrentState=1;Class=UCON;break;47 case POINT: w=0;n=0;p=0;e=1;CurrentSt

9、ate=3;Class=UCON;break;48 default: HandleOtherWord( );Class=ClassOther;49 CurrentState=EndState;50 51 break;52 case 1:switch (symbol)53 54 case DIGIT: w=w*10+d;break; /CurrentState=155 case POINT: CurrentState=2;break;56 case POWER: CurrentState=4;break;57 default: ICON=w;CurrentState=EndState;58 59

10、 break；60 case 2:switch (symbol)61 62 case DIGIT: n+;w=w*10+d;break;63 case POWER: CurrentState=4;break;64 default: FCON=w*pow(10,e*p-n);CurrentState=EndState;65 66 break;67 case 3:switch (symbol)68 69 case DIGIT: n+;w=w*10+d;CurrentState=2;break;70 default: HandleError( )；CurrentState=EndState;71 7

11、2 break；73 case 4:switch (symbol)74 75 case DIGIT: p=p*10+d;CurrentState=6;break;76 case MINUS: e=-1;CurrentState=5;break;77 case PLUS: CurrentState=5;break;78 default: HandleError( );CurrentState=EndState;79 80 break；81 case 5:switch (symbol)82 83 case DIGIT: p=p*10+d;CurrentState=6;break;84 defaul

12、t: HandleError( );CurrentState=EndState;85 86 break;87 case 6:switch (symbol)88 89 case: DIGIT:p=p*10+d;break;90 default: FCON=w*pow(10,e*p-n);CurrentState=EndState;91 92 break;93 94 return CurrentState;95 96 int LEX (void)97 98 int ch;99 CurrentState=0;100 while (CurrentState!=EndState)101 102 ch=G

13、etChar( );103 EXCUTE (CurrentState,ch);104 105 return Class;106 实验二 算符优先分析语法制导翻译程序设计实现一、实验目的与要求通过设计、编制、调试典型的算符优先语法分析程序，实现对实验一所得词法分析程序所提供的单词序列进行语法检查和结构分析，并进行语义处理。二、实验内容选择对各种常见高级程序设计语言都较为通用的语法结构无符号数的算术四则运算作为分析对象，设计并实现一个完整的语法制导翻译程序。输入：由实验一输出的单词类别串，如1，15031，50输出：对于所输入的源程序，如果输入符号串是给定文法定义的合法句子，输出分析过程以及计算结

14、果；如果不是句子，则进行错误提示。三、实现方法1、 首先根据算术四则运算的语法定义，构造算符优先分析表。2、语法分析程序编写设置输入缓冲区、分析栈、算符优先分析表，并根据算符优先分析法编写语法分析程序。3、语法制导翻译程序实现 对以上语法分析器增加简单的语义处理功能，构造算符优先语法制导翻译器，实现算数表达式的语法分析与计算。4、语法制导翻译程序测试用于测试的实例源文件中应有语法正确的，也应有语法错误的符号串，语法正确的输出分析和计算结果，错误的给予错误提示。实验报告要求实验报告主要包括四方面内容：1、实验设计实验采用的文法，状态转换图或矩阵，程序流程设计和每部分的主要功能说明等。2、程序代码实验实现的源程序，要求符合代码行首缩进、单句代码换行、标识符命名合理，并包括必要的注释。3、实验过程问题分析记录记录实验过程中发生的编译错误并分析错误原因和解决的方法及结果，参考表3。表3 实验一中发生的编译错误记录表编号出错时间出错代码错误提示出