正文：
???
詞法分析器可有兩種:一種是把詞法分析器作為語法分析的一個子程序,一種是把詞法分析器作為編譯程序的獨立一遍.在前一種情況下,詞法分析器不斷地被語法分析器調用,每調用一次詞法分析器將從源程序的字符序列拼出一個單詞,并將其Token值返回給語法分析器.后一種情況則不同,詞法分析器不是被語法分析器不斷地調用,而是一次掃描全部單詞完成編譯器的獨立一遍任務.
???
詞法分析器的本質：基本任務是進行模式匹配,其關鍵在于分析過程中的模式說明和模式識別方法,在編譯分析中即正規表達式和有限自動機。
???
構造詞法分析器方法：1、手工構造；2、利用自動生成工具LEX。但是無論用那種方法，其內在工作原理都是相同的，都要經過正規式到最小狀態DFA的轉換。
?
?
?
???
正規表達式與有限自動機的關系：（1）、字母表Σ上的有限自動機M所接受的語言L（M）是Σ上的一個正規集；（2）、對于Σ上的每一個正規式r，存在一個Σ上的非確定有限自動機M，使得L（M）=L（r）。這就是說，正規式所表示的語言即正規集與有限自動機所識別的語言是完全等價的，只是表示形式不同而已。同一個語言，既可以用FA描述，也可以用正規式描述。而詞法分析器則是根據它們的規則構造的。
?
?
?
編譯器是將一種語言翻譯為另一種語言的計算機程序。編譯器將源程序（source language）編寫的程序作為輸入，而產生用目標語言（target language）編寫的等價程序。通常地，源程序為高級語言（high-level language），如C或C++，而目標語言則是目標機器的目標代碼（object code，有時也稱作機器代碼（machine code）），也就是寫在計算機機器指令中的用于運行的代碼。
編譯器是一種相當復雜的程序，其代碼的長度可從10000行到1000000行不等。編寫甚至讀懂這樣的一個程序都非易事，大多數的計算機科學家和專業人員也從來沒有編寫過一個完整的編譯器。但是，幾乎所有形式的計算均要用到編譯器，而且任何一個與計算機打交道的專業人員都應掌握編譯器的基本結構和操作。除此之外，計算機應用程序中經常遇到的一個任務就是命令解釋程序和界面程序的開發，這比編譯器要小，但使用的卻是相同的技術。因此，掌握這一技術具有非常大的實際意義。
?
一、
編譯系統的
發展：
上世紀50年代，IBM的John Backus帶領一個研究小組對FORTRAN語言及其編譯器進行開發。但由于當時人們對編譯理論了解不多，開發工作變得既復雜又艱苦。與此同時， Noam Chomsky開始了他對自然語言結構的研究。他的發現最終使得編譯器的結構異常簡單，甚至還帶有了一些自動化。Chomsky的研究導致了根據語言文法的難易程度以及識別它們所需要的算法來對語言分類。正如現在所稱的Chomsky架構（Chomsky Hierarchy），它包括了文法的四個層次：0型文法、1型文法、2型文法和3型文法，且其中的每一個都是其前者的特殊情況。2型文法（或上下文無關文法）被證明是程序設計語言中最有用的，而且今天它已代表著程序設計語言結構的標準方式。分析問題（parsing problem，用于上下文無關文法識別的有效算法）的研究是在60年代和70年代，它相當完善的解決了這個問題?，F在它已是編譯原理中的一個標準部分。
??? 有限狀態自動機（Finite Automaton）和正則表達式（Regular Expression）同上下文無關文法緊密相關，它們與Chomsky的3型文法相對應。對它們的研究與Chomsky的研究幾乎同時開始，并且引出了表示程序設計語言的單詞的符號方式。
??? 人們接著又深化了生成有效目標代碼的方法，這就是最初的編譯器，它們被一直使用至今。人們通常將其稱為優化技術（Optimization Technique），但因其從未真正地得到過被優化了的目標代碼而僅僅改進了它的有效性，因此實際上應稱作代碼改進技術（Code Improvement Technique）。
??? 當分析問題變得好懂起來時，人們就在開發程序上花費了很大的功夫來研究這一部分的編譯器自動構造。這些程序最初被稱為編譯器的編譯器（Compiler-compiler），但更確切地應稱為分析程序生成器（Parser Generator），這是因為它們僅僅能夠自動處理編譯的一部分。這些程序中最著名的是Yacc（Yet Another Compiler-compiler），它是由Steve Johnson在1975年為Unix系統編寫的。類似的，有限狀態自動機的研究也發展了一種稱為掃描程序生成器（Scanner Generator）的工具，Lex（與Yacc同時，由Mike Lesk為Unix系統開發）是這其中的佼佼者。
??? 在70年代后期和80年代早期，大量的項目都貫注于編譯器其它部分的生成自動化，這其中就包括了代碼生成。這些嘗試并未取得多少成功，這大概是因為操作太復雜而人們又對其不甚了解。
??? 編譯器設計最近的發展包括：首先，編譯器包括了更加復雜算法的應用程序它用于推斷或簡化程序中的信息；這又與更為復雜的程序設計語言的發展結合在一起。其中典型的有用于函數語言編譯的Hindley-Milner類型檢查的統一算法。其次，編譯器已越來越成為基于窗口的交互開發環境（Interactive Development Environment，IDE）的一部分，它包括了編輯器、連接程序、調試程序以及項目管理程序。這樣的IDE標準并沒有多少，但是對標準的窗口環境進行開發已成為方向。另一方面，盡管近年來在編譯原理領域進行了大量的研究，但是基本的編譯器設計原理在近20年中都沒有多大的改變，它現在正迅速地成為計算機科學課程中的中心環節。
??? 在九十年代，作為GNU項目或其它開放源代碼項目的一部分，許多免費編譯器和編譯器開發工具被開發出來。這些工具可用來編譯所有的計算機程序語言。它們中的一些項目被認為是高質量的，而且對現代編譯理論感性趣的人可以很容易的得到它們的免費源代碼。
??? 大約在1999年，SGI公布了他們的一個工業化的并行化優化編譯器Pro64的源代碼，后被全世界多個編譯器研究小組用來做研究平臺，并命名為Open64。Open64的設計結構好，分析優化全面，是編譯器高級研究的理想平臺。
?
?
二、與編譯器相關的程序：
?
(1)
解釋程序（interpreter）
??? 解釋程序是如同編譯器的一種語言翻譯程序。它與編譯器的不同之處在于：它立即執行源程序而不是生成在翻譯完成之后才執行的目標代碼。從原理上講，任何程序設計語言都可被解釋或被編譯，但是根據所使用的語言和翻譯情況，很可能會選用解釋程序而不用編譯器。例如，我們經常解釋BASIC語言而不是去編譯它。類似地，諸如LISP的函數語言也常常是被解釋的。解釋程序也經常用于教育和軟件的開發，此處的程序很有可能被翻譯若干次。而另一方面，當執行的速度是最為重要的因素時就使用編譯器，這是因為被編譯的目標代碼比被解釋的源代碼要快得多，有時要快10倍或更多。但是，解釋程序具有許多與編譯器共享的操作，而兩者之間也有一些混合之處。
?
(2)
匯編程序（assembler）
??? 匯編程序是用于特定計算機上的匯編語言的翻譯程序。正如前面所提到的，匯編語言是計算機的機器語言的符號形式，它極易翻譯。有時，編譯器會生成匯編語言以作為其目標語言，然后再由一個匯編程序將它翻譯成目標代碼。
(3)
連接程序（linker）
??? 編譯器和匯編程序都經常依賴于連接程序，它將分別在不同的目標文件中編譯或匯編的代碼收集到一個可直接執行的文件中。在這種情況下，目標代碼，即還未被連接的機器代碼，與可執行的機器代碼之間就有了區別。連接程序還連接目標程序和用于標準庫函數的代碼，以及連接目標程序和由計算機的操作系統提供的資源（例如，存儲分配程序及輸入與輸出設備）。有趣的是，連接程序現在正在完成編譯器最早的一個主要活動（這也是“編譯”一詞的用法，即通過收集不同的來源來構造）。連接過程對操作系統和處理器有極大的依賴性。
?
(4)
裝入程序（loader）
??? 編譯器、匯編程序或連接程序生成的代碼經常還不完全適用或不能執行，但是它們的主要存儲器訪問卻可以在存儲器的任何位置中且與一個不確定的起始位置相關。這樣的代碼被稱為是可重定位的（relocatable），而裝入程序可處理所有的與指定的基地址或起始地址有關的可重定位的地址。裝入程序使得可執行代碼更加靈活，但是裝入處理通常是在后臺（作為操作環境的一部分）或與連接相聯合時才發生，裝入程序極少會是實際的獨立程序。
(5)
預處理器（preprocessor）
??? 預處理器是在真正的翻譯開始之前由編譯器調用的獨立程序。預處理器可以刪除注釋、包含其他文件以及執行宏（宏macro是一段重復文字的簡短描寫）替代。預處理器可由語言（如C）要求或以后作為提供額外功能（諸如為FORTRAN提供Ratfor預處理器）的附加軟件。
(6)
編輯器（editor）
??? 編譯器通常接受由任何生成標準文件（例如ASCII文件）的編輯器編寫的源程序。最近，編譯器已與另一個編輯器和其他程序捆綁進一個交互的開發環境——IDE中。此時，盡管編輯器仍然生成標準文件，但會轉向正被討論的程序設計語言的格式或結構。這樣的編輯器稱為基于結構的（structure based），且它早已包括了編譯器的某些操作；因此，程序員就會在程序的編寫時而不是在編譯時就得知錯誤了。從編輯器中也可調用編譯器以及與它共用的程序，這樣程序員無需離開編輯器就可執行程序。
(7)
調試程序（debugger）
??? 調試程序是可在被編譯了的程序中判定執行錯誤的程序，它也經常與編譯器一起放在IDE中。運行一個帶有調試程序的程序與直接執行不同，這是因為調試程序保存著所有的或大多數源代碼信息（諸如行數、變量名和過程）。它還可以在預先指定的位置（稱為斷點（breakpoint））暫停執行，并提供有關已調用的函數以及變量的當前值的信息。為了執行這些函數，編譯器必須為調試程序提供恰當的符號信息，而這有時卻相當困難，尤其是在一個要優化目標代碼的編譯器中。因此，調試又變成了一個編譯問題。
(8)
描述器（profiler）
??? 描述器是在執行中搜集目標程序行為統計的程序。程序員特別感興趣的統計是每一個過程的調用次數和每一個過程執行時間所占的百分比。這樣的統計對于幫助程序員提高程序的執行速度極為有用。有時編譯器也甚至無需程序員的干涉就可利用描述器的輸出來自動改進目標代碼。
(9)
項目管理程序（project manager）
??? 現在的軟件項目通常大到需要由一組程序員來完成，這時對那些由不同人員操作的文件進行整理就非常重要了，而這正是項目管理程序的任務。例如，項目管理程序應將由不同的程序員制作的文件的各個獨立版本整理在一起，它還應保存一組文件的更改歷史，這樣就能維持一個正在開發的程序的連貫版本了（這對那些由單個程序員管理的項目也很有用）。項目管理程序的編寫可與語言無關，但當其與編譯器捆綁在一起時，它就可以保持有關特定的編譯器和建立一個完整的可執行程序的鏈接程序操作的信息。在Unix系統中有兩個流行的項目管理程序：sccs（source code control system）和rcs（revision control system）。
?
?
?
???
詞法分析器可有兩種:一種是把詞法分析器作為語法分析的一個子程序,一種是把詞法分析器作為編譯程序的獨立一遍.在前一種情況下,詞法分析器不斷地被語法分析器調用,每調用一次詞法分析器將從源程序的字符序列拼出一個單詞,并將其Token值返回給語法分析器.后一種情況則不同,詞法分析器不是被語法分析器不斷地調用,而是一次掃描全部單詞完成編譯器的獨立一遍任務.
???
詞法分析器的本質：基本任務是進行模式匹配,其關鍵在于分析過程中的模式說明和模式識別方法,在編譯分析中即正規表達式和有限自動機。
???
構造詞法分析器方法：1、手工構造；2、利用自動生成工具LEX。但是無論用那種方法，其內在工作原理都是相同的，都要經過正規式到最小狀態DFA的轉換。
?
?
?
???
正規表達式與有限自動機的關系：（1）、字母表Σ上的有限自動機M所接受的語言L（M）是Σ上的一個正規集；（2）、對于Σ上的每一個正規式r，存在一個Σ上的非確定有限自動機M，使得L（M）=L（r）。這就是說，正規式所表示的語言即正規集與有限自動機所識別的語言是完全等價的，只是表示形式不同而已。同一個語言，既可以用FA描述，也可以用正規式描述。而詞法分析器則是根據它們的規則構造的。
?
?
?
編譯器是將一種語言翻譯為另一種語言的計算機程序。編譯器將源程序（source language）編寫的程序作為輸入，而產生用目標語言（target language）編寫的等價程序。通常地，源程序為高級語言（high-level language），如C或C++，而目標語言則是目標機器的目標代碼（object code，有時也稱作機器代碼（machine code）），也就是寫在計算機機器指令中的用于運行的代碼。
編譯器是一種相當復雜的程序，其代碼的長度可從10000行到1000000行不等。編寫甚至讀懂這樣的一個程序都非易事，大多數的計算機科學家和專業人員也從來沒有編寫過一個完整的編譯器。但是，幾乎所有形式的計算均要用到編譯器，而且任何一個與計算機打交道的專業人員都應掌握編譯器的基本結構和操作。除此之外，計算機應用程序中經常遇到的一個任務就是命令解釋程序和界面程序的開發，這比編譯器要小，但使用的卻是相同的技術。因此，掌握這一技術具有非常大的實際意義。
?
一、
編譯系統的
發展：
上世紀50年代，IBM的John Backus帶領一個研究小組對FORTRAN語言及其編譯器進行開發。但由于當時人們對編譯理論了解不多，開發工作變得既復雜又艱苦。與此同時， Noam Chomsky開始了他對自然語言結構的研究。他的發現最終使得編譯器的結構異常簡單，甚至還帶有了一些自動化。Chomsky的研究導致了根據語言文法的難易程度以及識別它們所需要的算法來對語言分類。正如現在所稱的Chomsky架構（Chomsky Hierarchy），它包括了文法的四個層次：0型文法、1型文法、2型文法和3型文法，且其中的每一個都是其前者的特殊情況。2型文法（或上下文無關文法）被證明是程序設計語言中最有用的，而且今天它已代表著程序設計語言結構的標準方式。分析問題（parsing problem，用于上下文無關文法識別的有效算法）的研究是在60年代和70年代，它相當完善的解決了這個問題。現在它已是編譯原理中的一個標準部分。
??? 有限狀態自動機（Finite Automaton）和正則表達式（Regular Expression）同上下文無關文法緊密相關，它們與Chomsky的3型文法相對應。對它們的研究與Chomsky的研究幾乎同時開始，并且引出了表示程序設計語言的單詞的符號方式。
??? 人們接著又深化了生成有效目標代碼的方法，這就是最初的編譯器，它們被一直使用至今。人們通常將其稱為優化技術（Optimization Technique），但因其從未真正地得到過被優化了的目標代碼而僅僅改進了它的有效性，因此實際上應稱作代碼改進技術（Code Improvement Technique）。
??? 當分析問題變得好懂起來時，人們就在開發程序上花費了很大的功夫來研究這一部分的編譯器自動構造。這些程序最初被稱為編譯器的編譯器（Compiler-compiler），但更確切地應稱為分析程序生成器（Parser Generator），這是因為它們僅僅能夠自動處理編譯的一部分。這些程序中最著名的是Yacc（Yet Another Compiler-compiler），它是由Steve Johnson在1975年為Unix系統編寫的。類似的，有限狀態自動機的研究也發展了一種稱為掃描程序生成器（Scanner Generator）的工具，Lex（與Yacc同時，由Mike Lesk為Unix系統開發）是這其中的佼佼者。
??? 在70年代后期和80年代早期，大量的項目都貫注于編譯器其它部分的生成自動化，這其中就包括了代碼生成。這些嘗試并未取得多少成功，這大概是因為操作太復雜而人們又對其不甚了解。
??? 編譯器設計最近的發展包括：首先，編譯器包括了更加復雜算法的應用程序它用于推斷或簡化程序中的信息；這又與更為復雜的程序設計語言的發展結合在一起。其中典型的有用于函數語言編譯的Hindley-Milner類型檢查的統一算法。其次，編譯器已越來越成為基于窗口的交互開發環境（Interactive Development Environment，IDE）的一部分，它包括了編輯器、連接程序、調試程序以及項目管理程序。這樣的IDE標準并沒有多少，但是對標準的窗口環境進行開發已成為方向。另一方面，盡管近年來在編譯原理領域進行了大量的研究，但是基本的編譯器設計原理在近20年中都沒有多大的改變，它現在正迅速地成為計算機科學課程中的中心環節。
??? 在九十年代，作為GNU項目或其它開放源代碼項目的一部分，許多免費編譯器和編譯器開發工具被開發出來。這些工具可用來編譯所有的計算機程序語言。它們中的一些項目被認為是高質量的，而且對現代編譯理論感性趣的人可以很容易的得到它們的免費源代碼。
??? 大約在1999年，SGI公布了他們的一個工業化的并行化優化編譯器Pro64的源代碼，后被全世界多個編譯器研究小組用來做研究平臺，并命名為Open64。Open64的設計結構好，分析優化全面，是編譯器高級研究的理想平臺。
?
?
二、與編譯器相關的程序：
?
(1)
解釋程序（interpreter）
??? 解釋程序是如同編譯器的一種語言翻譯程序。它與編譯器的不同之處在于：它立即執行源程序而不是生成在翻譯完成之后才執行的目標代碼。從原理上講，任何程序設計語言都可被解釋或被編譯，但是根據所使用的語言和翻譯情況，很可能會選用解釋程序而不用編譯器。例如，我們經常解釋BASIC語言而不是去編譯它。類似地，諸如LISP的函數語言也常常是被解釋的。解釋程序也經常用于教育和軟件的開發，此處的程序很有可能被翻譯若干次。而另一方面，當執行的速度是最為重要的因素時就使用編譯器，這是因為被編譯的目標代碼比被解釋的源代碼要快得多，有時要快10倍或更多。但是，解釋程序具有許多與編譯器共享的操作，而兩者之間也有一些混合之處。
?
(2)
匯編程序（assembler）
??? 匯編程序是用于特定計算機上的匯編語言的翻譯程序。正如前面所提到的，匯編語言是計算機的機器語言的符號形式，它極易翻譯。有時，編譯器會生成匯編語言以作為其目標語言，然后再由一個匯編程序將它翻譯成目標代碼。
(3)
連接程序（linker）
??? 編譯器和匯編程序都經常依賴于連接程序，它將分別在不同的目標文件中編譯或匯編的代碼收集到一個可直接執行的文件中。在這種情況下，目標代碼，即還未被連接的機器代碼，與可執行的機器代碼之間就有了區別。連接程序還連接目標程序和用于標準庫函數的代碼，以及連接目標程序和由計算機的操作系統提供的資源（例如，存儲分配程序及輸入與輸出設備）。有趣的是，連接程序現在正在完成編譯器最早的一個主要活動（這也是“編譯”一詞的用法，即通過收集不同的來源來構造）。連接過程對操作系統和處理器有極大的依賴性。
?
(4)
裝入程序（loader）
??? 編譯器、匯編程序或連接程序生成的代碼經常還不完全適用或不能執行，但是它們的主要存儲器訪問卻可以在存儲器的任何位置中且與一個不確定的起始位置相關。這樣的代碼被稱為是可重定位的（relocatable），而裝入程序可處理所有的與指定的基地址或起始地址有關的可重定位的地址。裝入程序使得可執行代碼更加靈活，但是裝入處理通常是在后臺（作為操作環境的一部分）或與連接相聯合時才發生，裝入程序極少會是實際的獨立程序。
(5)
預處理器（preprocessor）
??? 預處理器是在真正的翻譯開始之前由編譯器調用的獨立程序。預處理器可以刪除注釋、包含其他文件以及執行宏（宏macro是一段重復文字的簡短描寫）替代。預處理器可由語言（如C）要求或以后作為提供額外功能（諸如為FORTRAN提供Ratfor預處理器）的附加軟件。
(6)
編輯器（editor）
??? 編譯器通常接受由任何生成標準文件（例如ASCII文件）的編輯器編寫的源程序。最近，編譯器已與另一個編輯器和其他程序捆綁進一個交互的開發環境——IDE中。此時，盡管編輯器仍然生成標準文件，但會轉向正被討論的程序設計語言的格式或結構。這樣的編輯器稱為基于結構的（structure based），且它早已包括了編譯器的某些操作；因此，程序員就會在程序的編寫時而不是在編譯時就得知錯誤了。從編輯器中也可調用編譯器以及與它共用的程序，這樣程序員無需離開編輯器就可執行程序。
(7)
調試程序（debugger）
??? 調試程序是可在被編譯了的程序中判定執行錯誤的程序，它也經常與編譯器一起放在IDE中。運行一個帶有調試程序的程序與直接執行不同，這是因為調試程序保存著所有的或大多數源代碼信息（諸如行數、變量名和過程）。它還可以在預先指定的位置（稱為斷點（breakpoint））暫停執行，并提供有關已調用的函數以及變量的當前值的信息。為了執行這些函數，編譯器必須為調試程序提供恰當的符號信息，而這有時卻相當困難，尤其是在一個要優化目標代碼的編譯器中。因此，調試又變成了一個編譯問題。
(8)
描述器（profiler）
??? 描述器是在執行中搜集目標程序行為統計的程序。程序員特別感興趣的統計是每一個過程的調用次數和每一個過程執行時間所占的百分比。這樣的統計對于幫助程序員提高程序的執行速度極為有用。有時編譯器也甚至無需程序員的干涉就可利用描述器的輸出來自動改進目標代碼。
(9)
項目管理程序（project manager）
??? 現在的軟件項目通常大到需要由一組程序員來完成，這時對那些由不同人員操作的文件進行整理就非常重要了，而這正是項目管理程序的任務。例如，項目管理程序應將由不同的程序員制作的文件的各個獨立版本整理在一起，它還應保存一組文件的更改歷史，這樣就能維持一個正在開發的程序的連貫版本了（這對那些由單個程序員管理的項目也很有用）。項目管理程序的編寫可與語言無關，但當其與編譯器捆綁在一起時，它就可以保持有關特定的編譯器和建立一個完整的可執行程序的鏈接程序操作的信息。在Unix系統中有兩個流行的項目管理程序：sccs（source code control system）和rcs（revision control system）。
?
?
?
?
編譯原理與技術的一整套理論在整個計算機科學領域占有相當重要的地位。學習它，對程序設計人員有很大的幫助。我們考究歷史會發現那些人人稱頌的程序設計大師都是編譯領域的高手，像寫出BASIC語言的BILL GATES，SUN的JAVA之父等等，在編譯上都有很深的造詣。
我們知道，詞法分析在編譯器的設計過程中是非常重要的，研究編譯原理中的算法可以幫助我們更加深層次的理解程序語言和內部機制，可以用來做簡單的命令解釋器，比如游戲的腳本引擎。而且，界面開發也需要編譯原理的知識。
正則表達式是一種可以用于模式匹配和替換的強有力的工具。例如搜索引擎就用到正則表達式的模式匹配功能。同時我們可以在幾乎所有的基于UNIX系統的工具中找到正則表達式的身影，例如，vi編輯器，Perl或PHP腳本語言，以及awk或sed shell程序等。此外，象JavaScript這種客戶端的腳本語言也提供了對正則表達式的支持。由此可見，對正則表達式的研究已經超出了某種語言或某個系統的局限。
編譯技術幾乎是所有計算機高級編程語言（諸如C、C++、JAVA等）所必須的，盡管有些（如BASIC）用解釋程序，但解釋程序的前端與編譯器是相通的，因此研究編譯技術是非常必要的。
編譯原理的相關技術還可應用于其它許多領域，例如文本編輯器、信息檢索系統、模式識別器；排版、繪圖系統；程序驗證器；集成電路設計；外文翻譯等等。
英特爾公司與中國合作項目中最顛峰的技術是中科院計算所與英特爾公司共同合作的IA-64位開放源代碼編譯系統。編輯器接受以高級程序設計語言(如C、C++和Fortran)編寫的程序，并將其轉換為處理器能夠識別的機器指令。像安騰這樣的處理器擁有多個功能部件，能夠并行地執行多條指令。因此，要求現代編譯器也能夠識別源代碼中的并行性，對指令流進行高度，以縮短程序的執行時間，提高處理器的性能。隨著微處理器體系結構的升級換代，同步提高編譯器技術也變得越來越重要。中國科學院計算技術研究所李國杰院士說：“隨著微處理器技術的飛速發展，處理器性能在很大程度上取決于編譯器的質量，編譯技術成為計算機的核心技術，地位變得越來越重要。我國要發展自己的微處理器事業，必然要有自己的編譯技術作為后盾。”“IA-64開放源代碼編譯系統的研究，有助于掌握先進的處理器和編譯器的設計技術以及產品軟件開發過程的管理技術和先進的軟件工程技術，為研制自有知識產權的微處理器和編譯器提供技術儲備。”而且，中國的龍芯的成功，應該歸功于好的技術路線和編譯技術的突破。
?
?
3.
程序設計及實現過程
?
?
???
要把正規表達式轉換為最小化狀態DFA，可以直接通過相關算法轉換，但是這將會使得設計過程非常復雜，而且程序的可理解性將會大大降低。所以整個程序通過下列三個步驟實現：
(一)???????????
由正規表達式構造NFA；
(二)???????????
把NFA轉化為與其等價的DFA；
(三)???????????
把DFA最小化；
?
?
?
程序設計過程主要是分析各階段設計過程要用到的相關算法。
(一)???????????
由正規表達式構造NFA：使用Thompson構造法
???
輸入：字母表∑上的一個正規表達式r。
???
輸出：接受L(r)的NFA N。
?
?
?
?
???
使用子集構造算法
???
輸入：一個NFA N；
???
輸出：一個接受同樣語言的DFA D。
???
方法：為D構造轉換表Dtran，DFA的每個狀態是NFA的狀態集，D將并行地模擬N對輸入串的所有可能的移動。
??? a
、構造NFA? N的狀態K的子集的算法：
???
假定所構造的子集族為C（D的狀態集合），即C= (T1, T2,,... TI),其中T1, T2,,... TI為狀態S的子集。
???
開始，令
e
-closure(S0)
為C中唯一成員，并且它是未被標記的。
??? while
（C中存在尚未被標記的子集T）do? begin?? {????? 標記T；?????????????????????? for 每個輸入字母a?? do ? begin{
??????????????????? U:=
e
-closure(move(T,a))
；????????? ?????
?????????????????? if? U
不在C中?? then ???????????
???????????????????
將U作為未標記的子集加在C中；
??? Dtran[T
，a]:=U??? } }
??? b
、
e
-closure
的計算
???
將T中所有的狀態壓入棧stack中；
???
將
e
-closure
（T）初始化為T；
??? While
棧stack不空do begin
???
將棧頂元素t彈出棧；
?
?? for
每個這樣的狀態u：從t到u有一條標記為
e
的邊do
?????? if u
不在
e
-closure
（T）內 do begin
??????????
將u添加到
e
-closure
（T）；
??????????
將u壓入棧stack中
?????? End
End
?
?
???
最小化DFA狀態數的算法：
???
輸入：DFA M（其狀態集合為S），輸入符號為
∑，轉換函數為f：S×∑--〉S，開始狀態為s0? ，接受狀態集為F。
???
輸出：一個DFA M’，它和M接受同樣的語言，且狀態數最少。
???
方法：
1、
構造具有兩個組的狀態集合的初始劃分∏：接受狀態組F，非接受狀態組S-F。
2、
對∏采用下面所述的過程來構造新的劃分∏new。
??? for
∏中的每個組G? do begin
??????
當且僅當對任意輸入符號a，狀態s和t在a上的轉換到達∏中的同一組中???? 的狀態時，才把G劃分成小組，以便G的兩個狀態s和t在同一小組中；
?????? /*
最壞情況下，一個狀態就可能成為一個組*/
??????
用所有新形成的小組集代替∏new中的G；
??? end
3、
如果∏new=∏，令∏final=∏，再執行步驟4；否則，令∏:=∏new，重復步驟2。
4、
在劃分∏final的每個狀態組中選一個狀態作為該組的代表，這些代表構成了簡化后的DFA M’的狀態。令s是一個代表狀態，而且假設：在DFA M中，在輸入a上有從s到t的轉換。令t所在組的代表是r（r可能就是t），那么在M’中有一個從s到r的a上的轉換。令包含s0的狀態組的代表是M’的開始狀態，并令M’的接受狀態是那些屬于F集的狀態所在組的代表。注意，∏final的每個組或者僅含F中的狀態，或者不含F中的狀態。
5、
如果M’含有死狀態（即一個對所有輸入符號都有到自身的轉換的非接受狀態d），即從M’中去掉它；刪除從開始狀態不可到達的狀態；取消從任何其它狀態到死狀態的轉換定義。
?
?
?
???
詞法分析的任務是對輸入的字符串形式的源程序按順序進行掃描，在掃描的同時，根據源語言的詞法規則識別具有獨立意義的單詞（符號），并產生與其等價的屬性字流（內部編碼）作為輸出。通常屬性字流即是對識別的單詞給出的標記符號的集合。
???
詞法分析程序一般具有如下功能:讀入字符串形式的源程序;識別出具有獨立意義的最小語法單位:單詞。
???
事實上，由正規表達式到最小化DFA的轉換源程序中的測試生成串部分就是對所輸入的單詞進行判斷，看其是否能被生成的DFA接受（也就是這個單詞是否符合正規式定義的要求）。這本質上就是一個簡單的詞法分析。為了更好地說明做這個題目的目的和意義，也為了使本文的主題得到升華，我另外設計了一個用于分析C語言詞法的簡單的詞法分析器，過程如下。
???
定義某種語言的單詞，并給出編號。該語言單詞包括：保留字、運算符、標識符、常量、格式符等。根據給定的語言子集構造詞法分析器。輸出為中間文件。在設計時為了便于理解，不使用內部編碼而用中文字符對同類型的單詞進行標識。例如所有定義的關鍵字（保留字）統一用“關鍵字”對其進行標識，當掃描時遇到關鍵字就輸出該關鍵字的字符串和“關鍵字”標識。
?
?
?
詞法分析程序的一般設計方法：
??? 1、根據要求寫出詞法分析的正規文法G；
??? 2、根據正規文法G，寫出正則式RE；
??? 3、根據正則式RE，畫出NFA；
??? 4、將NFA轉化為DFA；
??? 5、將DFA轉化為mininum state DFA；
??? 6、mininum state? DFA就是詞法分析程序的流程圖，根據此流程圖編寫相應的詞???????? 法分析程序。