資源描述：
《編譯原理 第五章.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第5章自頂向下語(yǔ)法分析方法語(yǔ)法分析是編譯程序的核心部分，其作用是識(shí)別由詞法分析給出的單詞符號(hào)序列是否為給定文法的正確句子，目前常用的語(yǔ)法分析方法有兩大類(lèi)：l自頂向下分析：也稱(chēng)面向目標(biāo)的分析方法，也就是從文法的開(kāi)始符出發(fā)，試圖推導(dǎo)出與輸入單詞串相匹配的句子，分為確定的自頂向下分析和不確定的自頂向下分析兩種，常用的有遞歸子程序法和LL分析法。l自底向上分析：也稱(chēng)移進(jìn)—?dú)w約分析方法，從輸入單詞串開(kāi)始，試圖歸約到文法的開(kāi)始符。分為算符優(yōu)先分析和LR分析。（第6、7章講述）第5章自頂向下語(yǔ)法分析方法5.1確定的自頂
2、向下分析思想5.2LL（1）文法的判別5.3某些非LL（1）文法到LL（1）文法的等價(jià)變換5.4不確定的自頂向下分析思想5.5確定的自頂向下分析方法5.5.1遞歸子程序法5.5.2預(yù)測(cè)分析法5.1確定的自頂向下分析思想思想從文法的開(kāi)始符出發(fā)，根據(jù)當(dāng)前的輸入符號(hào)，確定選用哪個(gè)產(chǎn)生式替換相應(yīng)非終結(jié)符往下推導(dǎo)。若輸入串是給定文法的句子，則必能推出，否則出錯(cuò)。例5.1G1[S]：S→pA
3、qBA→cAd
4、a分析輸入串W=pccadd自頂向下推導(dǎo)過(guò)程：S＝〉pA＝〉pcAd＝〉pccAdd＝〉pccadd分析輸入串
5、W=pccadd自頂向下推導(dǎo)過(guò)程：S＝〉pA＝〉pcAd＝〉pccAdd＝〉pccaddSpA=〉SpdAcA=〉A(chǔ)cSpdAcAda=〉A(chǔ)cSpdAcAd可以根據(jù)當(dāng)前的輸入符號(hào)決定選擇哪個(gè)產(chǎn)生式往下推導(dǎo)，分析過(guò)程是唯一確定的。例5.2G2[S]：S→Ap
6、BqA→a
7、cAB→b
8、dB分析輸入串W=ccap自頂向下推導(dǎo)過(guò)程：S＝〉A(chǔ)p＝〉cAp＝〉ccAp＝〉ccapFIRST(Ap)={a,c},FIRST(Bq)={b,d}（下面定義）對(duì)同一非終結(jié)符（S）的不同的產(chǎn)生式右部，并且它們以非終結(jié)符開(kāi)始，在
9、推導(dǎo)過(guò)程中選用哪個(gè)產(chǎn)生，要看它們的開(kāi)始符號(hào)集合是什么。l對(duì)一個(gè)文法符號(hào)串的開(kāi)始符號(hào)集合定義如下：定義5.1設(shè)G=（VN，VT，P，S）是上下文無(wú)關(guān)文法，F(xiàn)IRST（α）={a
10、α＝〉aβ,a∈VT，α,β∈V*}若α＝〉ε，則規(guī)定ε∈FIRST（α）**例5.3G[S]:S→aA
11、dA→bAS
12、εw=abd的分析過(guò)程。自頂向下推導(dǎo)過(guò)程：S＝〉aA＝〉abAS＝〉abS＝〉abd,FOLLOW(A)={#,a,d}（下面定義）當(dāng)非終結(jié)符有不同的產(chǎn)生式右部，且有ε產(chǎn)生式時(shí)，選擇產(chǎn)生式進(jìn)行匹配要看該非終結(jié)符的后
13、跟符號(hào)集合。l定義一個(gè)文法符號(hào)的后跟符號(hào)集合如下：定義5.2設(shè)G=（VN，VT，P，S）是上下文無(wú)關(guān)文法，A∈VN，S是開(kāi)始符FOLLOW(A)={a
14、S＝〉μAβ,a∈VT，a∈FIRST(β),μ∈V*,β∈V+}若S＝〉μAβ,且β＝〉ε，則#∈FOLLOW(A)****也可定義為FOLLOW(A)={a
15、S＝〉...Aa....，a∈VT}若有S＝〉...A，則規(guī)定#∈FOLLOW(A)用‘#’作為輸入串的結(jié)束符，或稱(chēng)為句子括號(hào)，如：#輸入串#*l定義一個(gè)產(chǎn)生式的選擇集合如下：定義5.3選擇集合S
16、ELECT給定上下文無(wú)關(guān)文法的產(chǎn)生式A→α,A∈VN，α∈V*，如果α＝〉ε,則SELECT（A→α）=FIRST（α），如果α＝〉ε,則SELECT（A→α）=FIRST（α）{ε}∪FOLLOW(A)**定義5.4一個(gè)上下文無(wú)關(guān)文法是LL（1）文法的充分必要條件是，*每個(gè)非終結(jié)符的兩個(gè)不同產(chǎn)生式A→α，A→β，滿足：SELECT（A→α）∩SELECT（A→β）=Φ，其中α、β不能同時(shí)＝〉ε或者：一個(gè)上下文無(wú)關(guān)文法是LL（1）文法，當(dāng)且僅當(dāng)同一非終結(jié)符的各個(gè)產(chǎn)生式的可選集互不相交。LL（1）文法的含
17、義：第一個(gè)L表明自頂向下分析是從左向右掃描輸入串；第二個(gè)L表示分析過(guò)程中將用最左推導(dǎo)，1表示只需向右看一個(gè)符號(hào)便可決定選擇哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)。類(lèi)似也可以有LL（k）文法，一般k=1，2例5.4設(shè)文法G[S]為：S→aAS
18、bA→bA
19、ε則SELECT（S→aAS）={a}SELECT（S→b）=SELECT（A→bA）=SELECT（A→ε）=FOLLOW（A）=FIRST（S）={a，b}因?yàn)椋篠ELECT（S→aAS）∩SELECT（S→b）={a}∩=ΦSELECT（A→bA）∩S
20、ELECT（A→ε）=∩{a，b}≠Φ所以，文法G[S]不是LL（1）文法。5.2LL（1）文法的判別例5.5G[S]:S→AB
21、bCA→b
22、εB→aD
23、εC→AD
24、bD→aS
25、c判別步驟：1．求出能推出ε的非終結(jié)符SABCD是是是否否假定所給文法是經(jīng)過(guò)壓縮的，即文法中不包含多余規(guī)則，說(shuō)明判斷LL（1）文法的步驟。2．計(jì)算FIRST集◆對(duì)每一文法符號(hào)X∈V，計(jì)算FIRST（X）（a）若X∈VT，則FIRST（X）={X}
