【文章內(nèi)容簡(jiǎn)介】 RT N) 4) ((ART ADJ N) 4) ((ART ADJ N VP) 1) 規(guī)則 3改寫(xiě) 11 ((N) 5) ((ART ADJ N) 4) ((ART ADJ N VP) 1) ART匹配 a 12 (() 6) ((ART ADJ N) 4) ((ART ADJ N VP) 1) N匹配 mouse 13 結(jié)束 “1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過(guò)程（續(xù)） 1. SNP VP 2. NPART N 3. NPART ADJ N 4. VPV 5. VPV NP 搜索策略 ? 深度優(yōu)先 ? 后備狀態(tài)采用 “ 棧 ”結(jié)構(gòu) ? 后備狀態(tài)少，存儲(chǔ)效率高 ? 面臨 “ 左遞歸 ” 問(wèn)題 ? 廣度優(yōu)先 ? 后備狀態(tài)采用 “ 隊(duì)列 ”結(jié)構(gòu) ? 后備狀態(tài)多，存儲(chǔ)效率不高 自底向上句法分析 ? 簡(jiǎn)單的自底向上句法分析效率不高，常常會(huì)重復(fù)嘗試 相同的 匹配操作（回溯之前已匹配過(guò)）。 ? 一種基于圖的句法分析技術(shù)（ Chart Parsing）被提出，它把已經(jīng)匹配過(guò)的結(jié)果保存起來(lái)，今后需要時(shí)可直接使用它們，不必重新匹配。（動(dòng)態(tài)規(guī)劃） Chart Parsing的數(shù)據(jù)表示 ? 圖 （ chart） 的 結(jié)點(diǎn)表示句子中詞之間的位置數(shù)字 ? 非活動(dòng)邊 集（ chart的核心，常直接就被稱為 chart） ? 記錄分析中規(guī)約成功所得到的所有詞法 /句法符號(hào) ? 活動(dòng)邊 集 ? 未完全匹配的產(chǎn)生式，用加小圓圈標(biāo)記（ 186。）的產(chǎn)生式來(lái)表示，如： ? NP ART 186。ADJ N ? NP ART 186。N ? 待處理 表 （ agenda） ? 記錄等待加入 chart的已匹配成功的詞法 /句法符號(hào) ? 上面的活動(dòng)邊、非活動(dòng)邊以及詞法 /句法符號(hào)都帶有“ 始 /終結(jié)點(diǎn) ” 位置 信息 “1 The 2 cat 3 caught 4 a 5 mouse 6”分析中的數(shù)據(jù)示例 1 2 3 4 The cat caught ART NP ART 186。 N NP ART 186。 ADJ N 活動(dòng)邊 非活動(dòng)邊 1. SNP VP 2. NPART N 3. NPART ADJ N 4. VPV 5. VPV NP N(2,3) agenda 5 6 a mouse 重復(fù)下面的操作，直到 agenda為空并且輸入中沒(méi)有下一個(gè)詞 ? 若 agenda為空，則把句子中下一個(gè)詞的各種詞法符號(hào)（詞性）和它們的位置加入進(jìn)來(lái)， ? 從 agenda中取一個(gè)元素（設(shè)為 C，位置為： p1p2) ? 對(duì)下面形式的每個(gè)規(guī)則增加活動(dòng)邊： ? XCX1...Xn，增加一條 活動(dòng)邊 ： XC 186。 X1...Xn，位置為： p1p2； ? XC，把 X加入 agenda，位置為： p1p2 ? 將 C作為 非活動(dòng)邊 加入到 chart的位置 p1p2 ? 對(duì) 已有活動(dòng)邊 進(jìn)行 邊擴(kuò)展 ? 對(duì)每個(gè)形式為： XX1... 186。 C...Xn的活動(dòng)邊，若它在 p0p1之間，則增加一條 活動(dòng)邊 ： XX1... C 186。...Xn，位置 :p0p2 ? 對(duì)每個(gè)形式為： XX1... Xn 186。 C的活動(dòng)邊，若它在 p0p1之間，則把 X加入 agenda ，位置為： p0p2 Chart Parsing句法分析算法 “1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過(guò)程 (算法 ) 1 2 3 4 The cat caught ART NP ART 186。 N NP ART 186。 ADJ N 活動(dòng)邊 非活動(dòng)邊 1. SNP VP 2. NPART N 3. NPART ADJ N 4. VPV 5. VPV NP ART(1,2) agenda 5 6 a mouse “1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過(guò)程 (算法 ) 1 2 3 4 The cat caught ART NP ART 186。 N NP ART 186。 ADJ N 活動(dòng)邊 非活動(dòng)邊 1. SNP VP 2. NPART N 3. NPART ADJ N 4. VPV 5. VPV NP N(2,3) agenda 5 6 a mouse N NP(1,3) “1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過(guò)程 (算法 ) 1 2 3 4 The cat caught ART NP ART 186。 N NP ART 186。 ADJ N 活動(dòng)邊 非活動(dòng)邊 1. SNP VP 2. NPART N 3. NPART ADJ N 4. VPV 5. VPV NP agenda 5 6 a mouse N NP(1,3) S NP 186。 VP NP “1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過(guò)程 (算法 ) 1 2 3 4 The cat caught ART NP ART 186。 N NP ART 186。 ADJ N 活動(dòng)邊 非活動(dòng)邊 1. SNP VP 2. NPART N 3. NPART ADJ N 4. VPV 5. VPV NP agenda 5 6 a mouse N V(3,4) S NP 186。 VP NP VP V 186。 NP VP(3,4) V “1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過(guò)程 (算法 ) 1 2 3 4 The cat caught ART NP ART 186。 N NP ART 186。 ADJ N 活動(dòng)邊 非活動(dòng)邊 1. SNP VP 2. NPART N 3. NPART ADJ N 4. VPV 5. VPV NP agenda 5 6 a mouse N S NP 186。 VP NP VP V 186。 NP VP(3,4) V VP S(1,4) “1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過(guò)程 (算法 ) 1 2 3 4 The cat caught ART NP ART 186。 N NP ART 186。 ADJ N 活動(dòng)邊 非活動(dòng)邊 1. SNP VP 2. NPART N 3. NPART ADJ N 4. VPV 5. VPV NP agenda 5 6 a mouse N S NP 186。 VP NP VP V 186。 NP V VP S(1,4) S “1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過(guò)程 (算法 ) 1 2 3 4 The cat caught ART NP ART 186。 N NP ART 186。 ADJ N 活動(dòng)邊 非活動(dòng)邊 1. SNP VP 2. NPART N 3. NPART ADJ N 4. VPV 5. VPV NP agenda 5 6 a mouse N S NP 186。 VP NP VP V 186。 NP V VP ART(4,5) S NP ART 186。 N NP ART 186。 ADJ N ART “1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過(guò)程 (算法 ) 1 2 3 4 The cat caught ART NP ART 186。 N NP ART 186。 ADJ N 活動(dòng)邊 非活動(dòng)邊 1. SNP VP 2. NPART N 3. NPART ADJ N 4. VPV 5. VPV NP agenda 5 6 a mouse N S NP 186。 VP NP VP V 186。 NP V VP N(5,6) S NP ART 186。 N NP ART 186。 ADJ N ART N NP(4,6) “1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過(guò)程 (算法 ) 1 2 3 4 The cat caught ART NP ART 186。 N NP ART 186。 ADJ N 活動(dòng)邊 非活動(dòng)邊 1. SNP VP 2. NPART N 3. NPART ADJ N 4. VPV 5. VPV NP agenda 5 6 a mouse N S NP 186。 VP NP VP V 186。 NP V VP S NP ART 186。 N NP ART 186。 ADJ N ART N NP(4,6) S NP 186。 VP NP VP(3,6) “1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過(guò)程 (算法 ) 1 2 3 4 The cat caught ART NP ART 186。 N NP ART 186。 ADJ N 活動(dòng)邊 非活動(dòng)邊 1. SNP VP 2. NPART N 3. NPART ADJ N 4. VPV 5. VPV NP agenda 5 6 a mouse N S NP 186。 VP NP VP V 186。 NP V VP S NP ART 186。 N NP ART 186。 ADJ N ART N S NP 186。 VP NP VP(3,6) VP S(1,6) “1 The 2 cat 3 caught 4 a 5 mouse 6”的分析過(guò)程 (算法 ) 1 2 3 4 The cat caught ART NP ART 186。 N NP ART 186。 ADJ N 活動(dòng)邊 非活動(dòng)邊 1. SNP VP 2. NPART N 3. NPART ADJ N 4. VPV 5. VPV NP agenda 5 6 a mouse N S NP 186。 VP NP VP V 186。 NP V VP S NP ART 186。 N NP ART 186。 ADJ N ART N S NP 186。 VP NP VP S(1,6) S Proj. 3 實(shí)現(xiàn)一個(gè)基于簡(jiǎn)單英語(yǔ)語(yǔ)法的 chart句法分析器。 ?agenda采用棧 or隊(duì)列？ ?可能會(huì)有無(wú)用（不可能用到）的活動(dòng)邊，影響效率。 句法分析與邏輯程序設(shè)計(jì) ? 邏輯程序設(shè)計(jì)是把程序組織成一組事實(shí)（謂詞）和一組推理規(guī)則，計(jì)算（推理）過(guò)程由實(shí)現(xiàn)系統(tǒng)自動(dòng)給出，它基于謂詞演算（ Predicate Calculus）進(jìn)行計(jì)算。 ? PROLOG是一個(gè)邏輯程序設(shè)計(jì)語(yǔ)言，在程序中，用子句（ clause）描述事實(shí)和推理規(guī)則，推理過(guò)程由 PROLOG的執(zhí)行機(jī)制自動(dòng)完成。 ? 對(duì)句法分析而言， ? 事實(shí)：句子中每個(gè)詞的詞性以及詞在句子中的位置等 ? 推理規(guī)則：文法（產(chǎn)生式） 一個(gè)基于 CFG的 PROLOG句法分析器 ? 詞典、詞形還原以及詞性標(biāo)注結(jié)果可表示成事實(shí)： ? isar