第 3 讲 词法分析

1、1第三讲 词 法 分 析 词法分析程序的设计 单词的描述工具 有限自动机 正规式和有穷自动机的等价性 正规文法和有穷自动机间的转换 词法分析程序的自动构造工具23.1 词法分析程序的设计词法分析程序的设计 词法分析（词法分析（lexical analysis） 逐个读入源程序字符并按照构词规则切分成一系逐个读入源程序字符并按照构词规则切分成一系 列单词。列单词。 词法分析是编译过程中的一个阶段，在语法分词法分析是编译过程中的一个阶段，在语法分 析前进行。也可以和语法分析结合在一起作为析前进行。也可以和语法分析结合在一起作为 一遍，由语法分析程序调用词法分析程序来获一遍，由语法分析程序调用词法分

2、析程序来获 得当前单词供语法分析使用。得当前单词供语法分析使用。 单词单词是语言中具有独立意义的是语言中具有独立意义的最小单位最小单位，包括保留字、标识符、运算符、标点符包括保留字、标识符、运算符、标点符号和常量等。号和常量等。3一、 词 法 分 析 程 序源程序源程序词法分析程序词法分析程序语法分析程序语法分析程序Tokenget token. 主要任务：主要任务： 读源程序，产生单词符号读源程序，产生单词符号 其他任务：其他任务： 滤掉空格，跳过注释、换行符滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序，追踪换行标志，复制出错源程序， 宏展开，宏展开，4二、二、 单单 词词 符符

