語(yǔ)法分析幻燈片

1、第 5 章 語(yǔ)法分析 語(yǔ)法分析是編譯的第二階段；其任務(wù)是語(yǔ)法分析是編譯的第二階段；其任務(wù)是識(shí)別識(shí)別和和處理處理比單詞更大的語(yǔ)法單位比單詞更大的語(yǔ)法單位，如：，如：程序設(shè)計(jì)語(yǔ)言中程序設(shè)計(jì)語(yǔ)言中的的表達(dá)式表達(dá)式、各種各種說(shuō)明說(shuō)明和和語(yǔ)句語(yǔ)句乃至全部乃至全部源程序源程序，指出指出其中的其中的語(yǔ)法錯(cuò)誤；必要時(shí)，可生成內(nèi)部形式，便于語(yǔ)法錯(cuò)誤；必要時(shí)，可生成內(nèi)部形式，便于下一階段處理。下一階段處理。 內(nèi)容提要內(nèi)容提要: :5.1 5.1 語(yǔ)法分析的基本概念語(yǔ)法分析的基本概念5.2 5.2 遞歸子程序法遞歸子程序法5.3 ll(1)5.3 ll(1)分析法分析法5.4 lr()5.4 lr()分析法分析法5

2、.5 5.5 簡(jiǎn)單優(yōu)先分析法簡(jiǎn)單優(yōu)先分析法5.1 語(yǔ)法分析的基本概念5.1.1 語(yǔ)法分析的定義與分類(lèi) 【定義定義】形式上說(shuō)，語(yǔ)法分析是指對(duì)給定的符號(hào)形式上說(shuō)，語(yǔ)法分析是指對(duì)給定的符號(hào)串（串（ ），判定其是否是某文法），判定其是否是某文法g(z)g(z)的句子。即的句子。即z z 成立嗎成立嗎 ? ? = + + z z 成立嗎成立嗎 ? ? = . .+ + 【分類(lèi)分類(lèi)】語(yǔ)法分析方法通常分兩大類(lèi)：語(yǔ)法分析方法通常分兩大類(lèi)： 1. 1. 自頂向下法自頂向下法（推導(dǎo)法推導(dǎo)法） 2. 2. 自底向上法自底向上法（歸約法歸約法） 從開(kāi)始符號(hào)出發(fā)，采用從開(kāi)始符號(hào)出發(fā)，采用推導(dǎo)推導(dǎo)運(yùn)算運(yùn)算，試圖，試圖自頂

3、自頂向下向下構(gòu)造語(yǔ)法樹(shù)。構(gòu)造語(yǔ)法樹(shù)。 從給定的符號(hào)串出發(fā)，采用從給定的符號(hào)串出發(fā)，采用歸約歸約運(yùn)算運(yùn)算，試圖，試圖自底向上自底向上構(gòu)造語(yǔ)法樹(shù)。構(gòu)造語(yǔ)法樹(shù)。或或 通常采用通常采用“最左推導(dǎo)法最左推導(dǎo)法”。 通常采用通常采用“最左歸約法最左歸約法”給定：給定： = a= a* *(b+c)(b+c)， 是否是表達(dá)式？是否是表達(dá)式？(接上頁(yè))5.1.2 算法設(shè)計(jì)分析1【例例5.15.1】 g(e) g(e)： e - t | e+t | e-t e - t | e+t | e-t t - f | t t - f | t* *f | t/ff | t/f f - i | (e) f - i | (e)

4、 最左推導(dǎo)最左推導(dǎo)分析過(guò)程：分析過(guò)程：【結(jié)論結(jié)論】自頂向下分析的關(guān)鍵技術(shù)是如何確定具有自頂向下分析的關(guān)鍵技術(shù)是如何確定具有相同左部的產(chǎn)生式之相同左部的產(chǎn)生式之侯選者侯選者！即即 e ae a* *(b+c)(b+c) = + +=t=t* *f f =f=f* *f f =a=a* *f f =a=a* *(e)(e)=a=a* *(e+t)(e+t) =a=a* *(t+t)(t+t) =a=a* *(f+t)(f+t) =a=a* *(b+t)(b+t)=a=a* *(b+f)(b+f) =a=a* *(b+c)(b+c)- - 自頂向下法自頂向下法: :e e = = t t 為了清楚每

5、次為了清楚每次歸約歸約的是什麼？我們觀察語(yǔ)法樹(shù)的的是什麼？我們觀察語(yǔ)法樹(shù)的 = a= a* *(b+c)(b+c)5.1.2 算法設(shè)計(jì)分析2 e - t | e+t | e-t e - t | e+t | e-t t - f | t t - f | t* *f | t/ff | t/f f - i | (e) f - i | (e) - - 自底向上法自底向上法a a* *(b+c)(b+c) =. .f f* *(b+c)(b+c)=. .t t* *(e+c)(e+c)=. .t t* *(b+c)(b+c)=. .t t* *(f+c)(f+c)=. .t t* *(t+c)(t+c)=

6、. .t t* *(e+f)(e+f)=. .t t* *(e+t)(e+t) =. .t t* *(e)(e)=. .t t* *f f=. .e e=. .t t=. .+ +e e a a* *(b+c)(b+c)即即【結(jié)論結(jié)論】自底向上分析的關(guān)鍵技術(shù)是自底向上分析的關(guān)鍵技術(shù)是如何確定如何確定當(dāng)前句型的句柄！當(dāng)前句型的句柄！最左歸約最左歸約分析過(guò)程分析過(guò)程： 構(gòu)造過(guò)程： 5.2.1 遞歸子程序法的設(shè)計(jì)原理： 語(yǔ)法分析的核心技術(shù)是語(yǔ)法分析的核心技術(shù)是“文法文法”的的機(jī)內(nèi)表示機(jī)內(nèi)表示問(wèn)題；遞歸子程序法直接把問(wèn)題；遞歸子程序法直接把文法文法變成變成程序。程序。 對(duì)每一個(gè)對(duì)每一個(gè)非終結(jié)符非終結(jié)符

