句法分析

1、句法分析I,張宇哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院zhangyu@ir.hit.edu.cn,2024年3月16日6時(shí)22分,中文信息處理--句法分析,2,內(nèi)容提要,什么是句法分析與形式語言句法分析的比較上下文無關(guān)語法的分析策略自頂向下分析法自底向上分析法左角分析法,2024年3月16日6時(shí)22分,中文信息處理--句法分析,3,內(nèi)容提要（續(xù)）,上下文無關(guān)語法的分析算法移進(jìn)－歸約算法Marcus確定性分析算法CYK算

2、法Earley算法Tomita算法Chart算法概率上下文無關(guān)語法組塊分析與部分分析,2024年3月16日6時(shí)22分,中文信息處理--句法分析,4,什么是句法分析,句法分析（Parsing）和句法分析器（Parser)句法分析是從單詞串得到句法結(jié)構(gòu)的過程；不同的語法形式，對(duì)應(yīng)的句法分析算法也不盡相同；由于短語結(jié)構(gòu)語法（特別是上下文無關(guān)語法）應(yīng)用得最為廣泛，因此以短語結(jié)構(gòu)樹為目標(biāo)的句法分析器研究得最為徹底；很多其他形式語

3、法對(duì)應(yīng)的句法分析器都可以通過對(duì)短語結(jié)構(gòu)語法的句法分析器進(jìn)行簡(jiǎn)單的改造得到。本講義將主要介紹上下文無關(guān)語法的句法分析器。,2024年3月16日6時(shí)22分,中文信息處理--句法分析,5,與形式語言句法分析的比較,形式語言一般是人工構(gòu)造的語言，是一種確定性的語言，即對(duì)于語言中的任何一個(gè)句子，只有唯一的一種句法結(jié)構(gòu)是合理的，即使語法本身存在歧義，也往往通過人為的方式規(guī)定一種合理的解釋。如程序語言中的if…thenif…then…else…結(jié)

4、構(gòu)，往往都人為規(guī)定else 子句與最接近的if 子句配對(duì)；而在自然語言中，歧義現(xiàn)象是天然地大量存在著的，而且這些歧義的解釋往往都有可能是合理的，因此，對(duì)歧義現(xiàn)象的處理是自然語言句法分析器最本質(zhì)的要求。由于要處理大量的歧義現(xiàn)象，導(dǎo)致自然語言句法分析器的復(fù)雜程度遠(yuǎn)高于形式語言的句法分析器。,2024年3月16日6時(shí)22分,中文信息處理--句法分析,6,句法結(jié)構(gòu)歧義的消解,人們正常交流中所使用的語言，放在特定的環(huán)境下看，一般是沒有歧義的，

5、否則人們將無法交流（某些特殊情況如幽默或雙關(guān)語除外）如果不考慮語言所處的環(huán)境和語言單位的上下文，將會(huì)發(fā)現(xiàn)語言的歧義現(xiàn)象無所不在；結(jié)論：一般來說，語言單位的歧義現(xiàn)象在引入更大的上下文范圍或者語言環(huán)境時(shí)總是可以被被消解的。句法分析的核心任務(wù)就是消解一個(gè)句子在句法結(jié)構(gòu)上的歧義。,2024年3月16日6時(shí)22分,中文信息處理--句法分析,7,句法結(jié)構(gòu)的歧義消解（續(xù)）,我是縣長。 我是縣長派來的。咬死了獵人的狗跑了。 就是這條狼

6、咬死了獵人的狗。小王和小李的妹妹結(jié)婚了。 小王和小李的妹妹都結(jié)婚了。,2024年3月16日6時(shí)22分,中文信息處理--句法分析,8,例子－語法,小王和小李的妹妹結(jié)婚了,2024年3月16日6時(shí)22分,中文信息處理--句法分析,9,例子－分析結(jié)果之一,2024年3月16日6時(shí)22分,中文信息處理--句法分析,10,例子－分析結(jié)果之二,2024年3月16日6時(shí)22分,中文信息處理--句法分析,11,另一個(gè)例子,我是縣長派來的,202

7、4年3月16日6時(shí)22分,中文信息處理--句法分析,12,另一個(gè)例子－分析結(jié)果,2024年3月16日6時(shí)22分,中文信息處理--句法分析,13,句法分析的基本策略,句法分析通常采用的策略有：自頂向下分析法；自底向上分析法；左角分析法；其他策略。,2024年3月16日6時(shí)22分,中文信息處理--句法分析,14,上下文無關(guān)語法的分析算法,常見的上下文無關(guān)語法的句法分析算法：CYK算法；移進(jìn)－歸約算法；Marcus確定性分析算法

