编译原理课件

第一章引論§1.1什麼是編譯程序一、程式語言的分類1、程式語言分為兩類：高級語言低級語言2、低級語言可分為兩類：機器語言組合語言二、基本概念 把用組合語言或高級語言寫成的程式轉換成機器語言的程式，被稱為翻譯程式。 組合語言的翻譯程式稱為組合語言程式 把高級語言的翻譯程式稱為編譯程序。

編譯程序的輸入對象稱為根源程式，輸出對象稱為目標程式。三、編譯過程1、執行一個高級程式一般分為兩步：

①

通過編譯程序把根源程式翻譯成機器語言程式。

②

執行目標程式編譯過程：編譯方式：編譯程序計算結果源程序目標程式初始數據運行系統副程式2、也可以採用邊翻譯邊執行的解釋執行方式，這種處理程式稱為解釋程式。解釋程式的結果是根源程式的執行結果。解釋方式：解釋程式計算結果根源程式初始數據

採用這種方法的優勢：可移植性。發佈的程式理論上可以在任何硬體平臺上運行。即C#通過安裝在機子上的CLR(CommonLanguageRuntime-公共語言運行時），Java通過安裝在機子上的JVM(JavaVirtualMachine-Java虛擬機)來執行中間代碼和位元組碼。

傳統的語言（例如C、C++

），源代碼在經過編譯連接後直接生成了二進位代碼。而C#、java這些語言把源代碼編譯為了中間語言，C#把源代碼編譯為微軟中間語言MSIL，Java把源代碼編譯為位元組碼。

簡單的理解是，為了實現這種移植性，在機子上又加了一層平臺（CLR、JVM),讓中間代碼在這個平臺上進行運行，而JVM、CLR在不同的操作系統上以不同的方式實現。

C是直接編譯成機器碼，java是編譯程序將java根源程式編譯成JVM可執行代碼--java位元組碼，再由虛擬機解釋執行。§1.2編譯程序的組成一、編譯程序要完成的工作：詞法分析語法分析中間代碼生成中間代碼優化目標代碼生成及和硬體有關的工作

表格管理

錯誤處理

詞法分析中間代碼生成

語法分析中間代碼優化目標代碼生成

根源程式

目標程式例子：用Pascal將英語句子譯成數字，用1～26替A～Z，空格用#，句號不變。例如：thisisanexampleProgramencode(input，output)Constblank=‘’,termin=‘.’,well=‘#’;Varletter:char;code:integer;BeginRead(letter);Whileletter<>TermindoBeginIfletter=blankThenWrite(well:2)ElseBegincode:=Ord(letter)-Ord('A')+1;Write(code:3)EndRead(letter)EndWrite(termin)End運行結果：208919#919#114#5241131612.二、編譯的步驟

1、分析單詞：保留字、識別字、常數、運算符、分界符

2、語法分析：分析語法結構和程式層次程式開始部分說明部分執行語句(input,output)開始部分程式開始程式名參數ProgramEncode說明部分常量變數Well=‘#‘常量定義語句1語句2語句3Blank=‘‘Termin=‘.‘，，語句部分Begin語句組End語句1；語句2；……Read參數(Letter)其他情況類似！3、語義處理和產生目標程式

①

程式處理

②

說明語句處理

③

可執行語句處理詞法分析語法分析中間代碼生成前端中間代碼優化目標代碼生成及和硬體有關的工作後端三、編譯階段的組合1、前後端結合某編譯程序前端A機型後端B機型後端＋不同機型上的編譯程序A編譯程序前端B編譯程序前端生成同一中間語言共同的後端＋＋幾種編譯程序2、結論：

①

分前後端可提高效率，減少重複勞動

②

利於優化，便於組合1、編譯程序按其掃描遍數分為： 一遍掃描 多遍掃描2、若通過對根源程式的掃描直接生成目標代碼，則稱編譯程序是單遍的。3、多遍掃描的好處是：便於分工、便於優化，但前後掃描之間難免有些重複性工作。§1.3編譯程序的分遍根源程式→詞法分析程式→中間檔1→語法分析程式→中間檔2→語義分析→中間檔3→優化→中間檔4→目標程式多遍掃描的步驟：

目前大部分編譯程序都是多遍掃描的。一遍掃描:以語法分析為主。參考文獻： 呂映芝.編譯原理.清華大學出版社,北京:1998.§1.4編譯程序的開發

1、開發編譯程序的步驟：

①

對語言的語法與語義有準確無誤的理解。

②

確定編譯程序的要求。

③

根據編譯程序的規模確定編譯程序的具體分遍及每遍的具體任務。

④分別調試各次的掃描程式，連調2、編譯程序的自動化 利用自展技術完成。 首先利用組合語言的編寫最簡單的編譯程序，例如加法的編譯程序。 將乘法轉換為加法，利用得到的加法編譯程序得到乘法的編譯程序，以此類推。

PL0……PLn均是PASCAL的子集。第2章PL/0編譯程序的實現2.1PL/0語言描述2.2PL/0編譯程序的結構2.3PL/0編譯程序的語法語義分析2.4PL/0編譯程序的錯誤處理2.5類pcode代碼解釋器本章目的：以PL/0為實例,學習編譯程序實現的基本步驟和相關技術

PL/0編譯程序

PL/0編譯程式

PL/0語言程式

類pcode代嗎源語言(PL/0)目標語言(類pcode)實現語言（pascal)PL/0

類pcodepascal