7、，構(gòu)造一個(gè)子程序，用以識(shí)，構(gòu)造一個(gè)子程序，用以識(shí)別該非終結(jié)符所定義的符號(hào)串。別該非終結(jié)符所定義的符號(hào)串。每個(gè)子程序以產(chǎn)生每個(gè)子程序以產(chǎn)生式左部非終結(jié)符命名式左部非終結(jié)符命名，以產(chǎn)生式右部構(gòu)造子程序內(nèi)以產(chǎn)生式右部構(gòu)造子程序內(nèi)容。容。例如：設(shè)有如下產(chǎn)生式：例如：設(shè)有如下產(chǎn)生式： a - abed | bac | a - abed | bac | 則有：遞歸子程序則有：遞歸子程序 a:a: 遞歸子程序法屬于遞歸子程序法屬于自頂向下語(yǔ)法分析方法自頂向下語(yǔ)法分析方法。故。故又名遞歸下降法。又名遞歸下降法。 設(shè)計(jì)原理：設(shè)計(jì)原理：y yn n入口入口出口出口a?a?b?b?next(w)next(w)y y

8、next(w) next(w) next(w)next(w)n nc?c?y yn nerr2err2e?e?遇時(shí)時(shí) b b a a dyerr1err1nnext(w)next(w)a - abed | bac | a - abed | bac | 判斷當(dāng)前單詞是否是c即w=c?調(diào)用子程序a( (接上頁(yè)接上頁(yè)) )讀單詞函數(shù)5.2.2 遞歸子程序的構(gòu)造算法 擴(kuò)展文法擴(kuò)展文法：增設(shè)一個(gè)產(chǎn)生式，作為主程序：增設(shè)一個(gè)產(chǎn)生式，作為主程序：z-z z-z ， 入出口約定入出口約定： 子程序入口時(shí)，其子程序入口時(shí)，其首符號(hào)首符號(hào)已經(jīng)讀來(lái)！已經(jīng)讀來(lái)！子程序出口時(shí)，子程序出口時(shí)，其其后繼符后繼符應(yīng)該讀來(lái)！應(yīng)

9、該讀來(lái)！ 子程序內(nèi)容設(shè)計(jì)子程序內(nèi)容設(shè)計(jì)：遇遇終結(jié)符終結(jié)符，判定之，判定之 ，確認(rèn)后讀下一單詞；，確認(rèn)后讀下一單詞；遇遇非終結(jié)符非終結(jié)符, ,調(diào)用之調(diào)用之, ,返回后不讀下一單詞；返回后不讀下一單詞； 遇遇空串空串( ( ) ) ，直接出口；，直接出口； 【例例5.25.2】g(s):g(s):令令 z - s , z - s , 則則 遞歸子程序遞歸子程序: :子程序子程序a開(kāi)始開(kāi)始結(jié)束結(jié)束 #snext(w)err0yn入口入口出口出口 a berr1next(w)a berr2next(w)snext(w)子程序子程序snnnyyy入口入口 cnext(w)出口出口遇遇 時(shí)時(shí)ny dnex

10、t(w)err3yn主程序主程序s - aab |bs , a - cd | s - aab |bs , a - cd | 實(shí)際上，上述兩點(diǎn)可歸納為同一個(gè)條件，即：實(shí)際上，上述兩點(diǎn)可歸納為同一個(gè)條件，即： 遞歸子程序要求文法應(yīng)是：遞歸子程序要求文法應(yīng)是： 5.2.3 遞歸子程序法對(duì)文法的要求： 遞歸子程序是根據(jù)文法各產(chǎn)生式的遞歸子程序是根據(jù)文法各產(chǎn)生式的首符號(hào)首符號(hào)與當(dāng)前與當(dāng)前所讀所讀單詞單詞進(jìn)行匹配，以決定進(jìn)行匹配，以決定候選產(chǎn)生式候選產(chǎn)生式的；這就要求的；這就要求文法：文法： 具有相同左部的各產(chǎn)生式，首符號(hào)不同；具有相同左部的各產(chǎn)生式，首符號(hào)不同； 文法不能有左遞歸！文法不能有左遞歸！如：

11、如：a - aa - a |a|a ( (首符號(hào)相同，首符號(hào)相同，) )； a - aa - a | | ( (直接左遞歸，直接左遞歸，) )。 ll(1)ll(1)文法文法! !（見(jiàn)（見(jiàn) 5.35.3節(jié)）。節(jié)）。 5.2.4 5.2.4 遞歸子程序的遞歸子程序的構(gòu)造例構(gòu)造例： . 消除左遞歸后的文法消除左遞歸后的文法1:g(e) :g(e) :t - f t - f 2 2 f f f - i | ( e )f - i | ( e )e - t e - t 1 1t t 【提示提示】 根據(jù)文法變換：根據(jù)文法變換：a - aa - a | | a - a - 【例例5.35.3】g(e)g(e

12、)： e - t | ee - t | e1 1t t t - f | t t - f | t2 2f f f - i | (e) f - i | (e) 其中：其中：1 1(+,-),(+,-),2 2( (* *,/),i(,/),i(變量或常數(shù)變量或常數(shù)) )主程序主程序t - f t - f 2 2 f f f - i | ( e )f - i | ( e )e - t e - t 1 1 t t 子程序子程序e令令 z - ez - e開(kāi)始開(kāi)始結(jié)束結(jié)束 #enext(w)err0yn入口入口出口出口 next(w)t 1 1tyn入口入口出口出口 next(w)f 2 2fyn子程序

13、子程序t( (接上頁(yè)接上頁(yè)) )t - f t - f 2 2 f f f - i | ( e )f - i | ( e )e - t e - t 1 1 t t 入口入口出口出口 i (err1next(w)err2next(w)e )yyynnn子程序子程序f( (接上頁(yè)接上頁(yè)) ). . 消除左遞歸后的文法消除左遞歸后的文法2 :2 :g(e) :g(e) :t - f t - f 2 2 f f f - i | ( e )f - i | ( e )e - t e - t 1 1 t t e - t ee - t ee - e - 1 1t e | t e | t - f tt - f

