编译原理实验指南

1、编译原理实验指南计算机与软件学院软件工程系蔡树彬目 录目 录2实验一、文件读写操作6（一）.实验目的6（二）.预备知识61.文件名62.文件路径63.文件File74.读文件BufferedReader75.写文件PrintWriter86.文件异常与关闭文件8（三）.实验内容91.路径92.读文件93.写文件94.简单处理10实验二、集合与线性表操作11（一）.实验目的11（二）.预备知识111.集合和线性表的基本操作112.Collection113.泛型（Generic）134.集合与线性表基本操作的使用13（三）.实验内容141.字符集合142.产生式153.产生式栈15实验三、文法类

2、的设计17（一）.实验目的17（二）.预备知识171.类与对象172.文法定义173.异常与异常处理184.字符集V的闭包V*19（三）.实验内容191.产生式（集）类的设计192.文法类的设计203.直接推导的判断214.推导的判断21实验四、文法的化简22（一）.实验目的22（二）.预备知识221.等价文法222.无用符号和无用产生式223.删除不可终止符号的算法234.删除不可达符号的算法23（三）.实验内容241.无用符号和无用产生式的删除242.单产生式的消除24实验五、无符号数的识别25（一）.实验目的25（二）.预备知识251.图和矩阵252.Switch语句25（三）.实验内容

3、261.编写一个识别无符号数的程序262.编写一个识别有理数的程序26实验六、DFA类的设计27（一）.实验目的27（二）.预备知识271.DFA272.转换函数f 与映射Map273.字符串识别算法28（三）.实验内容291.设计DFA类292.DFA对象的生成293.字符串的识别29实验七、NFA类的设计与确定化30（一）.实验目的30（二）.预备知识301.NFA302.e-NFA303.求e闭包的算法314.e-NFA的确定化算法31（三）.实验内容321.e-NFA类的设计与确定化322.NFA的字符串识别32实验八、由正则表达式构造e-NFA33（一）.实验目的33（二）.预备知识

4、331.正则表达式332.Thompson算法333.运算优先级与后缀表达式35（三）.实验内容351.将中缀的正则表达式转换为后缀的正则表达式352.实现Thompson算法36实验九、基于正则表达式的词法分析器（综合）37（一）.实验目的37（二）.预备知识371.由正则表达式构造e-NFA372.e-NFA的设计与确定化373.DFA的设计与字符串识别374.识别结果的输出37（三）.实验内容381.改进DFA的输出382.从正则表达式到DFA的串联383.实现基于正则表达式的词法分析器38实验一、递归下降分析法39（一）.实验目的39（二）.预备知识391.递归392.非终结符与递归调

5、用39（三）.实验内容401.调用词法分析器402.实现递归下降分析法403.文法扩展40实验一一、语法树的设计41（一）.实验目的41（二）.预备知识411.树412.语法树上的一些概念41（三）.实验内容421.设计语法树类422.语法树的输出42实验一二、First集与Follow集的构造43（一）.实验目的43（二）.预备知识431.First集和Follow集432.First集的构造算法433.Follow集的构造算法44（三）.实验内容451.读入文法452.求任意字符串的First集453.求全部非终结符的First集45实验一三、LL分析法46（一）.实验目的46（二）.预备

6、知识461.First集和Follow集462.LL（1）文法463.LL（1）分析表464.LL分析总控程序47（三）.实验内容481.LL(1)分析表的构造482.LL(1)分析法483.构造语法树48实验一四、LR分析法（综合）49（一）.实验目的49（二）.预备知识491.LR(0)项目类492.LR(0)项目的闭包493.活前缀DFA504.LR(0)分析表的构造505.LR分析总控程序51（三）.实验内容521.活前缀DFA的构造与输出522.LR（0）分析表的构造523.LR分析法的实现524.SLR(1)分析表的构造525.LR(1)分析表的构造53实验一五、整数算术表达式的翻

7、译（综合）54（一）.实验目的54（二）.预备知识541.词法分析542.语法分析543.语法制导的翻译模式544.整数算术表达式的语法动作55（三）.实验内容561.建立语法树562.设计整数算术表达式文法所有产生式的语义动作563.实现整数算术表达式的翻译56实验一、 文件读写操作（一）. 实验目的编译器读取源程序文件，经过分析处理，再生成目标文件。这个过程的前后2端都需要进行文件的读写操作。本实验关注文件读写操作，为后续实验做好准备。（二）. 预备知识1. 文件名文件名称及后缀等基础知识，这里不一一进行介绍。2. 文件路径读写一个文件需要用到文件的路径，而文件的路径又可分为绝对路径和相对

