ch4 词法分析.ppt

《ch4 词法分析.ppt》由会员分享，可在线阅读，更多相关《ch4 词法分析.ppt（86页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、词法分析程序的设计单词的描述工具单词的识别系统实现词法分析程序的自动构造第4章 词法分析4.1词法分析(lexical analysis)程序设计逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留关键字、标识符、常量、运算符、标点符号、分界符等。词法分析是编译过程中的一个阶段，在语法分析前进行。也可和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。4.1.1词法分析程序和语法分析程序的关系源程序词法分析程序语法分析程序Tokenget token.4.1.2词法分析程序的主要任务及输出词法分析程序的主要任务及输

2、出读源程序，产生用二元组表示的单词符号读源程序，产生用二元组表示的单词符号(单词种类，单词自身的值单词种类，单词自身的值)。单词种类是语法分析需要的信息，单词自身的值是语义分析和代码生成阶段需要的信息。如 const i=25,yes=1;两个单词种类是常数，常数值分别为25,1.滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符记录源程序的行号，以便出错处理程序准确记录源程序的行号，以便出错处理程序准确定位源程序的错误定位源程序的错误宏展开等宏展开等 词法分析程序的主要任务词法分析程序的主要任务读源程序，产生用二元组表示的单词符号读源程序，产生用二元组表示的单词符号(单词种别，单词自身的值

3、单词种别，单词自身的值)。对某些单词来说，不仅仅需要它的值，还需要其它信息以方便代码生成。如标识符还需要记载它的层次，类别如标识符还需要记载它的层次，类别(整形、实整形、实形、布尔等形、布尔等)，这些属性都收集到一个符号表中。，这些属性都收集到一个符号表中。可以将此法分析输出的单词二元表示设计成可以将此法分析输出的单词二元表示设计成(标标识符识符,指向该标示符所在符号表中位置指针指向该标示符所在符号表中位置指针)。6界符和运算符界符和运算符:关键字可分成一类关键字可分成一类，也可以一个关键字，也可以一个关键字分成一类。分成一类。常数可统归一类常数可统归一类，也可按类型（整型、，也可按类型（整型

