編譯原理 第七章 lr分析法

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

1、第7章　LR分析第七章LR分析法課前索引【課前思考】　　◇復(fù)習(xí)自頂向下和自底向上語法分析思想的區(qū)別　　◇自底向上分析方法是一種移進-歸約過程　　◇算符優(yōu)先分析法是如何確定可歸約串的？　　◇什么是規(guī)范推導(dǎo)和規(guī)范歸約？它們之間有什么關(guān)系？　　◇什么是規(guī)范句型？　　◇什么是規(guī)范句型的句柄？　　◇移進-歸約過程是當分析的棧頂符號串形成句柄時就采取歸約動作　　◇自底向上分析法的關(guān)鍵問題是在分析過程中如何確定句柄。　　◇如何確定一個輸入符號串是否是所給文法的句子？【學(xué)習(xí)目標】　　本章將介紹自底向上分析的另一種方法，即LR分析法?！　?/p>

2、◇理解LR分析法的基本思想　　◇理解可歸前綴和子前綴概念　　◇理解識別活前綴的有限自動機概念　　◇掌握LR分析器的構(gòu)造思想和方法　　◇對給定的文法能構(gòu)造LR(0)、SLR(1)、LALR(1)、LR(1)四種分析器，并能判斷所給文法是四種分析器的哪幾類?！　　髮o定的輸入符號串能用構(gòu)造的分析器判斷該輸入串是否是所給文法的句子　　◇了解某些二義性文法在LR分析中的應(yīng)用?！緦W(xué)習(xí)指南】　　LR分析法的歸約過程是規(guī)范推導(dǎo)的逆過程，所以LR分析過程是一種規(guī)范歸約過程。LR分析法正是給出一種能根據(jù)當前分析棧中的符號串(通常以狀態(tài)表示

3、)和向右順序查看輸入串的K個(K≥0)符號就可唯一地確定分析器的動作是移進還是歸約和用哪個產(chǎn)生式歸約，因而也就能唯一地確定句柄。其中LR(0)分析器是在分析過程中不需向右查看輸入符號，因而它對文法的限制較大，然而，它是構(gòu)造其它LR類分析器的基礎(chǔ)。因此，首先應(yīng)學(xué)好LR(0)項目集規(guī)范族構(gòu)造的基本原理和方法。當K=1時，已能滿足當前絕大多數(shù)高級語言編譯程序?qū)崿F(xiàn)的需要。SLR(1)分析是為學(xué)習(xí)LR(1)分析做準備，LR(1)項目集族的構(gòu)造是LALR(1)分析器的構(gòu)造原理和基礎(chǔ)。LALR(1)分析器是當前大多數(shù)高級程序設(shè)計語言編

4、譯程序所采用的語法分析技術(shù)，也是編譯程序語法分析器自動構(gòu)造工具YACC(將在第13章介紹）的實現(xiàn)基本原理。由此，LR(0)、SLR(1)、LALR(1)、LR(1)四種分析器的構(gòu)造方法都必須深入理解和掌握。【難重點】　　◇可歸前綴和子前綴概念　　◇識別活前綴的有限自動機概念　　◇對可歸前綴為規(guī)范歸約的句柄的理解　　◇構(gòu)造LR(1)項目集族時搜索符的計算　　◇LR分析器的關(guān)鍵部分是分析表的構(gòu)造　　◇第7章　LR分析對給定的文法能構(gòu)造LR(0)、SLR(1)、LALR(1)、LR(1)四種分析器　　◇當一個文法能構(gòu)造出不含移

5、進-歸約或歸約-歸約沖突時的LR(0)/SLR(1)/LALR(1)/LR(1)分析表時，稱這個文法為LR(0)/SLR(1)/LALR(1)/LR(1)文法?！　　髮o定的文法能判斷是四種LR類文法的哪幾類　　◇了解某些二義性文法在LR分析中的應(yīng)用【知識結(jié)構(gòu)】第7章　LR分析在第6章中已經(jīng)討論過，自底向上分析方法是一種移進-歸約過程，當分析的棧頂符號串形成句柄時就采取歸約動作，因而自底向上分析法的關(guān)鍵問題是在分析過程中如何確定句柄。LR分析法正是給出一種能根據(jù)當前分析棧中的符號串(通常以狀態(tài)表示)和向右順序查看輸入串的

6、K個(K≥0)符號就可唯一地確定分析器的動作是移進還是歸約和用哪個產(chǎn)生式歸約，因而也就能唯一地確定句柄。LR分析法的歸約過程是規(guī)范推導(dǎo)的逆過程，所以LR分析過程是一種規(guī)范歸約過程。LR(K)分析方法是1965年Knuth提出的，括號中的K表示向右查看輸入串符號的個數(shù)。這種方法比起自頂向下的LL(K)分析方法和算符優(yōu)先分析方法對文法的限制要少得多，也就是說對于大多數(shù)用無二義性上下文無關(guān)文法描述的語言都可以用相應(yīng)的LR分析器進行識別，而且這種方法還具有分析速度快，能準確、即時地指出出錯位置。它的主要缺點是對于一個實用語言文法

7、的分析器的構(gòu)造工作量相當大，K愈大構(gòu)造愈復(fù)雜，實現(xiàn)相當困難。目前對于真正實用的編譯程序，所采用的LR分析器都是借助于美國Bell實驗室1974年推出的"一個編譯器的編譯器-YACC"來實現(xiàn)的。它能接受一個用BNF描述的滿足LALR(1)的上下文無關(guān)文法并將自動構(gòu)造LALR(1)語法分析器?！　”菊聦⒅饕榻BLR分析的基本思想和當K≤1時LR分析器的基本構(gòu)造原理和方法。其中LR(0)分析器是在分析過程中不需向右查看輸入符號，因而它對文法的限制較大，對絕大多數(shù)高級語言的語法分析器是不能適用的，然而，它是構(gòu)造其它LR類分析器的

8、基礎(chǔ)。當K=1時，已能滿足當前絕大多數(shù)高級語言編譯程序的需要。因此，我們將著重介紹LR(0)、SLR(1)、LALR(1)、LR(1)四種分析器的構(gòu)造方法。其中SLR(1)和LALR(1)分別是LR(0)和LR(1)的一種改進。7.1LR分析概述一個LR分析器由3個部分組成：　　(1)總控程序，也可以稱為驅(qū)動程序。對