8、路径。绝对路径是文件的完整路径，如d:projecthellosrcHello.java。因为工程开发与部署环境存在差异，一般少用绝对路径。相对路径是文件的部分路径，如srcHello.java。如果当前项目在d:projecthello下运行，则完整路径是d:projecthellosrcHello.java。这种形式使得文件路径具有一定的灵活性，较常使用。在Java中可以通过System.getProperty("user.dir")获取当前路径。在Eclipse项目中运行程序时，当前路径是项目的根目录。如工作空间在d:project，当前项目名称是hello，则当前路

9、径是：d:projecthello。在控制台下运行程序时，当前路径是class文件所在的目录，如果class文件包含包名，则以该class文件最顶层的包名作为当前路径。在Java代码内书写文件路径时，需注意大小写和的转义。如“d:projecthellosrcHello.java”，须为“d:projecthellosrcHello.java”或“d:/project/hello/src/Hello.java”。3. 文件FileJava中，文件（及其路径名）可以使用类File来表示。一般情况下，可以使用File(String pathname)来构造文件对象。如：File aFile=new

10、 File("a.txt")。然后使用aFile.canRead()等方法，判断是否具有文件读写权限。注意：File对象可以代表尚未存在的文件或目录。例如，aFile=new File("a.txt")，但当前目录下，并不存在“a.txt”，这是允许的。此时，读取aFile文件的内容，将得不到任何内容。但可以通过向aFile里面写入内容，使系统创建“a.txt”文件。4. 读文件BufferedReader为了一次性读入一行数据，通常使用BufferedReader这个类来读文件。又因为构造BufferedReader对象时，需要使用Reader对象，所

11、以一般通过构造一个FileReader对象来构造BufferedReader对象。如BufferedReader br=new BufferedReader(new FileReader(aFile)。然后，可使用br.readLine()方法来一次读入一行数据。其他方法就不再这里一一列举。5. 写文件PrintWriter 写文件通常使用PrintWriter。如PrintWriter pw=new PrintWriter(aFile)。之后可使用pw.println()等方法来一次写入一行数据。如不指定pw自动flush缓冲区，则在向pw中写入一定数据后，需要手动进行flush()。6.

12、文件异常与关闭文件（打开）、读写文件时，可能出现FileNotFoundException、IOException等文件异常。因此对文件的读写操作，需要放在trycatch块中。如try PrintWriter pw = new PrintWriter(aFile);BufferedReader br=new BufferedReader(new FileReader(otherFile); catch (FileNotFoundException e) catch (IOException e) 读写完文件之后，就需要关闭文件。如br.close()、pw.close()了。（三）. 实验内

13、容1. 路径a) 输出当前路径b) 在C盘根目录和当前目录下分别创建文件“AbsPath.txt”和“RelPath.txt”。2. 读文件a) 打开“AbsPath.txt”和“RelPath.txt”，在里面分别录入2个句子，如“hello world”等。b) 打开“AbsPath.txt”、“RelPath.txt”，文件内容显示到屏幕上。3. 写文件a) 打开“AbsPath.txt”和“RelPath.txt”，通过程序在里面分别写入1个短句（100字以内）和1个长句（1024字以上）并保存。b) 重新读取“AbsPath.txt”和“RelPath.txt”的内容并显示在视频上，

14、比较写入 à 读取 à 输出的内容是否完全相同。4. 简单处理a) 在“RelPath.txt”文件中，粘贴一段英文段落。b) 编写程序，读入RelPath.txt中的数据，将英文段落中的单词（空格隔开），按一个一行的次序，分别输出到另一个文件“Out.txt”中，并且同时也打印到屏幕上。实验二、 集合与线性表操作（一）. 实验目的编译器处理源程序文件的过程中，集合、链表、栈是经常出现的数据结构。与数据结构课程关注集合、线性表的编程实现不同，本实验关注它们的使用。在Java语言中，集合和线性表分别就是Java工具类Util包中的Set和List两个接口。特别的，本实验关注H

15、ashSet、ArrayList（或Vector）和Stack（它们分别是集合、链表和栈的实现类）的使用，为后续实验做好准备。（二）. 预备知识1. 集合和线性表的基本操作集合和线性表（链表和栈）的基本操作是数据结构课程的基础知识，这里不一一进行介绍。2. Collection在Java中，集合容器(Collection)是一个对象的容器，可以存放一组对象，主要用来组织和管理存放在容器中的对象。注：Java中，集合Set继承了Collection，因此Collection很难翻译。目前较多情况下仍将Collection译为“集合”，如“Java Collection Framework”，一般

16、译为“Java集合框架”。但要注意，此时的“集合”指Collection。其它情况下，集合指Set。其中，常用的几个实现类如下： HashSet 使用散列算法实现Set接口 TreeSet 使用平衡二叉树算法实现SortedSet接口 ArrayList 使用数组存放对象来实现List接口 Vector 与ArrayList的区别在于Vector是同步、线程安 全的，而ArrayList是异步、线程不安全的。性能上，Vector比ArrayList低。 Stack 上图没有画出，它是Vector的直接子类，实现了栈的基本操作。 LinkedList 使用双向链表来实现List接口3. 泛型（G

