词法分析与有限状态自动机课件.ppt

1、2022-12-17华东师大计算机科学技术系1有限状态自动机有限状态自动机 3.1.1 基本概念基本概念 FA的非形式描述的非形式描述 有限状态自动机由有限状态自动机由3部分组成：部分组成：一根输入带：输入带可以理解成由一系列带一根输入带：输入带可以理解成由一系列带块组成，每个带块上只含有一个输入符号（终结块组成，每个带块上只含有一个输入符号（终结符号），其全体构成集合符号），其全体构成集合VT，特殊符号特殊符号“”表示表示输入符号串的结束，输入符号串的结束，VT。一个输入头：初始时，输入头指向第一个带一个输入头：初始时，输入头指向第一个带块（即指向输入带最左端的带块），输入头每次块（即指向输

2、入带最左端的带块），输入头每次将输入头下方带块上的输入符号读入，然后输入将输入头下方带块上的输入符号读入，然后输入头向右移动一个带块。头向右移动一个带块。2022-12-17华东师大计算机科学技术系2基本概念基本概念 一个有限状态控制器：有限状态控制器所能一个有限状态控制器：有限状态控制器所能处于的状态的全体组成状态集合处于的状态的全体组成状态集合Q，Q中有若中有若干特殊状态：一个初始状态干特殊状态：一个初始状态q0和若干最终状态和若干最终状态qf。开始时有限状态控制器处于初始状态，以。开始时有限状态控制器处于初始状态，以后有限状态控制器所处状态由状态转换函数后有限状态控制器所处状态由状态转换

3、函数 决定。决定。2022-12-17华东师大计算机科学技术系3基本概念基本概念 例例1 令令VT=0,1,2,3Q=S,A,B2030 _ S B A 1 2 3+0 0 S是初态是初态 用用-表表示示A是终态是终态用用+表表示示有向弧表示有向弧表示转换转换2022-12-17华东师大计算机科学技术系4FA的工作过程的工作过程初始时，初始时，FA处于初态，输入头指向第一个输入处于初态，输入头指向第一个输入符，随着带上符号的读入，符，随着带上符号的读入，FA从一个状态转向从一个状态转向另一个状态。若遇到如下情况，另一个状态。若遇到如下情况，FA结束工作：结束工作：1.输入头指向输入头指向、FA

4、处于终态。称输入串被处于终态。称输入串被FA接受。（如接受。（如2030 ）2.输入头指向输入头指向、FA不在终态。称输入串不不在终态。称输入串不被被FA接受。接受。（如（如203 ）3.FA无法转换。称输入串不被无法转换。称输入串不被FA接受。接受。（如（如1031 ）2022-12-17华东师大计算机科学技术系5FA的形式描述的形式描述 定义定义1：有限状态自动机：有限状态自动机M是一个五元组：是一个五元组：M(VT,Q,q0,Qf)，其中：，其中：VT：有限非空终结符集合：有限非空终结符集合 Q：有限非空状态集合有限非空状态集合 ：从从QVT到到Q的幂集的幂集2Q上的状态转换函数上的状态

5、转换函数 q0：初始状态，：初始状态，q0 Q Qf：最终状态集，：最终状态集，Qf Q|Qf|1 2022-12-17华东师大计算机科学技术系6FA的形式描述的形式描述1.对对q,q1 Qa VT (q,a)=q1的含义为：当前的含义为：当前状态为状态为q，若输入头所指符号为，若输入头所指符号为a，则转向下一状，则转向下一状态态q1，输入头右移。，输入头右移。2.2.是是QVT2Q上的一个单射上的一个单射一般地一般地(q,a)=q1,q2,qn qi Q i=1,2,n因此称因此称FA M为不为不确定的确定的FA，记为，记为NFA。3.若映射若映射 是是QVT Q，即对任何，即对任何q Q，

