第3章 詞法分析

第３章詞法分析

任務(wù)：從左至右逐個(gè)字符地對源程序進(jìn)行掃 描，產(chǎn)生一個(gè)個(gè)的單詞符號，把作為 字符串的源程序改造成為單詞符號串。內(nèi)容簡介§3.1對于詞法分析器的要求

一．功能和輸出形式二．接口設(shè)計(jì)§3.2詞法分析器的設(shè)計(jì)

一．輸入和預(yù)處理二．單詞符號的識別三．狀態(tài)轉(zhuǎn)換圖及其實(shí)現(xiàn)§3.3正規(guī)表達(dá)式與有限自動機(jī)

一．單詞符號的描述

1.正規(guī)式與正規(guī)集2.正規(guī)文法二．有限自動機(jī)

1.DFA2.NFA

3.NFA與DFA的等價(jià)4.DFA的化簡

三．正規(guī)式與有限自動機(jī)的等價(jià)性四．正規(guī)文法與有限自動機(jī)的等價(jià)性§3.4詞法分析器的自動產(chǎn)生（LEX）2§３.１對于詞法分析器的要求一、功能和輸出形式１、功能：輸入源程序，輸出單詞符號２、單詞符號的分類（１）關(guān)鍵字：由程序語言定義的具有固定意義的標(biāo)識符，也稱為保留字或基本字。例如：Pascal語言中的begin，end，if，while等。（２）標(biāo)識符：用來表示各種名字。 例如變量名、數(shù)組名、過程名等。（３）常數(shù)：整型、實(shí)型、布爾型、文字型等 例如：100，3.14159，true，‘sample’（４）運(yùn)算符：+、-、*、/（５）界符：，；（）等3３、輸出的單詞符號形式 二元式：（單詞種別，單詞符號的屬性值）§３.１對于詞法分析器的要求單詞符號的編碼：標(biāo)識符：一般統(tǒng)歸為一種常數(shù)：常按整型、實(shí)型、布爾型等分類關(guān)鍵字：全體視為一種／一字一種運(yùn)算符：一符一種界符：一符一種通常用“整數(shù)編碼”“單詞符號的特征或特性”4例：考慮下述Ｃ++代碼段：while(i>=j)i--;§３.１對于詞法分析器的要求經(jīng)詞法分析器處理后，它將被轉(zhuǎn)換為如下的單詞符號序列：

<while,-><(,-><id,指向i的符號表項(xiàng)的指針><>=,->

<

id,指向j的符號表項(xiàng)的指針><),-><id,指向i的符號表項(xiàng)的指針><--,-><;,->5§３.１對于詞法分析器的要求二、接口設(shè)計(jì)１、詞法分析器作為獨(dú)立的一遍

２、詞法分析器作為一個(gè)獨(dú)立的子程序，但并不一定作為獨(dú)立的一遍

語法分析器詞法分析器調(diào)用（取下一個(gè)單詞）單詞優(yōu)點(diǎn)：使整個(gè)編譯程序的結(jié)構(gòu)更簡潔、清晰和條理化。

詞法分析 字符流 單詞序列（源程序） （輸出在一個(gè)中間文件上）6１、預(yù)處理：剔掉空白符、跳格符、回車符、換行符、注解部分等.一、輸入、預(yù)處理§３.２詞法分析器的設(shè)計(jì)

原因：

編輯性字符除了出現(xiàn)在文字常數(shù)中之外，在別處的任何出現(xiàn)都無意義.

注解部分不是程序的必要組成部分，它的作用僅在于改善程序的易讀性和易理解性.

7

每當(dāng)詞法分析器調(diào)用時(shí)，就處理出一串確定長度（如120個(gè)字符）的輸入字符，并將其裝進(jìn)詞法分析器所確定的掃描緩沖區(qū)中。２、預(yù)處理子程序§３.２詞法分析器的設(shè)計(jì)8

起點(diǎn)指示器搜索指示器掃描緩沖區(qū)的兩個(gè)指示器：一個(gè)指向當(dāng)前正在識別的單詞的開始位置（即新 單詞的首字符）