4、、实型、布尔型等），每个类型的常数实型、布尔型等），每个类型的常数划分成一类。划分成一类。所有的标识符分为一类。所有的标识符分为一类。词类编码原则词类编码原则:一字一码。一字一码。一类型一码。一类型一码。一类一码。一类一码。一字一码。一字一码。词法分析器的输出：词法分析器的输出：(词类编码，单词自身的属性值词类编码，单词自身的属性值）7 表表1 1 单词词类编码单词词类编码8对于关键字、界符、运算符来说，它们的词对于关键字、界符、运算符来说，它们的词类编码就可以表示其完整的信息，故对于这类编码就可以表示其完整的信息，故对于这类单词，其类单词，其单词自身的属性单词自身的属性值通常为空值通常为空对

5、于标识符，词类编码所反映的信息不够充对于标识符，词类编码所反映的信息不够充分，标识符的具体特性还要通过分，标识符的具体特性还要通过单词自身的单词自身的属性属性进行互相区分。标识符的单词自身的属进行互相区分。标识符的单词自身的属性常用其性常用其在符号表中的入口指针来表示在符号表中的入口指针来表示对于常数，对于常数，其其单词自身的属性单词自身的属性常用其在常常用其在常数表中的入口指针来表示数表中的入口指针来表示4.1.3词法分析工作分离的考虑词法分析工作分离的考虑 简化设计简化设计改进编译效率改进编译效率增加编译系统的可移植性增加编译系统的可移植性 10词法分析的设计形式词法分析的设计形式 (1

6、1)设计成一个独立程序，完成词法设计成一个独立程序，完成词法分析的任务，结果以文件的形式组织，分析的任务，结果以文件的形式组织，做为语法分析的输入做为语法分析的输入源程序源程序词法词法分析分析符号表符号表TOKENTOKEN字字错误信息错误信息11词法词法分析分析语法分析语法分析语义分析和语义分析和中间代码生成中间代码生成源源程程序序中中间间代代码码 符符 号号 表表 管管 理理 错错 误误 的的 诊诊 查查 处处 理理(2 2)作为语法分析和语义分析的子程序作为语法分析和语义分析的子程序用正规文法或者正则表达式描述单词符号的语法构成用正规文法或者正则表达式描述单词符号的语法构成 4.2.1

7、正规文法正规文法正规正规(3型型)文法文法G=(VN,VT,P,S),其中其中P中的产生式的形式中的产生式的形式为为A B或者或者A，其中，其中A和和B是非终结符号，是非终结符号，VT*。高级语言中几类单词的高级语言中几类单词的3型文法描述：型文法描述：标识符、无符号整数、运算符、标点符号、关键词、无符号标识符、无符号整数、运算符、标点符号、关键词、无符号实数等。教科书实数等。教科书p52。4.2 单词的描述工具单词的描述工具124.2.2 正规式正规式 正规式也称正则表达式,是描述单词的构成语法的有效工具，是定义正规集的数学工具。正规表达式（regular expression）是说明单词的

8、模式(pattern)的一种重要的表示法（记号），我们用以描述单词符号。程序设计语言的单词都能用正规式程序设计语言的单词都能用正规式 来定义来定义.正规式的递归定义正规式的递归定义4设字母表为，辅助字母表=,|,.,*,(,)。4(1)和都是上的正规式，表示的正规集分别为和；4(2)任何a,a是上的一个正规式，表示的正规集分别为a；4(3)假设e1和e2都是上的正规式，表示的正规集分别为L(e1)和L(e2)，则(e1),e1|e2,e1.e2,e1*都是上的正规式,它们表示的正规集分别为L(e1)，L(e1)L(e2),L(e1)L(e2),(L(e1)*；4(4)仅由有限次使用上述三步骤定

9、义的表达式才是上的正规式，仅有这些正规式表示的子集才是上的正规集。4*.|三个符号的优先级一次降低，都是左结合的4正规式等价：如果它们所表示的正规集相同4正规式服从的代数规律：或交换律或的可结合律连接的可结合律分配律或的抽取律存在连接的恒等元素教科书p53例1.=a，b，上的正规式和相应的正规集 a ab ab (ab)(ab)a (ab)(ab)(aabb)(ab)aa,babaa,ab,ba,bb,a,aa,任意个a的串 ,a,b,aa,ab,bb 所有由 a和b组成的串 上所有含有两个相继的a或两个相继的b组成的串 例例2.令令=l，d，则则 上的正规式上的正规式 r=l(l d)定义的

10、正规集为定义的正规集为:l,ll,ld,ldd,其中其中l代表字母代表字母,d代表数字代表数字,正规正规式式 即是即是 字母字母(字母字母|数字数字),它表示的正规集中的每个元它表示的正规集中的每个元素的模式是素的模式是“字母打头的字母数字串字母打头的字母数字串”,就是程序设计就是程序设计语言允许的标识符词法规则语言允许的标识符词法规则.例例3.=d，.，e，+，-,则则 上的正规式上的正规式 d(.dd )(e(+-)dd )表示的表示的是无符号数的集合。其中是无符号数的集合。其中d为为09的数字。的数字。4.2.3正规文法和正规式的等价性正规文法和正规式的等价性4一个正规语言可以由正规文法

11、定义，也可以由正规式定义，对于一个任一个正规式，存在一个生成同一个语言的正规文法；反之亦然。两者可以互相转换。4(1)正规式转换成正规文法p544(2)正规文法转换成正规式p54(1)正规式转换成正规文法将上的一个正规式r转换成文法G=(VN,VT,S,P)令令VT=，然后确定，然后确定P和和VN。选定一个非终结符选定一个非终结符S定为识别符号，生成规则定为识别符号，生成规则Sr；对于对于xy是正则式，定义一个规则是正则式，定义一个规则Axy,然后改写然后改写成：成：AxB,By，A,B VN对于对于x*y正则式，定义一个规则正则式，定义一个规则Ax*y,然后改写然后改写成：成：,AxB|y,

12、BxB|y，A,B VN对于对于x|y正则式，定义一个规则正则式，定义一个规则Ax|y,A,B VN例子例子:r=a(a|d)*对应的正规文法对应的正规文法SaA AaB|dB|BaB|dB|(2)正规文法转换成正规式正规文法转换成正规式将上的一个文法G=(VN,VT,S,P)转换成正规式r令令VT=S=r；对于对于AxB,By规则规则，定义一个正则式，定义一个正则式A=xy,对于对于AxA|y规则，定义规则，定义A=x*y正则式正则式对于规则对于规则Ax|y,定义定义A=x|y正则式正则式例子例子:对于文法对于文法GSSaA|a AaA|dA|a|d对应的的正则式为正则式为r=a(a|d)*

13、4.3有穷自动机有穷自动机 有穷自动机作为一种单词识别器，能准确地识别正规集，即识别正规式所表示的集合.应用有穷自动机这个理论，为词法分析程序的自动构造寻找有效的方法和工具。有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有 穷自动机(Nondeterministic Finite Automata)。关于有穷自动机有穷自动机我们将讨论如下题目确定的有穷自动机DFA不确定的有穷自动机NFANFA转换为DFADFA的最小化4.3.1确定的有穷自动机确定的有穷自动机DFADFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，

14、f，S，Z）其中1.K是一个有穷状态的集，它的每个元素称为一个状态；2.是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号表；DFA定义:M=（K，f，S，Z）3.f是转换函数，是在KK上的映射，即，如 f（ki，a）=kj，（kiK，kjK）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；4.SK是唯一的一个初态；5.Z K是一个终态集，终态也称可接受状态或结束状态。一个DFA 的例子：DFA M=（S，U，V，Q，a，b，f，S，Q）其中f定义为：f（S，a）=U f（V，a）=Uf（S，b）=Vf（V，b）=Qf（U，a）

15、=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q DFA 的状态图表示bSUVQaaaba，bb若存在一条从初态结点到某一终态结点的道路，且这条路若存在一条从初态结点到某一终态结点的道路，且这条路径上所有弧的标记符号链接成的符号串等于径上所有弧的标记符号链接成的符号串等于t t被被DFADFA 接受接受,则称则称t t。若初态结点又是终态结点，则空字被。若初态结点又是终态结点，则空字被DFADFA 接受接受DFA 的矩阵表示的矩阵表示字符字符状态状态0001*上的符号串上的符号串t t被被DFADFA M M接受接受例例：证明证明t=baab被下图的被下图的DFA所接受所接受。f（S，ba

16、ab）=f（f（S，b），），aab）=f（V，aab）=f（f（V，a），），ab）=f（U，ab）=f（f（U，a），），b）=f（Q，b）=QQ属于终态。属于终态。得证。得证。bSUVQabba,baaDFA M所能接受的符号串的全体记为L(M).结论：上一个符号串集V是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M)。DFA的确定性表现在转换函数f:K K是单值函数DFA的行为很容易用程序来模拟.DFA M=（K，f，S，Z）的行为的模拟程序K:=S；c:=getchar;while ceof do K:=f(K,c);c:=getchar;if K is in Z th

17、en return(yes)else return(no)4.3.2 不确定有穷自动机不确定有穷自动机NFA定义NFA M=K，f，S，Z，其中K为状态的有穷非空集，为有穷输入字母表，f为K*到K的子集（2 K）的一种映射，SK是初始状态集，Z K为终止状态集.NFA不确定性表现在转换函数f:K*2 K是多值函数.例子 NFA M=（S，P，Z，0，1，f，S，P，Z）其中 f（S，0）=Pf（S，1）=S，Z f（P，1）=Zf（Z，0）=Pf（Z，1）=P状态图表示SPZ00,1111矩阵表示矩阵表示简化为具有转移的不确定的有穷自动机 在NFA中f为K*到K的子集（2 K）的一种映射 12

18、3abc有如下定理:对任何一个具有转移的不确定的有穷自动机NFA N，一定存在一个不具有转移的不确定的有穷自动机NFA，使得L(M)=L(N)。与上例等价的一个NFA.2acbb31acacbb123acb对对NFA M=K，f，S，Z 有如下定义有如下定义*上的符号串t在NFA M上运行.一个输入符号串t，（我们将它表示成Tt1的形式，其中T，t1*）在NFA M上运行运行的定义为：f（Q，Tt1）=f（f（Q，T），t1）其中QK.*上的符号串t被NFA M接受若t*，f(S0，t)=P，其中S0 S，P Z，则称t为NFA M所接受接受（识别识别）*上的符号串t被NFA M接受理解:对于

19、对于 中的任何一个串中的任何一个串t，若存在一条若存在一条从某从某一初态结到某一终态结的道路一初态结到某一终态结的道路，且，且这条道路上所有弧的标记字依序连接成这条道路上所有弧的标记字依序连接成的串的串(不理采那些标记为不理采那些标记为的弧的弧)等于等于t，则则称称t可为可为NFA M所识别所识别(读出或接受读出或接受)。若若M的某些结既是初态结又是终态结，的某些结既是初态结又是终态结，或者存在一条从某个初态结到某个终态或者存在一条从某个初态结到某个终态结的道路结的道路,其上所有弧的标记均为其上所有弧的标记均为，那，那么空字可为么空字可为M所接受。所接受。0001111010001110000

20、0010001100NFA M所能接受的符号串的全体记为 L(M)结论：上一个符号串集V是正规的，当且仅当存在一个上的不确定的有穷自动机M，使得V=L(M)。(0|1)*(000|111)(0|1)*4.3.3 NFA转换为等价的转换为等价的DFA DFA是NFA的特例.对每个NFA N一定存在一个DFA，使得 L(M)=L(N)。将NFA转换成接受同样语言的DFA.这种算法称为子集法子集法.与某一与某一NFA等价的等价的DFA不唯一。不唯一。定义对状态集合定义对状态集合I的几个有关运算：的几个有关运算：状态集合状态集合I的-闭包，表示为表示为-closure(I)，定定义为一状态集，是状态集

21、义为一状态集，是状态集I中的任何状态中的任何状态S经任经任意条意条弧而能到达的状态的集合。弧而能到达的状态的集合。状态集合状态集合I的任何状态的任何状态S都属于都属于-closure(I)。即即 I-closure(I)状态集合状态集合I的a弧转换，表示为表示为move(I,a)定义定义为状态集合为状态集合J，其中其中J是所有那些可是所有那些可从从I中的某一中的某一状态经过一条状态经过一条a弧弧(a前可以有若干前可以有若干)而到达的状而到达的状态的集合态的集合。例1:I=1,-closure(I)=1,2；I=5,-closure(I)=5,6,2；move(1,2,a)=5,3,4-clos

22、ure(5,3,4)=2,3,4,5,6,7,8；一个NFA如下：12534687aaa NFA确定化算法确定化算法-子集法子集法:设NFA N=(K,f,K0,Kt)，按如下办法构造一个DFA M=(S,d,S0,St)，使得L(M)=L(N)：(1)M的状态集S由K K的一些子集的一些子集组成。用S1 S2.Sj表示S的元素，其中S1,S2,.Sj是K的状态。(2)M和N的输入字母表是相同的，即是；(3)转换函数是这样定义的：d(S1 S2,.Sj,a)=R1R2.Rt 其中 R1,R2,.,Rt=-closure(move(S1,S2,.Sj,a)(4)S0=-closure(K0)为M

23、的开始状态；(5)St=Si Sk.Se，其中Si Sk.SeS且Si,Sk,.SeKt构造构造子集子集的算法：的算法：假定所构造的子集族为C，即C=(T1,T2,.TI),其中T1,T2,.TI为状态K的子集。(1)开始，令-closure(K0)为C中唯一成员，并且它是未被标记的。2 while（C中存在尚未被标记的子集T）do 标记T；for 每个输入字母每个输入字母a do U:=-closure(move(T,a)；if U不在C中 then 将U作为未标记的子集加在C中 例例2：NFA的确定化的确定化 NFA4f35621iaaaabbbb4f35621iaaaabbbbNFA(K

24、,f,K0,Kt)-closure(move(T,a)T-closure(move(T,b)K0=iS=T0=-closure(K0)A=T1=Ia,B=T2=IbF=T6 等价的DFAaCDBAEFSbaaaaabbbbbabF5.3.4 确定有穷自动机的化简确定有穷自动机的化简 有穷自动机的化简是说它没有有穷自动机的化简是说它没有多余状态，多余状态，并且并且它的状态中没有它的状态中没有两个是互相等价两个是互相等价的。的。通过消除多余状态和合并等价状态而转换成一通过消除多余状态和合并等价状态而转换成一个个最小的与之等价的有穷自动机最小的与之等价的有穷自动机。所谓有穷自动机的多余状态，是指这样

25、的状态：所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能从自动机的开始状态出发，任何输入串也不能到达的那个状态到达的那个状态；或者从这个状态没有通路到或者从这个状态没有通路到达终态。达终态。DFA的最小化就是寻求最小状态的最小化就是寻求最小状态DFA 最小状态最小状态DFA的含义的含义:没有多余状态没有多余状态(死状态死状态)没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别）两个状态两个状态S和和T等价的条件：等价的条件：兼容性兼容性同是终态或同是非终态同是终态或同是非终态传播性传播性从从S出发对于所有读入符号出发对于所有读入符号a a和从和

26、从T出发出发读入读入a到达的状态等价。到达的状态等价。C和和F读入读入a都到达都到达C,读入读入b都到达都到达E.C和和F等价，等价，D和和E读入读入a都到达都到达F,读入读入b都到达都到达.D和和E等价，等价，C和和D同是终态同是终态,读入读入a到达到达C和和F,C和和F同是终态同是终态,读入读入b到达到达E和和D,所以所以C和和D等价。等价。aCDBAEFSbaaaaabbbbbabF最小状态最小状态DFA 对于一个DFA M=（K,f,k0,kt)，存在一个最小状态DFA M=（K,f,K0,Kt)，使L(M)=L(M).结论结论:接受接受L的最小状态有穷自动机不计同构是唯一的最小状态有

27、穷自动机不计同构是唯一的。的。DFA的最小化算法的最小化算法-分割法分割法 把一个把一个DFA的状态分成的状态分成一些不相交的子一些不相交的子集集，使得任何不同的两子集的状态都是，使得任何不同的两子集的状态都是可区别的，而同一子集中的任何两个状可区别的，而同一子集中的任何两个状态都是等价的态都是等价的.DFA的最小化算法的最小化算法 求求DFA M=DFA M=（K,f,kK,f,k0,0,k,kt t)的最小的最小DFA MDFA M (1)(1)构造状态的一初始划分构造状态的一初始划分：终态终态k kt t 和非终态和非终态K-K-k kt t两组两组(group)group)(2)(2)

28、对对施施用过程用过程PP PP 构造新划分构造新划分new new (3)3)如如new new =,=,则令则令 finalfinal=并继续步骤并继续步骤 4 4，否则否则:=newnew重复重复2.2.(4 4)为为finalfinal中的每一组选一代表，这些代表构中的每一组选一代表，这些代表构成成MM的状态。若的状态。若k k是一代表且是一代表且f(k,a)=t,f(k,a)=t,令令r r是是t t组的组的代表，则代表，则MM中有一转换中有一转换f f(k,a)=r(k,a)=r MM的开始状态是含有的开始状态是含有S0S0的那组的代表的那组的代表 MM的终态是含有的终态是含有F F

