编译原理和技术课件

編譯原理和技術

第一章引論

名詞解釋翻譯器(translator)、編譯器(compiler)解釋器(interpreter)編譯器從邏輯上可以分成若干個階段每個階段把根源程式從一種表示變換成另一種表示本章通過描述編譯器的各個階段來介紹編譯這個課題1.1編譯器概述詞法分析器語法分析器語義分析器根源程式中間代碼生成器獨立於機器的代碼優化器代碼生成器依賴於機器的代碼優化器目標機器代碼符號表符號表

positioninitialrate.........123詞法分析器id,1

=

id,2

+

id,3

60

position=initial+rate

601.1編譯器概述

記號流

字元流1.1編譯器概述運算式的語法特徵任何一個識別字都是運算式任何一個數都是運算式如果e1和e2都是運算式，那麼

e1+e2

e1

*

e2

(e1)也都是運算式運算式運算式運算式識別字運算式運算式(initial)識別字(rate)數(60)*+initial+rate*60的分析樹符號表

positioninitialrate.........123語法分析器id,1

=

id,2

+

id,3

60

=

+

60

id,1

id,2

id,3

語法樹1.1編譯器概述

記號流符號表

positioninitialrate.........1231.1編譯器概述語義分析器

=

+

60

id,1

id,2

id,3

=

+

inttofloatid,1

id,2

id,3

60

語法樹

語法樹符號表

positioninitialrate.........123中間代碼生成器t1=inttofloat(60)t2=id3

t1t3=id2+t2id1=t3

=

+

inttofloatid,1

id,2

id,3

60

1.1編譯器概述

三地址中間代碼

語法樹符號表

positioninitialrate.........123代碼優化器t1=inttofloat(60)t2=id3

t1t3=id2+t2id1=t3t1=id3*60.0id1=id2+t11.1編譯器概述

三地址中間代碼

三地址中間代碼符號表

positioninitialrate.........123代碼生成器MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id1t1=id3*60.0id1=id2+t11.1編譯器概述

三地址中間代碼

彙編代碼1.1編譯器概述解釋器和編譯器的區別詞法分析器語法分析器語義分析器根源程式中間代碼生成器獨立於機器的代碼優化器代碼生成器依賴於機器的代碼優化器目標機器代碼解釋器不生成目標代碼，而是直接執行根源程式所指定的運算

解釋器也需要對根源程式進行詞法、語法和語義分析,中間代碼生成1.1編譯器概述BASIC年代的解釋器功能：它將高級語言的根源程式翻譯成一種中間語言程式，然後對中間語言程式進行解釋執行在那個年代，編譯和解釋兩個功能是合在一個程式中，該程式被稱為解釋器Java年代的解釋器上述兩個功能分在兩個程式中前一個叫做編譯器，它把根源程式翻譯成一種叫做位元組碼的中間語言程式後一個叫做解釋器，它對位元組碼程式進行解釋執行1.1編譯器概述階段分組前端後端詞法分析器語法分析器語義分析器根源程式中間代碼生成器獨立於機器的代碼優化器代碼生成器依賴於機器的代碼優化器目標機器代碼1.1編譯器概述詞法分析器語法分析器語義分析器根源程式中間代碼生成器獨立於機器的代碼優化器代碼生成器依賴於機器的代碼優化器目標機器代碼階段分組遍1.2編譯器技術的應用

高級語言的實現高級編程語言易於編程，但程式運行較慢低級語言編程時可實施更有效的控制方式，得到更有效的代碼，但難編寫、易出錯、難維護流行編程語言的大多數演變都是朝著提高抽象級別的方向每一輪編程語言新特徵的出現都刺激編譯器優化的新研究1.2編譯器技術的應用

高級語言的實現 每一輪編程語言新特徵的出現都刺激編譯器優化的新研究支持用戶定義的聚合數據類型和高級控制流，如數組和記錄、迴圈和過程調用：C、Fortran面向對象的主要概念是數據抽象和性質繼承，使得程式更加模組化並易於維護：Smalltalk、C++、C#、Java類型安全的語言：Java沒有指針，也不允許指針算術。它用無用單元收集機制來自動地釋放那些不再使用的變數佔據的記憶體Java設計來支持代碼移植和代碼移動1.2編譯器技術的應用

針對電腦體系結構的優化電腦體系結構的迅速演化引起對新的編譯器技術一種不知足的需要並行化