3、 号号 单词符号一般可分为下列五种：单词符号一般可分为下列五种： 1、基本字、基本字（关键字关键字）：）：begin, end, if, while, var 等等 2、标识符、标识符：各种名称，如常量名、变量名、过：各种名称，如常量名、变量名、过程名等程名等 3、常数、常数（量）：（量）：25, 3.1415, TRUE, “ABC”等等 4、运算符、运算符：如：如 + ，-，*，/，=等等 5、界符、界符：逗号，分号，括号等：逗号，分号，括号等5 输出表示输出表示（单词类别，单词自身的值）（单词类别，单词自身的值） 例：例： A:=B+2 ( 2, 指向指向A的符号表的入口指针）的符号表的

4、入口指针）( 4, := ) ( 2, 指向指向B的符号表的入口指针的符号表的入口指针 ) ( 4, + ) ( 3, 2 )6 词法分析工作独立的原因：词法分析工作独立的原因： 简化设计简化设计 改进编译效率改进编译效率 增加编译系统的可移植性增加编译系统的可移植性 73.2 单单 词词 的的 描描 述述 工工 具具 正规文法：正规文法： 文法文法G=（VN，VT，P，S），），P中每一产中每一产生式的生式的形式都为：形式都为： AaBAaB 或或 AaAa，（右线型文法右线型文法） 或或 ABaABa 或或 AaAa，（左线型文法左线型文法） 其中：其中：AVAVN N ，BVBVN N

5、， aVaVT T8一、一、 几几 类类 单单 词词 的的 描描 述述 标识符标识符： 标识符标识符 l | l字母数字字母数字 字母数字字母数字 l | d | l字母数字字母数字| d 字母数字字母数字 无符号整数无符号整数： 无符号整数无符号整数 d | d无符号整数无符号整数 运算符运算符： 运算符运算符 + | - | * | / | = | 界符界符： 界符界符 , | ; | ( | ) | 其中：其中：l 表示字母；表示字母；d表示数字表示数字9 无符号实数无符号实数： 无符号实数无符号实数 d 余留无符号数余留无符号数| . 十进小数十进小数 | e指数部分指数部分 余留无符

6、号数余留无符号数 d 余留无符号数余留无符号数| . 十进小数十进小数 | e指数部分指数部分| 十进小数十进小数 d 余留十进小数余留十进小数余留十进小数余留十进小数 e指数部分指数部分| d 余留十进小数余留十进小数| 指数部分指数部分 d 余留整指数余留整指数| s整指数整指数整指数整指数 d 余留整指数余留整指数余留整指数余留整指数 d 余留整指数余留整指数 |其中其中s表示正或负号。表示正或负号。 如如 25.55e+5 和和 2.110二、正二、正 规规 式式 (regular expression) 定义定义（正规式正规式和它所表示的和它所表示的正规集正规集）：）：设字母表为设字

7、母表为 ，辅助字母表，辅助字母表 = ， ， ， ， ， ， 。1、 和和 都是都是 上的正规式，它们所表示的上的正规式，它们所表示的 正规集分别为正规集分别为 和和 ；2、任何、任何 a ，a 是是 上的一个正规式，它所上的一个正规式，它所 表示的正规集为表示的正规集为 a；113、假定假定e1和和e2都是都是 上的正规式，它们所表示的正规上的正规式，它们所表示的正规集分别为集分别为L(e1)和和L(e2)，那么，那么，(e1), e1 e2, e1 e2, e1 也都是正规式也都是正规式,它们所表示的正规集分别为它们所表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e

8、2)和和(L(e1) 。4、仅由有限次使用上述三步骤而定义的表达式才是、仅由有限次使用上述三步骤而定义的表达式才是 上的正规式，仅由这些正规式所表示的字集才是上的正规式，仅由这些正规式所表示的字集才是 上的正规集。上的正规集。12其中其中“ ”读为读为“或或”（也有使用（也有使用“+”代替代替 “ ” 的）；的）；“ ”读为读为“连接连接”；“ ”读为读为“闭包闭包”(即，任意有限次的自重复连接即，任意有限次的自重复连接)。在不致混淆时，括号可省去。在不致混淆时，括号可省去。规定算符的优先顺序为规定算符的优先顺序为“ ”、“ ”、“ ” 。连接符连接符“ ”一般可省略不写。一般可省略不写。“

9、”和和“ ” 都是左结合的。都是左结合的。“ ” 是右结合的是右结合的13 例例4.2 令令 =a，b， 上的正规式和相应的正上的正规式和相应的正规集的例子有：规集的例子有：正规式正规式正规集正规集a a a b a , b ab ab (a b)(a b) aa , ab , ba , bb a , a, aa, ；任意个；任意个 a 的串的串(a b) , a, b, aa, ab , 所有由所有由 a 和和 b 组成的串组成的串(a b) (aa bb)(a b) 上所有含有两个相继上所有含有两个相继 的的 a 或两个相继的或两个相继的 b 组成组成 的串的串 14 例例 =l，d，r=

10、l(l d) 定义的正规集定义的正规集: l,ll,ld,ldd,（标识符）标识符） 例例4.3 =d，.，e，+，-,则则 上的正规上的正规式式 d (.dd )(e(+ - )dd )表示的是表示的是无符号数的集合。其中无符号数的集合。其中d为为09的数字。的数字。15三、三、 正正 规规 式式 等等 价价 若两个正规式若两个正规式e1和和e2所表示的所表示的正规集相同正规集相同,则说则说e1和和e2等价等价,写作写作e1=e2。 例如：例如： e1= (a b)， e2 = b a 又如：又如： b(ab) = (ba) b(a b) = (a b ) 16四、四、 正正 规规 式式 的

11、的 运运 算算 律律 设设 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 “或或”的抽取律的抽取律17五、正规文法和正规式的等价变换五、正规文法和正规式的等价变换对对 上的正规式上的正规式 r ,

12、存在一个存在一个G=(VN,VT,P,S) 使得使得 L(G) = L(r) ，反之亦然。反之亦然。18 1. 将将 正正 规规 式式 转转 换换 成成 正正 规规 文文 法法 VT = , S VN ，生成正规产生式生成正规产生式 S r (1) 对形如对形如 A xy 的的正规产生式：正规产生式：A xB B y （B VN） (2)对形如对形如Ax y的的正规产生式：正规产生式： A xA A y (3)对形如对形如Ax y的的正规产生式正规产生式: A x A y 不断应用上述规则做变换，直到每个产生式最多不断应用上述规则做变换，直到每个产生式最多含一个含一个终结符。终结符。19例：将

13、例：将 r = a(a d) 转换成相应的正规文法。转换成相应的正规文法。GS: SaA AaA AdA AVT = a, d Sa(a d) SaAA(a d) A(ad)A AAaA AdA20 2. 将将 正正 规规 文文 法法 转转 换换 成成 正正 规规 式式（1） A xB, B y A = xy （2）A xA y A = x y（3）A x y A = x y21Gs: S aA A aA A dA S a A a A d S=aA a A = aA dA a d = (a d)A (a d) = (a d) (a d) S=a(a d) (a d) a = a(a d) (a

14、 d) =a(a d) R=a(a d) 223.3 有有 穷穷 自自 动动 机机 确定的有穷自动机（确定的有穷自动机（DFA） 不确定的有穷自动机（不确定的有穷自动机（NFA） NFA DFA 的转换的转换 DFA的化简的化简23 ：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，f，S，Z）其中: 1 1。K K 是一个有穷集，是一个有穷集，状态集状态集, ,它的每个元素称为一个状态；它的每个元素称为一个状态； 2 2。 是一个有穷字母表，它的每个元素称为一个输入符号，是一个有穷字母表，它的每个元素称为一个输入符号，所以也称所以也称为为输入符号表输入符号表； 3 3。f f 是是转

15、换函数转换函数，是在，是在 KK 上的映射，即，如上的映射，即，如 f（ki，a）= kj，（，（kiK，kjK）就意味着，当前状态为就意味着，当前状态为ki，输入符为输入符为 a 时，将转换为下一个状态时，将转换为下一个状态 kj，我们把我们把 kj 称作称作 k ki 的一个后继状态；的一个后继状态； 4。S SK K 是唯一的一个是唯一的一个初态初态； 5 5。Z Z K 是一个是一个终态集终态集，终态也称，终态也称可接受状态可接受状态或或结束状态结束状态。241. DFA 示 例DFA M=（S,U,V,Q, a,b, f, S, Q）其中其中 f 定义为：定义为：f（S，a）=Uf（

16、V，a）=Uf（S，b）=Vf（V , b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q252. DFA 的的 状状 态态 图图 表示表示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（ V , b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QbSUVQaaaba，bb263. DFA 的的 矩矩 阵阵 表表 示示f（S，a）=Uf（V，a）=Uf（S，b）=Vf（V ，b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=QabSUVUQVVUQQQQ字符状态010027 一个输入符一个输入符号号串串t，（，（我们将它表示成

17、我们将它表示成Tt的形式，的形式，其中其中T，t *）在）在DFA M上上运行运行的定义为：的定义为： f（Q， Tt）=f（f（Q，T），），t） 其中其中QK扩充转换函数扩充转换函数f f，是是K*K上的映射，且：上的映射，且： f（Q， ）= Q284. * 上的符上的符号号串串 t 被被 M 接受接受 对于对于*中的任何字符串中的任何字符串t，若存在一条从初态结点若存在一条从初态结点到某一终态结点的道路，且这条路上所有弧的的到某一终态结点的道路，且这条路上所有弧的的标记符连接成的字符串等于标记符连接成的字符串等于t，则称则称t可为可为DFA M所接受，若所接受，若M的初态结点同时又是终

18、态结点，则的初态结点同时又是终态结点，则空字空字( )可为可为M所所接受接受（识别识别）。）。 若若 t *，f(S，t) = P，其中其中 S 为为 DFA M 的开始的开始状态，状态，P Z，Z为终态集。为终态集。则称则称 t 为为 DFA M所所接受接受（识别识别）。）。29例：证明例：证明 t=baab 被如下的被如下的 DFA 所接受所接受DFA M=（S,U,V,Q, a,b, f, S, Q）其中其中 f 定义为：定义为：f（S，a）=Uf（V，a）=Uf（S，b）=Vf（ V , b）=Qf（U，a）=Qf（Q，a）=Qf（U，b）=Vf（Q，b）=Q30bSUVQaaaba，

19、bb证明：证明： 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） = QQ属于终态。得证。属于终态。得证。315. 确定的有穷自动机（确定的有穷自动机（DFA）接受的语言）接受的语言 DFA M=（K，f，S，Z）所能接所能接受的符号串的全体记为受的符号串的全体记为 L(M) L(M) = x | f(S, x) Z , x 结论：结论： 上一个字符串集上一个字符串集 V 是正规的，是正规的，当且仅当，存在一个当且仅当，存在一个 上的确定有穷上的确定有穷自动机自

20、动机 M，使得使得 V=L(M)。32二、不确定的有穷自动机二、不确定的有穷自动机NFA 定义定义 N = (K， ，f，S，Z)，其中其中K为状态为状态的有的有穷非空穷非空集集， 为为有穷输入有穷输入字母表字母表，f为映射为映射函数函数，f: K * 2K，S K是初是初始状始状态集态集，Z K为终为终止状止状态集态集。331. 状状 态态 图图 表表 示示例子例子 NFA N=（S，P，Z，0，1，f，S，P，Z）其中其中 ： f（S，0）=P f（S，1）=S，Zf（P，1）=Z f（Z，0）=Pf（Z，1）=PSPZ00,1111342. 矩矩 阵阵 表表 示示01SPS,Z0PZ0Z

21、PP1简化为01SPS,Z0P.Z0ZPP1例：例：NFA N=（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）= P35*上的符上的符号号串串t在在NFA N上运行。上运行。 *上的符上的符号号串串t被被NFA N接受（识别）。接受（识别）。具有具有 转移的不确定的有穷自动机转移的不确定的有穷自动机 NFAf为为 K （ ）到）到2K的的映射。的的映射。对任何一个具有对任何一个具有 转移的不确定的有穷自动机转移的不确定的有穷自动机NFA N，一定存在一个不具有一定存在一个不具有 转移的不确定转

22、移的不确定的有穷自动机的有穷自动机NFA ，使得，使得L(M)=L(N)。36DFA M=（K，f，S，Z）的行为的模拟程序的行为的模拟程序K:=S；c:=getchar;while ceof do K:=f(K,c); if K= then break else c:=getchar; ;if K is in Z then return (yes) else return (no)37三、三、 NFA 的的 确确 定定 化化 DFA是是NFA的特例的特例.对每个对每个DFA M一定存一定存在一个在一个NFA ，使得，使得 L(M)=L(M )。 对每个对每个NFA M存在着与之存在着与之等价

23、等价的的DFA M 。与某一与某一NFA等价的等价的DFA不唯一。不唯一。381. 定义对状态集合定义对状态集合I的几个有关运算的几个有关运算 1 状态集合状态集合 I 的的 -闭包，表示为闭包，表示为 -closure(I)，定义定义为一状态集，是状态集为一状态集，是状态集 I 中的任何状态中的任何状态 R 经任意条经任意条 弧而能到达的状态的集合。弧而能到达的状态的集合。状态集合状态集合I的任何状态的任何状态 R 都属于都属于 -closure(I)。 2 状态集合状态集合 I 的的 a 弧转换，表示为弧转换，表示为 move(I,a) 定义定义为状态集合为状态集合 J，其中其中 J 是所

24、有那些可从是所有那些可从 I 的某一状的某一状态经过一条态经过一条 a 弧而到达的状态的全体。弧而到达的状态的全体。 3 定义：定义：Ia = -closure(J)，其中：，其中：J= move(I,a) 39例例I = 1, -closure(I) = 1, 2；I = 5, -closure(I) = 5, 6, 2；move(1,2,a) = 5,4 ,3 -closure(5,3,4) = 5, 4, 3, 6, 2, 8 , 7；12534687aaa402. NFA 到 DFA 的 等 价 变 换 算 法 假设假设 NFA N = (K, , f, K0, Kt)按如下办法按如下

25、办法构造一个构造一个 DFA M = (S, , d, S0, St)，使得使得L(M)=L(N)： 1. M的状态集的状态集S由由K的一些子集组成。用的一些子集组成。用S1 S2. Sj表示表示S的元素，其中的元素，其中S1, S2,. Sj是是K的状态。并且约的状态。并且约定，状态定，状态S1, S2,. Sj是按某种规则排列的，即对于是按某种规则排列的，即对于子集子集S1, S2= S2, S1,来说，来说，S的状态就是的状态就是S1 S2；41 2. M和和N的输入字母表是相同的，即是的输入字母表是相同的，即是 ； 3. 转换函数是这样定义的：转换函数是这样定义的： D(S1 ,S2

26、,. , Sj,a) = R1 , R2 ,. , Rt其中其中 ：R1 , R2 ,. , Rt = -closure(move(S1 ,S2 ,. , Sj,a) 4. S0= -closure(K0)为为M的开始状态；的开始状态； 5. St = Si ,Sk ,.,Se | Si ,Sk ,. ,Se S 且且 Si , Sk,. Se Kt 42构造构造NFA N的状态的状态K的子集的算法：的子集的算法： 假定所构造的子集族为假定所构造的子集族为C，即即C= (T1, T2,. TI),其中其中T1, T2,. TI为状态为状态K的子集。的子集。 1. 开始，令开始，令 -closu

27、re(K0)为为C中唯一成员，中唯一成员，并且它是未被标记的。并且它是未被标记的。43 2.while （C中存在尚未被标记的子集中存在尚未被标记的子集T）do 标记标记T； for 每个输入字母每个输入字母a do U:= -closure(move(T,a)； if U不在不在C中中 then 将将U作为未标记的子集加在作为未标记的子集加在C中中 44例，将下图的例，将下图的NFA N转换成转换成DFA M023456789101bbbaaNFA N45023456789101bbbaa -closure(move(Ti,a) -closure(move(Ti,b)T0= -closure

28、(0) =0,1,2,4,71,2,3,4,6,7,8加入为加入为T11,2,4,5,6,7 加入为加入为T2T1= 1,2,3,4,6,7,81,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7,9 加入为加入为T3T2= 1,2,4,5,6,71,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7 已存在已存在T2T3= 1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7,10 加入为加入为T4T4= 1,2,4,5,6,7,10 1,2,3,4,6,7,8 已存在已存在T11,2,4,5,6,7 已存在已存在T246-

29、closure(move(Ti,a)-closure(move(Ti,b)T0= -closure(0) =0,1,2,4,71,2,3,4,6,7,8加入为T11,2,4,5,6,7 加入为T2T1= 1,2,3,4,6,7,81,2,3,4,6,7,8 已存在T11,2,4,5,6,7,9 加入为T3T2= 1,2,4,5,6,71,2,3,4,6,7,8 已存在T11,2,4,5,6,7 已存在T2T3= 1,2,4,5,6,7,9 1,2,3,4,6,7,8 已存在T11,2,4,5,6,7,10 加入为T4T4= 1,2,4,5,6,7,10 1,2,3,4,6,7,8 已存在T11

30、,2,4,5,6,7 已存在T2初态终态b02134abaaaabbbDFA M47四、四、 DFA 的最小化（化简）的最小化（化简） 最小状态最小状态DFA 没有多余状态没有多余状态(死状态死状态) ) 没有两个状态是互相等价（不可区别）没有两个状态是互相等价（不可区别） 两个状态两个状态s和和t等价：满足等价：满足 一致性一致性同是终态或同是非终态同是终态或同是非终态 蔓延性蔓延性从从s出发读入某个出发读入某个a a和从和从 t出发出发读入某个读入某个a到达的状态等价。到达的状态等价。48消消 除除 多多 余余 状状 态态s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s

31、0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s5 s6s3 s1s8 s0s0 s1s3 s60 1011000110s0s1s2s3s4s5s6s7s8s1 s5s2 s7s2 s5s5 s7s3 s1s0 s10 1011001s0s1s2s3s5s749 如图，状态0和4是可区别的。 状态2和3是可区别的，因为读入b后分别到达2和4，而2和4不是等价的。b02134abaaaabbbDFA M50 对于一个对于一个DFA M =DFA M =（K,fK,f, k, k0 0,k,kt t) )，存在一个存在一个

32、最小状态最小状态DFA M = =（K K,f,f, k, k0 0, ,k,kt t) )，使使L(M)=L(M). 算法的核心：算法的核心：把把M的状态集的状态集K分成不相交的子集分成不相交的子集。 结论结论 接受接受L的最小状态有穷自动机不计同构是唯的最小状态有穷自动机不计同构是唯一的。一的。51将下图中的将下图中的DFA M最小化最小化 1, 2, 3, 4, 5, 6, 7Ia: 6, 7, 1, 4, 7, 4, 4Ib: 3, 3, 5, 6, 3, 1, 21,2,3,4 5,6,71,2 3,4 5 6,71,2 3 4 5 6,71352746aaaaaaabbbbbbb1

33、3546aaaaabbbbb52五、五、正规式正规式和有穷自动机的等价性和有穷自动机的等价性 1. 对于对于上的上的NFA M，可以构造一个，可以构造一个上的正规式上的正规式R,R,使得使得L(R)=L(M)。 2 2. .对于对于上的一个正规式上的一个正规式R，可以构造，可以构造一个一个上的上的NFA M，使得，使得L(M)=L(R)。53 1. 对于对于上的上的NFA M，可以构造一个，可以构造一个上的上的正规式正规式R,R,使得使得L(R)=L(M)。第一步：在M的状态转换图上加进两个结点，一个为x结点，一个为y结点。从x结点用弧连接到M的所有初态结点，从M的所有终态结点用弧连接到y结点

34、。形成一个与M等价的M,M只有一个初态x和一个终态y。第二步：逐步消去M中的所有结点，直至只剩下x和y。（消去规则见下页）最后x和y结点间的弧上的标记则为所求的正规式R。54123R1R213R1 R213R1R213R1| R2123R1R3R213R1 R2* R355例：03124a,baaa,ba,bbb求该求该NFA所对应的正规式所对应的正规式R.5603124a,baaa,ba,bbbxy024a|baaa|ba|bbbxy57a|b024a|baaa|bbbxy0a|baa(a|b)*bb(a|b)*xy580a|baa(a|b)*bb(a|b)*xyxy(a|b)* (aa |

35、bb)(a|b)*0a|bxyaa(a|b)* |bb(a|b)*(aa |bb)(a|b)*R=(a|b)* (aa |bb)(a|b)*59 2 2. .对于对于上的一个正规式上的一个正规式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=(K

36、1,1,f1,k1,F1), M2=(K2,2,f2,k2,F2),其中K1,K2不相交.则，NFA M= (K1K2k0,f,k0,F)，k0是新增加的状态符号: = 1 2； f=f1f2 f(k0,)= k1,k2 ； F=F1 F260 (5) R =R1 R2, 分别将步骤（1）（2）（3）应用到R1,R2 产生M1=(K1,1,f1,k1,F1), M2=(K2,2,f2,k2,F2),其中K1,K2不相交. 则，NFA M = ( K1K2k0, 1 2, f, k0, F2 ) : k0,是新增加的状态符号， f=f1f2 对F1中的所有状态k有：f1(k,) = k2 。 (6) R =R*, 分别将步骤（1）（2）（3）应用到R 产生M1=(K