29、的那组的代表的那组的代表 (5 5)去掉去掉MM中的死状态中的死状态.过程过程PPPP:Construction of newFor each group G of do begin 1.Partiton G into subgroups such that two states s and t of G are in the same subgroups if and only if for all input symbols a,states s and t have transitions on a to states in the same group of;/*at worst,a

30、state will be in a subgroup by itself*/2.replace G in new by the set of all subgroups formed end DFA的最小化例10:S,A,B C,D,E,F1:S,A,B C,D,E,F 2:CDBAEFSbaaaaaabbbbbbaA S,BbB SDBASaaabbbbaa对所有的输入符号a,b，集合C,D,E,F 的输出都是等价的。选D作为C,D,E,F的代表。例例4.9 p61图图4.84(1)初始化分P=(1,2,3,4,5,6,7)4(2)P1=(1,23,45,6,7)4(3)P1=(1,23,

31、45,6,7)4(3)P1=(1,23,45,6,7)=A,B,C,D,E4236571aaaaabbbabbabb6CB6DAaaabbbabbaE4.4正规式和有穷自动机的等价性正规式和有穷自动机的等价性 词法分析程序的自动构造基于有穷自动机和正有穷自动机和正规表达式的等价性规表达式的等价性。(1)对于上的一个NFA M，可以构造一个上的正规式R,使得L(R)=L(M)。(2)对于上的一个正规式R，可以构造一个上的NFA M，使的L(M)=L(R)。从上的一个正规式R构造上的一个NFA M，使得L(M)=L(R)的方法。“语法制导”的方法，即按正规式的语法结构指引构造过程，构造规则具体描述

