編譯原理的目標語言集錦60句

由 文心雕龍 分享時間：2024-04-25 22:16:55 加入收藏我要投稿點贊

編譯原理知識點總結

編譯原理是大學計算機專業的必修科目，也是計算機的基礎知識，學好編譯原理，有助于更好的進行編程的操作，下面是編譯原理知識點總結，一起來看看吧！

　　編譯原理知識點總結

一編譯器

簡單講，編譯器就是將“高級語言”翻譯為“機器語言(低級語言)”的程序。一個現代編譯器的主要工作流程:源代碼(sourcecode)→預處理器

(preprocessor)→編譯器(compiler)→匯編程序(assembler)→目標代碼(objectcode)→鏈接器(Linker)→可執行程序(executables)

二工作原理

編譯是從源代碼(通常為高階語言)到能直接被計算機或虛擬機執行的目標代碼(通常為低階語言或機器語言)的翻譯過程。然而，也存在從低階語言到高階語言的編譯器，這類編譯器中用來從由高階語言生成的低階語言代碼重新生成高階語言代碼的又被叫做反編譯器。

也有從一種高階語言生成另一種高階語言的編譯器，或者生成一種需要進一步處理的的中間代碼的編譯器(又叫級聯)。

典型的編譯器輸出是由包含入口點的名字和地址，以及外部調用(到不在這個目標文件中的函數調用)的機器代碼所組成的目標文件。一組目標文件，不必是同一編譯器產生，但使用的編譯器必需采用同樣的輸出格式，可以鏈接在一起并生成可以由用戶直接執行的可執行程序

三編譯器的發展史

(1)20世紀50年代

