尾《编是译原理》实验.doc

《编译原理》实验 《编译原理》是国内外各高等院校计算机科学技术类专业，特别是计算机软件专业的一门重要专业课程。该课程系统地向学生介绍编译程序的结构、工作流程及编译程序各组成部分的设计原理和实现技术。由于该课程理论性和实践性都比较强，内容较为抽象复杂，涉及到大量的软件设计算法，因此，一直是一门比较难学的课程。为了使学生更好地理解和掌握编译技术的基本概念、基本原理和实现方法，实践环节非常重要，只有通过上机进行程序设计，才能使学生对比较抽象的教学内容产生具体的感性认识，增强学生综合分析问题、解决问题的能力，并对提高学生软件设计水平大有益处。 本实验内容可在《编译原理》课程教学的同时，安排学生进行相关的实验。实验平台可选择在MS-DOS或Windows操作系统环境，使用C/C++的任何版本作为开发工具。学生在做完试验后，应认真撰写实验报告，内容应包括实验名称、实验目的、实验要求、实验内容、测试或运行结果等。 实验一 词法分析 实验目的 对C语言的一个子集设计并实现一个简单的词法分析器，掌握利用状态转换图设计词法分析器的基本方法。 2．实验要求 利用该词法分析器完成对源程序字符串的词法分析。输出形式是源程序的单词符号二元式的代码，并保存到文件中。 3．实验内容 (1) 假设该语言中的单词符号及种别编码如下表所示。 单词符号及种别编码 单词符号 种别编码 单词符号 种别编码 main 1 [ 28 int 2 ] 29 char 3 { 30 if 4 } 31 else 5 , 32 for 6 : 33 while 7 ； 34 标识符ID 10 ＞ 35 整型常数NUM 20 ＜ 36 = 21 ＞＝ 37 + 22 ＜＝ 38 - 23 ＝＝ 39 * 24 ！＝ 40 / 25 41 ( 26 42 ) 27 || 43 (2) 关键字main int char if else for while都是小写并都是保留字。 算符和界符 = + － * / ＜ ＜＝ ＞ ＞＝ ＝＝　!＝ || , : ; { } [ ] ( ) ID和NUM的正规定义式为： ID→letter(letter | didit)* NUM→digit digit* letter→a | … | z | A | … | Z digit→ 0 | … | 9 如果关键字、标识符和常数之间没有确定的算符或界符作间隔，则至少用一个空格作间隔。空格由空白、制表符和换行符组成。 (3) 设计词法分析器的步骤： 首先根据上面单词符号表及ID和NUM的正规定义式，构造出状态转换图； 定义相关的变量和数据结构。关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： char *KEY_WORDS[7]={″main″,″int″,″char″,″if″,″else″,″for″,″while″}；i = 10; while(i) i = i - 1; } 输出如下二元式代码序列： (1,main) (26,() (27,)) (30,{) (2,int) (10,i) (21,=) (20,10) (34,;) (7,while) (26,() (10,i) (27,)) (10,i) (21, =) (10,i) (23,-) (20,1) (34,;) (31,}) 实验二 NFA的确定化 1．实验目的 设计并实现将NFA确定化为DFA的子集构造算法，从而更好地理解有限自动机之间的等价性，掌握词法分析器自动产生器的构造技术。该算法也是构造LR分析器的基础。 2．实验要求 设计并实现计算状态集合I的ε闭包的算法ε_Closure(I)和转换函数Move(I,a)，并在此基础上实现子集构造算法Subset_Construction。利用该从NFA到DFA的转换程序Subset_Construction，任意输入一个NFA N=（S,Σ,δ,s0,F），输出一个接收同一语言的DFA M=（S’,Σ,δ’,s0’,F’）。 3．实验内容 令I是NFA N的状态集S的一个子集，I的ε闭包的ε_Closure(I)构造规则如下： 若s∈I，则s∈ε_Closure(I)； 若s∈ε_Closure(I)且δ(s, ε)=s’而s’ ?ε_Closure(I) ，则s’∈ε_Closure(I) 根据上面的规则，下面给出了一个计算I的ε闭包的算法ε_Closure(I)。 SET S; SETε_Closu