17、eneric）注：泛型与范型同音，但意义相差甚远。范型（Paradigm）的范，指一种规范的、可作为模范的样式、范例，也译为范式。如OO范式等，包含了面向对象编程许多方面的内容，与面向过程的范式作为区别。泛型（Generic）的泛，指的是泛化的含义，因为Generic是“类属的”的意思。在C+中，泛型就是“模板（Template）”。因为同音的缘故，许多网络上的文章，把“泛型”误为“范型”，要特别注意区分。泛型的例子如下：Set<Object>，一个存放元素是“Object”的集合；Set<String>，一个存放元素是“String”的集合；Stack<Inte

18、ger>，一个存放元素是“Integer”的集合；Stack<aUserDefinedClass>，一个存放由用户定义的类的集合4. 集合与线性表基本操作的使用通常使用形如 Set<Integer> si=new HashSet<Integer>();来声明一个存放整数的集合（注：类Integer可换成其它自定义的类）。然后，可使用si.add(new Integer(5);来向集合中插入一个元素“5”；再使用si.contains(new Integer(5)来判断集合中是否包含元素“5”；再使用si.remove(new Integer(5);来从

19、集合中删除元素“5”。若要遍历访问集合si中的全部元素，则需要使用迭代器Iterator。通过Iterator<Integer> it=si.iterator();取得si的迭代器，再通过判断while(it.hasNext() /是否遍历到最后一个元素，若是最后元素， /则hasNext为假，否则为真Integer i=it.next(); /访问当前元素/do something，对当前元素i进行操作 。线性表的声明、操作与集合的声明、操作非常类似，只是换了一个类名而已。如声明Stack<String> ss=new Stack<String>为一个存放

20、字符串的栈，然后可通过ss.peek()、ss.push(aString)、ss.pop()来访问栈顶元素、进行入栈和出栈操作。 需要特别注意的是，集合Set不重复保存相同元素。那么，Set要如何做，才能判断一个元素是否跟另一个元素相同？答案就是o.equals(e)。如果元素o、e都不为空，并且o.equals(e)，那么集合Set就认为o和e是相同的元素。对基本数据类型，如Integer、String等，因为语言已经实现了对应的equals方法，所以可以直接使用。若集合中的元素是自定义的类，那么，则需要考虑应如何实现equals方法。在C+的STL库中，则要实现的是小于等于的LE方法。（三

21、）. 实验内容1. 字符集合a) 声明一个存放非终结符的集合sc。考虑应拿什么数据类型或数据结构保存非终结符？b) 从文件“NonTerminal.txt”中读取所有的非终结符。文件内容如下：a, b, c, d.也即使用逗号分隔非终结符，使用句话表示输入结束。c) 使用迭代器遍历读入的非终结符，按一行输出一个非终结符的方式，显示在屏幕上，并同时写入到另外一个文件中。2. 产生式a) 产生式是形如“A è aB”之类的式子，由产生式左侧和产生式右侧2个部分组成，中间的“è”用处在于显示的时候可以分隔2端，并没有特别含义。如果我们只处理2型和3型文法，即上下文无关文法和线性文

22、法，那么，产生式应如何设计怎样的数据结构来保存产生式。换句话说，产生式类应如何设计?b) 特别的，产生式类中，equals（或LE）方法，应如何实现？3. 产生式栈a) 声明一个存放产生式的栈。产生式使用内容2中的产生式类。b) 从文件“Production.txt”中读取所有的产生式。文法的内容如下：A -> aBC -> sdfdf也即一行一个产生式，产生式中间的分隔符是“->”（或其它，可自己再定义），一直到文件结束。c) 将读入的产生式，按栈先进后出（First In Last Out FILO）的次序，一行一个在屏幕上显示出来，并写入到另外一个文件中。实验三、 文法

23、类的设计（一）. 实验目的词法分析和语法分析是编译器的重要组成部分，而文法正是词法和语法的共同理论基础。本实验要求设计一个文法类，通过动手编程，加深对抽象的文法定义的理解。（二）. 预备知识1. 类与对象类与对象是面向对象程序设计的核心思想。作为编程语言课程的基础知识，这里不再赘述。2. 文法定义一个文法GS可表示为形如（VN，VT，P，S）的四元组，其中VN，VT和P是非空有限集合，分别称为非终结符集、终结符集和产生式集，SVN称为文法的开始符号，并且VNVT=Æ，V=VNVT称为文法的字母表。首先，文法的定义里面，出现3个集合和一个集合的元素。有关集合的操作，我们已在实验二、中进