起點(diǎn)指示器一個(gè)用于向前搜索以尋找單詞的終點(diǎn)

搜索指示器

圖_源程序輸入緩沖區(qū)的對半互補(bǔ)結(jié)構(gòu)§３.２詞法分析器的設(shè)計(jì)9二.單詞符號的識別——超前搜索

1．關(guān)鍵字的識別2．標(biāo)識符的識別

3．常數(shù)的識別4．算符和界符的識別§３.２詞法分析器的設(shè)計(jì)10三、狀態(tài)轉(zhuǎn)換圖及其實(shí)現(xiàn)1、狀態(tài)轉(zhuǎn)換圖及其示例

§３.２詞法分析器的設(shè)計(jì)例:012

數(shù)字?jǐn)?shù)字 其它*012

字母或數(shù)字字母 其它*11例:(課本42頁表3.1;43頁圖3.3)§３.２詞法分析器的設(shè)計(jì)122、狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)實(shí)現(xiàn)方法：用程序?qū)崿F(xiàn)，讓每個(gè)狀態(tài)結(jié)點(diǎn)對應(yīng)一小段程序。A、變量和過程說明ch 字符變量，存放最新讀進(jìn)的源程序字符。strToken 字符數(shù)組，存放構(gòu)成單詞符號的字符串。GetChar 子程序過程，將下一輸入字符讀到ch中，搜索指示器前移一字符位置。④

GetBC 子程序過程，檢查ch中的字符是否為空白。若是，則調(diào)用GetChar直至ch中進(jìn)入一個(gè)非空白字符。⑤Concat 子程序過程，將ch中的字符連接到strToken之后?！欤?２詞法分析器的設(shè)計(jì)13IsLetter和IsDigit 布爾函數(shù)過程，它們分別判斷ch中的字符是否為字母和數(shù)字。Reserve 整型函數(shù)過程，對strToken中的字符串查找保留字表，若它是一個(gè)保留字則返回它的編碼，否則返回0值（假定0不是保留字的編碼）。Retract子程序過程，將搜索指示器回調(diào)一個(gè)字符位置，將ch置為空白字符。InsertId 整型函數(shù)過程，將strToken中的標(biāo)識符插入符號表，返回符號表指針。InsertConst整型函數(shù)過程，將strToken中的常數(shù)插入常數(shù)表，返回常數(shù)表指針?！欤?２詞法分析器的設(shè)計(jì)14B、示例圖中結(jié)點(diǎn)i所對應(yīng)的程序段可表示為：GetChar（）;if(IsLetter()){…狀態(tài)j的對應(yīng)程序段…；}elseif(IsDigit()){…狀態(tài)k的對應(yīng)程序段…；}elseif(ch=‘/’){…狀態(tài)l的對應(yīng)程序段…；}else{…錯(cuò)誤處理…;}圖中結(jié)點(diǎn)i所對應(yīng)的程序段可表示為：GetChar（）;while(IsLetter()orIsDigit())GetChar();…狀態(tài)j的對應(yīng)程序段…lkji字母數(shù)字/ji字母或數(shù)字

其它§３.２詞法分析器的設(shè)計(jì)15C、例

