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

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

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

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

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

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

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

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

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

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