24、行了介绍。其次，对非终结符和终结符，我们采用与课本相同的方式，使用大写字母表示非终结符，小写字母表示终结符。因为大小写字母均可采用基本数据类型char表示，所以我们可以使用数据结构set<Character>来表示非终结符集和终结符集。最后，对产生式集，集合的元素是一个产生式。产生式是一个有结构的事物，例如 A ® ab， 由3个部分组成，左边的非终结符A（我们仅处理2、3型文法），中间的“®”符号和右边的字符串“ab”。其中，对任意产生式来说，中间的“®”符号都是相同的，仅用于区分产生式的左右两边，我们也可以用“:=”等其他符号替换。产生式左右两侧的

25、符号和符号串，才是我们需要重点关注的内容。因此，我们可以设计一个产生式类，来保存产生式的左部和右部，该类还有一个静态的属性，表示产生式终结的“®”符号。3. 异常与异常处理文法一开始保存在一个文件中，然后由文法类读入内存并产生相应的文法对象。那么，文件中描述的“文法”，可能并不是一个合法的文法，例如，终结符集和非终结符集有交集，那么，文法对象就不能正常产生，此时文法类应该抛出一个文法初始化异常。既然要抛出异常（Exception），那么相应的，需要设计一个异常类（或直接使用系统的异常类）。另外，读入文法时，就应该进行异常的捕获与处理。假设设计了一个异常InvalidGrammarEx

26、ception（继承了系统异常Exception），并且在判断读入文法无效时抛出 throw new InvalidGrammarException(s); /s是一个字符串那么，在恰当的地方，就应该try /从文件读入一个文法；catch(InvalidGrammarException e)/利用e传来的信息进行相应处理；4. 字符集V的闭包V*字符集V的闭包V*= V0V1V2是经常出现的符号。但是在程序中，我们无法表示这样一个具有无穷元素的集合。为了判断字符串vV*是否成立，我需要反过来，检查v中每个字符，是否属于V，也即需要设计一个判断方法，使得能够依据如：for(int i=0;i&

27、lt;v.length();i+) if (!viV) return false; return true; 来判断字符串vV*是否成立。（三）. 实验内容1. 产生式（集）类的设计产生式左部是一个大写字母表示的非终结符，可以使用数据类型char表示；产生式右部是一个字符串，可以使用数据类型String表示；产生式中间的分隔符“® ”，在文件中不容易输入、输出，可自己采用其它形式的分隔符（静态变量）；对产生式集，一种考虑是，我们可以直接使用语言自带的集合Set<>来实现。另一种考虑是，我们在产生式集上，经常要寻找左部相同的产生式，如所有的A产生式，或者要寻找所有右部包含字

28、符A的产生式等操作。因此，我们可以设计一个新的产生式集合类。实现的方法有2种，一种是直接继承已有的集合实现类HashSet<>，另一种是采用组合的方式，组合一个集合实现类。尽管现在编程方面，比较推荐的是多用组合/聚合，少用继承，但对产生式集合这个例子来说，并不违背继承的要求，这2种做法都可考虑。2. 文法类的设计如上分析，文法类的主要属性由这几个部分组成，首先是三个集合，分别是两个Set<Character>表示终结符集和非终结符集，还有一个Set<Production>（或ProductionSet）表示产生式集，另有一个特殊的开始符号S是一个char。文

29、法保存在文件中，因此需要设计一个方法，从文本文件中读取文法信息并创建文法类。文件中，文法是如何表示的，就需要进行约定、设计。简单地说，可以假设第一行输入的字符（空格隔开）是非终结符，第二行的是非终结符，第三行是开始符号，最后产生式集合，产生式之间用空格隔开，使用 => 表示。然后再将读入的内容，特别是产生式的数据，进行处理，生成产生式对象，再保存到文法类的产生式集属性中。又由于文法必须满足一定的规则，因此，在构造文法对象的时候，需要判断从文件读入的文法是否有效。若无效，则需要抛出文法构造异常，否则，构造出相应文法对象并返回。3. 直接推导的判断构造了文法对象后，我们可以使用“直接推导”的

30、定义，来判断输入的2个字符串a和b之间是否存在“直接推导”的关系。简言之，即能否由a直接推导出b。简单的判断方式是，遍历字符串a中每个字符，如果ai是一个终结符，则i+；否则，也即ai是一个非终结符，记为A，则取出所有的A产生式，分别将ai替换为各个A产生式的右侧，再判断产生出来的字符串是否与b相同，若相同则a可直接推导出b。4. 推导的判断推导的判断比较复杂，简单说，就是如果字符串a使用多步直接推导，能得到字符串b，则a可以推导出b。但是，在使用直接推导的时候，可能陷入死循环等错误，要注意。该方法的实现，允许存在bug。实验四、 文法的化简（一）. 实验目的本次实验主要是在实验三、文法类设计