課本43頁圖3.3；45--46頁§３.２詞法分析器的設(shè)計(jì)16§３.３正規(guī)表達(dá)式與有限自動機(jī)一、正規(guī)式，正規(guī)集，正規(guī)文法二、確定有限自動機(jī)（DFA)三、非確定有限自動機(jī)(NFA)四、NFA=>DFA=>化簡五、正規(guī)式有限自動機(jī)六、左線性正規(guī)文法有限自動機(jī)右線性正規(guī)文法有限自動機(jī)17§３.３正規(guī)表達(dá)式與有限自動機(jī)一、正規(guī)式與正規(guī)集１、遞歸定義正規(guī)式ε，Φa(a∈∑）若U，V是正規(guī)式

U.V,U|V,U*

正規(guī)集{ε}，Φ{a}L(U)，L(V)

L(U)L(V),L(U)∪L(V),(L(U))*

18§３.３正規(guī)表達(dá)式與有限自動機(jī)例題：Ａ、令∑＝｛ａ，ｂ｝，下面是∑上的正規(guī)式和相應(yīng)的正規(guī)集正規(guī)式

ba* a(a|b)*

(a|b)*(aa|bb)(a|b)*正規(guī)集∑上所有以b為首后跟任意多個(gè)a的字∑上所有以a為首的字∑上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b的字19§３.３正規(guī)表達(dá)式與有限自動機(jī)正規(guī)式

(A|B)(A|B|0|1)*(0|1)(0|1)*Ｂ、令∑＝｛Ａ，Ｂ，０，１｝，則：一個(gè)正規(guī)式的正規(guī)集與之完全等價(jià)，只是表達(dá)形式不同。正規(guī)集∑上的“標(biāo)識符”的全體∑上的“數(shù)”的全體20§３.３正規(guī)表達(dá)式與有限自動機(jī)２、運(yùn)算

“｜”（或）：表示從各選擇對象中選擇“?”（連接積）：表示“連接”起來“*”（閉包）：任意有限次的自重復(fù)連接注：S*=∪Sn={ε}∪S∪SS∪……L(r*)=L(r)*優(yōu)先級：*>

?

>”|”∞n=021§３.３正規(guī)表達(dá)式與有限自動機(jī)例題：Ａ、L(r|s)

L(rs)L((a|b)c)B、L((a|b)*)={ε,a,b,aa,ab,ba,bb,…}

L(a|(b*))={ε,a,b,bb,bbb,…}C、a|bc*——a|(b(c*))ab|c*d——(ab)|((c*)d)=L(r)∪L(s)={r}∪{s}={r,s}=L(r)L(s)={r}{s}={rs}=L(a|b)L(c)={a,b}{c}={ac,bc}223、等價(jià)：若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn) 為二者等價(jià)。 兩個(gè)等價(jià)的正規(guī)式Ｕ和Ｖ，記為Ｕ＝Ｖ§３.３正規(guī)表達(dá)式與有限自動機(jī)例：b(ab)*=(ba)*b(a|b)*=(a*b*)*(a*b*)*=(a|b)*L(a*b*)*=[(L(a))*

(L(b))*]*={ε,a,b,aa,bb,........}*={ε,a,b,ab,...}L(a|b)*={a,b}*={ε,a,b,ab,…}

23４、令Ｕ、Ｖ、Ｗ均為正規(guī)式，則：Ｕ｜Ｖ＝Ｖ｜Ｕ （交換律）Ｕ｜（Ｖ｜Ｗ）＝（Ｕ｜Ｖ）｜Ｗ （結(jié)合律）Ｕ（ＶＷ）＝（ＵＶ）Ｗ （結(jié)合律）

U（V|W）=UV|UW （分配律）（V|W）U=VU|WU

εU=Uε

=UU*=(U|ε)* (U*)*=U*§３.３正規(guī)表達(dá)式與有限自動機(jī)24例題：Ａ、已知字母表∑={a，b，c}，試求在該字母表上的僅包括一個(gè)b的所有串的集合相對應(yīng)的正規(guī)式 §３.３正規(guī)表達(dá)式與有限自動機(jī)B、已知字母表∑={a，b，c}，若集合是包括了最多一個(gè)b的所有串，求其相應(yīng)的正規(guī)式 (a|c)*b(a|c)*(a|c)*(b|ε)(a|c)*25§３.３正規(guī)表達(dá)式與有限自動機(jī)二、確定有限自動機(jī)DFA（DeterministicFiniteAutomata）1、DFAM是一個(gè)五元式

M=（S，∑，δ，s0，F(xiàn)）其中：S——有限集，其中的每個(gè)元素稱為一個(gè)狀態(tài)∑——有窮字母表，其中的每個(gè)元素稱為一個(gè)輸入字符δ：S×∑S