14、tt - t - 2 2f t | f t | f - i | ( e )f - i | ( e ) 文法文法 g(e)消除花括號(hào)后可得：消除花括號(hào)后可得：令令 z - e z - e ，則可構(gòu)造遞歸子程序如下：，則可構(gòu)造遞歸子程序如下： （主程序（主程序 省略）省略）入口入口出口出口te子程序子程序e入口入口 1 1next(w)t出口出口遇遇 時(shí)時(shí)nyee子程序子程序ee - t ee - t ee - e - 1 1t e | t e | t - f tt - f tt - t - 2 2f t | f t | f - i | ( e )f - i | ( e )( (接上頁(yè)接上頁(yè)) )

15、 1. 1. 什麼是什麼是ll(1)ll(1)分析法？分析法？ 5.3.1 ll(1)分析法基本概念 5.3 ll(1)分析法 ll(1) 分析法的基本要點(diǎn)有三：分析法的基本要點(diǎn)有三： 利用一個(gè)利用一個(gè)分析表分析表，登記如何，登記如何選擇產(chǎn)生式選擇產(chǎn)生式的知識(shí)；的知識(shí)； 利用一個(gè)利用一個(gè)分析棧分析棧，記錄分析過(guò)程；，記錄分析過(guò)程； 此分析法要求文法必須是此分析法要求文法必須是 ll(1)文法文法。 ll(1) ll(1)分析法是指從分析法是指從左左到右掃描到右掃描最最左左推導(dǎo)推導(dǎo)( (llll) )和只查看和只查看一一個(gè)當(dāng)前符號(hào)（括號(hào)中的個(gè)當(dāng)前符號(hào)（括號(hào)中的 1 1）之意；）之意； ll(1)

16、ll(1)分析法又稱(chēng)預(yù)測(cè)分析法，與遞歸子程序分析法又稱(chēng)預(yù)測(cè)分析法，與遞歸子程序法同屬于自頂向下確定性語(yǔ)法分析方法法同屬于自頂向下確定性語(yǔ)法分析方法; ; 2. ll(1)2. ll(1)分析過(guò)程示例分析過(guò)程示例 g(z)g(z)：z-dazz-daz | bac | bac a-aa a-aa | | 棧棧 當(dāng)前符號(hào)當(dāng)前符號(hào) 剩余序列剩余序列 棧操作棧操作 選擇推導(dǎo)產(chǎn)生式后，為什麼要逆序壓棧選擇推導(dǎo)產(chǎn)生式后，為什麼要逆序壓棧? ? 當(dāng)棧頂為當(dāng)棧頂為a,a,當(dāng)前單詞為當(dāng)前單詞為c c時(shí)，為什么選擇時(shí)，為什么選擇 a a ? ?討討論論逆逆序序壓壓棧棧# # # c # c a a# c# c#

17、c # c a a# # c c# # c a c a b b a a a ab ba c #a c # 選擇選擇 z zbacbacb ba c #a c #匹配匹配 b ba ac #c # 選擇選擇a aaaaaa ac #c #匹配匹配 a a c c# # 選擇選擇a a c c# #匹配匹配 c c# #正確結(jié)束正確結(jié)束 z z查分查分析表析表 對(duì)符號(hào)串：對(duì)符號(hào)串： = = bacbac # # 的分析過(guò)程：的分析過(guò)程：分析表：分析表： 設(shè)有文法g(z), # 棧底標(biāo)記和結(jié)束標(biāo)記;#棧棧結(jié)束結(jié)束： 若若 棧頂符棧頂符=a =a 且且 當(dāng)前符為當(dāng)前符為a a； 則則 pop,next

18、(w);pop,next(w);# z 開(kāi)始開(kāi)始：棧棧 ; next(w)；當(dāng)前符當(dāng)前符 w= # 重復(fù)執(zhí)行重復(fù)執(zhí)行 、 ，直到棧中只剩，直到棧中只剩 # # 為止：為止： 即：棧調(diào)整：即：棧調(diào)整：# a# 即：棧調(diào)整：即：棧調(diào)整：# a# a a 3. ll(1) 3. ll(1)分析法算法概要分析法算法概要 若若 棧頂符棧頂符=a =a 且且 當(dāng)前符當(dāng)前符 w=a w=a 且且 有有產(chǎn)生式產(chǎn)生式： a aa a ， 則則 pop,push(apop,push(a ) )r r ; ; 逆序壓棧! 否則，否則，錯(cuò)誤處理錯(cuò)誤處理！5.3.2 ll(1)文法及其判定1.首符號(hào)集合、后繼符集合與選

19、擇符集合 設(shè)設(shè) g(z)=(vg(z)=(vn n, v, vt t, z, p), z, p)，a-a- pp，則，則 【注注】 ( ( 可空可空), ), ( ( 不可空不可空) )； 若若 = = 則則 first(first( )= )= ； 設(shè)設(shè) # #為輸入串的結(jié)束符，則為輸入串的結(jié)束符，則 #follow(z); #follow(z); =* * *first(first( )= t| )= t| t t，tvtvt t =* *follow(a)= t| z follow(a)= t| z atat，tvtvt t =* *【注注】 求求 follow(a) follow(a)

20、 要點(diǎn)：要點(diǎn)： 查所有右部含有查所有右部含有a a的產(chǎn)生式的產(chǎn)生式: b - : b - a a 若若 不空時(shí)不空時(shí) , , 則則 first(first( ) )follow(a)follow(a) ； 若若 取空時(shí)取空時(shí) , , 則則 follow(b)follow(b)follow(a)follow(a) ； 若若 = = 時(shí)時(shí) , , 則則 follow(b)follow(a)follow(b)follow(a)。select(select()= first()= first(dazdaz)=d )=d select(select()= first()= first(bcabca)=b

21、)=bselect(select()= first()= first(aaaa)=a )=a select(select()= first()= first( )follow(a)= )follow(a)= b,db,d，# # 即：即： b - b - a ag(z)g(z)： z - daz z - daz | bca | bca a - aa a - aa | | 【例5.4】 求文法產(chǎn)生式的選擇集合:則有：則有： 產(chǎn)生式產(chǎn)生式序號(hào)序號(hào) select( select()= d )= d ；2. ll(1)2. ll(1)文法及其判定文法及其判定 ll(1) ll(1)文法可確保文法可確保