31、的基础上，删除文法中的无用符号和无用产生式，化简文法。通过实验，加深对产生式、推导和语言等文法核心概念的理解。（二）. 预备知识1. 等价文法对两个文法G1和G2，如果L(G1)=L(G2)，那么我们称文法G1和G2等价。文法化简的目标，就是找到一个与旧文法G1等价的新文法G2，使得G2中终结符集、非终结符集和产生式集的基数（即元素个数），都小于等于它们在G1中的对应物。2. 无用符号和无用产生式简言而，若文法中一个符号v是无用符号，则v要么是不可终止的，要么是不可达的。所谓不可终止，是指一旦产生的字符串里面出现了字符v，则由该字符串推导出去的任意其它字符串，都不可能最后推导产生出句子，即陷入

32、死循环，无法形成终结符号串。所谓不可达，是指无法从开始符号S，推导产生某个字符v。也即v一定不会出现在句子中。删除文法中的无用符号和无用产生式，是简单而要必要的。3. 删除不可终止符号的算法核心步骤是：1：求Vn。判断每一条产生式，若产生式右边所有字符都是终结符，则将产生式左部的非终结符放到Vn中；2：不断扩充Vn直到不再扩大为止。循环遍历每条产生式，若产生式右边所有字符都属于VtÈVt,则将该产生式左边的非终结符也加入到Vn中。若集合Vn的元素增加，则再次遍历所有产生式，直到在一次循环中，Vn的元素不再增加为止。3：求新的产生式集P。对每条产生式，若产生式左右两边的所有字符都属于V

33、t È Vn，则将该产生式放到P中。4. 删除不可达符号的算法核心步骤是：1：将文法的开始符置于Vn中；2：循环遍历每条产生式，若产生式左边的非终结符属于Vn，则将其右边各字符分别放到Vn和Vt中，遍历结束后判断Vn或Vt的元素是否增加，若增加则再次遍历，直到2个集合的大小都保持不变为止。3：遍历每条产生式，若其产生式左右部的字符都属于Vn和Vt则将该产生式其放到P中。（三）. 实验内容1. 无用符号和无用产生式的删除在文法类里面，增加一个新的方法，成为无用符号和无用产生式的删除方法，调用该方法，则可以得到对当前文法进行化简后产生的新文法。2. 单产生式的消除单产生式是型如“A

34、74;B”的产生式。通常这类产生式也需要进行化简消除。简言之，消除“A®B”产生式的基本思想，就是找到“B”可产生的所有非单产生式b1，bn，然后替换“A®B”为一系列产生式“A®b1”，“A®bn”。实验五、 无符号数的识别（一）. 实验目的本次实验相对简单，主要是通过编写一个识别无符号数的程序，来了解状态转换图和状态矩阵的作用，为后续确定有限自动机的学习打下基础。（二）. 预备知识1. 图和矩阵图是一种重要的数据结构，它的存储方式有邻接矩阵和邻接表等，这些在数据结构课程已经介绍过，这里不再赘述。2. Switch语句本次实验，处理的是特定的图（识别无

35、符号数的状态转换图），因此也可以不使用数据结构存储这张图，而是用“硬编码”的形式，将状态的转换硬编码成嵌套的switch语句。例如，使用：switch (当前状态) case 某个状态：switch (遇到字符) case 某类字符： do something break;case 某类字符： do something break;break;case 某个状态：switch (遇到字符) break; 来实现无符号数的识别。（三）. 实验内容1. 编写一个识别无符号数的程序无符号数的状态转换图可参见课本P51页的图3-3，状态矩阵可参加P55页的表3-1，识别程序（框架）可参加P57的程序3

36、-3。2. 编写一个识别有理数的程序因为在程序中输入的表示数字的符号串都是有限长的，因此程序中出现的数，实际上都是有理数。前面已经完成了一个识别无符号数的程序，那么，在这个基础上，实现一个既能识别无符号数，又能识别有符号数的有理数识别程序。实验六、 DFA类的设计（一）. 实验目的确定的有限自动机是进行词法分析的主要工具。本次实验要求设计一个DFA类，并完成基于DFA的字符串识别方法，通过动手实验，加深都抽象的DFA的理解。（二）. 预备知识1. DFA确定的有限自动机DFA是一个型如(K,f,S0,Z)的五元组，其中K是状态集，S是字符集，f:K´S® K是状态转换函数，

37、S0是开始状态，Z是终态集。DFA的核心是转换函数f。2. 转换函数f 与映射Map转换函数f的实现是本次实验的核心内容。可以采用多种方式表示转换函数。例如，实验五、使用“硬编码”的方式，将一个固定的转换函数编码到程序中；在数据结构课程中，我们使用邻接矩阵和邻接表来表示“图”上的任意两个顶点间是否存在一条边（这是一个从顶点和顶点的笛卡儿积到布尔类型的函数：V´V®B）。更一般的方式，函数可以使用映射类Map来实现。简单地说，Map按（键Key，值Value）对的形式存储数据。对同Map中的一个Key，就有一个Value与其关联。若已知函数f(x)=y，那么x就是Map中的K