（即?狀態(tài)s∈S，a∈∑，δ(s,a)唯一的確定下一狀態(tài)）

δ(s,a)=s’:當(dāng)現(xiàn)行狀態(tài)為s，輸入字符為a時(shí)，將轉(zhuǎn)換到下一狀態(tài)s’

s0∈S，唯一的初態(tài)F?S，是一個(gè)終態(tài)集（可空）

s的一個(gè)后繼狀態(tài)26§３.３正規(guī)表達(dá)式與有限自動機(jī)2、DFA的兩種表達(dá)方式（1）狀態(tài)轉(zhuǎn)換矩陣?yán)篋FAM=（{0，1，2，3}，{a，b}，δ，0，{3}）其中δ為： δ（0，a）=1 δ（0，b）=2 δ（1，a）=3 δ（1，b）=2 δ（2，a）=1 δ（2，b）=3 δ（3，a）=3 δ（3，b）=327則其狀態(tài)轉(zhuǎn)換矩陣為：狀態(tài)ab012132213333§３.３正規(guī)表達(dá)式與有限自動機(jī)δ（0，a）=1δ（0，b）=2δ（1，a）=3δ（1，b）=2δ（2，a）=1δ（2，b）=3δ（3，a）=3δ（3，b）=328（2）狀態(tài)轉(zhuǎn)換圖§３.３正規(guī)表達(dá)式與有限自動機(jī)DFAM:

m個(gè)狀態(tài)：圖中有

個(gè)狀態(tài)結(jié)點(diǎn); n個(gè)輸入符號：每個(gè)結(jié)點(diǎn)頂多有

條箭弧射出;

每條箭弧用∑中的一個(gè)

（相同/不同)

輸入字符作標(biāo)記;

整張圖含有

個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè) （可為0）終態(tài)結(jié)點(diǎn).

0132

a a baa，ｂ

b b29例題：構(gòu)造一個(gè)DFAM，它接受字母表{a，b，c}上以a或b開始的字符串，或者以c開始但所含的a不多于一個(gè)的字符串。

§３.３正規(guī)表達(dá)式與有限自動機(jī)30§３.３正規(guī)表達(dá)式與有限自動機(jī)3、識別（讀出/接受）

對于任何∑*中的任何字α，若存在一條從初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記符連接成的字等于α，則稱α可為DFAM所識別（接受/讀出）。若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則空字ε可為M所識別/接受。DFAM所能識別的字的全體記為L（M）。若一個(gè)DFAM的輸入字母表為∑，則稱M是∑上的一個(gè)DFA。31ａａｂｂａａａａｂａａｂａｂａｂａｂａ0132

a a baa，ｂ

b b32§３.３正規(guī)表達(dá)式與有限自動機(jī)4、定理

∑上的一個(gè)字集V?∑*是正規(guī)的，當(dāng)且僅當(dāng)存在∑上的DFAM，使得V=L（M）33§３.３正規(guī)表達(dá)式與有限自動機(jī)三、非確定有限自動機(jī)（NFA）1、一個(gè)NFA是一個(gè)五元式

M=（S，∑，δ，S0，F(xiàn)）其中：S——有限集，其中每個(gè)元素稱為一個(gè)狀態(tài)∑——有窮字母表，其中的每個(gè)元素稱為一個(gè)輸入字符δ：S×∑*2S

S的子集

字S0?S，是一個(gè)非空初態(tài)集F?S，是一個(gè)終態(tài)集（可空）34§３.３正規(guī)表達(dá)式與有限自動機(jī)三、非確定有限自動機(jī)（NFA）DFANFAS∑δ初態(tài)終態(tài)F有限狀態(tài)集字母表S×∑S初態(tài)唯一可為空

同左同左S×∑*2S初態(tài)不一定唯一同左35§３.３正規(guī)表達(dá)式與有限自動機(jī)2、狀態(tài)轉(zhuǎn)換圖注：含有m個(gè)狀態(tài)和n個(gè)輸入符號（1）整張圖含有

