句法分析前部分

句法分析前部分第1頁，共33頁，2023年，2月20日，星期一提綱：☆概述☆短語結(jié)構(gòu)分析☆線圖分析法第2頁，共33頁，2023年，2月20日，星期一★句法分析：是指對輸入的單詞序列（一般為句子）判斷其構(gòu)成是否合乎給定的語法，分析合乎語法的句子的句法結(jié)構(gòu)★句法分析的任務(wù)：1）判斷輸入的字符串是否屬于某種語言2）消除輸入句子中詞法和結(jié)構(gòu)等方面的歧義3）分析輸入句子的內(nèi)部結(jié)構(gòu)，如成分構(gòu)成、上下文關(guān)系等★類型：

短語結(jié)構(gòu)分析(Phraseparsing) 完全句法分析(Fullparsing) 局部句法分析(Partialparsing) 依存句法分析(Dependencyparsing)8.1概述第3頁，共33頁，2023年，2月20日，星期一句法形式化（grammarformalism）屬于句法理論研究的范疇常見的機遇約束的語法：

☆功能合一語法（functionalunificationgrammar,FUG）

☆樹連接語法(tree-adjoininggrammar，TAG)☆詞匯功能語法（lexical-functionalgrammar，LFG）☆廣義的短語結(jié)構(gòu)語法（genneralizedphrasestructuregrammar,GPSG）☆中心語驅(qū)動的短語結(jié)構(gòu)語法（head-drivenphasestructuregrammar，HPSG）8.1.2語法形式化第4頁，共33頁，2023年，2月20日，星期一句法分析方法分為：基于規(guī)則的分析方法和基于統(tǒng)計的分析方法基于規(guī)則的分析方法的基本思路：由人工組織語法規(guī)則，建立語法知識庫，通過條件約束和檢查來實現(xiàn)句法結(jié)構(gòu)的歧義的消除?；谝?guī)則的分析方法的主要優(yōu)點：分析算法可以利用手工編寫的語法規(guī)則分析輸入的句子所有可能的句法結(jié)構(gòu)；對于特定的領(lǐng)域和目的，利用手工編寫的有針對性的規(guī)則能較好地處理句子中的部分歧義和一些超語法現(xiàn)象?；谝?guī)則的分析方法的缺陷：對于一個中等長度的輸入句子來說，要利用大覆蓋度的語法規(guī)則分析出所有可能的句子結(jié)構(gòu)是非常困難的，分析過程的復(fù)雜性往往是程序無法實現(xiàn)；即使能夠分析出句子所有可能的結(jié)構(gòu)，也難以在巨大的句法分析結(jié)果集合中實現(xiàn)有效的消歧義，并選擇出最有可能的結(jié)果。手工編寫的規(guī)則一般帶有一定的主觀性，對于實際應(yīng)用系統(tǒng)來說，往往難以覆蓋大領(lǐng)域的所有復(fù)雜語言④手工編寫的規(guī)則本身是一件大工作量的復(fù)雜勞動，而且編寫的規(guī)則對特定的領(lǐng)域有密切的相關(guān)性，不利于句法分析系統(tǒng)向其他領(lǐng)域移植。8.1.3基本方法第5頁，共33頁，2023年，2月20日，星期一

句法分析的例子（參見前面第4章）

他還提出一系列具體措施的政策要點。

他/PN

還/AD

提出/VV

一/CD

系列/M

具體/JJ

措施/NN

和/CC

政策/NN

要點/NN

。/PU8.2短語結(jié)構(gòu)分析第6頁，共33頁，2023年，2月20日，星期一(IP(NP-SBJ(PN他))

(VP(ADVP(AD還))

(VP(VV提出))

(NP-OBJ(QP(CD一)

(CLP(M系列)))

(NP(NP(ADJP(JJ具體)

(NP(NN措施)))

(CC和)

(NP(NN政策)

NN要點))))))

(PU。))8.2

短語結(jié)構(gòu)分析第7頁，共33頁，2023年，2月20日，星期一樹狀表示：IPNPVPPUPNADVPVP。他ADVVNP還提出QPNPCDCLPNPCCNP一MADJPNP和NNNN系列JJNN政策

要點具體

措施8.2