38、ey，y就是Value。那么，为了存储转换函数，我们可以利用泛型技术，设计一个从K´S到K的映射，例如，Map<x，K>。这是，又出现一个问题，x应该是什么？x应该是K´S，也就是说，我们还需要再设计一个类，表示K´S的笛卡尔积。假设我们设计了一个类KC表示K´S的笛卡尔积，那么映射Map<KC，K>就可以表示我们需要的转换函数f:K´S® K了。至于Map上的操作，如利用put操作构造所需的f，利用get操作获取函数值等，则可参考相应API说明，这里就不再赘述了。3. 字符串识别算法有了映射Map<KC

39、，K> f后，识别输入的字符串s是否能被自动机所识别的算法，就可以进行设计了。1：取初态S0、s首字符c，构造f的输入参数kc2：令nextS=f.get(kc)，若nextS和s下一个字符c不为空，则取nextS、c构造新的输入参数kc，继续步骤2；直到nextS或s下一个字符c为空3：如果c为空并且nextS是终态，则字符串s被自动机识别；否则不被识别。（三）. 实验内容1. 设计DFA类因为DFA是一个五元组，因此DFA类的属性至少应该有5个，分别是状态集、字符集、转换函数、初态和终态集。其中有3个集合，可使用大写字母或数字表示状态，小写字母表示字符，转换函数则可用前面讨论的映射表

40、示。2. DFA对象的生成我们需要从文本文件中读入一个DFA并生成相应的DFA对象。此时就需要约定文本文件的格式。例如，如何表示转换函数f。一种简单的约定，可以是第一行是大写字母表示的状态集，用空格隔开；第二行是小写字母表示的字符集，用空格隔开，第三行是单个大写字母表示初态；第四行诗大写字母表示的终态集合，用空格隔开；第五行开始，每行是一个型如(A,a)®B的式子，表示在状态A时，遇到字符a，转换到状态B。需要注意的是，与文法的读入类似，读入的DFA文本文件也可能包含错误，此时就应该检查DFA的有效性并在生成DFA无效时抛出异常。3. 字符串的识别具体算法如前所示，输入任意字符，判断

41、DFA对象能否识别。实验七、 NFA类的设计与确定化（一）. 实验目的通过设计NFA类，掌握NFA与DFA的区别与联系；通过实现NFA的确定化算法，掌握NFA的确定化过程。（二）. 预备知识1. NFA不确定的有限自动机NFA是一个型如(K,f,S0,Z)的五元组，其中K是状态集，S是字符集，f:K´S®r(K)是状态转换函数，S0是开始状态，Z是终态集。NFA与DFA的区别仅在于转换函数f。DFA是f:K´S®K，而NFA是f:K´S®r(K)，一个是转换到一个状态，另一个是转换到一个状态的集合。在实现上，NFA的转换函数与DFA的

42、转换函数的差异，仅在于Map的值类型，一个是K，一个是Set<K>。 2. e-NFA带e的不确定有限自动机e-NFA在NFA的基础上，转换函数f又有了一点变化，f:K´(SÈe)®r(K)，即转换边上，既可以是字符集S中的一个字符，也可以是一个特殊的空串。在实现上，这意味着要改变f的输入参数KC。有3种实现的方式，一种是选取一个特殊的符号，例如e来表示空串；另一种是改变C的数据类型为字符串，S中的字符则变成是由单个字符组成的字符串，e则是空串“”；还有一种方法是允许C的取值为空来表示空串。这3种方法在使用起来各有优缺点，可根据自己的习惯选用。3. 求

43、e闭包的算法求集合S的e闭包的算法，核心步骤如下：1：将集合S中的每个元素，都放入S的e闭包和待扩展集合E中；2：取出待扩展集合E中的一个si，利用fNFA.get(si, e)取出si经过e边转移到的状态集合NSi，将NSi中不属于S的e闭包的元素，同时放入S的e闭包和待扩展集合E中；3：重复步骤2直到E为空，则求出了S的e闭包。4. e-NFA的确定化算法NFA的确定化和e-NFA的确定化算法，在核心过程上是相同的。区别仅在于e-NFA的确定化时，需要求当前状态集的e-closure。对不带e的NFA而已，一个状态集的e闭包显然等于自身。因此不再额外实现不带e的NFA的确定化算法，而仅实现