個(gè)狀態(tài)結(jié)點(diǎn)。（2）每個(gè)結(jié)點(diǎn)可以射出

條弧，每條弧用

作為輸入字，箭弧上的標(biāo)記

（允許/不允許）相同。（3）整張圖

至少含有一個(gè)初態(tài)結(jié)點(diǎn)以及

若干個(gè)（可為0個(gè)）終態(tài)結(jié)點(diǎn)。（4）某些結(jié)點(diǎn)既可為初態(tài)結(jié)點(diǎn)也可為終態(tài)結(jié)點(diǎn)。∑*中一個(gè)字（可以是空字ε）允許36m若干例：q0q111000DFA?NFA?37§３.３正規(guī)表達(dá)式與有限自動機(jī)3、識別（讀出/接受）

對于∑*中的任何一個(gè)α，若存在一條從某一初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記字依序連接成的字（忽略那些標(biāo)記為ε的?。┑扔讦?，則稱α可為NFAM所識別（讀出/接受）。若M的某些結(jié)點(diǎn)既是初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)，或者存在一條從某個(gè)初態(tài)結(jié)點(diǎn)到某個(gè)終態(tài)結(jié)點(diǎn)的ε通路，則空字

ε可為M所接受。38§３.３正規(guī)表達(dá)式與有限自動機(jī)4、定理對于每個(gè)NFAM，存在一個(gè)DFAM’，使得L（M）=L（M’）。即，假設(shè)L是一個(gè)NFA接受的正規(guī)集，則存在一個(gè)DFA也接受L。39§３.３正規(guī)表達(dá)式與有限自動機(jī)四、NFA=>DFA(確定化）=>化簡（最少化）401、ε_CLOSURE（I）：I中的每個(gè)狀態(tài)∈ε_CLOSURE（I）；若s∈ε_CLOSURE（I），則狀態(tài)s經(jīng)過標(biāo)記為ε的弧到達(dá)的狀態(tài)s’∈ε_CLOSURE（I）。ε_CLOSURE（{x}）={x,5,1}412、Ia=ε_CLOSURE（J）若s∈Is經(jīng)過1條標(biāo)記為a的弧到達(dá)的狀態(tài)s’∈JI={x,5,1}Ia={x,5,1}a=ε_CLOSURE({5,3})={5,3,1}Ib={x,5,1}b=ε_CLOSURE({5,4})={5,4,1}42IIaIb{X,5,1}ε_CLOSURE(初態(tài)）（一）NFA=>DFA{5,3,1}{5,4,1}{5,3,1}{5,4,1}{5,2,3,1,6,Y}{5,4,1}{5,2,3,1,6,Y}{5,3,1}{5,2,4,1,6,Y}{5,2,4,1,6,Y}{5,2,3,6,1,Y}{5,4,6,1,Y}{5,4,6,1,Y}{5,3,6,1,Y}{5,2,4,6,1,Y}{5,3,6,1,Y}{5,6,3,1,Y}{5,2,6,4,1,Y}{5,2,6,3,1,Y}{5,6,4,1,Y}§３.３正規(guī)表達(dá)式與有限自動機(jī)解：（1）構(gòu)造DFA的狀態(tài)轉(zhuǎn)換矩陣

（2）構(gòu)造重新命名后的狀態(tài)轉(zhuǎn)換矩陣DFAM’’ L(M’’)=L(M’)=L(M)Sab0121322143354645646354445（二）DFA的化簡狀態(tài)s和t等價(jià)：s和t到達(dá)終態(tài)能夠識別相同的字。

461、首先分為非終態(tài)集和終態(tài)集{0,1,2}和{3,4,5,6}2、分別對每個(gè)集合進(jìn)行試探：（1）{0,1,2}a={1,3,1}把集合分為{0,2}和{1}

{0,2}b={2,5}把集合劃分為{0}和{2}

把集合{0,1,2}劃分為{0}、{1}和{2}472、（1）{0}、{1}、{2}、{3,4,5,6}

（2）{3,4,5,6}a={3,6,6,3}

{3,4,5,6}b={4,5,5,4}

集合{3，4，5，6}不必再劃分。3、最終形成的劃分{0}{1}{2}{3,4,5,6}48{0}{1}{2}{3,4,5,6}用一個(gè)狀態(tài)代表一個(gè)狀態(tài)子集。0132abababa,b49§３.３正規(guī)表達(dá)式與有限自動機(jī)五、正規(guī)式有限自動機(jī)關(guān)系定理定理：

上的NFAM所能識別的語言L(M)可以用

上的正規(guī)式來表示。即：對

上的NFAM，可構(gòu)造一個(gè)正規(guī)式

，使得L(

)=L(M)。定理：

上任何正規(guī)式

，存在DFAM使得L(M)=L(

)。即：由正規(guī)式

可以構(gòu)造一個(gè)DFAM，使得L(M)＝L(

)。50§３.３正規(guī)表達(dá)式與有限自動機(jī)五、正規(guī)式有限自動機(jī)1、有限自動機(jī)=>正規(guī)式1)把狀態(tài)轉(zhuǎn)換圖的概念拓廣，令每條弧上都可以用一個(gè)正規(guī)式作標(biāo)記。2)在M的轉(zhuǎn)換圖上加兩個(gè)結(jié)點(diǎn)：x、y。從x用

