【正文】 一產(chǎn)生式的右邊都不含有兩個相繼（并列）的非終結(jié)符，即不 含有如下形式的產(chǎn)生式的右部：?QR?則我們稱該文法為算符文法。DFA的最小化可以揭示狀態(tài)之間的內(nèi)在聯(lián)系，便于其存儲實現(xiàn),便于建立用DFA描述的任務(wù)模型，一些理論問題也與最小化思想有關(guān)。DFA的最小化是指,構(gòu)造一個與之等價且狀態(tài)數(shù)最小的DFA,即等價最小DFA。DFA的最小化確定性有限自動機(DFA ,Deterministic Finite Automata)的最小化仍是有限自動機應(yīng)用及實現(xiàn)方面的重要問題之一。在實際應(yīng)用中，用NFA(不確定有窮自動機)識別詞法存在不確定和狀態(tài)的冗余,因而,就要將NFA(不確定有窮自動機)轉(zhuǎn)換為DFA(確定有窮自動機),消除了不可到達和不確定。把程序設(shè)計語言的所有詞法規(guī)則都構(gòu)造出相應(yīng)的有限自動機,就得到一個詞法分析器。NFA的確定化有限自動機理論是描述詞法規(guī)則的基本理論。而已經(jīng)證明DFA是NFA的一個特例，即對于每一個NFA M存在一個DFA M’’，使得L(M)=L(M’’)。這種不確定性給識別過程帶來的反復(fù)，無疑會影響到FA的工作效率。有限自動機由其映射f是否為單值而分為確定的有限自動機DFA和非確定的有限自動機NFA。正則表達式到NFA 在編譯系統(tǒng)中，詞法分析階段是整個編譯系統(tǒng)的基礎(chǔ)。詞法分析是編繹的基礎(chǔ)，執(zhí)行詞法分析的程序即為詞法分析器，它的任務(wù)是對輸入或給定的源程序，從左至右逐個字符進行掃描，產(chǎn)生一個個單詞符號，把作為字符串的源程序改造成單詞符號串的中間程序。4．答辯：課題的論述、測試及問題回答三、課程設(shè)計內(nèi)容詞法分析器的構(gòu)造：人們理解一個程序，起碼是在單詞級別上來思考。課程設(shè)計題目見“主要內(nèi)容”。盡量避免出現(xiàn)操作錯誤時出現(xiàn)死循環(huán)。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋。如果程序不能正常運行或運行過程中出現(xiàn)了不滿足算法思想的情況，寫出出現(xiàn)這一情況的原因或改進行的方法。二、教學(xué)基本要求1．設(shè)計和調(diào)試過程要規(guī)范化需求分析：將題目中要求的功能進行敘述分析，并且設(shè)計解決此問題的數(shù)據(jù)存儲結(jié)構(gòu)，（有些題目已經(jīng)指定了數(shù)據(jù)存儲的，按照指定的設(shè)計），設(shè)計或敘述解決此問題的算法，描述算法可以使用自然語言、偽代碼、或函數(shù)的方式。并進一步培養(yǎng)學(xué)生的抽象思維能力，進一步鞏固《編譯原理》課程所學(xué)知識。第二篇：《編譯原理課程設(shè)計》教學(xué)大綱《編譯原理課程設(shè)計》教學(xué)大綱課程名稱： 課程編號： 適用專業(yè)： 總 學(xué) 分： 總 周 時： 主 撰 人： 撰寫日期：一、目的與任務(wù)通過程序設(shè)計上機調(diào)試程序?qū)崿F(xiàn)算法，學(xué)習(xí)編譯程序調(diào)試技巧和設(shè)計編譯程序的一般原則，加深對詞法分析、語法分析、語義分析和中間代碼生成等編譯階段及實用編譯系統(tǒng)的認(rèn)識，初步掌握編譯程序構(gòu)造的基本原理與技術(shù), 從形式語言理論的角度, 進一步認(rèn)識與理解程序設(shè)計語言。其中設(shè)計經(jīng)驗總結(jié)可以包括下列方面：你在編程過程中花時多少？多少時間在紙上設(shè)計？多少時間上機輸入和調(diào)試？多少時間在思考問題？遇到了哪些難題？你是怎么克服的？你對你的軟件如何評價？你的收獲有哪些？ 評分教師對每個實驗結(jié)果進行評分(優(yōu)、良、中、及格、不及格)，記入成績。5．5 注意事項測試數(shù)據(jù)的設(shè)計：每組測試數(shù)據(jù)包括輸入數(shù)據(jù)、預(yù)期的輸出結(jié)果、實際的輸出結(jié)果和預(yù)期的是否相吻合（如果不吻合，實際輸出什么？可能錯誤的原因？檢查源代碼或設(shè)計進行查錯，紀(jì)錄結(jié)果）。??演示軟件，教師根據(jù)實際情況提出測試用例，學(xué)生作最后的修改和完善，教師評分。3．調(diào)試，教師幫助解決學(xué)生設(shè)計和調(diào)試中出現(xiàn)的難題。1．根據(jù)流程圖編制并輸入代碼，教師查看學(xué)生的設(shè)計，對設(shè)計提出修改意見。最后畫出較詳細(xì)的程序流程圖。同時對軟件進行需求分析，通過回答下面問題得到：1．軟件提供哪些功能？軟件有什么用？界面怎樣？怎樣使用該軟件？對輸入數(shù)據(jù)的格式有什么要求？用什么語言開發(fā)？怎樣測試該軟件？該軟件開發(fā)的進度如何安排？2．寫出以上問題的答案，然后自問：你的分析材料別人能非常清楚地看懂嗎？如果回答是肯定的，就可以搞設(shè)計了。請參考有關(guān)文檔資料。其功能非常強大，可用于任何語言的分析。編寫一個代碼生成程序編寫一個代碼生成程序，形成三地址程序并輸出到文件中，打印三地址程序。難度：一般。⑵同上的過程還可以進行：正偶數(shù)的判斷、自然數(shù)的判斷、定點數(shù)的判斷等。編出程序。難度：一般。工作量：一般。請參照C語言教材，編制一個軟件，輸入包含轉(zhuǎn)義符的字符串，輸出沒有轉(zhuǎn)義符的真實字符串。源程序掃描程序?qū)δ撤N高級語言的源程序進行分析，建立符號表，找出盡可能多的問題并輸出相關(guān)的出錯信息。（關(guān)于正則表達式的介紹參見另一文檔，）3 邏輯運算分析可對關(guān)系表達式進行分析，并得出結(jié)果。）n 文本搜索程序：在一連串文本中搜索所需的字符串。（以上涉及到正規(guī)式的方案難度較大，其他難度一般。u 方案3：只要包含正規(guī)式即可，當(dāng)名稱中包含該正規(guī)式，就輸出來：如輸入“(a|b)1”，輸出“a1,ab1245（含有b1）”；輸入“(a|b)*”，輸出“abc,a1,ab1245”。u 方案1：通配符，把“*、?”當(dāng)作通配符：如輸入“a*”，顯示“abc,a1,ab1245”；輸入“a?”，輸出“a1”。⑴字符串搜索程序：使用到正規(guī)式、詞法分析等，還需要有較大的設(shè)計技巧。難度：較難。難度和工作量同一元函數(shù)的計算。工作量：較大。如f(x)=3*sin(x/2+)+x^2等。工作量：中等。也可設(shè)計成其他專用函數(shù)計算程序，如冪函數(shù)計算、三角函數(shù)計算等。根據(jù)功能的不同可以分為：n 多項式函數(shù)計算程序：只處理多項式函數(shù)，如f(x)=x^3+x^2+5等。⑵函數(shù)表達式計算程序：這是一款能計算函數(shù)值的實用程序，輸入含有自變量x的函數(shù)表達式被接受后，可接著輸入自變量x的值，輸出函數(shù)值y的值。難度：難。工作量：中等。工作量：中等。n 整數(shù)表達式計算器：考慮負(fù)數(shù)。難度：較難。使用了編譯原理中的詞法分析、算符優(yōu)先分析等。題目大小適中。估計時間(150學(xué)時)，其中：；；、檢查問題、繪制流程圖、寫相關(guān)文檔，最后集成設(shè)計（實驗）報告并自行打印。要求進行簡單的需求分析、設(shè)計說明，寫出程序結(jié)構(gòu)框架，闡明設(shè)計思路、用到的原理和方法。第一篇：《編譯原理》課程設(shè)計教學(xué)大綱《編譯原理》課程設(shè)計教學(xué)大綱揭金良 2006．10．20 1 目的通過課程設(shè)計，將《編譯原理》的相關(guān)理論和技術(shù)運用到軟件開發(fā)中，提高學(xué)生的應(yīng)用程序設(shè)計能力，提高分析問題、解決問題的能力。內(nèi)容利用編譯原理的某種思想或方法，設(shè)計一個應(yīng)用程序，實現(xiàn)的具體內(nèi)容自擬（見下面的選題指導(dǎo)）。程序規(guī)模適中，著重于內(nèi)核功能。過程指導(dǎo)5．1 選題通過平時積累，找到適合于自己的應(yīng)用或某種軟件功能，該應(yīng)用能利用編譯原理中的某些理論。參考題目如下： 表達式計算器表達式計算器：這是一款算術(shù)表達式計算程序，通過輸入表達式達到計算的目的，可代替目前普遍使用的計算器。根據(jù)功能的不同可分為：⑴無符號整數(shù)表達式計算器：輸入無符號整數(shù)表達式，輸出結(jié)果。工作量：中等。難度：較難。n 定點實數(shù)表達式計算器：難度：較難。n 通用表達式計算器：。工作量：中等。使用了詞法分析、算符優(yōu)先分析。難度：較難。但要避免出現(xiàn)不同用，如不要設(shè)計成僅能處理f(x)=2^x的冪函數(shù)，因為這樣的函數(shù)利用普通編程就能實現(xiàn)，無法體現(xiàn)編譯原理。n 通用初等函數(shù)計算程序：能處理所有的初等函數(shù)的計算。難度：難（因為涉及到函數(shù)名稱和參數(shù)的識別問題）。n 二元或多元函數(shù)的計算：如f(x,y)=x^2+y^2等。⑶邏輯運算分析：輸入邏輯表達式串，對表達式進行分析，并得出結(jié)果。2 字符串搜索程序輸入要查找的字符串的正規(guī)表達式，軟件可在大量文本(要求不低于3000字符的文檔資料文件)中找到符合描述的字符串。根據(jù)功能的不同可以分為：n 名稱查找程序（類似于文件名）：存有大量的名稱，如abc,123,a1,ab1245等，輸入要查找的規(guī)則，找出符合規(guī)則的名稱。u 方案2：正規(guī)式，把“*”當(dāng)作“閉包”，把“|”當(dāng)作“或”：如輸入“(a|b)1”，輸出“a1”；輸入“(a|b)*c”，輸出“abc”。u 方案4：含有通配符的正規(guī)式，設(shè)“”表示任意字母，“$”表示任意數(shù)字（其他可再設(shè)多一點，如表示符號等，但會減少名稱中的符號種數(shù)）：如輸入“a*” 輸出“abc”；輸入“a(|$)*”，輸出“abc,a1,ab1245”。注：以上的$等符號是隨便設(shè)定的，請在實際編程時修改它。同“名稱查找程序”中的有關(guān)正規(guī)式的方案，難度較大，具體正規(guī)式包含哪些符號和通配符可另定。這個設(shè)計結(jié)果可改變后用于電路分析、謂詞演算等。轉(zhuǎn)義符的識別C語言的字符串常量書寫時使用了大量的轉(zhuǎn)義符，如“”表示單斜杠，而“n”表示換行（同“u000A”），“x20”表示十六進制表示形式（恰好兩位）與 ASCII 字符匹配（這里代表值為32的ASCII字符，即空格）。難度：一般。有限自動機的運行設(shè)計一個確定的有限自動機，寫出狀態(tài)轉(zhuǎn)換函數(shù)，或畫出狀態(tài)圖，編制程序，輸入一個字符串，程序能判別該字符串是否能被該有限自動機接受，可以考慮輸出能否接受的同時，輸出狀態(tài)路徑。⑴整數(shù)的判斷：寫出整數(shù)的正規(guī)式，畫出狀態(tài)圖，寫出狀態(tài)轉(zhuǎn)換函數(shù)。難度：簡單。⑶實數(shù)的判斷：過程同上。7 編寫一個語法分析程序編寫一個語法分析程序，對輸入到緩沖區(qū)的符號進行分析，建立相應(yīng)的語法樹，并輸出相應(yīng)的語法樹。9 學(xué)習(xí)使用LEX和YACC工具LEX和YACC分別是生成詞法分析程序和語法分析程序的工具，即編譯程序的編譯程序。學(xué)習(xí)使用LEX和YACC工具并編寫相應(yīng)程序。5．2 分析選好題目后，分析該題目的應(yīng)用性，可用到編譯原理的哪些理論？對它們進行簡單闡述。5．3 設(shè)計對軟件劃分功能模塊，將模塊細(xì)化，設(shè)計出數(shù)據(jù)存放格式，寫出各模塊（函數(shù)）的功能、傳遞參數(shù)的格式和返回值的類型，畫出模塊結(jié)構(gòu)圖。5．4上機按課表的安排上機（修改設(shè)計/編碼/調(diào)試/測試）。2．修改設(shè)計，繼續(xù)完成輸入代碼，并作初步調(diào)試。4．修改設(shè)計中的缺陷，完善程序。繼續(xù)完善程序，并完成設(shè)計說明書，上交成果。上交文檔（打印，文件名中包含姓名）；（存在一個文本文件中）；：有關(guān)的文檔資料，包括：選題報告，簡單的軟件需求分析說明書，軟件設(shè)計說明，設(shè)計經(jīng)驗總結(jié)。以下幾方面可以提高分?jǐn)?shù)： 7．1 軟件實用性強；7．2 軟件使用了編譯原理中的某些理論； 7．3 軟件具有擴展性； 7．4 各類文檔寫的很規(guī)范；7．5 設(shè)計時非常投入，設(shè)計后很有心得； 7．6 其他優(yōu)點。通過編譯程序的編寫和調(diào)試能力的訓(xùn)練，激發(fā)學(xué)生進一步思考問題，培養(yǎng)學(xué)生的學(xué)習(xí)興趣和創(chuàng)新能力。本次課程設(shè)計的時間為2周，目的是通過實際的題目如：詞法分析、語法分析、代碼優(yōu)化等，使學(xué)生了解和掌握編譯程序的工作原理，同時培養(yǎng)學(xué)生用相關(guān)的程序設(shè)計語言進行程序設(shè)計，實現(xiàn)編譯的功能，從而提高學(xué)生的綜合能力。給出實現(xiàn)功能的一組或多組測試數(shù)據(jù)（測試文法），程序調(diào)試后，將按照此測試數(shù)據(jù)進行測試的結(jié)果列出來。源程序要按照寫程序的規(guī)則來編寫。程序能夠運行，要有基本的容錯功能。2．課程設(shè)計實習(xí)報告的書寫格式編譯原理 436105 軟件工程 2W 2012．6審 核 人：① 設(shè)計題目②運行環(huán)境（軟、硬件環(huán)境）③算法設(shè)計的思想 ④算法設(shè)計分析 ⑤主要函數(shù) ⑥源代碼 ⑦運行結(jié)果分析 ⑧收獲及體會 3．實施方式本次課程設(shè)計分成9個題目，都有一定的工作量，涵蓋本課程內(nèi)容和實際應(yīng)用相關(guān)的主要技術(shù)，學(xué)生可以自由組隊選擇其中一個實現(xiàn)。根據(jù)老師給定的9個題目進行分析設(shè)計，本次課程設(shè)計采取分組的辦法進行，34人為一組，要求每組學(xué)生在規(guī)定時間內(nèi)獨立完成。同樣，在編繹一個程序時，也是在單詞級別上來分析和翻譯源程序。設(shè)計目的與任務(wù)：通過本課程設(shè)計教學(xué)所要求達到的目的是：對詞法分析工作流程進行總體設(shè)計和詳細(xì)設(shè)計，最終用C語言來設(shè)計一個簡單詞法分析器，實現(xiàn)對源程序的詞法分析功能，對輸入程序去除注釋，并以二元式形式輸出程序中所有單詞。對于單詞的識別，有限自動機FA是一種十分有效的工具。在非確定的有限自動機NFA中，由于某些狀態(tài)的轉(zhuǎn)移需從若干個可能的后續(xù)狀態(tài)中進行選擇，故一個NFA對符號串的識別就必然是一個試探的過程。而DFA引擎在任意時刻必定處于某個確定的狀態(tài)，它搜索是無需象NFA一樣必須記錄所有的可能路徑（trace multiple possible routes through the NFA），這也是DFA運行效率高于NFA的原因。設(shè)計目的與任務(wù)通過本課程設(shè)計教學(xué)所要求達到的目的是：充分理解和掌握NFA，DFA以及NFA確定化過程的相關(guān)概念和知識，編程實現(xiàn)對輸入的任意正規(guī)式轉(zhuǎn)換成NFA的形式輸出。一條詞法規(guī)則表示一個正規(guī)表達式(又叫正規(guī)式)，而一個正規(guī)式又可化為一個DFA(確定有窮自動機)，這個有限自動機可用來識別詞法規(guī)則所定義的所有單詞符號。然后,再轉(zhuǎn)換為計算機可識別的程序就能自動實現(xiàn)詞法的分析和檢查。設(shè)計目的與任務(wù)通過本課程設(shè)計教學(xué)所要求達到的目的是：掌握從NFA到DFA的轉(zhuǎn)換，以及用子集法把NFA轉(zhuǎn)換成DFA理論，編程實現(xiàn)將NFA(不確定有窮自動機)轉(zhuǎn)換為DFA(確定有窮自動機)。DFA的最小化可以揭示狀態(tài)之間的內(nèi)在聯(lián)系，便于其存儲實現(xiàn)，便于建立用DFA描述的任務(wù)模型，一些理論問題也與最小化思想有關(guān)。許多文獻給出了一個最小化算法，算法的思想是，構(gòu)造狀態(tài)集的一個劃分，再將這個劃分中的每個子集作為新的狀態(tài)，從而得到等價最小DFA。語法分析之LL(1)文法通過該課程設(shè)計了解了程序語言的自上而下的語法分析過程,提高了編程能力,能使我們了解編程語言更多的細(xì)節(jié) 設(shè)計目的與任務(wù)（1）讀入文法（2）求出first(), follow()（3）判斷是否為LL(1)文法（4）若是，構(gòu)造分析表；（5）輸入一個字符串看是否是文法的一個句子。假設(shè)文法中的任意兩個終結(jié)符之間最多只有一個優(yōu)先關(guān)系，則該文法稱為算符優(yōu)先文法。然后按照算符優(yōu)先算法求出各終結(jié)符的算符優(yōu)先關(guān)系，填寫算符優(yōu)先表，并將其輸出。這種方法可以適用于很大一類上下無關(guān)文法的語法分析。當(dāng)一串貌似句柄的符號串呈現(xiàn)于分析棧的