8、；Earley算法；Tomita算法（GLR算法、富田算法）；Chart算法（圖分析算法、線圖分析算法）；,2024年3月16日6時(shí)22分,中文信息處理--句法分析,15,自頂向下和自低向上分析法1,句法分析的過程也可以理解為句法樹的構(gòu)造過程所謂自頂向下分析法也就是先構(gòu)造句法樹的根結(jié)點(diǎn)，再逐步向下擴(kuò)展，直到葉結(jié)點(diǎn)；所謂自底向上分析法也就是先構(gòu)造句法樹的葉結(jié)點(diǎn)，再逐步向上合并，直到根結(jié)點(diǎn)。,2024年3月16日6時(shí)22分,中文信

9、息處理--句法分析,16,自頂向下和自低向上分析法2,自頂向下的方法又稱為基于預(yù)測(cè)的方法，也就是說，這種方法是先產(chǎn)生對(duì)后面將要出現(xiàn)的成分的預(yù)期，然后再通過逐步吃進(jìn)待分析的字符串來驗(yàn)證預(yù)期。如果預(yù)期得到了證明，就說明待分析的字符串可以被分析為所預(yù)期的句法結(jié)構(gòu)。如果某一個(gè)環(huán)節(jié)上預(yù)期出了差錯(cuò)，那就要用另外的預(yù)期來替換（即回溯）。如果所有環(huán)節(jié)上所有可能的預(yù)期都被吃進(jìn)的待分析字符串所“反駁”，那就說明待分析的字符串不可能是一個(gè)合法的句子，分析失敗

10、。自底向上的方法也叫基于歸約的方法。就是說，這種方法是先逐步吃進(jìn)待分析字符串，把它們從局部到整體層層歸約為可能的成分。如果整個(gè)待分析字符串被歸約為開始符號(hào)S，那么分析成功。如果在某個(gè)局部證明不可能有任何從這里把整個(gè)待分析字符串歸約為句子的方案，那么就需要回溯。,2024年3月16日6時(shí)22分,中文信息處理--句法分析,17,自頂向下分析法－示例1,2024年3月16日6時(shí)22分,中文信息處理--句法分析,18,自頂向下分析法－示例2

11、,2024年3月16日6時(shí)22分,中文信息處理--句法分析,19,自頂向下分析法－示例3,2024年3月16日6時(shí)22分,中文信息處理--句法分析,20,自頂向下分析法－示例4,2024年3月16日6時(shí)22分,中文信息處理--句法分析,21,自頂向下分析法－示例5,2024年3月16日6時(shí)22分,中文信息處理--句法分析,22,自頂向下分析法－示例6,2024年3月16日6時(shí)22分,中文信息處理--句法分析,23,自頂向下分析法－示例7

12、,2024年3月16日6時(shí)22分,中文信息處理--句法分析,24,自頂向下分析法－示例8,2024年3月16日6時(shí)22分,中文信息處理--句法分析,25,自頂向下分析法－示例9,2024年3月16日6時(shí)22分,中文信息處理--句法分析,26,自頂向下分析法－示例10,2024年3月16日6時(shí)22分,中文信息處理--句法分析,27,自頂向下分析法－示例11,2024年3月16日6時(shí)22分,中文信息處理--句法分析,28,自頂向下分析法－示

13、例12,2024年3月16日6時(shí)22分,中文信息處理--句法分析,29,自頂向下分析法－示例13,2024年3月16日6時(shí)22分,中文信息處理--句法分析,30,自頂向下分析法－示例14,2024年3月16日6時(shí)22分,中文信息處理--句法分析,31,自頂向下分析法－示例15,2024年3月16日6時(shí)22分,中文信息處理--句法分析,32,自頂向下分析法－示例16,2024年3月16日6時(shí)22分,中文信息處理--句法分析,33,自頂向下

14、分析法－示例17,2024年3月16日6時(shí)22分,中文信息處理--句法分析,34,自頂向下分析法－示例18,2024年3月16日6時(shí)22分,中文信息處理--句法分析,35,自頂向下分析法－示例19,2024年3月16日6時(shí)22分,中文信息處理--句法分析,36,自頂向下分析法－示例20,2024年3月16日6時(shí)22分,中文信息處理--句法分析,37,自底向上分析法－示例1,2024年3月16日6時(shí)22分,中文信息處理--句法分析,38,