弧連接到M的所有初態(tài)結(jié)點(diǎn)；從M的終態(tài)結(jié)點(diǎn)用

弧連接到y(tǒng)。這個(gè)新的NFA為M’，且L(M)=L(M’)。3)通過引入的3條有限自動機(jī)替換規(guī)則逐步消去M’中的所有結(jié)點(diǎn)，直到只剩下x和y為止。這樣，在x至y的弧線上的標(biāo)記就是

上的正規(guī)式，也就是M接受的正規(guī)式。51§３.３正規(guī)表達(dá)式與有限自動機(jī)五、正規(guī)式有限自動機(jī)1、有限自動機(jī)=>正規(guī)式替換規(guī)則:jiAB

jiA|B

jiA*A

Bjkijki? ?

A代之以代之以代之以jiAB52練習(xí)1：53練習(xí)1：練習(xí)2：55練習(xí)2：56§３.３正規(guī)表達(dá)式與有限自動機(jī)五、正規(guī)式有限自動機(jī)2、正規(guī)式=>有限自動機(jī)57證明過程如下：（1）若正規(guī)式有零個(gè)運(yùn)算符時(shí)：正規(guī)式，構(gòu)造NFA為：對應(yīng)正規(guī)式，構(gòu)造NFA為：對應(yīng)正規(guī)式a，構(gòu)造NFA為：

（2）假設(shè)正規(guī)式有k(k>=1)個(gè)運(yùn)算符時(shí)結(jié)論成立。（3）則正規(guī)式有k+1(k>=1)個(gè)運(yùn)算符時(shí)：xyxy

xya58

R=stR=s*xyN(s)

N(s)N(t)

xyN(s)N(t)

R=s|t59書上例子P5660轉(zhuǎn)換規(guī)則：

1)由正規(guī)式

構(gòu)造一個(gè)如下僅有兩個(gè)結(jié)點(diǎn)x，y的狀

態(tài)圖。

2)按所引入的3條正規(guī)式分裂規(guī)則分裂

。3)重復(fù)步驟2直到每個(gè)弧上的標(biāo)記是

上的一個(gè)字符或

為止。4)將所得的NFAM(因?yàn)榘?/p>

弧)進(jìn)行確定化就得到DFA。xy

61正規(guī)式分裂規(guī)則12

|

12

2

112

3112

*

2

3

62例、根據(jù)正規(guī)式(a|b)*(aa|bb)(a|b)*，構(gòu)造DFAM，使之等價(jià)。xy(a|b)*(aa|bb)(a|b)*1y(a|b)*(a|b)*

2x(aa|bb)1y

2xaa5

bba|b

6

a|b1y

2xa5

ba

6