32、如下：教科书p62-63.(1)R=,构造任一具有空终态集的NFA M (2)R=，构造的NFA M=(k0,f,k0.k0):f（k0,a)对于 所有a都没定义。(3)R=a,构造的NFA M=(k0,k1,f,k0.k1):f(k0,a)=k1 (4)R=R1|R2,将步骤（1）（2）（3）分别应用到R1,R2 产生M1=(K1,f1,k1,F1),M2=(K2,f2,k2,F2),其中K1,K2不相交.构造的NFA M=(K1K2k,f,k,F):k是新增加的状态符号，f包含f1和f2,且f(k,a)=f1(k1,a)f2(k2,a).若k1F1且k2F2则 F=F1 F2，否则F=F1

33、 F2 k(5)R=R1R2 将步骤（1）（2）（3）分别应用到R1,R2 产生M1=(K1,f1,k1,F1),M2=(K2,f2,k2,F2),其中K1,K2不相交.构造的NFA M=(K1K2,f,k1,F2):f包含f1和f2,且f(k,a)=f1(k,a),当 kF1时;f(k,a)=f2(k,a),当 k K2时;f(k1,)=k2,(6)R=R1*将步骤（1）（2）（3）分别应用到R1,产生M1=(K1,f1,k1,F1),构造的NFA M=(K1 k0,F F0,f,k0,F0)其中 k0,F F0 是新增加的两个状态,f(k,a)=f1(k,a),当 kF1时;f(k0,)=

