編譯原理第五章 自頂向下語法分析方法

《編譯原理第五章 自頂向下語法分析方法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第5章　自頂向下語法分析方法第五章自頂向下語法分析方法課前索引【課前思考】　　為了了解自頂向下（自上而下）分析的一般過程和問題，請(qǐng)學(xué)員首先回顧在"文法和語言"一章中介紹的有關(guān)基本概念：　　◇句子、句型和語言的定義是什么？　　◇什么叫最左推導(dǎo)？　　◇什么叫最右推導(dǎo)和規(guī)范推導(dǎo)？　　◇什么叫確定的自頂向下語法分析？　　◇自頂向下語法分析是從文法的開始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找與輸入符號(hào)匹配的推導(dǎo)。　　◇確定的自頂向下語法分析中用的是哪種推導(dǎo)？　　◇在確定的自頂向下語法分析過程中，當(dāng)以同一個(gè)非終結(jié)符

2、為左部的產(chǎn)生式有多個(gè)不同右部時(shí)，如何選擇用哪個(gè)產(chǎn)生式的右部替換當(dāng)前的非終結(jié)符？　　◇確定的自頂向下語法分析對(duì)文法有何限制？【學(xué)習(xí)目標(biāo)】　　確定的自頂向下分析方法雖對(duì)文法有一定的限制，但由于實(shí)現(xiàn)方法簡(jiǎn)單、直觀，便于手工構(gòu)造或自動(dòng)生成語法分析器，因而仍是目前常用的方法之一。要求學(xué)員通過本章的學(xué)習(xí)后達(dá)到以下要求：　　◇能夠?qū)σ粋€(gè)給定的文法判斷是否是LL(1)文法；　　◇能構(gòu)造預(yù)測(cè)分析表；　　◇能用預(yù)測(cè)分析方法判斷給定的輸入符號(hào)串是否是該文法的句子；　　◇能對(duì)某些非LL(1)文法做等價(jià)變換：　　　①消除左遞

3、歸　　?、谔崛∽蠊惨蜃印　】赡軙?huì)變成LL(1)文法。這樣可擴(kuò)大自頂向下分析方法的應(yīng)用。【學(xué)習(xí)指南】　　確定的自頂向下分析由于實(shí)現(xiàn)方法簡(jiǎn)單、直觀、便于手工構(gòu)造，因此，仍是目前常用的語法分析方法之一，尤其對(duì)小型編譯器的實(shí)現(xiàn)較為適合。對(duì)初學(xué)編譯技術(shù)的學(xué)員也較容易入門。確定的自頂向下分析要求文法是LL(1)的，所以，能否用確定的自頂向下分析方法構(gòu)造語法分析器，首先必須對(duì)所給文法進(jìn)行判斷。由此構(gòu)造LL(1)分析器的關(guān)鍵問題是對(duì)文法的LL(1)判別。而判斷LL(1)文法時(shí)用到文法符號(hào)串的開始符號(hào)集合（FIRS

4、T集）和非終結(jié)符的后跟符號(hào)集合（FOLLOW集）的計(jì)算。本章的學(xué)習(xí)要求學(xué)員對(duì)給定的文法能熟練、準(zhǔn)確地計(jì)算出產(chǎn)生式右部符號(hào)串的開始符號(hào)集合和每個(gè)非終結(jié)符的后跟符號(hào)集合，只有這兩個(gè)集合的元素計(jì)算準(zhǔn)確無誤，才能對(duì)LL(1)文法的判斷得出正確結(jié)論，從而正確構(gòu)造LL(1)分析表。對(duì)非LL(1)文法的等價(jià)變換特別要注意的是：消除了左遞歸、提取了左公共因子后不一定就能滿足LL(1)文法的條件?！倦y重第5章　自頂向下語法分析方法點(diǎn)】　　語法分析是編譯程序的核心部分。語法分析的作用是識(shí)別由詞法分析給出的單詞符號(hào)序列是

5、否是給定文法的正確句子(程序)，目前語法分析常用的方法有自頂向下（自上而下）分析和自底向上（自下而上）分析兩大類。本章將主要介紹確定的自頂向下分析思想和對(duì)文法的要求。確定的自頂向下分析要求文法滿足LL(1)文法。本章主要介紹內(nèi)容為：　　◇LL(1)文法的定義和判別　　◇非LL(1)文法的等價(jià)變換　　◇確定的自頂向下分析方法　　◇遞歸子程序法（已在第2章應(yīng)用本章不重復(fù)）　　◇預(yù)測(cè)分析方法重點(diǎn):　?、貺L(1)文法的定義和判別　?、诜荓L(1)文法的等價(jià)變換　?、垲A(yù)測(cè)分析方法難點(diǎn):　　對(duì)一個(gè)文法如何判斷

6、是否是LL(1)文法，由于在判斷LL(1)文法時(shí)用到文法符號(hào)串的開始符號(hào)集合（FIRST集）和非終結(jié)符后跟符號(hào)集合（FOLLOW集）的計(jì)算，而一般學(xué)員往往因概念不清或不夠細(xì)心對(duì)這兩個(gè)集合的計(jì)算常常出錯(cuò)，導(dǎo)致判斷和分析結(jié)果的錯(cuò)誤。【知識(shí)結(jié)構(gòu)】第5章　自頂向下語法分析方法語法分析是編譯程序的核心部分。語法分析的作用是識(shí)別由詞法分析給出的單詞符號(hào)序列是否是給定文法的正確句子(程序)，目前語法分析常用的方法有自頂向下（自上而下）分析和自底向上（自下而上）分析兩大類。而自底向上分析又可分為算符優(yōu)先分析和LR分

7、析，這三種分析方法各有優(yōu)缺點(diǎn)。但都是當(dāng)今編譯程序構(gòu)造的實(shí)用方法，我們將在本章和第6、7章著重介紹它們的實(shí)現(xiàn)原理和技術(shù)?！　∽皂斚蛳路治龇ㄒ卜Q面向目標(biāo)的分析方法，也就是從文法的開始符號(hào)出發(fā)企圖推導(dǎo)出與輸入的單詞串完全相匹配的句子，若輸入串是給定文法的句子，則必能推出，反之必然出錯(cuò)。自頂向下分析法又可分為確定的和不確定的兩種，確定的分析方法需對(duì)文法有一定的限制，但由于實(shí)現(xiàn)方法簡(jiǎn)單、直觀，便于手工構(gòu)造或自動(dòng)生成語法分析器，因而仍是目前常用的方法之一。不確定的方法即帶回溯的分析方法，這種方法實(shí)際上是一種窮舉

8、的試探方法，因此效率低，代價(jià)高，因而極少使用，本章不做詳細(xì)介紹。為了了解自頂向下（自上而下）分析的一般過程和問題我們首先回顧在“文法和語言”一章中介紹的關(guān)于句子、句型和語言的定義及什么叫最左推導(dǎo)、最右推導(dǎo)和規(guī)范推導(dǎo)的基本概念。在確定的自頂向下語法分析中用的是最左推導(dǎo)。句型、句子、語言的定義句型:　　有文法G[S]，若Sx，且x∈V*則稱x是文法G[S]的句型。　　符號(hào)表示經(jīng)過0步或若干步的推導(dǎo)。句子:　　有文法G[S]，若Sx，且x∈VT*，則稱x是文法G[S]的句子