6、ai VT，(q,ai)至多只有一个元素至多只有一个元素q，称，称FA M是是确定性的确定性的FA，记为，记为DFA。2022-12-17华东师大计算机科学技术系7FA的形式描述的形式描述对对FA的拓展的拓展Q0 Q|Q0|1 即初态可以是一个集合即初态可以是一个集合：从从QVT*到到2Q上的单值映射，即输入上的单值映射，即输入符可以是一个串，包括符可以是一个串，包括 称称M为一个传递图或转换系统或为一个传递图或转换系统或NFA。例例1：M1(VT,Q,q0,F)VT=a,b,Q=q0,q1,q2F=q2:(q0,a)=q1 (q0,b)=q2 (q1,a)=q1 (q1,b)=q1 (q2,

7、a)=q2 (q2,b)=q1M1是一个是一个DFA。2022-12-17华东师大计算机科学技术系8FA的表示的表示3.1.2 状态转换图和状态转换表状态转换图和状态转换表1.1.状态转换图：状态转换图：q q Q 若若q，q Q，a VT，且，且q (q,a)，初态用初态用标记、终态用标记、终态用+标记标记 qqqa2022-12-17华东师大计算机科学技术系9状态转换图状态转换图 例例2：例：例1的的DFA M1可表示为：可表示为：q0q2q1abbaa,b2022-12-17华东师大计算机科学技术系10状态转换表状态转换表2.2.状态转换表（矩阵）状态转换表（矩阵）表的列对应输入符号及特

8、殊符号表的列对应输入符号及特殊符号，行，行和和M M的状态的状态q q相对应。相对应。状态转换表的状态转换表的q qi i行行a aj j列中填以列中填以 (q(qi i,a,aj j)中中的状态。的状态。表的第一行和表的第一行和M M的初始状态的初始状态q q0 0相对应；相对应；这一列和最终状态这一列和最终状态q qf f行的元素标以行的元素标以A A，以表，以表示该状态是最终状态。示该状态是最终状态。2022-12-17华东师大计算机科学技术系11状态转换表状态转换表 例例3：例：例1的的DFA M1可表示为：可表示为：Mab q0q1q2q1q1q1q2q2q1A2022-12-17华

9、东师大计算机科学技术系12示例示例 例例4：设计一个接受以：设计一个接受以a为头符号和尾符号，中为头符号和尾符号，中间可出现任意多个间可出现任意多个a,b的符号串的的符号串的FA M。解：解：令：令：VT=a,bQ=q0,q1,q2aq0q2q1aaa,baM是是NFA2022-12-17华东师大计算机科学技术系13FA识别的语言识别的语言1.格局格局FA M的一个格局是二元组（的一个格局是二元组（q,w )q Q，w w VT*2.动作动作对对q (q,a)则则FA M 的动作记为：的动作记为：(q,aw)(q,w)a VT w w VT*3.对对w VT*，q0是初态，称是初态，称w被被F

10、A M所接受，表示为：所接受，表示为：(q0,w)(qf,)qf F*2022-12-17华东师大计算机科学技术系14FA识别的语言识别的语言 定义定义2：设：设M是一个是一个FA，w w VT*若：若：(q0,w)(qf,)qf F q0是初态是初态称称w是是M的一个句子。的一个句子。M句子的全体称为句子的全体称为M的语言，记为：的语言，记为：L(M)=w|(q0,w)(qf,),w w VT*例例5：对例：对例4的的NFA M，输入串，输入串abba 有：有：(q0,abba)(q1,bba)(q1,ba)(q1,a )(q2,)qq2 F abbaabba L(M)L(M)=a|a(a|

11、b)*a*2022-12-17华东师大计算机科学技术系15FA的确定化的确定化 定义定义3：对：对FA M与与FA M，若，若L(M)=L(M)则称则称M与与M等价。等价。3.1.4 FA的确定化的确定化 定理定理3.1 对任一给定的对任一给定的NFA M存在一个存在一个DFA M使使L(M)=L(M)。分析：分析：由定理由定理3.1 L(DFA)L(NFA)由由FA的定义的定义 L(DFA)L(NFA)得到得到 L(DFA)L(NFA)2022-12-17华东师大计算机科学技术系16FA的确定化的确定化证明：证明：“构造性证明构造性证明”对给定的对给定的NFA M(VT,Q,q0,F)构造一

12、个构造一个DFA M(VT,Q,q0,F)1.令令VT VT2.Q 2Q 即即Q的元素是的元素是Q的子集，的子集，Q也是也是有限集，有限集，|Q|=2|Q|3.对对 a VT 若若(qi1,.qin,a)=qj1,qjm 令令(qi1,.qin,a)=qj1,qjm Q4.M的初态的初态q0=q0 Q5.F中的元素由中的元素由Q中那些至少含有中那些至少含有F中一个元素的中一个元素的状态组成，即状态组成，即qj1,qjm F 则则 qjk F 1 k n M M是是DFADFA2022-12-17华东师大计算机科学技术系17FA的确定化的确定化 再证：再证：L(M)=L(M)，即要证，即要证 x