22、 遞歸子程序法遞歸子程序法 和和 ll(1)ll(1)分分析法析法 的正確運(yùn)用。的正確運(yùn)用?！纠?.55.5】 g(z) g(z)： z - daz z - daz | bca | bca a - aa a - aa | | select( select()= b)= bselect(select()= a )= a ；即：即： db=db= 又又 ab,d,#= ab,d,#= select(select()= )= b,db,d，# # g(z) g(z) 是是 ll(1)ll(1)文法。文法。 ll(1)分析法示例：【例5.6】 g(z)：z - z b | a 【注注】上述文法可進(jìn)行

23、等價(jià)變換，消除左遞歸得：上述文法可進(jìn)行等價(jià)變換，消除左遞歸得： select( select()= a )= a select( select()= a )= a 選擇集合相交選擇集合相交 具有左遞歸的文法，一定不是具有左遞歸的文法，一定不是ll(1)ll(1)文法！文法！ g g (z)(z)是是ll(1)ll(1)文法，可以用文法，可以用 ll(1)ll(1)分析法。分析法。 select( select()= b )= b select( select()= # )= # 選擇集合不相交選擇集合不相交g g (z)(z)： z - aa z - aa , , a - ba a - ba

24、| | 列： 終結(jié)符 | #5.3.3 ll(1)分析器設(shè)計(jì)(實(shí)現(xiàn)) 應(yīng)用時(shí)，可用下列函數(shù)查表，獲取相應(yīng)產(chǎn)生式：應(yīng)用時(shí)，可用下列函數(shù)查表，獲取相應(yīng)產(chǎn)生式： l(l(棧頂符，當(dāng)前符）棧頂符，當(dāng)前符）= = 產(chǎn)生式序號(hào)產(chǎn)生式序號(hào)【結(jié)構(gòu)設(shè)計(jì)結(jié)構(gòu)設(shè)計(jì)】. ll(1). ll(1)分析表的構(gòu)造分析表的構(gòu)造: : ll(1)ll(1)控制程序控制程序+ +ll(1)ll(1)分析表分析表ll(1)ll(1)分析表是存儲(chǔ)分析表是存儲(chǔ)文法選擇集合的知識(shí)表文法選擇集合的知識(shí)表。 行：行： 非終結(jié)符非終結(jié)符表項(xiàng)：表項(xiàng)：產(chǎn)生產(chǎn)生式式序號(hào) z # a a a 如如 g(z)g(z)： z - aab z - aab

25、| aca | aca select( select()=a; )=a; 【算法設(shè)計(jì)算法設(shè)計(jì)】 a - da a - da | | i則則 l( a , a ):=l( a , a ):=a - a - i 求求文法文法選擇集合，確認(rèn)選擇集合，確認(rèn) ll(1)ll(1)文法；文法； 依次取依次取產(chǎn)生式產(chǎn)生式：select(select()=d;)=d;select(select()=c,d ; )=c,d ; select(select()= )= b,c,#;b,c,#;是是 ll(1)ll(1)文法文法, ,ll(1)ll(1)分析表：分析表：不相交不相交不不相相交交若若 a select

26、( ) a select( ) i next(w)next(w)y yn nerrerrn ny yn nn nerrerr push(#),push(z) push(#),push(z) pop(x) pop(x)y y開(kāi)始開(kāi)始結(jié)束結(jié)束xvxvt tn nerrerry yxvxvn nw = #w = #x = wx = wy y查查ll(1)ll(1)分析表分析表: : l( x ,w )= ?l( x ,w )= ? 空？空？. ll(1). ll(1)分析法控制程序：分析法控制程序：push ( ipush ( ir r ）把產(chǎn)生式把產(chǎn)生式 i i 右部逆序壓棧右部逆序壓棧把棧頂符把

27、棧頂符彈入到變彈入到變量量x x中中! ! ll(1)分析法綜合示例：【例例5.75.7】 g(e) g(e)： e - t | e e - t | e 1 1 t t t - f | t t - f | t 2 2 f f f - i | ( e ) f - i | ( e ) 此文法含左遞歸，不是此文法含左遞歸，不是ll(1)ll(1)文法文法; ;經(jīng)文法經(jīng)文法變換（消除左遞歸）后可得：變換（消除左遞歸）后可得：g(e): e - t eg(e): e - t e e e - - 1 1 t et e | | t - f t t - f t t t - - 2 2 f tf t | | f

28、 - i f - i | ( e ) | ( e ) 其中：其中： 1 1( + ,- ) , ( + ,- ) , 2 2 ( ( * * ,/ ) ,/ ) 這是這是ll(1)ll(1)文法嗎文法嗎? ?select(select()=first(te)= )=first(te)= i i, ,( ( 1.1.求求g(e) g(e) 的的選擇集合：選擇集合： 三對(duì)選擇集合兩兩不相交，三對(duì)選擇集合兩兩不相交，g(e): e - t eg(e): e - t e e e - - 1 1 t et e | | t - f t t - f t t t - - 2 2 f tf t | | f -

29、i f - i | ( e ) | ( e ) e -e -e-e-t -t -t-t-f -f -select(select()=first()=first( 1 1tete )= )= 1 1 select(select()=follow(e)=follow(e )= )= ) ), ,# # select(select()=first(ft)= )=first(ft)= i i, ,( ( select(select()=first()=first( 2 2ftft )= )= 2 2 select(select()=follow(t)= )=follow(t)= 1 1 , ,) ),

30、 ,# # select(select()=first(i)= )=first(i)= i i select(select()=first(e)= )=first(e)= ( ( g(e) g(e)是是 ll(1) ll(1) 文法。文法。( (接上頁(yè)接上頁(yè)) ) 2.構(gòu)造 ll(1) 分析表： 花括號(hào)花括號(hào)內(nèi)內(nèi)是求得的是求得的選擇集合！選擇集合！ f t t e e ) ( # 2 1 it t - - 2 2 ftft 2 2 | | 1 1, ,) ), ,# # f - i f - i i i | (e) | (e) ( ( e - tee - te i i, ,( ( e e - -

31、 1 1 tete 1 1 | | ) ), ,# # t - ftt - ft i,(i,( g(e):g(e):( (接上頁(yè)接上頁(yè)) ) 符號(hào)串 a+b# 的ll(1)分析過(guò)程：查分析表： 操 作剩余序列 w x 分析棧# ( + 匹配成功 ) b # +1# et1 :push(et1) b # +e# e :push( ) + b # +t# e t : push(i) + b # a f tf ( a 匹配成功 ) + b # a i i :push(tf) + b # a t e t ：push(et) a+b # a+b # a e# e : push(tf) b # b t#

