《编译原理》 年  月期末考试指导一、考试说明（一）说明满分为 100 分，考试时间为 90 分钟, 考试形式为开卷。（二） 试卷包含的题型及各题型相应的答题技巧问答题（每题 8 分，总计 100 分）答题技巧：需要答出与问题相关的重要知识点（即讲义与课件中的知识点），如需要，可对相关内容展开简单阐述。二、复习重点内容第一章 概论1、编译器与解释程序的关联 编译器：一次编译多次使用目标程序的运行效率高；编译技术复杂解释程序：逐个指令进行解释常驻计算机；通过部分编译技术就可实现解释程序是如同编译器的一种语言翻译程序。它与编译器的不同之处在于：它立即执行源程序而不是生成在翻译完成之后才执行的目标代码。从原理上讲，任何程序设计语言都可被解释或被编译，但是根据所使用的语言和翻译情况，很可能会选用解释程序而不用编译器 。另一方面，当执行的速度是最为重要的因素时就使用编译器，因为被编译的目标代码比被解释的源代码要快得多。2、编译器的翻译步骤 （）扫描程序功能读取源程序执行词法分析将字符序列划分成一个个单词获取单词种类，一个单词的种类和它的拼写构成一个记号，把源程序看成记号的序列以供进一步分析输入源程序文本或字符序列输出记号序列其他功能错误处理填写符号表和文字表可延后（）语法分析程序功能进行语法分析找出程序的结构语法定义程序的结构及构成程序的要素要素之间的关系以及程序结构与要素间的关系。程序的结构决定程序的主要含义输入记号序列输出分析树或语法树进一步把源程序看成有结构的记号序列（）语义分析程序程序的语义程序的意思包括程序的结构各语法结构的数据类型有无类型匹配错误语义决定程序的运行分析源程序的目的就是要确定该程序的意思以便将其翻译成等价的目标程序输入语法树或分析树输出注释树  将语义信息作为注释添加到语法树中  计算扫描程序语法分析程序和语义分析程序构成编译器的分析部分，通过分析部分编译器识别出源程序的正确性对于正确的源程序得到源程序的结构和语义等翻译时需要的信息其余三个模块（源代码优化程序、代码生成器、目标代码优化程序）构成编译器的综合部分，综合分析的结果将源程序翻译成与其等价且高质量的目标程序。 -+-.4&4, &.-4-.,.+-.4&4,..+-.4&., , K4,3、TINY 语法分析程序 语言文法的 b?J 表示F4U4]aN4]aNU4#,4$4UAAA ]4U Q-4]aNX.4]aNY]4UAAA,F]4UAAA]4UAAA,"]4UAAAQU4.]QX4]4.]QY4]U%C&4.]QU4#4$U'C]4U #4N. $4N.U^C!, UQCN4CH 语法分析程序的实现文件5-5主分析程序)O工作程序有  个相互递归的过程构成变量保存向前看记号；4指向当前语法树的根结点辅助函数6-,F"K4"bQ3KF3Qb4、递归下降分析程序中的错误校正应急方式忽视出错位置的记号继续进行分析出错处理函数d3Qb-)4F输出出错记号的行号及 4FNQ(*记号和串值第六章 语义分析1、 属性和属性文法属性语言结构的任意特性属性类型：静态属性编译时可以确定的属性编译时属性动态属性程序运行时才能确定的属性属性直接与语言的文法符号相关联 8语法制导属性的表记对于文法符号 e 以及 e 的一个属性 与 e 关联的  的值记作 e5属性的集合表示为#D$文法规则的表示eUeeDe这里e 是非终结符eDe 是终结符或非终结符当一个符号在文法规则中出现一次以上时使用适当的下标区分这些不同的出现2、属性等式,属性规则 对于文法规则 eUeeDe和属性的集合#D$关联于文法符号 e 的属性 f 的属性值 e5f 可能与规则中关联于其他符号的相同或不同属性的属性值有关使用等式来表示属性和属性值间的这种关系属性等式属性等式的一般形式 e5f&Hfe5De5De5De5这里Hf 是一个函数其参数中不含 e5f3、属性文法的定义和表示：对于文法 T&[K属性 D 的属性文法是#>C:[> 是与  有关的属性等式的列表$属性文法的表示：文法规则属性等式语义规则规则 与规则  相关的属性等式列表DD规则 与规则  相关的属性等式列表主要任务是填写属性等式4、属性文法的简化和扩充在属性文法中：允许使用  表达式，允许使用  表达式和 "- 表达式等，允许使用函数函数的定义可以在别处给出，例如对于规则 FUG可以给出属性等式 F5O.&N4O.G其中N4O. 是求数字字符的值的函数N4O.-I#NISgg,$5、属性计算算法）相关图和赋值顺序属性等式和属性值的计算属性等式 e5f&Hfe5De5De5De5蕴含着如下信息把右边的函数表达式的值赋给 e5f；e5f 依赖于等式右边出现的属性值；为求 e5f这些属性值必须是已知的必须先求：需要按某种顺序来求属性值；属性的等式给出了计算顺序的约束条件；结合分析树或语法树给出的这些约束的图形表示相关图相关图给出赋值顺序的约束关系研究相关图的目的就是要考察相关图与赋值顺序的关系及有哪些赋值的顺序按相关图的不同对属性进行分类对各类属性给出相应的属性计算算法讨论如何来存储属性值两类相关图：属性文法的相关依赖图（局部信息）句子的依赖图（全局信息）属性文法的相关依赖图：每个文法规则有一个相关依赖图；在图中对于文法规则中的每个文法符号 e 和每个属性 f有一个结点 e5f；对于与该文法规则相关联的每个属性等式e5f&Hfe5De5De5De5 ； 对 于 右 边 每 个 结 点 e45.  有 一 条 从e45. 到 e5f 的边句子的依赖图：对于符合文法规则的字符串 >> 的依赖图是 > 的语法树中与每个非叶子结点相关的文法规则的相关依赖图的联合；在依赖图中与每个符号相关的结点画在一组中 8与语法树联系在一起基于相关图的属性计算：相关图指明了字符串各属性间的依赖关系；为了能够计算一个字符串的所有属性该字符串的相关图中必须没有循环 非循环有向图：这时通过拓扑排序算法可以得到计算顺序。因此语义计算算法就是拓扑排序算法6、 符号表用于存放标识符的类型等各种属性。例考虑简单声明的属性文法使用符号表存放变量的类型。543将  的串值 4 和类型 3 插入到符号表54 是由扫描器或语法分析器得到的串值使用符号表的 bO.3 算法①符号表的结构目录数据结构：检索维护可能的实现方法：线性表；各种搜索树二叉搜索树>dB 树? 树哈希表杂凑表：需要频繁地操作是编译器的核心操作也是对编译速度影响最大的操作要求高效哈希表是最佳候选第七章 运行时环境1、 程序执行时的存储器组织 计算机的存储器分类寄存器直接编址随机访问存储器h>6：有代码区和数据区直接编址随机访问存储器h>6i 代码区结构：过程  的入口点→过程  的代码过程  的入口点→过程  的代码过程  的入口点→过程  的代码j 数据区的结构：全程!静态区：存放全程!静态变量、较大的常量编译时可求地址动态数据区：编译时地址不可求栈区：存放局部变量、函数调用时和返回时所需的信息、临时变量（调用函数时生成，退出函数时消除）堆区：特殊的线性表：存放由 4.. 等要求的动态数据k 栈：处理器栈：支持过程调用和返回通过类似于汇编语言的 .. 语句和 N 语句处理有时需要编译程序显式地在存储器处理模拟处理器栈存储器栈数据栈：记录过程的活动记录当调用过程或函数时，需要为其局部数据分配存储空间  产生该过程的活动记录调用结束后需要释放活动记录占用的空间l 活动记录的一般组织示意图自变量参数空间：数据的顺序等细节依赖于目标机器的体系结构被编译语言的特性等，参数空间用于存放实参，存放的具体内容由参数的传递机制决定返回地址等簿记信息的空间： 用作簿记信息的空间包括返回地址各过程所用空间的大小固定其他空间随过程不同而不同但对一个过程的每次调用均相同局部数据空间：用作存放局部变量等局部数据局部临时变量空间：用作存放局部临时变量m 活动记录分配根据语言的不同，活动记录可能被分配在静态区Jchh>GG栈区+[.堆区BK[分配在栈区时，有时称活动记录为栈框架 4寄存器也是运行时环境的结构部分：保存临时变量、局部变量、全局变量记录执行的状态：特殊用途的寄存器程序计数器用于记录下一个机器指令的地址；执行一般指令时 按指令的占位递增或递减，转移、子过程指令等强制更新  寄存器，可以通过强制更新  来模拟这些指令栈指针使用栈框架时记录栈中的位置框架指针 指向当前活动记录的固定位置自变量指针指向保存自变量参数的活动记录函数的调用和返回运行时环境的重要组成部分，需要完成一系列操作调用序列：调用一个函数时必须执行的操作序列分配活动记录的存储空间计算、分配自变量寄存器的保存和设置返回序列：函数被调用完毕后必须执行的操作序列放置可由调用过程访问的返回值重新调整寄存器释放活动记录的存储空间调用序列设计：如何在调用程序和被调用程序间分配调用序列操作2、 完全静态运行时环境最简单的运行时环境：所有的数据都是静态的，而且执行程序期间在存储器中保持固定可以用来实现没有指针及动态分配，且过程不可递归调用的语言Jchh>GG：每个过程只有一个在执行之前被静态分配的活动记录通过固定的地址访问所有的变量和过程3、 TINY 语言的运行时环境 采用简化了的静态运行时环境，在符号表中保留变量的地址保留地址O`-)4..,查找地址`.N-)4初始化地址.&,基于栈的运行时环境 静态的运行时环境不容许动态地分配存储器在允许递归调用以及每一个调用中都重新分配局部变量的语言中，不能静态地分配活动记录 ；必须以一个基于栈的风格来分配活动记录当进行一个新的过程调用时，一个新的活动记录被分配在栈的顶部活动记录的压入而当调用退出时，则再次解除分配活动记录的弹出活动记录的栈运行时栈、调用栈随着程序执行时发生的调用增长和缩小一个过程在某一时刻可以有若干个不同的活动记录，每一个代表一次不同的调用基于栈的运行时环境的特点：这样的环境要求的簿记和变量访问间的技术比完全静态环境要复杂许多活动记录中必须有额外的簿记信息调用序列还包括设置和保存这个额外信息所需的步骤返回序列包括恢复这些信息的步骤基于栈的环境的正确性和所需簿记信息的数量很大程度上依赖于被编译的语言的特性有两种基于栈的运行时环境A没有局部过程的基于栈的环境+A带有局部过程的基于栈的环境[.没有局部过程的基于栈的环境基于栈的运行时环境的要求能够维护框架指针，容许访问局部变量允许调用结束时恢复活动记录，返回调用过程框架指针 通常保存在寄存器中通常也称作 有关先前活动的信息一般是放在当前活动中，称为控制链或动态链它指向调用程序的活动记录 这一指针有时称为旧 ，它代表了  的先前值，并被放在栈中参数区和变量区之间的某处F此外，还有一个栈指针，指向栈顶基于栈的环境中要处理的问题对名称（变量）的访问通过相对于框架指针的偏移量访问参数和局部变量通过绝对地址访问全局和静态变量；对函数进行调用和从调用返回时的操作调用序列；返回序列参数传递机制函数的调用序列的第一个任务就是在新活动记录的开始设置形参的存储空间，同时建立实参与形参间的联系；联系的具体形式根据参数的传递方式的不同而不同参数传递分类）值传递：计算实参值并把该值拷贝到形参，作为形参的初始值；在函数运行期间，形参被看成用实参值初始化了的简单局部变量，不再与实参有任何形式的联系优点：单纯；对编译程序没有特殊要求；安全缺点：缺乏灵活性；参数大时效率较低）引用传递：把实参的地址传递给形参，使形参成为实参的别名对于对形参的任意操作，编译程序通过传递过来的地址，转化成对相应的实参的相应操作编译程序负责将对形参的访问转化为对实参的间接访问优点：每个形参的存储空间固定：求址方便灵活：可以把形参作为返回值参数或同时作为输入、输出接口 当参数较大时可以提高空间和时间效率缺点：使用不当时安全性或!和效率较差；安全性可以通过常量修饰符人为地控制可将函数定义设计成 O 324#555$这时，编译程序禁止 4 成为左值，从而抑制对实参的更新操作）值结果传递：同时将实参的值和地址传递给形参，实参值是形参的初始值在函数运行时，形参作为简单的局部变量使用在返回序列中，通过实参的地址将形参的最终结果传递回实参优点：灵活缺点：兼具值传递和引用传递的缺点第八章 代码生成1、中间表示和中间代码 （）中间表示h中间代码：有利于简化编译，产生高效代码，提高可移植性语法树：二维，与目标代码极不相像，差距大，而且没有将任意的语法树直接转换成机器代码的一般手法（）中间代码：使用跳转实现控制，线性化（抽象）汇编码三地址码二地址码逆波兰式[(代码6(码nO 字节码（）6简单的目标机器 语言的编译器以 6 的“机器代码”为目标语言6 是简单的虚拟计算机与具体机器无关（9）36-4 的基本结构6 机的组成通过数组模拟只读指令存储区 64X55Y数据区 64X55Y 个通用寄存器 FX55GY：寄存器 G 为程序计数器 运行过程使用 6 代码初始化 6464XY初始化为数据区最高地6X55Y初始化为 从 64 的指令开始执行直到出错或到达 o>B 指令（）6 指令集：（寄存器指令）hc 指令格式 为寄存器号操作码效果o>B停止执行忽略操作数从标准输入设备读入整型值存入 FXY忽略  和 cp在标准输出中写出 FXY的值忽略  和 >IIFXY&FXY'FXY Kp?FXY&FXYSFXY6pBFXY&FXY)FXYIdFXY&FXY!FXY可能产生除  错误（寄存器(存储器指令）h6 指令格式&'FXY 和  是寄存器号操作码效果BIFXY&64XY装入内存BI>FXY&装入地址 为偏移量BI+FXY&忽略 装入常量K64XY&FXYnB FXY%FXGY&nBb FXY%&FXGY&nTb FXY*&FXGY&nT FXY*FXGY&nbq FXY&&FXGY&nb FXYr&FXGY&其他说明无条件转移到'FXYBIG间接转移到寄存器  指示的地址BIG条件转移到距当前指令距离为 ' 的指令nbqG进入子程序前可以使用 BI>G把返回地址存放到 FXY中（）6 模拟器忽略空行忽略以)开头的注释行指令形式编号操作码操作数注释忽略的操作数也不能省略指令可不按编号顺序排列实际载入代码区时将按编号顺序重排（G）阶乘计算的手动代码)输入一个正整数计算其阶乘并输出结果从输入设备读取一个整数存入 FXYnBbG如果 FXY%& 跳转到指令 FXGY''BI+FXY&BI+FXY&)96pBFXY&FXY)FXYKp?FXY&FXYSFXYnb(G如果FXY%*跳转到指令 9Gcp输出 FXY的内容o>B停机)程序结束2、TINY 语言的代码生成器 编译器的代码生成器生成 6 代码文件6 代码文件可以通过 6 模拟器模拟运行中间代码生成可以被看作是一个属性计算，类似于第  章中研究的许多属性问题：生成代码被看作一个字符串属性每条指令用换行符分隔，这个代码就成了一个合成属性并能用属性文法定义，并且能在分析期间直接生成或者通过语法树的后序遍历生成 （） 代码生成器的 6 接口 指针FXGY4内存指针FXY指向存储器的顶部用于访问临时变量FXY&F全程指针FXY指向存储器的地步用于访问命名变量FXY&（）寄存器累加器&FXY&FXY用于计算结果存放于  中寄存器 9 无命名且从不使用（）代码发行函数4+44发行注释代码4hc发行 hc 指令O4hc-)-),4h6发行 h6 指令O4h6-)-),4K跳过将来要反填的位置返回当前指令位置并保存在 5 的内部4K跳过一个位置该位置将在后面填上转移指令4K不跳过位置但可以得到当前位置以备后面的转移引用4?N用于设置当前指令位置到先前位置来反填4h返回当前指令位置给先前调用 4?N 的值典型用法4?NOB,4h,4h6`>将绝对代码转变成相对于  的相对地址用于产生诸如反填转移或其他由4K 返回的代码位置的转移的代码（9） 代码生成器文件F5主函数O+TO功能：产生若干注释和标准序言指令设置 4 寄存器并清除位置 设置启动时的运行时环境在语法树上调用 T产生 o>B 指令终止程序T 根据结点类型调用 FK4 或 FbQ并在同属上递归调用自身常量和标识符结点的代码当前的运算结果总是存放在  中常量从结点属性获取常量的值并装入 4h6sBI+s(*5O.s装入常量s,标识符从符号表中获取标识符的存储位置 . 并装入 .&`.N(*54,4h6sBIs.Fs装入标识符的值s,3、运算符结点 （）算术运算符结点递归生成左操作数的代码 T, 为左孩子指针将运算结果存储于临时变量4h6sKs4ct((4s运算符压入左操作数s,递归生成右操作数的代码T, 为右孩子指针 装入左操作数4h6sBIs''4ct4s运算符装入左操作数s,生成运算符相关的计算代码4hcs>IIss加运算符s,（）比较运算符结点同算术运算符相关操作左操作数在 右操作数在 生成比较运算符相关的计算代码4hcsKp?ss小于运算符s,4h6/nB1/如果成立则终止跳转到成立的情况”,利用减和跳转实现比较4h6/BI+1/不成立的情况”,赋值 4h6/BI>1/无条件跳转”,跳过成立情况4h6/BI+1/成立的情况”,赋值 4、语句结点分别处理  种句子并对子结点递归调用 T（）赋值语句：生成赋值号右边表达式的代码T(*-.XY,在根结点查找赋值号左边的标识符的存储位置.&`.N(*54,把表达式的值存储于 .&.'F处4h6sKs.FsF 语句存储计算结果s,赋值语句代码示例 & )QQ 是第一个标识符  是第二个BI装入标识符的值K运算符存储左操作数BI装入标识符的值BI运算符装入左操作数6pB乘运算KF 语句存储计算结果语句：读取整型数值4hcsss读取整型数值s,查找标识符位置.&`.N(*54,存储读取的值4h6sKs.Fs 语句存储读取的值s,（）" 语句：生成表达式的代码T(*-.XY,写出表达式的值4hcscpss写出 s,9 语句：生成测试表达式的代码T,生成测试表达式不成立时跳转到 . 部分的指令但目前还不知道跳转的目标位置所以先记住指令编号以后适时进行回填OB&4K, 语句：生成 -4 部分的代码 T,记住跳转指令的位置OB&4K,获取 . 部分代码第一个指令或者没有 . 部分时下一个语句的第一个指令的位置NB&4K,回填第一个跳转指令4?NOB,把指令编号改成 OB4h6`>/nbq1NB/ 语句跳转到 . 部分”,发布跳转指令4h,改回指令编号 语句：生成 . 部分的代码T,获取下一个语句的位置NB&4K,回填第二个跳转指令4?NOB,4h6`>sBI>sNBs跳转到语句结束s,4h,G 语句：记住语句体代码第一个指令的位置OB&4K,生成语句体的代码T,生成测试表达式的代码T,生成跳转回语句体开头的代码4h6`>snbqsOBs 语句跳转回语句体s,5、中间代码生成中的其他问题 语言缺少实用语言中代码生成的一些考虑因素只有整型数据大小固定没有函数调用不需要活动记录逻辑运算单纯6、数据类型与偏移量  语言类型单一每个数据占一个单位QF3F(4( 为 Q3 的偏移量标识符的偏移量记录于符号表中一般情况数据大小不同对于不同类型的数据分别求其偏移量三、重点习题5 简单论述用程序解决问题的基本方法。5 使用  语言编写完成如下工作的程序，并简述该程序的编译、执行过程：从输入读取两个非负整数，如果前者不小于后者则输出前者和后者的差否则输出 。例如，如果前者是 ，后者是 ，则输出 。5 陈述从正则语言出发构造正则表达式的基本方法。 3、编译器中的主要数据结构为了实现编译器我们通常需要以下数据结构枚举类型记号种类语法单元等的命名结构体分析树语法树的节点符号表等树形结构分析树语法树注释树线性表哈希表符号表常量表文件输入输出临时文件4、TINY 语言和 TINYC 语言 （） 语言结构简单 程序是由分号分隔开的语句序列不含过程函数和变量声明只有整型变量只有两个控制语句 和 输入!输出语句变量名"整型算术表达式注释#注释$不能嵌套可跨行表达式布尔型%&整型'()!没有*布尔型表达式只用于控制语句的条件测试只能含有一个比较运算符（）+ 语言的 + 版本语句序列是语句的序列语句由分号结尾声明格式变量名,控制语句 "-.按 + 语言格式复合语句#语句序列$输入语句 /012变量名输出语句 /01整型算术表达式注释!)注释)!不能嵌套可跨行比较运算符包括*%&&其余与  语言相通但按 + 语言格式5、TINY 编译器的创建和 TINY 程序的运行 编译器：模块结构与翻译步骤基本一致用法34.53生成 6 机代码文件 4.54创建  编译器使用 + 语言编译器编译  编译器的源程序条件编译标志生成功能有限的编译器或显示附加信息用以编译器学习和调试第二章 词法分析 1、扫描处理的过程和相关概念扫描程序的任务将源程序作为字符文件读入将其分为若干个单词并产生相应的记号。记号源程序中的信息单元逻辑单元表示一类单词记号是为这类单词起的名字典型的记号种类关键字标识符特定符号运算符分隔符每一种又可细分为若干个记号2、词法的形式描述 通过格式匹配读取一个个单词并获取各单词的种类记号记号格式的名字表示单词的一个集合 95 设 B 是所有由 、、 组成的含有偶数个  和  的字符串组成的集合。编写表示 B的正则表达式。5 设 B 是所有由 、、 组成的含有偶数个  或偶数个  的字符串组成的集合。画出识别 B 的 IJ> 的状态转移图并给出分别对  和  的处理过程。5 对于第  题的  程序，给出  扫描器的输出。（对于每个单词，可以用（记号，单词拼写）的形式表示相关的输出。）G5 给出第  题的  程序的语法树。5 给出乘除法表达式的文法在此之上给出表达式分析树属性的属性文法，解释基于该属性文法的 )9!9 的分析树构造过程。考试指导使用说明： 本考试指导只适用于 201803 学期 6 月期末考试使用，包括正考和重修内容。指导中的章节知识点涵盖考试所有内容，给出的习题为考试类型题，详见课程讲义或笔记。如果在复习中有疑难问题请到课程答疑区提问。最后祝大家考试顺利！ 单词具体的字符串匹配的内容格式说明描述特定记号所表示的集合的结构正则表达式识别算法根据格式说明判定单词及其种类有穷自动机3、使用正则表达式表示单词结构 （）把正则表达式作为词法描述工具同四则运算表达式一样正则表达式有其外观和含义四则运算表达式的外观由数加减乘除运算符和括号组成符合一定规则的式子正则表达式的外观由基本的正则表达式运算符号和括号组成符合一定规则的式子四则运算表达式的含义刻画数或数的集合的性质正则表达式的含义刻画字符串集合的性质（）正则表达式的用途：正则表达式是描述构造特定单词集合正则语言的结构的式子正则表达式所表示的数据对象是某个字符集合 7 上的字符串集合，这样的字符集合 7 称为字母表，字母表 7 随处理对象的不同而不同（）正则表达式的定义：正则表达式8正则语言8字符串集合的运算若干集合运算，集合的并运算，字符串集合的连接运算、闭包运算（9）正则语言定义：定义字母表∑上的正则语言递归定义如下基本正则语言对于任意的 :;#$是正则语言,由空串 < 组成的集合#<$是正则语言,空集 = 是正则语言,运算并运算若 > 和 ? 是正则语言则 >@? 是正则语言连接运算若 > 和 ? 是正则语言则 >A? 是正则语言,闭包运算若 > 是正则语言则 >)是正则语言,最小性限定只有从几百本正则语言出发通过有限次使用运算得到的才是正则语言 5没有其他正则语言（）正则表达式及其表示的集合：定义字母表∑上的  及其表示的集合 B递归定义如下基本的 对于任意的 :;符号  是 B&#$,符号 < 是 B<&#<$,符号 = 是 B=&=,运算符号设  和  是 则选择运算符C 或 是 BC&B@B,连接运算符 与  的连接是 B&BAB,闭包运算符) 的闭包是 B)&B),括号运算符括号 是 B&B,最小性限定只有从基本  出发通过有限次使用以上规则构建出来的是 5（）正则表达式命名：表示整数的  是CCCDCECCCDCE)命名F&CCDCE&FCF)注意在一个名字的定义中不能直接或间接地使用该名字（G）等价性：定义若  和  表示同一个集合即 B&B则称  和  等价记作 &5 并非所有集合都能用正则表达式表示：能力有限；可以高效处理等价性证明方法：证明等式两边的正则表达式表示的集合相同；分解与综合；利用已知的结果（）编写正则表达式的基本手法：研究所涉的对象  掌握字符串集合与表示该集合的正则表达式的关系特别是简单集合与基本正则表达式的关系以及集合运算与正则表达式的运算符号间的关系观察所给字符串集合 > 中字符串的一般结构对集合或字符串做适当的划分 8 分解把 > 划分成 ?@+若 B&?B&+则 BC&>把 > 划分成 ?A+若 B&?B&+则 B&>把 > 划分成 ?)若 B&?则 B)&>4、 有穷自动机 标识符的识别过程正则表达式H&..CF)识别手续第一步从输入读取一个字符 -,!!初始化若 - 是字母则从输入读取下一个字符 - 并转到第二步,否则转到第三步,第二步当 - 是字母或数字时从输入读取下一个字符 -,若 - 是输入结束则结束并给出成功的信息,否则转第三步第三步从输入读取所有字符,然后结束并给出失败的信息5标识符的识别过程演示的优缺点：直观形象；繁琐过度抽象有穷自动机的特征有穷自动机与正则表达式关系密切可用于在输入串中识别模式的过程可用于构造扫描程序的算法状态转移图的特征初始状态是唯一的接受状态可以有多个或零个对任意的状态  和输入 有且仅有一条从  射出的带有标志  的弧称为路径 可以并弧化简符合这些条件的有穷自动机叫做确定性的有穷自动机简称 IJ>9IJ> 的形态状态转移图直观数学定义严格状态转换表面向编程定义IJ>6是一个五元组;K>其中5;是字母表字符的有穷集合5K 是状态集合状态的有穷集合5KL;MK称为转换函数95 是初始状态5> 是接受状态的集合是 K 的子集5字母表是问题固有的,状态集合是编写 IJ> 时定义的用户可以自由命名定义给定 IJ>6对于字符 D当以下条件成立时称 6 接受字符串 D存在状态序列 D使得&&D(&K且 :> 是接受状态 这时D 是从初始状态出发到达某个接受状态的路径序列定义IJ>6 接受的语言是所有 6 接受的字符串组成的集合即B6&#":;)C6 接受 "$IJ> 构建小结使用状态存储关键信息确定初始状态空串所包含的信息确定接受状态接受的串应该包含的信息状态转移信息更新IJ> 的基本构造手法：掌握 IJ> 的基本概念结构和思想>IJ> 由状态和路径构成? 状态记录到目前为止读取了什么样的字符串8抽取必要有限的信息+路径描述读取字符后的信息更新从正则语言出发构造 IJ>>观察需要接受的字符串的结构决定需要记录的信息? 区分一个字符串是否能够成为需要接受的字符串的前缀+ 当到达某个状态且刚好读取完一个字符串时是否接受该字符串8接受状态I 按题意对字母表中的字符分类以决定路径名和状态转换的形式从正则表达式出发构造 IJ>> 将正则表达式分解成简单或 IJ> 已知的子表达式的组合? 对每个子表达式构造相应的 IJ>+ 把各 IJ> 按相应子表达式之间的运算结构组合起来构成对应于整个正则表达式的 IJ>5、 TINY 扫描程序的实现 使用双层开关语句法主要文件5-5主要函数F主要数据记号N串值KF其他变量文件变量N.F 行数.保留字保留字表OP查表函数OBN输入函数FQ+-受限缓冲.?N 是否存储当前字符O退回字符NFQ+-第三章 上下文无关文法及分析1、 上下文无关文法（）描述程序设计语言的语法结构QMQQCQCN4M'C(C)（）规则的说明：字母用正则表达式表示的记号 语言的记号字母表# -.N."HN4'()!&%,&$字母表  及语法符号集  上的上下文无关文法规则产生式的形式>MR>: 称为语法符号或语法结构名语法变元R:@@#C$) 直观含义使用 R 定义 > 的结构（）产生式的实例QMQQCQCN4M'C(C)产生式的变形：允许更多元符号QMQ/'1C1(1C1)1QC//Q11CN4S去除选项符号CQMQQM'QMQM(QMN4M)（9）上下文无关文法的定义上下文无关文法的简写法和用处：简写法：通过产生式判断  和 规定第一个产生式的左部是开始符号对于左部相同的产生式将其右部用C连接构成一个产生式一个 +JTT 定义一个语言记作 BT定义语言时使用推导的概念2、 推导 （）通过产生式推导出 +JT 定义的句子程序句子是由终结符正则表达式表示的记号构成的串即记号序列正则表达式是 +JT 的字符所有推导出的句子构成 +JT 定义的语言语法分析的任务：判别一个字符串是否是句子程序分析出句子的语法结构推导是定义+JT和语言句子集合之间的纽带（）一步推导的步骤：在要展开的字符串中选取一个非终结符 >,选取一个左部为 > 的产生式>U"C"CDC",选取上面产生式的右部的一个选择 ",使用 " 替换要展开字符串中选取的 >由字符串 R 开始经过一次推导得到字符串 V 时记为RWV或者RWVXYXY表明在该步推导中使用了产生式 即通过 &>UZ 展开 R 中的某个 > 而推导出 V（）推导的定义和扩展定义推导对于 +JTT&K[ 及 RV:@)RWV 当且仅当存在 >UZ:[ 及RR:@)有 R&R>R 且 V&RZR5 步以上的推导包括  步W)（9）+JT 定义的所有句子的集合构成它定义的语言定义+JT 定义的语言,+JTT&K[定义的语言 BT是 T 定义的所有句子的集合即BT&#R:)CKW)R$由 +JT 定义的语言称为上下文无关语言（）递归规则：如下形式的规则组称为左递归规则>U>RCV其中R 非空V 不以 > 开始 从 > 出发可以推导出 VVRVRRVRRRD如>U>C 生成语言#C\$&B'>U>C< 生成语言#C\$&B)<(产生式左递归规则与闭包的关系可以用上下文无关文法代替正则表达式如下形式的规则称为右递归规则>UR>CV3、 分析树 +JT 通过推导定义句子和语言，推导构造句子并确定句子的结构，但推导具有不确定性，一个句子可以有多个推导序列。最左推导每步推导展开句型中的最左非终结符最右推导每步推导展开句型中的最右非终结符抽取推导的主要特征忽视表面的差别 分析树标记树：内部结点的标记非终结符叶结点的标记终结符根结点的标记开始符号内部结点及其子结点表示推导中相关非终结符的替换内部结点 > 及其子结点的序列 R 对应于该部分替换中所用的产生式 >UR分析树与最左推导9()9 最左推导与分析树的前序序列前序编号一致分析树与最右推导9()9 最右推导与分析树的后序序列后序编号相反分析树的特点：适用于表示记号串的组织结构记号表现为叶结点推导步骤由内部结点表现完全依照语法的定义含有翻译过程中不需要的冗余信息可以考虑使用更简单更直接的方法表示这些信息 抽象语法树4、 抽象语法树语法树包含了翻译所需的所有语法信息；效率更高；分析程序通常通过分析树表示所有步骤 但只构造语法树或类似的中间代码；对于具体的语法结构需要具体地考察它的语法树结构简单算术表达式的语法树：文法QUQQCQCN4U'C]C^子树的根表示该子树对应的表达式的值应该以要表示的表达式的运算符为根QQ 形式的表达式的语法树N4 的语法树退化成一个结点Q的语法树退化成 Q 的语法树函数形式与语法树QQ实际上是函数  及其参数两个 Q的中缀表示可以把这一关系拓展到其他函数及相似的结构 语句4N.Q可以看成是有两个参数的函数第一个参数是 4第二个参数是 Q三元表达式与单元运算符三元表达式Q_QQ有三个参数都为 Q 适当命名.QQQ 单元运算符如(Q 语句的语法树 Q4 Q4.4语句序列的语法树语句序列44D4；其中的语句的数目不定；只有前后顺序没有层次关联兄弟关系5、 二义性（）二义性文法：在其定义的语言中存在带有两棵或多棵不同分析树的句子的文法,无法唯一确定句子程序的语法结构。（）消除二义性的思想在尽量不改变被识别语言的条件下修改文法使其唯一地确定句子程序的语法结构 决定选择哪一棵树是正确的QUQQCQCN4U'C]C^上面文法的直观含义一个 Q 或者是一个 N4或者是一个带括号的 Q或者是两个Q 通过一个  连接起来；无论  是'(还是)。（）消除二义性的方法之设置优先权（）消除二义性的方法之设置结合性悬挂 . 问题下面的  语句的文法存在二义性4U ]4C- ]4U Q4C Q4.4QUC  -.- 有两棵分析树9消除二义性的方案大幅度修改文法把语句分成两类4-`4匹配的语句即不含不带 . 的  语句的语句N4-`4不匹配的语句即含有不带 . 的  语句的语句修改被识别语言加入  语句的结束标示需要相应地修改文法 ]4U Q-4]aC Q-4]a.4]a不修改文法及被识别语言而是在语法分析程序中额外加入最近嵌套的规则 编译器采用第二种方法第四章 自顶向下分析1、递归下降识别算法 基本思想：为每个非终结符 > 编写一个递归的识别过程 >；>识别由 > 推导出的串；关于 > 的文法规则就是 >的形式定义；文法规则的右部决定 >的代码结构；选择对应于替代情况；在一个选择中，终结符对应于与输入记号的匹配，非终结符对应于对相应识别过程的调用优缺点：优点简单易实现缺点对文法要求高需要使用 b?J 形式足以完成  语言编译器和 + 语言编译器的语法识别和分析工作重复和选择：使用 b?J利用 b?J 消除左递归： 利用 b?J 把QUQ4C4改写为QU4#4$b?J 在递归下降识别的优势：b?J 紧密映射递归下降识别程序的代码；能够通过选择提取左因子消除  语句的二义性；能够通过重复消除左递归；使用递归下降识别时应使用b?J。4 的 b?J 和识别过程4 的 b?J：4U #4N. $识别过程：N4,F ,"-.&^4-, ,"-.,4,2、 语法分析 递归下降计算器之 Q 的算法 NQF,F4&4,"-.&'&] '4-',4&4'4,]4-],4&4]4,,"-.,N4,Q,语法分析过程之 Q 的算法 NQ3Q,F4&4,"-.&'&]"4&4c,4-,. +-."4&4,F-+-."4&4,4&"4,"-.,N4,Q, 语句的语法分析过程 N K43Q,F4- ,4-,4&4K4 ,+-.4&Q,4-,