張素文-第6章句法模式識別

1、第第6 6章章 句法模式識別句法模式識別6.1 句法模式識別概述句法模式識別概述6.2 形式語言的基本概念形式語言的基本概念6.3 模式的描述方法模式的描述方法6.4 文法推斷文法推斷6.5 句法分析句法分析6.6 句法結(jié)構(gòu)的自動機識別句法結(jié)構(gòu)的自動機識別第第6章章 句法模式識別句法模式識別6.1 句法模式識別概述句法模式識別概述模式用句子形式描述，結(jié)構(gòu)信息十分重要。 模式子模式基元句子詞組單詞組合關(guān)系自然語言的文法 句法模式識別用小而簡單的基元與語法規(guī)則描述和識別大而復(fù)雜的模式，通過對基元的識別，進而識別子模式，最終識別復(fù)雜模式。 符合某個文法的所有句子的集合一個模式類（b）墻壁 f地板 g

2、EDBbadce（c）圖6.1 景物結(jié)構(gòu)描述與英文句子句法描述的對比句法模式識別系統(tǒng)的組成： 句法模式識別的理論基礎(chǔ)：形式語言 20世紀50年代中期喬姆斯基（Chomsky）。 * 基元選擇尚無通用的方法；* 文法推斷理論遠不及統(tǒng)計學(xué)習(xí)發(fā)展得成熟。 句法模式識別存在的主要問題：6.2 形式語言的基本概念形式語言的基本概念6.2.1 基本定義基本定義1字母表與問題有關(guān)的符號的有限集合，用V或表示。 2句子 由字母表中符號組成的有限長度的符號串，又稱鏈?？站溆帽硎?。 組成：英文小寫字母、數(shù)字。例：由 中元素可組成句子： ,cbaV ,1ZCBAV2, 1, 03V例：abc，aacc，重寫次數(shù)句子

3、的長度：句子包含符號的數(shù)目，用|表示。9|333cba3語言由字母表中的符號根據(jù)某種文法組成的句子的集合。 V *：V中符號組成的所有句子的集合，包括空句；V +：不包含空句的句子集合。 *VV,*aabbccabV,aabbccabV例：4文法構(gòu)成一種語言的句子所必須遵守的規(guī)則。 ),(SPVVGTNVN ：非終止符的有限集，子模式的集合，大寫字母表示。 VT ：終止符有限集，基元的集合，字母表起始部分的小寫 字母表示 。終止符和非終止符組成的混合字符串：用英文字母表尾部的小寫字母x，y，v，w等表示。終止符組成的字符串：用希臘字母，等表示。性質(zhì)： VVVTNTNVV（字母表）（空集）P：生

4、成式的有限集。用文法產(chǎn)生句子時的重寫規(guī)則。：P字符串 字符串 替換 S：起始符，代表模式本身，特殊的非終止符。用生成式構(gòu)成句子時，必須由左邊是S的生成式開始。 一種語言有一種文法，由文法G構(gòu)成的語言用L(G)表示： ,|)(*xSVxxGLGT且文法G構(gòu)成的句子由終止符組成VT中字符組成的所有句子的集合 文法G的推導(dǎo)關(guān)系 aabccaaBccaaAccaAcS 利用文法構(gòu)成句子時，除第一個生成式必須利用左邊為起始符 S 的生成式外，其余生成式使用的先后次序及重復(fù)使用的次數(shù)都不受限制。是說明：解：6.2.2 文法分類文法分類四種類型：0型文法、1型文法、2型文法和3型文法。10型文法：型文法：無

5、約束文法。P：其中， ， 。V*V21型文法：型文法：上下文有關(guān)文法 。含意： 32型文法：型文法：上下文無關(guān)文法 。解：每個生成式的左邊都是單變量，右邊是非空字符串， 故G是上下文無關(guān)文法。 屬于L(G)的句子： 結(jié)果不唯一。 43型文法：型文法：正則文法、有限態(tài)文法。 是 后一種文法的限制比前一種文法的限制嚴格；限制愈多的文法愈容易推斷；句法模式識別中多采用上下文無關(guān)文法和正則文法。6.3 模式的描述方法模式的描述方法6.3.1 基元的確定基元的確定根據(jù)結(jié)構(gòu)特征對模式進行描述。 結(jié)構(gòu)描述法，又稱句法表示法。 模式的表示：鏈表示法、樹表示法、圖表示法。 對應(yīng)的文法：鏈文法（串文法）、樹文法、

6、圖文法。 還有網(wǎng)文法、陣列文法等。 目前關(guān)于基元的確定沒有一個通用的解決辦法?；倪x擇遵循兩個基本原則。 1基元應(yīng)是模式的基本單元，能夠通過一定的結(jié)構(gòu)關(guān)系對數(shù) 據(jù)進行緊湊、方便地描述。2基元應(yīng)該容易用現(xiàn)有的非句法方法進行提取或識別。例如：語音識別中 音素； 識別手寫文字 筆劃。6.3.2 模式的鏈表示法模式的鏈表示法1鏈碼法鏈碼法鏈碼：用不同斜率的直線段或曲線段為基元表示圖形模式。弗利曼鏈碼： 以八個基本方向的有向線段為基元，用07八個數(shù)字符號表示。 用字符表示基元后，被描述的圖形表示成的字符串。 弗利曼鏈碼基元 數(shù)字“2”的折線化和量化結(jié)果編碼： 矩形網(wǎng)格覆蓋； 折線化和量化；形成鏈碼(有

7、序結(jié)構(gòu))。例：“2”的鏈碼表示為1075456000 x2圖形描述語言法圖形描述語言法簡稱PDL（Picture Description Language，PDL）。 基本基元：有向線段(直線段、弧線段) 。由 “頭(箭頭端)” 和 “尾” 構(gòu)成。關(guān)系基元：表示基元之間連接關(guān)系的算子。頭尾相接 頭頭相接 尾尾相接 頭頭 且尾尾相接頭尾顛倒 （）組合關(guān)系(配合使用)例：用PDL法表示大寫英文字母A。(a+b)(a+b)*c)(a+b)*c)+b)(a+(a+b)*c)+b)鏈表示法：只能從左邊或右邊與其它符號相連，一維連接方式。 6.3.3 模式的樹表示法模式的樹表示法高維表示法。 1樹的定義樹