編譯器重新整理指令，使得指令級並行更有效

編譯器從傳統的串行程序自動生成並行代碼，使之運行於多處理器上記憶體分層

編譯器優化歷來集中在優化處理器的執行上，但是現在更強調要使記憶體分層更有效1.2編譯器技術的應用

新電腦體系結構的設計現在電腦系統的性能不僅僅取決於它的原始速度，還取決於編譯器是否能生成充分利用其特徵的代碼在現代電腦體系結構的研究中，在處理器的設計階段就開發編譯器，並將編譯生成的代碼在模擬器上運行，以評價擬採用體系結構的特徵編譯器技術影響電腦體系結構設計的一個著名例子是精簡指令集電腦（RISC）的發明1.2編譯器技術的應用

程式翻譯二進位翻譯

編譯器技術可用於把一種機器的二進位代碼翻譯成另一種機器的代碼，以運行原先為別的指令集編譯的代碼資料庫查詢解釋器

資料庫查詢由一些謂詞組成，這些謂詞由包含關係運算的布爾運算式組成，可以被解釋執行,也可以被編譯成搜索資料庫的命令2.1詞法記號及屬性

2.1.1詞法記號、模式、詞法單元

記號名

詞法單元例舉

模式的非形式描述

if if 字元i,f

for for 字元f,o,rrelation <,<=,=,… <或<=或=或…id sum,count,D5 由字母開頭的字母數字串number 3.1,10,2.8E12 任何數值常數literal “seg.error” 引號“和”之間任意不含 引號本身的字串2.1詞法記號及屬性歷史上詞法定義中的一些問題忽略空格帶來的困難

DO8I

3.75 等同於 DO8I

3.75DO8I

3,75關鍵字不保留

IFTHENTHENTHEN=ELSE；ELSE…關鍵字、保留字和標準識別字的區別保留字是語言預先確定了含義的詞法單元標準識別字也是預先確定了含義的識別字，但程式可以重新聲明它的含義2.1詞法記號及屬性2.1.2詞法記號的屬性

position=initial+rate

60的記號和屬性值：

id，指向符號表中position條目的指針

assign_op

id，指向符號表中initial條目的指針

add_op

id，指向符號表中rate條目的指針

mul_op

number，整數值60

2.1詞法記號及屬性2.1.3詞法錯誤詞法分析器對根源程式採取非常局部的觀點例：難以發現下麵的錯誤

fi(a==f(x))

…在實數是“數字串.數字串”格式下，可以發現下麵的錯誤 123.x緊急方式的錯誤恢復 刪掉當前若干個字元，直至能讀出正確的記號錯誤修補 進行增、刪、替換和交換字元的嘗試2.2詞法記號的描述與識別

2.2.1串和語言字母表：符號的有限集合，例：={0,1}串：符號的有窮序列，例：0110,

語言：字母表上的一個串集 {,0,00,000,…},{},句子：屬於語言的串串的運算連接（積） xy，s

=s=s

冪

s0為，si為si-1s（i>0）

2.2詞法記號的描述與識別

語言的運算並： L

M={s|s

L或s

M}連接： LM={st|s

L且t

M}冪： L0是{

}，Li是Li-1L

閉包： L

=L0

L1

L2

…正閉包： L+=L1

L2

…例L:{A,B,…,Z,a,b,…,z},D:{0,1,…,9}L

D,LD,L6,L*,L(L

D)*,D+

2.2詞法記號的描述與識別

2.2.2正規式正規式用來表示簡單的語言，叫做正規集

正規式 定義的語言 備註

{

}

a {a} a

(r)|(s) L(r)∪L(s) r和s是正規式 (r)(s)

L(r)L(s) r和s是正規式

(r)*

(L(r))* r是正規式

(r) L(r) r是正規式 ((a)(b)*)|(c)可以寫成ab*|c

2.2詞法記號的描述與識別

正規式的例子

={a,b}a|b

{a,b}(a|b)(a|b)

{aa,ab,ba,bb}aa|ab|ba|bb

{aa,ab,ba,bb}a* 由字母a構成的所有串集(a|b)* 由a和b構成的所有串集複雜的例子(00|11|((01|10)(00|11)

(01|10)))

句子：010011010000100000101110012.2詞法記號的描述與識別

2.2.3正規定義

對正規式命名，使表示簡潔 d1

