資源描述：
《ch5-自頂向下語法分析方法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第五章自頂向下語法分析在上一章中用正規(guī)式描述了單詞符號的結(jié)構(gòu)，并研究了如何用有限自動機構(gòu)造詞法分析器的問題。由于正規(guī)式與正規(guī)文法是等價的，它們的描述能力有限，而高級語言的語法結(jié)構(gòu)適合用上下文無關(guān)文法描述，因此，我們將上下文無關(guān)文法用作語法分析的基礎(chǔ)。本章介紹編譯程序構(gòu)造中的一些典型的語法分析方法。1語法分析就是識別由詞法分析給出的單詞符號序列是否是給定文法的正確句子(程序).語法分析常用的方法:自頂向下分析與自底向上分析.而自底向上分析又可分為:算符優(yōu)先分析與LR分析.自頂向下分析也稱面向目標(biāo)的分析方法,也就是從文法的開始符號出發(fā)企圖推導(dǎo)出與輸入的單詞串完全相匹配的句子.自頂向下分析方法分為
2、:確定的和不確定的.確定的分析方法需要對文法有一定的限制;而不確定的方法是一種窮舉的試探方法.25.1確定的自頂向下分析若有文法G1[s]：S->pA
3、qBA->cAd
4、aB->dB
5、b構(gòu)造輸入串W=pccadd的語法樹。該文法的特點：1）每個產(chǎn)生式的右部都由終結(jié)符號開始；2）若兩個產(chǎn)生式有相同的左部，則它們的右部由不同的終結(jié)符開始。確定的自頂向下分析方法是從文法的開始符號出發(fā)，如何根據(jù)當(dāng)前的輸入符號唯一確定選用哪個產(chǎn)生式替換相應(yīng)非終結(jié)符往下推導(dǎo)，或構(gòu)造一顆相應(yīng)的語法樹。這種文法完全可以根據(jù)當(dāng)前的輸入符號決定選擇哪個產(chǎn)生式往下推導(dǎo),因此分析過程是唯一確定的.3文法G2[S]為：S->ApS-
6、>BqA->aA->cAB->bB->dB給出輸入串W=ccap的推導(dǎo)過程。該文法的特點：1）產(chǎn)生式的右部不全是由終結(jié)符開始；2）若兩個產(chǎn)生式有相同的左部，則它們的右部是由不同的終結(jié)符或非終結(jié)符開始；3）文法中無空產(chǎn)生式。4文法G3[S]為：S->aAS->dA->bASA->?給出W=abd的推導(dǎo)過程。5相關(guān)概念：FIRST集【定義】設(shè)G=(VN,VT,S,P)是上下文無關(guān)文法,又設(shè)?是文法G的任一字符串，定義?的首符集FIRST(?)={a
7、??a…,a∈VT}若??ε，ε∈FIRST(?)FIRST(?)是從?可推導(dǎo)出的所有首終結(jié)符或可能的ε。**6相關(guān)概念：FOLLOW集【定義】假設(shè)
8、S是文法G的開始符號，對于G的任何非終結(jié)符A，定義非終結(jié)符A的后繼符號的集合：FOLLOW(A)={a
9、S?...Aa...，a∈VT}。特別是，若S?...A，則規(guī)定#∈FOLLOW（A）。FOLLOW(A)是G的所有句型中緊接在A之后出現(xiàn)的終結(jié)符或#。這里#作為輸入串的結(jié)束符。因此,當(dāng)文法中含有形如:A->?A->?的產(chǎn)生式時,其中A?VN,?,??V*,當(dāng)?和?不同時推導(dǎo)出空時,則對非終結(jié)符A的替換仍可唯一地確定候選.**7相關(guān)概念：SELECT集【定義】假設(shè)A??是文法G的任一規(guī)則，定義規(guī)則A??的選擇集合SELECT為：SELECT(A??)=其中A∈VN，?∈(VN?VT)*，F(xiàn)
10、IRST(?)若???(FIRST(?)-{?})?FOLLOW(A)若?=>ε*/*8LL(1)文法這里的第一個L表示從左到右掃描字符串，第二個L表示最左推導(dǎo)，1表示每一步只需向前看一個符號。一個上下文無關(guān)文法G是LL(1)文法， 當(dāng)且僅當(dāng)對G中每個非終結(jié)符A的任何兩個不同的規(guī)則A→α
11、?，滿足:SELECT(A→α)?SELECT(A→?)=?其中α、?中至多只有一個能推導(dǎo)出?串。95.2LL(1)文法的判別判斷LL(1)文法的步驟:1.求出能夠推出?的非終結(jié)符1)初始化2)掃描文法的產(chǎn)生式a)刪除所有右部含有終結(jié)符的產(chǎn)生式,若以某一非終結(jié)符為左部的所有產(chǎn)生式都被刪除,則將數(shù)組中對應(yīng)該非
12、終結(jié)符的標(biāo)記修改為“否”;b)若某一非終結(jié)符的某一產(chǎn)生式右部為?,則將數(shù)組中對應(yīng)該非終結(jié)符的標(biāo)志置為“是”,并從文法中刪除該非終結(jié)符的所有產(chǎn)生式.10判別步驟(續(xù))3)掃描產(chǎn)生式右部的每一符號a)若所掃描到的非終結(jié)符號在數(shù)組中的對應(yīng)標(biāo)志是“是”,則刪去該非終結(jié)符,若這使得產(chǎn)生式右部為空,則對產(chǎn)生式左部的非終結(jié)符在數(shù)組中對應(yīng)的標(biāo)志改為“是”,并刪去該非終結(jié)符為左部的所有產(chǎn)生式;b)若所掃描到的非終結(jié)符號在數(shù)組中的對應(yīng)標(biāo)志是“否‘,則刪去該產(chǎn)生式,若這使得產(chǎn)生式左部非終結(jié)符的有關(guān)產(chǎn)生式都被刪去,則將數(shù)組中該非終結(jié)符對應(yīng)的標(biāo)志改成”否“.4)重復(fù)3),直到掃描完一遍文法的產(chǎn)生式,數(shù)組中非終結(jié)符對應(yīng)
13、的特征再沒有改變?yōu)橹?112.計算FIRST集1)計算每一文法符號X的FIRST集-----FIRST(X)(a)若X?VT,則FIRST(X)={X};(b)若X?VN且有產(chǎn)生式X->a….,a?VT,則a?FIRST(X);(c)若X?VN且有產(chǎn)生式X->?,則??FIRST(X);(d)X?VN且Y1,…,Yi都?VN,而有產(chǎn)生式X->Y1…Yn.當(dāng)Y1,…,Yi-1=>?(其中1?i?n),則FIRS
