编译原理：第4章 词法分析（1、2、3）

1、第4章 词法分析本章重点词法分析器的设计技术，即有穷状态自动机技术和正则式技术正则文法、正则式、非确定的有穷状态自动机（NFA）、确定的有穷状态自动机（DFA）之间的等价性及相互变换的方法。4.1 词法分析程序的设计 1 词法分析程序的功能 源程序 单词序列 2 单词的词类和属性 （词类符号，单词的属性值） 3 把词法分析设计成一个独立程序 (1) 语法分析程序的子程序； （2）组织成一遍扫描。词法分析器=80;eniLLine=80;=;输入031字母字母数字数字数字=；4562001字母1字母1字母200=5000=53数字3数字3数字3数字44；6输出1字母1字母 id , Line =

2、 , num, 80 ;, 有限控制器分析结束While ij do if ij then i:i-j else j:=j-i while ， i ， ， j ， do ， if ， i ， ， j , then , i , := , i, - , j ,else, j , := , j , - , i 词法分析器1 词法分析程序的功能程序语言单词的分类： 1关键字(保留字或基本字)：begin, end 2标识符：用来表示各种名字 3字面常数：256，3 .14，true, abc 4 运算符：如，、*、/ 等等 5分界符：如逗号，分号，冒号等2 单词的词类和属性词法分析器的输出： （词类编

3、码，单词自身的属性值）* 词类编码提供给语法分析程序使用；* 单词自身的属性值提供给语义分析程序使用。具体的分类设计以方便语法分析程序使用为原则。关键字可分成一类，也可以一个关键字分成一类。常数可统归一类，也可按类型( 整型、实型、布尔型等)，每个类型的常数划分成一类。单词自身的属性值提供的内容，是由词法分析和语义分析的任务划分决定的。2 单词的词类和属性例如：图3.1的源程序经词法分析器的输出while， id，指向i的符号表入口的指针relop ， NE id，指向j的符号表入口的指针do， if， id，指向i的符号表入口的指针 id，指向j的符号表入口的指针3 把词法分析设计成一个独立

4、程序 （1）组织成一遍扫描；（2）作为语法分析和语义分析的子程序词法分析语法分析语义分析和中间代码生成源程序中间代码 符 号 表 管 理 错 误 的 诊 查 处 理（1）词法分析程序的主要任务扫描源程序，产生单词符号（2）词法分析程序的其他任务滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序，宏展开，（3）就词法分析工作从语法分析工作独立出来的原因简化设计改进编译效率增加编译系统的可移植性 词法分析程序的工作实例 PL/0编译程序的结构图扫描器分析器代码生成器表格管理出错管理目标程序（中间代码）以PL/0（2.2节，P16）为例=数据流，调用关系PL/0编译器等用一趟（pass）扫描方式

5、 以语法分析器为核心，扫描器和代码生成器都作为一个独立过程，由分析器调用。（当语法分析正确，调用代码生成器）图1（a）PL/0编译程序的结构图实例 PL/0编译程序的结构图扫描器分析器代码生成器表格管理出错管理目标程序（中间代码）PL/0语言目标程序PL/0语言解释执行程序输入数据输出数据图1(a) PL/0编译程序的结构图图1(b) PL/0解释执行结构图 4 扫描器的接口设计扫描器以两种方式与语法分析器连接： （1）词法分析可作为单独一遍来实现词法分析器处理字符串源程序，输出是关于单词符号序列的中间文件，供语法分析使用。 字符串源程序 词法分析 单词符号串源程序 图词法分析单独作为一遍 （

6、2）词法分析程序作为语法分析程序的子程序 有些编译程序将词法分析和语法分析安排在同一遍中，此时词法分析作为语法分析程序的一个子程序。每当语法分析需要一个新的单词符号时，就调用词法分析子程序，词法分析子程序从字符串源程序中识别出一个具有独立意义的单词，将其单词符号返给语法分析。字符串源程序 词法分析器 语法分析器 图词法分析作为语法分析子程序 取单词 送单词扫描器主要操作（1）next-char（输入模块: 读下一字符）返回字符以全局量或参数形式传给其他模块（2）error（错误处理模块）发现非法的单词符号（3）识别单词（核心任务）构造单词的内部表示-属性字（语义字）难点：词法的三种表示：正则文