15、自底向上分析法－示例2,2024年3月16日6時(shí)22分,中文信息處理--句法分析,39,自底向上分析法－示例3,2024年3月16日6時(shí)22分,中文信息處理--句法分析,40,自底向上分析法－示例4,2024年3月16日6時(shí)22分,中文信息處理--句法分析,41,自底向上分析法－示例5,2024年3月16日6時(shí)22分,中文信息處理--句法分析,42,自底向上分析法－示例6,2024年3月16日6時(shí)22分,中文信息處理--句法分析,43,

16、自底向上分析法－示例7,2024年3月16日6時(shí)22分,中文信息處理--句法分析,44,自底向上分析法－示例8,2024年3月16日6時(shí)22分,中文信息處理--句法分析,45,自底向上分析法－示例9,2024年3月16日6時(shí)22分,中文信息處理--句法分析,46,自底向上分析法－示例10,2024年3月16日6時(shí)22分,中文信息處理--句法分析,47,自底向上分析法－示例11,2024年3月16日6時(shí)22分,中文信息處理--句法分析,4

17、8,自底向上分析法－示例12,2024年3月16日6時(shí)22分,中文信息處理--句法分析,49,自底向上分析法－示例13,2024年3月16日6時(shí)22分,中文信息處理--句法分析,50,自底向上分析法－示例14,2024年3月16日6時(shí)22分,中文信息處理--句法分析,51,自底向上分析法－示例15,2024年3月16日6時(shí)22分,中文信息處理--句法分析,52,自底向上分析法－示例16,2024年3月16日6時(shí)22分,中文信息處理--句

18、法分析,53,左角分析法－概述,左角分析法是一種自頂向下和自底向上相結(jié)合的方法所謂“左角(Left Corner)”是指任何一個(gè)句法子樹中左下角的那個(gè)符號(hào)比較：,2024年3月16日6時(shí)22分,中文信息處理--句法分析,54,左角分析法－示例1,2024年3月16日6時(shí)22分,中文信息處理--句法分析,55,左角分析法－示例2,2024年3月16日6時(shí)22分,中文信息處理--句法分析,56,左角分析法－示例3,2024年3月16日6

19、時(shí)22分,中文信息處理--句法分析,57,左角分析法－示例4,2024年3月16日6時(shí)22分,中文信息處理--句法分析,58,左角分析法－示例5,2024年3月16日6時(shí)22分,中文信息處理--句法分析,59,左角分析法－示例6,2024年3月16日6時(shí)22分,中文信息處理--句法分析,60,左角分析法－示例7,2024年3月16日6時(shí)22分,中文信息處理--句法分析,61,左角分析法－示例8,2024年3月16日6時(shí)22分,中文信息處

20、理--句法分析,62,左角分析法－示例9,2024年3月16日6時(shí)22分,中文信息處理--句法分析,63,左角分析法－示例10,2024年3月16日6時(shí)22分,中文信息處理--句法分析,64,左角分析法－示例11,2024年3月16日6時(shí)22分,中文信息處理--句法分析,65,左角分析法－示例12,2024年3月16日6時(shí)22分,中文信息處理--句法分析,66,左角分析法－示例13,2024年3月16日6時(shí)22分,中文信息處理--句法分

21、析,67,左角分析法－示例14,2024年3月16日6時(shí)22分,中文信息處理--句法分析,68,左角分析法－示例15,2024年3月16日6時(shí)22分,中文信息處理--句法分析,69,左角分析法－示例16,2024年3月16日6時(shí)22分,中文信息處理--句法分析,70,左角分析法－示例17,2024年3月16日6時(shí)22分,中文信息處理--句法分析,71,左角分析法－示例18,2024年3月16日6時(shí)22分,中文信息處理--句法分析,72,

22、左角分析法－示例19,2024年3月16日6時(shí)22分,中文信息處理--句法分析,73,左角分析法－示例20,2024年3月16日6時(shí)22分,中文信息處理--句法分析,74,左角分析法－示例21,2024年3月16日6時(shí)22分,中文信息處理--句法分析,75,左角分析法－示例22,2024年3月16日6時(shí)22分,中文信息處理--句法分析,76,左角分析法－示例23,2024年3月16日6時(shí)22分,中文信息處理--句法分析,77,左角分析法