abb34ab63練習(xí)1：L(R)=(a|b)*abb，構(gòu)造NFA使L(N)=L(R)

練習(xí)2：L(R)=a*b*abb，構(gòu)造NFA使L(N)=L(R)

64練習(xí)1：L(R)=(a|b)*abb，構(gòu)造NFA使L(N)=L(R)

解：xy

(a|b)*abbx

yabb

abx

yabb

a,b

x

y

ababb65x

(a|b)*abby練習(xí)2：L(R)=a*b*abb，構(gòu)造NFA使L(N)=L(R)

解：x

ybab

a

bx

a*b*abby661、右線性正規(guī)文法GR有限自動機(jī)2、左線性正規(guī)文法GL

有限自動機(jī)3、有限自動機(jī)

右線性正規(guī)文法GR4、有限自動機(jī)

左線性正規(guī)文法GL§３.３正規(guī)表達(dá)式與有限自動機(jī)六、正規(guī)文法有限自動機(jī)67

1、右線性正規(guī)文法GR

有限自動機(jī)§３.３正規(guī)表達(dá)式與有限自動機(jī)六、正規(guī)文法有限自動機(jī)引例：GR:S→aAA→bBB→cSABfabcδ(S,a)=Aδ(A,b)=Bδ(B,c)=f68

1、右線性正規(guī)文法GR有限自動機(jī)§３.３正規(guī)表達(dá)式與有限自動機(jī)六、正規(guī)文法有限自動機(jī)GR(VT,VN,S,P)P:A→aBB→bFA(∑,S,δ,S0,F)字母表∑：VT狀態(tài)集S：VN

∪{f}S0：開始符號S對應(yīng)的狀態(tài)F：{f}δ：δ(A,a)=Bδ(B,b)=f69

GR:A→0|0B|1DB→0D|1CC→0|0B|1DD→0D|1D702、左線性正規(guī)文法GL

有限自動機(jī)§３.３正規(guī)表達(dá)式與有限自動機(jī)六、正規(guī)文法有限自動機(jī)引例：GL:S→AcA→BbB→aSABfcbaδ(A,c)=Sδ(B,b)=Aδ(q0,a)=Bq0S71

§３.３正規(guī)表達(dá)式與有限自動機(jī)六、正規(guī)文法有限自動機(jī)GL(VT,VN,S,P)P:A→BaB→bFA(∑,S,δ,S0,F)字母表∑：VT狀態(tài)集S：VN

∪{q0}S0：q0F：開始符號S對應(yīng)的狀態(tài)δ：δ(B,a)=Aδ(

q0,b)=B722、左線性正規(guī)文法GL

有限自動機(jī)

GL:f→0|C0B→0|C0C→B1D→1|C1|D0|D1|B0733、有限自動機(jī)

右線性正規(guī)文法GR§３.３正規(guī)表達(dá)式與有限自動機(jī)六、正規(guī)文法有限自動機(jī)引例1：SABCabc引例2：SABCabcd74

3、有限自動機(jī)

右線性正規(guī)文法GR§３.３正規(guī)表達(dá)式與有限自動機(jī)六、正規(guī)文法有限自動機(jī)引例1：SABCabc

GR:S→aAA→bBB→cCC→ε75

3、有限自動機(jī)

右線性正規(guī)文法GR§３.３正規(guī)表達(dá)式與有限自動機(jī)六、正規(guī)文法有限自動機(jī)

GR:S→aAA→bBB→cC

C→dB|ε引例2：SABCabcd76

規(guī)則：3、有限自動機(jī)

右線性正規(guī)文法GRFA(∑,S,δ,s0,F)δ(A,a)=BGR(VT,VN,S,P)VT：

∑VN：狀態(tài)集S對應(yīng)的符號集S：初態(tài)s0對應(yīng)的符號P：A→aB當(dāng)C是終態(tài)時(shí)，增加：C→ε77

ABDabaabbbC

GR:A→aB|bDB→bCC→aA|bDD→aB|bD|ε784、有限自動機(jī)

左線性正規(guī)文法GL§３.３正