短語結(jié)構(gòu)分析第8頁，共33頁，2023年，2月20日，星期一短語結(jié)構(gòu)分析:

目標(biāo)：實現(xiàn)高正確率、高魯棒性

(robustness)、

高速度的自動句法分析過程。

困難：自然語言中存在大量的復(fù)雜的結(jié)構(gòu)

歧義

(structural

ambiguity)。8.2

短語結(jié)構(gòu)分析第9頁，共33頁，2023年，2月20日，星期一結(jié)構(gòu)歧義

例如：(1)

I

saw

a

boy

in

the

park.

[

I

saw

a

boy

]

in

the

park.

I

saw

a

[

boy

in

the

park].

(2)

I

saw

a

boy

in

the

park

with

a

telescope.

(3)

I

saw

a

boy

swimming

on

the

bridge.

(4)

關(guān)于魯迅的文章。

(5)

把重要的書籍和手稿帶走了。8.2短語結(jié)構(gòu)分析第10頁，共33頁，2023年，2月20日，星期一

英語中的結(jié)構(gòu)歧義隨介詞短語組合個數(shù)的增加而不斷加深的，這個組合個數(shù)我們稱之為開塔蘭數(shù)(Catalan

number，記作CN)。如果句子中存在這樣n

(n為自然數(shù))個介詞短語，CN可由下式獲得[Samuelsson,2000]：8.2

短語結(jié)構(gòu)分析第11頁，共33頁，2023年，2月20日，星期一

基本方法和開源的句法分析器：

基于CFG規(guī)則的分析方法：

線圖分析法

(chart

parsing)

CYK

算法

Earley

(厄爾利)算法

LR

算法

/

Tomita

算法

…

…

－Top-down:

Depth-first/

Breadth-first

－Bottom-up8.2

短語結(jié)構(gòu)分析第12頁，共33頁，2023年，2月20日，星期一基于PCFG的分析方法

PCFG:

Probabilistic

Context-Free

Grammar

(有時也寫作

Stochastic

CFG,

SCFG)其他統(tǒng)計模型部分開源的句法分析器8.2

短語結(jié)構(gòu)分析第13頁，共33頁，2023年，2月20日，星期一線圖分析法

三種策略

自底向上(Bottom-up)

從上到下(Top-down)

從上到下和從下到上結(jié)合8.3

線圖分析法第14頁，共33頁，2023年，2月20日，星期一8.3

線圖分析法第15頁，共33頁，2023年，2月20日，星期一執(zhí)行操作：

查看任意相鄰幾條邊上的詞性串是否與某條重寫規(guī)則的右部相同，如果相同，則增加一條新的邊跨越原來相應(yīng)的邊，新增加邊上的標(biāo)記為這條重寫規(guī)則的頭(左部)。重復(fù)這個過程，直到?jīng)]有新的邊產(chǎn)生。8.3

線圖分析法第16頁，共33頁，2023年，2月20日，星期一點規(guī)則：用于表示規(guī)則右部被歸約(reduce)的程度。

設(shè)有規(guī)則：NPDetAN

NPDetNNPAN

句子:Thegoodbook8.3

線圖分析法第17頁，共33頁，2023年，2月20日，星期一

點規(guī)則：用于表示規(guī)則右部被歸約(reduce)的程度。設(shè)有規(guī)則：NPDetAN

NPDetNNP

AN

句子:Thegoodbook8.3

線圖分析法第18頁，共33頁，2023年，2月20日，星期一

數(shù)據(jù)結(jié)構(gòu)

線圖(Chart)：保存分析過程中已經(jīng)建立的成分(包括終結(jié)符和非

終結(jié)符)、位置(包括起點和終點)。通常以

n×n

的數(shù)組表示(n

為句子包含的詞數(shù))。

代理表(待處理表)(Agenda)：記錄剛剛得到的一些重寫規(guī)則所代

表的成分，這些重寫規(guī)則的右端符號串與輸入詞性

串(或短語標(biāo)志串)中的一段完全匹配，通常以棧

或線性隊列表示。

活動邊集(ActiveArc)：記錄那些右端符號串與輸入串的某一段相

匹配，但還未完全匹配的重寫規(guī)則，通常以數(shù)組或

列表存儲。8.3

