編譯原理課件

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

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

①

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

②

執(zhí)行目標程序編譯過程：編譯方式：編譯程序計算結果源程序目標程序初始數(shù)據(jù)運行系統(tǒng)子程序2、也可以采用邊翻譯邊執(zhí)行的解釋執(zhí)行方式，這種處理程序稱為解釋程序。解釋程序的結果是源程序的執(zhí)行結果。解釋方式：解釋程序計算結果源程序初始數(shù)據(jù)

采用這種方法的優(yōu)勢：可移植性。發(fā)布的程序理論上可以在任何硬件平臺上運行。即C#通過安裝在機子上的CLR(CommonLanguageRuntime-公共語言運行時），Java通過安裝在機子上的JVM(JavaVirtualMachine-Java虛擬機)來執(zhí)行中間代碼和字節(jié)碼。

傳統(tǒng)的語言（例如C、C++

），源代碼在經過編譯連接后直接生成了二進制代碼。而C#、java這些語言把源代碼編譯為了中間語言，C#把源代碼編譯為微軟中間語言MSIL，Java把源代碼編譯為字節(jié)碼。

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

C是直接編譯成機器碼，java是編譯程序將java源程序編譯成JVM可執(zhí)行代碼--java字節(jié)碼，再由虛擬機解釋執(zhí)行。§1.2編譯程序的組成一、編譯程序要完成的工作：詞法分析語法分析中間代碼生成中間代碼優(yōu)化目標代碼生成及和硬件有關的工作

表格管理

錯誤處理

詞法分析中間代碼生成

語法分析中間代碼優(yōu)化目標代碼生成

源程序

目標程序例子：用Pascal將英語句子譯成數(shù)字，用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、分析單詞：保留字、標識符、常數(shù)、運算符、分界符

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

①

程序處理

②

說明語句處理

③

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

①

分前后端可提高效率，減少重復勞動

②

利于優(yōu)化，便于組合1、編譯程序按其掃描遍數(shù)分為： 一遍掃描 多遍掃描2、若通過對源程序的掃描直接生成目標代碼，則稱編譯程序是單遍的。3、多遍掃描的好處是：便于分工、便于優(yōu)化，但前后掃描之間難免有些重復性工作。§1.3編譯程序的分遍源程序→詞法分析程序→中間文件1→語法分析程序→中間文件2→語義分析→中間文件3→優(yōu)化→中間文件4→目標程序多遍掃描的步驟：

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

1、開發(fā)編譯程序的步驟：

①

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

②

確定編譯程序的要求。

③

根據(jù)編譯程序的規(guī)模確定編譯程序的具體分遍及每遍的具體任務。

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

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

PL/0編譯程序

PL/0編譯程序

PL/0語言程序

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

類pcodepascal

2.1PL/0語言描述PL/0編譯程序類pcode解釋程序類pcode代碼PL/0源程序輸入輸出PL/0編譯系統(tǒng)的結構框架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表示的符號說明

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

|：表示‘或’

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

[]：表示為任選項

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

<程序>→<分程序>●<分程序>→[<常量說明部分>][<變量說明部分>][<過程說明部分>]<語句><常量說明部分>→CONST<常量定義>{,<常量定義>}<常量定義>→<標識符>=<無符號整數(shù)><無符號整數(shù)>→<數(shù)字>{<數(shù)字>}<變量說明部分>→VAR<標識符>{,<標識符>}<標識符>→<字母>{<字母>|<數(shù)字>}<過程說明部分>→<過程首部><分程序>{;<過程說明部分>}<過程首部>→procedure<標識符><語句>→<賦值語句>|<條件語句>|<當型循環(huán)語句>|<過程調用語句>|<讀語句>|<寫語句>|<復合語句>|<空><賦值語句>→<標識符>：=<表達式><復合語句>→begin<語句>{；<語句>}end<條件>→<表達式><關系運算符><表達式>|odd<表達式>

<表達式>→[+|—]<項>{<加法運算符><項>}<項>→<因子>{<乘法運算符><因子>}<因子>→<標識符>|<無符號整數(shù)>|‘(’<表達式>‘)’

<加法運算符>→+|-

<乘法運算符>→*|/

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

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

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

、‘;’