34、f(F1,)=k1,F F0,对于正规式R=,构造的NFA FS对于正规式R=,构造的NFA F对于正规式R=a ,构造的NFA FSa对于正规式r,r=R1|R2构造的NFA对于正规式r,r=R1 R2构造的NFA对于正规式r,r=R1*构造的NFA正规表达式正规表达式 1*0(0|1)*举例举例:从从正规表达式正规表达式构造等价的构造等价的 -NFA0|1 1*从从正规表达式正规表达式构造等价的构造等价的 -NFA(0|1)*1*0(0|1)*R=(a|ab)*b b*应用 正规式用于说明(描述)单词的结构十分简洁方便。而把一个正规式编译(或称转换)为一个NFA进而转换为相应的DFA，这个

35、NFA或DFA正是识别该正规式所表示的语言的句子的识别器。基于这种方法中的构造词法分析程序.应用 词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等，这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作 又如LEX，说明词法分析程序的语言，可以看成是一个模式动作语言。词法分析程序的自动构造工具也广泛应用于许多方面，如用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线路设计和文本编辑的自动生成等。4.5 正规文法和有穷自动机的等价性正规文法和有穷自动机的等价性4正规文法与正则表达式是等价的4从正规文法G直接构造有穷自动机NFA M，满足L(G)=L(M).(1)M