2.1PL/0語言描述PL/0編譯程序類pcode解釋程式類pcode代碼PL/0根源程式輸入輸出PL/0編譯系統的結構框架PL/0語言PL/0程式示例PL/0的語法描述圖PL/0語言文法的EBNF表示PL/0語言：PASCAL語言的子集PL/0程式示例CONSTA=10;（*常量說明部分*）

VARB,C;（*變數說明部分*）

PROCEDUREP;（*過程說明部分*）

VARD;

PROCEDUREQ;

VARX;

BEGIN

READ(X);D:=X;WHILEX#0DOCALLP;

END;

BEGIN

WRITE(D);

CALLQ;

END;

BEGIN

CALLP;

END.Q的過程體p的過程體主程式體程式分程式.內的文字表示非終結符或內的文字或符號表示終結符2.1.1PL/0語言的語法描述圖語法描述圖下頁分程式Constidentnumber=,;Varidentprocedureident分程式;語句,;;語句ident:=callident;運算式.begin語句語句end條件語句ifthen條件語句Whiledo()readident()write,,運算式條件運算式運算式運算式odd.=#<<=>=>+-運算式項項.+-identnumber運算式因數.()*因數項因數/.1、EBNF表示的符號說明

<>：是非終結符→：左部由右部定義

|：表示‘或’

{}：表示為可以重複部分

[]：表示為任選項

()：表示成分優先2.1.2PL/0語言文法的EBNF表示2、PL/0語言文法的EBNF表示為：

<程式>→<分程式>●<分程式>→[<常量說明部分>][<變數說明部分>][<過程說明部分>]<語句><常量說明部分>→CONST<常量定義>{,<常量定義>}<常量定義>→<識別字>=<無符號整數><無符號整數>→<數字>{<數字>}<變數說明部分>→VAR<識別字>{,<識別字>}<識別字>→<字母>{<字母>|<數字>}<過程說明部分>→<過程首部><分程式>{;<過程說明部分>}<過程首部>→procedure<識別字><語句>→<賦值語句>|<條件語句>|<當型迴圈語句>|<過程調用語句>|<讀語句>|<寫語句>|<複合語句>|<空><賦值語句>→<識別字>：=<運算式><複合語句>→begin<語句>{；<語句>}end<條件>→<運算式><關係運算符><運算式>|odd<運算式>

<運算式>→[+|—]<項>{<加法運算符><項>}<項>→<因數>{<乘法運算符><因數>}<因數>→<識別字>|<無符號整數>|‘(’<運算式>‘)’

<加法運算符>→+|-

<乘法運算符>→*|/

<關係運算符>→!=|<|≤|≥|>|=

<條件語句>→If<條件>then<語句><過程調用語句>→Call<識別字><當型迴圈語句>→While<條件>DO<語句><讀語句>→Read’(’<識別字>{，<識別字>}’)’<寫語句>→Write’(’<運算式>{，<運算式>}’)’<字母>→a|b|…|X|Y|Z<數字>→0|1|2|…|8|93、PL/0編譯程序是用PASCAL語言編寫，可在任何配有PASCAL編譯系統的電腦上運行。如下圖：PL/0Compiler源文本PASCALCompilerPL/0Compiler目標文本PL/0根源程式PL/0Compiler目標文本PL/0目標程式詞法分析程式語法語義分析程式代碼生成程式表格管理程式出錯處理程式PL/0根源程式目標程式2.2PL/0編譯程序的結構PL/0編譯程序的總體設計其編譯過程採用一趟掃描方式以語法、語義分析程式為核心

詞法分析程式和代碼生成程式都作為一個過程，當語法分析需要讀單詞時就調用詞法分析程式，而當語法、語義分析正確，需要生成相應的目標代碼時，則調用代碼生成程式。表格管理程式實現變數，常量和過程識別字的資訊的登錄與查找。出錯處理程式，對詞法和語法、語義分析遇到的錯誤給出在根源程式中出錯的位置和與錯誤性質有關的編號，並進行錯誤恢復。2.3PL/0編譯程序的詞法分析識別的單詞：保留字或關鍵字：如：BEGIN、END、IF、THEN等運算符：如：+、-、*、/、：=、#、>=、<=等識別字：用戶定義的變數名、常數名、過程名常數：如：10、25、100等整數界符：如：‘,’、‘.’

、‘;’

、‘(’

、‘)’等詞法分析過程GETSYM所要完成的任務：讀根源程式（getch)濾空格識別保留字識別識別字拼數識別單字符單詞拼雙字元單詞詞法分析過程:GETSYM框圖（見教材圖2.5）程式（

proceduregetsym）當識別到識別字時先查保留字表

使用狀態轉換圖實現詞法分析程式的設計方法詞法分析程式的設計---使用狀態轉換圖實現表示狀態，對應每個狀態編一段程式，每個狀態調用取字元程式，根據當前字元轉到不同的狀態，並做相應操作。表示終態，已識別出一個單詞。2.4PL/0編譯程序語法語義分析自頂向下的語法分析遞歸子程序法