8、的定義樹T是一個或一個以上結(jié)點的有限集合，并且滿足：1）存在一個唯一的指定為根的結(jié)點；2）其余結(jié)點分為m個不相交的集合T1，T2，Tm，其中 每一個集合本身都是一個樹，稱為T的子樹。同一層上各子樹交換位置構(gòu)成的樹不同。樹的有序性：一個結(jié)點具有子樹的個數(shù)，結(jié)點a的秩記為 r(a) 。葉結(jié)點的秩為零。 秩：長方體 基元 樹結(jié)構(gòu)描述 結(jié)點a的秩可能是2，l或0。0, 1, 2)(ar例：結(jié)點a可能有2，1或0個分枝樹文法定義為四元式),(SPrVGt2樹文法樹文法字母表 以字母表中字母為根結(jié)點的樹的秩 起始樹的有限集 VTS 生成式的有限集由樹文法Gt產(chǎn)生的語言L(Gt)是一些樹的集合即模式集： ,

9、|)(*STTTTTTGLitGiTt所有結(jié)點都是終止符的樹的集合樹T由S中的起始樹Ti開始，用文法Gt的生成式逐步導(dǎo)出圖6.7 模式的樹狀表示解：生成式 中右邊的樹分別用T1，T2 ，T3表示。有 TTTTSAtGAtGStG321)(tGLT 試判斷圖6.7所示的樹是否屬于L(Gt)的一個句子。3擴展樹文法擴展樹文法其中，P中生成式 形式：),(SPrVGt一個樹文法有一個對應(yīng)的擴展樹文法。例6.6 構(gòu)成例6.5中樹文法對應(yīng)的擴展樹文法。6.4 文法推斷文法推斷6.4.1 基本概念基本概念文法推斷：用已知類別的模式樣本集訓(xùn)練類別文法的過程。統(tǒng)計模式識別訓(xùn)練判別函數(shù) 句法模式識別訓(xùn)練類別文法

10、 目的：構(gòu)造出能正確描述某類模式的文法，其中主要是求 生成式集合P。 * 選擇文法形式（鏈文法、樹文法、圖文法）。 * 根據(jù)樣本進行推斷文法。 基本步驟：1語言語言L(G)的正樣本集和負樣本集的正樣本集和負樣本集2文法推斷的基本思路文法推斷的基本思路根據(jù)樣本集RR+，R-推導(dǎo)出文法G，簡化時只有R+ 。* 給定一個R+型的訓(xùn)練樣本集，共n個句子，陸續(xù)送入 一個 “文法推斷機”。* 輸入一個句子，由此初步推斷出一個能導(dǎo)生出該句子 的文法G1。* 輸入第二個句子，補充或修改G1，從而推斷出能導(dǎo)生 出這兩個句子的文法G2。* 推斷出文法Gn。* 將Gn中各條文做合并處理。* 先推斷出幾種不同的文法，

11、然后再選擇一種。簡化文法的方法：6.4.2 余碼文法的推斷余碼文法的推斷1余碼的定義余碼的定義2余碼文法的推斷余碼文法的推斷余碼文法又稱形式微商文法。 6.4.3 擴展樹文法的推斷擴展樹文法的推斷BA 第三步：合并等價非終止符，刪除被合并的非終止符的所有后代生成式。例6.8 設(shè)某類句法模式樹描述的樣本集中含有樹T1和T2： 解：第一步：分別寫出產(chǎn)生樹T1和T2的生成式。產(chǎn)生樹T1的生成式：增加一個，得到產(chǎn)生樹T2的生成式： 6.5 句法分析句法分析6.5.1 參考鏈匹配法參考鏈匹配法利用文法對未知類別的句法模式進行識別或分類的過程。句法分析：* 對每一類模式給出一組樣本鏈(參考鏈)。 設(shè)有M類

12、模式。* 將輸入鏈x與每一類的參考鏈進行比較，并規(guī)定一個比較容 限。 x被識別為與其匹配“最好”的參考鏈所屬的模式類。 6.5.2 填充樹圖法填充樹圖法用于上下文無關(guān)文法的分析。 若已知某語言的文法Gi，給定某待識別的鏈x，建立一個以x為底，以起始符S為頂?shù)娜切?，如圖6.8所示。 用文法Gi的生成式填充這個三角形，使之成為一個分析樹。若填充成功，表示x可以由文法Gi導(dǎo)出， 圖6.8 待填充的三角形 填充三角形的方法： 頂下法 底上法 )(GLx解：填充三角形成功， 圖6.9 用文法G的生成式填充的三角形6.5.3 CYK分析法分析法庫克(Cocke) -楊格(Younger) -卡塞米(Ka

13、sami)分析法用于上下文無關(guān)文法的分析1喬姆斯基范式喬姆斯基范式 要求：生成式必須表示為喬姆斯基范式。 BCA aA 或其中A，B，C為非終止符，a為終止符。 例如，喬姆斯基范式為2CYK分析法分析法輸入：喬姆斯基范式的上下文無關(guān)文法G、輸入鏈x；輸出：關(guān)于鏈x的分析表。關(guān)鍵：構(gòu)造x的分析表 方法：步驟： 第五步：停機，填表結(jié)束。 6.5.4 厄利分析法厄利分析法一種有效的上下文無關(guān)文法的分析算法。 圓點：分割開經(jīng)分析后符合的部分和尚未考慮的部分。 思路： 步驟： 反復(fù)執(zhí)行2和3，到?jīng)]有新項目加入I0為止。反復(fù)執(zhí)行5和6，到?jīng)]有項目加到Ij中為止。解： 6.6 句法結(jié)構(gòu)的自動機識別句法結(jié)構(gòu)的

