自頂向下語法分析方法.ppt

《自頂向下語法分析方法.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第5章自頂向下語法分析方法語法分析（SyntaxAnalysis）是編譯程序的核心部分。詞法分析只是將字符形式的源程序中的各個(gè)單詞識(shí)別出來，形成單詞的機(jī)內(nèi)表示形式，但是這些單詞串如何構(gòu)成更大的語法成分——語句，那就由語法分析來完成。語法分析的主要任務(wù)就是“組詞成句”，即在詞法分析識(shí)別出單詞串的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，識(shí)別出各類語法成分，如“語句”、“程序”等。將完成語法分析任務(wù)的程序稱為語法分析程序，也稱為語法分析器或簡稱分析器。程序設(shè)計(jì)語言的語法結(jié)構(gòu)是用上下文無關(guān)文法描述的，因此，語法分析器的實(shí)現(xiàn)原理就是

2、按所給定的文法G，識(shí)別輸入符號(hào)串α是否為一個(gè)句子（即α∈L(G)成立嗎？），同時(shí)檢查和處理語法錯(cuò)誤。語法分析的關(guān)鍵是句型識(shí)別問題。給定一串單詞（即文法的終結(jié)符），怎樣知道它是不是該文法產(chǎn)生的一個(gè)句子呢？可以利用推導(dǎo)，或者利用語法樹來進(jìn)行判斷。一般來說，語法分析的過程就是為一個(gè)句子建立語法樹的過程。語法分析的方法很多，按照建立語法樹的不同方向，通常將語法分析分為兩類，一類是自頂向下分析法，另一類是自底向上分析法。本章主要介紹自頂向下分析法，自底向上分析法。第4章教學(xué)內(nèi)容語法分析的任務(wù)；確定的自頂向下語法分析的基本

3、思想；LL(1)文法的定義和判別方法；非LL(1)文法到LL(1)文法的等價(jià)變換；確定的自頂向下分析方法：遞歸下降分析法預(yù)測分析法自底向上語法分析的基本思想；短語、直接短語和句柄的定義，以及如何利用語法樹尋找短語、直接短語和句柄。自底向上語法分析方法：優(yōu)先分析法LR分析法一、自頂向下的語法分析思想【自頂向下（top-down）分析法的基本思想】自頂向下語法分析的基本思想是以文法的開始符號(hào)為樹根，采用最左推導(dǎo)，試圖自上而下地為輸入的單詞串構(gòu)造一棵語法樹。若語法樹的端末節(jié)點(diǎn)從左向右排列恰好是輸入串，則該輸入串就是文

4、法的句子，否則就不是。這種分析過程實(shí)質(zhì)是一種試探過程，是反復(fù)使用不同產(chǎn)生式來匹配輸入串的過程。示例【例4.1】設(shè)有以下文法G1[S]:S→aABA→bA

5、cB→dBe

6、de輸入串a(chǎn)bbcde的最左推導(dǎo)如下：S?aAB?abAB?abbAB?abbcB?abbcde因此，輸入串a(chǎn)bbcde是該文法G1的句子。下面從建立語法樹來看句子的推導(dǎo)過程。為了自頂向下地構(gòu)造輸入串a(chǎn)bbcde的語法樹，首先按文法的開始符號(hào)產(chǎn)生根節(jié)點(diǎn)S，再根據(jù)產(chǎn)生式規(guī)則自頂向下地生長這棵語法樹。語法樹的建立過程如圖所示。SaABbAbAcde自

7、頂向下分析法也稱面向目標(biāo)的分析方法，在對(duì)輸入串進(jìn)行最左推導(dǎo)的過程中，在選擇產(chǎn)生式時(shí)其實(shí)是一種試探方法，如果每一步選擇產(chǎn)生式來匹配的時(shí)候都能夠每選必中，則這種方法稱為確定的分析方法；否則在選擇產(chǎn)生式時(shí)面臨多種可能，不知道選擇哪一個(gè)產(chǎn)生式合適，就是不確定的分析方法。因此自頂向下分析法又可分為確定的和不確定的兩種，確定的分析方法對(duì)文法有一定的限制，但由于實(shí)現(xiàn)方法簡單、直觀，便于手工構(gòu)造或自動(dòng)生成語法分析器，因而仍是目前常用的方法之一。不確定的方法即帶回溯的分析方法，這種方法實(shí)際上是一種窮舉的試探方法，因此效率低，代價(jià)

8、高，因而極少使用。1.不確定的自頂向下分析不確定的自頂向下分析法的基本思想是，對(duì)任何輸入串α試圖用一切可能的辦法，從文法的開始符號(hào)出發(fā)，自上而下的為它建立一棵語法樹。如果試探成功，則α為相應(yīng)文法的句子，否則α就不是文法句子。這種分析過程本質(zhì)上是一種窮舉試探過程，是反復(fù)使用不同規(guī)則，謀求匹配輸入串的過程。因此這種匹配過程往往一次不能成功，需要重新匹配，稱為回溯。引起回溯的原因在于文法中關(guān)于某個(gè)非終結(jié)符的產(chǎn)生式有多個(gè)時(shí)，而根據(jù)面臨的輸入符無法唯一確定選擇哪個(gè)產(chǎn)生式來匹配，從而引起回溯。自頂向下分析法中存在的問題回溯

9、問題左遞歸問題回溯問題回溯時(shí)需要恢復(fù)到出錯(cuò)點(diǎn)位置，刪去曾經(jīng)匹配過的符號(hào)，還包括一些語義處理。因此處理回溯是一項(xiàng)復(fù)雜的工作，在回溯時(shí)，要清除在回溯之前編譯程序所做的大量記錄工作，然后重新開始記錄，這就降低了語法分析的效率。避免回溯是自頂向下語法分析中需要解決的問題之一?；厮莸木唧w表現(xiàn)回溯具體表現(xiàn)為下列兩種情況：1.由于相同左部的產(chǎn)生式的候選式的FIRST集交集不為空而引起回溯。2.由于相同左部非終結(jié)符的候選式存在能推導(dǎo)出ε的產(chǎn)生式，且該非終結(jié)符的FOLLOW集中含有其它候選式的FIRST集的元素。表現(xiàn)一示例由于相

10、同左部的產(chǎn)生式的候選式的FIRST集交集不為空而引起回溯：【例4．6】設(shè)有文法G6[S]為：S→xAyA→**

11、*串x*y的分析過程SxAy**(S,x)選擇產(chǎn)生式S→xAy當(dāng)前要替換的非終結(jié)符當(dāng)前要匹配的輸入符(A,*)可選擇兩個(gè)產(chǎn)生式A→**或A→*SxAy*回溯：回到出錯(cuò)點(diǎn)，重新選擇產(chǎn)生式A→*，成功原因上述文法發(fā)生回溯的原因就在于A的兩個(gè)產(chǎn)生式的候選式的第一個(gè)符號(hào)都是*，從而根