下载文档原格式
编译原理基础知识编译原理是计算机科学中一门重要的学科，它研究的是将程序源代码转化为可执行代码的过程。
掌握编译原理的基础知识对于理解计算机编程语言的运行原理以及进行高效编程至关重要。
本文将介绍编译原理的基本概念、过程和常用算法。
一、编译原理概述编译器是实现编译原理的工具，它将高级语言代码转化为机器语言代码。
编译器的工作过程可以分为三个主要阶段：词法分析、语法分析和语义分析。
词法分析器主要负责将源代码分解为词法单元，语法分析器则负责将词法单元组织成语法树，而语义分析器则检查语法树的语义错误并进行修正。
二、词法分析词法分析是编译器的第一个阶段，它将源代码分解为词法单元（Token）。
词法单元是程序中的最小可识别单位，如标识符、关键字、运算符等。
词法分析器通常使用有限自动机、正则表达式等方法进行词法单元的识别和分类。
三、语法分析语法分析是编译器的第二个阶段，它将词法单元组织成语法树（Parse Tree）。
语法树是由语法分析器根据源代码的语法规则生成的一棵树状结构。
语法分析器使用上下文无关文法（CFG）来描述语法规则，并通过递归下降、LR分析等算法进行语法单元的解析和组织。
四、语义分析语义分析是编译器的第三个阶段，它主要负责检查语法树的语义错误并进行修正。
语义分析器会检查变量的声明和使用是否一致、类型是否匹配等问题，并生成中间代码或目标代码。
常见的语义分析算法包括类型检查、符号表管理等。
五、代码生成代码生成是编译器的最后一个阶段，它将语义分析阶段生成的中间代码或目标代码转化为可执行代码。
代码生成器会优化代码的执行效率，包括寄存器分配、指令选择、代码重排等。
常用的代码生成算法有静态单赋值（SSA）形式转换、线性扫描代码生成等。
六、总结编译原理是计算机科学中的一门重要学科，它涉及到将源代码转化为可执行代码的过程。
掌握编译原理的基础知识可以帮助我们理解计算机编程语言的运行原理，提高编程效率。
本文介绍了编译原理的概述，包括词法分析、语法分析、语义分析和代码生成等基本概念和过程。
编译原理第⼀章学习笔记第1章编译程序的基本概念1.1什么是编译程序java中反编译命令：javap汇编语⾔本质上是⼀种助记符编译程序和解释程序两⼤不同：编译程序有⽬标程序⽽解释程序没有⽐如在C语⾔中，.exe就是⽬标程序前者效率⾼⽽后者交互性好1.2 编译程序的逻辑结构编译程序分为五个阶段词法分析结果是⼀个token序列语义分析结果是⼀个语义树语法分析结果是⼀个语法树/中间代码中间代码形式与源语⾔和⽬标语⾔没有关系——————————————————以此为界，上⾯是前端，下⾯是后端优化处理⽬标代码⽣成在编译过程中，编译程序不断地和符号表管理程序和错误处理程序打交道1.3编译程序的实现机制遍：编译程序对源程序或等价程序扫描的遍数在整个编译过程中，看似扫描了五遍，其实只有两遍，分别是对前端和后端进⾏的扫描即第⼀遍：词法分析、语法分析、语义分析。
第⼆遍：代码优化和中间代码⽣成每遍中的各阶段的⼯作是穿插进⾏的，例如下图：其中，语法分析器处于核⼼地位，每当语法分析器需要⼀个完整的语法单位时，便向词法分析器请求⼀个Token。
当接收到所需要的token之后，便调⽤语义分析器⽣成中间代码。
1.4 编译程序的⽣成⽅法涉及三个语⾔：源语⾔、⽬标语⾔和编译程序的实现语⾔编译程序的⽣成⽅法：⽤：利⽤已有的编译器写：⾃⼰动⼿写⼀个半⽤半写：重写现有编译器的后端⾃动⽣成编译程序：词法分析程序⽣成器LEX语法分析程序⽣成器YACC编译程序⽣成器输⼊：词法规则、语法规则和语义解释1.5 编译过程实例分析对如下C语⾔程序进⾏编译：int a,b;b = a + 2*5;1.词法分析：识别单词并分类词法分析的结果是以token的形式传给语法分析2.语法分析：组词成句并进⾏语法错误检查⽣成结果是⼀棵语法树分⽀语句由变量和表达式组成：变量赋值语句(expression)赋值语句可以分成项(item)/项之间的加减项可以分成因式(factor)/因式的乘除因式则可以是具体的常数/变量3.语义分析：分析各种语法成分语义分析需要构建两个东西——标识符的语义辞典（符号表）&语句的语义树（中间语⾔）符号表分为：名字类型，⽐如整型int种类，⽐如变量，常量，函数的名字等等，这⾥是值value地址，是⼀个指针接下来是语义树，和语法树很类似，但是是完全不同的，前者是描述语义信息，⽽后者描述的确实构成。
编译原理复习重点含答案编译原理复习重点编译原理是计算机科学中的一门重要课程，它研究的是如何将高级语言程序转化为机器语言的过程。
在编译原理的学习中，我们需要掌握一些重要的概念和技术，以便能够理解和应用编译器的工作原理。
本文将重点介绍编译原理的几个重要主题，并提供相应的答案供参考。
一、词法分析词法分析是编译器的第一个阶段，它的任务是将输入的字符序列划分为一个个有意义的词素（token）。
词法分析器通常使用有限自动机（DFA）来实现，其工作原理是将输入字符序列逐个读入，并根据事先定义好的词法规则进行匹配和识别。
常见的词法单元包括关键字、标识符、常量、运算符等。
常见的词法规则包括：1. 关键字：例如if、while、for等。
2. 标识符：由字母、数字和下划线组成，且以字母或下划线开头。
3. 常量：包括整数常量、浮点数常量、字符常量和字符串常量等。
4. 运算符：例如加法运算符+、减法运算符-等。
5. 分隔符：例如逗号、分号等。
词法分析的结果是一个个词法单元，每个词法单元包含一个词素和对应的词法单元类型。
例如，对于输入程序"int a = 10;"，词法分析的结果可能是[("int", "关键字"), ("a", "标识符"), ("=", "运算符"), ("10", "整数常量"), (";", "分隔符")]。
二、语法分析语法分析是编译器的第二个阶段，它的任务是将词法分析器输出的词法单元序列转化为抽象语法树（AST）。
语法分析器通常使用上下文无关文法（CFG）来描述语言的语法结构，并使用递归下降、LL(1)分析、LR分析等算法进行分析。
常见的语法规则包括：1. 表达式：例如算术表达式、布尔表达式等。
编译原理知识点总结编译原理是计算机科学中的一个重要领域，它研究的是将高级程序语言转化为可执行目标代码的原理和方法。
在软件开发过程中，编译器起着至关重要的作用，因此了解编译原理的知识点对于理解和优化程序的性能至关重要。
1. 词法分析：词法分析是编译器的第一步，它将源代码划分为一个个的词法单元，如关键字、标识符、运算符等。
词法分析器通过正则表达式和有限自动机来实现，可以有效地将源代码转化为词法单元流。
2. 语法分析：语法分析是编译器的第二步，它通过语法规则将词法单元流转化为抽象语法树（AST）。
语法分析器使用上下文无关文法来描述语言的语法结构，并通过LL（1）分析、LR（1）分析等算法来构建抽象语法树。
3. 语义分析：语义分析是编译器的第三步，它对抽象语法树进行语义检查和类型推断。
语义分析器会检查变量的作用域、类型是否匹配等语义错误，并生成中间代码或目标代码。
4. 中间代码生成：中间代码生成是编译器的一项重要任务，它将抽象语法树转化为中间表示形式，如三地址码、四地址码等。
中间代码是一种抽象的低级语言，便于后续的优化和目标代码生成。
5. 代码优化：代码优化是编译器的关键环节，它通过对中间代码进行分析和优化，提高程序的执行效率和资源利用率。
常见的代码优化技术包括常量折叠、循环优化、函数内联等。
6. 目标代码生成：目标代码生成是编译器的最后一步，它将中间代码转化为目标机器代码。
目标代码生成器根据目标机器的特性和指令集，生成可执行的目标代码。
7. 符号表管理：符号表是编译器中用于管理变量、函数等符号信息的数据结构。
符号表包含了符号的名称、类型、作用域等信息，编译器在词法分析、语法分析和语义分析阶段使用符号表进行符号的查找和管理。
8. 错误处理：错误处理是编译器中一个重要的组成部分，它负责检测和报告源代码中的错误。
编译器需要能够准确地定位错误的位置，并给出有意义的错误信息，帮助程序员快速定位和修复错误。
编译原理涉及的知识点非常广泛，上述仅是其中的一部分。
编译原理知识点引论：⏹编译的概念⏹编译过程⏹编译程序的结构⏹编译程序的生成高级语言形式化：⏹上下文无关文法⏹终结符号、非终结符号、产生式⏹推导（最左/右）、归约(规范归约)、语法树⏹句子、句型（规范句型）、短语、直接短语、句柄⏹文法定义的语言⏹文法的二义性(理解)⏹0型、1型、2型、3型文法（前两种了解，后两种要掌握）词法分析：⏹词法分析器的功能⏹状态转换图⏹正规式与正规集⏹DFA、NFA⏹与正规式等价的FA、NFA的确定化、DFA的化简⏹正规文法（左/右线性文法）⏹正规式与正规文法的等价性⏹正规文法与FA的等价性⏹词法分析器自动构造工具LEX（了解）语法分析：⏹自上而下分析：LL(1)分析⏹文法的左递归、回溯⏹LL(1)文法条件（掌握）⏹FIRST集合、FOLLOW集合、SELECT集合⏹递归下降分析法（掌握）⏹预测分析法（掌握）⏹自下而上分析：移进-归约分析⏹算符优先分析法（理解）⏹算符优先文法⏹FIRSTVT集、LASTVT集⏹算符优先关系表⏹算符优先分析算法、素短语、最左素短语⏹LR分析法⏹LR分析算法⏹前缀、活前缀、LR(0)项目集规范族⏹识别活前缀的DFA（掌握）⏹LR(0)分析表、SLR(1)分析表（掌握）⏹LR(1)项目集规范族⏹LR(1)分析表、LALR(1)分析表（了解）⏹出错处理⏹语法分析器自动构造工具YACC（了解）语义分析和中间代码生成：⏹属性文法⏹属性、综合属性、继承属性⏹语义规则⏹翻译模式⏹中间语言（理解）⏹后缀式、三地址代码、抽象语法树、DAG图⏹带注释的语法树⏹一遍扫描的语法制导翻译（理解）⏹LR语法制导翻译技术⏹递归下降语法制导翻译技术符号表的组织与管理（了解）⏹符号表的作用⏹符号表的组织运行时的存储组织与管理（了解）⏹运行时存储器的划分⏹活动记录⏹简单栈式存储分配⏹堆式动态存储分配⏹临时变量的存储分配优化技术：（理解）⏹优化方法概述：⏹局部优化⏹三地址代码的基本块、流图⏹基本块的DAG表示⏹合并已知量、删除公共子表达式、删除无用赋值、交换代码顺序⏹循环优化⏹循环查找⏹代码外提、强度削弱、删除归纳变量⏹窥孔优化⏹冗余存取、删除不可达代码、控制流优化目标代码生成：（了解）⏹目标代码生成器的功能⏹模型机的代码生成算法⏹生成的目标代码较短⏹充分利用寄存器。
编译原理要点整理//红色字体标注的是重点中的重点，大题的归宿第一章引论1.翻译器，编译器的定义2.编译器工作步骤和流程3.编译器前端后端的概念，理解为什么要有前端后端4.“遍”的概念第二章词法分析1.词法分析器的定义2.词法分析器所要完成的任务3.记号，模式，词法单元概念区分4.串的运算（和，连接，指数，闭包，正闭包）5.正规定义6.转换图（注意开始状态和结束状态以及需要将指针回退的状态）7.不确定的有限自动机（NFA）定义8.确定的有限自动机（DFA）定义9.从正规式到NFA（明确通过正规式如何构造连接运算，和运算，闭包运算的NFA）10.此方法产生的NFA的性质11.从NFA到DFA（子集构造法）12.DFA的化简（合并不可区别状态）13.从语言描述直接到DFA14.了解Lex学完本章：能语言描述改写成正规定义，能将正规定义转化为语言描述，给出一个正规式，能转换成相应的NFA，DFA并化简。
第三章语法分析1.上下文无关文法定义2.区分句子和句型3.最左推导&& 最右推导4.分析树5.文法二义性6.消除左递归&& 提左因子7.了解语言鸟瞰（0型文法：短语文法；1型文法：上下文有关文法；2型文法：上下文无关文法；3型文法：正规式）8.FIRST集合&& FOLLOW集合定义及计算方法9.LL（1）文法定义10.了解自上而下的递归下降的预测分析11.自上而下非递归的预测分析（详细明确预测分析器接受某一输入串时的具体过程，明确栈如何变化，输入输出如何变化）12.预测分析表的构造13.句柄的概念14.自下而上的分析方法：用栈实现移近-归约分析（详细明确预测分析器接受某一输入串时的具体过程，明确栈如何变化，输入输出如何变化）15.LR文法和LR分析算法16.构造SLR分析表（从文法构造识别活前缀的DFA（LR（0）项目集规范族），从DFA构造SLR分析表）17.构造规范的LR分析表（从文法构造识别活前缀的DFA（LR（1）项目集规范族），从DFA构造规范的LR分析表）18.构造LALR分析表（从文法构造识别活前缀的DFA（合并同心的LR（1）项目集），从DFA构造规范的LR分析表）（合并同心项目集可能会引起归约-归约冲突，不会引起新的移进-归约冲突）学完本章：能计算FIRST集合和FOLLOW集合；给定一个文法，能判断是否是LL(1)文法，并为其构造分析表；能构造LR(1)文法的三种预测分析表；明确移近归约分析中的每一个步骤，明确栈如何变化。
第一章1. 程序设计语言是人与计算机联系的工具，通过程序设计语言指挥计算机按照自己的意志进行运算和操作显示信息和输出运算结果。
2. 最早的计算机程序设计语言是机器语言(指令系统)。
机器语言中的指令都是用二进制代码直接表示的。
3. 机器语言和符号语言以及汇编语言都是低级程序设计语言。
4. 1954年FORTRAN I语言的问世标志计算机高级程序设计语言的诞生。
5. 计算机高级程序设计语言独立于机器，比较接近于自然语言，容易学习掌握,编写程序效率高,编写的程序易读易理解易移植。
6. 翻译程序：将高级语言编写的程序翻译成机器语言。
7. 编译程序的工作过程：编译程序这要功能是将源程序翻译成等价的目标程序，这个翻译过程分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。
8. 编译程序的重要意义在于它使高级语言独立于机器语言，使程序员用高级语言编写程序时不必考虑那些直接与机器有关的琐碎的环节，这些细节由编译程序区处理。
9. 编译程序包括：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序和目标代码生成程序以及表格处理程序和出错处理程序。
10.编译程序的组织方式：编译过程分为六个阶段,改划分是编译程序的逻辑组织方式。
编译过程分为前端和后端。
前端包括词法分析、语法分析、语义分析、中间代码生成、代码优化。
后端包括目标代码生成,依赖于计算机的硬件系统和机器指令系统。
这种组织方式便于编译程序的移植，如果移植到不同类型的机器上只需修改编译程序的后端即可。
11.翻译方式：编译方式和解释方式。
12.源程序：用高级语言编写的程序。
源程序是编译程序加工的对象。
13.编译方式：先将源程序翻译成汇编语言程序或机器语言程序（目标程序），然后再执行。
这个翻译程序为编译程序.14.编译方式中源程序的编译和目标程序的运行时分成两个阶段完成的。
编译所的目标程序计算机暂时不能执行,必须由连接装配程序将目标程序和编译程序及系统子程序连接成一个可执行程序,这个可执行程序可直接被计算机执行。
编译原理Chapter 1 编译概述1. 编译程序：将高级语言的源程序翻译成等价的机器语言或汇编语言的目标程序2. 编译方式程序运行阶段：编译+运行 or 编译+汇编+运行（编译程序+汇编程序）3. 解释方式只有解释执行阶段，根本区别是不生成目标程序4. 编译程序的构成：词法分析，语法分析，语义分析和中间代码生成，代码优化，目标代码生成，表格管理，出错处理5. 阶段划分是在逻辑结构上，不是实际执行的顺序，可以把几个不同阶段组织为一遍扫描6. 代码优化和中间代码生成不是必需的7. 编译程序与具体的机器和语言有关8. 目标代码需要有运行系统和初始数据才能进行运行计算9. 生成编译程序的方法：自编译 or 移植Chapter 2 文法和语言1. 描述程序设计语言考虑的因素：语法，语义和语用2. 闭包和正闭包的关系：*0{}A AA A ε++== 3. 只含空串的集合和空集：0{}{}A ε=≠Φ=4. 形式语言的描述：有穷时用枚举，无穷时用文法5. 文法：{,,,}N T G V V P S =6. 设计文法时要注意空串是否在形式语言中，以及表达能力是否正确7. 最右推导为规范推导，最左规约为规范规约8. 当一个语言是无穷集合时，定义该语言的文法一定是递归的9. 求短语、直接短语和句柄的格式： 句型...中的子串...是（相对于非终结符...）句型...的短语（且为直接短语/句柄）10. 文法二义性：存在句子有两棵不同的语法树，有两个不同的最右（最左）推导（规约） 语言二义性：不存在无二义性的文法文法二义性可以通过非形式规则或改写消除11. 0型无限制文法，1型上下文有关文法，2型上下文无关文法，3型正规文法12. 多余规则：左部符号不可达 or 无法推出终结符号串Chapter 3 词法分析与有穷自动机1. 词法分析程序：扫描和分解字符串形式的源程序，识别出具有独立意义的单词符号，并以（单词种别，单词自身的值）得形式输出2. 单词符号的两种定义方式：正规文法和正规式3. 正规式与正规集一一对应，描述能力与正规文法等价，无法处理{|1}n na b n ≥等4. 正规文法到正规式：联立解正规式方程组，基本型是A aA b =+和A Aa b =+ 正规式到正规文法：反复添加非终结符，基本型是A ab →和*A a b →5. 单词符号的识别方式：有穷自动机（也可用来描述正规集，能力相同）DFA ：{,,,,}M Q f S Z =∑，f 单值函数，初态唯一，终态不唯一NFA ：{,,,,}M Q f S Z =∑，f 多值函数且允许ε输入（*∑），初态不唯一6. 正规式到NFA ：化简后分段转化FA 到正规式：添加总初态节点X 和总终态节点Y ，逐步消去中间节点NFA 到DFA ：1）确定化，(,)[(,)]J A b Closure f A b ε=-；2）最简化，删去多余状态，合并等价（一致性，蔓延性）状态7. 正规文法与有穷自动机的互相转化Chapter 4 语法分析1. 语法分析程序：输入词法分析后的单词符号串，输出句子的语法树或错误表2. 自上而下分析：1）要进行确定分析，则文法必须无左递归和无回溯2）消除左递归：'''|,|A Aa b A bA A aA ε→⇔→→消除回溯：提取公共左因子，判断是否为LL(1)文法3）递归下降分析法：scanner() 和 error() 何时使用，main() 的写法4）预测分析法：预测分析表的构造，反序入栈；分析表无多重定义元素表明LL(1)，优点是分析表相对小3. 自下而上分析：1）可规约串在规范规约分析法中是句柄，在算符优先分析法中是最左素短语；2）算符优先分析法算符文法规则右部没有相邻非终结符，算符优先文法非终结符间有唯一优先关系 算符优先关系表的构造：FIRSTVT(A) 和 LASTVT(A)素短语：含终结符的直接短语不考虑非终结符的作用，速度快但可能错误识别文法中不含的句子3）LR 分析法综述对文法要求最少，可处理大部分无二义性上下文无关文法LR 分析表 = 分析动作ACTION 表 + 状态转换GOTO 表四种动作：移近s ，规约r ，接受acc ，报错4）LR(0)分析法LR(0)项目指明对活前缀的识别状态，分为规约、移近、待约和接受项目； DFA 中每个状态对于若干项目的集合LR(0)分析表中没有移近-规约冲突和规约-规约冲突则是LR(0)文法5）SLR(1)分析法在LR(0)分析法基础上向前查看一个输入符号，避免无脑规约6）LR(1)分析法LR(1)项目 = [LR(0)项目，搜索符]，规约仅在输入符号是搜索符时进行Chapter 5 语法制导翻译技术和中间代码生成1. 语义分析的任务：静态语义审查，执行真正的翻译（生成中间代码或目标代码）2. 语法制导翻译法不是形式化方法，使用属性文法描述语义3.综合属性自下而上，继承属性自上而下传递信息4.常用中间代码：逆波兰式，三元式，四元式，树形表示5.简单算术表达式到四元式的翻译6.布尔表达式到四元式的翻译Chapter 7 代码优化1.代码优化的目的：生成高效率（存储空间少，运行时间短）的目标代码2.代码优化的分类：是否涉及具体计算机：与机器有关（目标代码级），与机器无关（中间代码级）；根据涉及程序范围：局部优化，循环优化，全局优化3.用DAG实现局部优化1）基本块的判断，入口和出口语句的定义2）合并已知量、删除公共子表达式和删除无用赋值3）原基本块—> DAG图—> 优化后的基本块4.从程序流图找出循环，通过代码外提、强度削弱和删除归纳变量进行优化。
编译原理学习笔记--语法分析（⼆）⾃顶向上分析⽅法1 思想 简单来说就是试图从输⼊符号串出发，将其直接作为叶⼦结点，然后向上构造出⼀棵分析树。
从树根到叶⼦叫展开，⽽从叶⼦回树根就叫归约。
所以这种⽅法的关键在于查找当前句型的可归约串，然后规约到⾮终结符，形成⼀个新串，再重复查找句型，归约的过程。
2 ⽅法2.1 优先分析法1. 简单优先分析法规范归约:按照⽂法符号之间的优先关系确定当前句型的可归约串。
(划重点意义不⼤,因为它限制了作⽤范围只能是简单优先⽂法。
2. 算符优先分析法算符⽂法：若产⽣式右边任意位置都没有连续两个或以上的⾮终结符出现，则称为算符⽂法。
算符优先⽂法：若算符⽂法G不含有\varepsilon产⽣式，且它的任何两个构成序对的终结符号之间最多有>、<、=三种优先关系中的⼀种成⽴，则称G是⼀个算符优先⽂法。
其实上⾯这些定义并没有什么卵⽤2.2 LR分析⽅法句柄：最左直接短语。
也是分析树最左边的只有⽗⼦两代的⼦树叶结点⾃左⾄右排列形成的符号串。
LR是⼀种规范规约，具体过程如下：1. 把输⼊符号⼀个⼀个地移进栈⾥，直到栈顶的符号串形成⼀个可归约串为⽌。
2. 把栈顶的这个可归约串归约为产⽣式的左部符号，直到栈顶不再有可归约串为⽌。
3. 重复以上移进-归约操作，直到归约到⽂法的开始符号。
2.3 规范规约步骤：先找出当前句型的句柄，然后把句柄归约为相应产⽣式的左部符号，得到⼀个新的句型，重复此过程，最终归约到⽂法的开始符号。
形式定义：假定\alpha是⽂法G的⼀个句⼦，如果右句型序列\alpha_n,\alpha_{n-1},...,\alpha_1,\alpha_0满⾜以下两个条件，则称该序列是\alpha的⼀个规范归约。
1.\alpha_n = \alpha,\alpha_0 = S2.对任何i(0<i\leq n),\alpha_{n-1}是经过把\alpha_i的句柄替换为相应产⽣式的左部符号⽽得到的。
编程| 编译原理CH1解释程序和编译程序（了解区别）编译程序若源程序是用高级语言书写，经加工后得到目标程序，上述翻译过程称“编译”。
解释程序（类似于口译，不生成目标代码）对源程序进行解释执行的程序。
共同点如果源语言是高级编程语言，目标语言是机器代码和汇编语言这样的低级语言，这类翻译程序就叫做编译程序或解释程序。
区别编译程序会生成目标代码，而解释程序不会。
编译过程（五个阶段，会背，填空题）词法分析语法分析语义分析及中间代码生成代码优化目标代码生成编译的前端和后端编译前端只依赖于源程序，独立于目标计算机。
编译后端编译后端的工作主要是目标代码的生成和优化，独立于源程序，完全依赖于目标机器和中间代码。
CH2单词的类别（五种单词记号）保留字字面量标识符运算符分界符单词输出的形式<单词种别，单词的属性值>该式是一个二元式词法错误校正的常用策略（简答题）（也可以是这种问法，答案是一样的）对词法错误校正的常用策略是修补尝试，一般包括：删除一个多余的字符插入一个遗漏的字符用一个正确的字符替换一个不正确的字符交换两个相邻的字符NFA确定化，需给出每一个子集书上P34页图2.12 ，结果在P37页一般做题的方法和规则找初态一般在最左边的是一个箭头，箭头的那个状态就是初态。
如上图的i就是初态识别空串在进行识别空串的时候，可以识别很多个空串。
比如上面图中，对于初态i来说，识别1个空串的结果是b，两个是2。
再识别空串，发现已经没有了。
所以结果就是{i,1,2}识别后得出的结果，再识别Ia和Ib识别后得出结果，对于Ia的结果是再次识别空串和a刚才的结果是{i,1,2}对这个结果进行Ia，先对i来说，再识别空串，可以是{1，2}，而i来说识别不了a，因为它上面没有a。
对于1来说，再识别空串的结果是{2}，识别a的结果是{1}，对于2来说，不可以再识别空串了，再识别a是{3}，把所以得到的结果整合一下，即结果为{1，2，3}。