32、e t ok # # :push ( ) # #t # e t :push ( ) #e# e ( b 匹配成功) # b i i : push（i） # b f tf# e# et# e # et分析表控制程序 lr( ) lr( )分析法是指從分析法是指從左左到右到右掃描掃描、最、最左左歸約歸約( (lrlr) )之意；它屬于自底向上分析方法。之意；它屬于自底向上分析方法。 常用的算法有常用的算法有l(wèi)r(0)lr(0)和和lr(1)lr(1)等，其中括號(hào)內(nèi)的等，其中括號(hào)內(nèi)的數(shù)數(shù)是指不查看是指不查看(0)(0)或只查看或只查看一一個(gè)當(dāng)前符號(hào)個(gè)當(dāng)前符號(hào)(1)(1)，即可，即可確定當(dāng)前句型的確定

33、當(dāng)前句型的句柄句柄。5.4 lr( )5.4 lr( )分析法分析法 利用一個(gè)利用一個(gè)分析表分析表，登記，登記選擇選擇句柄產(chǎn)生式句柄產(chǎn)生式的知識(shí)；的知識(shí)； 利用一個(gè)利用一個(gè)分析棧分析棧，記錄分析過(guò)程；，記錄分析過(guò)程；【分析算法分析算法】依次讀取依次讀取單詞，單詞，并進(jìn)行如下操作：并進(jìn)行如下操作： 當(dāng)棧頂出現(xiàn)當(dāng)棧頂出現(xiàn)句柄句柄時(shí)，時(shí)，規(guī)約規(guī)約之，否則之，否則移進(jìn)移進(jìn)。 5.4.1. lr( )5.4.1. lr( )分析法基本概念分析法基本概念 lr( ) lr( ) 分析法的基本要點(diǎn)有三：分析法的基本要點(diǎn)有三：1. 1. 什么是什么是lrlr（）分析法？（）分析法？【例例5.85.8】 g(z

34、): z-abad, a-bc| g(z): z-abad, a-bc|c, b-bb|cc, b-bb|c 2. lr( )2. lr( )分析法分析過(guò)程示例：分析法分析過(guò)程示例： 符號(hào)串符號(hào)串 abccdabccd 最左歸約過(guò)程最左歸約過(guò)程: : 符號(hào)串符號(hào)串 abccd abccd 的語(yǔ)法樹(shù)：的語(yǔ)法樹(shù)： abccdabccd 的語(yǔ)法樹(shù)的語(yǔ)法樹(shù) a b c c da b c c db bb ba az z 歸約過(guò)程歸約過(guò)程的的句柄句柄：句柄句柄次序次序 c cbbbb c cabadabadabccdabccd =. .abbcdabbcd =. .abcdabcd =. .abadaba

35、d =. . z z 句柄產(chǎn)生式句柄產(chǎn)生式 操操 作作 剩余串剩余串 w w 分析棧分析棧 移進(jìn)移進(jìn),next,next d # d # c c# a# a 歸約，歸約， a - c a - c # # d d# a b# a b 移進(jìn)移進(jìn),next,next # # d d# a b# a b 歸約，歸約， z - abad z - abad # # a b a# a b a ok ok # # # b - bb b - bb b - c b - c 移進(jìn)移進(jìn),next,next c d # c d # c c# a# a 移進(jìn)移進(jìn),next ,next b c c d # b c c d

36、# a a# # 歸約，歸約， d # d # c c # a b# a b 歸約，歸約， d # d # c c# a b# a b 移進(jìn)移進(jìn),next,next c c d # c c d # b b# # b b b b z z a a a a b b c c c c d d句句柄柄( (接上頁(yè)接上頁(yè)) ) 利用利用分析棧分析棧記錄行分析過(guò)程：記錄行分析過(guò)程：【注注】 何時(shí)棧頂出現(xiàn)何時(shí)棧頂出現(xiàn)句柄？句柄？怎樣求當(dāng)前怎樣求當(dāng)前句柄產(chǎn)生式句柄產(chǎn)生式 ？設(shè)設(shè) 待分析的符號(hào)串待分析的符號(hào)串: abccd#abccd#語(yǔ)法樹(shù)語(yǔ)法樹(shù)3. 3. 有限自動(dòng)機(jī)有限自動(dòng)機(jī)用作用作句柄識(shí)別器：句柄識(shí)別器： 如