23、－示例24,2024年3月16日6時(shí)22分,中文信息處理--句法分析,78,左角分析法－示例25,2024年3月16日6時(shí)22分,中文信息處理--句法分析,79,左角分析法－示例26,2024年3月16日6時(shí)22分,中文信息處理--句法分析,80,左角分析法－示例27,2024年3月16日6時(shí)22分,中文信息處理--句法分析,81,左角分析法－示例28,2024年3月16日6時(shí)22分,中文信息處理--句法分析,82,左角分析法－示例29

24、,2024年3月16日6時(shí)22分,中文信息處理--句法分析,83,左角分析法－示例30,2024年3月16日6時(shí)22分,中文信息處理--句法分析,84,左角分析法－示例31,2024年3月16日6時(shí)22分,中文信息處理--句法分析,85,左角分析法－示例32,2024年3月16日6時(shí)22分,中文信息處理--句法分析,86,左角分析法－示例33,2024年3月16日6時(shí)22分,中文信息處理--句法分析,87,左角分析法－示例34,2024

25、年3月16日6時(shí)22分,中文信息處理--句法分析,88,左角分析法－示例35,2024年3月16日6時(shí)22分,中文信息處理--句法分析,89,左角分析法－示例36,2024年3月16日6時(shí)22分,中文信息處理--句法分析,90,左角分析法－示例37,2024年3月16日6時(shí)22分,中文信息處理--句法分析,91,左角分析法－示例38,2024年3月16日6時(shí)22分,中文信息處理--句法分析,92,左角分析法－示例39,2024年3月16

26、日6時(shí)22分,中文信息處理--句法分析,93,左角分析法－示例40,2024年3月16日6時(shí)22分,中文信息處理--句法分析,94,左角分析法－示例41,2024年3月16日6時(shí)22分,中文信息處理--句法分析,95,左角分析法－示例42,2024年3月16日6時(shí)22分,中文信息處理--句法分析,96,左角分析法－示例43,2024年3月16日6時(shí)22分,中文信息處理--句法分析,97,左角分析法－示例44,2024年3月16日6時(shí)22

27、分,中文信息處理--句法分析,98,左角分析法－示例45,2024年3月16日6時(shí)22分,中文信息處理--句法分析,99,左角分析法－示例46,2024年3月16日6時(shí)22分,中文信息處理--句法分析,100,左角分析法－示例47,2024年3月16日6時(shí)22分,中文信息處理--句法分析,101,左角分析法－示例48,2024年3月16日6時(shí)22分,中文信息處理--句法分析,102,左角分析法－示例49,2024年3月16日6時(shí)22分,

28、中文信息處理--句法分析,103,左角分析法－示例50,2024年3月16日6時(shí)22分,中文信息處理--句法分析,104,左角分析法－示例51,2024年3月16日6時(shí)22分,中文信息處理--句法分析,105,左角分析法－示例52,2024年3月16日6時(shí)22分,中文信息處理--句法分析,106,左角分析法－示例53,2024年3月16日6時(shí)22分,中文信息處理--句法分析,107,左角分析法－示例54,2024年3月16日6時(shí)22分,

29、中文信息處理--句法分析,108,左角分析法－示例55,2024年3月16日6時(shí)22分,中文信息處理--句法分析,109,左角分析法－示例56,2024年3月16日6時(shí)22分,中文信息處理--句法分析,110,左角分析法－示例57,2024年3月16日6時(shí)22分,中文信息處理--句法分析,111,左角分析法－示例58,2024年3月16日6時(shí)22分,中文信息處理--句法分析,112,左角分析法－示例59,2024年3月16日6時(shí)22分,

30、中文信息處理--句法分析,113,左角分析法－示例60,2024年3月16日6時(shí)22分,中文信息處理--句法分析,114,左角分析法－示例61,2024年3月16日6時(shí)22分,中文信息處理--句法分析,115,移進(jìn)－歸約算法：概述,移進(jìn)－歸約算法：Shift-Reduce Algorithm移進(jìn)－歸約算法類似于下推自動(dòng)機(jī)的LR分析算法移進(jìn)－歸約算法的基本數(shù)據(jù)結(jié)構(gòu)是堆棧移進(jìn)－歸約算法的四種操作：移進(jìn)：從句子左端將一個(gè)終結(jié)符移到棧頂