36、的字母表与G的终结符相同；(2)对G中的每个非终结符生成M的一个状态G的开始符号S是M的开始状态S；(3)增加一个新状态作为的终态；(4)对中形如AtB规则，构造的(A,t)=B函数;(5)对中形如At规则，构造的(A,t)=Z 函数教科书p65词法分析器的手工构造词法分析器的手工构造p19p19图图2.52.5，pl/0pl/0语言源程序见语言源程序见p434p4344为了构造词法分析器，要研究构词法，每种词类的结构模式以及识别它的数学模型有穷自动机。它的模拟程序可以作为词法分析器的控制程序。4确定的有限自动机（DFA）4构造识别单词的DFA4由DFA编写词法分析程序7879在识别标识符的过

37、程中，要拼写出来，并和在识别标识符的过程中，要拼写出来，并和保留字区别开来；识别出的标识符要填入符保留字区别开来；识别出的标识符要填入符号表中号表中编写词法分析程序编写词法分析程序根据根据DFADFA的状态转换图（的状态转换图（识别单词识别单词）构造）构造词词法分析程序，每个法分析程序，每个状态状态对应对应一段程序，完一段程序，完成到达此状态的工作；成到达此状态的工作；在识别常数的过程中，要把它转换成机器表在识别常数的过程中，要把它转换成机器表示以作为属性值，记录到常数表中。示以作为属性值，记录到常数表中。词法分析程序的控词法分析程序的控制程序模拟制程序模拟状态转换图的状态转换。状态转换图的状