13、 VT*(q0,x)qi1,qik,qim F (q0,x)qi1,qik,qim qik F证明：对证明：对x的长度的长度|x|作归纳法作归纳法1.当当|x|=0时，结论成立时，结论成立2.假定假定|x|n，结论成立，结论成立3.当当|x|=n,由由 的定义，结论成立的定义，结论成立*2022-12-17华东师大计算机科学技术系18FA的确定化的确定化 例例6：例：例4的的M 是是NFA 可用表的形式表示为：可用表的形式表示为：Mab q0q1,q2q1q1,q2 q1 q2q2 AMab q0 q1,q2q1,q2 q1,q2 q1 Aq1 q1,q2 q1 确定化确定化2022-12-1

14、7华东师大计算机科学技术系19FA的最小化的最小化 3.1.3 FA的最小化的最小化 一般地说，对给定的一个一般地说，对给定的一个FA M，可以找到任，可以找到任意多个不同的意多个不同的FA M，有，有L(M)=L(M)，因，因此得到最小的此得到最小的FA是有意义的。是有意义的。定义定义4：若：若FA的二个状态的二个状态q与与q，对任意一个，对任意一个长度为长度为k或小于或小于k的符号串的符号串w，q接受接受w当且仅当当且仅当q接受接受w，称，称q与与q是是k等价的，否则称等价的，否则称q与与q是是k可区分的。可区分的。q与与q等价的充要条件是对等价的充要条件是对 k 0，q与与q是是k等价的

15、。等价的。2022-12-17华东师大计算机科学技术系20FA的最小化的最小化 状态分离法状态分离法 基本思想：基本思想：对对DFA的状态集的状态集Q进行进行k等价类划分，即将等价类划分，即将Q划划分成分成Qk1,.Qkn的的n个子集，子集中的状态是个子集，子集中的状态是k等等价的。然后进行价的。然后进行k+1的等价类划分的等价类划分直至无法直至无法进一步划分为止。进一步划分为止。则得到的等价子集中各状态等价，可合并为一个则得到的等价子集中各状态等价，可合并为一个状态。状态。2022-12-17华东师大计算机科学技术系21状态分离法状态分离法具体做法：具体做法：1.0等价类划分：将等价类划分：

16、将Q划分成划分成F与与Q-F二个二个0等价类。等价类。2.若已经进行了若已经进行了k等价类划分，等价类划分，Q已经被划分成已经被划分成Q1，Qn（n 2)n个子集，进行个子集，进行k+1等价类划分。等价类划分。对对 Qi(i=1n)q,q Qi，若有，若有a VT，（q，a）Qj 和和（q，a）Ql，jl 或或 （q，a）存在）存在 而而（q，a）不存在或反之。）不存在或反之。则将则将Qi划分为二个子集划分为二个子集Qi1，Qi2，使使q Qi1，q Qi2。3.重复重复2直至无法进一步划分为止。直至无法进一步划分为止。2022-12-17华东师大计算机科学技术系22状态分离法状态分离法4.对

17、每一个子集对每一个子集Qi(i=1n)，任选一个代表，任选一个代表qi，并修改并修改，修改方法为：，修改方法为：转向转向Qi中任何一个状态改成转向中任何一个状态改成转向qi。若一个。若一个状态子集中某一状态是原来的开始状态，则状态子集中某一状态是原来的开始状态，则该状态子集的代表就是新的有限状态自动机该状态子集的代表就是新的有限状态自动机的开始状态。同理，若一个状态子集中的状的开始状态。同理，若一个状态子集中的状态均是最终状态，则该状态子集的代表就是态均是最终状态，则该状态子集的代表就是新的有限状态自动机的最终状态。新的有限状态自动机的最终状态。5.抹去可能存在的无用状态与不可及状态抹去可能存

18、在的无用状态与不可及状态。则则DFA M是最小的（或简化的）。是最小的（或简化的）。2022-12-17华东师大计算机科学技术系23状态分离法状态分离法 例例7：试将下图中所示的有限状态自动机：试将下图中所示的有限状态自动机M最最 小化。小化。A B C D E F G a b a b a a a a a b b b b b+2022-12-17华东师大计算机科学技术系24例例7续一续一解：最小化的过程为：解：最小化的过程为：1.初 始 时 的 划 分 由初 始 时 的 划 分 由 2 个 子 集 组 成，即：个 子 集 组 成，即：（A,B,C,D,E,F,G）2.集 合集 合 D,E,F,