IBM的JohnBackus帶領一個研究小組對FORTRAN語言及其編譯器進行開發。但由于當時人們對編譯理論了解不多，開發工作變得既復雜又艱苦。與此同時，NoamChomsky開始了他對自然語言結構的研究。他的發現最終使得編譯器的結構異常簡單，甚至還帶有了一些自動化。Chomsky的研究導致了根據語言文法的難易程度以及識別它們所需要的算法來對語言分類。正如現在所稱的Chomsky架構(ChomskyHierarchy)，它包括了文法的四個層次:0型文法、1型文法、2型文法和3型文法，且其中的每一個都是其前者的特殊情況。2型文法(或上下文無關文法)被證明是程序設計語言中最有用的，而且今天它已代表著程序設計語言結構的標準方式。分析問題(parsingproblem，用于上下文無關文法識別的`有效算法)的研究是在60年代和70年代，它相當完善的解決了這個問題。現在它已是編譯原理中的一個標準部分。

有限狀態自動機(FiniteAutomaton)和正則表達式(RegularExpression)同上下文無關文法緊密相關，它們與Chomsky的3型文法相對應。對它們的研究與Chomsky的研究幾乎同時開始，并且引出了表示程序設計語言的單詞的符號方式。

人們接著又深化了生成有效目標代碼的方法，這就是最初的編譯器，它們被一直使用至今。人們通常將其稱為優化技術(OptimizationTechnique)，但因其從未真正地得到過被優化了的目標代碼而僅僅改進了它的有效性，因此實際上應稱作代碼改進技術(CodeImprovementTechnique)。

當分析問題變得好懂起來時，人們就在開發程序上花費了很大的功夫來研究這一部分的編譯器自動構造。這些程序最初被稱為編譯器的編譯器(Compiler-compiler)，但更確切地應稱為分析程序生成器(ParserGenerator)，這是因為它們僅僅能夠自動處理編譯的一部分。這些程序中最著名的是Yacc(YetAnotherCompiler-compiler)，它是由SteveJohnson在1975年為Unix系統編寫的。類似的，有限狀態自動機的研究也發展了一種稱為掃描程序生成器(ScannerGenerator)的工具，Lex(與Yacc同時，由MikeLesk為Unix系統開發)是這其中的佼佼者。

在70年代后期和80年代早期，大量的項目都貫注于編譯器其它部分的生成自動化，這其中就包括了代碼生成。這些嘗試并未取得多少成功，這大概是因為操作太復雜而人們又對其不甚了解。

(2)國內編譯器的研發歷史

我國編譯器研發工作起步并不算晚，早在60年代初期，董韞美院士和楊芙清院士就分別在中科院和北大領導研究組開發編譯器，那時面向的高級語言是ALGOL和FORTRAN，目標機是國產機。

在改革開放前，由于國家需要，中科院、國防科大、江南計算所、北大等單位一直在研制國產計算機，包括大型機和高性能計算機(如向量機、并行機)，相應的也在研制高級語言編譯器。中科院計算所以董韞美院士領導的研究組先后開發了119機、109機的類ALGOL語言編譯器BCY。國防科大開發了向量編譯器和向量識別器。

70年代中科院計算所張兆慶教授研究組(以后稱ACTGroup)開始在國產機上研制FORTRAN語言編譯器，先后參與了眾多的院級和國家級科研攻關項目，主持開發了013，757，KJ8920等國產大型機系統中的FORTRAN語言編譯器，所研制的編譯器支持了數百萬行應用軟件的運行。

90年代以來ACTGroup承擔科學院重大項目，國家攻關項目，863項目，以及國際合作項目，先后開發了共享內存多處理機的并行識別器，分布式內存多處理機的并行識別器，SIMD芯片和VLIW芯片的并行優化C編譯器。將編譯技術與圖形學結合，ACTGroup還推出了集成化、可視化的并行編程環境。ACTGroup在先進編譯技術和并行編程環境方面的研究工作獲國內外專家高度評價，國際著名學者評價此研究組居編譯領域的世界先進行列。

(3)研究現狀

編譯器設計最近的發展包括:首先，編譯器包括了更加復雜算法的應用程序它用于推斷或簡化程序中的信息;這又與更為復雜的程序設計語言的發展結合在一起。其中典型的有用于函數語言編譯的Hindley-Milner類型檢查的統一算法。其次，編譯器已越來越成為基于窗口的交互開發環境(InteractiveDevelopmentEnvironment，IDE)的一部分，它包括了編輯器、連接程序、調試程序以及項目管理程序。這樣的IDE標準并沒有多少，但是對標準的窗口環境進行開發已成為方向。另一方面，盡管近年來在編譯原理領域進行了大量的研究，但是基本的編譯器設計原理在近20年中都沒有多大的改變，它現在正迅速地成為計算機科學課程中的中心環節。

在九十年代，作為GNU項目或其它開放源代碼項目的一部分，許多免費編譯器和編譯器開發工具被開發出來。這些工具可用來編譯所有的計算機程序語言。它們中的一些項目被認為是高質量的，而且對現代編譯理論感性趣的人可以很容易的得到它們的免費源代碼。

大約在1999年，SGI公布了他們的一個工業化的并行化優化編譯器Pro64的源代碼，后被全世界多個編譯器研究小組用來做研究平臺，并命名為Open64。Open64的設計結構好，分析優化全面，是編譯器高級研究的理想平臺。

(4)國內編譯器開發的現狀

90年代以來，國內主要以研制并行機為主，相應的并行編譯器研制也在國內開展起來。代表性的成果有:上海復旦大學朱傳琪教授研究組研制的面向共享存儲并行機的并行優化編譯器AFT達到世界領先水平。

清華大學湯志忠教授研究組在軟流水優化技術上做了很優秀的研究工作。清華大學鄭緯民教授研究組開發了交互式并行化系統TIPSExplorer，北京大學許卓群教授、李曉明教授研究組在HPF(HighPerformanceFortran)編譯器方面做了多年工作，取得很好的研究成果。此外，國防科大、江南計算所等單位也都有從事并行編譯技術研究。隨著芯片研制，國內還有若干單位也在開展基于GCC生成面向特定芯片的編譯器工作。

編譯原理期末總結復習

篇一：

【第1句】：簡答題

【第1句】：什么是編譯程序？

答：編譯程序是一種將高級語言程序(源程序)翻譯成低級語言(目標程序)的程序。

將高級程序設計語言程序翻譯成邏輯上等價的低級語言(匯編語言,機器語言)程序的翻譯程序。

【第2句】：請寫出文法的形式定義？

答：一個文法G抽象地表示為四元組G=（Vn,Vt,P,S）

–其中Vn表示非終結符號

–Vt表示終結符號，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ

–S是開始符號，

–P是產生式，形如：α→β(α∈V+且至少含有一個非終結符號，β∈V*)

【第3句】：語法分析階段的功能是什么？

答：在詞法分析的基礎上，根據語言的語法規則，將單詞符號串分解成各類語法短語(例：

程序、語句、表達式)。確定整個輸入串是否構成語法上正確的程序。

【第4句】：局部優化有哪些常用的技術？

答：優化技術1—刪除公共子表達式

優化技術2—復寫傳播

優化技術3—刪除無用代碼

優化技術4—對程序進行代數恒等變換（降低運算強度）

優化技術5—代碼外提

優化技術6—強度削弱

優化技術7—刪除歸納變量

優化技術簡介——對程序進行代數恒等變換（代數簡化）

優化技術簡介——對程序進行代數恒等變換（合并已知量）

5．編譯過程分哪幾個階段？

答：邏輯上分五個階段：詞法分析、語法分析、語義分析與中間代碼生成、代碼優化、目

標代碼生成。每個階段把源程序從一種表示變換成另一種表示。

【第6句】：什么是文法？

答：文法是描述語言的語法結構的形式規則。是一種工具，它可用于嚴格定義文案的結構；

用有窮的規則刻劃無窮的集合；文法是被用來精確而無歧義地描述語言的文案的構成方式；文法描述語言的時候不考慮語言的含義。

【第7句】：語義分析階段的功能是什么？

答：對語法分析所識別出的各類語法范疇分析其含義，進行初步的翻譯(翻譯成中間代碼)；

并對靜態語義進行審查。

【第8句】：代碼優化須遵循哪些原則？

答：等價原則：不改變運行結果

有效原則：優化后時間更短，占用空間更少

合算原則：應用較低的代價取得較好的優化效果

【第9句】：詞法分析階段的功能是什么？

答：

逐個讀入源程序字符并按照構詞規則切分成一系列單詞

任務：讀入源程序，輸出單詞符號

—濾掉空格，跳過注釋、換行符

—追蹤換行標志，指出源程序出錯的行列位置

—宏展開，……

【第10句】：什么是符號表？

答：符號表在編譯程序工作的過程中需要不斷收集、記錄和使用源程序中一些語法符號

的類型和特征等相關信息。這些信息一般以表格形式存儲于系統中。如常數表、變量名表、數組名表、過程名表、標號表等等，統稱為符號表。對于符號表組織、構造和管理方法的好壞會直接影響編譯系統的運行效率。

【第11句】：什么是屬性文法？

答：是在上下文無關文法的基礎上，為每個文法符號(含終結符和非終結符)配備若干個屬

性值，對文法的每個產生式都配備了一組屬性計算規則(稱為語義規則)。在語法分析過程中，完成語義規則所描述的動作，從而實現語義處理。

【第12句】：什么是基本塊

答：是指程序中一順序執行的語句序列，其中只有一個入口語句和一個出口語句，入口

是其第一個語句，出口是其最后一個語句。

【第13句】：代碼優化階段的功能是什么？

答：對已產生的中間代碼進行加工變換，使生成的目標代碼更為高效(時間和空間)。

【第14句】：文法分哪幾類？

答：文法有四種:設有G=(Vn,Vt,P,S),不同類型的文法只是對產生式的要求不同：

０型文法(短文文法)：G的每個產生式αβ滿足：α∈V+且α中至少含有一個非終結符,β∈V*

１型文法(上下文有關文法)：如果G的每個產生式αβ均滿足|β|>=|α|,僅當Ｓε除外，但S不得出現在任何產生式的右部

２型文法(上下文無關文法)：G的每個產生式為Aβ,A是一非終結符，β∈V*

３型文法(正規文法)：G的每個產生式的形式都是：AαB或Aα，其中A,B是非終結符，α是終結符串。(右線性文法)。

【第15句】：循環優化常用的技術有哪些？

答：代碼外提；強度削弱；刪除歸納變量。

【第16句】：什么是算符優先文法？

答：算符文法G的任何終結符a,b之間要么沒有優先關系，若有優先關系,

至多有

中的一種成立,則G為一算符優先文法。

【第2句】：計算題

（一）推導、最左推導、最右推導和語法樹,復習表達式文法及相關例題。

【第1句】：表達式的推導

例：G=({E},{i,+,*,(,)},P,E)

P：EE+E|E*E|(E)|i

答：表達式(i)和(i+i)*i的推導：

E(E)(i)

EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i

EE*EE*i(E)*i(E+E)*i(E+i)*i(i+i)*i

(i+i)*i的最左推導過程：

EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*i

(i+i)*i的最右推導過程：

EE*EE*i(E+E)*i(E+i)*i(i+i)*i

2．語法樹

例：對文法G=({E},{i,+,*,(,)},P,E)

P：EE+E|E*E|(E)|i

答：文案(i+i)*i的語法樹：

例：G=({E},{i,+,*,(,)},P,E)

P：EE+E|E*E|(E)|i

答：文案(i*i+i)的語法樹：

(1)E(E)(E+E)(E*E+E)(i*E+E)(i*i+i)

（二）給定語言求文法

（三）逆波蘭式

篇二：

翻譯程序:把一種語言程序轉換成另一種語言程序，且在功能上是相同的這樣的程序。編譯程序：把高級語言轉換成低級語言，且在功能上是相同的這樣的程序。

解釋程序：邊解釋邊執行源程序的程序。區別：編譯程序有中間代碼，而解釋程序沒有。編譯過程的五個階段：

【第1句】：詞法分析任務：對構成源程序的字符串進行掃描和分解，識別出一個個單詞。

【第2句】：語法分析任務：在詞法分析的基礎上，根據語言規則，把單詞符號串分解成各類語法

單位。

【第3句】：語義分析和中間代碼產生任務：對語法分析所識別出的各類語法范疇，分析其含義，

并進行初步翻譯。

【第4句】：優化任務：對前段產生的中間代碼進行加工變換，以期在最后階段能產生出更為高效

的目標代碼。

【第5句】：目標代碼生成任務：把中間代碼變換成特定機器上的低級語言代碼。

編譯程序的七個部分詞法分析器，語法分析器、語義分析與中間代碼產生器、優化器、目標代碼生成器、表格管理和出錯處理。

編譯程序生成的五個辦法：機器語言、高級語言、移植、自編譯方式和使用工具自動生成。詞法規則：指單詞符號的形成規則。（也就是正規式）

語法規則：規定了如何從單詞符號形成更大的結構。就是語法單位的形成規則。空字：不包含任何符號的序列。

閉包：中所有的符號組成的集合。

上下文無關文法是指：所定義的語法范疇是完全獨立于這種范疇可能出現的環境的文法。上下文無關文法的四個組成部分：一組終結符號、一組非終結符號、一個開始符號和一組產生式。

終結符號也就是不可再分的基本符號。

非終結符號是用來代表語法范疇，表示一定符號串的集合。

開始符號是語言中我們最感興趣的語法范疇。

產生式是定義語法范疇的書寫規則。

文案：文法中從開始符號推導的終結符號串。

句型：從開始符號推導的符號串。

語言：文法中所有文案的集合。

程序語言的單詞符號分為五種：關鍵字、標識符、常數、運算符和界符。

二元式表示：（種類，屬性）

正規式的運算符有三種：或，連接和閉包。優先順序是：閉包，連接，或。

DFA怎么識別字：若存在一條從初態結點到某一終態結點的通路，且這條通路上所有弧的標記符連接成的字是a，則稱a可為DFA所識別。

DFA怎么識別空字：若DFA的初態結點同時又是終態結點，則空字可為DFA所識別。NFA怎么識別字：若存在一條從某一初態結點到終態結點的通路，且這條通路上所有弧的標記字依序連接成的字等于a，則稱a可為NFA識別。

NFA怎么識別空字：若M的某些結點即是初態又是終態結點，或者存在一條從某個初態結點到某個終態結點的空通路，那么，空字可為M所識別。

語言的語法結構是用上下文無關文法描述的。

語法分析分為兩類：自上而下分析法，自下而上分析法。

自上而下分析法面臨的問題：【第1句】：文法的左遞歸問題。【第2句】：回溯【第3句】：成功可能是暫時的，產生虛假匹配。【第4句】：難于知道輸入串中出錯的確切位置。【第5句】：效率低，代價高。

為什么消除左遞歸？因為含有左遞歸的文法將自上而下分析的過程陷入無限循環。為什么消除回溯？因為回溯統一做一大堆無效的工作。

自下而上分析法：從輸入串開始，逐步進行歸約，知道歸約到文法的開始符號。短語：符號串推導過程中某非終結符推導的部分。

直接短語：符號串推導過程中某非終結符一步推導的部分。

句柄：一個句型的最左直接短語。

最左歸約是最有推導的逆過程。

中間語言形式：后綴式，三元式，四元式，間接三元式。

中間語言的好處：【第1句】：便于進行與機器無關的代碼優化工作。【第2句】：使編譯程序改變目標機更容易。

【第3句】：使編譯程序的`結構在邏輯上更為簡單，以中間語言為界面，編譯前端和后端的借口更清晰。

篇三：

(1)程序設計語言

機器語言:由0、1代碼構成，不需翻譯就可直接執行其程序。

匯編語言:機器指令助記符（偽代碼）形式，匯編后才可執行其程序。

高級程序設計語言:類自然語言和數學公式形式

(2)基本術語

源程序(SourceProgram)：用源語言寫的程序。源語言可以是匯編語言，也可以是高級程

序設計語言。

目標程序(TargetProgram)：也稱為“結果程序”，是源程序經翻譯程序加工以后所生成

的程序。目標程序可以用機器語言表示，也可以用匯編語言或其它中間語言表示。

翻譯程序(TranslatingProgram)：是指把一個源程序翻譯成邏輯上等價的目標程序的程序。

源程序為其輸入，目標程序為其輸出。

匯編程序(Assembler)：是指把一個匯編語言寫的源程序轉換成等價的機器語言表示的目

標程序的翻譯程序。

編譯程序(Compiler)：若源程序是用高級程序設計語言所寫，經翻譯程序加工生成目標程

序，則該翻譯程序就稱為“編譯程序”，也可稱為編譯器。

解釋程序：是高級語言翻譯程序的一種，他將源語言書寫的源程序作為輸入，解釋一句

后就提交計算機執行一句，并不形成目標程序，就像外語翻譯中的“口譯”一樣，不產生全文的翻譯文本。

運行系統(RunningSystem)：目標程序執行時，需要有一些子程序（如一些連接裝配程序

及一些連接庫等）配合進行工作，由這些子程序組成的一個子程序庫稱為運行系統。編譯系統(CompilingSystem)：編譯程序和運行系統合稱編譯系統。

(3)程序的翻譯

除機器語言程序外，用其它語言書寫的程序都必須經過翻譯才能被計算機識別。這一過

程由翻譯程序來完成。

編譯方式是一種分階段進行的方式，包括翻譯和運行兩部分。

前一階段：翻譯

后一階段：運行，由運行系統配合完成。

(4)過程

【第1句】：詞法分析階段

這個階段的任務是從左到右一個字符一個字符地讀入源程序，對構成源程序的字符流進行掃描和分解，從而識別出一個個單詞（也稱單詞符號或符號TOKEN）。

某源程序片斷如下：

beginvarsum,first,count:real;sum:=first+count*10end.

保留字beginvarrealend

標識符sumfirstcountsumfirstcount

界符.

逗號，逗號,冒號：分號；加號+乘號*賦值號：=整數1010

【第2句】：語法分析階段

是編譯過程的第二個階段。語法分析的任務是在詞法分析的基礎上將單詞序列分解成各類語法短語，如“程序”，“語句”，“表達式”等等。一般這種語法短語，也稱語法單位，或語法成分，或語法范疇。

語法分析所依據的是語言的語法規則，即描述程序結構的規則。通過語法分析確定整個輸入串是否構成一個語法上正確的程序。

【第3句】：語義分析階段

依據語言的語義規則，對語法分析得到的語法結構分析其含義以及應進行的運算，審查源程序中有無語義錯誤，為代碼生成階段收集類型信息。

【第4句】：中間代碼生成

在進行了上述的語法分析和語義分析階段的工作之后，有的編譯程序將源程序轉變成一種內部表示形式，這種內部表示形式叫做中間代碼。

所謂“中間代碼”是一種結構簡單，含義明確的記號系統，這種記號系統可以設計為多種多樣的形式。

重要的設計原則：一是容易生成；二是容易將它翻譯成目標代碼。

【第5句】：代碼優化

任務：對前階段產生的中間代碼系列進行變換或改造。目的是使生成的目標代碼更高效，即省時間省空間。例如上例四個四元式可優化為下面兩個四元式。

【第6句】：目標代碼生成

任務：將中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。它的工作與硬件系統結構和指令含義有關。

【第7句】：表格管理

編譯過程中源程序的各種信息被保留在種種不同的表格里，編譯各階段的工作都涉及到構造、查找或更新有關的表格，因此需要有表格管理的工作；

【第8句】：出錯處理

如果編譯過程中發現源程序有錯誤，編譯程度應報告錯誤的性質和錯誤發生的地點，并且將錯誤所造成的影響限制在盡可能小的范圍內，使得源程序的其余部分能繼續被編譯下去，有些編譯程序還能自動校正錯誤，這些工作稱之為出錯處理。

(5)前端與后端

參考上面的圖，目的是為了在多種源語言和多種目標語言的開發過程中，可以靈活搭配組合，消除重復開發的工作量，提高編譯系統的開發效率。

(6)遍

所謂遍，是對源程序或源程序的中間形式從頭到尾掃視并完成規定任務的過程。

每一遍掃視可完成一個階段或多個階段的功能。

一遍的編譯程序：以語法分析程序為核心。

多遍掃描的優點：

可以減少內存容量的需求，分遍后，以遍為單位分別調用編譯的各個程序，各遍程序可以相互覆蓋。

可使各遍的編譯程序相互獨立，結構清晰。

能夠進行充分優化，產生高質量的目標程序。

可將編譯程序分為前端和后端，有利于編譯程序的移植。

多遍掃描的缺點

每遍都要讀符號、送符號，增加了許多重復性的工作，降低編譯效率。

(7)程序設計語言范型（從支持的計算模式）

【第1句】：強制(命令)式語言:是面向動作的，即一個計算過程看做是一系列動作，其動作是命令驅動，以語言形式表示。

也稱過程式語言，如C,FORTRAN等;

【第2句】：函數式語言：注重程序表示的功能

也稱應用式語言，如ML和LISP等；

【第3句】：基于規則的語言：檢查一定的使能條件，滿足時執行動作

也稱邏輯程序設計語言，如PROLOG。

【第4句】：面向對象語言：提供抽象數據類型，支持封裝性、繼承性和多態性。

如C++和Java等。

(1)符號和符號串

【第1句】：字母表：元素的有窮非空集合。

【第2句】：符號串：由字母表中的符號組成的任何有窮序列。

【第3句】：符號串的頭尾，固有頭和固有尾：如果z=xy是一符號串，那么x是z的頭，y是z

的尾，如果x是非空的，那么y是固有尾；同樣如果y非空，那么x是固有頭。如:設z=abc，那么z的頭是，a,ab,abc,除abc外，其它都是固有頭；z的尾是,c,bc,abc,z的固有尾是,c,bc。

【第4句】：符號串的運算

（1）符號串的連接：設x和y是符號串，x和y的連接xy是把y的符號寫在x的符號后得的符號串。

如：x=ST,y=abu,則xy=STabu顯然有x=x=x。

（2）符號串的方冪：設x是符號串，把x自身連接n次得x的幾次方冪xn。

如：設x=ab則x0=x1=abx2=ababx3=ababab

（3）符號串集合的乘積：設A和B為符號串集合，則A和B的乘積定義為AB={xy|xA且yB}

如：a={a,b},B={00,11}則AB={a00,a11,b00,b11}顯然：{}A=A{}=A

（4）符號串集合的方冪：設A為符號串集，則A的n次方冪An定義為:An=AA……A=AAn-1=An-1A

（5）符號串集合的正閉包A+：A+=A1UA2U…UAnU…

（6）符號串集合的閉包A*：A*=A0UA+={}UA+

如：設有正字母表={0，1}則*=0U1U2U…UnU…={,0,1,00,01,10,11,000,001,……}

(2)文法

文法G定義為四元組（VN，VT，P，S）其中:

（1）VN為非終結符號集

非終結符號表示一個語言短語（或語法成分、語法單位）。如程序、語句、表達式等。一般用大寫字母或用〈〉括起表示非終結符號。

（2）VT為終結符號集

終結符號：組成語言的基本符號。是文法中不屬于非終結符號集合的符號。一般用小寫字母或不帶〈〉的符號表示。如程序設計語言的單詞符號。

設V=VNUVT，稱V為文法G的字母表。

（3）P為產生式（也稱規則）的集合。

產生式的形式：→或∷=，其中∈V+，∈V*

（4）S稱作識別符號或開始符號，是一個非終結符號。

一般表示此文法定義的最大語法短語，至少要在一條產生式中作為左部出現。句型、文案的定義

設G[S]是一文法，如果符號串x是從識別符號推導出來的，即有S*x，則稱x是文法G[S]的句型。

若x僅由終結符號組成，即S*x,xVT，則稱x為G[S]的文案。

句型：在一棵樹生長過程的任何時刻，所有那些端末結點自左至右的排列，就是一個句型。

語言的定義：文法G產生的語言記為L（G），它是文法G產生的全部文案的集合。文法等價定義：若L（G1）=L（G2）則稱文法G1和G2是等價的。

(3)文法的類型N.Chomsky

0型文法：定義0型語言，對應Turing機；

1型文法：定義1型語言，對應線性限界自動機；箭頭后面的要比前面的長或相等2型文法：定義2型語言，對應非確定下推自動機；箭頭前面的是非終結符，后面是串3型文法：定義3型語言，對應有限自動機。非終結符可以推出一個終結符或一個終結符和一個非終結符

最右推導也稱為規范推導，所得句型稱為規范句型。

如果一個文法存在某個句型對應兩棵不同的語法樹，則說這個文法是二義的。或者說，若一個文法中存在某個句型，它有兩個不同的最左（最右）推導，則這個文法是二義的。

上下文無關文法是否具有二義性是不可判定的。

但有些特殊的2型文法[例如LL（1）、LR（0）、LR（1）等文法]是無二義性的。一個文法兼有左遞歸和右遞歸是導致二義性的常見原因。

排除文法二義性通常有兩種方法:

（1）在語義上加些限制

（2）重新構造一個無二義性的文法

(4)句型的分析

句型的分析：就是識別一個符號串是否為某文法的句型。是某個推導的構造過程。分析方法分兩大類：自上而下分析法和自下而上分析法推導與歸約，最右推導是規范推導，逆過程為規范規約

若S*A+（由A+得）則稱是句型相對于非終結符A的短語。

若S*A(由A→得)則稱是句型相對于A→的直接短語（也稱簡單短語）。一個句型的最左直接短語稱為該句型的句柄。

一棵子樹（至少要有父子兩代）的所有端末結點自左至右排列起來形成相對于子樹根的短語。若子樹只有父子兩代，則得到直接短語。

(5)有關文法

（1）有害規則文法中含形如U→U的產生式。

它對描述語言沒有必要，且會引起文法的二義性。

（2）多余規則文法中任何一個文案的推導都用不到的規則。

（3）無用規則文法中含形如U→V的產生式，即單產生式。

為保證文法G的任一非終結符A在文案推導中出現，必須滿足如下兩個條件：

（1）A必須在某句型中出現，A。

（2）必須能夠從A推導出終結符號串t。

有關文法的化簡和改造，包括以下幾項工作：

（１）無用符號和無用產生式的刪除。

（２）－產生式的消除。

（３）單產生式的消除。

（４）左遞歸的消除。

(1)詞法分析輸出

單詞符號（TOKEN)是一個程序設計語言的基本語法符號。程序設計語言的單詞符號一般可分成下列5種：

