复习—编译原理第3章讲述

《复习—编译原理第3章讲述》由会员分享，可在线阅读，更多相关《复习—编译原理第3章讲述（56页珍藏版）》请在金锄头文库上搜索。

1、计算机学院计算机学院 * 编译原理编译原理 1 计算机学院 编 译 原 理 主讲人：郑丽萍 时间：2014-2015学年第二学期 联系方式： zhengliping80 计算机学院计算机学院 * 编译原理编译原理 2 词法分析程序又称扫描器，是编译过程的第一步，是下 一步进行语法分析的基础。词法分析的任务: 1. 从构成源程序的字符串中识别出一个个具有独立意义的 最小语法单位“单词”，并将其转化为内部编码形式。 2. 删除无用的空白字符和回车字符以及其他非实质性字符 。 3. 删除注释。 4. 进行词法检查,报告所发现的错误。 词法分析的任务 计算机学院计算机学院 * 编译原理编译原理 3 n

2、 逐个读入源程序字符，然后按照构词规则切分成一列 单词，再转换成单词序列。单词是语言中具有独立意 义的最小单位。 n 词标(token）是单词的机内表示，其格式由实现系统 规定。 单词符号一般可分为下列五种： n 基本字，关键字； n 标识符； n 常数（量）； n 运算符； n 分隔符 单词的划分 计算机学院计算机学院 * 编译原理编译原理 4 单词符号的内部表示 词法分析的功能是识别出的具有独立意义的单词，并转化为 相应的内部表示。 词法分析的输出常采用二元式(class，value),如图3.3所示 。class为以整数码或助记符,value则是该单词的值(如变量 名在符号表中的序号,常

3、数的二进制表示,以及运算符和分隔 符的编码,等等) class单词类别 value单词值 图3.3 词法分析程序的输出形式 计算机学院计算机学院 * 编译原理编译原理 5 由正规文法构造状态转换图 l 一个状态转换图是由一组矢线连接的有限个节点所组成的 有向图。 l每个节点均代表在识别或分析过程中扫描器的状态，其中 有一个是开始状态(带箭头)，至少有一个状态是结束状态（ 双圈）。 l状态间用矢线连接，矢线上标记有符号，表示在矢线射出 端的状态下，读入矢线上标记的符号可转换到矢线指向的状 态。状态图只有有穷个状态。 12 开始a 0 a b b 计算机学院计算机学院 * 编译原理编译原理 6 正

4、规文法形式：Aa或ABa（左线性）或AaB（右线性） 其中：A,BVn，aVt; 正规文法描述语言单词，状态转换图可识别单词，它们之间 存在等价关系。 一.对于右线性文法构造状态转换图 设G=(Vn,Vt,P,S)是一右线性文法,Vn中的每个非终结符号对 应状态图中的一个结点,且的开始符号所标记的结点为初 态结点; 增设一个不属于的符号F标记终态结点。 |VN|=k,共有k+1个节点（状态）。 计算机学院计算机学院 * 编译原理编译原理 7 1. 对于G中的每一条形如Aa的规则，从结点A引一条矢线到 终态结点F，并用符号a标记这条矢线。 2. 对于G中每一条形如AaB的规则，从结点A引一条矢线

5、到 结点B，并用符号a标记这条矢线。 注意: 文法G中含有无用符号和无用产生式须事先予以删除; 若L(G),则初态结点S也同时是一个终态结点; 若G中含有产生式A,则将结点A设置为终态结点; 右线性文法构造状态图规则 计算机学院计算机学院 * 编译原理编译原理 8 b a a bV S U a 例如：文法GS SaU|bV UbV|a VaU|b b Q 右线性文法状态图构造实例 计算机学院计算机学院 * 编译原理编译原理 9 状态转换图对符号串的识别 利用状态转换图可识别相应文法所表示的符号串。 12 开始a 0 a b b 定义：设VT * ，如果状态转换图中存在一条从初态到 终态的路径，

6、此路径上的标记符号顺序相连构成符号串 ，则称为状态图所识别串。 状态图识别语言：状态图所识别的串集合。 计算机学院计算机学院 * 编译原理编译原理 10 对符号串W=a1a2a3an，ai VT 识别过程： l 从初态S出发，自左至右逐个扫描W中的字符，在S状态下扫 视的符号为a1； l 在节点S所射出诸矢线中寻找标记为a1的矢线(若不存在， 则说明W有错)； l 读入a1，沿矢线方向到下一状态，在此状态时扫描a2， ， l 直至W中全部字符读完且进入终态F,则W已被接受。 对符号串的识别过程 计算机学院计算机学院 * 编译原理编译原理 11 状态图的一种实现-状态矩阵法 程序设计语言一般含有

7、若干类单词符号,我们可首先为每类 单词建立一张状态转换图,然后将这些状态转换图合并成一 张统一的状态图,最后再据此构造词法分析程序。 计算机内表示状态转换图的方法之一是状态矩阵。 状态矩阵：状态图中的各个状态S1，S2，Sn为行，以可 能输入的输入符号a1，a2，am为列，组成一个n行m列矩 阵。 计算机学院计算机学院 * 编译原理编译原理 12 a1 a2 am Bij=BSi,aj 含义：当前状态Si，正扫视符号aj，则以序偶（Si，aj）去查询 矩阵B，扫描器根据Bij的指示，执行相应的语义动作，转到Sk 状态。若某aj不与Si配对，即状态图中从节点Si不存在以aj为标 记的射出矢线，则

8、Bj置为“error”,进行词法错误检查和处理。 计算机学院计算机学院 * 编译原理编译原理 13 有限自动机（FA） u有限自动机是一种具有离散输入与输出系统的数学模型,是状 态转换图的形式化。在这种数学模型中有有限个状态，状态间 存在着转换关系。系统可以处于有限个状态中的任意一个之中 ，系统的当前状态概括了有关过去输入的信息。 u当系统处在某个状态之下读入一个字符时，会使系统所处的 状态发生变化，从而形成状态转换。改变后的状态称为后继状 态。 计算机学院计算机学院 * 编译原理编译原理 14 在状态转换中，后继状态可能为一个，也可能为多个。有限自 动机分确定的和不确定的。 所谓“确定的有限

9、自动机” ( Deterministic Finite Automata DFA)是指在当前的状态下，输入一个符号，有限自动机将转换 到唯一的后继状态； “不确定的有限自动机” (Nondeterministic Finite Automata NFA)在当前状态下输入一个符号，可能有两种或两种以上可选 择的后继状态。 有限自动机的分类 计算机学院计算机学院 * 编译原理编译原理 15 确定的有限自动机 1、确定的有限自动机定义 将前面介绍的状态转换图抽象,可得到一个确定的有限自动机 M（记作DFA M）是一个五元组:M=（ K， ，f，S0，Z） 其中： K：是一个有限状态的集合。 ：是一个

10、有限个输入字符组成的字母表 f：状态转换函数，是一个KK的单值映射， 形式 为f (p, a)=q 。 S0：S0K，是唯一的初始状态。 Z：ZK，称为终结状态集合。 可见,一个确定的有限自动机是相应的状态图的一种形式描述 。 这是一个单值函数，指明当前 状态为p，输入符号为a时，自 动机将从状态p转换到下一个状 态q，q称为p的后继状态。 计算机学院计算机学院 * 编译原理编译原理 16 DFA M=（S，U，V，Q，a，b，f，S，Q）其中 f定义为： f（S，a）=Uf（V，a）=U f（S，b）=Vf（V，b）=Q f（U，a）=Qf（U，b）=V 例：SaU|bV UbV|a VaU

11、|b b a a b V S U a b Q 计算机学院计算机学院 * 编译原理编译原理 17 2、确定的有限自动机状态图 u确定的有限自动机M可以用状态图来表示。 u状态图中的结点代表状态，它与自动机中的状态集合K相 对应，其中包括初始状态S0和终结状态集合Z。 u状态间用矢线连接，矢线上标记有输入符号，每条矢线 对应一个状态转换函数f，矢线上标记的输入符号集合就是 字母表。 计算机学院计算机学院 * 编译原理编译原理 18 3、确定的有限自动机状态转换矩阵 u确定的有限自动机M还可以用状态转换矩阵来表示。 u矩阵中的第一列元素与自动机中的状态集合K相对应，且 初始状态S0是第一列的第一个元

12、素，右上角标记*的元素对 应终结状态。 u矩阵中的第一行元素与字母表中的每个输入符号相对 应。矩阵中的元素对应每个状态转换函数。 u如果有状态转换函数f(p,a)=q,其中p,qK,a，那么 ，就在矩阵中状态p对应的行和符号a对应的列单元中填入q 。 计算机学院计算机学院 * 编译原理编译原理 19 4、确定的有限自动机接受的语言 为了讲解确定的有限自动机如何接受或识别字符串，首先， 我们对状态转换函数作补充定义： f(S,)=S f(S,aw)=f(f(S,a),w),a，w*，即w是上的字符串 例如,有f(0,a)=1 且f(1,b)=2,则 f(0,ab)=f(f(0,a),b)=f(1

13、,b)=2 对一个确定的有限自动机M以及某个字符串x（x*），如果 有f(S0, x)=S，且SZ，则字符串x就被该自动机M所接受。 即将f的定义域扩充到K* 计算机学院计算机学院 * 编译原理编译原理 20 u从状态图上看，如果一个字符串能被自动机接受，则存在 一条从初始状态到某一终结状态的通路，且将这条通路上所 有矢线标记的符号一次连接起来就组成了字符串x。 u若初始状态也是终结状态，或是存在一条从初始状态到某 一终结状态的路径，路径上的所有标记都是，则可被 DFA接受。 u一个确定的有限自动机M所接受的语言就是所能接受的字 符串构成的集合，用L（M）表示，可定义为： L（M）=x|f(S

14、0,x)Z，x* 计算机学院计算机学院 * 编译原理编译原理 21 l DFA的确定性表现在转换函数 :KK是一个单值函 数，即：对任何状态kK以及输入符号a，(k,a)能唯 一确定下一个状态。 l 从状态转换图来看，若字母表含有n个输入字符，那么 任何一个状态结点最多有n条弧射出，而且每条弧以一个不 同的输入字符标记。 总 结： 计算机学院计算机学院 * 编译原理编译原理 22 非确定的有限自动机 非确定的有限自动机与确定的有限自动机的区别主要是状 态转换函数f为多值函数。 1、非确定的有限自动机定义 一个非确定的有限自动机NFA M是一个五元式 M=（K，f，S0，Z） 其中:K：有穷状态

15、集; ：输入字母表 S0：开始状态S0K; Z：终止状态集ZK f：状态转换函数，为K到K的子集的映射。 形式为 f( Si, aj )=Sk1,Sk2,Skm 非确定的有限自动机同样可以用状态图和状态转换矩阵来 表示，表示方法与确定的相同。 计算机学院计算机学院 * 编译原理编译原理 23 2、非确定的有限自动机接受的语言 与确定的有限自动机一样，为了判别一个字符串x能否被NFA M 接受，我们还需要对状态转换函数做补充定义：f(S,)=S f(S,aw)=f(f(S,a),w),a,w* 再设f(S,a)=Sk1,Sk2, , Skm 且定义 f(Sk1,Sk2,Skm,w)=mi=1f(

16、Ski,w) 表示从M的当前状态集出发，扫描字符串x后，所到达的状态集 等于从当前状态集的每一个状态出发，扫描字符串x后所到达 的状态集之和。 即将f的定义域扩充 到2K* 计算机学院计算机学院 * 编译原理编译原理 24 对于某个字符串 x（x *）， 若有f (S0, x )=K，且K Z ，则x为M所接受。 从状态图上看，如果一个字符串能被非确定的自动机接 受，则至少存在一条从初始状态到某一终结状态的通路 ，且将这条通路上所有矢线标记的符号依次连接起来就 组成了字符串x。 NFA M所接受的语言为 L（M）=x | f(S0, x )Z ， x * NFA所接受的语言 计算机学院计算机学院 * 编译原理编译原理 25 *上的符号串t被NFA M接受也可理解为： l 对于中