19、G 不 需 要 进 一 步 划 分，不 需 要 进 一 步 划 分，考察子集考察子集A,B,C。由于。由于（B,a）=D D,E,F,G，而而（A,a）（C,a）B A,BC，因此因此Q可进一步划分为：（可进一步划分为：（A,C,B,D,E,F,G）。）。3.由于由于（A,b）C A,C，而而（C，b）E D,E,F,G。因此因此Q可进一步划分为：（可进一步划分为：（A,C,B,D,E,F,G）2022-12-17华东师大计算机科学技术系25例例7续二续二 这时不能再划分了，得到的最小化的有限状态这时不能再划分了，得到的最小化的有限状态自动机如下表所示：自动机如下表所示：Mab ABCCBDB

20、DCDDDF2022-12-17华东师大计算机科学技术系26习题习题P55 习题习题31.3.22.3.33.补充题补充题1.1.将如下所示的非确定有限状态自动机将如下所示的非确定有限状态自动机M M确定化和最小确定化和最小化化。M a b S A-A B,C A B A-C-F 2022-12-17华东师大计算机科学技术系272.2.试给出下述每个有限状态自动机所识别的语言试给出下述每个有限状态自动机所识别的语言 0+1 0 0 1 0 1 2 1 3 1 4 5 6 0,1 7 0,1 8 0,1 9 a a a a 1 2 a 3 4 5 a)b)2022-12-17华东师大计算机科学技

21、术系280 1+0 1 1 1 2 0 3 c)2022-12-17华东师大计算机科学技术系29正则表达式（正则表达式（REX)3.2 正则表达式（正则表达式（Regular Expression）、有限）、有限状态自动机、状态自动机、3型文法及其相互间的关系型文法及其相互间的关系 正则表达式又称正规式正则表达式又称正规式 有限状态自动机有限状态自动机(FA)是正则文法（是正则文法（3型文法）型文法）的数学模型，正则表达式（的数学模型，正则表达式（REX）所表示的值，）所表示的值，即为即为FA所能接收的语言的全体，因此这三者所能接收的语言的全体，因此这三者的关系可用下图表示：的关系可用下图表示

22、：FA3型文法型文法REX2022-12-17华东师大计算机科学技术系30正则表达式正则表达式 通常称有限状态自动机和三型文法所接受的语通常称有限状态自动机和三型文法所接受的语言为正则语言言为正则语言。REX在词法分析中有很重要的作用，它可以精在词法分析中有很重要的作用，它可以精确地表示单词符号的组成，定义单词符号集。确地表示单词符号的组成，定义单词符号集。3.2.1 3.2.1 正规式与正规集正规式与正规集 如程序设计语言中的标识符（如程序设计语言中的标识符（ID）可以用）可以用REX表示为：表示为：Let(let|Dig)*其中其中 Let是字母、是字母、Dig是数字是数字 2022-12

23、-17华东师大计算机科学技术系31正则表达式正则表达式 定义定义1：设：设 是字母表。是字母表。上的上的REX及其值及其值REX所所表示的符号串集合（正规集表示的符号串集合（正规集）递归定义如下：）递归定义如下：、是正则表达式，其值表示空集和是正则表达式，其值表示空集和；对对 中每一字母中每一字母ai ，ai是正则表达式，其值表是正则表达式，其值表 示集合示集合ai；若若p,q是是REX，值分别为，值分别为L(p)和和L(q)，则则p|q，pq和和p*也是也是 上的上的REX，其值分别是：其值分别是：L(p)L(q)，L(p)L(q)，L(p)*。有限次使用上述规则得到的仍是有限次使用上述规则

