资源描述：
《正则表达式有限自动机NFA课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、编译原理与技术课程总结课程目录第1章概论第2章词法分析第3章语法分析第4章语法制导翻译生成中间代码第5章运行环境第6章代码生成第1章概论1．编译器：先翻译后执行，工作效率高，即时间快、空间省；交互性与动态特性差、可移植性差。大多数PL采用此种方法翻译；2．解释器：边翻译边执行，工作效率低，即时间慢、空间费；交互性与动态特性好、可移植性好。早期的Basic和现在的Java等。编译与解释是语言翻译的两种基本形式编译过程1．编译器的工作过程：词法分析、语法分析、语义分析中间代码生成、代码优化目标代码生成符号表管理出错处理2．编译器的阶段<1>
2、词法分析：识别单词，至少分以下几大类：关键字、标识符、字面量、特殊符号；<2>语法分析：得到语言结构并以树的形式表示；<3>语义分析：考察结构正确的句子是否语义合法，可修改树结构；<4>中间代码生成（可选）：生成一种既接近目标语言，又与具体机器无关的表示，便于优化与代码生成；（编译器与解释器的以上工作阶段可以一致）编译过程各阶段工作的归纳编译过程各阶段工作的归纳<5>中间代码优化（可选）：局部优化、循环优化、全局优化等；实际上是一个等价变换，变换前后的指令序列完成同样的功能，而程序占用的空间和执行的时间都更省、更有效。<6>目标代码生成
3、：不同形式的目标代码－汇编、可重定位、内存形式（Load-and-Go）;<7>符号表管理：合理组织符号，便于各阶段使用；<8>出错处理：错误的种类－词法错、语法错、静态语义错、动态语义错。编译器的分析/综合模式1．前端：语言结构的分析2．后端：语言意义的分析与处理3．中间代码：前端与后端的分界例题1.从程序运行的角度看，编译程序和解释程序的主要区别是是否生成目标代码。2.编译程序的基本组成有：词法分析、、、中间代码生成、代码优化、、和，其中，中间代码生成和代码优化是可选的;对表达式中运算数的类型检查一般在阶段进行。3.编译程序是对__
4、______。A.汇编语言的翻译B.高级语言的解释执行C.机器语言的执行D.高级语言的翻译第2章词法分析词法分析的两个重要环节：规定所有合法输入＋识别合法输入要点：<1>什么是正规式？什么是正规集？<2>什么是有限状态自动机？<3>如何利用Thomson算法从正则表达式构建NFA？如何利用子集法从NFA得到DFA？如何将一个DFA最小化？第2章词法分析要点：<4>为什么要进行词法分析？<5>如何从描述设计出正规式？<6>正则表达式、有限自动机、NFA、DFA与词法分析器的关系？疑难点为什么要进行词法分析？词法分析的第一个目的是将输入的程
5、序文本中所有符号分类，使得接下来的语法分析可以在分析语法的过程中不再关心程序文本的细节。举例来说：C语言语句：inta;intb显然是两个不同的语句，但是对语法分析而言，它们是相同的，其格式都是：类型名标识符（对语法分析器而言，变量的名称没有意义）。词法分析器的作用就是将这些不同的部分先去除，只将语法分析需要关心的部分整理出来，留待语法分析器处理。语法分析的第二个目的是初步整理出符号表的内容，并将其留给语义分析器处理。疑难点如何从描述设计出正规式？从描述生成正规式没有任何现成的、形式化的方法，只能依靠经验。正则表达式、有限自动机、NFA
6、、DFA与词法分析器的关系？正则表达式是一种描述字符串组成的规则。有限自动机可以看作是一种利用状态转换表示字符串匹配过程的算法。NFA和DFA则是有限自动机工作过程的图形化表示。其中NFA可以利用Thomson算法与正则表达式建立一一对应的关系。而词法分析器则是将DFA表示的算法用计算机程序实现后得到的程序。词法分析器中可以直接用无限循环和switch-case语句将自身的状态与DFA中的状态图实现一一对应。例题1.词法分析的输出由记号的种类和属性两部分组成。2.指出NFA与DFA的主要区别。正规式0*(10*1)*0*所表示的语言是含
7、有偶数个1的0、1串。词法分析是编译的第一阶段，其主要任务是读取输入字符流（源程序），产生用于进行语法分析的的记号序列，同时过滤空白符号和注释。例题5.有正规式r=(a
8、b)*(aa
9、bb)(a
10、b)*，试给出：（1）r的正规集；（2）识别该正规集的DFA（要有步骤）；（3）最小化的DFA。解：（1）L(r)是至少含有两个相连的a或两个相连的b的a、b串的集合。例题5.有正规式r=(a
11、b)*(aa
12、bb)(a
13、b)*，试给出：（2）识别该正规集的DFA（要有步骤）；解：（2）构造r的NFA如图1所示。确定化：（NFA中没有ε状态转移，
14、故仅需求smove）初态：A={0}m(A,a)={0,1}Bm(A,b)={0,2}Cm(B,a)={0,1,3}Dm(B,b)={0,2}Cm(C,a)={0,1}Bm(C,b)={0,2,3}Em(D