31、歸約：根據(jù)規(guī)則，將棧頂?shù)娜舾蓚€(gè)符號(hào)替換成一個(gè)符號(hào)接受：句子中所有詞語都已移進(jìn)到棧中，且棧中只剩下一個(gè)符號(hào)S，分析成功，結(jié)束拒絕：句子中所有詞語都已移進(jìn)棧中，棧中并非只有一個(gè)符號(hào)S，也無法進(jìn)行任何歸約操作，分析失敗，結(jié)束,2024年3月16日6時(shí)22分,中文信息處理--句法分析,116,移進(jìn)－歸約算法：舉例,2024年3月16日6時(shí)22分,中文信息處理--句法分析,117,移進(jìn)－歸約算法：沖突,移進(jìn)－歸約算法中有兩種形式的沖突：移

32、進(jìn)－歸約沖突：既可以移進(jìn)，又可以歸約歸約－歸約沖突：可以使用不同的規(guī)則歸約沖突解決方法：回溯回溯導(dǎo)致的問題：回溯策略：對(duì)于互相沖突的各項(xiàng)操作，給出一個(gè)選擇順序斷點(diǎn)信息：除了在堆棧中除了保存非終結(jié)符外，還需要保存斷點(diǎn)信息，使得回溯到該斷點(diǎn)時(shí)，能夠恢復(fù)堆棧的原貌，并知道還可以有哪些可選的操作,2024年3月16日6時(shí)22分,中文信息處理--句法分析,118,移進(jìn)－歸約算法：示例1,回溯策略：移進(jìn)－歸約沖突：先歸約，后移進(jìn)歸約－

33、歸約沖突：規(guī)則事先排序，先執(zhí)行排在前面的規(guī)則斷點(diǎn)信息：當(dāng)前規(guī)則：標(biāo)記當(dāng)前歸約操作所使用的規(guī)則序號(hào)候選規(guī)則：記錄在當(dāng)前位置還有哪些規(guī)則沒有使用（由于這里規(guī)則是排序的，所以這一條可以省略）被替換結(jié)點(diǎn)：歸約時(shí)被替換的結(jié)點(diǎn)，以便回溯時(shí)恢復(fù),2024年3月16日6時(shí)22分,中文信息處理--句法分析,119,移進(jìn)－歸約算法：示例2,給規(guī)則排序并加上編號(hào)：,2024年3月16日6時(shí)22分,中文信息處理--句法分析,120,移進(jìn)－歸約算法：示例

34、3,2024年3月16日6時(shí)22分,中文信息處理--句法分析,121,移進(jìn)－歸約算法：示例4,2024年3月16日6時(shí)22分,中文信息處理--句法分析,122,移進(jìn)－歸約算法：示例5,2024年3月16日6時(shí)22分,中文信息處理--句法分析,123,移進(jìn)－歸約算法：示例6,2024年3月16日6時(shí)22分,中文信息處理--句法分析,124,移進(jìn)－歸約算法：示例7,2024年3月16日6時(shí)22分,中文信息處理--句法分析,125,移進(jìn)－歸約

35、算法：特點(diǎn),移進(jìn)－歸約算法是一種自底向上的分析算法為了得到所有可能的分析結(jié)果，可以在每次分析成功時(shí)都強(qiáng)制性回溯，直到分析失敗可以看到，采用回溯算法將導(dǎo)致大量的冗余操作，效率非常低,2024年3月16日6時(shí)22分,中文信息處理--句法分析,126,移進(jìn)－歸約算法的改進(jìn),如果在出現(xiàn)沖突（移進(jìn)－歸約沖突和歸約－歸約沖突）時(shí)能夠減少錯(cuò)誤的判斷，將大大提高分析的效率引入規(guī)則：通過規(guī)則，給出在特定條件（棧頂若干個(gè)符號(hào)和待移進(jìn)的單詞）應(yīng)該采取的

36、動(dòng)作引入上下文：考慮更多的棧頂元素和更多的待移進(jìn)單詞來寫規(guī)則引入緩沖區(qū)（Marcus算法）：是一種確定性的算法，沒有回溯，但通過引入緩沖區(qū)，可以延遲作出決定的時(shí)間,2024年3月16日6時(shí)22分,中文信息處理--句法分析,127,CYK算法－概述,CYK算法：Cocke-Younger-Kasami算法CYK算法是一種并行算法，不需要回溯；CYK算法建立在Chomsky范式的基礎(chǔ)上Chomsky范式的規(guī)則只有兩種形式：A→BC

