第四章词法分析

null第4章第4章词法分析本章目的本章目的本章将讨论词法分析程序的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。 描述程序设计语言的词法的机制是3型文法和正则 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达式，识别机制是有穷状态自动机。4.1 词法分析程序的设计4.1 词法分析程序的设计词法分析(lexical analysis) 逐个读入源程序字符并按照构词规则切分成一系列单词。 单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。 词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍。4.1.1 词法分析程序与 语法分析程序的接口方式 4.1.1 词法分析程序与 语法分析程序的接口方式 主要任务：读源程序，产生单词符号 其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序， 宏展开，……帮助理解术语帮助理解术语常常遇到的术语 token 单词,词标，符号 lexeme 词素，词位 pattern 模式，式样 In general，there is a set of strings in the input for which the same token is produced as output. This set of strings is described by a rule called a pattern associated with the token.帮助理解术语帮助理解术语The pattern is said to match each string in the set. A lexeme is a sequence of characters in the source program that is matched by the pattern for a token. e.g. Const pi=3.14159；中的pi是token “identifier”的lexeme，其pattern为letter followed by letters and/or digit.4.1.2 词法分析程序的输出4.1.2 词法分析程序的输出单词(Token)符号一般可分为下列五种： 基本字(关键字) begin end if while var 标识符—常量名、变量名、过程名 常数(量)—数值常量、字符串、逻辑值 运算符—+、-、*、/、<、= 界符— ，；( )词法分析程序的输出词法分析程序的输出输出表示采用单词的二元式形式： (单词种别，单词自身的值) 语句：Const i=25,yes=1 (Id,指向i的符号表的入口指针) (Id,指向yes的符号表的入口指针) 词法分析程序的输出词法分析程序的输出单词的种别用整数编码表示： 编码 单词 1 标识符 2 常数 3 保留字 4 运算符 5 界符 词法分析程序的输出词法分析程序的输出 程序段：if i=5 then x:=y; if (3, ‘if’) i (1,指向i的符号表入口) = (4,‘=’ ) 5 (2,‘5’) then (3, ‘then’) x (1,指向x的符号表入口) := (4, ‘:=’ ) y (1,指向y的符号表入口) ; (5,‘;’ ) 4.1.3 将词法分析工作分离的考虑4.1.3 将词法分析工作分离的考虑词法分析工作独立的原因： 1. 简化设计 2. 改进编译效率 3. 增加编译系统的可移植性 4.2 单词的描述工具4.2 单词的描述工具单词(Token)—基本语法符号 描述工具—程序设计语言的单词的语法都能用正规文法或3型文法来描述。 词法分析技术—基于描述工具建立的4.2.1 正规文法4.2.1 正规文法3型文法 G=(VN,VT,P,S) P中的每一条规则都有：AaB或Aa 其中A，B VN a  VT 正规文法描述的是VT 上的正规集正规文法的例—单词的描述正规文法的例—单词的描述<标识符>ll<字母数字> <字母数字>ldl<字母数字>d<字母数字> <无符号整数>dd<无符号整数> <运算符>+-* /=<<等号>><等号> <等号>= <界符> ， ；( )……正规文法的例—单词的描述正规文法的例—单词的描述例4.1 无符号数的单词描述 <无符号数>d<余留无符号数> .<十进小数>e<指数部分> <余留无符号数>d<余留无符号数> .<十进小数>e<指数部分> <十进小数>d<余留十进小数> <余留十进小数> e<指数部分> d<余留十进小数>正规文法的例—单词的描述正规文法的例—单词的描述<指数部分>d<余留整指数>s<整指数> <整指数>d<余留整指数> <余留整指数>d<余留整指数> 其中s表示 + 或 - 号 用实数 25.55e+5 和 2.1 进行分析4.2.2 正规式4.2.2 正规式正规式也称正则表达式，正规表达式 正规表达式(regular expression)是说明单词的pattern(词法)的一种重要的表示法(记号)，是定义正规集的 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 工具。正规式的定义正规式的定义正规式和它所表示的正规集的递归定义： 设字母表为 辅助字母表’={，，，，*，(，)}。 其中的“”读为“或”，亦可用“+” “ ”读为“连接”； “*”读为“闭包”，即任意有限次自重复连接。正规式的定义正规式的定义1. 和都是上的正规式，它们所表示的正规集分别为{  }和； 2. 任何 a ，a是上的一个正规式，它所表示的正规集为{a}；正规式的定义正规式的定义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、仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集。正规式与正规集正规式与正规集在不致混淆时，括号可省略。 规定算符的优先顺序为“(”、“)”、“*”、“ ”、“” 。 连接符“ ”一般可省略不写。 “*”、“ ”和“” 都是左结合的。reviewreviewRegular expressions on the alphabet å are defined by the following recursive rules: 1) ε and φ is a regular expression 2) Every symbol of å is a regular expression 3) if r1 and r2 are regular expressions, so are (r1) r1r2 r1|r2 r1* 4) Nothing else is a regular expression.reviewreview å = {0,1,2,3,4,5,6,7,8,9} (1|2|3|4|...8|9|0) (1|2|3|4|5|6|7|8|9|0)* (1|2|3...|8|9|0)+ is a regular expression正规式与正规集的例正规式与正规集的例例4.2 令={a，b}，上的正规式和相应的正规集的例子有： 正规式 正规集 a {a} ab {a,b} ab {ab} (ab)(ab) {aa,ab,ba,bb}正规式与正规集的例正规式与正规集的例 正规式 正规集 a* { ,a,a, ……任意个a的串} (ab)* { ,a,b,aa,ab ……所有由a 和b组成的串} (ab)*(aabb)(ab)* {*上所有含有两个相继的a 或两个相继的b组成的串}正规式与正规集的例正规式与正规集的例例 4.3 ={d，.，e，+，-}， 则上的正规式： d*(.dd*  )(e(+-  )dd*  ) 表示的是无符号数的集合。 其中d为0~9的数字，“.”为小数点。 上的正规式： e2=dd* 定义的正规集：无符号整数 可以简单的导出具体的数，例如： 正规式与正规集的例正规式与正规集的例例： ={l，d} 则上的正规式：r=l(l d)* 定义的正规集： {l,ll,ld,ldd,……} 例： ={字母，数字} ={l，d} 则上的正规式：e1=字母(字母数字)* e1=l(l d)* 定义的正规集：所有标识符的集合正规式的等价正规式的等价若两个正规式e1和e2所表示的正规集相同，则说e1和e2等价，写作e1=e2 例如：e1= ab 等价于 e2 = ba 又如：e1= b(ab)* 等价于 e2 =(ba)*b e1= (ab)* 等价于 e2 =(a*b*)*正规式服从的代数规律正规式服从的代数规律设r,s,t为正规式，有： 1. rs=sr “或”服从交换律 2. r(st)=(rs)t “或”的可结合律 3. (rs)t=r(st) “连接”的可结合律 4. r(st)=rsrt (st)r=srtr 分配律 5. r=r r=r 是“连接”的恒等元素零一律 6. rr=r r*=rrr… “或”的抽取律 4.2.3 正规文法到正规式4.2.3 正规文法到正规式一个正规语言可以由正规文法定义，也可以由正规式定义。 对任意一个文法，存在一个定义同一个语言的正规式。反之亦然。 两者之间的转换—结构的等价性。即： 对于上的一个正规式r ，存在一个文法G=(VN,VT,P,S) 且语言 L(G)=L(r) 反之亦然。正规式到正规文法正规式到正规文法1. 将上的一个正规式转换成文法： G={VN,VT,P,S} 所谓转换就是确定： 非终结符的非空有穷集VN 终结符的非空有穷集VT 产生式的非空有穷集P 开始符号S正规式到正规文法正规式到正规文法令VT =  确定产生式和VN的元素 对任何的正规式r，S  VN ，生成正规产生式：Sr，同时确定VN和P。 将S定为G的识别符号。 不断应用上述规则做变换，直到每个产生式右端最多只含一个终结符为止。正规式到正规文法正规式到正规文法若x和y都是正规式，对形如 Axy的正规产生式，重写为： AxB By 并且新非终结符BVN 对形如 Ax*y的正规产生式，可重写为： AxB Ay BxB By BVN 形如Ax  y的产生式，可重写为： Ax Ay正规式到正规文法正规式到正规文法例4.4 将 R=a(ad)* 转换成 G1=({S,A,B},{a,d},S,P} 其中 P：S aA B (ad)B A (ad)B A  B  令S为文法的开始符号， VT={a,d} VN={S,A,B} 正规式到正规文法正规式到正规文法R=a(ad)* Sa(ad)* SaA A(ad)* SaA AaB AdB A BaB BdB B SaA A(ad)B A B(ad)B B正规文法到正规式正规文法到正规式2. 将正规文法转换成正规式 转换结果为形如：开始符S终结符 的形式 转换规则：正规文法到正规式正规文法到正规式例4.5文法G[s]： SaA Sa AaA AdA Aa Ad S=aAa  A=(aAdA)(ad)  A=(ad)A(ad)  A=(ad)*(ad)应用规则 转换S=a(ad)*(ad)a =a((ad)*(ad)) =a((ad)*) =a(ad)*正规式r应用代数 规律4.3 有穷自动机4.3 有穷自动机有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合， 有穷自动机分为两类： 确定的有穷自动机DFA (Deterministic Finite Automata) 不确定的有穷自动机NFA (Nondeterministic Finite Automata)4.3.1 确定的有穷自动机(DFA)4.3.1 确定的有穷自动机(DFA)DFA定义： 一个确定的有穷自动机(DFA)M 是一个五元组：M =(K，Σ，f，S，Z ) 其中： 1. K 是一个有穷集，它的每个元素称为一个状态； 2. Σ是一个有穷字母表，它的每个元素称为一个输入符号，也称Σ为输入符号字母表；DFA定义DFA定义3. f是转换函数，是在K×Σ→K 上的映射，即，如 f (ki，a )=kj，(ki∈K，kj∈K ) 就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，把kj称作ki的一个后继状态； 4. S∈K 是唯一的一个初态； 5. Z K 是一个终态集，终态也称可接受状态或结束状态。reviewreviewDFA M=( K，Σ，f，S，Z ) 1) A finite set of states, one of which is designated the initial state or start state, and some of which are designated as final states. 2) An alphabet of possible input symbols. 3) A finite set of transitions that specifies for each state and for each symbol of the input alphabet, which state to go to next.DFA 例DFA 例例4.6 DFA M =({S,U,V,Q }，{a,b }，f，S，{Q }) 其中f定义为： f (S，a )=U f (V，a )=U f (S，b )=V f (V，b )=Q f (U，a )=Q f (Q，a )=Q f (U，b )=V f (Q，b )=Q DFA 的状态(转换)图表示 DFA 的状态(转换)图表示假定DFA M 含有m 个状态，n个输入字符，那么这个状态图含有m个结点，每个结点最多有n个弧射出。 整个图有唯一的初态结点和若干个终态结点。 若 f (ki，a )=kj 表示从状态结点ki 到kj 有标记为a的弧。 DFA 的状态(转换)图表示 DFA 的状态(转换)图表示前例的状态图DFA 的矩阵表示DFA 的矩阵表示前例的矩阵：行表示状态，列表示输入字符，矩阵元素表示对应行、列的状态。DFA的接受DFA的接受对于∑*中的任意字符串t，若存在一条从初态结点到终态结点的路径，且这条路径上的所有弧标记符连接成的字符串等于t，则称t可为DMA ∑所接受。 当初态和终态为同一结点时，可接受空串。DFA的接受DFA的接受若 t  ∑*，f (S，t )=P，其中S 为M 的开始状态，P Z，Z为终态集。 则称 t 为DFA M 所接受(识别)。 扩充转换函数f ： 设Q∈K，函数f (Q，ε)= Q，即如果输入串为空串，则仍停留在原来的状态上。 一个输入符号串t，将它表示成t1tx 的形式，其中t1∈∑，tx∈∑* 符号串t在DFA M上运行的定义为： f (Q， t1tx )=f (f (Q，t1 )，tx ) 其中Q∈KDFA M 上的运行DFA 例DFA 例例： 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 t=baab 被例4.6的DFA所接受。 f (S，baab)=f (f (S，b )，aab) =f (V，aab)=f (f (V，a)，ab) =f (U，ab)=f (f (U，a)，b)=f (Q，b)=Q Q 属于终态。 得证。 DFA的结论 DFA的结论DFA M 所能接受的符号串的全体记为L(M ) 结论： 上一个符号串集V∑*是正规的，当且仅当存在一个上的确定有穷自动机M，使得V=L(M )。DFA的确定性DFA的确定性DFA的确定性表现在转换函数f ：K×Σ→K是一个单值函数 对任何状态 k∈K，输入符号 a∈∑，f (k,a)唯一地确定下一个状态DFA模拟程序DFA模拟程序DFA M =(K，Σ，f，S，Z )的行为的模拟程序 K:=S; c:=getchar; while c<>eof do { K:=f(K,c); c:=getchar; }; if K is in Z then return (‘yes’) else return (‘no’)DFA DFA DFA å ={digit,not digit}DFA å ={digit,not digit}4.3.2 不确定的有穷自动机(NFA)4.3.2 不确定的有穷自动机(NFA)NFA定义：M ={K，，f，S，Z } 其中：K 为状态的有穷非空集  为有穷输入字母表 f 为K * 到K 的子集的映象 S  K 是初始状态集 Z  K 为终止状态集不确定的有穷自动机(NFA)不确定的有穷自动机(NFA)一个含有m 个状态和n个输入字符的NFA的状态转换图：有m个状态结点，其中至少包含一个初态结点和若干个终态结点，每个结点可用若干条弧连接其它状态结点，每条弧用* 上的一个串标记。NFA的例和状态图表示，例4.7 NFA的例和状态图表示，例4.7 NFA M=({0,1,2,3,4},{a,b},f,{0},{2,4}) f(0,a)={0,3} f(0,b)={0,1} f(1,b)={2} f(2,a)={2} f(2,b)={2} f(3,a)={4} f(4,a)={4} f(4,b)={4} 可识别含有aa或bb的串NFA的例和状态图表示NFA的例和状态图表示NFA M=({S,P,Z},{0,1}, f,{S,P},{Z}) 其中 f(S，0)={P} f(S，1)={S，Z} f(P，1)={Z} f(Z，0)={P} f(Z，1)={P}矩阵表示NFA矩阵表示NFA矩阵表示 被NFA M 接受被NFA M 接受∑*上的符号串t被NFA M 接受： 若存在从初态到终态结点的弧的标记串t，则 t ∑*，f (S0，t )=P， 其中S0 ∈S，P  Z，忽略标记为的弧， 则称t为NFA M 所接受(识别)在NFA上运行在NFA上运行类似DFA，对NFA M ={K，，f，S，Z }也有如下定义： ∑*上的符号串t在NFA M上运行： 一个输入符号串t，将它表示成t1 tx 的形式，其中t1∈∑，tx∈∑* 在NFA M上运行的定义为： f (Q,t1tx )=f (f (Q,t1 ),tx ) 其中Q ∈KNFA与DFANFA与DFADFA是NFA的特例。 对每个NFA M 一定存在一个DFA M’，使得L(M )=L(M’ )。则称：M 与M’ 是等价的 对每个NFA M 都存在着与之等价的DFA M’ 与某一NFA等价的DFA不唯一4.3.3 NFA→DFA的转换4.3.3 NFA→DFA的转换定理：设L为一个由NFA接受的集合，则存在一个接受L的DFA NFA的确定化—NFA→DFA的转换 转换算法—子集法： DFA的每一个状态对应NFA的一组状态 在NFA读入一个输入符号串后，T是标记某个符号的路径可以到达的一个子集，DFA的状态表示NFA状态的T。NFA的确定化NFA的确定化定义对状态集合I的几个有关运算： 1. 状态集合I 的- 闭包，表示为： -closure (I ) 定义为一状态集，是状态集I中的任何状态S，经任意条弧而能到达的状态的集合。 状态集合I 的任何状态S 都属于 -closure (I )。NFA的确定化NFA的确定化2. 状态集合I 的a 弧转换，表示为： move (I,a ) 定义为状态集合J，其中J是所有那些可从I的某一状态，经过一条a弧而到达的状态的全体。 定义 Ia = -closure (J )具有转移的NFA具有转移的NFA对任何一个具有转移的不确定的有穷自动机 NFA N，一定存在一个不具有转移的不确定的有穷自动机NFA M，使得L(M )=L(N )。NFA的确定化的例NFA的确定化的例I={0}, -closure(I)={0,1,2,4,7}； move({0,1,2,4,7},a)={3,8} -closure({3,8})={1,2,3,4,6,7,8}NFA的确定化的例NFA的确定化的例I={1}, -closure(I)={1,2}； I={5}, -closure(I)={5,6,2}； move({1,2},a)={5,3,4} -closure({5,3,4})={2,3,4,5,6,7,8}；NFA的确定化NFA的确定化假设NFA N =(K, , f, K0, Kt )，若I 是K 的一个子集，设 I =(S1,S2,S3,……,SJ)，a是 中的一个元素，则： move (I,a )=f (S1,a ) f (S2,a ) f (S3,a )…… 按如下办法构造一个 DFA M =(S, ,d,S0,St )， 使得L(M )=L(N )NFA的确定化NFA的确定化1. M 的状态集S由K的一些子集组成。 用[S1 S2... Sj]表示S的元素， 其中S1, S2,,... Sj是K 的状态。 并且约定，状态S1, S2,,... Sj是按某种规则排列的，即对于子集{S1, S2}={ S2, S1,}来说，S的状态就是[S1 S2]；NFA的确定化NFA的确定化2. M 和N 的输入字母表是相同的，即是 ； 3. 转换函数是这样定义的： d([S1 S2,... Sj],a)= [R1R2... Rt] 其中 {R1,R2,... , Rt} = -closure (move ({S1, S2,,... Sj},a)) NFA的确定化NFA的确定化4. S0 =-closure (K0 )为M 的开始状态； 5. St ={[Si Sk... Se]} 其中 [Si Sk... Se]S 且 {Si , Sk,,... Se}Kt NFA的确定化NFA的确定化构造NFA N 的状态K 的子集的算法： 假定所构造的子集族为C，即C= (T1, T2,,... TI)，其中T1, T2,,... Ti为状态K的子集。 1. 开始，令-closure (K0 )为C中唯一成员，并且它是未被标记的。NFA的确定化NFA的确定化2. While (C中存在尚未被标记的子集T) do { 标记T； for 每个输入字母a do { U:= -closure(move(T,a))； if U不在C中 then 将U作为未标记的子集加在C中 } }4.3.4 确定有穷自动机的化简4.3.4 确定有穷自动机的化简最小状态DFA 没有多余状态(死状态) 没有两个状态是互相等价(不可区别) 两个状态s和t可区别：不满足 兼容性——同是终态或同是非终态 传播性——从s出发读入某个a (a) 和从t出发读入某个a到达的状态等价。确定有穷自动机的化简确定有穷自动机的化简说一个有穷自动机是化简了的，即是说，它没有多余状态并且它的状态中没有两个是互相等价的。 一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。 所谓有穷自动机的多余状态，是指这样的状态：从自动机的开始状态出发，任何输入串也不能到达的那个状态；或者从这个状态没有通路到达终态。DFA的最小化DFA的最小化对于一个DFA M =(K,∑,f, k0,,kt )，存在一个最小状态DFA M’ =(K’,∑,f’, k0’,,kt’ )，使L(M’ )=L(M ) 算法的核心：把M的状态集K分成不相交的子集。 结论：接受L的最小状态有穷自动机不计同构是唯一的。DFA的最小化DFA的最小化DFA M=(K,∑,f, k0,, kt )最小状态DFA M’ 1. 构造状态的一初始划分：终态kt 和非终态K- kt 两组； 2. 对∏施用过程PP 构造新划分∏new； 将中的每一个组G 划分为子组，而G 中的两个状态ki 和kj 在同一子组中的充分必要条件是：对于所有输入符号a而言， ki 和kj转换后的状态都在∏new中的同一子组G 中。DFA的最小化DFA的最小化3. 如∏new=∏，则令∏final=∏并继续步骤4，否则∏=∏new重复2； 4. 为∏final中的每一组选一代表，这些代表构成M’ 的状态。 若k 是一代表且f (k,a )=t，令r 是t 组的代表，则M’ 中有一转换f’ (k,a )=r0， M’ 的开始状态是含有k0 的那组的代表， M’ 的终态是含有kt 的那组的代表； 5.去掉M’ 中的死状态。 ∏0:{S,A,B} {C,D,E,F} ∏1:{S,A,B} {C,D,E,F} ∏2:aaDFA的最小化的例4.4 正规式和有穷自动机的等价性4.4 正规式和有穷自动机的等价性有穷自动机和正规表达式的等价性： 1.对于∑上的一个NFA M，可以构造一个∑上的正规式R，使得L(R )=L(M )。 2.对于∑上的一个正规式R，可以构造一个∑上的NFA M，似的L(M )=L(R )。 “语法制导”的方法：按Σ上的一个正规式R的语法结构指引构造过程，构造Σ上的一个NFA M，使得L(M )=L(R )的方法。“语法制导”构造规则“语法制导”构造规则构造规则具体描述如下： (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 = (K1K2{k },∑,f,k,F ) k 是新增加的状态符号，“语法制导”构造规则“语法制导”构造规则F 包含f1 和f2， 且f (k,a )=f1 (k1,a )f2 (k2,a ) 若k1 F1 且k2 F2 则 F =F1  F2，否则F =F1  F2 {k } (5)R =R1.R2 (6)R =R1*用状态图说明用状态图说明对于正规式R = ，构造的NFA 对于正规式 ，所构造的NFA 对于正规式a，a ∑，所构造的NFA用状态图说明用状态图说明对于正规式R= s|t构造的NFA用状态图说明用状态图说明对于正规式R=st构造的NFA用状态图说明用状态图说明对于正规式R=s*构造的NFA构造NFA N的例构造NFA N的例例 R=(a|ab)* b b*4.5 正规文法和有穷自动机间的转换4.5 正规文法和有穷自动机间的转换从正规文法G直接构造一个有穷自动机 NFA M，使得L(m )=L(G )： 字母表与G的终结符相同 为G中的每个非终结符生成一个状态，G的开始符号S就是开始状态S 增加一个新状态，作为NFA的终态正规文法和有穷自动机间的转换正规文法和有穷自动机间的转换对G中的形如 AtB 的产生式，构造M的一个转换函数。其中t为终结符或，A和B为非终结符。f(A,t)=B 对G中的形如 At 的产生式，构造M的一个转换函数。f(A,t)=Z 正规文法和有穷自动机间的转换的例正规文法和有穷自动机间的转换的例例4.12 与文法G[S]等价的NFA M G[S]： SaA SbB S  AaB AbA BaS BbA B  4.6 词法分析程序自动构造工具4.6 词法分析程序自动构造工具正规式用于说明(描述)单词的结构十分简洁方便。 而把一个正规式编译(或称转换)为一个NFA进而转换为相应的DFA，这个NFA或DFA正是识别该正规式所表示的语言的句子的识别器。 基于这种方法来构造词法分析程序词法分析程序自动构造工具词法分析程序自动构造工具词法分析程序的设计技术可应用于其它领域，比如查询语言以及信息检索系统等。 这种应用领域的程序设计特点是，通过字符串模式的匹配来引发动作，回想LEX，说明词法分析程序的语言，可以看成是一个模式动作语言。词法分析程序自动构造工具词法分析程序自动构造工具词法分析程序的自动构造工具也广泛应用于许多方面，如用以生成一个程序，可识别印刷电路板中的缺陷，又如开关线路设计和文本编辑的自动生成等。 LEX 语言LEX 语言LEX程序由三部分组成：说明部分、转换规则和辅助过程，用%%做间隔符。 格式为： 说明部分 %% 转换规则 %% 辅助过程4.7 典型例题及解答4.7 典型例题及解答1.构造正规式 1(0︱1)*101 相应的DFA 解 首先构造相应的NFA，然后再将其确定化。 采用“语法制导法”，即依据正规式的语法来构造。首先， 将 1(0︱1)*101 分解成γ=γ1γ2γ3 其中 γ1=1， γ2=(0︱1)*典型例题及解答典型例题及解答γ3=101 γ=γ1γ2γ3=1(0︱1)*101相对应的NFA 典型例题及解答典型例题及解答正规式1(0︱1)*101相对应的DFA 状态转换表典型例题及解答典型例题及解答2.将图示的DFA最小化0典型例题及解答典型例题及解答划分终态集和非终态集： {0,1,2,3,5}，{4,6,7}。 再划分： {0,1}={2}{0,1,2,3,5} {3}=Φ {2,5}={4}{4,6,7} {4,7}={4}{4,6,7} {6}=Φ典型例题及解答典型例题及解答命名状态：A-{0,1}，B-{2,5}， C-{3}，D-{4,7}，E-{6} 最小化：