線圖分析法第19頁，共33頁，2023年，2月20日，星期一算法描述：

從輸入串的起始位置到最后位置，循環(huán)執(zhí)行如下步驟：

(1)

如果待處理表(Agenda)為空，則找到下一個位置上的詞，

將該詞對應(yīng)的(所有)詞類X

附以

(i,

j)

作為元素放到待處

理表中，即X

(i,

j)。其中，i,

j

分別是該詞的起始位置和

終止位置，j

>

i，j-

i

為該詞的長度。

(2)

從Agenda

中取出一個元素X(i,

j)。

(3)

對于每條規(guī)則

A

X

，將

AX

(i,

j)

加入活動

邊集ActiveArc

中，然后調(diào)用

擴(kuò)展弧子程序。8.3

線圖分析法第20頁，共33頁，2023年，2月20日，星期一

擴(kuò)展弧子程序：(a)

將

X

插入圖表(Chart)的

(i,

j)

位置中。(b)

對于活動邊集(ActiveArc)中每個位置為(k,

i)

(i

>k

1)的點

規(guī)則，如果該規(guī)則具有如下形式：A

X

,

如果A=S,

則

把

S(1,

n+1)

加入到

Chart

中，并給出一個完整的分析結(jié)

果；否則，則將

A(k,

j)

加入到Agenda表中。(c)

對于每個位置為(k,

i)

的點規(guī)則：AX，則將

AX

(k,j)加入到活動邊集中。8.3

線圖分析法8.3

線圖分析法第21頁，共33頁，2023年，2月20日，星期一8.3

線圖分析法第22頁，共33頁，2023年，2月20日，星期一8.3

線圖分析法第23頁，共33頁，2023年，2月20日，星期一8.3

線圖分析法句子分析:第24頁，共33頁，2023年，2月20日，星期一8.3

線圖分析法句子分析:第25頁，共33頁，2023年，2月20日，星期一8.3

線圖分析法最后分析結(jié)果：第26頁，共33頁，2023年，2月20日，星期一8.3

線圖分析法第27頁，共33頁，2023年，2月20日，星期一算法的時間復(fù)雜度分析

設(shè)n為輸入句子的長度，C為上下文無關(guān)文法中的非終結(jié)符的數(shù)目，S為點規(guī)則的狀態(tài)數(shù)目(大于CFG規(guī)則的數(shù)目)，顯然S

>

C。因為Agenda表中的元素形式為X(i,j)，因此,

Agenda表中最大的元素個數(shù)為：Cn2。8.3

線圖分析法第28頁，共33頁，2023年，2月20日，星期一

由于ActiveArc中的元素形式為：A→X[i,j]，所以ActiveArc表中最大的元素數(shù)目為：Sn2.

{

Chart表中的邊的形式為：A[i,j]，因此，Chart表中最大的元素數(shù)目為：Cn2。}

我們來考察算法中每一步執(zhí)行的最大次數(shù)：8.3

線圖分析法第29頁，共33頁，2023年，2月20日，星期一算法描述：

從輸入串的起始位置到最后位置，循環(huán)執(zhí)行如下步驟：

(1)如果待處理表(Agenda)為空，則找到下一個位置上的詞，將該詞對應(yīng)的(所有)詞類X附以(i,j)作為元素放到待處理表中，即X(i,j)。其中，i,j分別是該詞的起始位置和終止位置，j>i，j-i為該詞的長度。最多執(zhí)行的次數(shù)為：C(2)從Agenda中取出一個元素X(i,j)加入活動邊集ActiveArc中，最多執(zhí)行的次數(shù)為：1(3)對于每條規(guī)則

A

X

，將

AX

(i,

j)

加入活動邊集ActiveArc

中，然后調(diào)用

擴(kuò)展弧子程序。最多執(zhí)行的次數(shù)為：Sn28.3

線圖分析法第30頁，共33頁，2023年，2月20日，星期一

擴(kuò)展弧子程序：(a)

將X插入圖表(Chart)的(i,j)位置最多執(zhí)行的次數(shù)為：1(b)

對于活動邊集(ActiveArc)中每個位置為(k,

i)

(i

>k

1)的點

規(guī)則，如果該規(guī)則具有如下形式：A

X