編譯原理期末總結(jié)復(fù)習
篇一：
一、簡答題
1.什么是編譯程序？
答：編譯程序是一種將高級語言程序(源程序)翻譯成低級語言(目標程序)的程序 。
將高級程序設(shè)計語言程序翻譯成邏輯上等價的低級語言(匯編語言,機器語言)程序的翻譯程序。
2.請寫出文法的形式定義？
答：一個文法G抽象地表示為四元組 G=（Vn,Vt,P,S）
– 其中Vn表示非終結(jié)符號
– Vt表示終結(jié)符號，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ
– S是開始符號，
– P是產(chǎn)生式，形如：α→β(α∈V+且至少含有一個非終結(jié)符號，β∈V*)
3.語法分析階段的功能是什么？
答：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，將單詞符號串分解成各類語法短語(例：
程序、語句、表達式)。確定整個輸入串是否構(gòu)成語法上正確的程序。
4.局部優(yōu)化有哪些常用的技術(shù)？
答：優(yōu)化技術(shù)1—刪除公共子表達式
優(yōu)化技術(shù)2—復(fù)寫傳播
優(yōu)化技術(shù)3—刪除無用代碼
優(yōu)化技術(shù)4—對程序進行代數(shù)恒等變換（降低運算強度）
優(yōu)化技術(shù)5—代碼外提
優(yōu)化技術(shù)6—強度削弱
優(yōu)化技術(shù)7—刪除歸納變量
優(yōu)化技術(shù)簡介——對程序進行代數(shù)恒等變換（代數(shù)簡化）
優(yōu)化技術(shù)簡介——對程序進行代數(shù)恒等變換（合并已知量）
5．編譯過程分哪幾個階段？
答：邏輯上分五個階段：詞法分析、語法分析、語義分析與中間代碼生成、代碼優(yōu)化、目
標代碼生成。每個階段把源程序從一種表示變換成另一種表示。
6. 什么是文法？
答：文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則。是一種工具，它可用于嚴格定義句子的結(jié)構(gòu)；
用有窮的規(guī)則刻劃無窮的集合；文法是被用來精確而無歧義地描述語言的句子的構(gòu)成方式；文法描述語言的時候不考慮語言的含義。
7. 語義分析階段的功能是什么？
答：對語法分析所識別出的各類語法范疇分析其含義，進行初步的翻譯(翻譯成中間代碼)；
并對靜態(tài)語義進行審查。
8.代碼優(yōu)化須遵循哪些原則？
答：等價原則：不改變運行結(jié)果
有效原則：優(yōu)化后時間更短，占用空間更少
合算原則：應(yīng)用較低的代價取得較好的優(yōu)化效果
9.詞法分析階段的功能是什么？
答：
逐個讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞
任務(wù)：讀入源程序，輸出單詞符號
— 濾掉空格，跳過注釋、換行符
— 追蹤換行標志，指出源程序出錯的行列位置
— 宏展開，……
10.什么是符號表？
答：符號表在編譯程序工作的過程中需要不斷收集、記錄和使用源程序中一些語法符號
的類型和特征等相關(guān)信息。這些信息一般以表格形式存儲于系統(tǒng)中。如常數(shù)表、變量名表、數(shù)組名表、過程名表、標號表等等，統(tǒng)稱為符號表。對于符號表組織、構(gòu)造和管理方法的好壞會直接影響編譯系統(tǒng)的運行效率。
11.什么是屬性文法？
答：是在上下文無關(guān)文法的基礎(chǔ)上，為每個文法符號(含終結(jié)符和非終結(jié)符)配備若干個屬
性值，對文法的每個產(chǎn)生式都配備了一組屬性計算規(guī)則(稱為語義規(guī)則)。在語法分析過程中，完成語義規(guī)則所描述的動作，從而實現(xiàn)語義處理。
12.什么是基本塊
答：是指程序中一順序執(zhí)行的語句序列，其中只有一個入口語句和一個出口語句，入口
是其第一個語句，出口是其最后一個語句。
13.代碼優(yōu)化階段的功能是什么？
答：對已產(chǎn)生的中間代碼進行加工變換，使生成的目標代碼更為高效(時間和空間)。
14.文法分哪幾類？
答：文法有四種:設(shè)有G=(Vn,Vt,P,S),不同類型的文法只是對產(chǎn)生式的要求不同：
�。靶臀姆�(短文文法)： G的每個產(chǎn)生式αβ滿足：α∈V+且α中至少含有一個非終結(jié)符,β∈V*
１型文法(上下文有關(guān)文法)：如果G的每個產(chǎn)生式αβ均滿足|β|>=|α|,僅當Ｓε除外，但S不得出現(xiàn)在任何產(chǎn)生式的右部
�。残臀姆�(上下文無關(guān)文法)：G的每個產(chǎn)生式為Aβ, A是一非終結(jié)符，β∈V*
３型文法(正規(guī)文法)：G的每個產(chǎn)生式的形式都是：AαB或Aα，其中A,B是非終結(jié)符，α是終結(jié)符串。(右線性文法)。
15.循環(huán)優(yōu)化常用的技術(shù)有哪些？
答：代碼外提；強度削弱；刪除歸納變量。
16.什么是算符優(yōu)先文法？
答：算符文法G的任何終結(jié)符a,b之間要么沒有優(yōu)先關(guān)系，若有優(yōu)先關(guān)系,
至多有
中的一種成立,則G為一算符優(yōu)先文法。
二、計算題
�。ㄒ唬┩茖�(dǎo)、最左推導(dǎo)、最右推導(dǎo)和語法樹,復(fù)習表達式文法及相關(guān)例題。
1. 表達式的推導(dǎo)
例： G = ({E}, {i, +, *, (, ) } , P , E)
P： E E+E | E*E | (E) | i
答：表達式(i)和(i+i)*i的推導(dǎo)：
E (E) (i)
E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i
E E*E E*i (E)* i (E + E)*i (E+ i)*i (i + i)*i
(i+i)*i的最左推導(dǎo)過程：
E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i
(i+i)*i的最右推導(dǎo)過程：
E E*E E*i (E + E)*i (E+ i)*i (i + i)*i
2．語法樹
例：對文法G = ({E}, {i, +, *, (, ) } , P , E)
P： E E + E | E * E | ( E ) | i
答： 句子(i+i)*i 的語法樹：
例： G = ({E}, {i, +, *, (, ) } , P , E)
P： E E + E | E * E | ( E ) | i
答：句子 ( i * i + i)的語法樹：
(1) E (E) (E + E) (E * E + E) (i * E + E) (i *i + i)
�。ǘ┙o定語言求文法
�。ㄈ┠娌ㄌm式
篇二：
翻譯程序:把一種語言程序轉(zhuǎn)換成另一種語言程序，且在功能上是相同的這樣的程序。 編譯程序：把高級語言轉(zhuǎn)換成低級語言，且在功能上是相同的這樣的程序。
解釋程序：邊解釋邊執(zhí)行源程序的程序。區(qū)別：編譯程序有中間代碼，而解釋程序沒有。 編譯過程的五個階段：
1、 詞法分析 任務(wù)：對構(gòu)成源程序的字符串進行掃描和分解，識別出一個個單詞。
2、 語法分析 任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語言規(guī)則，把單詞符號串分解成各類語法
單位。
3、 語義分析和中間代碼產(chǎn)生 任務(wù)：對語法分析所識別出的各類語法范疇，分析其含義，
并進行初步翻譯。
4、 優(yōu)化 任務(wù)：對前段產(chǎn)生的中間代碼進行加工變換，以期在最后階段能產(chǎn)生出更為高效
的目標代碼。
5、 目標代碼生成 任務(wù)：把中間代碼變換成特定機器上的低級語言代碼。
編譯程序的七個部分詞法分析器，語法分析器、語義分析與中間代碼產(chǎn)生器、優(yōu)化器、目標代碼生成器、表格管理和出錯處理。
編譯程序生成的五個辦法：機器語言、高級語言、移植、自編譯方式和使用工具自動生成。 詞法規(guī)則：指單詞符號的形成規(guī)則。（也就是正規(guī)式）
語法規(guī)則：規(guī)定了如何從單詞符號形成更大的結(jié)構(gòu)。就是語法單位的形成規(guī)則。 空字：不包含任何符號的序列。
閉包：中所有的符號組成的集合。
上下文無關(guān)文法是指：所定義的語法范疇是完全獨立于這種范疇可能出現(xiàn)的環(huán)境的文法。 上下文無關(guān)文法的四個組成部分：一組終結(jié)符號、一組非終結(jié)符號、一個開始符號和一組產(chǎn)生式。
終結(jié)符號也就是不可再分的基本符號。
非終結(jié)符號是用來代表語法范疇，表示一定符號串的集合。
開始符號是語言中我們最感興趣的語法范疇。
產(chǎn)生式是定義語法范疇的書寫規(guī)則。
句子：文法中從開始符號推導(dǎo)的終結(jié)符號串。
句型：從開始符號推導(dǎo)的符號串。
語言：文法中所有句子的集合。
程序語言的單詞符號分為五種：關(guān)鍵字、標識符、常數(shù)、運算符和界符。
二元式表示：（種類，屬性）
正規(guī)式的`運算符有三種：或，連接和閉包。優(yōu)先順序是：閉包，連接，或。
DFA怎么識別字：若存在一條從初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，且這條通路上所有弧的標記符連接成的字是a，則稱a可為DFA所識別。
DFA怎么識別空字：若DFA的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，則空字可為DFA所識別。 NFA怎么識別字：若存在一條從某一初態(tài)結(jié)點到終態(tài)結(jié)點的通路，且這條通路上所有弧的標記字依序連接成的字等于a，則稱a可為NFA識別。
NFA怎么識別空字：若M的某些結(jié)點即是初態(tài)又是終態(tài)結(jié)點，或者存在一條從某個初態(tài)結(jié)點到某個終態(tài)結(jié)點的空通路，那么，空字可為M所識別。
語言的語法結(jié)構(gòu)是用上下文無關(guān)文法描述的。
語法分析分為兩類：自上而下分析法，自下而上分析法。
自上而下分析法面臨的問題：1.文法的左遞歸問題。2.回溯3.成功可能是暫時的，產(chǎn)生虛假匹配。4.難于知道輸入串中出錯的確切位置。5.效率低，代價高。
為什么消除左遞歸？因為含有左遞歸的文法將自上而下分析的過程陷入無限循環(huán)。 為什么消除回溯？因為回溯統(tǒng)一做一大堆無效的工作。
自下而上分析法：從輸入串開始，逐步進行歸約，知道歸約到文法的開始符號。 短語：符號串推導(dǎo)過程中某非終結(jié)符推導(dǎo)的部分。
直接短語：符號串推導(dǎo)過程中某非終結(jié)符一步推導(dǎo)的部分。
句柄：一個句型的最左直接短語。
最左歸約是最有推導(dǎo)的逆過程。
中間語言形式：后綴式，三元式，四元式，間接三元式。
中間語言的好處：1.便于進行與機器無關(guān)的代碼優(yōu)化工作。2.使編譯程序改變目標機更容易。
3.使編譯程序的結(jié)構(gòu)在邏輯上更為簡單，以中間語言為界面，編譯前端和后端的借口更清晰。
篇三：
(1)程序設(shè)計語言
機器語言: 由0、1代碼構(gòu)成，不需翻譯就可直接執(zhí)行其程序。
匯編語言: 機器指令助記符（偽代碼）形式，匯編后才可執(zhí)行其程序。
高級程序設(shè)計語言: 類自然語言和數(shù)學(xué)公式形式
(2) 基本術(shù)語
源程序(Source Program)：用源語言寫的程序。源語言可以是匯編語言，也可以是高級程
序設(shè)計語言。
目標程序(Target Program) ：也稱為“結(jié)果程序”，是源程序經(jīng)翻譯程序加工以后所生成
的程序。目標程序可以用機器語言表示，也可以用匯編語言或其它中間語言表示。
翻譯程序(Translating Program)：是指把一個源程序翻譯成邏輯上等價的目標程序的程序。
源程序為其輸入，目標程序為其輸出。
匯編程序(Assembler)：是指把一個匯編語言寫的源程序轉(zhuǎn)換成等價的機器語言表示的目
標程序的翻譯程序。
編譯程序(Compiler)：若源程序是用高級程序設(shè)計語言所寫，經(jīng)翻譯程序加工生成目標程
序，則該翻譯程序就稱為“編譯程序”，也可稱為編譯器。
解釋程序：是高級語言翻譯程序的一種，他將源語言書寫的源程序作為輸入，解釋一句
后就提交計算機執(zhí)行一句，并不形成目標程序，就像外語翻譯中的“口譯”一樣，不產(chǎn)生全文的翻譯文本。
運行系統(tǒng)(Running System)：目標程序執(zhí)行時，需要有一些子程序（如一些連接裝配程序
及一些連接庫等）配合進行工作，由這些子程序組成的一個子程序庫稱為運行系統(tǒng)。 編譯系統(tǒng)(Compiling System)：編譯程序和運行系統(tǒng)合稱編譯系統(tǒng)。
(3) 程序的翻譯
除機器語言程序外，用其它語言書寫的程序都必須經(jīng)過翻譯才能被計算機識別。這一過
程由翻譯程序來完成。
編譯方式是一種分階段進行的方式，包括翻譯和運行兩部分。
前一階段：翻譯
后一階段：運行，由運行系統(tǒng)配合完成。
(4) 過程
1、詞法分析階段
這個階段的任務(wù)是從左到右一個字符一個字符地讀入源程序，對構(gòu)成源程序的字符流進行掃描和分解，從而識別出一個個單詞（也稱單詞符號或符號TOKEN）。
某源程序片斷如下：
begin var sum, first, count: real; sum:=first+count*10 end.
保留字 begin var real end
標識符 sumfirstcountsumfirstcount
界符 .
逗號，逗號,冒號：分號；加號+乘號*賦值號 ：=整數(shù)10 10
2、語法分析階段
是編譯過程的第二個階段。語法分析的任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列分解成各類語法短語，如“程序”，“語句”，“表達式”等等。一般這種語法短語，也稱語法單位，或語法成分，或語法范疇。
語法分析所依據(jù)的是語言的語法規(guī)則，即描述程序結(jié)構(gòu)的規(guī)則。通過語法分析確定整個輸入串是否構(gòu)成一個語法上正確的程序。
3、語義分析階段
依據(jù)語言的語義規(guī)則，對語法分析得到的語法結(jié)構(gòu)分析其含義以及應(yīng)進行的運算，審查源程序中有無語義錯誤，為代碼生成階段收集類型信息。
4、中間代碼生成
在進行了上述的語法分析和語義分析階段的工作之后，有的編譯程序?qū)⒃闯绦蜣D(zhuǎn)變成一種內(nèi)部表示形式，這種內(nèi)部表示形式叫做中間代碼。
所謂“中間代碼”是一種結(jié)構(gòu)簡單，含義明確的記號系統(tǒng)，這種記號系統(tǒng)可以設(shè)計為多種多樣的形式。
重要的設(shè)計原則：一是容易生成；二是容易將它翻譯成目標代碼。
5、代碼優(yōu)化
任務(wù)：對前階段產(chǎn)生的中間代碼系列進行變換或改造。目的是使生成的目標代碼更高效，即省時間省空間。例如上例四個四元式可優(yōu)化為下面兩個四元式。
6、目標代碼生成
任務(wù)：將中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。它的工作與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)。
7、表格管理
編譯過程中源程序的各種信息被保留在種種不同的表格里，編譯各階段的工作都涉及到構(gòu)造、查找或更新有關(guān)的表格，因此需要有表格管理的工作；
8、出錯處理
如果編譯過程中發(fā)現(xiàn)源程序有錯誤，編譯程度應(yīng)報告錯誤的性質(zhì)和錯誤發(fā)生的地點，并且將錯誤所造成的影響限制在盡可能小的范圍內(nèi)，使得源程序的其余部分能繼續(xù)被編譯下去，有些編譯程序還能自動校正錯誤，這些工作稱之為出錯處理。
(5) 前端與后端
參考上面的圖，目的是為了在多種源語言和多種目標語言的開發(fā)過程中，可以靈活搭配組合，消除重復(fù)開發(fā)的工作量，提高編譯系統(tǒng)的開發(fā)效率。
(6) 遍
所謂遍，是對源程序或源程序的中間形式從頭到尾掃視并完成規(guī)定任務(wù)的過程。
每一遍掃視可完成一個階段或多個階段的功能。
一遍的編譯程序：以語法分析程序為核心 。
多遍掃描的優(yōu)點：
可以減少內(nèi)存容量的需求，分遍后，以遍為單位分別調(diào)用編譯的各個程序，各遍程序可以相互覆蓋。
可使各遍的編譯程序相互獨立，結(jié)構(gòu)清晰。
能夠進行充分優(yōu)化，產(chǎn)生高質(zhì)量的目標程序。
可將編譯程序分為前端和后端，有利于編譯程序的移植。
多遍掃描的缺點
每遍都要讀符號、送符號，增加了許多重復(fù)性的工作，降低編譯效率。
(7) 程序設(shè)計語言范型（從支持的計算模式）
1. 強制(命令)式語言:是面向動作的，即一個計算過程看做是一系列動作，其動作是命令驅(qū)動，以語言形式表示。
也稱過程式語言，如C,FORTRAN等;
2. 函數(shù)式語言：注重程序表示的功能
也稱應(yīng)用式語言，如ML和LISP等；
3. 基于規(guī)則的語言：檢查一定的使能條件，滿足時執(zhí)行動作
也稱邏輯程序設(shè)計語言，如PROLOG。
4. 面向?qū)ο笳Z言：提供抽象數(shù)據(jù)類型，支持封裝性、繼承性和多態(tài)性。
如C++和Java等。
(1) 符號和符號串
1、 字母表：元素的有窮非空集合。
2、 符號串：由字母表中的符號組成的任何有窮序列。
3、 符號串的頭尾，固有頭和固有尾：如果z=xy是一符號串，那么x是z的頭，y是z
的尾，如果x是非空的，那么y是固有尾；同樣如果y非空，那么x是固有頭。 如:設(shè)z=abc，那么z的頭是，a, ab, abc, 除abc外，其它都是固有頭；z的尾是, c, bc, abc, z的固有尾是, c, bc。
4、 符號串的運算
�。�1）符號串的連接：設(shè)x和y是符號串，x和y的連接xy是把y的符號寫在x的符號后得的符號串。
如：x=ST, y=abu, 則xy=STabu顯然有x=x=x。
�。�2）符號串的方冪：設(shè)x是符號串，把x自身連接n次得x的幾次方冪xn。
如：設(shè)x=ab則x0=x1=abx2=ababx3=ababab
（3）符號串集合的乘積：設(shè)A和B為符號串集合，則A和B的乘積定義為AB={xy|xA且yB}
如：a={a, b}, B={00, 11} 則AB={a00, a11, b00, b11} 顯然：{}A=A{}=A
�。�4）符號串集合的方冪：設(shè)A為符號串集，則A的n次方冪An定義為:An=AA……A=AAn-1=An-1A
�。�5）符號串集合的正閉包A+：A+=A1 U A2 U … U An U …
�。�6）符號串集合的閉包A*：A*=A0 U A+ = {} U A+
如：設(shè)有正字母表={0，1} 則*=0 U 1 U 2 U … U n U …={, 0, 1, 00,01, 10, 11, 000, 001,……}
(2) 文法
文法G定義為四元組（VN ，VT，P，S）其中:
（1）VN 為非終結(jié)符號集
非終結(jié)符號表示一個語言短語（或語法成分、語法單位）。 如 程序、語句、表達式等。一般用大寫字母或用〈 〉括起表示非終結(jié)符號。
�。�2）VT 為終結(jié)符號集
終結(jié)符號：組成語言的基本符號。是文法中不屬于非終結(jié)符號集合的符號。一般用小寫字母或不帶〈 〉的符號表示。如程序設(shè)計語言的單詞符號。
設(shè)V=VN U VT，稱V為文法G的字母表。
�。�3）P 為產(chǎn)生式（也稱規(guī)則）的集合。
產(chǎn)生式的形式：→或∷=，其中∈V+，∈V*
（4）S 稱作識別符號或開始符號，是一個非終結(jié)符號。
一般表示此文法定義的最大語法短語，至少要在一條產(chǎn)生式 中作為左部出現(xiàn)。 句型、句子的定義
設(shè)G[S]是一文法，如果符號串x是從識別符號推導(dǎo)出來的，即有S*x， 則稱x是文法G[S]的句型。
若x僅由終結(jié)符號組成，即S*x, xV T ，則稱x為G[S]的句子。
句型：在一棵樹生長過程的任何時刻，所有那些端末結(jié)點自左至右的排列，就是一個句型。
語言的定義：文法G產(chǎn)生的語言記為L（G），它是文法G產(chǎn)生的全部句子的集合。 文法等價定義：若L（G1）=L（G2）則稱文法G1和G2是等價的。
(3) 文法的類型 N.Chomsky
0型文法：定義0型語言，對應(yīng)Turing機；
1型文法：定義1型語言，對應(yīng)線性限界自動機；箭頭后面的要比前面的長或相等 2型文法：定義2型語言，對應(yīng)非確定下推自動機；箭頭前面的是非終結(jié)符，后面是串 3型文法：定義3型語言，對應(yīng)有限自動機。非終結(jié)符可以推出一個終結(jié)符或一個終結(jié)符和一個非終結(jié)符
最右推導(dǎo)也稱為規(guī)范推導(dǎo)，所得句型稱為規(guī)范句型。
如果一個文法存在某個句型對應(yīng)兩棵不同的語法樹，則說這個文法是二義的�；蛘哒f，若一個文法中存在某個句型，它有兩個不同的最左（最右）推導(dǎo)，則這個文法是二義的。
上下文無關(guān)文法是否具有二義性是不可判定的。
但有些特殊的2型文法[例如LL（1）、LR（0）、LR（1）等文法]是無二義性的。 一個文法兼有左遞歸和右遞歸是導(dǎo)致二義性的常見原因。
排除文法二義性通常有兩種方法:
�。�1）在語義上加些限制
（2）重新構(gòu)造一個無二義性的文法
(4) 句型的分析
句型的分析：就是識別一個符號串是否為某文法的句型。是某個推導(dǎo)的構(gòu)造過程。 分析方法分兩大類：自上而下分析法和自下而上分析法推導(dǎo)與歸約，最右推導(dǎo)是規(guī)范推導(dǎo)，逆過程為規(guī)范規(guī)約
若S*A+（由A+得）則稱是句型相對于非終結(jié)符A的短語。
若S*A(由A→得)則稱是句型相對于A→的直接短語（也稱簡單短語）。 一個句型的最左直接短語稱為該句型的句柄。
一棵子樹（至少要有父子兩代）的所有端末結(jié)點自左至右排列起來形成相對于子樹根的短語。若子樹只有父子兩代，則得到直接短語。
(5) 有關(guān)文法
�。�1）有害規(guī)則 文法中含形如U→U的產(chǎn)生式。
它對描述語言沒有必要，且會引起文法的二義性。
�。�2）多余規(guī)則 文法中任何一個句子的推導(dǎo)都用不到的規(guī)則。
�。�3）無用規(guī)則 文法中含形如U→V的產(chǎn)生式，即單產(chǎn)生式。
為保證文法G的任一非終結(jié)符A在句子推導(dǎo)中出現(xiàn)，必須滿足如下兩個條件：
�。�1）A必須在某句型中出現(xiàn)，A。
（2） 必須能夠從A推導(dǎo)出終結(jié)符號串t。
有關(guān)文法的化簡和改造，包括以下幾項工作：
�。ǎ保o用符號和無用產(chǎn)生式的刪除。
�。ǎ玻� －產(chǎn)生式的消除。
�。ǎ常﹩萎a(chǎn)生式的消除。
�。ǎ矗┳筮f歸的消除。
(1) 詞法分析輸出
單詞符號（TOKEN) 是一個程序設(shè)計語言的基本語法符號。程序設(shè)計語言的單詞符號一般可分成下列5種：
1．基本字，也稱關(guān)鍵字，如PASCAL語言中的begin，end，if，while和var等。
2．標識符，用來表示各種名字，如常量名、變量名和過程名等。
3．常數(shù)，各種類型的常數(shù)，如25，3.1415，TRUE和"ABC"等。
4．運算符，如+，*，<= 等。
5．界符，如逗點，分號，括號等。
詞法分析程序所輸出的單詞符號常常采用下二元式表示：（單詞種別，單詞自身的值） 可用整數(shù)碼或助記符等表示。
(2) 單詞的描述工具
程序設(shè)計語言中的單詞(TOKEN)是基本語法符號。單詞符號的語法可以用有效的工具加以描述。
正規(guī)式和它所表示的正規(guī)集的遞歸定義如下。設(shè)字母表為∑，輔助字母表∑ ={ |, ·, *, (, ) }
定義（正規(guī)式和它所表示的正規(guī)集）：
設(shè)字母表為Σ，輔助字母表Σ`={Φ，ε，|，·，*，(， }。
② ε和Φ都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為{ε}和{ }；
② 任何a∈Σ，a是Σ上的一個正規(guī)式，它所表示的正規(guī)集為{a}；
�、� 假定e1和e2都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2)，那么，(e1), e1|e2, e1·e2, e1*也都是正規(guī)式,它們所表示的正規(guī)集分別為L(e1), L(e1)∪L(e2), L(e1)L(e2)和(L(e1))*。
�、� 僅由有限次使用上述三步驟而定義的表達式才是Σ上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是Σ上的正規(guī)集。
(3) 有窮自動機
有窮自動機（也稱有限自動機）作為一種識別裝置，它能準確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程
【編譯原理期末總結(jié)復(fù)習】相關(guān)文章：
編譯原理小論文03-30
編譯原理知識點總結(jié)03-30
編譯原理的學(xué)習心得體會03-19
編譯原理實驗課程教學(xué)設(shè)計的改進論文06-12
編譯原理課程設(shè)計心得體會01-12
會計學(xué)原理復(fù)習總結(jié)范文04-29
物理期末復(fù)習總結(jié)03-05