44、一个e-NFA的确定化算法。1：求开始状态S0的e闭包，标记为新状态q0，并将q0放入待扩展状态集中，记新状态个数为1；2：取出待扩展状态集中的一个元素qi=Si1,Sin，2.1 依次取出字符集中的每个字符aj，2.1.1 对qi中每个状态Sik，1£k£n，构造输入参数pk=(Sik, a j)，再令rk=fNFA.get(pk)，rt=，求出qt=e-closure(rt)；：若qt为新出现的r(K)的元素(新的状态集)，则令t=新状态个数，并将qt放入带扩展状态集中，新状态个数+1；否则令t=已有r(K)元素(已有的状态集)对应的新状态下标；：最后记录，fDFA.p

45、ut(qi，aj)，qt) 3：重复步骤2直到待扩展状态集为空；4：以fDFA 为基础，构造相应的DFA。（三）. 实验内容1. e-NFA类的设计与确定化NFA类在实验中的作用、意义较小，故可直接设计e-NFA类。在完成e-NFA类的设计后，根据预备知识中的确定化算法，实现e-NFA的确定化。2. NFA的字符串识别有了确定化算法之后，NFA的字符串识别算法就有两种：一种是直接利用NFA，采用深度（或宽度）优先搜索的方法，利用输入的字符串，直接在NFA上寻找一条从初态到终态的路径。 令一种是将NFA确定化为DFA，再利用DFA进行字符串的识别。实现这两种字符串识别算法，并分析对比它们的时空效

46、率。实验八、 由正则表达式构造e-NFA （一）. 实验目的根据正则表达式，采用Thompson算法，构造e-NFA，深入理解正则表达式与NFA的关联，为后续实验打好基础。（二）. 预备知识1. 正则表达式利用连接运算符“·”（通常省略）、选择运算符“|”和闭包运算符“*”构成的的字符串正则表达式，可方便描述各种常见的“单词”。除了在编译器中，在其他需要进行文本处理的场合也非常常见。近年来，正则表达式非常流行。例如，Jeffrey E.F. Friedl专门介绍正则表达式的Mastering Regular Expressions（译文版精通正则表达式）都已经出了第3版。尽管课程介绍

47、的正则表达式仅是正则表达式的一个子集，但通过对这种简单正则表达式的学习、使用，非常有利于我们更好的掌握java（以及其他语言）中的正则表达式。更多关于正则表达式的内容，请参考精通正则表达式（第3版）。2. Thompson算法Thompson算法是基于正则表达式的运算符，递归构造出识别语言与正则表达式对应的语言等价的e-NFA。简单说，对r1|r2、r1r2和r*，分别构造出如下图的e-NFA。r1|r2 Þ e-NFAr1r2 Þ e-NFAr* Þ e-NFA当n=0时，直接构造出相应的e-NFA则非常简单，这里就不一一列出了。3. 运算优先级与后缀表达式Th

48、ompson方法构造e-NFA的过程，需要按运算符运算次序进行递归构造。但我们通常输入的正则表达式，采用的是中缀表达式的形式，隐含了运算符间的运算优先级。此时直接按从左到右的方式进行递归、运算构造出的e-NFA并不恰当。为了解决这个问题，也有3种不同的思路。一种是直接约定，3个运算符的运算优先级相同，按从左到右的优先级进行运算，但这个方法有悖我们常识，并不建议；另一种是，要求每个运算符都需要放在独立的括号中，这也是我们课本上介绍正则表示式时采用的方法，例如(a|b)|(c*)。这种方式通过()解决了运算符间的优先级问题。相对来说，容易实现又不会违背常识，但是这样的正则表达式写起来就有点麻烦。最

49、后一种方法是，使用我们通常的带优先级的中缀表达式方法书写正则表达式，再设计算法，将中缀表达式转换成后缀表达式。该算法在数据结构课程已有介绍，直接利用一个栈和一个优先函数即可，这里就不展开介绍了。（三）. 实验内容1. 将中缀的正则表达式转换为后缀的正则表达式简单地说，就是碰到操作数（字符）的时候，直接输出；碰到运算符的时候，则比较当前运算符与栈顶运算符的优先级，根据优先级的大小，确定是否入栈、出栈。2. 实现Thompson算法利用步骤1得到的后缀表达式，按运算符进行递归，构造出符合要求的e-NFA。实验九、 基于正则表达式的词法分析器（综合）（一）. 实验目的本次实验是词法分析一章内容的综合

50、实验，要求将前面正则表达式、NFA、DFA的实验串联起来，实现一个基于正则表达式的词法分析器。通过该实验，梳理词法分析相关知识点，加强对词法分析的认识和理解，掌握正则表达式和DFA的应用。（二）. 预备知识1. 由正则表达式构造e-NFA 具体内容见实验八、2. e-NFA的设计与确定化具体内容见实验七、3. DFA的设计与字符串识别具体内容见实验七、 4. 识别结果的输出词法分析器识别出各个类别的单词后，需要按（类别、值）的形式，依次输出源程序中的各个单词。这个输出的类别码，我们需要在最开始由正则表达式构造出的e-NFA处指定。若最后得到的DFA，在同一个状态上有多个输出类别码，则意味着出现