、‘(’

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

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

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

程序分程序.constidentnumber=,;varident,;;procedureident;分程序語句分程序identreadend;語句表達式：=begin語句語句)(ident,

自頂向下的語法分析

VARA;BEGINREAD(A)END.

<程序><分程序>.<變量說明部分><語句>VAR<標識符>；

<復合語句>

A

BEGIN<語句>END<讀語句>

READ

（

<標識符>）

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

例：如何用遞歸子程序法實現(xiàn)表達式的語法分析項表達式+-項+-項

因子

因子

*/語法圖因子的語法圖因子identnumber(表達式)表達式的EBNF

〈表達式〉∷=[+|-]〈項〉{（+|-）〈項〉}

〈項〉∷=〈因子〉{（*|/）〈因子〉}

〈因子〉∷=〈標識符〉|〈無符號整數(shù)〉|‘（’〈表達式〉‘）’〈表達式〉的遞歸子程序實現(xiàn)

procedureexpr;

begin

ifsymin[plus,minus]then

begin

getsym;term;

end

elseterm;

whilesymin[plus,

minus]do

begin

getsym;term;

end

end;

〈項〉的遞歸子程序實現(xiàn)

procedureterm;

begin

factor;

whilesymin[times,

slash]do

begin

getsym;factor;

end

end;〈因子〉的遞歸子程序實現(xiàn)

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 根據(jù)不同的指令有所區(qū)別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取常數(shù)10到棧頂(5)opr02次棧頂與棧頂相加(6)sto14棧頂值送變量c中(7)opr00

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

int05主程序入口開辟5個?？臻g(9)opr016從命令行讀入值置于棧頂(10)sto03將棧頂值存入變量b中(11)lod03將變量b的值取至棧頂(12)lit00將常數(shù)值0進棧(13)opr09次棧頂與棧頂是否不等(14)jpc024

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

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

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

3.1文法的直觀概念

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

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

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

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

<句子>

<主語><謂語>

<代詞><謂語>

我<謂語>

我<動詞><直接賓語>

我是<直接賓語>

我是<名詞>

我是大學生

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

語義Semantics

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

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

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

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

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

<整數(shù)>→<數(shù)字>|<整數(shù)><數(shù)字><數(shù)字>→0|1|2|…|9

標識符:以字母開頭以后由字母和數(shù)字組成的符號串。例子：<標識符>的巴科斯范式

<標識符>→<字母><標識符>→<標識符><字母><標識符>→<標識符><數(shù)字><字母>→a|b|…|z

<數(shù)字>→0|1|…|9例子：判定字符串a4y是<標識符>

<標識符>

<標識符><字母>

<標識符>y

<標識符><數(shù)字>y

<標識符>4y

<字母>4y

a4y2、語法圖作用：直觀、形象的描述語法規(guī)則。例子：標識符的語法圖表示標識符字母字母數(shù)字例子：無符號數(shù)的語法圖表示

2.45E+12無符號數(shù)無符號整數(shù)數(shù)字E無符號整數(shù)3.2符號和符號串1、字母表:它是非空有窮集。例如：∑={a,b,c}或∑={1,2,3}2、符號：字母表中的元素稱為符號。3、符號串：符號的有窮序列，符號串也稱為字。用ε來表示空符號串。例如：a,ab,abc,dsfsd4、長度：符號串的長度是指該串所包含的符號個數(shù)。用|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文法與語言的形式定義

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

表示文法需要一種工具，其中最常用的工具是所謂的巴克斯范式(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如何來描述一種語言？如果語言是有窮的（只含有有窮多個句子），可以將句子逐一列出來表示如果語言是無窮的，找出語言的有窮表示。語言的有窮表示有兩個途經：生成方式（文法）：語言中的每個句子可以用嚴格定義的規(guī)則來構造。識別方式（自動機）：用一個過程，當輸入的一任意串屬于語言時，該過程經有限次計算后就會停止并回答“是”，若不屬于，要麼能停止并回答“不是”，（要麼永遠繼續(xù)下去。）

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

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

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

VT=φ

用V表示VN∪

VT

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

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

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

1G：S→aAb

A→abA→aAb

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

例子：

B→b|Bb

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

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

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

產生式集記為P

初始符記為Z例子：自然數(shù)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型文法或正則（正規(guī)）文法（RG）產生的語言稱為3型語言正則（正規(guī)）語言（RL）

文法和語言

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

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

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

3型文法（正規(guī)文法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為一個新狀態(tài),它不在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規(guī)范推導和句柄定義3.6

設xUy

xuy是一直接推導。如果U是句型xUy中的最右非終極字符，則稱該推導為規(guī)范直接推導并記為xUyxuy。如果xy中的每步都是規(guī)范直接推導，則稱該推導為規(guī)范推導并記為xy。

r

+

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

如果每步都是最右非終極字符，則也稱該規(guī)范推導為最右推導。例子：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、用語法樹可證明每個句子都有一規(guī)范推導。構造語法樹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有關文法實用中的一些說明

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

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

2.文法中不包含多余規(guī)則

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

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

文法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在句子推導中出現(xiàn),必須滿足如下兩個條件：

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

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

*

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

對任一文法G1都可以構造文法G2使得L(G1)=L(G2)，并且G2有這樣的特點，即文法的初始符不出現(xiàn)于產生式的右部。例子：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的每個非終極符出現(xiàn)于某句型中。

定理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不出現(xiàn)在任何句型中，因此可以刪去相關的產生式。 得出：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。重復這個過程，直至不出現(xiàn)新的產生式為止。例子：設有文法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常整數(shù)：3實常數(shù)：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,則定義函數(shù)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…}語法圖文法正則式→自動機→狀態(tài)圖→編程a(a|b)*{a,aa,ab,aaa…}標識符：<字母>(<字母>|<數(shù)字>)*例子：Σ={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均可用矩陣(狀態(tài)轉換矩陣)或狀態(tài)轉換圖來表示。S是狀態(tài)集{s0,s1,…,sn}(n≥1)∑是字母表{a1,a2,…,an}(n≥1)δ是映射：S×∑→S,且為單值的

s0

是初始狀態(tài)，s0∈SF是終止狀態(tài)集，F(xiàn)

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狀態(tài)轉換圖如下：S0-abbbaS1S3-+S2a

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

表示推導。定義2.4

設A=(