37、何確認(rèn)首次出現(xiàn)的如何確認(rèn)首次出現(xiàn)的 c c 的父親是的父親是 b b, ,而不是而不是 a a ？g(z): z - abadg(z): z - abad a - bc | a - bc | c c b - bb | c b - bb | c 句柄句柄一定一定出現(xiàn)于出現(xiàn)于某某一個(gè)產(chǎn)生式的一個(gè)產(chǎn)生式的右部右部； 歸約過(guò)程中如何確認(rèn)歸約過(guò)程中如何確認(rèn)句柄句柄？ 是否是句柄是否是句柄，還要看，還要看其其所在符號(hào)串中的所在符號(hào)串中的位置位置。 怎樣判斷棧頂出現(xiàn)的怎樣判斷棧頂出現(xiàn)的句柄句柄不是不是 bcbc, ,而是而是 c c ? ? 顯然是錯(cuò)誤的顯然是錯(cuò)誤的( (從文法中可判定：從文法中可判定：aa

38、aa不能相鄰不能相鄰!) !) 若用若用 bcbc 歸約，則有歸約，則有 a abcbccd aacd(cd aacd( ) ) =. . 若用若用 a a作父親，則有作父親，則有 a abcbccd abacd(cd abacd( ) ) =. .顯然是錯(cuò)誤的顯然是錯(cuò)誤的( (從文法中可判定：從文法中可判定：acac不能相鄰不能相鄰! !語(yǔ)語(yǔ)法法樹(shù)樹(shù) 我們討論如下兩個(gè)問(wèn)題：我們討論如下兩個(gè)問(wèn)題：# #abc cd#abc cd#分析棧分析棧 擴(kuò)展文法，使擴(kuò)展文法，使文法符號(hào)文法符號(hào)附有附有位置位置信息：信息： 增設(shè)一個(gè)產(chǎn)生式增設(shè)一個(gè)產(chǎn)生式( (如：如：z- zz- z ) )， 帶有帶有位置

39、位置編編碼的碼的文法符號(hào)文法符號(hào)，稱(chēng)為，稱(chēng)為文法出現(xiàn)文法出現(xiàn)。g(z)g(z)并把產(chǎn)生式并把產(chǎn)生式右端符號(hào)順序編碼，作為右端符號(hào)順序編碼，作為位置位置( (狀態(tài)狀態(tài)) )信息信息: :【注注】 由于由于文法出現(xiàn)文法出現(xiàn)比比文法符號(hào)文法符號(hào)多了一個(gè)位置信息，多了一個(gè)位置信息， 在分析時(shí)，如果用在分析時(shí)，如果用文法出現(xiàn)文法出現(xiàn)代替代替文法符號(hào)文法符號(hào)，是否有助于，是否有助于句柄句柄的確認(rèn)呢？的確認(rèn)呢？ 句柄識(shí)別器的構(gòu)造方法句柄識(shí)別器的構(gòu)造方法 利用利用擴(kuò)展文法擴(kuò)展文法構(gòu)造構(gòu)造句柄識(shí)別器句柄識(shí)別器： 若把若把擴(kuò)展文法擴(kuò)展文法中的中的位置號(hào)位置號(hào)看成看成狀態(tài)狀態(tài)，那么，那么就可用就可用有限自動(dòng)機(jī)有限自

40、動(dòng)機(jī)描述描述如下：如下： 對(duì)每個(gè)產(chǎn)生式，構(gòu)造自動(dòng)機(jī)，用以識(shí)別自己的符對(duì)每個(gè)產(chǎn)生式，構(gòu)造自動(dòng)機(jī)，用以識(shí)別自己的符號(hào)串；號(hào)串； (0,z)=1;(0,z)=1; 預(yù)見(jiàn)預(yù)見(jiàn) 某個(gè)某個(gè)非終結(jié)符非終結(jié)符，也就，也就預(yù)見(jiàn)預(yù)見(jiàn) 其所有其所有產(chǎn)產(chǎn)生式的頭符號(hào)生式的頭符號(hào); ;于是各產(chǎn)生式的于是各產(chǎn)生式的子自動(dòng)機(jī)子自動(dòng)機(jī)可可并接并接在一起在一起。 【表示表示】: : 0 0狀態(tài)狀態(tài) 預(yù)見(jiàn)預(yù)見(jiàn) z z 后變換為后變換為 1 1狀態(tài)狀態(tài) ！ 設(shè)編碼設(shè)編碼0 0作為自動(dòng)機(jī)的作為自動(dòng)機(jī)的開(kāi)始狀態(tài)開(kāi)始狀態(tài)，第二個(gè)產(chǎn)生式，構(gòu)造第二個(gè)產(chǎn)生式，構(gòu)造自動(dòng)機(jī)自動(dòng)機(jī)：則則 第一個(gè)產(chǎn)生式，構(gòu)造第一個(gè)產(chǎn)生式，構(gòu)造自動(dòng)機(jī)自動(dòng)機(jī)： (0,a

41、)=2;(0,a)=2; (2,b)=3;(2,b)=3; (3,a)=4;(3,a)=4; (4,d)=5;(4,d)=5; 句柄識(shí)別器句柄識(shí)別器的自動(dòng)機(jī)構(gòu)造示例：的自動(dòng)機(jī)構(gòu)造示例：其中：其中：r(j)r(j) 歸約函數(shù)歸約函數(shù)( (即即 按序號(hào)為按序號(hào)為(j)(j)的的產(chǎn)生式產(chǎn)生式歸約！歸約！) )； 移進(jìn)狀態(tài)：移進(jìn)狀態(tài)： 歸約狀態(tài)：歸約狀態(tài)：b - bb - b9 9 b b1010 (4)(4)| c| c11 11 (5)(5)z - zz - z1 1 (0)(0)z z - a- a2 2 b b3 3 a a4 4 d d5 5 (1)(1)a - ba - b6 6 c c7

42、 7 (2)(2)| | c c8 8 (3)(3)g(z)g(z) 符號(hào)說(shuō)明符號(hào)說(shuō)明 0 0，2 2，3 3，4 4，6 6，9 9 ； 0 01111+ +z za ab bb bb bb bc cc ca ad db bc cokokr(3)r(3)r(1)r(1)r(2)r(2)r(4)r(4)r(5)r(5)c c 由由擴(kuò)展文擴(kuò)展文法法到到句柄識(shí)別句柄識(shí)別器器的構(gòu)造過(guò)程的構(gòu)造過(guò)程如右圖所示：如右圖所示：【例例5.85.8】 5 5，7 7，8 8，1010，1111； 分析結(jié)束分析結(jié)束( (okok) )。 接受狀態(tài)：接受狀態(tài)： 1 1 0 01111+ +z za ab bb bb

43、 bb bc cc ca ad db bc cokokr rr rr rr rr rc c 根據(jù)根據(jù)句柄識(shí)別器句柄識(shí)別器進(jìn)行進(jìn)行l(wèi)rlr分析過(guò)程：分析過(guò)程： 根據(jù)根據(jù)句柄識(shí)別器句柄識(shí)別器， abccd# abccd# 識(shí)別過(guò)程：識(shí)別過(guò)程：(#(#0 0, ,a a) )=(#=(#0 0a a2 2b b9 9b b1010, ,c c) )=(#=(#0 0a a2 2b b3 3a a4 4, ,d d) )=(#=(#0 0a a2 2, ,b b) ) =(#=(#0 0a a2 2b b9 9, ,c c) )=(#=(#0 0a a2 2b b9 9c c1111, ,c c) )

44、=(#(#0 0a a2 2b b3 3, ,c c) ) = = (#(#0 0a a2 2b b3 3c c8 8, ,d d) )=(#(#0 0a a2 2b b3 3a a4 4d d5 5, ,# #) )=( (# #0 0z z1 1, ,# #) )=0k=0k 句柄識(shí)別器句柄識(shí)別器又稱(chēng)又稱(chēng)“活前綴圖活前綴圖”: : 意思是在意思是在最左最左歸約歸約過(guò)程中，識(shí)別了過(guò)程中，識(shí)別了句柄句柄，實(shí)際上也就識(shí)別了以，實(shí)際上也就識(shí)別了以句句柄柄為后綴的該句型為后綴的該句型( (規(guī)范句型規(guī)范句型) )的前部符號(hào)串。的前部符號(hào)串。注注b - bb - b9 9 b b1010 (4)(4)|

45、 c| c11 11 (5)(5)z - zz - z1 1 (0)(0)z z - a- a2 2 b b3 3 a a4 4 d d5 5 (1)(1)a - ba - b6 6 c c7 7 (2)(2)| | c c8 8 (3)(3)句句柄柄【例例5.85.8】文法的文法的句柄識(shí)別器句柄識(shí)別器: :+ +lr(0)lr(0)分析器的基本組成：分析器的基本組成：lr(0)lr(0)分析法要求文法應(yīng)是分析法要求文法應(yīng)是 lr(0lr(0）文法）文法。lr(0)lr(0)分析表分析表 lr(0)lr(0)控制器控制器 lr( lr(0 0) )中的中的0 0, ,是指是指不必查看當(dāng)前符號(hào)不

46、必查看當(dāng)前符號(hào)就可確就可確認(rèn)認(rèn)句柄句柄之意；之意；5.4.2 lr(0)5.4.2 lr(0)分析器設(shè)計(jì)分析器設(shè)計(jì)1. 1. lr(0)lr(0)文法文法及其判定及其判定 句柄識(shí)別器中，句柄識(shí)別器中，移進(jìn)移進(jìn)和和歸約歸約不沖突不沖突；即；即 移進(jìn)和歸約不同時(shí)發(fā)生！移進(jìn)和歸約不同時(shí)發(fā)生！ 滿足下述特點(diǎn)的文法稱(chēng)為滿足下述特點(diǎn)的文法稱(chēng)為 lr(0)lr(0)文法文法。例例5.8 5.8 文法，就是文法，就是 lr(0)lr(0)文法，請(qǐng)看：文法，請(qǐng)看： 歸約歸約時(shí)不必查看當(dāng)前符號(hào)；時(shí)不必查看當(dāng)前符號(hào)；【算法算法】 根據(jù)根據(jù)句柄識(shí)別器，句柄識(shí)別器，填寫(xiě)填寫(xiě) lr(0)lr(0)分析表：分析表： 若若

47、(i,x)=k,x(v(i,x)=k,x(vn n+v+vt t),),則則 r(i,x):= r(i,x):= xkxk ; ; 若若 狀態(tài)狀態(tài)i i 標(biāo)記有（標(biāo)記有（- -，r(j),r(j), 則則 對(duì)任何對(duì)任何 a (va (vt t+#+#），）， r(i,a):= r(i,a):= r(j)r(j) ; ; r(1,#):= r(1,#):= okok 。 2. lr(0)2. lr(0)分析表構(gòu)造分析表構(gòu)造 擴(kuò)展文法，擴(kuò)展文法，構(gòu)造句柄識(shí)別器；構(gòu)造句柄識(shí)別器； lr()lr()分析表分析表是是 lr()lr()分析法的分析法的知識(shí)表知識(shí)表, ,是是句柄識(shí)句柄識(shí)別器別器的一種機(jī)內(nèi)的

48、一種機(jī)內(nèi)表示形式：表示形式：狀狀態(tài)態(tài)編編碼碼終結(jié)符終結(jié)符 + #+ #非終結(jié)符非終結(jié)符 r(_,_):r(_,_):0 1 0 1 a a # # z z n nakakokokzkzkr(j)r(j)r(j)r(j) 0 01111+ +z za ab bb bb bb bc cc ca ad db bc cokokr rr rr rr rr rc clr(0)lr(0)分析表分析表【例例5.85.8】文法文法構(gòu)造過(guò)程：構(gòu)造過(guò)程： 9 9 10 10 z z a a 1 1 5 5 0 0 4 4 8 8 d d # # 6 6 7 7 11 11 3 3 2 2 b b c c b b a

49、 a b b1010c c1111 b b9 9r r(4)(4)r r(4)(4)r r(4)(4)r r(4)(4)r r(4)(4) z z1 1 a a4 4 ok okr r(1)(1)r r(1)(1)r r(1)(1)r r(1)(1)r r(1)(1) a a2 2d d5 5r r(3)(3)r r(3)(3)r r(3)(3)r r(3)(3)r r(3)(3)r r(5)(5)r r(2)(2) r r(5)(5)r r(2)(2)c c7 7r r(2)(2)r r(2)(2)r r(2)(2)r r(5)(5)r r(5)(5)r r(5)(5)c c8 8 b b6

50、 6 b b3 3 b b9 9c c11113. lr(0)3. lr(0)控制程序設(shè)計(jì)控制程序設(shè)計(jì)開(kāi)始開(kāi)始push(#0)push(#0)next(w)next(w)查查lr(0)lr(0)分析表分析表r(xk,w)=?r(xk,w)=?r=r=空空? ?y yerrerrr=okr=ok結(jié)束結(jié)束r=r=r(j)r(j)r=wir=wipush wipush wi 則則 push ai;push ai;取取 a - a - (j) (j) pop( pop( );); 若若 r(xk,a)=air(xk,a)=ai xk xk 棧頂棧頂文法出現(xiàn)文法出現(xiàn)；歸約歸約移進(jìn)移進(jìn)lr( )lr( )

51、控制器控制器n n lr(0) lr(0)分析法小結(jié)示例分析法小結(jié)示例g(z): z - abadg(z): z - abad a - bc | a - bc | c c b - bb | c b - bb | c【例例5.85.8】文法文法: : 擴(kuò)展文法，使擴(kuò)展文法，使文法符號(hào)文法符號(hào)附有附有位置位置信息：信息： b - bb - b9 9 b b1010 (4)(4)| c| c11 11 (5)(5)z - zz - z1 1 (0)(0)z z - a- a2 2 b b3 3 a a4 4 d d5 5 (1)(1)a - ba - b6 6 c c7 7 (2)(2)| | c

52、c8 8 (3)(3) 由由擴(kuò)展文法擴(kuò)展文法構(gòu)造構(gòu)造句柄識(shí)別器：句柄識(shí)別器： 0 01111+ +z za ab bb bb bb bc cc ca ad db bc cokokr(3)r(3)r(1)r(1)r(2)r(2)r(4)r(4)r(5)r(5)c c 0 01111+ +z za ab bb bb bb bc cc ca ad db bc cokokr rr rr rr rr rc c 9 9 10 10 z z a a 1 1 5 5 0 0 4 4 8 8 d d # # 6 6 7 7 11 11 3 3 2 2 b b c c b b a a b b1010c c1111

53、 b b9 9r r(4)(4)r r(4)(4)r r(4)(4)r r(4)(4)r r(4)(4) z z1 1 a a4 4 ok okr r(1)(1)r r(1)(1)r r(1)(1)r r(1)(1)r r(1)(1) a a2 2d d5 5r r(3)(3)r r(3)(3)r r(3)(3)r r(3)(3)r r(3)(3)r r(5)(5)r r(2)(2) r r(5)(5)r r(2)(2)c c7 7r r(2)(2)r r(2)(2)r r(2)(2)r r(5)(5)r r(5)(5)r r(5)(5)c c8 8 b b6 6 b b3 3 b b9 9c

54、 c1111 由句柄識(shí)別由句柄識(shí)別器構(gòu)造器構(gòu)造lr(0)lr(0)分分析表：析表： lr(0) lr(0)分析法分析法分析過(guò)程分析過(guò)程示例：示例： 剩余串剩余串 操操 作作 w w 分析棧分析棧#0 a2 #0 a2 b9b9 b10b10 push(c8),next(w) push(c8),next(w) d# d# c c#0 a2#0 a2 reduce(3)reduce(3) # # d d#0 a2 b3#0 a2 b3 push(d5),next(w) push(d5),next(w) # # d d#0 #0 a2 b3a2 b3 reduce(1)reduce(1) # #0

55、#0 a2 b3 a4a2 b3 a4 okok # #0#0 d# d# d# d# cd# cd# ccd# ccd# bccd# bccd# push(c11),next(w) push(c11),next(w) c c#0 a2#0 a2 push(a2),next(w) push(a2),next(w) a a#0 #0 reduce(4)reduce(4) c c reduce(5)reduce(5) c c#0 a2 b9#0 a2 b9 push(b9),next(w) push(b9),next(w) b b#0#0 a2 a2 b9 b9 c11c11 b3 b3 c8c8

56、 a4 a4 d5 d5 z1 z1查分析表查分析表查產(chǎn)生式查產(chǎn)生式控制程序控制程序符號(hào)串：符號(hào)串：abccdabccd# #【例例5.95.9】lr(0)lr(0)分析法示例分析法示例1 1： 構(gòu)造下述文法的構(gòu)造下述文法的lr(0)lr(0)分析表：分析表： g(z)g(z)： z - aab , a - ca | d z - aab , a - ca | d 0 0+ +z za aa ad db bc ca aokokr(1)r(1)r(2)r(2)r(3)r(3)c cd d 構(gòu)造句柄識(shí)別器：構(gòu)造句柄識(shí)別器： 擴(kuò)展文法擴(kuò)展文法：g(z) z- zg(z) z- z1 1 (0) (0)

57、 z - a z - a2 2 a a3 3 b b4 4 (1)(1) a - c a - c5 5 a a6 6 (2)| d (2)| d7 7 (3)(3) 設(shè)計(jì)設(shè)計(jì)lr(0) lr(0) 分析表：分析表：r(3)r(3)r(2)r(2) d7 d7 r(1) r(1) d7 d7 d d z1 z1 z z a6 a6 a3 a3 a a ok ok 1 1 c5 c5 5 5 a2 a2 0 0 r(1) r(1) (1) (1) r(1) r(1) r(1) r(1) 4 4r(3)r(3)r(2)r(2) # #r(2)r(2)r(2)r(2) r(2) r(2) 6 6r(3

58、)r(3)r(3)r(3) r(3) r(3) 7 7 b4 b4 3 3 c5 c5 2 2 c c b b a a 0 0+ +z za aa ad db bc ca aokokr(1)r(1)r(2)r(2)r(3)r(3)c cd d【例例5.105.10】左遞歸文法的左遞歸文法的lr(0)lr(0)分析表構(gòu)造：分析表構(gòu)造： d d z z a a 1 1 5 5 0 0 4 4 # # 6 6 3 3 2 2 c c b b a a 0 0+ +z za aa ad db bc cokokr(1)r(1)r(2)r(2)r(3)r(3)z-zz-z1 1(0);(0); z -az

59、-a2 2a a3 3b b4 4(1);(1); a -aa -a3 3c c5 5(2)|d(2)|d6 6(3)(3)g(z)g(z)【注注】為了使為了使句柄識(shí)別句柄識(shí)別器器是是確定機(jī)確定機(jī)，左遞歸產(chǎn)，左遞歸產(chǎn)生式生式(2)(2)中的中的a a要與要與(1)(1)中中的的a a編碼相同編碼相同!?,!?, r r(3)(3) r r(2)(2) r r(1)(1) d d6 6 z z1 1 a a3 3 ok okr r(2)(2) r r(2)(2) r r(2)(2) r r(2)(2) a a2 2r r(1)(1) r r(1)(1) r r(1)(1) r r(1)(1)r

60、r(3)(3) r r(3)(3) r r(3)(3) r r(3)(3) c c5 5 b b4 4 【例例5.115.11】lr(0)lr(0)分析法示例分析法示例1 1 構(gòu)造下述文法的構(gòu)造下述文法的lr(0)lr(0)分析表：分析表： g(z) z - aab , a - ac | dg(z) z - aab , a - ac | d 擴(kuò)展文法：擴(kuò)展文法：g(z) z- zg(z) z- z1 1 (0) (0) z - a z - a2 2 a a3 3 b b4 4 (1)(1) a - a a - a5 5c c6 6 (2)| d(2)| d7 7 (3)(3) 構(gòu)造可歸前綴圖：