24、得到的仍是 上的上的REX。2022-12-17华东师大计算机科学技术系32正则表达式正则表达式规则：规则：1.1.优先级由高到低为：优先级由高到低为：*，,|,|。2.2.可用可用（，）改变优先级。改变优先级。3.3.记记R R*R R为为R R+值值L(RL(R+)=L(R)=L(R*)L(R)L(R)。性质性质1.1.交换律交换律R|S=S|RR|S=S|R2.2.结合律结合律R|(S|T)=(R|S)|T R(ST)=(RS)TR|(S|T)=(R|S)|T R(ST)=(RS)T3.3.分配律分配律R(S|T)=RS|RTR(S|T)=RS|RT(R|S)T=RT|ST(R|S)T=

25、RT|ST4.4.同一律同一律R=R=RR=R=R2022-12-17华东师大计算机科学技术系33正则表达式正则表达式 例例1试写出试写出 0，1上下述集合的上下述集合的REX：所有以所有以1开始和结束的符号串。开始和结束的符号串。恰含有恰含有3个个1的所有符号所组成的集合。的所有符号所组成的集合。集合集合01，1。所有以所有以111结束的符号串。结束的符号串。解答：解答：1(0|1)*1|1 0*10*10*10*01|1 (0|1)*1112022-12-17华东师大计算机科学技术系34正则表达式与有限状态自动机正则表达式与有限状态自动机3.2.2 REX 和和FA定理定理3.2 （Kle

26、ene)设设R是是 上的一个上的一个REX，则，则存在一个存在一个FA M，有，有L(M)=L(R)。反之亦然。反之亦然。证：证：1.对给定的对给定的REX到到FA从从REXREX构造构造FAFA可以分两步进行。可以分两步进行。从从REX R到传递图到传递图T XYR2022-12-17华东师大计算机科学技术系35Kleene定理定理反复应用下述替代规则，直至所有有向弧都以反复应用下述替代规则，直至所有有向弧都以 中中的符号或标记的符号或标记 为止。为止。若 j i i AB 若，则用 替代 A B j i i ，则用 A B i j i k i C*若，则用 替代 i C i A|B2022

27、-12-17华东师大计算机科学技术系36Kleene定理定理 消除应用消除应用所得到的传递图中的所得到的传递图中的弧，可以分为弧，可以分为两步：首先消除两步：首先消除环路，其次消除其他环路，其次消除其他弧。弧。a)环路的消除方法：环路的消除方法：i将将环路的诸项合并为一个顶点。环路的诸项合并为一个顶点。ii修改各个相关的有向弧。修改各个相关的有向弧。iii若若环路中某一状态是最终（或初始）状环路中某一状态是最终（或初始）状 态，态，则新顶点是最终（或初始）状态。则新顶点是最终（或初始）状态。b）其它）其它弧的消除有两种方法：弧的消除有两种方法：1）子集法：即计算）子集法：即计算-Closure

28、（T），其表示从状），其表示从状态集态集T中任何一状态沿中任何一状态沿弧可以到达的状态全体。弧可以到达的状态全体。2022-12-17华东师大计算机科学技术系37Kleene定理定理 其要点是：从初始状态其要点是：从初始状态q0的的X=-Closure（q0）开）开始，按如下方法构造状态集：始，按如下方法构造状态集：i令令SetX；ii若若Set中还有未考察过的状态子集中还有未考察过的状态子集Xi，则对于每，则对于每一输入符号一输入符号a VT，计算：，计算：T=-Closure（move（Xi,a），），Set=SetT（其中（其中move(Xi,a)=q|q(p,a),p Xi）。重复执）

29、。重复执行（行（ii），直至不存在这样的），直至不存在这样的Xi。这样得到的。这样得到的Set即为消除即为消除弧后的弧后的DFA。DFA的初始状态就是的初始状态就是-Closure（q0），最终状态由那些至少含有一个最），最终状态由那些至少含有一个最终状态的状态子集组成。终状态的状态子集组成。2022-12-17华东师大计算机科学技术系38Kleene定理定理2）逐步消除法：）逐步消除法：其要点是找到类似于下图所示，但从其要点是找到类似于下图所示，但从B再无再无弧引弧引出的出的弧。弧。删除状态删除状态A A到状态到状态B B的的弧，对每一条从状态弧，对每一条从状态B B到状到状态态C C标记为

30、标记为a ai i的弧，增加的弧，增加1 1条从状态条从状态A A到状态到状态C C标记标记为为a ai i的弧。若的弧。若B B是最终状态，则让是最终状态，则让A A为最终状态。为最终状态。重复上述过程直至消除全部的重复上述过程直至消除全部的弧，这样得到的弧，这样得到的一般是一般是NFANFA。A B 2022-12-17华东师大计算机科学技术系39Kleene定理定理 例例2：试给出与下图所示的传递图等价的、确定的、试给出与下图所示的传递图等价的、确定的、最小的有限状态自动机。最小的有限状态自动机。D F E G,1 1 0 1 1 +2022-12-17华东师大计算机科学技术系40例例2