7、法、正则式、状态转换图（即FA）。三者之间的等价性及相互变换的方法。4.2 单词的定义及识别单词的描述工具 （1）正则文法（2）正则表达式（3）有穷状态自动机FA正则文法擅长正则语言的生成。FA 擅长正则语言的识别。正则表达式具有简单化和数学化的特点，更接近语言的集合表示和语言的计算机表示。1 单词定义(正则文法,3型文法）定义：如：标识符的文法定义I- aA|bA|zAA- aA|bA|zA|A- 0A|1A|9A|或用l代表字母，d代表数字则I-lAA-lA|dA|识别单词的装置：FA（finite automata） 2 正则语言的识别装置-FA 为了构造词法分析器，要研究构词法、每种词

8、类的结构模式以及识别它的数学模型有穷自动机FA。 FA的模拟程序可以作为词法分析器的控制程序。(1) 有穷自动机（FA）的三种表示形式(2) 根据正则文法来构造FA(3) 编写词法分析程序（依据“描述模型”进行系统实现）有穷自动机FAa1a2a3a4ajan#把FA看作由一个读头和一个有穷状态转换器组成。开始状态后继符号有穷状态转换读头输入带有穷自动机FA（1）它可以从左至右从带上一次读一个字符， 每读一个字符改变一次状态；（2）在开始读字符前，FA处于开始状态；（3）有一些状态指定为终止状态；（4）当FA处于终止状态又准备读带右边的字符时，带上的字符串就被FA识别或接受，或者说，该串 L(F

9、A)。有穷自动机FAFA 定义了正则语言集合。FA 对于上的任意串w，能够判定它是可接受的还是不可接受的。若FA处于状态qi，正在读字符a，而状态应转换为qj ，则（a） f (qi, a) = qj, f: 状态转换函数或映射（b） 状态装换图，节点代表状态，弧代表转换，弧上符号代表输入字符， ：开始状态， ：代表终止状态（c）矩阵方式 M qi, a = qj qiqjaMaqiqj（1）有穷自动机的三种表示形式例： 给出识别语言 以i为首的i，d串 的FA的三种形式。解： FA Mii,dBA 状态 idFABBBB1状态转换矩阵f (A, i) = Bf (B, i) = Bf (B,

10、 d) = B(B为终止状态)（1）有穷自动机的三种表示形式例：识别语言 L = 以i为首的i、d串的FA的转换规则 MidFq1q20q2q2q21q1iq2di FA 正则文法f(q1, i)=q2 q1 iq2f(q2, i)=q2 q2 iq2| dq2|f(q2, d)=q2 （ q2 为终态）（1）有穷自动机的三种表示形式 图 标识符及无符号数的状态转换图(a) 标识符；(b) 无符号整数；(c) 无符号数有穷自动机简介（*）在线性时间模型中, 认为一次执行可完全由状态（或系统的事件）建模, 称为一个执行轨迹 (trace)。系统的行为就是这样的执行序列的集合。 由于序列的集合 是

11、一种形式语言, 这自然导致了使用自动机用于系统的规范（定义）和验证。27状态转换图显示了一个由状态、转换组成的状态机。 有限自动机的状态转换图说明系统的动态视图。状态图强调一个对象按事件次序发生的行为。有穷自动机简介（*）28有穷自动机的一个实例（2） 根据正则文法来构造FA已知： G = (VN，VT，P，S )是正则文法，不失一般性，假定规则是右线性，用文法的非终极符作为状态，开始符号作为开始状态。再增加一个新的符号R，作为终止状态。若文法中有：qiaqj 则 f(qi,a) = qj qj a 则 f(qj,a) = R S 则 S也作为终止状态例：(a) 文法定义 迭代.e+|-(b)