37、 A→x這里A,B,C是非終結(jié)符，x是終結(jié)符由于后一種形式實(shí)際上就是詞典信息，在句法分析之前已經(jīng)進(jìn)行了替換，所以在分析中我們只考慮形如A→BC形式的規(guī)則由于任何一個(gè)上下文無關(guān)語法都可以轉(zhuǎn)化成符合Chomsky范式的語法，因此CYK算法可以應(yīng)用于任何一個(gè)上下文無關(guān)語法,2024年3月16日6時(shí)22分,中文信息處理--句法分析,128,CYK算法－數(shù)據(jù)結(jié)構(gòu)1,2024年3月16日6時(shí)22分,中文信息處理--句法分析,129,CYK算法－

38、數(shù)據(jù)結(jié)構(gòu)2,一個(gè)二維矩陣：{ P(i , j) }每一個(gè)元素P(i , j)對(duì)應(yīng)于輸入句子中某一個(gè)跨度（Span）上所有可能形成的短語的非終結(jié)符的集合橫坐標(biāo)i：該跨度左側(cè)第一個(gè)詞的位置縱坐標(biāo)j：該跨度包含的詞數(shù)上圖中P(3,1)={NP,N}表示“縣長”可以歸約成N和NP，P(3,3)={Sφ}表示“縣長派來”可以規(guī)約成Sφ,2024年3月16日6時(shí)22分,中文信息處理--句法分析,130,CYK算法：算法描述,2024年3月1

39、6日6時(shí)22分,中文信息處理--句法分析,131,CYK算法：特點(diǎn),本質(zhì)上是一種自底向上分析法；采用廣度優(yōu)先的搜索策略；采用并行算法，不需要回溯，沒有冗余的操作；時(shí)間復(fù)雜度O(n3)；由于采用廣度優(yōu)先搜索，在歧義較多時(shí)，必須分析到最后才知道結(jié)果，無法采用啟發(fā)式策略進(jìn)行改進(jìn)。,2024年3月16日6時(shí)22分,中文信息處理--句法分析,132,Earley算法－概述,Earley算法也是一種并行算法，不需要回溯；類似于CYK算法，

40、Earley算法中也通過一個(gè)二維矩陣來存放已經(jīng)分析過的結(jié)果；Earley算法的一個(gè)重要貢獻(xiàn)是引入了點(diǎn)規(guī)則，進(jìn)一步減少了規(guī)則匹配中的冗余操作；Earley算法是一種自頂向下的分析算法,2024年3月16日6時(shí)22分,中文信息處理--句法分析,133,Earley算法：點(diǎn)規(guī)則,所謂點(diǎn)規(guī)則，是在規(guī)則的右部的終結(jié)符或非終結(jié)符之間的某一個(gè)位置上加上一個(gè)圓點(diǎn)，表示規(guī)則右部被匹配的程度例子：– VP → · V NP 表示這條規(guī)則還

41、沒有被匹配– VP → V · NP 表示這條規(guī)則右部的V已經(jīng)匹配成功，而NP還沒有被匹配– VP → V NP · 表示這條已被完全匹配，并形成了一個(gè)短語VP,2024年3月16日6時(shí)22分,中文信息處理--句法分析,134,Earley算法：數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)：二維矩陣{E(i,j)}，其中每個(gè)元素是一個(gè)點(diǎn)規(guī)則的集合，用來存放句子中單詞i到單詞j這個(gè)跨度上所分析得到的所有點(diǎn)規(guī)則還是以“我是縣長派來的”為例：

42、Earley算法就是從左到右逐步填充這個(gè)二維矩陣的過程,2024年3月16日6時(shí)22分,中文信息處理--句法分析,135,Earley算法：算法描述,初始化：對(duì)于規(guī)則集中，所有左端為初始符S的規(guī)則S→α ，把S→·α加入到E(0,0)中如果B→· A β在E(0,0)中，那么對(duì)于所有左端為符號(hào)A的規(guī)則A→α ，把A→·α加入到E(0,0)中循環(huán)執(zhí)行以下步驟，直到分析成功或失?。喝绻鸄→α

43、·xjβ在E(i,j-1)中，那么把A→αxj·β加入到E(i,j)中如果A→α·Bβ在E(i,j)中，那么對(duì)所有左端為符號(hào)B的規(guī)則B→γ，把B→·γ加入到E(j,j)中如果B→γ在E(i,j)中，且在E(k,i-1)存在A→α·Bβ，那么把A→αB·β加入到E(k,j)中,2024年3月16日6時(shí)22分,中文信息處理--句法分析,136,復(fù)習(xí)思考題,“小王和小李的妹妹結(jié)婚