程式分程式.constidentnumber=,;varident,;;procedureident;分程式語句分程式identreadend;語句運算式：=begin語句語句)(ident,

自頂向下的語法分析

VARA;BEGINREAD(A)END.

<程式><分程式>.<變數說明部分><語句>VAR<識別字>；

<複合語句>

A

BEGIN<語句>END<讀語句>

READ

（

<識別字>）

A<程式>為文法的開始符號，以開始符號作為根結點構造一棵倒掛著的語法樹。遞歸副程式法遞歸副程式法：對應每個非終結符語法單元，編一個獨立的處理過程（或副程式）。語法分析從讀入第一個單詞開始，由非終結符<程式>（即開始符）出發，沿語法描述圖箭頭所指出的方向進行分析。當遇到非終結符時，則調用相應的處理過程，從語法描述圖看，也就進入了一個語法單元，再沿當前所進入的語法單元所指箭頭方向繼續進行分析。當遇到描述圖中是終結符時，則判斷當前讀入的單詞是否與圖中的終結符相匹配，若匹配，再讀取下一個單詞繼續分析。遇到分支點時，將當前的單詞與分支點上多個終結符逐個相比較，若都不匹配時可能是進入下一個非終結符語法單位或是出錯。

例：如何用遞歸副程式法實現運算式的語法分析項運算式+-項+-項

因數

因數

*/語法圖因數的語法圖因數identnumber(運算式)運算式的EBNF

〈運算式〉∷=[+|-]〈項〉{（+|-）〈項〉}

〈项〉∷=〈因數〉{（*|/）〈因數〉}

〈因子〉∷=〈識別字〉|〈無符號整數〉|‘（’〈運算式〉‘）’〈運算式〉的遞歸副程式實現

procedureexpr;

begin

ifsymin[plus,minus]then

begin

getsym;term;

end

elseterm;

whilesymin[plus,

minus]do

begin

getsym;term;

end

end;

〈項〉的遞歸副程式實現

procedureterm;

begin

factor;

whilesymin[times,

slash]do

begin

getsym;factor;

end

end;〈因數〉的遞歸副程式實現

procedurefactor;

begin

ifsym<>identthen

begin

ifsym<>numberthen

beginifsym=‘(‘then

begin

getsym;

expr;

ifsym=‘)’thengetsym

elseerror

end

elseerrorendendend;

程式

pl0分程式

block語句

statement條件

condition運算式expression項

term因數

factor語法調用關系圖編譯程序總體流程圖

目標代碼類pcode目標代碼類pcode是一種假想棧式電腦的組合語言。指令格式：flaf 功能碼l 層次差（識別字引用層減去定義層）a 根據不同的指令有所區別2.5PL/0編譯程序的目標代碼結構和目標代碼生成指令功能表

consta=10;

varb,c;

procedurep;

begin

c:=b+a;

end;

begin

read(b);

whileb#0do

begin

callp;

write(2*c);

read(b);

end

end.

(0)jmp08轉向主程序入口(1)jmp02轉向過程p入口(2)

int03

過程p入口,為過程p開闢空間(3)lod13取變數b的值到棧頂(4)lit010取常數10到棧頂(5)opr02次棧頂與棧頂相加(6)sto14棧頂值送變數c中(7)opr00

退棧並返回調用點(16)(8)

int05主程序入口開闢5個棧空間(9)opr016從命令行讀入值置於棧頂(10)sto03將棧頂值存入變數b中(11)lod03將變數b的值取至棧頂(12)lit00將常數值0進棧(13)opr09次棧頂與棧頂是否不等(14)jpc024

等時轉(24)（條件不滿足轉）(15)cal02

調用過程p(16)lit02常數值2進棧(17)lod04將變數c的值取至棧頂(18)opr04次棧頂與棧頂相乘(2*c)(19)opr014棧頂值輸出至螢幕(20)opr015換行(21)opr016從命令行讀取值到棧頂(22)sto03棧頂值送變數b中(23)jmp011無條件轉到迴圈入口(11)(24)opr00結束退棧第3章文法和語言

當我們表述一種語言時，無非是說明這種語言的句子，如果語言只含有有窮多個句子，則只需列出句子的有窮集就行了，但對於含有無窮句子的語言來講，存在著如何給出它的有窮表示的問題。以自然語言為例，人們無法列出全部句子，但是人們可以給出一些規則，用這些規則來說明(或者定義)句子的組成結構，比如漢語句子可以是由主語後隨謂語而成，構成謂語的是動詞和直接賓語，我們採用EBNF來表示這種句子的構成規則：

3.1文法的直觀概念

BNF範式和語法圖1、巴科斯範式:EBNF <句子>→<主語><謂語> <主語>→<代詞>|<名詞> <代詞>→你|我|他

<名詞>→王明|大學生|工人

<謂語>→<動詞><賓語> <動詞>→是|學習

<賓語>→<代詞>|<名詞>帶<>的叫非終止符,不帶<>的叫終止符。<邏輯值>→True|False例子：

<句子>

<主語><謂語>

<代詞><謂語>

我<謂語>

我<動詞><直接賓語>

我是<直接賓語>

我是<名詞>

我是大學生

“我是大學生”的構成符合上述規則，而“我大學生是”不符合上述規則，我們說它不是句子。這些規則成為我們判別句子結構合法與否的依據，換句話說，這些規則看成是一種元語言，用它描述漢語。這裏僅僅涉及漢語句子的結構描述。其中一種描述元語言稱為文法。語言概述語言是由句子組成的集合，是由一組符號所構成的集合。漢語--所有符合漢語語法的句子的全體英語--所有符合英語語法的句子的全體程式設計語言--所有該語言的程式的全體每個句子構成的規律研究語言每個句子的含義每個句子和使用者的關係研究程式設計語言每個程式構成的規律每個程式的含義每個程式和使用者的關係語言研究的三個方面語法Syntax

語義Semantics

語用Pragmatics語法--表示構成語言句子的各個記號之間的組合規律語義--表示各個記號的特定含義。（各個記號和記號所表示的對象之間的關係）語用--表示在各個記號所出現的行為中，它們的來源、使用和影響。

每種語言具有兩個可識別的特性，即語言的形式和該形式相關聯的意義。語言的實例若在語法上是正確的，其相關聯的意義可以從兩個觀點來看，其一是該句子的創立者所想要表示的意義，另一是接收者所檢驗到的意義。這兩個意義並非總是一樣的，前者稱為語言的語義，後者是其語用意義。幽默、雙關語和謎語就是利用這兩方面意義間的差異。

如果不考慮語義和語用，即只從語法這一側面來看語言，這種意義下的語言稱作形式語言。形式語言抽象地定義為一個數學系統。“形式”是指這樣的事實：語言的所有規則只以什麽符號串能出現的方式來陳述。形式語言理論是對符號串集合的表示法、結構及其特性的研究。是程式設計語言語法分析研究的基礎。例子:整數(1)單個數字是整數

(2)整數再接上數字仍是整數用BNF範式表示:

<1><整數>→<數字><數字>→0|1|2|…|9<2><整數>→<整數><數字><整數>→<數字>|<整數><數字>所以合起來有：

<整數>→<數字>|<整數><數字><數字>→0|1|2|…|9

識別字:以字母開頭以後由字母和數字組成的符號串。例子：<識別字>的巴科斯範式

<識別字>→<字母><識別字>→<識別字><字母><識別字>→<識別字><數字><字母>→a|b|…|z

<數字>→0|1|…|9例子：判定字串a4y是<識別字>

<識別字>

<識別字><字母>

<識別字>y

<識別字><數字>y

<識別字>4y

<字母>4y

a4y2、語法圖作用：直觀、形象的描述語法規則。例子：識別字的語法圖表示識別字字母字母數字例子：無符號數的語法圖表示

2.45E+12無符號數無符號整數數字E無符號整數3.2符號和符號串1、字母表:它是非空有窮集。例如：∑={a,b,c}或∑={1,2,3}2、符號：字母表中的元素稱為符號。3、符號串：符號的有窮序列，符號串也稱為字。用ε來表示空符號串。例如：a,ab,abc,dsfsd4、長度：符號串的長度是指該串所包含的符號個數。用|x|表示符號串x的長度。例如：|a|=1，|abn|=35、連結：設x和y為符號串，則稱xy為他們的連結。

例如：x=aa,y=bb,則xy=aabb6、空集：不含任何元素的集合,記為

。7、乘積：設A和B是符號串集，則用AB表示A和B的乘積。A={a,b},B={c,d},則AB={ac,ad,bc,bd}8、方冪：設A為符號串集，則定義

A0={ε}A1=AAn=An-1A

例如：A={a,b}則有：

A0={ε}A1={a,b}A2={aa,ab,ba,bb}9、正閉包：設A為符號串集，則用A+表示A的正閉包，其具體定義如下：

A+=A1∪A2∪A3∪

…

例如：A={a},A+={a,aa,aaa,……}10、星閉包：設A為一集合，則定義A的星閉包為A*

，其具體定義如下A*=A0∪A+

例如：A={a},A*={ε,a,aa,aaa,……}

一、引言

例子：

y:=a+b*x

語法：賦值語句由變數加“:=”加運算式構成。語義：右邊運算式求值與左變數結合賦值。用途：運算式的值的保存和計算。3.3文法與語言的形式定義

形式化方法：用一整套帶有嚴格規定的符號體系來描述問題的理論和方法。

表示文法需要一種工具，其中最常用的工具是所謂的巴克斯範式(BNF)。例子:

A={an|n≥1}A={a2n|n≥1}其BNF表示有：其BNF表示有：

(1)

A→a|aA(1)

A→aa|aaA

(2)

A→a|Aa(2)

A→aa|Aaa例子：

A={abna|n≥1}其BNF表示有多種如下：

(1)

A→aBaB→b|Bb(2)

A→aBaB→b|bB(3)

A→aBB→ba|bB如何來描述一種語言？如果語言是有窮的（只含有有窮多個句子），可以將句子逐一列出來表示如果語言是無窮的，找出語言的有窮表示。語言的有窮表示有兩個途經：生成方式（文法）：語言中的每個句子可以用嚴格定義的規則來構造。識別方式（自動機）：用一個過程，當輸入的一任意串屬於語言時，該過程經有限次計算後就會停止並回答“是”，若不屬於，要麽能停止並回答“不是”，（要麽永遠繼續下去。）

文法即是生成方式描述語言的：語言中的每個句子可以用嚴格定義的規則來構造.下麵給出文法的定義.進而在文法的定義的基礎上,給出推導的概念,句型、句子和語言的定義.定義文法G定義為四元組(VN，VT，P，S)其中VN為非終結符號(或語法實體，或變數)集；VT為終結符號集；P為產生式(也稱規則)的集合；VN，VT和P是非空有窮集。

S稱作識別符號或開始符號，它是一個非終結符，至少要在一條產生式中作為左部出現。

VN和VT不含公共的元素，即VN∩

VT=φ

用V表示VN∪

VT

，稱為文法G的字母表或字彙表規則，也稱重寫規則、產生式或生成式，是形如α→β或α∷=β的(α，β)有序對，其中α是字母表V的正閉包V+中的一個符號，β是V*中的一個符號。α稱為規則的左部，β稱作規則的右部。文法的定義例文法G=（VN，VT，P，S）

VN={S},VT={0,1} P={S→0S1,S→01} S為開始符號例文法G=（VN，VT，P，S）

VN={識別字，字母，數字} VT={a,b,c,…x,y,z,0,1,…,9} P={<識別字>→<字母> <識別字>→<識別字><字母> <識別字>→<識別字><數字><字母>→a,…,<字母>→z<數字>→0,…,<數字>→9} S=<識別字>文法的寫法

1G：S→aAb

A→abA→aAb

A→ε2G[S]：A→abA→aAbA→εS→aSb3G[S]：A→ab|aAb|εS→aSb二、文法和語言形式定義1、規則式，產生式

例子：

B→b|Bb

A→a|A2、文法G[Z]：規則的非空有窮集合。Z：識別符號，開始符號。V：字母表，符號集合。 例子：G[S]={S→0，S，1} V＝{S，0，1}定義3.1

文法是一個四元組G(VN，VT，P，Z)。非終極符集記為VN(大寫字母)

終極符集記為VT(小寫字母)

產生式集記為P

初始符記為Z例子：自然數G1(VN,VT,P,Z)和識別字G2(VN,VT,P,I) VN={N,D} VT={0,1,2

,9} P={N→D|ND,D→0|1|2|

|9}

G1：N→D|NDD→0|1|2||9識別字G2(VN,VT,P,I) VN={I,D,L} VT={0,1,2

,9,a,b…z} P={I→L|IL|ID, L→a|b|…|zD→0|1|2|

|9}

G2：I→L|IL|IDL→a|b|c||zD→0|1|2||9定義3.21、直接推導：設x和y是符號串，若用一次產生式可從x導出y，則稱y為x的直接推導，並記為x

y。

例子：x=Ab,y=ab,A→a,Abab2、推導：若用若干次產生式可從x串導出y串，則稱y為x的推導，並記為xy。

+

例子：X=AB,A→a,B→bABaBab

即：ABab

+

*3、星推導:xy(當且僅當x=y或x y)。

例子：AB

AB0步

ABaB1步

ABab2步即：ABab

+

*

+4、句型：稱x為句型，若有Zx，其中Z是文法的開始符。凡是由初始符推出的任意符號集合叫句型。例子：Z→AB,A→a,ZaB5、句子:稱x為句子，若有Zx，且x中不包含非終極符的句型。不包含非終極符的句型叫句子。

*

*

*

例子：G[S]:S→0S1S→01

解: S0S100S11000111

所以有: S={01,0011,000111…}L(G)={0n1n|n≥1}6、語言:所有句子的集合稱為語言。設是G給定文法，Z是開始符，則語言L(G)可描述如下：定義3.3

設G1,G2為給定文法，如果L(G1)=L(G2),則稱G1和G2等價。L(G)=｛x|Zx,x∈VT*｝

*例1

已知文法求語言並判斷是否等價

G1=(VN,VT,P,A)G2=(VN,VT,P,Z)VN={A}VN={A,B}VT={a,b}VT={a,b}P={A→ab}P={A→Bb,B→a}A1

ab L(G1)={ab}A2

Bb

ab

L(G2)={ab}G1與G2是等價的。例2:G3[S]:S→A|S-AA→a|b|cG4[S]:S→A|A-SA→a|b|c推導過程如下：S

S-ASS-AAabcS-A

S-A-A

A-A-A

a-b-cG3與G4等價，但G3與G4的語義不同。推導過程如下：S

A-SSA-SAA-S

A-A-S

A-A-A

a-b-cabca-b-c和a-b-c文法的等價若L（G1）=L（G2），則稱文法G1和G2是等價的。

如文法G1[A]：A→0R與G2[S]：S→0S1等價

A→01S→01R→A1定義3.4

0型文法(短語結構文法):產生式為：α→β，其中α和β是符號串。

1型文法(上下文有關文法)：產生式為：αAβ→αuβ，其中A∈VN，u為非空串。

2型文法(上下文無關文法):A→β，其中A∈VN，β為非空串。3.4文法的類型

3型文法(正則文法):產生式為：A→a,A→bB,其中A,B∈VN,#a,b∈VT是符號串。例子:G[Z]:Z→aZ→aAA→b|bBB→b

所以:G[Z]是3型文法文法的類型例：1型（上下文有關）文法文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD文法的類型例：2型（上下文無關）文法

文法G[S]： S→AB A→BS|0 B→SA|1

3型文法G[S]：

S→0A|1B|0 A→0A|1B|0S B→1B|1|0G[I]： I→lT I→l T→lT

T→dT

T→l

T→d

文法的類型2型文法1型文法0型文法四種文法之間的逐級“包含”關係3型文法文法和語言0型文法產生的語言稱為0型語言1型文法或上下文有關文法（CSG

）產生的語言稱為1型語言或上下文有關語言（CSL）2型文法或上下文無關文法（CFG

）產生的語言稱為2型語言或上下文無關語言（CFL）

3型文法或正則（正規）文法（RG）產生的語言稱為3型語言正則（正規）語言（RL）

文法和語言

四種文法之間的關係是將產生式做進一步限制而定義的。語言之間的關係依次：有不是上下文有關語言的0型語言，有不是上下文無關語言的1型語言，有不是正則語言的上下文無關語言。 根據形式語言理論,文法和識別系統間有這樣的關係0型文法（短語結構文法）的能力相當於圖靈機，可以表徵任何遞歸可枚舉集，而且任何0型語言都是遞歸可枚舉的

1型文法（上下文有關文法）：產生式的形式為α1Aα2→α1βα2，即只有A出現在α1和α2的上下文中時，才允許β取代A。其識別系統是線性界限自動機。

2型文法（上下文無關文法CFG）：產生式的形式為A→β，β取代A時與A的上下文無關。其識別系統是不確定的下推自動機。

3型文法（正規文法RG）：產生的語言是有窮自動機（FA）所接受的集合

3型文法产生的语言是有穷自动机（FA）所接受的集合.定理

設G=（VN，VT，P，S）是3型文法，則存在一個有窮自動機M=(K,∑,f,A,Z)，使得L(M)=L(G)有窮自動機NFAM這樣構造：·∑=VT·K=VN∪{N},N為一個新狀態,它不在VN中·A=S·Z={N}·

對G中的形如D→tB的產生式,t為終結符或ε,有f(D,t)=B；對G中形如D→t的產生式，t為終結符或ε,有f(D,t)=N;

對VT中的每一個a,有f(N,a)=φG［Ｓ］：

S→aA|bB

A→bB|aD|aB→aA|bD|bD→aD|bD|a|bBASaaabbba,bDZabab

使其右部為空字元串的產生式，稱為空產生式。產生式記為A→

或A→例子:G[S]:S→AaBA→AB|

B→bB|

所以:G[S]含有空產生式定義3.5

直接左遞歸：若有產生式A→A…

直接右遞歸：若有產生式A→…A

左遞歸：若有推導式AA…

右遞歸：若有推導式A…A

遞歸：若有產推導A…A…

+

+

+例子： 直接遞歸：A→AaB→aBB

左遞歸：S→Qc|cQ→Rb|bR→Sa|a Q

Rb

Sab

Qcab

Q

Qcab規範推導和句柄定義3.6

設xUy

xuy是一直接推導。如果U是句型xUy中的最右非終極字元，則稱該推導為規範直接推導並記為xUyxuy。如果xy中的每步都是規範直接推導，則稱該推導為規範推導並記為xy。

r

+

r+3.5上下無關文法及其語法樹

如果每步都是最右非終極字元，則也稱該規範推導為最右推導。例子：G[S]：S→ABA→Aa|bBB→a|Sb S

AB

bBB

baB(最左推導) S

AB

ASb

AABb

AAab

AbBab(最右推導)

S

AB

ASb

bBSb

baSb(非左非右)語法樹與二義性定義3.8設G=(VN,VT,P,S)是給定文法,則稱滿足下麵條件的樹為G的一棵語法樹。每個結點都標有G的一個文法符號,且根結點標有初始符S,非葉結點標有非終極符。如果一個非葉結點A有n個兒子結點(從左到右)B1,B2,…,Bn,則A→B1B2…,Bn一定是G的一個產生式。定義3.9

由某一結點及其所屬分枝組成的部分樹稱為原樹的一棵子樹。

只有單層分枝的子樹稱為簡單子樹。例子：Z→ABA→aB→bcSABacb定義3.7

假設ZxUy，Uu，則稱句型xuy中的u為該句型的短語，其中Z為初始符。

假設有ZxUy，U

u，則稱句型xuy中的u為該句型的簡單短語。

最左邊的簡單短語稱為句柄。

*

+

*3.6句型的分析例子：G[S]：S→ABA→AaA→bBB→aB→Sb

解：S

AB

bBB

baB

baSbyB

SbuxUU

Sb是句型baSb的短語，簡單短語SbaB

*

解：S

AB

ASb

bBSb

baSbyB

auxU

a是句型baSb的短語，且是簡單短語。USbBSb

*yuxU

ba是句型baSb的短語，但不是簡單短語。所以：ba,a,Sb是句型baSb的短語

a,Sb是句型baSb的簡單短語

a是句型baSb的句柄。 USASb

*A

ba＋

解：S

AB

ASb

bBSb

baSb定理3.11、每個句型都有一棵語法樹，每個語法樹的葉組成一句型。

2、每棵子樹的葉組成短語，每棵簡單子樹的葉組成簡單短語，最左簡單子樹的葉組成句柄。

3、用語法樹可證明每個句子都有一規範推導。構造語法樹G[E]：E→E+T|T

T→T*F|F

F→(E)|a

EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a

EEE+TE+TTEE+TTFEE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*aEE+TE+T*FE+T*aE+F*aE+a*a

T+a*aF+a*aa+a*aEE+TT+TT+T*FF+T*FF+F*F

a+F*Fa+F*aa+a*a

EE+TTT*FFFaaa看不出句型中的符號被替代的順序上下文無關文法的語法樹的用處用於描述上下文無關文法句型推導的直觀方法

例:G[S]: S→aAS A→SbA A→SS S→a A→baS

aASSbAa

a

b

a句型aabbaa的語法樹（推導樹）葉子結點：樹中沒有子孫的結點。

從左到右讀出推導樹的葉子標記連接成的文法符號串，為G[S]的句型。也把該推導樹稱為該句型的語法樹。上下文無關文法的語法樹推導過程中施用產生式的順序

例:G[S]: S→aAS A→SbA A→SS S→a A→baS

aASSbAa

a

b

aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa一棵語法樹表示了一個句型的種種可能的(但未必是所有的)不同推導過程，包括最左(最右)推導。但是，一個句型是否只對應唯一的一棵語法樹呢?一個句型是否只有唯一的一個最左(最右)推導呢?例：G[E]:

E→i E→E+E E→E*E E→(E)EE+EE*EiiiEE*EiE+Eii句型i*i+i的兩個不同的最左推導：推導1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推導2：EE*Ei*Ei*E+Ei*i+Ei*i+i例子：G[S]：S→ABA→Aa|bBB→a|Sb

字串：bBABb短語：bB,AB,ABb簡單短語：bB,AB句柄：bBSABbBbSBA定義3.10如果一個文法G存在某個句子,使得它有兩棵語法樹,則稱G為二義性文法。 例子：證明G:E→E+E|E*E|(E)|i則G是二義性文法。

因為句子i+i*i具有兩棵語法樹分別如圖所示。EEE+i*EEiiEEE+i*EEii例子：證明G[S]:S→IfBThenSS→IfBThenSElseS是二義性文法。IfB1ThenIfB2ThenS2ElseS3該句子具有二義性(其中S表示語句，Sx無條件語句，Bx表示布爾變數)，分析情況如下：

IfB1ThenIfB2ThenS2ElseS3

例子：Ifx>1thenifx>2theny:=aelsey:=b解釋1:Ifx>1then

ifx>2theny:=aelsey:=b解釋2:Ifx>1then

ifx>2theny:=a

elsey:=bIfB２ThenS２ElseS３SIfB１ThenS１第一種：

IfB1ThenIfB2ThenS2ElseS3第二種：IfB１ThenS１ElseS３SIfB２ThenS２

IfB1ThenIfB2ThenS2ElseS3改寫文法如下：S→M|UM→IfBThenMElseM|S1U→IfBThenS|IfBThenMElseU怎樣排除二義性：語義上限制。改寫文法。M為匹配語句，U為非匹配語句。得到語法樹如下：UIfB１ThenSSIfB２ThenS２ElseMMS33.7有關文法實用中的一些說明

文法中不含有有害規則和多餘規則有害規則：形如U→U的產生式。會引起文法的二義性多餘規則：指文法中任何句子的推導都不會用到的規則文法中不含有不可到達和不可終止的非終結符1）文法中某些非終結符不在任何規則的右部出現，該非終結符稱為不可到達。2）文法中某些非終結符，由它不能推出終結符號串，該非終結符稱為不可終止。1.文法中不含有A→A的規則

例:S→0S1|01無二義性,可以改為:S→0S1|01|S句子0011有二義性。S0S101S0S101SS0S101S

2.文法中不包含多餘規則

①不可到達：所有推導均不會用到此規則

②不可終止：推導不出終結符號串例子:

文法G[S]：

(1)S→Be(5)A→e(2)B→Ce不可終止(6)C→Cf不可終止

(3)B→Af(7)D→f不可達

(4)A→Ae

對文法G=(VN,VT,S,P),為了保證其任一非終結符A在句子推導中出現,必須滿足如下兩個條件：

1.A必須在某句型中出現。即有SαAβ,其中α,β屬(VT∪VN)*。

2.必須能夠從A推出終結符號串t來。即At,其中t∈VT*。 因此檢查文法是否包含多餘規則是很有必要的。

*

+3.9文法的等價轉變換定理3.2

對任一文法G1都可以構造文法G2使得L(G1)=L(G2)，並且G2有這樣的特點，即文法的初始符不出現於產生式的右部。例子：G:E→E+E|E*E|(E)|i可改寫為：G:E’→EE→E+E|E*E|(E)|i

定理3.3

對任一文法G1都可以構造文法G2使得L(G1)=L(G2)，並且G2的每個非終極符出現於某句型中。

定理3.4

對任一文法G1均可構造文法G2使得L(G1)=L(G2)，且在G2中沒有形如A→B的產生式,其中B∈VN。證明：我們稱形如A→B的產生式為特型產生式。G2的構造演算法是：

1、對每個A∈VN，求βA={D|AD,D∈VN} 2、令G1中所有的非特型產生式為G2的產生式。

3、若有D∈βA，且有D→x(非特型)，則令A→x∈G2 4、刪除無用的產生式。

*例子：G[A]:A→B|aB→b求解如下： 保留：A→aB→b

擴充：A→BB→b

A→b G[A]：A→a|bB→b(多餘)

G[A]:A→a|b例子：設有如下文法

G1：A→B|dDB→A|C|bC→B|cD→d|Da

A→BA→BB→A

A→A

A→BB→C

A→C所以

A={A,B,C}則有：

A={A,B,C}B={B,A,C}C={C,A,B}D={}令G1中的非特型產生式為G2的產生式：

G2：A→dDB→bC→cD→d|Da再擴充產生式：

G2：A→b|cB→dD|cC→dD|b所以G2[A]:A→dDB→bC→cD→d|DaA→b|cB→dD|cC→dD|b

其中B和C不出現在任何句型中，因此可以刪去相關的產生式。 得出：G2[A]：A→dD|b|cD→d|Da定理3.5任一文法G1,可構造文法G2,使得L(G2)=L(G1)且G2中沒有ε產生式。證明：G2的構造演算法是：

1、開始令β={A|A→ε∈G1} 2、遞歸擴充β：β=β∪{D|D→x∈G1,x∈β+} 3、從G1刪除所有ε產生式。

4、從G1刪去只能導出空串的非終極符。 5、設β=β∪{A1,A2,…An}，

VN~β={B1,B2,…Bn}若有產生式A→C1C2…Cn，則Ci有三種可能：

Ci∈VT，Ci∈β，Ci∈VN~β。如果Ci∈β，則因為刪去了所有產生式，以此擴充一產生式A→C1C2…Cn。重複這個過程，直至不出現新的產生式為止。例子：設有文法G:A→aBbDD→BBB→ε|b

解：B→εD

BB

ε={B,D}

則有β={B,D}刪去ε產生式得：

A→aBbDD→BBB→b

再擴充下麵產生式：

A→abDA→aBbA→abD→B

定理3.6設有文法G1,則可構造文法G2,使得L(G2)=L(G1),並且G2沒有直接左遞歸的產生式。

A→A|A→A’

A’→A’|例子：A→Aab|cd

A→cdA’A’→abA’|

A

一般而言：

A→A

1|A

2|...|A

n|1|2|…|m則有:A→

1A’|2A’|…|mA’

A’→

1A’|2A’|…|nA’|

例子：考慮下麵文法

E→E+T|TT→T*E|FF→(E)|i用上述方法可以改寫為：

E→TE’E’→+TE’|

T→FT’T’→*ET’|

F→(E)|i第4章詞法分析詞法分析器

詞法分析是任何編譯程序的第一步工作，因此編譯程序都有完成詞法分析的程式部分，稱這種程式為詞法分析器或掃描器。

詞法分析器的共同特點是把每個單詞轉換成其內部形式，稱它為符號或記號(TOKEN)。4.1詞法分析程式的設計

詞法分析器的功能可圖示如下。其charsequence表示字元序列。詞法分析器語法分析器charsequenceTOKEN詞法分析器charsequenceTOKENsequence詞法分析器的設計TOKEN的通常結構是一個二元組:CLASSVALTOKEN:其中CLASS示種類部分，VAL是值部分TOKEN結構的一種方法可如下圖，其中n是從4開始的編碼，且一特殊符一碼。1識別字：2常整數：3實常數：0n特殊符：CLASSVALNAMELCONSL單詞的識別

詞法分析的關鍵之一是如何識別單詞的問題，其中最重要的是識別字的識別問題。4.2單詞的描述工具定義2.1

正則運算式設Σ為給定字母表,RE表示Σ上正則運算式之集,則定義：

1.Λ,ε∈RE2.若a∈Σ,則a∈RE3.若e1,e2∈RE,則(e1|e2)∈RE,(e1

e2)∈RE,(e1)*∈RE例子：

Σ={a,b}

正則式eL(e)b+{b,bb,bbb…}b*{ε,b,bb,bbb…}

例子：(a|b)*{a,aa,ab,aaa…}(a|b)0{ε}(a|b)1{a,b}(a|b)2=(a|b)(a|b){aa,ab,ba,bb}定義2.2

設e∈RE,則定義函數L(e)如下：

L(Λ)=

L(ε)={ε}L(a)={a}L(e*)=L(e)*L(e1|e2)=L(e1)∪L(e2)L(e1

e2)=L(e1)L(e2)定理2.1

設e1,e2∈RE,則有：

1：L(e1|e2)=L(e2|e1)2：L((e1|e2)|e3)=L(e1|(e2|e3))3：L((e1e2)e3)=L(e1(e2e3))4：L(e1(e2|e3))=L(e1e2|e1e3)5：L((e1|e2)e3)=L(e1e3|e2e3)6：L(εe1)=L(e1ε)=L(e1)例子：

正則式eL(e)ab*{a,ab,abb,abbb…}ab+{ab,abb,abbb…}a(a|b)+{aa,ab,aaa…}a(a|b)*{a,aa,ab,aaa…}語法圖文法正則式→自動機→狀態圖→編程a(a|b)*{a,aa,ab,aaa…}識別字：<字母>(<字母>|<數字>)*例子：Σ={a,b}L(a*)=｛ε,a,aa…｝

L(ba*)=｛b,ba,baa…｝

L(a|ba*)=｛a,b,ba…｝

L(aa|bb|ab|ba)={aa,bb,ab,ba}例子：∑={a,b}L(e)正則式e2.∑上所有以a為首的字串集a(a|b)*1.∑上所有以a為首後跟任意多個(包括0個)b的字串集1.ab*

正則運算式所定義的集合，稱為正則集。4.3確定自動機定義2.3

確定自動機(DA)A是一個五元組A=(S,∑,δ,s0,F)自動機有窮自動機無窮自動機確定自動機非確定自動機自動機應用：廣泛應用在人工智慧，推理邏輯等領域。4.3.1確定自動機

每個DA均可用矩陣(狀態轉換矩陣)或狀態轉換圖來表示。S是狀態集{s0,s1,…,sn}(n≥1)∑是字母表{a1,a2,…,an}(n≥1)δ是映射：S×∑→S,且為單值的

s0

是初始狀態，s0∈SF是終止狀態集，F

S例子：A=(S,∑,δ,s0,F)S={s0,s1,s2,s3}∑={a,b}F={s2,s3}δ(s0,a)=s1δ(s0,b)=s2δ(s1,b)=s1δ(s2,a)=s3δ(s2,b)=s0δ(s3,a)=s2s2_s3s0s3_s2s1s1s2s1+s0ba狀態轉換圖如下：S0-abbbaS1S3-+S2a

前一條表明自動機的推理作用，後一條表明其詞法分析的作用。 如果β∈L(A),則稱β可被A所接受。其中→表示映射，

表示推導。定義2