12、 正则式表示（简洁）dd*(.dd*|)(e(+|-|)dd*|)（2） 根据正则文法来构造FA(C) FA：（识别）d.dNN1ON2N3N4N5ON6OOOOOOO空格deedd+/-l=:(l/d=dother=标识符超前搜索识别PL/0 所有单词的FAd.正则文法（无符号数）： NdN1N1dN1|.N2|eN4| N2dN3 N3dN3|eN4| N4dN5|+N6|-N6N5dN5| N6dN5 根据画出的（识别单词的）状态转换图构造词法分析程序，每个状态对应一段程序，完成到达此状态的工作；词法分析程序的控制程序模拟状态转换图的状态转换。 在识别标识符的过程中，要把标识符拼写出来，

13、并和保留字区别开来；在识别常数的过程中，要把它转换成机器表示以作为属性值。（3） 编写词法分析程序Start: getch;While (ch= ) do getch ; /*l滤掉无用的空格*/ case char of a.z: beginWhile letter or digit dobegin concat; getch end; /连接字符串 c:=reserve; /*查保留字表 */ if c=0 then return($ID,val) else return(c，-）end;（3） 编写词法分析程序0.9:begin While digit do begin /*concat

14、 连接字符串*/ concat; getch； end; Return($INT, val) end;3 编写词法分析程序+: Return($plus, _);-: Return($minus, _);): Return($rpar, _);:begin /*读取下一个字符,查看这一字符是否为=,若是即为=,否则为= 0）anbmck| n, m, k = 0， SaS|B BbB|C CcC|四 自动机（带有空转换的FA）确定化带有空转换的NFA的确定化算法： 由-NFA构造等价的DFA的算法与不带有空转换的NFA确定化的算法类似，只是需要引进状态集的-闭包（-CLOSURE）的概念，并在

15、算法中，凡是涉及到状态集时就用与它相对应的-闭包代替。定义状态集I 的空闭包：设I是一状态集，C(I)是其空闭包（-closure(I)）， 1 若PI，则 PC(I)； 2 对于PI，若 f(P, )=Q，则QC(I)； 即从P出发，经过任意条弧所能到达的任何状态Q，都属于C(I)。在确定化算法中，状态集由它的闭包代替，即可消除转换四 自动机（带有空转换的FA）确定化有如下定理：对任何一个具有转移的不确定的有穷自动机NFA N，一定存在一个不具有转移的不确定的有穷自动机NFA ，使得L(M)=L(N)。 NFAMabFSSAAA1 -NFA到DFA的确定化 实例SaAbDFAM abF SA

16、SAA1AA1122b1ab -NFA到DFA的转化 实例NFA MabFSA，DABADBCCEDDAE1解： 该NFA M识别的语言是L（M）=(a|b)*abb ，确定化的DFA M的状态转换矩阵及状态图分别如下图所示。 NFA M的状态转换矩阵BabESAbCbDaaDFA MabF 0 SADBADAD1 ABDBADACD2 ADBADAD3 ACDBADAED4 ADEBADAD1转换后的 DFA M的状态转换矩阵NFA MabFSA，DABADBCCEDDAE1DFA MabF0 SADBADAD1 ABDBADACD2 ADBADAD3 ACDBADAED4 ADEBADAD

17、1转换后的 DFA M的状态图3bb401aa2babbaa五 FA与正则文法的关系定理1：对任意的正则文法G=（ VN, VT, P, S），都存在一个有穷自动机A，使得L(A)=L(G)定理2：对任一DFA(或NFA)，都存在一个正则文法G，使L(G)=L(A)合并：一文法G是正则的，当且仅当存在一个FA，使L(G)=L(M) x L(G)x L(M)五 FA与正则文法的关系（1）正则文法FA (见前述:本课件28页)（2）FA正则文法（VN，Vt ，P，S） 设FA M=(Q,q0, F) 对于 转换函数(A, t) =B，可写一产生式 AtB 对于可接受状态z，增加一产生式z 此外：S=q0 VT =（FA的字母表）补充：左线性正则文法G构造 FA M具体步骤：（1）对于 A-a的产生式，按归约理解，句子中的第1个字符，都是用A-a的产生式进行归约的.对应到FA中，FA从开始状态出发，读到句子的第一个字符a,将它归约为A。此时引用初态 q, 定义为：f(q,a)=A.（2）对于 A-Ba的产生式，FA应该在状态B读入 a,其状态转为A , 即 f(B,a)=A. 也可理解为在状态B时，FA已将当前句子处理过的前缀归约成了B，此时它读入 a时，要将Ba归约为A。（3）按