51、二义。通常我们可以采用直接指定优先级的方法，解决这种二义性。例如，按照“标识符”的定义，所有的“关键字”都满足。但“关键字”的优先级明显高于“标识符”，因此，对关键字，输出的（类别，值）对，应该是（关键字，具体值）或者（关键字，关键字）。（三）. 实验内容1. 改进DFA的输出改进实验六、DFA识别出字符串后的结果输出部分，使得能够输出我们想要的（类别、值）单词序列。2. 从正则表达式到DFA的串联将实验八、实验七、实验六、串联起来，形成从正则表达式到基于DFA的字符串识别的完整过程。3. 实现基于正则表达式的词法分析器设计一个语言的词法规则，包括对应的正则表达式和输出预期，再利用步骤2的结果

52、，完成一个完整的基于正则表达式的词法分析器。实验一、 递归下降分析法（一）. 实验目的本次实验相对简单，主要是采用递归下降分析法，编写一个程序，判断由四则运算表达式语句组成的源代码，是否满足给定语法要求。通过动手编程，加深对自顶向下语法分析的理解，为后续LL（1）语法分析的学习打下基础。（二）. 预备知识1. 递归递归显然是递归下降分析法的核心内容。但递归作为程序设计语言的重要基础，应该已在基础课程中学习掌握。若在递归的上有困难，请及时复习之前的课程，此次不复赘述。2. 非终结符与递归调用在递归下降分析法中，每个非终结符都被设计为一个函数。对型如A®BC的产生式，在函数A()中，将会

53、依次调用函数B()和C()。在函数B()、C()中，相应的，若B产生式、C产生式中出现了非终结符，也必然会出现对那个（些）非终结符对应函数的调用。因为通常产生式中都会出现递归（否则就只能产生可枚举的有限语言），所以对非终结符的调用，递归情况几乎不可避免。也因此这种分析方法被称为递归下降分析法。所谓下降，是指这种分析方法，会逐渐向终结符靠拢，从树根，逐渐往叶子的方向生长，直到最后遇到终结符，不能再调用其它非终结符对应的函数，结束递归。（三）. 实验内容1. 调用词法分析器语法分析的输入，即是词法分析的输出。所以本次实验需要完成前面的词法分析实验，调用前面词法分析的结果。当然，由于本次实验要处理的

54、“单词”种类较少，也可直接在这里编写相应的词法分析程序，从源代码中，提取所需“单词”。2. 实现递归下降分析法递归下降分析法所使用的语法可参见课本P113页的例4.2，文法Gstatements或P116的文法G'statements。递归下降语法分析程序框架可参加课本P114页的程序4-1、116页的程序4-2和P118页的程序4-3。3. 文法扩展在课本P113的文法Gstatements（或P116的G'statements）的基础上，设计还能允许出现“赋值语句”的文法，并完成相应的实现代码。实验一一、 语法树的设计（一）. 实验目的语法树是编译器语法分析、语义分析和中间

55、代码生成3大主要阶段的核心数据结构，也因此是编译器的核心数据结构。通过设计并实现一个语法树类，加深对语法树的理解，为后续采用多种语法分析方法来建立语法树打下基础。（二）. 预备知识1. 树树是非常重要的数据结构，在数据结构课程里也经过了重点学习。这里只着重指出两点：1）树是由树根和子树构成的，树可以为空；2）语法树是一棵多叉树，而不是二叉树。2. 语法树上的一些概念在语法树中，若存在一个父子结构，即父亲节点A和所有的（直接）孩子结点组成的字符串a，则必然存在产生式A®aÎP。语法树上，任意一棵子树的叶子串，都是相对于子树根的短语；高度为2的子树，则是对应句型的直接短语；最左

56、边的高度为2的子树，就是当前句型的句柄。自顶向下的语法分析方法，从树根开始，不断利用产生式，产生父子结构，向目的句型生长。自底向上的语法分析方法，从句子（句型）开始，不断利用产生式，规约出相应的父子结构，向树根方向生长。语法树的内部节点，必然是非终结符；但语法树的叶子节点，不一定是终结符。（三）. 实验内容1. 设计语法树类语法树由2个部分组成，一部分是可以为任意字符的树根，另一部分是有序但个数不限的子树。所以语法树SyntaxTree的树根可以用数据类型char保存，子树可以用子树列表List<SyntaxTree>保存。此外，语法树上还需要有根据产生式生成子树的方法, addSubtreesFrom(Production p)；根据产生式，归约得到父亲结点的addParentFrom(Production p)方法；以及找到当前语法树句柄的getHandler()方法。2.