r1 d2

r2 ... dn

rn各個di的名字都不同每個ri都是

{d1,d2,…,di-1}上的正規式2.2詞法記號的描述與識別

正規定義的例子C語言的識別字是字母、數字和下劃線組成的串

letter_

A|B|…|Z|a|b|…

|z|_

digit

0

|1|…|9 id

letter_(letter_

|digit)*

2.2詞法記號的描述與識別

正規定義的例子

無符號數集合，例1946,11.28,63E8,1.99E

6

digit

0

|1|…|9

digits

digit

digit*

optional_fraction

.digits|

optional_exponent

(E(+|

|

)digits)|

number

digitsoptional_fractionoptional_exponent

簡化表示 number

digit+(.digit+)?(E(+|

)?digit+)?2.2詞法記號的描述與識別

正規定義的例子（進行下一步討論的例子）

while

while do

do relop

<|<=|=|<>|>|>=

letter

A|B|…|Z|a|b|…

|z id

letter(letter|digit)* number

digit+(.digit+)?(E

(+|

)?

digit+)?delim

blank|tab|newline

ws

delim+2.2詞法記號的描述與識別

2.2.4轉換圖關係算符的轉換圖

051624837return(relop,LE)return(relop,NE)return(relop,LT)return(relop,GE)return(relop,GT)return(relop,EQ)開始<=>=>=**otherother2.2詞法記號的描述與識別

識別字和關鍵字的轉換圖91011開始letterother*letter或digitreturn(installId())2.2詞法記號的描述與識別

無符號數的轉換圖 number

digit+(.digit+)?(E

(+|

)?

digit+)?開始1912131415161718digitdigitdigitdigitdigitdigitother.E+/

Edigitotherotherreturn(installNum())*2.2詞法記號的描述與識別

空白的轉換圖delim

blank|tab|newlinews

delim+2122開始delimother*delim202.3有限自動機

2.3.1不確定的有限自動機（簡稱NFA） 一個數學模型，它包括：

1、有限的狀態集合S

2、輸入符號集合

3、轉換函數move:S

(

{

})

P(S)

4、狀態s0是唯一的開始狀態

5、F

S是接受狀態集合識別語言(a|b)*ab

的NFA12開始a0abb輸入符號ab0{0,1}{0}1

{2}2

狀態

NFA的轉換表2.3有限自動機

識別語言(a|b)*ab

的NFA12開始a0abb2.3有限自動機

例

識別aa*|bb*的NFA12開始a0abb34

2.3.2確定的有限自動機（簡稱DFA)

一個數學模型，包括：1、有限的狀態集合S2、輸入字母集合

3、轉換函數move:S

S，且可以是部分函數4、唯一的開始狀態s05、接受狀態集合F

S12開始a0abbab識別語言(a|b)*ab

的DFA2.3有限自動機

2.3有限自動機

例 DFA，識別{0,1}上能被5整除的二進位數 已讀過 尚未讀 已讀部分的值 某時刻 101 0111000 5 讀進0 1010 111000 52=10 讀進1 10101 11000 102+1=21

5個狀態即可，分別代表已讀部分的值除以5的餘數例 DFA，識別{0,1}上能被5整除的二進位數0123開始410010101012.3有限自動機

10102=10101112=710例 DFA,接受0和1的個數都是偶數的字串00003211奇0奇1奇0偶11011開始偶0偶1偶0奇12.3有限自動機

2.3.3NFA到DFA的變換

子集構造法 1、DFA的一個狀態是NFA的一個狀態集合

2、讀了輸入a1a2…an後，

NFA能到達的所有狀態：s1,s2,…,sk，則

DFA到達狀態{s1,s2,…,sk}12a開始0abb{0}{0,1}aba{0,2}b2.3有限自動機

未畫完19開始

0ab

ab6782345

例 (a|b)*ab，NFA如下，把它變換為DFA2.3有限自動機

19開始

0ab

ab6782345

輸入符號ab狀態

2.3有限自動機

19開始

0ab

ab6782345

輸入符號abA狀態

A={0,1,2,4,7}

2.3有限自動機

19開始

0ab

ab6782345

輸入符號abAB狀態

A={0,1,2,4,7}B={1,2,3,4,6,7,8}

2.3有限自動機

19開始

0ab

ab6782345

輸入符號abABB狀態