31、（续一）（续一）解法一解法一 子集法：子集法：M的初始状态为的初始状态为D，而，而Closure(D)=D，E，G令令A=D，E，G，B=D，E，F，G VT=0，1 Closure(move(A，1)=D，E，F，GClosure(move(A，0)=FClosure(move(F，1)=GClosure(move(G，1)=D，E，GClosure(move(B，1)=D，E，F，GClosure(move(B，0)=F2022-12-17华东师大计算机科学技术系41例例2（续二）（续二）所以，所以，DFA M如下表所示：如下表所示：其中其中A=D,E,F,GA=D,E,F,G、B=D,E

32、,GB=D,E,G。注意：注意：状态状态F F与表示该状态是最终状态的标记与表示该状态是最终状态的标记F F的不的不同。同。M 0 1 A F B F F G B F B F G A F 2022-12-17华东师大计算机科学技术系42例例2（续三）（续三）解法二解法二 逐步消除法：逐步消除法：a)消除状态消除状态E到到G的的弧：弧：D F E G,1 1 1 0 1 1+2022-12-17华东师大计算机科学技术系43例例2（续四）（续四）b)消除状态消除状态D到到E的的弧：弧：D F E G 1 1 1,0 1 1+1+1 2022-12-17华东师大计算机科学技术系44例例2（续五）（续

33、五）消除所有消除所有弧后得到的状态表弧后得到的状态表 M 0 1 D F D,E,F F E D,F F F G G D F 2022-12-17华东师大计算机科学技术系45例例2（续六）（续六）c)确定化的确定化的DFA如下表所示：如下表所示：M 0 1 D F DEF F F G DEF F DEFG F DEFG F DEFG F G D F 2022-12-17华东师大计算机科学技术系46Kleene定理定理2.从传递图从传递图T到到REXi.设传递图设传递图T为：为：ii.逐步消除个状态或弧逐步消除个状态或弧 得到只剩状态得到只剩状态X、Y，消，消除方法为除方法为：略。得到：略。得到

34、：Sabcdff1f2XY+RXY2022-12-17华东师大计算机科学技术系47正则表达式与有限状态自动机正则表达式与有限状态自动机 例例3：设设V=a,b,V上的正则表达式上的正则表达式R=ba|a+：试：试设计接收设计接收R所表示的符号串集合的确定的，最小的所表示的符号串集合的确定的，最小的有限状态自动机有限状态自动机M。解：解：正则表达式正则表达式R可等价地改写为：可等价地改写为：R=(ba|a)*(ba|a)或或R=(ba|a)(ba|a)*。有限状态自动机有限状态自动机M=(V,Q,M=(V,Q,q,q0 0,Q,Qf f)，其其中中V=a,b,Q=S,A,BV=a,b,Q=S,A

35、,B，q q0 0=S=S，Q Qf f=B=B，如下图所示如下图所示,显然显然M M是确定的和最小的。是确定的和最小的。2022-12-17华东师大计算机科学技术系48 _ S B A b a a+a b 2022-12-17华东师大计算机科学技术系493.2.3 有限状态自动机与有限状态自动机与3型文法型文法定理定理3.3 对任一正则文法对任一正则文法G，存在有限自动机，存在有限自动机M，使得使得L(M)=L(G)。反之亦然。反之亦然。证：证：1.设设G=（VN，VT，p，），），令与其对应的令与其对应的M（VT，Q，Qf)其中：其中：VT，相同，即相同，即作为作为M的开始状态。的开始状态

36、。令令QVNF，F VN 若若a P，让，让（,a）中含有）中含有 若若a P，让，让（,a）中含有）中含有F a VT，令，令（F，a）令令QfF 容易证明容易证明L(M)=L(G)。(例见例见P47）2022-12-17华东师大计算机科学技术系502.设设M是是DFA M（VT，Q，Qf），令与），令与其对应的其对应的G=（VN，VT，p，），其中：），其中：VT，相同，相同，VNQ 若若（,a）C，Q，C Qf，让让a P 若若（,a）C，Q，C Qf，让让 a P或或a P 容易证明容易证明L(M)=L(G)。（例见（例见P49）2022-12-17华东师大计算机科学技术系51 3.2

37、.4 正则表达式与正则文法正则表达式与正则文法 定理定理3.4 对任一正则文法对任一正则文法G，存在，存在REX R，使得，使得L(R)=L(G)。反之亦然。反之亦然。证：一、从正则文法证：一、从正则文法G到到REX R 1.将将G中每个非终结符表示为关于它的正则式方中每个非终结符表示为关于它的正则式方程，得到一个联立方程组。程，得到一个联立方程组。即对即对a|b 为：为：ab 2.如如ab 则解为：则解为：a*b 3.利用利用REX的分配律、结合率和交换律求正则式的分配律、结合率和交换律求正则式方程组的解方程组的解R。容易证明容易证明L(R)=L(G)。（例见（例见P36）2022-12-1

38、7华东师大计算机科学技术系52二、从二、从REX R到正则文法到正则文法G对对V上的上的REX R及及正则文法正则文法G=（VN，VT，p，）1.VT=V。2.R让让R。3.如如a，b是是REX，则对形如，则对形如ab 的产生式转换为的产生式转换为a及及b，VN 。4.对形如对形如a*b转换为转换为a|b。5.重复使用规则重复使用规则3.和和4.，直至每个产生式至多含有一，直至每个产生式至多含有一个非终结符。个非终结符。容易证明容易证明L(R)=L(G)。（例见（例见P37）2022-12-17华东师大计算机科学技术系53 例例4：对例：对例3的的REX R=(ba|a)*(ba|a)，试设计

39、接收试设计接收R所表示的符号串集合的正则文法所表示的符号串集合的正则文法G。解：正则文法解：正则文法G=VT,VN,P,，其中，其中 VT=a,b，VN=,先让先让 (ba|a)(ba|a)*并转换为：并转换为：(ba|a)ba|a(ba|a)*ba|a|ba|b aba|b a注意：注意：可以改为可以改为以及消除以及消除的方法，得：的方法，得：2022-12-17华东师大计算机科学技术系54P为：为：a|b|a a|b|a a|a2022-12-17华东师大计算机科学技术系55习题习题P55 习题习题31.3.12.3.43.3.54.3.65.3.76.3.87.3.98.3.109.3.

40、112022-12-17华东师大计算机科学技术系563.3 词法分析程序的设计和实现词法分析程序的设计和实现 词法分析程序从输入串中识别单词。词法分析程序从输入串中识别单词。单词的构词规则可由状态转换图（单词的构词规则可由状态转换图（FA）或）或REX表示。表示。将将FA确定化、最小化即得到识别单词的确定化、最小化即得到识别单词的FA。编程实现编程实现FA，即得到词法分析程序。，即得到词法分析程序。2022-12-17华东师大计算机科学技术系571.词法分析程序的任务及环境词法分析程序的任务及环境词法分析程序的任务是：词法分析程序的任务是：a)识别源程序组成的输入符号中语义独立的最小识别源程序

41、组成的输入符号中语义独立的最小的词法单位的词法单位单词（单词（token）。）。b)删除注解和其他与输入介质相关的符号（如空删除注解和其他与输入介质相关的符号（如空格、回车等）。格、回车等）。c)报告各种不符合程序设计语言规定的词法错误。报告各种不符合程序设计语言规定的词法错误。d)符号表的维护（插入、查找符号表的维护（插入、查找)2022-12-17华东师大计算机科学技术系58i.单词符号的种类单词符号的种类单词是程序语言最基本的语法单位单词是程序语言最基本的语法单位,通常有五种通常有五种:(1)基本字：有的称关键字或保留字基本字：有的称关键字或保留字,如如if、while、for、do、g