14、自動機識別自動機：句法模式識別器。識別輸入鏈是否符合與該機相對應(yīng)的文法。 0型文法圖靈機1型文法線性有界自動機2型文法下推自動機3型文法有限態(tài)自動機每類文法對應(yīng)一類自動機： 鏈文法： 樹文法樹自動機。 其他：1有限態(tài)自動機有限態(tài)自動機6.6.1 有限態(tài)自動機與正則文法有限態(tài)自動機與正則文法),(0FqQA輸入字母表 內(nèi)部狀態(tài)有限集狀態(tài)轉(zhuǎn)換規(guī)則 初始狀態(tài) Qq 0終止狀態(tài)集 QF 自動機每次從一個狀態(tài)只能轉(zhuǎn)換到另一個指定的狀態(tài)。確定的有限態(tài)自動機：非確定的有限態(tài)自動機： 自動機每次從一個狀態(tài)可以轉(zhuǎn)換到一個指定狀態(tài)集中的任意一狀態(tài)。如： ,),(321qqaq2有限態(tài)自動機接受語言的方式有限態(tài)自動

15、機接受語言的方式有限態(tài)自動機接受的語言：指有限態(tài)自動機接受的鏈x的集合，記為L(A)。 ),(|)(0中在FxqxAL結(jié)構(gòu)：* x中的字符從左到右依次記錄在輸入帶上。 工作方式：* 只讀頭從輸入帶的最左邊一個單元開始依次讀取輸入字符。 * 每讀取一個字符，狀態(tài)控制器搜尋原存入的狀態(tài)轉(zhuǎn)換規(guī)則， 接受/拒絕這個字符。 * 如果自動機連續(xù)地接受輸入鏈的每個字符，最后停在一個終 止狀態(tài)上，則稱輸入鏈屬于該自動機能接受的那種語言，即 )(ALx解：將鏈x輸入自動機A，狀態(tài)轉(zhuǎn)換過程為22010qqqqqaabbFqbbaaq20),()(ALx狀態(tài)轉(zhuǎn)換圖：狀態(tài) 終止態(tài) 進入箭頭 狀態(tài)變化狀態(tài)變化方向220

16、10qqqqqaabb3有限態(tài)自動機與正則文法的對應(yīng)狀態(tài)有限態(tài)自動機與正則文法的對應(yīng)狀態(tài)1）按正則文法構(gòu)造有限態(tài)自動機A和G的對應(yīng)關(guān)系：正則文法的生成式 jiaAA bAi* 由正則文法G構(gòu)成對應(yīng)的有限態(tài)自動機A；應(yīng)用：若將非終止符Ai，Aj分別命名為qi，qj：,cbaVT,FBASFVQNSq 0A接受鏈x的過程為：FAAASbaac2）按有限態(tài)自動機確定正則文法對應(yīng)關(guān)系：若將qi，qj分別命名為Ai，Aj：6.6.2 下推自動機與上下文無關(guān)文法下推自動機與上下文無關(guān)文法1下推自動機下推自動機有限態(tài)自動機的限制：下推自動機(PDA)：有限態(tài)自動機+下推存儲器只能接受正則文法產(chǎn)生的語言，不能

17、接受上下文無關(guān)文法產(chǎn)生的語言?？勺R別上下文無關(guān)文法產(chǎn)生的句子。結(jié)構(gòu)： * 初始狀態(tài)q0：棧頂為最初的非終止符；* 只讀頭讀取輸入帶字符：輸入鏈中的終止符和棧頂?shù)姆墙K止 符共同決定自動機狀態(tài)的轉(zhuǎn)換；* 狀態(tài)轉(zhuǎn)換同時，棧頂內(nèi)容發(fā)生變化。* 自動機內(nèi)部狀態(tài)處于終止態(tài)或堆棧變空時，稱輸入鏈被自動 機接受（識別）了。下推自動機定義： ),(00FZqQAp有限態(tài)自動機加Z0和下推符號有限集最初處于棧頂?shù)姆墙K止符Z 0內(nèi)部狀態(tài)轉(zhuǎn)換和棧頂內(nèi)容改變的規(guī)則 規(guī)則 ：),(,),(),(),(2211mmqqqZaq討論：i* 為單個非終止符。* 為非終止符串。有下推動作， 最左邊的符號處于棧頂；i* 為空串。棧頂Z被彈出，處于Z下面的非終止符處于棧頂。 2下推自動機接受語言的方式下推自動機接受語言的方式1）終止態(tài)方式2）空堆棧方式自動機接受的語言為：),(),( :|)(00QqqZqxxALpAp 下推自動機接受的語言為：,),(),( :|)(*00FqqZqxxALpAp兩種語言等價。3下推自動機與上下文無關(guān)文法的對應(yīng)關(guān)系下推自動機與上下文