A={0,1,2,4,7}B={1,2,3,4,6,7,8}2.3有限自動機

19開始

0ab

ab6782345

輸入符號abABCB狀態

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}

2.3有限自動機

19開始

0ab

ab6782345

輸入符號abABCBC狀態

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}2.3有限自動機

19開始

0ab

ab6782345

輸入符號abABCBBC狀態

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}2.3有限自動機

19開始

0ab

ab6782345

輸入符號abABCBBDC狀態

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自動機

19開始

0ab

ab6782345

輸入符號abABCBBDCD狀態

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自動機

19開始

0ab

ab6782345

輸入符號abABCBBDCBCD狀態

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自動機

19開始

0ab

ab6782345

輸入符號abABCBBDCBCDBC狀態

A={0,1,2,4,7}B={1,2,3,4,6,7,8}C={1,2,4,5,6,7}D={1,2,4,5,6,7,9}

2.3有限自動機

19開始

0ab

ab6782345

輸入符號abABCBBDCBCDBC狀態

BD開始aAabbabCba2.3有限自動機

19開始

0ab

ab6782345

BD開始aAabbabCba12開始a0abbab識別語言(a|b)*ab

的自動機2.3有限自動機

19開始

0ab

ab6782345

BD開始aAabbabCba12開始a0abbab識別語言(a|b)*ab

的自動機子集構造法不一定得到最簡DFA2.3有限自動機

BD開始aAabbaa,bCbaEb2.3.4DFA的化簡死狀態在轉換函數由部分函數改成全函數表示時引入左圖需要引入死狀態E；右圖無須引入死狀態BD開始aAabbabCba2.3有限自動機

可區別的狀態A和B是可區別的狀態

從A出發，讀過單字符b構成的串，到達非接受狀態C，而從B出發，讀過串b，到達接受狀態DA和C是不可區別的狀態 無任何串可用來像上面這樣 區別它們BD開始aAabbabCba2.3有限自動機

方法1.{A,B,C},{D}move({A,B,C},a)={B}move({A,B,C},b)={C,D}2.{A,C},{B},{D}move({A,C},a)={B}move({A,C},b)={C}BD開始aAabbabCba12開始a0abbab2.3有限自動機

從正規式建立識別器的步驟從正規式構造NFA（本節介紹） 用語法制導的演算法，它用正規式語法結構來指導構造過程把NFA變成DFA（子集構造法，已介紹）將DFA化簡（合併不可區別狀態，也已介紹）2.4從正規式到有限自動機首先構造識別

和字母表中一個符號的NFA重要特點：僅一個接受狀態，它沒有向外的轉換i開始

識別正規式

的NFAafif開始識別正規式a的NFA2.4從正規式到有限自動機構造識別主算符為選擇的正規式的NFA重要特點：僅一個接受狀態，它沒有向外的轉換

fi開始識別正規式s|t的NFAN(s)N(t)

2.4從正規式到有限自動機構造識別主算符為連接的正規式的NFA重要特點：僅一個接受狀態，它沒有向外的轉換識別正規式st的NFAiN(s)f開始N(t)2.4從正規式到有限自動機構造識別主算符為閉包的正規式的NFA重要特點：僅一個接受狀態，它沒有向外的轉換N(s)f開始識別正規式s*的NFAi

2.4從正規式到有限自動機對於加括弧的正規式(s)，使用N(s)本身作為它的NFA2.4從正規式到有限自動機本方法產生的NFA有下列性質N(r)的狀態數最多是r中符號和算符總數的兩倍N(r)只有一個接受狀態，接受狀態沒有向外的轉換2.4從正規式到有限自動機19開始

0ab

ab6782345

本方法產生的NFA有下列性質N(r)的每個狀態有一個用

的符號標記的指向其他結點的轉換，或者最多兩個指向其他結點的

轉換2.4從正規式到有限自動機19開始

0ab

ab6782345

2.4從正規式到有限自動機

19開始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規式到有限自動機

19開始

0

ab678ab2345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規式到有限自動機

19開始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規式到有限自動機

19開始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規式到有限自動機

19開始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規式到有限自動機19開始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解2.4從正規式到有限自動機

19開始

0ab

ab6782345