42、oto等等(2)标识符：用户定义各种变量、数组、函数、标识符：用户定义各种变量、数组、函数、过程等的名字，以字母打头后接若干个字母、过程等的名字，以字母打头后接若干个字母、数字。如数字。如X2X2、LenLen、getwordgetword(3)常数：如常数：如216216、31.431.4(4)运算符：如运算符：如+、=、*、/等；等；(5)界限符：如界限符：如;、:、(、)及双字符界符及双字符界符:=、/*、*/及空白符等。及空白符等。（1 1）、（）、（4 4）、（）、（5 5）常可合为一，分为单、）常可合为一，分为单、双字符界限符。双字符界限符。2022-12-17华东师大计算机科学技

43、术系59ii.单词的编码单词的编码词法分析程序输出的是统一格式的单词，形词法分析程序输出的是统一格式的单词，形式为：式为：(type,value,lineNo,columnNo)一般可分为三类：一般可分为三类：a)标识符：表示为（标识符：表示为（ID,addr)，addr是标识是标识符在符号表的位置。符在符号表的位置。b)常数：表示为（常数：表示为（N,addr）addr是常数在常是常数在常数表的位置。数表的位置。c)界限符：表示为（界限符：表示为（DEL,code)，将关键字、，将关键字、运算符、单（双）界限符统一预先编号，运算符、单（双）界限符统一预先编号，则则code为界限符的内部码。为

