【正文】 種有效的自下而上分析技術(shù)，是一種規(guī)范歸約，其中L表示從左到右掃描輸入串，R表示構(gòu)造一個(gè)最右推導(dǎo)的逆過程。這種方法可以適用于很大一類上下無關(guān)文法的語法分析。LR方法的基本思想是：在規(guī)范歸約過程中，一方面記住已經(jīng)移進(jìn)和歸約出的整個(gè)符號串，即記住“歷史”；另一方面根據(jù)所用的產(chǎn)生式推測未來可能碰到的輸入符號，即對未來進(jìn)行“展望”。當(dāng)一串貌似句柄的符號串呈現(xiàn)于分析棧的頂端時(shí)，我們希望能夠根據(jù)所記載的“歷史”和“展望”以及“現(xiàn)實(shí)”的輸入符號等三方面的材料，來確定棧頂?shù)姆杺魇欠駱?gòu)成相對某一產(chǎn)生式的句柄。LR分析器的核心部分是一張分析表。這張分析表包括兩部分，一是“動(dòng)作”(ACTION)表，另一是“狀態(tài)轉(zhuǎn)換”(GOTO)表。對于一個(gè)文法，如果能用一個(gè)每步頂多向前檢查K個(gè)輸入符號的LR分析器進(jìn)行分析，則這個(gè)文法就稱為LR(K)文法。本文研究的LR(0)文法即K=0時(shí)的文法。設(shè)計(jì)目的與任務(wù)本課程設(shè)計(jì)所設(shè)計(jì)目的與任務(wù)是：通過C語言程序?qū)崿F(xiàn)LR(0)分析表的構(gòu)造，熟練掌握LR(0)分析表的構(gòu)造方法，即利用拓廣文法和構(gòu)造項(xiàng)目集規(guī)范族的方法。了解LR(0)分析器的工作原理，并能利用LR(0)分析表對輸入串進(jìn)行分析。逆波蘭表達(dá)式生成算法雖然源程序可以直接翻譯為目標(biāo)語言代碼，但許多編譯程序采用了獨(dú)立于機(jī)器的、復(fù)雜性介于源語言和機(jī)器翻譯語言之間的中間語言：后綴式（逆波蘭表達(dá)式）等。這樣做的好處是：（1）便于進(jìn)行與機(jī)器無關(guān)的代碼優(yōu)化工作；（2）使編譯程序改變目標(biāo)機(jī)更容易；（3）使編譯程序的結(jié)構(gòu)在邏輯上更為簡單明確。以中間語言為界面，編譯前端和后端的接口更清晰。設(shè)計(jì)目的與任務(wù)將非后綴式用來表示的算術(shù)表達(dá)式轉(zhuǎn)換為用逆波蘭式來表示的算術(shù)表達(dá)式，并能運(yùn)行查看結(jié)果。表達(dá)式的中間代碼生成源程序可以直接翻譯為目標(biāo)語言代碼，但是許多編譯程序卻采用了獨(dú)立于機(jī)器的、復(fù)雜性介于源語言和機(jī)器語言之間的中間語言。這樣我們可以做下面工作：（1）：便于進(jìn)行與機(jī)器無關(guān)的代碼優(yōu)化工作；（2）：使編譯程序以改變目標(biāo)機(jī)更容易；（3）：使編譯程序的結(jié)構(gòu)在邏輯上更為簡單明確；而以中間語言為界面，編譯前端和后端的接口更清晰，表達(dá)式可以用四個(gè)域分別稱為OP、ORGORG2及RESULT來表示。四、時(shí)間安排《編譯原理課程設(shè)計(jì)》安排在第三學(xué)期進(jìn)行，時(shí)間2周（1718周）。五、組織管理1．由院、系指派經(jīng)驗(yàn)豐富的專業(yè)教師擔(dān)任指導(dǎo)教師。2．課程設(shè)計(jì)實(shí)行指導(dǎo)教師負(fù)責(zé)制，由指導(dǎo)教師全面負(fù)責(zé)課程設(shè)計(jì)的指導(dǎo)與管理工作。六、成績考核與評定學(xué)生課程設(shè)計(jì)結(jié)束后寫出總結(jié)報(bào)告，對設(shè)計(jì)的內(nèi)容和效果進(jìn)行總結(jié)，按照學(xué)生在設(shè)計(jì)期間的表現(xiàn)，指導(dǎo)老師對每位學(xué)生寫出評語和鑒定，系課程設(shè)計(jì)領(lǐng)導(dǎo)小組組織答辯，最后確定每位學(xué)生課程設(shè)計(jì)成績，課程設(shè)計(jì)成績分為優(yōu)、良、中、及格和不及格五個(gè)等級。課程設(shè)計(jì)成績?yōu)槠綍r(shí)表現(xiàn)30%、設(shè)計(jì)報(bào)告50%、答辯20%。評分標(biāo)準(zhǔn)：① 優(yōu)秀：目的明確，態(tài)度端正，模范遵守學(xué)校的各項(xiàng)紀(jì)律。工作認(rèn)真，積極 主動(dòng)，吃苦耐勞，能出色的完成設(shè)計(jì)任務(wù)。撰寫了高質(zhì)量的總結(jié)報(bào)告。答辯準(zhǔn)確流利。② 良好：目的明確，態(tài)度端正，能遵守學(xué)校的各項(xiàng)紀(jì)律，工作比較積極主動(dòng)。能較好地完成設(shè)計(jì)任務(wù)，成績較突出，表現(xiàn)良好；撰寫了質(zhì)量比較高的實(shí)習(xí)報(bào)告。答辯較準(zhǔn)確流利。③ 及格：目的明確，態(tài)度基本端正，能遵守學(xué)校紀(jì)律，在督促下能開展工作 并完成一定的設(shè)計(jì)任務(wù)，無大的違紀(jì)違規(guī)現(xiàn)象；撰寫了實(shí)習(xí)報(bào)告。通過了答辯。④ 不及格：實(shí)習(xí)態(tài)度端正，不能遵守實(shí)習(xí)單位的紀(jì)律，不服從領(lǐng)導(dǎo)，自由散漫，工作消極被動(dòng)，不能完成實(shí)習(xí)任務(wù)，實(shí)習(xí)期間有失職、曠工、打架、酗酒等大的過失?；驘o實(shí)習(xí)報(bào)告，沒有通過答辯。2．成績評定依據(jù)上述考核內(nèi)容，最后采用優(yōu)（90分）、良（80～89分）、中（70～79分）及格（60～69分）、不及格（七、主要參考資料教材：《編譯原理及實(shí)踐》馮博琴等譯，機(jī)械工業(yè)出版社 教學(xué)參考書《程序設(shè)計(jì)語言與編譯》龔天富、侯文永編，電子工業(yè)出版社。《編譯原理》呂映芝、張素琴、蔣維杜主編，清華大學(xué)出版社，1998年《編譯原理》胡倫駿、徐蘭芳、劉建農(nóng)編，電子工業(yè)出版社2002年《編譯原理》（第二版）蔣立源、康慕寧主編，西北工業(yè)大學(xué)出版社，2002年《編譯原理習(xí)題精選》陳意云、張昱著，中國科技大學(xué)出版社，2002年《編譯原理習(xí)題與解析》 伍春香著，清華大學(xué)出版社，2001年《編譯原理實(shí)驗(yàn)指導(dǎo)書》自編第三篇：編譯原理課程設(shè)計(jì)課 程 設(shè) 計(jì) 報(bào) 告設(shè)計(jì)題目：一個(gè)簡單文法的編譯器前端的設(shè)計(jì)與實(shí)現(xiàn)班級： 計(jì)算機(jī)1206 組長學(xué)號：201239 組長姓名：閆智宣 指導(dǎo)教師：李曉華 設(shè)計(jì)時(shí)間：2014年12月[在此處鍵入]設(shè)計(jì)分工組長學(xué)號及姓名： 20123974閆智宣分工：語法分析，四元式生成，目標(biāo)代碼優(yōu)化及生成 組員1學(xué)號及姓名：20123977廖峭 分工：詞法分析，錯(cuò)誤處理 組員2學(xué)號及姓名：20123959郭天龍分工：符號表生成，語義動(dòng)作插入，操作界面[在此處鍵入]摘要編譯原理課程設(shè)計(jì)是通過C語言編譯器相關(guān)子系統(tǒng)的設(shè)計(jì)，進(jìn)一步加深對編譯器構(gòu)造的理解；第一部分詞法分析，設(shè)計(jì)各單詞的狀態(tài)轉(zhuǎn)換圖，并為不同的單詞設(shè)計(jì)種別碼，制作掃描器識別一個(gè)個(gè)單詞，返回值為識別碼的序號，返回Token序列。將詞法分析器設(shè)計(jì)成供語法分析器調(diào)用的子程序。詞法分析器具備預(yù)處理功能。將不翻譯的注釋等符號先濾掉，只保留要翻譯的符號串，即要求設(shè)計(jì)一個(gè)供詞法分析調(diào)用的預(yù)處理子程序；第二部分，語法分析，用遞歸下降法，實(shí)現(xiàn)對表達(dá)式、各種說明語句、控制語句進(jìn)行語法分析。若語法正確，則用語法制導(dǎo)翻譯法進(jìn)行語義翻譯；生成并打印出語法樹；若語法錯(cuò)誤，要求指出出錯(cuò)性質(zhì)和出錯(cuò)位置（行號）。我們還做了附加功能，即編譯后端，有中間代碼優(yōu)化，生成目標(biāo)代碼匯編語言。通過此次課程設(shè)計(jì)，提高了我們的獨(dú)立分析問題、解決問題的能力，以及系統(tǒng)軟件設(shè)計(jì)的能力； 提高程序設(shè)計(jì)能力、程序調(diào)試能力，團(tuán)結(jié)協(xié)作能力關(guān)鍵詞：詞法分析，語法分析，四元式生成，錯(cuò)誤處理，符號表生成，語義動(dòng)作插入，中間代碼優(yōu)化，生成目標(biāo)代碼 [在此處鍵入]目錄摘要 設(shè)計(jì)任務(wù) 設(shè)計(jì)要求（流程） 詞法分析模塊 功能 數(shù)據(jù)結(jié)構(gòu) 算法 語法分析模塊 數(shù)據(jù)結(jié)構(gòu) 符號表模塊 數(shù)據(jù)結(jié)構(gòu) 四元式模塊[在此處鍵入] 數(shù)據(jù)結(jié)構(gòu) 語義動(dòng)作分析模塊 數(shù)據(jù)結(jié)構(gòu) 錯(cuò)誤處理模塊 數(shù)據(jù)結(jié)構(gòu) 目標(biāo)代碼模塊 數(shù)據(jù)結(jié)構(gòu) 程序流程圖 程序說明 實(shí)驗(yàn)結(jié)果 。、體會和建議。[在此處鍵入]編譯器是將C語言翻譯為匯編語言代碼的計(jì)算機(jī)程序。編譯器將源程序（source language）編寫的程序作為輸入，翻譯產(chǎn)生目標(biāo)語言（target language）機(jī)器代碼的等價(jià)程序。通常地，源程序?yàn)楦呒壵Z言（highlevel language），C語言程序，而目標(biāo)則是 機(jī)器語言的目標(biāo)代碼（object code），也就是可以在計(jì)算機(jī)硬件中運(yùn)行的機(jī)器代碼軟件程序。這一過程可以表示為：源程序→編譯器 →目標(biāo)機(jī)器代碼程序?qū)W生在學(xué)習(xí)《編譯原理》課程過程中，結(jié)合各章節(jié)的構(gòu)造編譯程序的基本理論，要求用C語言描述及上機(jī)調(diào)試，實(shí)現(xiàn)一個(gè) C編譯程序（包括詞法分析，語法分析等重要子程序），使學(xué)生將理論與實(shí)際應(yīng)用結(jié)合起來，受到軟件設(shè)計(jì)等開發(fā)過程的全面訓(xùn)練，從而提高學(xué)生軟件開發(fā)的能力。 要求：（1）設(shè)計(jì)詞法分析器設(shè)計(jì)各單詞的狀態(tài)轉(zhuǎn)換圖，并為不同的單詞設(shè)計(jì)種別碼。將詞法分析器設(shè)計(jì)成供語法分析器調(diào)用的子程序。功能包括：。將不翻譯的注釋等符號先濾掉，只保留要翻譯的符號串，即要求設(shè)計(jì)一個(gè)供詞法分析調(diào)用的預(yù)處理子程序；； [在此處鍵入]（種別碼，屬性值，行號）。（2）語法分析要求用學(xué)習(xí)過的自底向上或自頂向下的分析方法等，實(shí)現(xiàn)對表達(dá)式、各種說明語句、控制語句進(jìn)行語法分析。若語法正確，則用語法制導(dǎo)翻譯法進(jìn)行語義翻譯；生成并打印出語法樹；若語法錯(cuò)誤，要求指出出錯(cuò)性質(zhì)和出錯(cuò)位置（行號）。（流程）本節(jié)主要分析程序的代碼結(jié)構(gòu)和代碼工程文件的劃分。（程序由幾個(gè)類組成: Token類和Variable類SymbolTable類ObjectCode類Lexical類Grammar類Four_Yuan類Action類ErrorItem類，分別為詞法分析和語法分析類。工程分為幾個(gè)文件：,,Four_Yuan,cs,）。本程序采用C語言以面向?qū)ο蟮乃枷刖帉?，程序分為幾部分：詞法分析（Lexical），語法分析（Grammer），目標(biāo)代碼生成（ObjectCode）。Lexical類主要的工作是詞法分析獲取Token。Grammer類的主要工作是根據(jù)Lexical類詞法分析之后的Token進(jìn)行語法分析，生成語法樹，最后并輸出語法樹。在處理過程中，Token類的對象作為Lexical類的一個(gè)成員變量，配合Grammer類進(jìn)行語法分析。工程文件總體上是按照九個(gè)類的格局分為十個(gè)文件，分別是九個(gè)類的聲明文件和實(shí)現(xiàn)文件。,,Four_Yuan,cs,，他們分別是Lexical類聲明文件、Lexical類實(shí)現(xiàn)文件、Grammer類聲明文件、Grammer類實(shí)現(xiàn)文件。[在此處鍵入]程序流程在程序中，Lexical類的對象(Token)作為Grammer類中的一個(gè)成員變量，配合Grammer類進(jìn)行語法分析。它們的關(guān)系是這樣的：Grammer類的一個(gè)成員變量temp首先對源程序刪除注釋，然后進(jìn)行詞法分析獲取所有Token，并將獲取的Token存儲在Token對象的tokenList（List類型）中。然后Grammer類的語法分析程序就根據(jù)tokenList中的Token進(jìn)行語法分析，生成語法樹，最后打印語法樹。同時(shí)，這也是程序的流程。[在此處鍵入] 詞法分析模塊 Lexical類主要的工作是詞法分析獲取Token序列。詞法分析階段的代碼被封裝成一個(gè)類——Lexical，Token中主要是Lexical類的聲明代碼。Lexical類對外提供的函數(shù)主要有：static public int RecogId(string str, int i)，static public int RecogDig(string str,int i)，static public int RecogOperator(string str, int i)，static public int RecogBound(string str, int i)，以上幾個(gè)函數(shù)構(gòu)成了詞法分析的骨架，在Lexical類中還有其他成員變量和函數(shù)，主要作為這三個(gè)函數(shù)處理過程的中間步驟，為這三個(gè)函數(shù)服務(wù)。Lexical類的代碼結(jié)構(gòu)和主要的成員變量和函數(shù)及其含義如下圖所示：算法的基本任務(wù)是從字符串表示的源程序中識別出具有獨(dú)立意義的單詞符號，其基本思想是[在此處鍵入]根據(jù)掃描到單詞符號的第一個(gè)字符的種類，拼出相應(yīng)的單詞符號。主程序示意圖：主程序示意圖如圖31所示。⑴ 關(guān)鍵字表的初值。關(guān)鍵字作為特殊標(biāo)識符處理，把它們預(yù)先安排在一張表格中（稱為關(guān)鍵字表），當(dāng)掃描程序識別出標(biāo)識符時(shí)，查關(guān)鍵字表。如能查到匹配的單詞，則該單詞為關(guān)鍵字，否則為一般標(biāo)識符。（2）程序中需要用到的主要變量為type和number 掃描子程序的算法思想：首先設(shè)置3個(gè)變量： [在此處鍵入]①token用來存放構(gòu)成單詞符號的字符串； ②number用來整型單詞；③type用來存放單詞符號的種別碼。Token定義Token定義:Token類型（TokenType）: 語法分析模塊語法分析是編譯過程的一個(gè)邏輯階段。語法分析的功能是在詞法分析的基礎(chǔ)上將單詞序列組合成各類語法短語，如“程序”，“語句”，“表達(dá)式” 數(shù)據(jù)結(jié)構(gòu)下圖為實(shí)現(xiàn)語法分析的類Grammar，屬性與方法的作用都已說明 在此處鍵入]下面終結(jié)符與非終結(jié)符意義B程序開始Z 數(shù)據(jù)類型，如int,char,float等V 標(biāo)識符S 語句P 語句塊E 加減算術(shù)表達(dá)式D 逗號表達(dá)式T 乘除算術(shù)表達(dá)式C 關(guān)系表達(dá)式L 邏輯表達(dá)式Q 標(biāo)識符或圓括號e 表示空i 表示標(biāo)識符 a)函數(shù)文法BZV()S[[在此處鍵入]b)語句塊文法PSP|eS{P} c)語句文法表達(dá)式語句文法SV=Egoto語句文法Si:SSgoto iif語句文法Sif(E)S[else S]while語句文法Swhile(E)S聲明語句文法SZVDD,VD|=ED|e d)表達(dá)式文法ET|E+T|ETTF|T*F|T/FCC|CL|C==C|C=LLQ|Lamp。amp。Q|L||i|(E)|!Q對應(yīng)于每個(gè)文法編寫如下遞歸下降子程序主程序（B）[在此處鍵入] [在此處鍵入] 符號表模塊進(jìn)行符號表的儲存，添加，更新，查找，保存標(biāo)識符活躍信息以及輸出。 數(shù)據(jù)結(jié)構(gòu)在此處鍵入] 四元式模塊四元式為中間代碼，編譯程序進(jìn)行完語義分析后，先生成中間代碼作為過渡，此時(shí)中間代碼與目標(biāo)代碼已經(jīng)比較相似 數(shù)據(jù)結(jié)構(gòu)[ 在此處鍵入]在語法分析中嵌入相應(yīng)的語義動(dòng)作，生成四元式 數(shù)據(jù)結(jié)構(gòu)[[在此處鍵入] GEQ(+)()(*)(/)(+,i1,i2,t)PUSH(i)ASSI(=)(=,t,_,POP)LABER(i)(lb,_,_,i)GOTO(i)(gt,_,_,i)IF(if)(if,a,_,_)EL(el)(el,_,_,_)IE(ie)(ie,_,_,_)WH()(wh,_,_,_)DO()(do,a,_,_)WE(we)(we,_,_,_) 錯(cuò)誤處理模塊 保存運(yùn)行時(shí)發(fā)現(xiàn)的錯(cuò)誤，儲存行號已經(jīng)詳細(xì)信