r9r7r8r4r3r5r6*)(r2r1a|bab(a|b)*ab的分解

(a|b)*ab的兩個NFA的比較12開始a0abb手工構造:演算法構造:2.4從正規式到有限自動機19開始

0ab

ab6782345

小結：從正規式建立識別器的步驟從正規式構造NFA把NFA變成DFA將DFA化簡存在其他辦法2.4從正規式到有限自動機

用Lex建立詞法分析器的步驟Lex編譯器Lex根源程式lex.llex.yy.cC編譯器lex.yy.ca.outa.out輸入流記號序列2.5詞法分析器的生成器Lex程式包括三個部分聲明％％翻譯規則％％輔助過程Lex程式的翻譯規則p1 {動作1}p2 {動作2}… …pn {動作n}2.5詞法分析器的生成器例——聲明部分%{/*常量LT,LE,EQ,NE,GT,GE, WHILE,DO,ID,NUMBER,RELOP的定義*/%}/*

正規定義

*/delim [\t\n]ws {delim}+letter [A

Za

z]digit [0

9]id {letter}({letter}|{digit})*number {digit}+(\.{digit}+)?(E[+\

]?{digit}+)?2.5詞法分析器的生成器例——翻譯規則部分{ws} {/*

沒有動作，也不返回*/}while {return(WHILE);}do {return(DO);}{id} {yylval=install_id();return(ID);}{number} {yylval=install_num(); return(NUMBER);}“<” {yylval=LT;return(RELOP);}“<=” {yylval=LE;return(RELOP);}“=” {yylval=EQ;return(RELOP);}“<>” {yylval=NE;return(RELOP);}“>” {yylval=GT;return(RELOP);}“>=” {yylval=GE;return(RELOP);}2.5詞法分析器的生成器例——輔助過程部分installId(){ /*

把詞法單元裝入符號表並返回指針。 yytext指向該詞法單元的第一個字元， yyleng給出的它的長度 */}installNum(){ /*

類似上面的過程，但詞法單元不是識別字而是數*/}2.5詞法分析器的生成器詞法分析器的作用和介面，用高級語言編寫詞法分析器等內容掌握下麵涉及的一些概念，它們之間轉換的技巧、方法或演算法非形式描述的語言

正規式正規式

NFA非形式描述的語言

NFANFA

DFADFA

最簡DFA非形式描述的語言

DFA（或最簡DFA）本章要點敘述下麵的正規式描述的語言，並畫出接受該語言的最簡DFA的狀態轉換圖

(1|01)*0*描述的語言是，所有不含子串001的0和1的串

3start001.1012剛讀過的不是0連續讀過一個0連續讀過不少於兩個0例題1bbbaabbaabbstartabbaaaaabababbabaababababababbbabaabb例題2用狀態轉換圖表示接受 (a|b)

a(a|b)(a|b)的DFA寫出語言“所有相鄰數字都不相同的非空數字串”的正規定義

123031357106798035790123answer

(0|no_00)(no_00)

(no_0|

)|no_0

no_0

(1|no_0-11)(no_0-11)

(no_0-1|

)|no_0-1

...no_0-8

9將這些正規定義逆序排列就是答案例題3 下麵C語言編譯器編譯下麵的函數時，報告 parseerrorbefore‘else’longgcd(p,q)longp,q;{if(p%q==0)

/*thenpart*/ returnq 此處遺漏分號 else

/*elsepart*/ returngcd(q,p%q);}例題43.1上下文無關文法3.1.1上下文無關文法的定義正規式能定義一些簡單的語言，能表示給定結構的固定次數的重複或者沒有指定次數的重複 例：a(ba)5,a(ba)*正規式不能用於描述配對或嵌套的結構 例1：配對括弧串的集合 例2：{wcw|w是a和b的串}

3.1上下文無關文法上下文無關文法是四元組（VT,VN,S,P）VT

: 終結符集合VN

: 非終結符集合S: 開始符號，非終結符中的一個P

: 產生式集合，產生式形式:A

例({id,+,

,

,(,)},{expr,op},expr,P)expr

expr

op

expr expr

(expr)expr

expr expr

idop

+ op

3.1上下文無關文法簡化表示expr

expr

op

expr |

(expr)|

expr|idop

+|

簡化表示E

EAE|(E)|

E|idA

+|

3.1上下文無關文法3.1.2

推導把產生式看成重寫規則，把符號串中的非終結符用其產生式右部的串來代替例 E

E+E|E

E|(E)|

E|id

E

E

(E)

(E+E)

(id+E)

(id+id)概念 上下文無關語言、等價的文法、句型記號S

*

、S

+w

3.1上下文無關文法例E

E+E|E

E|(E)|

E|id

最左推導 E

lm

E

lm

(E)

lm

(E

+E)

lm

(id+E)

lm

(id+id)最右推導（規範推導） E

rm

E

rm

(E)

rm

(E+E)

rm

(E+id)

rm

(id+id)3.1上下文無關文法3.1.3分析樹例E

E+E|E

E|(E)|

E|idEE

()EEE+idid3.1上下文無關文法3.1.4二義性 E

E

E

E

E+E

id

E

E

E+E

id

E+E

id

E+E

id

id+E

id

id+E

id

id+id

id

id+id 兩個不同的最左推導3.1上下文無關文法3.1.4二義性 E

E

E

E

E+E

id

E

E

E+E

id

E+E

id

E+E

id

id+E

id

id+E

id

id+id

id

id+id 兩棵不同的語法樹EEE*+EEidididEEidE*+EEidid3.2

語言和文法文法的優點

文法給出了精確的，易於理解的語法說明自動產生高效的分析器可以給語言定義出層次結構以文法為基礎的語言的實現便於語言的修改文法的問題文法只能描述編程語言的大部分語法，不能描述語言中上下文有關的語法特徵3.2

語言和文法3.2.1

正規式和上下文無關文法的比較正規式(a|b)*ab文法A0

a

A0|bA0|a

A1A1

b

A2A2

12開始a0abb3.2

語言和文法3.2.2分離詞法分析器理由為什麼要用正規式定義詞法

詞法規則非常簡單，不必用上下文無關文法對於詞法記號，正規式描述簡潔且易於理解從正規式構造出的詞法分析器效率高3.2

語言和文法從軟體工程角度看，詞法分析和語法分析的分離有如下好處簡化設計編譯器的效率會改進編譯器的可移植性加強便於編譯器前端的模組劃分3.2

語言和文法能否把詞法分析併入到語法分析中，直接從字元流進行語法分析若把詞法分析和語法分析合在一起，則必須將語言的注解和空白的規則反映在文法中，文法將大大複雜注解和空白由自己來處理的分析器，比注解和空格已由詞法分析器刪除的分析器要複雜得多3.2

語言和文法3.2.3

驗證文法產生的語言G:S

(S)S|

L(G)=配對的括弧串的集合3.2

語言和文法3.2.3

驗證文法產生的語言G:S

(S)S|

L(G)=配對的括弧串的集合按推導步數進行歸納：推出的是配對括弧串歸納基礎：S

歸納假設：少於n步的推導都產生配對的括弧串歸納步驟：n步的最左推導如下：

S(S)S*(x)S*(x)y3.2

語言和文法3.2.3

驗證文法產生的語言G:S

(S)S|

L(G)=配對的括弧串的集合按串長進行歸納：配對括弧串可由S推出歸納基礎：S

歸納假設：長度小於2n的都可以從S推導出來歸納步驟：考慮長度為2n(n

1)的w=(x)y

S(S)S*(x)S*(x)y3.2

語言和文法3.2.4適當的運算式文法用一種層次觀點看待運算式 id

id

(id+id)+id

id+id3.2

語言和文法3.2.4適當的運算式文法用一種層次觀點看待運算式

id

id

(id+id)+id

id+id

id

id

(id+id)

文法 expr

expr+term|term term

term

factor|factor

factor

id|(expr)3.2

語言和文法expr

expr+term|termterm

term

factor|factor

factor

id|(expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid+id

id分析樹

id

id

id分析樹

3.2

語言和文法3.2.5消除二義性stmt

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

elsestmt兩個最左推導：

stmt

ifexprthenstmt

ifexprthenifexprthenstmtelsestmt

stmt

ifexprthenstmtelsestmt

ifexprthenifexprthenstmtelsestmt

3.2

語言和文法

無二義的文法stmt

matched_stmt

|unmatched_stmtmatched_stmt

ifexprthenmatched_stmt

elsematched_stmt

|otherunmatched_stmt

ifexprthenstmt |ifexprthenmatched_stmt

elseunmatched_stmt3.2

語言和文法3.2.6消除左遞歸文法左遞歸 A

+Aa

直接左遞歸 A

Aa|b

串的特點 ba...a消除直接左遞歸 A

bA

A

aA

|

3.2

語言和文法例

算術表達文法

E

E+T|T （T+T...+T） T

T

F|F （F

F...

F） F

(E)|id消除左遞歸後文法 E

TE

E

+TE

|

T

FT

T

FT

|

F

(E)|id3.2

語言和文法非直接左遞歸 S

Aa|b

A

Sd|

先變換成直接左遞歸 S

Aa|b A

Aad|bd|

再消除左遞歸

S

Aa|b A

bdA

|A

A

adA

|

3.2

語言和文法3.2.7

提左因數有左因數的文法 A

1|

2提左因數 A

A

A

1|

2

3.2

語言和文法例

懸空else的文法 stmt

ifexprthenstmtelsestmt

|ifexprthenstmt |other 提左因數 stmt

ifexprthenstmt

optional_else_part |other optional_else_part

elsestmt |

3.2

語言和文法3.2.8

非上下文無關的語言構造L1={wcw|w屬於(a|b)*}識別字的聲明應先於其引用的抽象

L2={anbmcndm|n

0,m

0}形參個數和實參個數應該相同的抽象

L3={anbncn|n

0}早先排版描述的一個現象的抽象

b

e

g

i

n：5個字母鍵，5個回退鍵，5個下劃線鍵3.2

語言和文法L1

={wcwR|w

(a|b)*}

S

aSa|bSb|c

L2={anbmcmdn|n

1,m

1}

S

aSd|aAd A

bAc|bcL

2={anbncmdm|n1，m1} S

AB A

aAb|ab

B

cBd|cd3.2

語言和文法L3

={anbn|n

1}

S

aSb|abL3

是不能用正規式描述的語言的一個範例

若存在接受L3

的DFAD，狀態數為k個設D讀完,

a,aa,

…,ak

分別到達狀態s0,s1,

…,sk至少有兩個狀態相同，例如是si和sj，則ajbi屬於L3

si…fs0標記為ai的路徑標記為bi的路徑標記為aj

i的路徑…

…3.2

語言和文法3.2.9

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|13.2

語言和文法3.2.9

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|1短語文法3.2

語言和文法3.2.9

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外短語文法3.2

語言和文法3.2.9

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外短語文法、上下文有關文法3.2

語言和文法3.2.9

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外2型文法：A

，A

VN,

(VN∪VT)*短語文法、上下文有關文法3.2

語言和文法3.2.9

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外2型文法：A

，A

VN,

(VN∪VT)*短語文法、上下文有關文法、上下文無關文法3.2

語言和文法3.2.9

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外2型文法：A

，A

VN,

(VN∪VT)*3型文法：A

aB或A

a，A,B

VN,a

VT

短語文法、上下文有關文法、上下文無關文法3.2

語言和文法3.2.9

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：

，,(VN

VT)*,|

|11型文法：|

||

|，但S

可以例外2型文法：A

，A

VN,

(VN∪VT)*3型文法：A

aB或A

a，A,B

VN,a

VT

短語文法、上下文有關文法、上下文無關文法、正規文法3.2

語言和文法例 L3＝{anbncn|n

1}的上下文有關文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推導過程如下：S

*an-1S(BC)n

1 用S

aSBCn-1次S

+an(BC)n

用S

aBC1次S

+anBnCn 用CB

BC交換相鄰的CBS

+anbBn

1Cn 用aB

ab1次S

+anbnCn

用bB

bbn-1次S

+anbncCn-1 用bC

bc1次S

+anbncn 用cC

cc

n-1次3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹SaCbSaCbcdSaCbc 不能處理左遞歸3.3

自上而下分析不能處理左遞歸的例子 算術表達文法

E

E+T|T T

T

F|F F

(E)|idEE+TE+TE+T………3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹SSSaCbaaCCbbcdc 不能處理左遞歸、複雜的回溯技術3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹SSSaCbaaCCbbcdc 不能處理左遞歸、複雜的回溯技術、回溯導致語義工作推倒重來3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹SSSaCbaaCCbbcdc 不能處理左遞歸、複雜的回溯技術、回溯導致語義工作推倒重來、難以報告出錯的確切位置3.3

自上而下分析3.3.1自上而下分析的一般方法例 文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹SSSaCbaaCCbbcdc 不能處理左遞歸、複雜的回溯技術、回溯導致語義工作推倒重來、難以報告出錯的確切位置、效率低3.3

自上而下分析3.3.2LL(1)文法對文法加什麼樣的限制可以保證沒有回溯？先定義兩個和文法有關的函數FIRST(

)={a|

*a…,a

VT} 特別是，

*

時，規定

FIRST(

) 對A的任何兩個不同選擇

i

和

j，希望有 FIRST(

i)

FIRST(

j)=

若FIRST(

i)或FIRST(

j)含，還需增加條件3.3

自上而下分析3.3.2LL(1)文法對文法加什麼樣的限制可以保證沒有回溯？先定義兩個和文法有關的函數FIRST(

)={a|

*a…,a

VT} 特別是，

*

時，規定

FIRST(

)FOLLOW(A)={a|S

*…Aa…，a

VT} 如果A是某個句型的最右符號，那麼$屬於FOLLOW(A)3.3

自上而下分析LL(1)文法 任何兩個產生式A

|

都滿足下列條件：FIRST(

)

FIRST(

)=

若

*

，那麼FIRST(

)

FOLLOW(A)=

例如,對於下麵文法，面臨a…時，第2步推導不知用哪個產生式S

A

BA

ab| a

FIRST(ab)

FOLLOW(A)

B

aCC…3.3

自上而下分析LL(1)文法 任何兩個產生式A

|

都滿足下列條件：FIRST(

)

FIRST(

)=

若

*

，那麼FIRST(

)

FOLLOW(A)=

LL(1)文法有一些明顯的性質沒有公共左因數不是二義的不含左遞歸3.3

自上而下分析例 E

TE

E

+TE

|

T

FT

T

FT

|

F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E

)={+,

}FRIST(T

)={

,

}FOLLOW(E)=FOLLOW(E

)={),$}FOLLOW(T)=FOLLOW(T

)={+,),$}FOLLOW(F)={+,

,),$}3.3