38、态转换。804.64.6词法分析程序的自动构造工具词法分析程序的自动构造工具LEXLEX简介简介见见lex-yacclex-yacc使用说明使用说明1-141-14页，页，详细见详细见pdfpdf 单词的结构用正规式描述 正规式 NFA DFA min DFALEXLEX编译器编译器LEXLEX源程序源程序lex.1lex.1Lex.yy.c用用LEXLEX建立词法分析程序的过程建立词法分析程序的过程81C编译器编译器Lex.yy.ca.outa.out输入流输入流单词序列单词序列82声明声明%翻译规则翻译规则%辅助过程辅助过程lexlex源程序源程序 lexlex源程序由三部分组成源程序由三

39、部分组成83 声明包括变量，符号常量和正规定义式。声明包括变量，符号常量和正规定义式。翻译规则的形式为：翻译规则的形式为：p p1 1 动作动作1 1 p p2 2 动作动作2 2 p p n n 动作动作n n 84 每个每个p pi i是正规定义式的名子，每个是正规定义式的名子，每个 动作动作i i 是正规定义式是正规定义式p pi i识别某类单词识别某类单词时，词法分析器应执行动作的程序段。时，词法分析器应执行动作的程序段。用用C C书写。书写。标识符标识符 字母字母(字母字母|数字数字)*)*%标识符标识符 入口地址入口地址=LOOKUP();=LOOKUP();%LOOKUP()LOOKUP()本章小结本章小结 词法分析程序是编译第一阶段的工作，它读入字符流的源程序，按照词法规则识别单词，交由语法分析程序接下去。本章讲述了词法分析程序设计原则，并介绍了分别作为正规集描述和识别机制的正规式和有穷动机。在此基础上给出了词法分析程序自动构造工具如LEX的原理。作业P72Ex1,3,4(b),5,7,9,10