44、界限符的内部码。2022-12-17华东师大计算机科学技术系60iii.iii.词法分析程序的实现可以有两种方案：词法分析程序的实现可以有两种方案：a)a)把词法分析程序视为语法分析部分的一个把词法分析程序视为语法分析部分的一个子程序，每调用一次词法分析程序就扫描子程序，每调用一次词法分析程序就扫描一个单词。一个单词。b)b)把词法分析程序视为编译程序的一个独立把词法分析程序视为编译程序的一个独立模块，词法分析程序一次扫描全部的输入模块，词法分析程序一次扫描全部的输入符号。符号。常用的方法是常用的方法是a），优点是不用形成中间文件，），优点是不用形成中间文件，直接生成符号表。直接生成符号表。2

45、022-12-17华东师大计算机科学技术系612.词法分析程序的设计词法分析程序的设计i.识别单词的识别单词的FA的设计：的设计：0137空白空白字母字母|数字数字字母字母非字母非字母与数字与数字数字数字数字数字非数字非数字界限符界限符非法字符非法字符 24562022-12-17华东师大计算机科学技术系62 状态状态2的处理流程：的处理流程：查保留字查保留字 得内部码，输出（得内部码，输出（DEL，code）查或送符号表查或送符号表得到得到addr,输出（输出（ID,addr)状态状态4的处理流程：的处理流程：检查前一单词，决定正负号检查前一单词，决定正负号转换相应的常数表示（二、八、十六进

46、制）转换相应的常数表示（二、八、十六进制）查或送常数表得到查或送常数表得到addr，输出（，输出（N,addr)YN2022-12-17华东师大计算机科学技术系63 状态状态5的处理流程：的处理流程：若为若为.按小数点处理，转状态按小数点处理，转状态4 取下一字符取下一字符 是否为双字符界限符是否为双字符界限符 查表得到内部码，查表得到内部码，输出（输出（DEL，code)回送，查表得到内部码，回送，查表得到内部码，输出（输出（DEL，code)状态状态6的处理流程：报错的处理流程：报错Y Y N N 2022-12-17华东师大计算机科学技术系64说明说明上述的上述的FA只是一个粗框架，具体

47、实现时应根据不只是一个粗框架，具体实现时应根据不同语言的词法规则，作必要的改进和相应的处理。同语言的词法规则，作必要的改进和相应的处理。i.特定要求的处理：如特定要求的处理：如true、false表示真、假常数：表示真、假常数：NOT、IN等是运算符；等是运算符；.EQ.表示逻辑相等；允表示逻辑相等；允许许0 x1f、35L等作常数等等。等作常数等等。ii.无符号数的识别：无符号数的识别：如无符号数用如无符号数用REX表示为：表示为：(D+E|D+.D+E|E|.D+E)(+|-)D|D)D*|D+|D*.D+其中其中D表示数字表示数字0，1，9，则相应的最小，则相应的最小的的DFA为：为：2

48、022-12-17华东师大计算机科学技术系650213456EE+DDDD.D.E+D+D2022-12-17华东师大计算机科学技术系66iii.超前搜索超前搜索在在FORTRAN语言中，关键字不是保留字，空格语言中，关键字不是保留字，空格不是分隔符。因此：对语句不是分隔符。因此：对语句 100 DO 110 I=1 100 DO 110 I=1，1010（循环语句，（循环语句，DODO是关键字）是关键字）100 DO 110 I=1.10 100 DO 110 I=1.10（赋值语句，（赋值语句，DO110IDO110I是标识符）是标识符）iv.iv.拼字与缓冲区的组织拼字与缓冲区的组织a)

49、a)P22P22的左、右两区的缓冲区组织形式。的左、右两区的缓冲区组织形式。b)b)用用getline();getline();读入一行，如读入一行，如:char:char*fgets(char fgets(char*S,int n,FILE S,int n,FILE*fp)fp)这样拼字时只需移动缓冲区指针即可。这样拼字时只需移动缓冲区指针即可。while(while(*chp=chp=)chp+;)chp+;2022-12-17华东师大计算机科学技术系673.词法分析程序的实现词法分析程序的实现 FA的状态转换图可以视为一个程序的粗框图：的状态转换图可以视为一个程序的粗框图：FA程序程序状态状态子程序（程序段）子程序（程序段）状态转换状态转换程序的控制流程序的控制流