1、编编 译译 原原 理理第第 三三 章章词法分析和词法分析程序词法分析和词法分析程序Principles of Compiler DesignChapter 3.Lexical Analysis东华大学计算机学院3.1 设计扫描器时应考虑的问题设计扫描器时应考虑的问题 词法分析程序亦称为扫描器词法分析程序亦称为扫描器 任务：扫描程序，识别单词任务：扫描程序，识别单词 扫描器的输出是语法分析程序的输入扫描器的输出是语法分析程序的输入东华大学计算机学院3.1 How to construct a lexical analyzer A lexical analyzer is also called S
2、canner The main task of the lexical analyzer is to read the input characters of the source program,and group them into lexemes.The lexical analyzer outputs a sequence of tokens for each lexeme in the source program to the parser for syntax analysis.东华大学计算机学院3.1.1 词法分析的必要性词法分析的必要性 描述单词的结构比其它语法结构简单，仅描
3、述单词的结构比其它语法结构简单，仅用用3型文法就够了；型文法就够了；将单词识别从语法分析识别分离出来，可将单词识别从语法分析识别分离出来，可采用更有效的工具实现；采用更有效的工具实现；有些语言的单词识别与前后文相关，不宜有些语言的单词识别与前后文相关，不宜将其与语法分析合并；将其与语法分析合并；使编译程序各部分独立出来，有利于设计、使编译程序各部分独立出来，有利于设计、调试和维护调试和维护东华大学计算机学院3.1.1 Lexical Analysis Versus Parsing The separation of lexical and syntactic analysis often le
4、ads to a cleaner overall design.Compiler efficiency is improved.A separate lexical analyzer allows us to apply specialized techniques that serve only the lexical task,not the job of parsing.Compiler portability is enhanced.Input-device-specific peculiarities can be restricted to the lexical analyzer
5、.东华大学计算机学院3.1.2 单词符号的内部表示单词符号的内部表示常用的内部表示方法常用的内部表示方法:为便于阅读，常用为便于阅读，常用助记符助记符（或（或常量标识常量标识符、宏定义等）符、宏定义等）表示表示。单词的分类方法：可单词的分类方法：可（+、-、begin、end等）或等）或（如关键字（如关键字类、操作符类、分隔符类、变量名类、类、操作符类、分隔符类、变量名类、常数类等）。常数类等）。在识别出变量名、函数（过程）名时，在识别出变量名、函数（过程）名时，还应进行还应进行的工作。的工作。东华大学计算机学院3.1.2 Tokens A token is a pair consisting
6、 of a token name and an optional attribute value The token name is an abstract symbol representing a kind of lexical unit,e.g.,a particular keyword,or a sequence of input characters denoting an identifier.The token names are the input symbols that the parser processes.We will often refer to a token
7、by its token name.东华大学计算机学院3.1.3 识别标识符的若干约定和策略识别标识符的若干约定和策略 一般来说，单词的长度是有限制的。一般来说，单词的长度是有限制的。在允许长度下，应按最长匹配原则进在允许长度下，应按最长匹配原则进行识别行识别 有时需要超前扫描来进行单词识别。有时需要超前扫描来进行单词识别。在进行超前扫描时，还应注意在进行超前扫描时，还应注意“回退回退”字符，即将多吃掉的字符退还回输入字符，即将多吃掉的字符退还回输入缓冲区。缓冲区。东华大学计算机学院3.1.3 Token Recognition All tokens have finite length.To
8、kens are recognized when all possible symbols are scanned.Sometimes we need to look at least one additional character ahead.3.2 正规文法和状态转正规文法和状态转换图换图3.2 Regular Expressions&Transition Diagrams东华大学计算机学院3.2.1 由正规文法构造状态转换图由正规文法构造状态转换图 程序设计语言的单词都能用正规文法程序设计语言的单词都能用正规文法描述描述 一般说来，凡能用正规文法描述的语一般说来，凡能用正规文法描述的语
9、言，均可言，均可由某种有限状态算法由某种有限状态算法进行分析进行分析 状态转换图：状态转换图：有向图（一个初态有向图（一个初态+N个终态）个终态）射出结点，进入结点射出结点，进入结点东华大学计算机学院3.2.1 Conversion from regular-expression patterns to transition diagrams Tokens can be described by regular-expression Such tokens can therefore be analyzed by transition diagrams.Transition diagram:D
10、irected flowcharts with one (one state of lexemeBegin and some states called final)东华大学计算机学院构造状态转换图（一）构造状态转换图（一）由右线性文法构造状态转换图由右线性文法构造状态转换图G=(VN,VT,P,S)是右线性文法，是右线性文法，|VN|=K。状态转换图共有状态转换图共有K+1个状态个状态(结点结点)。构造规则：构造规则：AaB，从结点从结点A引一有向引一有向边到结点边到结点B,并用并用a标记这一有向边标记这一有向边;Aa，从结点从结点A引一有向边到终态结点引一有向边到终态结点F,并用并用a标记
11、这一有向边标记这一有向边;A，则将结点则将结点A设为终态。设为终态。东华大学计算机学院Transition diagram construction(1)From collections of regular expressions.Given G=(VN,VT,P,S)a set of regular expressions,with|VN|=K.There are K+1states in the diagram.For AaB,an edge from states A to B,it also be labeled with a.For Aa,an edge from A to fin
12、al state F,it is labeled with a.When A,state A is final itself.东华大学计算机学院构造状态转换图（一）构造状态转换图（一）无符号数的文法对应的无符号数的文法对应的状态转换状态转换图图0452136d.dddd.E+|-Edd东华大学计算机学院Transition diagram construction(1)Diagram for grammar of numeric0452136d.dddd.E+|-Edd东华大学计算机学院构造状态转换图（一）构造状态转换图（一）由右线性文法构造状态转换图由右线性文法构造状态转换图识别串：字符串识
13、别串：字符串w=a1a2an,ai VT从初态出发从初态出发,分别沿一切可能的路径到分别沿一切可能的路径到达终态结点达终态结点,并将所有矢线上所标记的并将所有矢线上所标记的字符依次连接起来，便得到状态转换字符依次连接起来，便得到状态转换图所能识别的全部符号串，这些符号图所能识别的全部符号串，这些符号串组成的集合构成了该文法识别的语串组成的集合构成了该文法识别的语言。言。东华大学计算机学院Transition diagram construction(1)From regular expressionRecognition of input string:w=a1a2an,ai VTBegins
14、 in the initial state,advance along any available edges and reaches the final state.All such strings formed by concatenating all edge labels form the collection of sentences that can be recognized by the diagram.东华大学计算机学院构造状态转换图（一）构造状态转换图（一）由右线性文法构造状态转换图由右线性文法构造状态转换图识别串：字符串识别串：字符串w=a1a2an,ai VT实际：建立
15、推导实际：建立推导 S*w第一步第一步 下扫描到下扫描到 而过渡到下一状态而过渡到下一状态A1，由构造规则可知，由构造规则可知，中必有产生式中必有产生式。后续步骤中，由状态后续步骤中，由状态Ai识别识别后过渡到后过渡到恰好对恰好对应了使用产生式应了使用产生式最后在状态最后在状态识别识别 后到达终态后到达终态，对应了使用，对应了使用产生式产生式进行推导：进行推导：东华大学计算机学院右线性文法与状态转换图右线性文法与状态转换图相应的相应的：(1)利用利用对符号串对符号串 进行识别进行识别,中状态转换模拟一中状态转换模拟一步直接推导步直接推导,即识别方法即识别方法(或称分析方法或称分析方法)为为“”
16、(2)右线性文法右线性文法只有产生式只有产生式，每一步推，每一步推导结果只含一个非终结符，导结果只含一个非终结符，规范规范推导推导(3)所识别的任一符号串所识别的任一符号串，存在，存在G中的一个推导中的一个推导(即有即有；反之；反之,对于对于中任一句子中任一句子，必存在一条从初态必存在一条从初态 到终态到终态 的路径的路径,此路径上各矢此路径上各矢线标记依次拼接组成的符号串为线标记依次拼接组成的符号串为东华大学计算机学院构造状态转换图（二）构造状态转换图（二）由左线性文法构造状态转换图由左线性文法构造状态转换图用用G的的VN符标记符标记M的结点，其中，的结点，其中，开始符开始符S对应的结点为终
17、态结点。对应的结点为终态结点。引入一个新结点：初态引入一个新结点：初态东华大学计算机学院构造状态转换图（二）构造状态转换图（二）矢线的连接规则为矢线的连接规则为:对于对于 中形如中形如 的产生式的产生式,引矢线引矢线 且标记为且标记为;对于对于G中形如中形如 的产生式的产生式,引矢线引矢线,且标记为且标记为.东华大学计算机学院构造状态转换图（二）构造状态转换图（二）例：例：文法文法G=(S,U,0,1,SS1|U1,UU0|0,S)东华大学计算机学院构造状态转换图（二）构造状态转换图（二）文法文法G=(S,U,0,1,SS1|U1,UU0|0,S)识别句子识别句子 东华大学计算机学院识别符号串
18、与归约识别符号串与归约 从初态从初态 到下一状态到下一状态A对应对应，即终结符即终结符 归约成非终结符归约成非终结符;从状态从状态B转换到状态转换到状态 对应对应,即将即将归约为归约为;状态状态 转换到状态转换到状态(终态终态)对应对应,即将即将归约为开始符归约为开始符.归约成功归约成功,恰好进入终态恰好进入终态,即状态转即状态转换图识别了换图识别了(或接受或接受)该符号串该符号串.识别识别的例子的归约过程的例子的归约过程东华大学计算机学院3.2.2 状态矩阵法状态矩阵法构造状态矩阵，构造状态矩阵，控制程序控制程序对单对单词加以识别词加以识别开始开始初始化初始化getchargetchar()
19、()查状态矩阵（查状态矩阵（state,symbolstate,symbol）end?end?回退一个字符回退一个字符东华大学计算机学院3.2.2 状态矩阵法状态矩阵法 它所它所对应的状态转移矩阵如图：对应的状态转移矩阵如图：状态状态a ab b0 01 12 21 13 32 22 21 13 33 33 33 3东华大学计算机学院词法分析程序构造过程词法分析程序构造过程正规表达式正规表达式构造识别该正规表构造识别该正规表达式的带达式的带 的自动机的自动机将将-自动机转化为自动机转化为DFA，并且最小化并且最小化根据最小化的根据最小化的DFA构造状态矩阵构造状态矩阵编写控制程序，对编写控制程
20、序，对词法进行识别词法进行识别3.3 有限自动机有限自动机状态转换图状态转换图实际上是实际上是有限自有限自动机动机的图形表示的图形表示东华大学计算机学院3.3.1 确定的有限自动机确定的有限自动机DFA 五要素五要素 M=(K,f,S0,Z)状态集合状态集合字母表字母表状态映射状态映射初态初态终态集终态集v状态映射状态映射 f：K Kv可将可将f定义域推广为定义域推广为 K*K (1)f(s,)=s,s K;(2)f(s,aw)=f(f(s,a),w),s K,a,w*;v所以，所以，f与与f不可区分不可区分东华大学计算机学院识识 别别 DFA M识别识别*中的中的x：从初态从初态S0出发出发
21、，经经一恰好标有一恰好标有x 的路径后可达到某终态的路径后可达到某终态S Z 即：即：f(S0,x)=S，S Z M的接受集的接受集 L(M)=x|f(S0,x)Z,x*DFA：给一状态，一字符，则唯一确定下给一状态，一字符，则唯一确定下一状态一状态 任一正规文法任一正规文法G，都存在一个都存在一个DFA M，使使得：得：L(G)=L(M)东华大学计算机学院习习 题题 对于文法：对于文法：G=(S,A,B,C,D,a,b,c,d,P,S)，P由如下产生式组成：由如下产生式组成：SaA|B AabS|bB Bb|cC CD Dd|bB （1）构造该文法的状态转换图）构造该文法的状态转换图 （2）
22、构造一等价的左线性文法）构造一等价的左线性文法东华大学计算机学院3.3.2 非确定的有限自动机非确定的有限自动机 NFA M=(K,f,S0,Z)f：K(K)，即将即将(Si,aj)映射到映射到K的一的一个子集个子集Sk1,Skm 即下一状态不唯一即下一状态不唯一 可类似地，把可类似地，把f的定义域拓广到的定义域拓广到K*(1)f(S,)=S;(2)f(S,aw)=f(f(S,a),w)a,w*mikkkkwSfwSSSfwaSffawSfim1),(),(),(),(21东华大学计算机学院NFA的接受集的接受集 L(M)=x|f(S0,x)Z ,x 例：例：识别符号串识别符号串ababb东华
23、大学计算机学院3.3.3 NFA与与DFA的等价性的等价性 NFA的确定化：构造一的确定化：构造一DFA，使得它使得它们有相同的接受集们有相同的接受集 思路：使思路：使DFA的状态与的状态与NFA某一状态某一状态子集相同子集相同v定理定理3.1v例：例：M=(S0,S1,a,b,f,S0,S1)v此确定化算法的弱点此确定化算法的弱点东华大学计算机学院3.3.4 具有具有 动作的动作的FA 允许对允许对 作转移作转移 例：例：vf也可以拓广到也可以拓广到f:K*(K).f(S,x)是由这样的状是由这样的状态态Q组成组成,存在从存在从S到到Q的路径的路径,该路径上的连线标记组成的该路径上的连线标记
24、组成的符号串恰好为符号串恰好为x,其中其中,允许有允许有有限个标记为有限个标记为 v串串aacc可被接受可被接受东华大学计算机学院状态状态S的的-闭包：闭包：-CLOSURE(S)定义定义 (1)S-CLOSURE(S);(2)设设Sj-CLOSURE(S),且且Sj Sk,则则Sk-CLOSURE(S);(3)有限地使用规则有限地使用规则（2）所得所得的集合为的集合为-CLOSURE(S).例例东华大学计算机学院f的定义的定义RqRqKKKwSfqwqfwRfaqfaRfKRRfRffaqfawSffPPCLOSUREwaSfSCLOSURESfwaKS),(),()4(),(),(:)(2
25、,22:)2(,)3(),(),(,);(),()2();(),()1(,*),(*对的定义拓广到及将实际上其中东华大学计算机学院 f与与f不相等不相等f(S,a)-CLOSURE(f(S,a)f(S,a)只走一步只走一步a矢线矢线|多步，第一步必须走多步，第一步必须走a矢线矢线|路径路径a：第一步可以是第一步可以是 矢线矢线v-NFA的接受集：的接受集：L(M)=w|f(S0,w)Zv-NFA的用途：构造更复杂的的用途：构造更复杂的FA东华大学计算机学院3.3.5 -FA的确定化的确定化 构造一构造一DFA，使使得它与得它与-FA等价。等价。例例东华大学计算机学院习题习题 试将下面的试将下面
26、的-FA确定化为确定化为DFA:S125634F东华大学计算机学院习题习题 试将下面的试将下面的-FA确定化为确定化为DFA:S125634F-CLOSURE(S)=S,1,2=q0F(q0,a)=1,2,3=q1F(q0,b)=1,2,4=q2F(q1,a)=1,2,3,5,6,F=q3F(q1,b)=1,2,4=q2F(q2,a)=1,2,3=q3F(q2,b)=1,2,4,5,6,F=q4F(q3,a)=1,2,3,5,6,F=q3F(q3,b)=1,2,4,6,F=q5F(q4,a)=1,2,3,6,F=q6F(q4,b)=1,2,4,5,6,F=q4F(q5,a)=1,2,3,6,F
27、=q6F(q5,b)=1,2,4,5,6,F=q4F(q6,a)=1,2,3,5,6,F=q3F(q6,b)=1,2,4,6,F=q5东华大学计算机学院3.3.6 DFA状态数的最小化状态数的最小化 对一个对一个DFA M，构造另一个，构造另一个DFA M，使，使得：得：L(M)=L(M)，后者有最小的状态数，后者有最小的状态数 可区分状态：可区分状态：s,t K，若，若 w*，f(s,w)=q Z，而，而f(t,w)=p Z，则，则s,t为一串为一串w所区分所区分 s和和t等价：等价：w，f(s,w)Z，f(t,w)Z 所以，可以将等价的状态合并所以，可以将等价的状态合并东华大学计算机学院最
28、小化算法最小化算法 算法主要思想：将算法主要思想：将K划分为划分为r个个互不相互不相交交的子集，子集内任何两个状态是等的子集，子集内任何两个状态是等价的，而不同子集任两个状态可区分。价的，而不同子集任两个状态可区分。例：例：东华大学计算机学院3.4 正规表达式及正规集正规表达式及正规集 L（G）L（M），），即：正规文法与即：正规文法与FA等价等价 所以，现在来为一个正规表达式构造所以，现在来为一个正规表达式构造一等价的一等价的FA东华大学计算机学院3.4.1正规表达式及正规集的定义正规表达式及正规集的定义 设设 是一字母表是一字母表,则则 上的正规表达式上的正规表达式(正则表达式正则表达式,
29、正规式正规式)及其表示的正规集可递归定义如下及其表示的正规集可递归定义如下:(1)是一正则表达式是一正则表达式,相应的正规集为相应的正规集为;(2)是一正则表达式是一正则表达式,相应的正规集为相应的正规集为;(3)a,a 是一正则表达式是一正则表达式,相应的正规集为相应的正规集为a;(4)设设r,s是正则表达式是正则表达式,且它们所表示的正规集为且它们所表示的正规集为Lr,Ls,则则 1.(r)(s)是正则表达式是正则表达式,相应的正规集为相应的正规集为LrLs;2.(r)|(s)是正则表达式是正则表达式,相应的正规集为相应的正规集为Lr Ls;3.(r)*是正则表达式是正则表达式,相应的正规
30、集为相应的正规集为Lr*有限地使用上面的规则有限地使用上面的规则(4),所得的表达式均是正规表所得的表达式均是正规表达式达式东华大学计算机学院例子例子 a*,aa*,a|ba*,(a|b)(a|b)(a|b)*正规集正规集1：n正规式正规式 正规式正规式r=正规式正规式s Lr=Ls东华大学计算机学院正规式的基本等价关系（公理）正规式的基本等价关系（公理）A1.r|s=s|r A2.r|r=rA3.r|=r A4.(r|s)|t=r|(s|t)A5.(rs)t=r(st)A6.r(s|t)=rs|rtA7.(s|t)r=sr|st A8.r=r=A9.r=r=r A10.r*=(|r)*=|r
31、r*东华大学计算机学院3.4.2 由正规文法构造相应的正规式由正规文法构造相应的正规式例：例：SaS|bA|b，AaS改写为：改写为：S=aS+bA+b，A=aS S=aS+baS+b =(a+ba)S+b 结果：结果：S=(a+ba)*b (a|ba)*b或：或：S=a*(baS+b)=a*baS+a*b =(a*ba)*a*b东华大学计算机学院3.4.2 由正规文法构造相应的正规式由正规文法构造相应的正规式 论断论断3.1 方程方程x=rx+t 有解有解 x=r*t 左线性文法左线性文法：x=xr+t的方程，有解的方程，有解x=tr*东华大学计算机学院3.4.3 正规式构造正规式构造FAT
32、hompson法法 对运算符个数对运算符个数n进行递归进行递归 算法：算法：1、n=0时：时：r=r=r=asffsfa2、设当、设当n=1,2,k-1时时,M均可构造均可构造,当当n=k时时,根据正规式的根据正规式的定义定义,r只能是只能是 r1|r2,r1r2,r1*这三种形式之一这三种形式之一.其中其中,r1,r2 中中最多含最多含k-1个运算符个运算符,且设相应的自动机为且设相应的自动机为M1=(K1,f1,S01,Sf1)L(M1)=Lr1M2=(K2,f2,S02,Sf2)L(M2)=Lr2K1K2=东华大学计算机学院Thmopson 法法(续续)(1)r=r1|r2,引入新开始状
33、态引入新开始状态S0,终态终态Sf,将将M1,M2并联并联:S01Sf1S02Sf2sSf (2)r=r1 r2,将将M1,M2串联串联S01Sf1S02Sf2(3)r=r*,引入新开始状态引入新开始状态S0,终态终态Sf,令原令原M1构成循环构成循环S01Sf1SSf 东华大学计算机学院习习 题题东华大学计算机学院习习 题题东华大学计算机学院习习 题题S=a(a+b)*b(a+b)*a(a+b)*b(a+b)*解：解：A=(a+b)*b(a+b)*a(a+b)*b(a+b)*;S=aA;A=(a+b)A+b(a+b)*a(a+b)*b(a+b)*;B=(a+b)*a(a+b)*b(a+b)*;A=(a+b)A+bB;B=(a+b)B+a(a+b)*b(a+b)*;C=(a+b)*b(a+b)*;B=(a+b)B+aC;C=(a+b)C+b(a+b)*;D=(a+b)*;C=(a+b)C+bD;D=(a+b)D;
