




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、第2章 詞法分析,數(shù)計(jì)學(xué)院 張曉紅 2020/8/5,1 詞法分析,第一階段:保證構(gòu)詞的正確 輸入:字符流 輸出:單詞流 分析的依據(jù):詞法規(guī)則 (如:標(biāo)識(shí)符被定義為字母開頭的字母數(shù)字串) 主要任務(wù): 分離并輸出單詞(保證單詞符合詞法規(guī)則 ); 輸出單詞的值和種類。 構(gòu)造符號(hào)表、常量表; 發(fā)現(xiàn)并報(bào)告詞法錯(cuò)誤。,概述,構(gòu)造編譯程序,必須了解源語言的詞法規(guī)則、語法規(guī)則、語義規(guī)則。 正則表達(dá)式(2.1)是一種描述詞法規(guī)則的有效工具。 有窮自動(dòng)機(jī)(2.2)是一種識(shí)別正則表達(dá)式所描述單詞的有效工具。,單詞識(shí)別的過程,(1)把單詞的結(jié)構(gòu)用正規(guī)式表達(dá)式描述; (2)把正規(guī)式轉(zhuǎn)換為一個(gè)不確定的有窮自動(dòng)機(jī)NFA;
2、 (3)把NFA轉(zhuǎn)換為相應(yīng)的確定的有窮自動(dòng)機(jī)DFA; (4)基于DFA構(gòu)造詞法分析程序。,本章內(nèi)容,正則表達(dá)式 FA概述 DFA定義 NFA定義 NFA的確定化(NFA到DFA的轉(zhuǎn)換) DFA的最小化 正則表達(dá)式與NFA的轉(zhuǎn)換 DFA在計(jì)算機(jī)中的表示 模擬DFA 模擬NFA 詞法分析的實(shí)現(xiàn),正規(guī)文法,某種程序設(shè)計(jì)語言中的所有單詞構(gòu)成一種語言。 正規(guī)表達(dá)式是描述詞法分析所要識(shí)別的單詞的結(jié)構(gòu)和好、集合一種工具。,有關(guān)概念,字母表/符號(hào)集:是符號(hào)的有窮非空集合。 漢語符號(hào)表包括:漢字、數(shù)字、標(biāo)點(diǎn)符號(hào)等 語言符號(hào)表包括:字母、數(shù)字、若干專用符號(hào)以及main、if等保留字。 符號(hào):符號(hào)表中的元素。 符號(hào)
3、串:符號(hào)表的符號(hào)組成的任何有窮序列。 例:=0,1 符號(hào)集 符號(hào)串有: 0,1,00,01,10,11 例:=a,b,c 符號(hào)集 符號(hào)串有:a,b,c,ab,aaca,有關(guān)概念,符號(hào)串的長度:符號(hào)串x有m個(gè)符號(hào),則長度就為m,表示|x|=m。 如: ababa 則長度是5 空符號(hào)串:不含任何符號(hào)的符號(hào)串,用表示 | |= 0。,符號(hào)串的運(yùn)算,(1) 符號(hào)串的頭(前綴)和尾(后綴) 設(shè)z=xy,則x是z的頭,y是z的尾。 例:設(shè)z=abc 則z的頭是:,a,ab,abc 則z的尾是:,c,bc,abc (2) 符號(hào)串的固有頭和固有尾 設(shè)z=xy符號(hào)串,若x非空,則y是固有尾; 若y非空,則x是固
4、有頭。 例:設(shè)z=abc 則z的固有頭是:, a, ab 則z的固有尾是:,c ,bc,符號(hào)串的運(yùn)算,(3) 符號(hào)串的連接(并置) 設(shè)x,y是符號(hào)串,連接xy是y符號(hào)寫在x符號(hào)之后。 例:x=ab, y=MN 則xy=abMN 顯然:x=x=x (4) 符號(hào)串的方冪 設(shè)x是符號(hào)串,則z=xxxx,稱z為x的方冪, 記z=xn。 因此, x0=, x1=x, x2=xx, x3=xxx 顯然,n0時(shí), 有xn =xx n-1 x n-1x,符號(hào)串的運(yùn)算,(5)符號(hào)串的集合 若集合A中的一切元素都是某符號(hào)集上的符號(hào)串,則稱A為該符號(hào)集上的符號(hào)串集合。 (6) 符號(hào)串集合的乘積(笛卡爾積) AB =
5、 AB=xy| xA且yb 例:A=a,b,B=c,d 則AB=ac,ad,bc,bd (7) 符號(hào)串集合的方冪 同一符號(hào)串集合的乘積。 A0=, A1=A, A2=AA, A3=A2A,符號(hào)串的運(yùn)算,(8)閉包(*) 符號(hào)表,用* 表示上所有有窮長的串集合,*稱為的閉包。 * =01 2. n 例:符號(hào)表=0,1 則*=,0,1,00,01,10,11,000,001,010,符號(hào)串的運(yùn)算,(9)正閉包(+) + =1 2. n +稱的正閉包。 用+ 表示上所有非空有窮長的串集合。 顯然:* 0+ + * 例:符號(hào)表=0,1 則*=0,1,00,01,10,11,000,001,010,正規(guī)
6、表達(dá)式,正規(guī)式與正規(guī)集的定義: 設(shè)字母表為, 輔助字母表=、|、*、(、),正規(guī)表達(dá)式, a a b b - (a) a 一個(gè)正規(guī)式可以表示若干個(gè)符號(hào)串, (b) b 其正規(guī)集就是這些符號(hào)串的集合 a|b a,b ab ab a* ,a,aa,aaa,aaaa,. b* ,b,bb,bbb,bbbb,. - (a|b)* a和b組成的所有串 a*|b* ,a,aa,aaa,aaaa,.,b,bb,bbb,bbbb,. aba* 以ab開頭后接若干個(gè)(包括0個(gè))a組成的串 (a|b)*(aa|bb)(a|b)* *上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b的a和b組成的串。,正規(guī)表達(dá)式,例:令d、 、
7、e、,則上的正規(guī)式d*(.dd*| )(e(+|-|)dd*|)表示的是所有無符號(hào)數(shù)。 其中:d為09中的數(shù)字。 比如:2,12.59,3.6e2,471.88e-1等都是正規(guī)式表示集合中的元素。,正規(guī)表達(dá)式,設(shè)A,B,C為正規(guī)式,正規(guī)式服從代數(shù)規(guī)律有: A|B=B|A A|(B|C)=(A|B)|C A(BC)=(AB)C A(B|C)=AB|AC (B|C)A=BA|CA A=A=A (A*)*=A* A*=|AA* (AB)*A=A(BA)* (A|B)*=(A*B*)*=(A*|B*)* A=b|aA 當(dāng)且僅當(dāng) A=a*b,有窮自動(dòng)機(jī)FA,有窮自動(dòng)機(jī)FA: 是一種自動(dòng)識(shí)別裝置,能正確識(shí)
8、別正規(guī)集; 是詞法分析程序的工具和方法,可自動(dòng)識(shí)別(且是正確識(shí)別)正規(guī)集。 有窮自動(dòng)機(jī)FA分為: 確定的有窮自動(dòng)機(jī)(DFA) 不確定的有窮自動(dòng)機(jī)(NFA),有窮自動(dòng)機(jī)FA,輸入符號(hào)串 “I am a teacher.” 初始狀態(tài)0出發(fā)。 狀態(tài)1識(shí)別:單詞“a” 狀態(tài)2識(shí)別:單詞“am”,1,確定的有窮自動(dòng)機(jī)DFA,一個(gè)確定的有窮自動(dòng)機(jī)DFA M是一個(gè)五元組: M=(Q,t,q0,F(xiàn)),其中: Q是一個(gè)有窮狀態(tài)集,每個(gè)元素表示一個(gè)狀態(tài); 是一個(gè)有窮字母表,每個(gè)元素是一個(gè)輸入字符; t是轉(zhuǎn)換函數(shù),是在QQ上的映象,如: t(qi ,a)= qj (qi, qjQ); 含義:當(dāng)前狀態(tài)為qi,輸入字符
9、a,轉(zhuǎn)換為qj狀態(tài) q0是初態(tài),q0Q; FQ,是終態(tài)集。 “確定” :下一個(gè)輸入字符惟一地確定了下一個(gè)當(dāng)前狀態(tài).,確定的有窮自動(dòng)機(jī)DFA,例:DFA的M: M(S,U,V,Q,a,b,f,S,Q) 其中f為: f(S,a)=U, f(S,b)=V, f(U,a)=Q f(U,b)=V, f(V,a)=U, f(V,b)=Q f(Q,a)=Q, f(Q,b)=Q,不確定的有窮自動(dòng)機(jī)NFA,一個(gè)不確定的有窮自動(dòng)機(jī)NFA M是一個(gè)五元組: M=(Q,t,S,F(xiàn)),其中: Q是一個(gè)有窮狀態(tài)集,每個(gè)元素表示一個(gè)狀態(tài); 是一個(gè)有窮字母表,每個(gè)元素是一個(gè)輸入字符; t是一個(gè)從Q*到Q上的子集的映射; t:
10、Q* 2k SQ,是一個(gè)非空初態(tài)集; F Q,是一個(gè)終態(tài)集。,NFA和DFA的差別,DFA有一個(gè)初始狀態(tài), NFA有一個(gè)初始狀態(tài)集; DFA的映射是單值映射, NFA的映射是多值映射; DFA不允許空轉(zhuǎn)換, NFA允許空轉(zhuǎn)換。,不確定的有窮自動(dòng)機(jī)NFA,例:一個(gè)NFA M: M(0,1,2,3,4,a,b,f,0,2,4) 其中:f(0,a)=0,3 f(2,b)=2 f(0,b)=0,1 f(3,a)=4 f(1,b)=2 f(4,a)=4 f(2,a)=2 f(4,b)=4,狀態(tài)轉(zhuǎn)換圖,方法如下: 圖的結(jié)點(diǎn)表示狀態(tài); 初始態(tài)用 “”或“”表示; 終態(tài)點(diǎn)用 “” 或“” 表示; 若f(Ki
11、,a)= Kj ,則從狀態(tài)點(diǎn)Ki 到Kj畫弧,標(biāo)記為a。,狀態(tài)轉(zhuǎn)換圖,例:DFA的M(S,U,V,Q,a,b,f,S,Q) 其中f為: f(S,a)=U, f(S,b)=V, f(U,a)=Q f(U,b)=V, f(V,a)=U, f(V,b)=Q f(Q,a)=Q, f(Q,b)=Q,U,V,狀態(tài)轉(zhuǎn)換圖,例:一個(gè)NFA M: M(0,1,2,3,4,a,b,f,0,2,4) 其中:f(0,a)=0,3 f(2,b)=2 f(0,b)=0,1 f(3,a)=4 f(1,b)=2 f(4,a)=4 f(2,a)=2 f(4,b)=4,說明:一個(gè)初態(tài),二個(gè)終態(tài)。 DFA是NFA的特例。,狀態(tài)轉(zhuǎn)換
12、矩陣,方法: 行表示狀態(tài) 列表示輸入字符 元素表示相應(yīng)狀態(tài)行和輸入字符下的新狀態(tài)。,狀態(tài)轉(zhuǎn)換矩陣,例:DFA的MS,U,V,Q,a,b,f,S,Q) 其中f為: f(S,a)=U f(S,b)=V f(U,a)=Q f(U,b)=V f(V,a)=U f(V,b)=Q f(Q,a)=Q f(Q,b)=Q,狀態(tài)轉(zhuǎn)換矩陣,例:一個(gè)NFA, M(0,1,2,3,4,a,b,f,0,2,4) 其中: f(0,a)=0,3 f(2,b)=2 f(0,b)=0,1 f(3,a)=4 f(1,b)=2 f(4,a)=4 f(2,a)=2 f(4,b)=4,字符,狀態(tài),構(gòu)形和移動(dòng),構(gòu)形:(q,w) q表示一個(gè)
13、狀態(tài) W是待掃描的輸入串 初始構(gòu)形:(q0,w) q0表示一個(gè)初始狀態(tài) W是整個(gè)輸入串 終止構(gòu)形:(q, ) q表示一個(gè)終止?fàn)顟B(tài) 是空串,構(gòu)形和移動(dòng),移動(dòng): (q,aw) (q, w) q為當(dāng)前狀態(tài) aw為當(dāng)前待輸入串 t(q,a)=q 表示當(dāng)前狀態(tài)q下輸入a后到達(dá)新狀態(tài)q,識(shí)別了符號(hào)a。,接受(識(shí)別)的概念,自動(dòng)識(shí)別單詞 對(duì)于*中的任何字符串w,若存在一條初態(tài)到某一終態(tài)的路,且這條路上所有弧的標(biāo)記符連接成的字符串等于w,則稱w可為FA M所接受/識(shí)別。 即: FA M=Q, ,q0 , t , F中 w滿足w *, (q0, w) * (q, ), q F 時(shí),稱為w可為FA M所接受/識(shí)別
14、。 若M的初態(tài)同時(shí)又是終態(tài),則空字可為M所接受。,FA M識(shí)別的語言L(M),FA M=Q, ,q0 , t , F所識(shí)別的語言L(M): L(M)=w | w *, (q0, w) * (q, ), q F FA M所接受/識(shí)別的符號(hào)串的集合。,接受(識(shí)別)的理解,設(shè)QK,函數(shù)f(Q,)=Q,則輸入字符串是空串,并停留在原狀態(tài)上。 輸入字符串t(t表示成Tt1形式,T,t1 *),在DFA M上運(yùn)行(移動(dòng))的定義為: f(Q,Tt1)=f(f(Q,T),t1),其中QK。 Q:當(dāng)前狀態(tài) Tt1:當(dāng)天待輸入串 f(Q,T):轉(zhuǎn)換后新狀態(tài) t1:剩余待輸入串,接受(識(shí)別)的理解,例如:baab字
15、符串被DFA所接受,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是終態(tài)) DFA M所能接受的字符串的全體記為L(M)稱為語言 (也即句子的集合),FA的等價(jià)性,對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)M和M,如果L(M)=L(M),則稱M與M是等價(jià)的。 例: DFA A=(q0,q1,a,b,t,q0,q0) t(q0,a)=q1, t(q1,b)=q0 DFA B=(q0,q1,q2,a,b,t,q0, q0,q2) t(q0,a)=q1, t(
16、q1,b)=q2,t(q2,a)=q1 L(A)=L(B)=(ab)n|n0 對(duì)于每個(gè)NFA M,存在一個(gè)DFA M,使得L(M)=L(M)。,NFA 轉(zhuǎn)換為等價(jià)的DFA(NFA確定化),NFADFA(子集法) 子集構(gòu)造法 DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合 讀了輸入a1 a2 an后, NFA能到達(dá)的所有狀態(tài):s1, s2, , sk, 則DFA到達(dá)狀態(tài)s1, s2, , sk,NFA 轉(zhuǎn)換為等價(jià)的DFA,NFADFA(子集法) 子集構(gòu)造法 DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合 讀了輸入a1 a2 an后, NFA能到達(dá)的所有狀態(tài):s1, s2, , sk, 則DFA到達(dá)狀態(tài)s1, s
17、2, , sk,NFA 轉(zhuǎn)換為等價(jià)的DFA,NFADFA(子集法) 子集構(gòu)造法 DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合 讀了輸入a1 a2 an后, NFA能到達(dá)的所有狀態(tài):s1, s2, , sk, 則DFA到達(dá)狀態(tài)s1, s2, , sk,NFA 轉(zhuǎn)換為等價(jià)的DFA,NFADFA(子集法) 子集構(gòu)造法 DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合 讀了輸入a1 a2 an后, NFA能到達(dá)的所有狀態(tài):s1, s2, , sk, 則DFA到達(dá)狀態(tài)s1, s2, , sk,NFA 轉(zhuǎn)換為等價(jià)的DFA,NFADFA(子集法) 子集構(gòu)造法 DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合 讀了輸入a1 a2 an
18、后, NFA能到達(dá)的所有狀態(tài):s1, s2, , sk, 則DFA到達(dá)狀態(tài)s1, s2, , sk,NFA 轉(zhuǎn)換為等價(jià)的DFA,NFA確定化的兩個(gè)步驟 (回顧DFA定義): 計(jì)算下一狀態(tài)轉(zhuǎn)移時(shí): 消除 狀態(tài)轉(zhuǎn)移:-closure(T) 消除多于一個(gè)的下一狀態(tài)轉(zhuǎn)移:move(S, a),NFA 轉(zhuǎn)換為等價(jià)的DFA,-closure(s): 從狀態(tài)s出發(fā),不經(jīng)任何字符達(dá)到的狀態(tài)的集合。 包括s和弧到達(dá)的新狀態(tài)s,以及新狀態(tài)s 的弧到達(dá)的新狀態(tài),直到集合不再增大。 用集合S表示。 S= -closure(s) =sf(s,) 其中f(s)是NFA中從狀態(tài)s出發(fā),僅沿弧到達(dá)的狀態(tài)集合。,NFA 轉(zhuǎn)換為
19、等價(jià)的DFA,NFA 轉(zhuǎn)換為等價(jià)的DFA,-closure(T) 定義 : 表示從NFA狀態(tài)集合T的每一狀個(gè)態(tài)出發(fā),沿弧能夠到達(dá)的所有狀態(tài)集合。 用集合S表示。 S= -closure(T) =-closure(t,) tT S=T(f(t,) 其中f(t,)是NFA中從狀態(tài)t出發(fā),僅沿弧到達(dá)的狀態(tài)集合。,NFA 轉(zhuǎn)換為等價(jià)的DFA,算法 S=T;/結(jié)果集合包括T集合本身doS=S; S=S( f(t,) (tS) / T的任一狀態(tài)出發(fā),沿弧能夠到達(dá)的所有狀態(tài) while( S=S );,NFA 轉(zhuǎn)換為等價(jià)的DFA,NFA 轉(zhuǎn)換為等價(jià)的DFA,DFA的轉(zhuǎn)移函數(shù) move(T,a) 定義: 表示
20、從狀態(tài)集T的任何一個(gè)狀態(tài)出發(fā),沿a弧轉(zhuǎn)移能夠到達(dá)的所有狀態(tài)構(gòu)成的狀態(tài)集合J。 用集合J表示。J=move(T,a),即 J=f(t, a), t T,NFA 轉(zhuǎn)換為等價(jià)的DFA,NFA 轉(zhuǎn)換為等價(jià)的DFA,DFA的狀態(tài)集合:要在move(T,a)的基礎(chǔ)上求 _closure 。即 f(S, a)= _closure (f(t, a) 其中S是NFA的狀態(tài)集, a 。,NFA 轉(zhuǎn)換為等價(jià)的DFA,NFA 轉(zhuǎn)換為等價(jià)的DFA,實(shí)現(xiàn)從NFA構(gòu)造DFA的算法-子集構(gòu)造法 已知:一個(gè)NFA M(,0,),其中 是一個(gè)有限狀態(tài)集合。 是一個(gè)字母表,它的每個(gè)元素稱為一個(gè)輸入符號(hào)。 0,0 稱為初始狀態(tài)。 ,
21、稱為終結(jié)狀態(tài)集合。 是一個(gè)從到的子集的映射,即:,NFA 轉(zhuǎn)換為等價(jià)的DFA,從NFA構(gòu)造一個(gè)等價(jià)的DFA M =(S,S0,St,),其中 S是一個(gè)有限狀態(tài)集合,用DFA的一個(gè)狀態(tài)s表示NFA的一個(gè)狀態(tài)子集Tj。 S=T0,T1,T2Tj DFA與NFA字母表相同。 S0S,S0為初始狀態(tài)。 S0=-closure(0) St,St稱為終結(jié)狀態(tài)集合。是包含原終止?fàn)顟B(tài)的所有新狀態(tài)的集合。 是一個(gè)從 到的單值映射,表示狀態(tài)與狀態(tài)之間的轉(zhuǎn)換關(guān)系。,算法 從NFA構(gòu)造DFA(子集法),輸入 NFA N 輸出 等價(jià)的DFA D。 初態(tài)含有NFA初態(tài),終態(tài)集是含有NFA終態(tài)的狀態(tài)集合 方法 用下述過程構(gòu)
22、造DFA :,S0=-closure(s0)作為初始狀態(tài) 加入Dstates,且尚未標(biāo)記; T=S0; while (TDstates- 記錄狀態(tài)轉(zhuǎn)移 T=Dstates中的下一個(gè)狀態(tài)。,有限自動(dòng)機(jī)的確定化,例 構(gòu)造NFA的DFA NFA狀態(tài)圖:,有限自動(dòng)機(jī)的確定化,1、-closure(0) = 0, 1, 2, 4, 7 = S1,2、標(biāo)記S1: -closure(move(S1,a))=1, 2, 3, 4, 6, 7, 8=S2,2、標(biāo)記S1: -closure(move(S1,b))= 1, 2, 4, 5, 6, 7 =S3,3、標(biāo)記S2: -closure(move(S2,a)=
23、1, 2, 3, 4, 6, 7, 8=S2,3、標(biāo)記S2: -closure(move(S2,b)= 1, 2, 4, 5, 6, 7, 9=S4,4、標(biāo)記S3: -closure(move(S3,a)= 1, 2, 3, 4, 6, 7, 8=S2,4、標(biāo)記S3: -closure(move(S3,b)= 1, 2, 4, 5, 6, 7 =S3,5、標(biāo)記S4: -closure(move(S4,a)= 1, 2, 3, 4, 6, 7, 8=S2,5、標(biāo)記S4: -closure(move(S4,b)= 1, 2, 4, 5, 6, 7,10=S5,6、標(biāo)記S5: -closure(mo
24、ve(S5,a)= 1, 2, 3, 4, 6, 7, 8 =S2,6、標(biāo)記S5: -closure(move(S5,b)= 1, 2, 4, 5, 6, 7 =S3,-closure(0)=0,1,2,4,7* S1 -closure (move(S1,a)=3,8,6,7,1,2,4* S2 -closure (move(S1,b)=5,6,7,1,2,4* S3 -closure (move(S2,a)=3,8,6,7,1,2,4 S2 -closure (move(S2,b)=5,9,6,7,1,2,4* S4 -closure (move(S3,a)=3,8,6,7,1,2,4 S2
25、 -closure (move(S3,b)=5,6,7,1,2,4 S3 -closure (move(S4,a)=3,8,6,7,1,2,4 S2 -closure (move(S4,b)=5,10,6,7,1,2,4* S5 -closure (move(S5,a)=3,8,6,7,1,2,4 S2 -closure (move(S5,b)=5,6,7,1,2,4 S3,識(shí)別abb和abab: 1 a 2 b 4 b 5 接受 1 a 2 b 4 a 2 b 5 不接受,過程總結(jié):,NFA,DFA,最小DFA,識(shí)別語言 (a|b)*ab 的自動(dòng)機(jī),子集構(gòu)造法不一定得到最簡DFA,DFA的化
26、簡,1 定義:所謂一個(gè)DFA M的化簡是指尋找一個(gè)狀態(tài)數(shù)比較少的DFA M,使L(M)=L(M)。 2 化簡方法 :(分割法) 化簡后的有限自動(dòng)機(jī)中沒有多余狀態(tài),同時(shí)沒有等價(jià)狀態(tài)。 因此化簡有限自動(dòng)機(jī)的方法有兩個(gè): 消除多余狀態(tài) 合并等價(jià)狀態(tài),DFA的化簡,多余狀態(tài)(直接清除): 不可到達(dá)的狀態(tài):從有限自動(dòng)機(jī)的開始狀態(tài)出發(fā),任何輸入串也不能到達(dá)的狀態(tài),(沒有入邊的非初始狀態(tài))。 死狀態(tài):即不是終態(tài)且對(duì)所有輸入字符均轉(zhuǎn)向其自身,(不指向其他狀態(tài)的非終止?fàn)顟B(tài))。,DFA的化簡,等價(jià)狀態(tài): 也稱不可區(qū)分的狀態(tài)。 在有限自動(dòng)機(jī)中,兩個(gè)狀態(tài)p和q等價(jià)應(yīng)滿足如下條件: (a)一致性條件:狀態(tài)p和q必須同時(shí)
27、為終止?fàn)顟B(tài)或?yàn)榉墙K止?fàn)顟B(tài)。 (b)蔓延性條件:對(duì)于所有輸入符號(hào),狀態(tài)p和q必須轉(zhuǎn)換到等價(jià)的狀態(tài)。 狀態(tài)p和q是可區(qū)分(即不等價(jià)的): 對(duì)于任何兩個(gè)狀態(tài)p和q ,若從一狀態(tài)出發(fā)接受輸入字符串,而從另一狀態(tài)出發(fā)不接受; 或者從p和q出發(fā)輸入字符串,到達(dá)不同的接受狀態(tài)。,DFA的化簡,合并等價(jià)狀態(tài)的方法-分割法 算法的核心:把DFA M的狀態(tài)集K分成若干個(gè)不相交的子集。其中狀態(tài)集中的任意兩個(gè)狀態(tài)都是等價(jià)的。 具體方法:構(gòu)造一張表,對(duì)每一個(gè)狀態(tài)對(duì)(si,sj)(ij)有一表項(xiàng),每當(dāng)發(fā)現(xiàn)一對(duì)狀態(tài)不等價(jià)時(shí),就放一個(gè)x到相應(yīng)表項(xiàng)中。 (1)根據(jù)一致性條件,在每一個(gè)對(duì)應(yīng)于終結(jié)狀態(tài)和非終結(jié)狀態(tài)的表項(xiàng)中放上一個(gè)x
28、。(2)根據(jù)蔓延性條件,對(duì)每一個(gè)狀態(tài)對(duì)(p,q),若a,(p,a)=r,(q,a)=s,如果r和s不等價(jià),則(p,q)不等價(jià)。 (3)重復(fù)2,直到?jīng)]有新的不等價(jià)狀態(tài)對(duì)出現(xiàn)。,算法 最小化DFA的狀態(tài)數(shù),輸入 DFA D=S,f,s0,F。 輸出 等價(jià)的D=S,f,s0,F,(D狀態(tài)數(shù)最少) 方法 執(zhí)行如下步驟: 1.初始劃分=S-F,F,F(xiàn)是終止?fàn)顟B(tài)集,S是所有狀態(tài)集; 2. 應(yīng)用下述過程構(gòu)造新的劃分new: for 的每一個(gè)組G 劃分G,G的兩個(gè)狀態(tài)s和t在同一組中的充要條件是: a.(f(s,a)Gif(t,a)Gi); - Gi是中某個(gè)組 用新劃分的組替代G,形成新的劃分new;,3.若
29、new=,令final=,轉(zhuǎn)4;否則令=new并重復(fù)步驟2; 4.在final每個(gè)組Gi中選一個(gè)代表si, 使得D中從Gi所有狀態(tài)出發(fā)的狀態(tài)轉(zhuǎn)移在D中均從si出發(fā),D中所有轉(zhuǎn)向Gi中的狀態(tài)轉(zhuǎn)移在D中均轉(zhuǎn)向si; 含有D中s0的狀態(tài)組G0的代表s0稱為D的初態(tài),D中所有含F(xiàn)中狀態(tài)的Gj的代表sj構(gòu)成D的終態(tài)集F; 5.刪除死狀態(tài)。(死狀態(tài):即不是終態(tài)且對(duì)所有輸入字符均轉(zhuǎn)向其自身,或從初態(tài)不可到達(dá)的狀態(tài)。),算法 最小化DFA的狀態(tài)數(shù),DFA的化簡,具體方法: 初始劃分:終態(tài)與非終態(tài); 利用可區(qū)分的概念,反復(fù)分裂劃分中的組Gi,直到不可再分裂; 由最終劃分構(gòu)造D,關(guān)鍵是選代表和修改狀態(tài)轉(zhuǎn)移; 消除
30、可能的死狀態(tài)和不可達(dá)狀態(tài)。,DFA的化簡,m(A,a)=B, m(A,b)=C m(B,a)=B, m(B,b)=D m(C,a)=B, m(C,b)=C m(D,a)=B, m(D,b)=E m(E,a)=B, m(E,b)=C,1初始劃分1=ABCD,E 2根據(jù)算法中步驟2,反復(fù)分裂劃分中的組: m(D, b)=E 2=ABC,D,E m(B, b)=D 3=AC,B,D,E 3? 于是:final=AC,B,D,E,3根據(jù)final構(gòu)造D: 選代表,用A代表AC組; 修改狀態(tài)轉(zhuǎn)移: (去掉結(jié)點(diǎn)C和所有出邊,將所有入邊改為指向A的弧。),m(A,a)=B, m(A,b)=A m(B,a)=
31、B, m(B,b)=D m(D,a)=B, m(D,b)=E m(E,a)=B, m(E,b)=A,用0、1、2、3代替A、B、D、E,得:,3,單詞識(shí)別,(1)把單詞的結(jié)構(gòu)用正規(guī)式或正規(guī)文法描述; (2)把正規(guī)式轉(zhuǎn)換為一個(gè)NFA; (3)把NFA轉(zhuǎn)換為相應(yīng)的DFA; (4)基于DFA構(gòu)造詞法分析程序。,單詞識(shí)別,各種詞法工具的轉(zhuǎn)換:,正規(guī)式,NFA N,DFA M,正規(guī)文法,DFA M,確定化,最小化,正規(guī)文法到NFA,正規(guī)文法G: (Vn,Vt,P,S) NFA M: (K,f,s0,Z) Vt= 添加狀態(tài)Z作為終止?fàn)顟B(tài); VnZ=K 開始符號(hào)S對(duì)應(yīng)的狀態(tài)就是初始狀態(tài)s0; f: U aV
32、 = f(U,a)=V U a = f(U,a)=Z,正規(guī)文法到NFA,例:正規(guī)文法G: (Vn,Vt,P,S) Vn=S,N Vt=+,-,d P=S+N S-N SdN Sd NdN Nd S 轉(zhuǎn)換為:NFA M: (K,f,s0,Z) = Vt=+,-,d 添加狀態(tài)Z作為終止?fàn)顟B(tài); K=VnZ =S,N,Z 初始狀態(tài)S; f: f(S,+)=N f(S,-)=N f(S,d)=N f(S,d)=Z f(N,d)=N f(N,d)=Z,NFA到正規(guī)文法,NFA M: (K,f,s0,Z) 正規(guī)文法G: (Vn,Vt,P,S) = Vt K = Vn ( K-Z=Vn ?) s0= S; 添
33、加產(chǎn)生式: Z P: f(U,a)=V = U aV f(U,a)=Z = U a,NFA到正規(guī)文法,例:NFA M: (K,f,s0,Z) K=S,A,B,C =x,y f= s0 = S Z=B,C 正規(guī)文法G: (Vn,Vt,P,S) Vt = =x,y Vn= K = S,A,B,C S=s0; 添加產(chǎn)生式: B C P: S xA S yB A xB A yA A A yC B xC B yC B Ya,正規(guī)表達(dá)式與NFA的等價(jià)性,對(duì)于上的每個(gè)正規(guī)式R,可以構(gòu)造一個(gè)上的NFA M,使得L(M)=L(R)。 對(duì)于上的NFA M,可以構(gòu)造一個(gè)上的正規(guī)式R,使得L(R)=L(M)。,正規(guī)表
34、達(dá)式到NFA,1、構(gòu)造開始狀態(tài)S和終止?fàn)顟B(tài)Z: 2、按照替換規(guī)則對(duì)正規(guī)表達(dá)式R,逐步進(jìn)行分解。 3、直到所有的弧上都是單個(gè)符號(hào)或者為止。,S,Z,R,正規(guī)式R到 NFA M的簡化替換規(guī)則:,正規(guī)表達(dá)式到NFA,例1:L(R) =(a|b)*abb,構(gòu)造NFA使L(N)=L(R) 解:,例2: L(R) =(a|b)*(aa|bb)(a|b)* 構(gòu)造L(N)使與L(R) 等價(jià)。, 正規(guī)式,構(gòu)造NFA為: 或: 對(duì)應(yīng)正規(guī)式,構(gòu)造NFA為: 對(duì)應(yīng)正規(guī)式a,構(gòu)造NFA為: s,t是正規(guī)式,相應(yīng)NFA為N(s),N(t),則正規(guī)式R=s|t,構(gòu)造NFA(R) 為:,x,y,正規(guī)表達(dá)式到NFA,從正規(guī)式R
35、構(gòu)造NFA完整規(guī)則如下:, s,t是正規(guī)式,相應(yīng)NFA為N(s),N(t),則正規(guī)式R=st,構(gòu)造NFA(R) 為:,x,y,N(t),N(s), s,t是正規(guī)式,相應(yīng)NFA為N(s),N(t),則正規(guī)式R=s*,構(gòu)造NFA(R) 為:,x,y,N(s),正規(guī)表達(dá)式到NFA,正規(guī)表達(dá)式到NFA轉(zhuǎn)換的遞歸算法: Procedure FSM(EXPR : reg-expr; P,Q : state) Var A:state; Begin If EXPR = then 什么也不做 Else If EXPR = then t(P, )=Q; Else If EXPR = a then t(P, a)=
36、Q;,正規(guī)表達(dá)式到NFA,Else If EXPR = (X) then FSM(X,P,Q); Else If EXPR = XY then 連接 Begin A:=newstate; FSM(X,P,A); FSM(Y,A,Q); End,正規(guī)表達(dá)式到NFA,Else If EXPR = X|Y then選擇 Begin FSM(X,P,Q); FSM(Y,P,Q); End,正規(guī)表達(dá)式到NFA,Else If EXPR = X* then閉包 Begin A:=newstate; FSM(,P,A); FSM(X,A,A); FSM(,A,Q); End End,正規(guī)表達(dá)式到NFA,正規(guī)
37、表達(dá)式到NFA,正規(guī)表達(dá)式到NFA,正規(guī)表達(dá)式到NFA,正規(guī)表達(dá)式到NFA,正規(guī)表達(dá)式到NFA,正規(guī)表達(dá)式到NFA,正規(guī)表達(dá)式到NFA,(a|b)*ab的兩個(gè)NFA的比較,手工構(gòu)造:,算法構(gòu)造:,NFA到正規(guī)表達(dá)式,1、拓廣NFA: 添加新的開始狀態(tài)S和終止?fàn)顟B(tài)Z,S與原開始狀態(tài)用連接,Z與原所有終止?fàn)顟B(tài)用連接 2、使用替換規(guī)則消去所有節(jié)點(diǎn)和連接。 3、直到只有S和Z,弧上的表達(dá)式即為轉(zhuǎn)換后的正規(guī)表達(dá)式R。,NFA到正規(guī)表達(dá)式,方法:在每一條弧上用一個(gè)正規(guī)式作標(biāo)記。 規(guī)則:,例2: L(M)如下圖: 求正規(guī)式R,使L(R)=L(M). 解:,a,b,y,a|b,a|b,(a|b)(a|b)*,
38、因此: L(R)= (a|b)(a|b)*,例3:M狀態(tài)圖如下: 求正規(guī)式R,是L(R)=L(M).,解:加x,y結(jié)點(diǎn)。,a,b,0,3,4,1,2,a,a,b,b,a,b,a,b,x,0,4,2,aa,bb,a,b,a,b,x,a,b,a,b,0,aa(a|b)*,bb(a|b)*,x,y,(a|b)*(aa|bb)(a|b)*,x,所以 L(R) =(a|b)*(aa|bb)(a|b)*,正規(guī)文法和正規(guī)式的等價(jià)性,程序設(shè)計(jì)語言中的單詞既能用正規(guī)文法表示,又能用正規(guī)式來表示。,正規(guī)文法: l|l l|d|l |d d|d l表示a-z中的任何英文字母 d表示0-9中的任何數(shù)字,正規(guī)式: 標(biāo)識(shí)
39、符: e1=字母(字母|數(shù)字)* 無符號(hào)整數(shù): e2=dd*,正規(guī)文法和正規(guī)式的等價(jià)性,一個(gè)正規(guī)語言可以由正規(guī)文法定義,也可以用正規(guī)式定義。 對(duì)于任意一個(gè)正規(guī)文法,存在一個(gè)定義同一語言的正規(guī)式。 對(duì)每一個(gè)正規(guī)式,存在一個(gè)生成同一語言的正規(guī)文法。 即正規(guī)式正規(guī)文法,正規(guī)表達(dá)式到正規(guī)文法,將上的一個(gè)正規(guī)式r轉(zhuǎn)換為一個(gè)正規(guī)文法G=(VN,VT,P,S)的規(guī)則: 令VT=, 對(duì)正規(guī)式r,生成Sr,S為G的開始符號(hào)。 不斷拆分r直到符合正規(guī)文法要求的規(guī)則形式: 若x,y都是正規(guī)式 對(duì)形如Axy的產(chǎn)生式,寫成AxBBy 其中B為新的非終結(jié)符,B VN 對(duì)形如Ax*y的產(chǎn)生式,重寫為:Ax A Ay 對(duì)形如
40、Ax|y的產(chǎn)生式,重寫為:AxAy 不斷利用上述規(guī)則進(jìn)行變換即可。,正規(guī)表達(dá)式到正規(guī)文法,例:將Ra(a|d)*變換成正規(guī)文法。,解:令S是文法開始符號(hào)。,S a(a|d)*,正規(guī)文法到正規(guī)表達(dá)式,將一個(gè)正規(guī)文法轉(zhuǎn)換為正規(guī)式的規(guī)則: 轉(zhuǎn)換規(guī)則: AxB,By 正規(guī)式為: A=xy AxA|y 正規(guī)式為: A=x*y Ax,Ay 正規(guī)式為: A=x|y 不斷收縮產(chǎn)生式規(guī)則,直到剩下一個(gè)開始符號(hào)定義的正規(guī)式。,正規(guī)文法到正規(guī)表達(dá)式,例:文法GS 轉(zhuǎn)換為正規(guī)式。,S aA S a A aA A dA A a A d,S aA S a A aA A dA A a A d,SaA|a,AaA|dA,Aa
41、|d,A(aA|dA)|(a|d) A(a|d)A|(a|d) A(a|d)*(a|d),根據(jù)上述規(guī)則3 Ax,Ay 推出A=x|y,將它化為正規(guī)文法 變成A (a|d)A|(a|d),再根據(jù)上述 規(guī)則2轉(zhuǎn)換 xy (a|d),將A代入SaA|a得到如下:,正規(guī)文法到正規(guī)表達(dá)式,例:文法GS 轉(zhuǎn)換為正規(guī)式,S aA S a A aA A dA A a A d,Sa( (a|d)*(a|d) |a =a(a|d)+|a =a(a|d)+|)= a(a|d)*,自動(dòng)識(shí)別單詞的方法,(1)把單詞的結(jié)構(gòu)用正規(guī)式描述; (2)把正規(guī)式轉(zhuǎn)換為一個(gè)NFA; (3)把NFA轉(zhuǎn)換為相應(yīng)的DFA; (4)基于DF
42、A構(gòu)造詞法分析程序。,DFA的行為的模擬程序,DFA M=(K,f,S,Z)的行為的模擬程序 K=S; c=getchar(); while (c!=eof) K=f(K,c); c=getchar(); If( K is in Z) then return (yes); else return (no);,DFA識(shí)別程序(模擬main()函數(shù)),main() char states5=0,1, 2, 3, 4; char s0=0; char f_states3=2, 4 ,0; char k=s0; while (c=getchar()!=eof) k=move(k,c); if(k=e)
43、 printf(“Here is a error.n”); break; if(isFinalState(k, f_states) then printf (“yes!n”); else printf (“ no!n”); ,DFA識(shí)別程序(完整main()函數(shù)),#include stdio.h“ main() /設(shè)別程序主函數(shù) /聲明要調(diào)用的兩個(gè)函數(shù) char move(char state,char ch); bool isFinalState(char k,char *f); /定義DFA char states5=0,1, 2,3,4; char s0=0; char f_state
44、s3=2,4,0; /識(shí)別過程 char k=s0,c; while(c=getchar()!=n) k=move(k,c);/狀態(tài)轉(zhuǎn)換 if(k=e) printf(Here is a error.n); break; /判別設(shè)別結(jié)果 if(isFinalState(k,f_states) printf (yes!n); else printf ( no!n); ,DFA識(shí)別程序(模擬轉(zhuǎn)換函數(shù)),/DFA轉(zhuǎn)換的程序表示 char move(char state,char ch) char t=e; switch(state) case 0: if(ch=0,DFA識(shí)別程序(模擬轉(zhuǎn)換函數(shù)),c
45、ase 2: if(ch=0,DFA識(shí)別程序(完整轉(zhuǎn)換函數(shù)),/DFA轉(zhuǎn)換的程序表示 char move(char state,char ch) char t=e; switch(state) case 0:if(ch=0 ,DFA識(shí)別程序(模擬判別終態(tài)函數(shù)),bool isFinalState(char k,char *f) for(int i=0;fi!=0;i+) if(k=fi) return true; return false; ,DFA識(shí)別程序(完整判別終態(tài)函數(shù)),/判別k是否為終止?fàn)顟B(tài) bool isFinalState(char k,char *f) for(int i=0;
46、fi!=0;i+) if(k=fi) return true; return false; ,模擬NFA,輸入 NFA N,x(eof), s0, F 輸出 若N接受x,回答“yes”,否則“no” 方法 用下邊的過程對(duì)x進(jìn)行識(shí)別。S是一個(gè)狀態(tài)的集合。 S = -閉包(s0); - 所有可能初態(tài)的集合 a = nextchar; while (a eof ) S =-閉包(move(S,a); - 所有下一狀態(tài)的集合 a = nextchar; if ( SF) then return “yes”; else return “no”;,DFA和NFA模擬的區(qū)別,三點(diǎn)區(qū)別: 模擬DFA模擬NFA
47、 1. 開始 初態(tài)(s)初態(tài)集(S) 2. 下一狀態(tài)轉(zhuǎn)移 下一狀態(tài) 下一狀態(tài)集 3. 結(jié)束 s is in F SF,例 在NFA上識(shí)別輸入序列abb和abab,識(shí)別abb: 1 計(jì)算初態(tài)集: -閉包(0)=0,1,2,4,7, A 2 從A出發(fā)經(jīng)a到達(dá):-閉包(move(A,a)=3,8,6,7,1,2,4,B 3 從B出發(fā)經(jīng)b到達(dá):-閉包(move(B,b)=5,9,6,7,1,2,4,C 4 從C出發(fā)經(jīng)b到達(dá):-閉包(move(C,b)=5,10,6,7,1,2,4,D 5 結(jié)束且D10=10,接受。識(shí)別的路徑為:A a B b C b D,識(shí)別abab: 初態(tài)集: -閉包(s0)=0,
48、1,2,4,7 A 從A出發(fā)經(jīng)a到達(dá):-閉包(move(A,a) = 3,8,6,7,1,2,4 B 從B出發(fā)經(jīng)b到達(dá):-閉包(move(B,b) = 5,9,6,7,1,2,4 C 從C出發(fā)經(jīng)a到達(dá):-閉包(move(C,a) = 3,8,6,7,1,2,4 B 從B出發(fā)經(jīng)b到達(dá):-閉包(move(B, b) = 5,9,6,7,1,2,4 C 識(shí)別路徑為:A a B b C a B b C。由于C10=,所以不接受,DFA在計(jì)算機(jī)中的表示,矩陣表示: T: 2 2 2 0 0 3 0 0 4 0 0 0 S4=0,1,2,3,4 l3=+,-,d T0,0=2 Ts0,l0=2 T0,+=
49、2,1,2,3,4,DFA在計(jì)算機(jī)中的表示,表結(jié)構(gòu): Struct state String stateName; int outNum; trans toutNum Struct trans char inputChar; state *f; ,總結(jié),本章講述了詞法分析程序設(shè)計(jì)原則,并介紹了分別作為正規(guī)集的描述機(jī)制和識(shí)別機(jī)制的正規(guī)式和有窮動(dòng)機(jī)。 在此基礎(chǔ)上給出了詞法分析程序自動(dòng)構(gòu)造工具的原理。,習(xí)題三,3.1 (1)S aSb|ab (3)(0|1)*1 (4)(b| )(ab)*(a| ),(5)(0|1)*(11|00)*,(6)(d| )d*( |E),習(xí)題三,3.2,_closure
50、(X)=X=s0(初始) 標(biāo)記s0: _closure(move(s0,0)=_closure (2)=2=s1 _closure(move(s0,1)= 標(biāo)記s1: _closure(move(s1,0)= _closure(move(s1,1)= _closure (0)=0,4,1,6,5=s2,標(biāo)記s2: _closure(move(s2,0)= _closure (3,8,10)=3,8,10=s3 _closure(move(s2,1)= _closure (7,9)=7,9=s4 標(biāo)記s3: _closure(move(s3,0)= _closure (4)=4,1,6,5=s5
51、 _closure(move(s3,1)= _closure (Y,6)=Y,6,5=s6(終止) 標(biāo)記s4: _closure(move(s4,0)= _closure (6)=6,5=s7 _closure(move(s4,1)= _closure (4)= s5,標(biāo)記s5: _closure(move(s5,0)= _closure (3,8,10)=s3 _closure(move(s5,1)= _closure (7,9)=s4 標(biāo)記s6: _closure(move(s6,0)= _closure (8,10)=8,10=s8 _closure(move(s6,1)= _closu
52、re (7,9)=s4 標(biāo)記s7: _closure(move(s7,0)= _closure (8,10)=s8 _closure(move(s7,1)= _closure (7,9)=s4,標(biāo)記s8: _closure(move(s8,0)= _closure (4)=s5 _closure(move(s8,1)= _closure (6)=s7,s0(初始) move(s0,0)=s1 move(s0,1)= move(s1,0)= move(s1,1)= s2 move(s2,0)= s3 move(s2,1)= s4 move(s3,0)= s5 move(s3,1)= s6(終止)
53、 move(s4,0)= s7 move(s4,1)= s5 move(s5,0)= s3 move(s5,1)= s4 move(s6,0)= s8 move(s6,1)= s4 move(s7,0)= s8 move(s7,1)= s4 move(s8,0)= s5 move(s8,1)= s7,習(xí)題三,3.3 初始狀態(tài):-closure(0)=0=s1 標(biāo)記s1: -closure(move(s1,a)=1,3=s2 -closure(move(s1,b)= 標(biāo)記s2: -closure(move(s2,a)=1,3=s2 -closure(move(s2,b)=2,4,6,5=s3 標(biāo)記s3(終止?fàn)顟B(tài)): -closure(move(s3,a)=4,6,5=s4 -closure(move(s3,b)=6,5,4=s4 標(biāo)記s4 (終止?fàn)顟B(tài)): -closure(move(s4,a)=6,5,4=s4 -closure(move(s4,b)=6,5,4=s4,習(xí)題三,習(xí)題三,3.4 確定化(子集法) 初始狀態(tài):-closure(0)=0=s1 標(biāo)記s1: -closure(move(s1,x)=1=s2 -closure(move(s1,y)=2=s3
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 店面形象規(guī)范管理辦法
- 工程全面預(yù)算管理辦法
- 外地常駐員工管理辦法
- 維修費(fèi)用控制管理辦法
- 私人扶貧基金管理辦法
- 育嬰師職業(yè)簡介課件模板
- 消防培訓(xùn)師課件
- 2025年滌綸高彈絲項(xiàng)目提案報(bào)告
- 腸道健康養(yǎng)生課件
- 腸癌術(shù)后護(hù)理
- 國有企業(yè)集中采購管理模式改進(jìn)研究
- 《小學(xué)生網(wǎng)絡(luò)安全教育》課件
- 【中學(xué)】【主題班會(huì)】護(hù)紅色根脈 圓復(fù)興夢想
- 2025-2030中國共享按摩椅行業(yè)市場深度調(diào)研及投資前景與投資策略研究報(bào)告
- 自然照護(hù)理念體位管理
- 二次供水試題及答案
- 耐高溫有機(jī)硅樹脂合成及改性技術(shù)
- 國家開放大學(xué)漢語言文學(xué)本科《中國現(xiàn)代文學(xué)專題》期末紙質(zhì)考試第三大題分析題庫2025春期版
- 全國職業(yè)院校技能大賽高職組(生產(chǎn)事故應(yīng)急救援賽項(xiàng))選拔賽考試題庫500題(含答案)
- DBJ50-T-098-2019 城市綠化養(yǎng)護(hù)質(zhì)量標(biāo)準(zhǔn)
- 陜西省榆林市神木市2024-2025學(xué)年八年級(jí)上學(xué)期1月期末道德與法治試題(含答案)
評(píng)論
0/150
提交評(píng)論