1．基本字，也稱關鍵字，如PASCAL語言中的begin，end，if，while和var等。

2．標識符，用來表示各種名字，如常量名、變量名和過程名等。

3．常數，各種類型的常數，如25，【第3句】：1415，TRUE和"ABC"等。

4．運算符，如+，*，<=等。

5．界符，如逗點，分號，括號等。

詞法分析程序所輸出的單詞符號常常采用下二元式表示：（單詞種別，單詞自身的值）可用整數碼或助記符等表示。

(2)單詞的描述工具

程序設計語言中的單詞(TOKEN)是基本語法符號。單詞符號的語法可以用有效的工具加以描述。

正規式和它所表示的正規集的遞歸定義如下。設字母表為∑，輔助字母表∑={|,·,*,(,)}

定義（正規式和它所表示的正規集）：

設字母表為Σ，輔助字母表Σ`={Φ，ε，|，·，*，(，}。

②ε和Φ都是Σ上的正規式，它們所表示的正規集分別為{ε}和{}；

②任何a∈Σ，a是Σ上的一個正規式，它所表示的正規集為{a}；

③假定e1和e2都是Σ上的正規式，它們所表示的正規集分別為L(e1)和L(e2)，那么，(e1),e1|e2,e1·e2,e1*也都是正規式,它們所表示的正規集分別為L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))*。

④僅由有限次使用上述三步驟而定義的表達式才是Σ上的正規式，僅由這些正規式所表示的字集才是Σ上的正規集。

(3)有窮自動機

有窮自動機（也稱有限自動機）作為一種識別裝置，它能準確地識別正規集，即識別正規文法所定義的語言和正規式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程

編譯原理小論文

編譯原理是計算機專業的一門重要專業課，旨在介紹編譯程序構造的一般原理和基本方法。那么編譯原理小論文要怎么寫呢？不妨來參考一下小編帶來的編譯原理小論文樣本。希望大家喜歡哦！

　　編譯原理小論文

摘要：本文探討了在計算機軟件技術快速發展的情況下，高校計算機類專業編譯原理課程的改革問題。提出了編譯原理課程教學模型從過程式向對象式的轉變、編譯程序的面向對象構造（包括編譯算法的描述）等問題，以及由此帶來的教學內容的調整和課程實驗的設計問題。

關鍵詞：編譯程序;教學改革;對象式程序設計;Java

1引言

編譯原理課程是高校計算機類專業的重要基礎和骨干課程。編譯原理對計算機專業的學生的重要性與高等數學對理科學生的重要性幾乎可以相提并論。同時，由于這門課程涉及其他多門課程的知識，使得它成為大學階段中最難學的課程之一。

從表面上看，編譯程序是將高級語言源程序翻譯成低級語言程序，但編譯程序構造的基本原理和技術也廣泛應用于一般軟件的設計和實現，其中的設計思想、算法、思維方式和技術都可能會對學生今后的職業發展產生比較大的影響。

當今，程序設計已經基本上從傳統的過程式轉向對象式，并且正在從對象式轉向組件型。這其實是程序設計范型的變遷，是在計算機技術背景下認識世界的觀點的變化：過程式將完成事務看成是一系列的步驟，而對象式卻將世界看成是由一系列對象組成的，這些對象之間交互合作完成特定的事務。從過程式到對象式，有著質的變化，而非一般的修改和完善，由此帶來了語言（算法描述工具）的變化。編程語言影響思維，面向對象的思維方法又促進了編程語言的發展。

目前，程序設計的一些后繼課程，如數據結構等都進行了同步跟進，出現了諸如用C++或Java描述的數據結構教材。但編譯原理課程卻沒有及時跟進，上述改變基本上沒有反映到編譯原理課程中。這門課程近20年來基本上沒有大的變化，教學內容仍然是基于過程式語言展開的，編譯算法和模型描述是用PASCAL語言或者C語言。雖然個別教材加入了少量關于對象式語言編譯技術的內容，那也是稍加點綴而已，作用不大。這就造成了一種奇怪的現象：對象式語言已經成了高校計算機教學的主流語言，社會上大量使用的也是對象式語言，而我們的編譯原理教學仍然沿襲舊的一套。這種“狀態”嚴重地脫離了計算機技術的發展和社會的實際需要，因此需要進行“調態”，其根本做法是“轉型”，即將本課程的討論對象從過程式語言轉到對象式語言。

國外近年關于編譯原理方面的新教材已經有了重要改變，不再連篇累牘地討論那些已經過時的內容，增加了許多新的內容。其中一個重大改變是出現了用對象式語言描述編譯算法和教學模型的編譯原理教材，如：用Java語言描述的編譯原理教材，且其教學模型為MiniJava。

這種改變也涉及到課程上機實踐。眾所周知，編譯原理課程的學術性和實踐性都很強：學術性是這門課程的生命所在，實踐性是這門課程的活力所在。因而本課程的上機實踐也要作同步調整。

2課程內容圍繞對象式語言展開

研究程序設計語言的語法描述需要有文法理論的支持，老教材中文法、詞法分析和語法分析部分內容基本上不需要作什么變動。詞法分析主要依賴有窮狀態自動機理論，語法分析主要講述LL方法和LR方法，其他方法略做介紹即可，無需展開討論。LL方法和LR方法含蓋了許多分析技術，理論性和應用性都很強，完全可以代表主流技術。

重要的就是研究對象和教學模型的改變。首先，研究對象將從過程式程序設計語言轉到對象式程序設計語言（當然還可以兼顧過程式），例如Java、C++等，圍繞實現這類語言的編譯實現技術展開討論。對象式程序設計語言的要素是封裝、繼承、多態性，在編譯實現時都必須仔細考慮。其次，涉及到對象式程序設計語言編譯程序教學的模型選擇問題。目前傳統的教材選擇的教學模型有PL/0、TiniC等。實踐證明，圍繞某個模型展開編譯設計技術的討論，效果是比較好的。課程研究對象和教學模型的改變涉及到調整的章節主要有語法分析、語義分析、代碼生成、符號表管理、存貯分配等方面。

一旦我們討論的模型發生變化，這些章節的內容就要作很大調整。如對象式語言的作用域規則、語言動態特性、模塊化封裝（類）、類的繼承、多態性的實現等，都需要具體的技術來實現，這些都要反映在教材和教學中。

就課程中關于代碼生成內容來看，目前Java編譯程序生成Java虛擬機（JVM）代碼，C#生成MSIL虛擬機代碼。這兩個虛擬機作為教學模型來說可能比較復雜了一些，在教學中可以選定一個簡單的子集;或者在PL/0虛擬機上適當增加一些指令代碼，以便于代碼生成、存貯分配等部分的講解。

實踐證明，作為教學模型，在教材上提供一個小型語言的編譯程序供學生分析和研究，非常有利于加深對基本原理的理解和掌握。這個小型編譯程序可以比較小但應該能夠說明一些基本問題，例如傳統的編譯原理課程中選擇PL/0編譯程序作為教學模型，就收到了比較好的教學效果。在對象式程序設計語言編譯原理課程中選擇Object—pl/0或者MiniJava作為教學模型是比較恰當的。前者是在傳統的PL/0語言上增加類，補充封裝、繼承、多態性之語言成分得到的;后者是對Java語言進行適當簡化得到的，其主要語法描述。

編譯原理課程可以圍繞此模型展開討論。國外已經有這類教材出現，并且不少大學已經開始使用。

3用對象式語言描述編譯算法和教學模型

本課程中各類編譯算法都應該伴隨著教學模型的變化，改用對象式語言來描述，如用Java語言描述或者用C++語言描述。其中一個重大的變化是教學模型如MiniJava或Object—pl/0要用對象式語言實現，也就是提出了教學模型的面向對象構造問題，這就比較好地將討論對象和描述討論對象的語言統一起來了。國外有的教材就選擇了用Java描述MiniJava編譯程序。

編譯程序是一個重要的中大型軟件，傳統的編譯程序大都是用PASCAL、C等語言描述的（參見圖2）。像編譯程序這樣的中大型程序如何用類這個工具來進行分解，其實是對學生的對象式程序設計能力的一個重要檢驗。學習用對象式語言來描述編譯程序，學生可能會受到一次嚴格的對象式語言程序設計訓練，編譯程序如何用類這個工具進行分解，這些類（對象）如何合作完成編譯任務，都需要較好的對象式程序設計基礎。圖3是一個程序設計語言文法的面向對象表示。

傳統的編譯程序構造主要存在如下一些問題：

（1）傳統編譯程序試圖通過將編譯程序根據功能模塊分解，而使整個編譯程序的復雜性降低。這種方法雖然在一定程度上簡化了編譯過程。但為了處理大型、復雜且多變的編譯程序，僅僅將它按照功能分解成詞法分析、語法分析、語義處理和代碼生成幾個階段是遠遠不夠的。

（2）傳統的編譯程序構造中，編譯的每個階段依然是大型、復雜的，且每個階段內部依然存在復雜的聯系，這對編譯程序的可維護性沒有實際上的改變，反而造成維護困難。

（3）雖然傳統的編譯程序構造有著豐富的理論基礎，也有一些工具諸如Lex、Yacc等，但對一個具體的編譯程序的構造仍然要從最基本的描述開始。傳統的編譯程序構造的功能分解方法缺乏支持復用的良好機制。

總之，過程式程序設計范式存在的問題在編譯程序設計中廣泛存在。而用對象式程序設計語言來描述編譯程序，則對象式程序設計范式帶來的好處基本上都能夠得到。具體主要表現在：

（1）編譯程序效率高。由于面向對象的編譯程序構造采用的是語法樹構造法，可以得到上下文相關信息，并根據上下文進行語法樹的優化，所以生成的代碼效率高。

（2）復用方便。由于語法類和具體的語法結構一一對應，所以在復用語法結構時，可以直接得到能被復用的語法類，不需要經過查找過程。

（3）修改方便。由于面向對象方法中的封裝和多態等技術的實現，語義處理方法中所用到的數據都是局部數據，因此要做語義修改時，只要繼承相應的語法類，并且重載相應的語義處理方法即可，需修改的內容較之傳統方法要少。

（4）有利于構造編譯程序類庫，使得編譯程序的構造能夠大量復用已有的類，這是更高層次上的復用。

4課程實驗的設計

計算機學科是一門技術學科，它雖然有一定的科學的成分，但工程技術的成分更多一些，因此需要加強動手能力的培養。編譯原理課程除了注重它的原理性，還必須注重其實踐性。學習這門課程時，學生對編譯的理解往往只停留在書本的概念上，而不知道怎樣把編譯理論應用到實際的編譯程序設計的實踐中。另外，有些學校只將教學內容鎖定在文法、詞法分析（有窮狀態自動機）、語法分析（LL、LR文法）上，以應付學生考研的需要。這些做法使得學生很難掌握這門課程的精髓。

編譯系統可能是所有軟件系統中最復雜的'系統之一，通過本課程實踐環節的教學，還可以幫助學生掌握一些大、中型軟件設計的技術和技巧，提高學生面向對象軟件開發的綜合能力。

傳統的編譯原理課程往往要求學生自己實現一個詞法分析程序;實現一個基于遞歸子程序遞歸下降分析程序或基于預測分析表的語法分析程序;為某虛擬機（例如PL/0虛擬機）生成代碼;對教學模型（例如PL/0）進行擴充，寫出完整的編譯程序等。且在此過程中學生可以借助詞法分析自動生成程序Lex和語法分析自動生成程序Yacc進行有關實驗。我們要求學生通過對教學模型的分析，能夠在機器上動手實現一個小的編譯系統，以加深對編譯整個過程的一致性、連貫性、整體性的理解。

一旦我們的討論對象改變為對象式語言，則其編譯程序語法和詞法分析的自動生成不能再采用Lex、Yacc這類工具了，需要改用JavaCC（JavaCompilerCompiler）或SableCC等，它們都能生成Java語言代碼;或者使用Jikespg（Jikespasergernerator），它生成C++代碼。

我們初步制定了本課程的實踐環節，它主要分四個層次：

（1）借助JavaCC或SableCC等工具讓學生自動生成小語言的詞法分析和語法分析程序。這個實驗的目的是教會學生關于詞法分析和語法分析的自動生成，同時弄清這些工具生成出來的代碼的程序結構，特別是面向對象的類結構。

（2）為上面生成的語法樹添加語義動作，完成生成代碼的工作。這個實驗的目的是讓學生理解如何在抽象語法樹上添加語義動作，理解為虛擬機生成代碼的知識。

（3）擴展教學模型，如MiniJava，為其增加一些語言成分，如有關語句等，然后為其構造完整的編譯程序。這一實驗讓學生把握編譯的總體，弄清各部分之間的關系。

（4）逐步構造面向對象的編譯程序類庫，使得“編寫”編譯程序逐步走向“組裝”編譯程序。

5結束語

對計算機人才的層次結構、知識、能力與素質等方面的要求在很大程度上取決于計算機市場。我們需要與時俱進，適時考慮相應教學體系和內容的改變。依賴過程范性的編譯原理課程勢必要被依賴對象范性的編譯原理課程所取代，這是軟件技術發展和社會實際應用的需要。但建立本課程新的課程信念、課程價值、課程技術等尚需時日，需要不斷探索和創新。

編譯原理課程的改革不僅需要教師付出大量辛勤勞動，及時跟進技術的發展，還需要好的教材、好的課程實驗設計。《對象式程序設計語言編譯原理》便是我們按照上述思路來編寫的教材。

參考文獻

[1]中國計算機本科專業發展戰略研究報告[J]。中國大學教學，2005，5：7—10。

[2]AndrewW。Apple。現代編譯器的Java實現[M]。北京：電子工業出版社，2004。

[3]DickGruneetc。ModernCompilerDesign[M]。JOHNWILEY&SONS，LTD，2002。

[4]胡學聯。開設軟件新技術課程的實踐探索[J]。黃河科技大學學報，2004，2。

[5]胡學聯等。對象式程序設計語言編譯原理[M]。

電路原理知識點總結

通過對知識與方法的歸納總結，使知識整體化、有序化、條理化、系統化、結構化、網絡化、形象化。使之便于理解，便于記憶，便于應用。下面就是小編整理的電路原理知識點總結，一起來看一下吧。

【第1句】：定義：把電源、用電器、開關、導線連接起來組成的電流的路徑，電路知識點總結。

【第2句】：各部分元件的作用：(1)電源：提供電能的裝置;(2)用電器：工作的設備;(3)開關：控制用電器或用來接通或斷開電路;(4)導線：連接作用，形成讓電荷移動的通路

【第2句】：電路的狀態：通路、開路、短路