【正文】 號串的中間程序。設計目的與任務：通過本課程設計教學所要求達到的目的是：對詞法分析工作流程進行總體設計和詳細設計，最終用C語言來設計一個簡單詞法分析器，實現(xiàn)對源程序的詞法分析功能，對輸入程序去除注釋，并以二元式形式輸出程序中所有單詞。正則表達式到NFA 在編譯系統(tǒng)中，詞法分析階段是整個編譯系統(tǒng)的基礎。對于單詞的識別，有限自動機FA是一種十分有效的工具。有限自動機由其映射f是否為單值而分為確定的有限自動機DFA和非確定的有限自動機NFA。在非確定的有限自動機NFA中，由于某些狀態(tài)的轉移需從若干個可能的后續(xù)狀態(tài)中進行選擇，故一個NFA對符號串的識別就必然是一個試探的過程。這種不確定性給識別過程帶來的反復，無疑會影響到FA的工作效率。而DFA引擎在任意時刻必定處于某個確定的狀態(tài)，它搜索是無需象NFA一樣必須記錄所有的可能路徑（trace multiple possible routes through the NFA），這也是DFA運行效率高于NFA的原因。而已經(jīng)證明DFA是NFA的一個特例，即對于每一個NFA M存在一個DFA M’’，使得L(M)=L(M’’)。設計目的與任務通過本課程設計教學所要求達到的目的是：充分理解和掌握NFA，DFA以及NFA確定化過程的相關概念和知識，編程實現(xiàn)對輸入的任意正規(guī)式轉換成NFA的形式輸出。NFA的確定化有限自動機理論是描述詞法規(guī)則的基本理論。一條詞法規(guī)則表示一個正規(guī)表達式(又叫正規(guī)式)，而一個正規(guī)式又可化為一個DFA(確定有窮自動機)，這個有限自動機可用來識別詞法規(guī)則所定義的所有單詞符號。把程序設計語言的所有詞法規(guī)則都構造出相應的有限自動機,就得到一個詞法分析器。然后,再轉換為計算機可識別的程序就能自動實現(xiàn)詞法的分析和檢查。在實際應用中，用NFA(不確定有窮自動機)識別詞法存在不確定和狀態(tài)的冗余,因而,就要將NFA(不確定有窮自動機)轉換為DFA(確定有窮自動機),消除了不可到達和不確定。設計目的與任務通過本課程設計教學所要求達到的目的是：掌握從NFA到DFA的轉換，以及用子集法把NFA轉換成DFA理論，編程實現(xiàn)將NFA(不確定有窮自動機)轉換為DFA(確定有窮自動機)。DFA的最小化確定性有限自動機(DFA ,Deterministic Finite Automata)的最小化仍是有限自動機應用及實現(xiàn)方面的重要問題之一。DFA的最小化可以揭示狀態(tài)之間的內(nèi)在聯(lián)系，便于其存儲實現(xiàn)，便于建立用DFA描述的任務模型，一些理論問題也與最小化思想有關。DFA的最小化是指,構造一個與之等價且狀態(tài)數(shù)最小的DFA,即等價最小DFA。許多文獻給出了一個最小化算法，算法的思想是，構造狀態(tài)集的一個劃分，再將這個劃分中的每個子集作為新的狀態(tài)，從而得到等價最小DFA。DFA的最小化可以揭示狀態(tài)之間的內(nèi)在聯(lián)系，便于其存儲實現(xiàn),便于建立用DFA描述的任務模型，一些理論問題也與最小化思想有關。語法分析之LL(1)文法通過該課程設計了解了程序語言的自上而下的語法分析過程,提高了編程能力,能使我們了解編程語言更多的細節(jié) 設計目的與任務（1）讀入文法（2）求出first(), follow()（3）判斷是否為LL(1)文法（4）若是，構造分析表；（5）輸入一個字符串看是否是文法的一個句子。算符優(yōu)先文法一個文法，如果它的任一產(chǎn)生式的右邊都不含有兩個相繼（并列）的非終結符，即不 含有如下形式的產(chǎn)生式的右部：?QR?則我們稱該文法為算符文法。假設文法中的任意兩個終結符之間最多只有一個優(yōu)先關系，則該文法稱為算符優(yōu)先文法。該課程設計按照求,(P),(P)各兩條規(guī)則，求出各非終結符的集。然后按照算符優(yōu)先算法求出各終結符的算符優(yōu)先關系，填寫算符優(yōu)先表，并將其輸出。LR(0)分析表的構造LR分析技術是一種有效的自下而上分析技術，是一種規(guī)范歸約，其中L表示從左到右掃描輸入串，R表示構造一個最右推導的逆過程。這種方法可以適用于很大一類上下無關文法的語法分析。LR方法的基本思想是：在規(guī)范歸約過程中，一方面記住已經(jīng)移進和歸約出的整個符號串，即記住“歷史”；另一方面根據(jù)所用的產(chǎn)生式推測未來可能碰到的輸入符號，即對未來進行“展望”。當一串貌似句柄的符號串呈現(xiàn)于分析棧的頂端時，我們希望能夠根據(jù)所記載的“歷史”和“展望”以及“現(xiàn)實”的輸入符號等三方面的材料，來確定棧頂?shù)姆杺魇欠駱嫵上鄬δ骋划a(chǎn)生式的句柄。LR分析器的核心部分是一張分析表。這張分析表包括兩部分，一是“動作”(ACTION)表，另一是“狀態(tài)轉換”(GOTO)表。對于一個文法，如果能用一個每步頂多向前檢查K個輸入符號的LR分析器進行分析，則這個文法就稱為LR(K)文法。本文研究的LR(0)文法即K=0時的文法。設計目的與任務本課程設計所設計目的與任務是：通過C語言程序實現(xiàn)LR(0)分析表的構造，熟練掌握LR(0)分析表的構造方法，即利用拓廣文法和構造項目集規(guī)范族的方法。了解LR(0)分析器的工作原理，并能利用LR(0)分析表對輸入串進行分析。逆波蘭表達式生成算法雖然源程序可以直接翻譯為目標語言代碼，但許多編譯程序采用了獨立于機器的、復雜性介于源語言和機器翻譯語言之間的中間語言：后綴式（逆波蘭表達式）等。這樣做的好處是：（1）便于進行與機器無關的代碼優(yōu)化工作；（2）使編譯程序改變目標機更容易；（3）使編譯程序的結構在邏輯上更為簡單明確。以中間語言為界面，編譯前端和后端的接口更清晰。設計目的與任務將非后綴式用來表示的算術表達式轉換為用逆波蘭式來表示的算術表達式，并能運行查看結果。表達式的中間代碼生成源程序可以直接翻譯為目標語言代碼，但是許多編譯程序卻采用了獨立于機器的、復雜性介于源語言和機器語言之間的中間語言。這樣我們可以做下面工作：（1）：便于進行與機器無關的代碼優(yōu)化工作；（2）：使編譯程序以改變目標機更容易；（3）：使編譯程序的結構在邏輯上更為簡單明確；而以中間語言為界面，編譯前端和后端的接口更清晰，表達式可以用四個域分別稱為OP、ORGORG2及RESULT來表示。四、時間安排《編譯原理課程設計》安排在第三學期進行，時間2周（1718周）。五、組織管理1．由院、系指派經(jīng)驗豐富的專業(yè)教師擔任指導教師。2．課程設計實行指導教師負責制，由指導教師全面負責課程設計的指導與管理工作。六、成績考核與評定學生課程設計結束后寫出總結報告，對設計的內(nèi)容和效果進行總結，按照學生在設計期間的表現(xiàn)，指導老師對每位學生寫出評語和鑒定，系課程設計領導小組組織答辯，最后確定每位學生課程設計成績，課程設計成績分為優(yōu)、良、中、及格和不及格五個等級。課程設計成績?yōu)槠綍r表現(xiàn)30%、設計報告50%、答辯20%。評分標準：① 優(yōu)秀：目的明確，態(tài)度端正，模范遵守學校的各項紀律。工作認真，積極 主動，吃苦耐勞，能出色的完成設計任務。撰寫了高質(zhì)量的總結報告。答辯準確流利。② 良好：目的明確，態(tài)度端正，能遵守學校的各項紀律，工作比較積極主動。能較好地完成設計任務，成績較突出，表現(xiàn)良好；撰寫了質(zhì)量比較高的實習報告。答辯較準確流利。③ 及格：目的明確，態(tài)度基本端正，能遵守學校紀律，在督促下能開展工作 并完成一定的設計任務，無大的違紀違規(guī)現(xiàn)象；撰寫了實習報告。通過了答辯。④ 不及格：實習態(tài)度端正，不能遵守實習單位的紀律，不服從領導，自由散漫，工作消極被動，不能完成實習任務，實習期間有失職、曠工、打架、酗酒等大的過失?；驘o實習報告，沒有通過答辯。2．成績評定依據(jù)上述考核內(nèi)容，最后采用優(yōu)（90分）、良（80～89分）、中（70～79分）及格（60～69分）、不及格（七、主要參考資料教材：《編譯原理及實踐》馮博琴等譯，機械工業(yè)出版社 教學參考書《程序設計語言與編譯》龔天富、侯文永編，電子工業(yè)出版社?！毒幾g原理》呂映芝、張素琴、蔣維杜主編，清華大學出版社，1998年《編譯原理》胡倫駿、徐蘭芳、劉建農(nóng)編，電子工業(yè)出版社2002年《編譯原理》（第二版）蔣立源、康慕寧主編，西北工業(yè)大學出版社，2002年《編譯原理習題精選》陳意云、張昱著，中國科技大學出版社，2002年《編譯原理習題與解析》 伍春香著，清華大學出版社，2001年《編譯原理實驗指導書》自編