0引言
離散數學是現代數學的一個重要分支，也是計算機科學與技術的理論基礎，所以又稱為計算機數學。
離散數學研究離散量的結構及其相互關系，通過離散數學的學習，不但可以掌握處理離散結構的描述工具和方法，為后續課程的學習創造條件，而且可以提高抽象思維和嚴格的邏輯推理能力，為將來參與創新性的研究和開發工作打下堅實的基礎。離散數學在各學科領域，特別在計算機科學與技術領域有著廣泛的應用，離散數學是很多計算機相關專業課的先行課程，例如《數據結構》、《算法分析與設計》、《計算機網絡》、《操作系統》、《數據庫》、《軟件工程》，當然也包括《編譯原理》（或稱《編譯方法》）課程。
編譯程序是計算機的重要系統軟件，是高級程序設計語言的支撐基礎，《編譯原理》主要承擔了語言實現原理、方法和技術的介紹，《編譯原理》是計算機相關專業的一門重要專業基礎課?！毒幾g原理》課程內容除了形式語言、有窮自動機等編譯原理所涉及的基礎知識外，其他內容基本上圍繞處理程序設計語言的編譯程序應該具有的各功能模塊展開，包括詞法分析、語法分析、語法制導翻譯、中間代碼生成、存儲管理、代碼優化和目標代碼生成等?！毒幾g原理》在理論、技術、方法上都對學生提供了系統而有效的訓練，有利于提高軟件人員的素質和能力?！毒幾g原理》的先行課包括《高級程序設計語言》、《計算機組成原理》、《數據結構》等，當然還有為編譯原理提供數學基礎的《離散數學》。
作為計算機科學與技術數學理論基礎的《離散數學》，不僅描述了計算機科學離散性的特點，而且著力于培養與提高學生的抽象思維能力與嚴格的邏輯推理能力；《編譯原理》在將程序語言編譯原理和技術應用于實踐,注重提高學生的動手能力的同時，更應該重視學生理論基礎的鞏固和形式思維能力的培養，這一點正需要離散數學來補充。因此，需要將《編譯原理》中的離散數學基礎知識還原，以加深對離散數序與編譯原理關系的理解，進而體現離散數學基礎知識的應用。
將編譯原理與離散數學結合，不僅可以讓學生了解離散數學理論在編譯技術中的應用，讓學生知道編譯原理與離散數學原理的對應關系，加深學生對離散數學原理的理解；并且可以在致力于提高學生在編譯技術方面的動手能力的同時，加強學生的數學理論修養和數學意識。因而，本文將致力于從《編譯原理》課程內容中還原離散數學原理，提高學生對這兩門課的學習興趣，談到的離散數學內容包括數理邏輯、關系理論、圖論和代數系統。
1、等價原理還原
等價是數學的一個基本原理，是替換定理的理論依據。在離散數學內容中，多處涉及到等價原理，包括集合相等關系、邏輯恒等式、等價關系、圖同構、代數系統同構等。實際上，在程序設計語言的編譯原理很多課程內容中皆可還原出等價原理。
形式文法作為《編譯原理》的最重要理論基礎，也是表示語言規則的一種重要手段，其中有文法等價的定義，如定義1所示。
定義1：如果L\\(G1\\)=L\\(G2\\)，則稱文法G1和G2是等價的，其中L\\(G1\\)表示由文法G1生成的語言。有窮自動機是《編譯原理》的另一個重要理論基礎，也可以表示語言中句子的生成過程，其中包含了有窮自動機等價的定義，如定義2所示。
定義2：對于任意兩個有窮自動機M1和M2，如果L\\(M1\\)=L\\(M2\\)，則稱M1與M2是等價的，其中L\\(M\\)表示由有窮自動機M生成的語言。圖1中的非確定有窮自動機NFAM1和確定有窮自動機DFAM2就是兩個等價的有窮自動機。有窮自動機的等價關系是NFA轉換為DFA、DFA化簡的理論依據。
可以還原等價原理的《編譯原理》課程內容還有很多，主要是對于同一內涵的不同外延表示形式，例如中間代碼的逆波蘭式、三元式、四元式以及樹形等。針對詞法規則，《編譯原理》課程內容中至少有正規文法、正則式和有窮自動機三種表示形式，它們相互間都是等價的。實際上，這些等價性也是語言規則三種不同表示方法（文法、正則式與有窮自動機）相互轉換的理論依據。
2、演繹與歸納還原
《離散數學》的數理邏輯中最重要的內容就是邏輯推理，由前提出發，采用相應的邏輯恒等式、永真蘊涵式、推理規則、推理方法等進行不停地推導，最終得到結論，這是一個嚴格的演繹分析過程，圖2\\(a\\)就是一個典型的數理邏輯中的邏輯推理過程。對于表示語言的形式文法而言，需要通過推導過程得到語言的句型或句子；文法的推導過程實際上就是離散數學的邏輯推理過程，從文法的開始符號（前提）出發，利用文法規則產生式（永真蘊涵式），采用相應的推理方法（最左或最右推導），最終得到句型或句子（結論）。圖2\\(b\\)就是根據形式文法進行句子“i*i+i”的一個典型最左推導過程，文法推導實際上對應自頂向下的分析方法，當然在這一分析過程中，可能會涉及到遞歸和回溯。
在推理證明中還有一種常用的證明方法，那就是從要求證的結論出發，依次為其找到相應的邏輯恒等式、永真蘊涵式、推理規則等作為結論的依據，即從結論出發追本溯源到前提，這是一種典型的歸納邏輯。在編譯原理的語法分析中，除自頂向下的分析方法外，還有一類自底向上的分析方法，即從要得到的句型或句子出發，利用文法產生式規則和推理方法，進行不停的歸約，一直到開始符號或直失敗，這是一個明顯的歸納邏輯推理過程，對應最右推導。表1就是圖4\\(b\\)的G[E]文法采用自底向上的分析方法對句子“i+i*i”的歸約過程，這里的底指句子“i+i*i”；實際上，從步驟10至2就是從開始符號出發得到最終句子的最右推導過程，如圖4\\(c\\)所示。
3、圖論還原
編譯原理的很多內容中都使用了形式化技術，最典型的就是使用產生式規則表示形式文法以及用狀態圖來描述有窮自動機，如圖1所示。編譯原理中體現形式化的最重要的內容就是使用語法樹來對應文法的句型或句子的推導過程，圖2\\(b\\)的最左推導過程對應語法樹圖3\\(a\\)，而圖2\\(c\\)的最右推導過程對應語法樹圖3\\(b\\)。
除以上提到的形式文法、有窮自動機狀態圖以及語法樹外，編譯原理內容中與離散數學圖論緊密相關的內容還包括：
（1）LL\\(1\\)文法FIRST集、FOLLOW集計算中使用的關系圖；（2）算符優先文法FIRSTVT集、LASTVT集計算中使用的關系圖；（3）算符優先文法的優先函數關系圖；（4）LR類文法中識別活前綴的有窮自動機；（5）描述語法樹中屬性之間信息流和語義規則的依賴圖；（6）抽象語法樹；（7）表達式描述時使用的有向無環圖；（8）空間棧式分配中的活動樹；（9）使用圖著色方法進行寄存器分配；（10）基本塊有向圖中的遍歷。
4、代數系統還原
編譯原理的處理對象是語言，課程基礎內容為形式文法和有窮自動機，既可以表示于產生語言，也可以計算語言。實際上，編譯程序中隨處都體現了計算思維。在語言中，表達完整意義的基本單位是句子，而在符號系統中，句子就是字符串；因而，字符串計算在編譯原理中尤其重要。
在編譯原理中，語言被定義為句子的集合，假設將語言指定為集合∑*，則∑*與定義在其上的計算則可構成代數系統。假如考慮語言（符號串集合）∑*上的連接運算，顯然連接運算“·”在語言∑*上是封閉的，因而，<∑*，·>為代數系統。
對于∑*上任意三個句子x，y，z，（x·y）·z=xy·z=xyz=x·（yz）=x·（y·z），連接運算“·”在語言∑*上滿足結合律，因而，<∑*，·>為半群。對于語言∑*上的空串（空字、空白）ε，顯然，ε·x=x=x·ε，ε為半群<∑*，·>的單位元（幺元），則<∑*，·>為含幺半群。
在編譯原理中，除形式文法外，正規式也可以表示規則，正規式與定義其上的運算也可以構成代數系統。
實際上，廣義來講，有窮自動機、語法樹等都可以作為運算對象，根據定義其上的運算，尤其是轉換，都可以討論它們獨有的代數系統。
5、結語
本文考察了《編譯原理》課程的形式文法、有窮自動機、語法分析、形式化以及語言運算等內容，關鍵是要通過對這些課程內容的討論與分析，獲取并還原隱含其中的離散數學原理，這些原理包括等價、演繹與歸納、圖論以及代數系統。通過還原《編譯原理》課程內容的離散數學原理，讓計算機相關專業的大學生認識到離散數學課程在后續的專業課中的重要地位，激發離散數學和編譯原理的學習興趣，進而提高離散數學修養，具有成熟的離散數學意識。
參考文獻：
[1]傅彥，顧小豐，王慶先等.離散數學及其應用［M］.北京:高等教育出版社,2007
[2]屈婉玲，王元元，傅彥等.《離散數學》課程教學實施方案［J］.中國大學教學,2011\\(1\\):39~41
[3]何炎祥.編譯原理（第三版）［M］.武漢：華中科技大學出版社，2010
[4]何炎祥，伍春香．計算機專業不需要編譯原理課程嗎?[J]．計算機教育，2009\\(4\\)：61~62，85
[5]張素琴，呂映芝，蔣維杜等.編譯原理（第2版）［M］.北京:清華大學出版社,2011
[6]王挺，李夢君，周會平.對編譯原理課程教學中計算思維培養的探討［J］.計算機教育,2009\\(21\\)：11~13
