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