自上而下分析3.3.3遞歸下降的預測分析為每一個非終結符寫一個分析過程這些過程可能是遞歸的例 type

simple |

id |array[simple]oftype simple

integer |char |numdotdotnum3.3

自上而下分析一個輔助過程voidmatch(terminalt){ if(lookahead==t)lookahead=nextToken(); elseerror();}3.3

自上而下分析voidtype(){ if((lookahead==integer)||(lookahead==char)|| (lookahead==num)) simple(); elseif(lookahead==

){match(

);match(id);} elseif(lookahead==array){ match(array);match(

[

);simple(); match(

]

);match(of);type(); } elseerror();}

type

simple |

id |array[simple]oftype3.3

自上而下分析voidsimple(){ if(lookahead==integer)match(integer); elseif(lookahead==char)match(char); elseif(lookahead==num){ match(num);match(dotdot);match(num); } elseerror();}

simple

integer |char |numdotdotnum3.3

自上而下分析3.3.4非遞歸的預測分析a+b$輸入預測分析程式分析表M輸出

XYZ$棧3.3

自上而下分析非終結符輸

入

符

號

id

+

...EE

TE

E

E

+TE

T

T

FT

T

T

T

FT

F

F

id分析表的一部分3.3

自上而下分析棧

輸

入

輸

出

$E

id

id+id$

預測分析器接受輸入id

*

id+id的前一部分動作

3.3

自上而下分析棧

輸

入

輸

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

預測分析器接受輸入id

*

id+id的前一部分動作

3.3

自上而下分析棧

輸

入

輸

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

預測分析器接受輸入id

*

id+id的前一部分動作

3.3

自上而下分析棧

輸

入

輸

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

$E

T

id

id

id+id$

F

id

預測分析器接受輸入id

*

id+id的前一部分動作

3.3

自上而下分析棧

輸

入

輸

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

$E

T

id

id

id+id$

F

id

$E

T

id+id$

預測分析器接受輸入id

*

id+id的前一部分動作

3.3

自上而下分析棧

輸

入

輸

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

$E

T

id

id

id+id$

F

id

$E

T

id+id$

$E

T

F

id+id$

T

FT

預測分析器接受輸入id

*

id+id的前一部分動作

3.3

自上而下分析棧

輸

入

輸

出

$E

id

id+id$

$E

T

id

id+id$

E

TE

$E

T

F

id

id+id$

T

FT

$E

T

id

id

id+id$

F

id

$E

T

id+id$

$