編譯原理課件

編譯原理和技術(shù)課程簡(jiǎn)介課程內(nèi)容介紹編譯器構(gòu)造的一般原理和基本實(shí)現(xiàn)方法介紹的理論知識(shí)：形式語言和自動(dòng)機(jī)理論、語法制導(dǎo)的定義和屬性文法、類型論等強(qiáng)調(diào)形式化描述技術(shù)強(qiáng)調(diào)對(duì)編譯原理和技術(shù)的宏觀理解，不把注意力分散到枝節(jié)算法，不偏向于某種源語言或目標(biāo)機(jī)器課程簡(jiǎn)介學(xué)習(xí)的意義對(duì)編程語言的設(shè)計(jì)和實(shí)現(xiàn)有深刻的理解，對(duì)和編程語言有關(guān)的理論有所了解，對(duì)宏觀上把握編程語言來說，起一個(gè)奠基的作用。從軟件工程看，編譯器是一個(gè)很好的實(shí)例，所介紹的概念和技術(shù)能應(yīng)用到一般的軟件設(shè)計(jì)之中。大多數(shù)程序員同時(shí)是簡(jiǎn)單語言的設(shè)計(jì)者，有助于提高對(duì)這些語言的設(shè)計(jì)水平。在軟件逆向工程、程序理解和軟件安全等方面有著廣泛的應(yīng)用。課程簡(jiǎn)介教材和參考書陳火旺，程序設(shè)計(jì)語言編譯原理，國(guó)防工業(yè)出版社，2000年A.

Aho,

R.

Sethi,

and

J.

D.Ullman,Compilers:

Principles,

Techniques,

andTools

,

2nd

edition,

Addison-Wesley,1986陳意云、張昱，編譯原理習(xí)題精選，中國(guó)科大出版社，2002第一章 程序設(shè)計(jì)語言與編譯程序程序設(shè)計(jì)語言的分類低級(jí)語言機(jī)器語言：計(jì)算機(jī)懂得的，用0、1表示指令（操作和數(shù)字）的語言。匯編語言：計(jì)算機(jī)的符號(hào)形式的指令系統(tǒng)，例如用ADD

X

Y表示X與Y相加，用CAL

P表示調(diào)用P等。高級(jí)語言與自然語言比較接近，具有豐富數(shù)據(jù)結(jié)構(gòu)和控制結(jié)構(gòu)等特點(diǎn)的程序設(shè)計(jì)語言。翻譯和解釋翻譯能夠把某一種語言程序(稱為源語言程序)轉(zhuǎn)換成另一種語言(成為目標(biāo)程序),而后者與前者在邏輯上是等價(jià)的.解釋以源程序作為輸入，在解釋過程中不產(chǎn)生目標(biāo)程序而是解釋執(zhí)行程序本身。編譯器:如果源語言是諸如FORTRAN、PASCAL、C、Ada、Smalltalk或Java這樣的“高級(jí)語言”，而目標(biāo)

語言是諸如匯編語言或機(jī)器語言之類的“低級(jí)語言”，這樣的翻譯器就稱為編譯器。源程序編譯程序目標(biāo)程序(*.C

/

*.PAS)源語言、源程序目標(biāo)語言、目標(biāo)程序匯編程序也是一種翻譯程序(*.OBJ

/

*.EXE)程序的執(zhí)行源程序解釋程序計(jì)算結(jié)果解釋執(zhí)行：使用解釋程序，對(duì)程序逐個(gè)語句進(jìn)行分析，根據(jù)語句的含義進(jìn)行執(zhí)行，象口譯。如：BASIC、DOS命令，問題：效率低下。輸入數(shù)據(jù)程序的執(zhí)行編譯執(zhí)行：首先由翻譯程序?qū)⒊绦蚍g成為機(jī)器語言（或者虛擬機(jī)的語言），然后執(zhí)行。翻譯的方式可以使得一次翻譯過后，多次運(yùn)行。適于花較大的精力進(jìn)行優(yōu)化工作。源程序編譯程序目標(biāo)程序運(yùn)行系統(tǒng)計(jì)算結(jié)果輸入數(shù)據(jù)編譯程序與運(yùn)行系統(tǒng)合稱為編譯系統(tǒng)交叉編譯（或匯編）計(jì)算機(jī)A源程序的編譯（或匯編）和目標(biāo)程序的執(zhí)行不一定在同一種計(jì)算機(jī)上完成。當(dāng)源程序由另一種計(jì)算機(jī)進(jìn)行編譯（或匯編）時(shí)，稱為交叉編譯或匯編。源程序P編譯程序C目標(biāo)程序P1計(jì)算機(jī)B運(yùn)行程序運(yùn)行結(jié)果S原始數(shù)據(jù)D編譯過程概述編譯器是一個(gè)復(fù)雜的系統(tǒng)程序，從邏輯上可以分成若干階段每個(gè)階段把源程序從一種表示變換成另一種表示通過描述編譯器的各個(gè)階段來介紹編譯這個(gè)課題翻譯外文書刊編譯源程序分析閱讀原文識(shí)別單詞分析句子辨析語句意義輸入并掃描源程序詞法分析語法分析語義分析綜合修辭加工寫出譯文代碼優(yōu)化目標(biāo)代碼生成編譯程序的邏輯結(jié)構(gòu)源程序詞法分析器語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器目標(biāo)程序出錯(cuò)管理器符號(hào)表管理器Pascal語句編譯示例position

:=

initial

+

rate

*

60假定變量都是實(shí)型1.1詞法分析作為編譯程序的輸入，源程序僅僅是一個(gè)長(zhǎng)長(zhǎng)的字符串，詞法分析程序?qū)堰@種形式的源程序轉(zhuǎn)換為便于編譯程序其余部分進(jìn)行處理的內(nèi)部格式。其工作任務(wù)如下：(1)識(shí)別出源程序中的各個(gè)基本語法單位；(2)刪除無用的空白字符、回車符以及其他非實(shí)質(zhì)性字符；

(3)刪除注釋；(4)進(jìn)行詞法檢查，報(bào)告所發(fā)現(xiàn)的錯(cuò)誤；1.1詞法分析.

.

..

.

.initialrate詞法分析器id1

:=

id2

+

id3

*

60position

:=

initial

+

rate

*

60

符

號(hào)

表1

position

.

.

.符號(hào)表是為每個(gè)標(biāo)識(shí)符保存一個(gè)記錄的數(shù)據(jù)結(jié)構(gòu)。通過該數(shù)據(jù)結(jié)構(gòu)可迅速查找標(biāo)識(shí)符記錄，在此記錄中讀取和存取數(shù)據(jù)。語法分析程序以詞法分析程序所輸出的用內(nèi)部編碼格式表示的單詞序列作為輸入，分析源程序的結(jié)構(gòu)，判別它是否為相應(yīng)程序設(shè)計(jì)語言的一個(gè)合法程序。其一般途徑如下：構(gòu)造一棵完整的分析樹，實(shí)質(zhì)是一個(gè)有標(biāo)記的有序樹形結(jié)構(gòu)，葉子上的標(biāo)記是程序中的各個(gè)單詞，而節(jié)點(diǎn)上的標(biāo)記則是程序設(shè)計(jì)語言的有關(guān)語法構(gòu)造名1.2語法分析1.2語法分析任何一個(gè)標(biāo)識(shí)符都是表達(dá)式；任何一個(gè)數(shù)都是表達(dá)式；1

2如果e

和e

都是表達(dá)式，那么e1

+

e2

e1

*

e2

(e1)也都是表達(dá)式表達(dá)式表達(dá)式標(biāo)識(shí)符表達(dá)式(initial)標(biāo)識(shí)符(rate)數(shù)(60)*表達(dá)式+表達(dá)式position

:=

initial

+

rate

*1.2語法分析表達(dá)式表達(dá)式標(biāo)識(shí)符表達(dá)式(initial)標(biāo)識(shí)符(rate)數(shù)(60)*表達(dá)式+表達(dá)式position

:=

initial

+

rate

*

60賦值語句:=標(biāo)識(shí)符(position)分析樹1.2語法分析.

.

..

.

.符

號(hào)

表1

position

.

.

.initialrate語法分析器id1

:=

id2

+

id3

*

60:=+*60id1id2id3語法樹1.3語義分析語法分析程序用以明確程序的組成結(jié)構(gòu)。語義分析用以分析各語法成分的含義和用途以及進(jìn)行的運(yùn)算和操作。其任務(wù)如下：(1)收集類型信息

(2)語義檢查1.3語義分析.

.

..

.

.符

號(hào)

表1

position

.

.

.initialrate語義分析器:=+*60id1id2id3:=+*id1id2id3

inttoreal60詞法分析器語法分析器語義分析器源程序出錯(cuò)管理器符號(hào)表管理器前三個(gè)階段完成對(duì)源程序的分析中間代碼生成器代碼優(yōu)化器代碼生成器目標(biāo)程序格式打印程序、文擋抽取程序、靜態(tài)檢查程序1.4中間代碼生成為了便于處理以及代碼的優(yōu)化，通常在語義分析后不直接產(chǎn)生機(jī)器語言或匯編語言形式的目標(biāo)代碼，而是生成介于源語言和目標(biāo)語言之間的中間語言代碼。目前常見的中間代碼形式有：(1)三地址代碼逆波蘭表示樹形結(jié)構(gòu)1.4中間代碼生成temp1

:=

inttoreal(60)temp2

:=

id3

*

temp1temp3

:=

id2

+

temp2id1

:=

temp3:=+*id1id2id3

inttoreal60中間代碼生成器三地址代碼由三地址語句序列組成每個(gè)三地址語句最多有三個(gè)操作數(shù)每個(gè)語句除賦值算符外，最多只有一個(gè)算符編譯器必須產(chǎn)生臨時(shí)變量保存每個(gè)語句的計(jì)算結(jié)果1.5

代碼優(yōu)化為了得到質(zhì)量較高的目標(biāo)代碼，常常在中間代碼生成和目標(biāo)代碼生成兩個(gè)階段之間，插入一個(gè)代碼優(yōu)化階段。如果中間代碼生成算法比較簡(jiǎn)單，則給代碼優(yōu)化留了很多機(jī)會(huì)。目標(biāo)程序的衡量標(biāo)準(zhǔn)：空間指標(biāo)時(shí)間指標(biāo)1.5

代碼優(yōu)化.

.

..

.

.符

號(hào)

表1

position

.

.

.initialratetemp1

:=

inttoreal(60)temp2

:=

id3

*

temp1temp3

:=

id2

+

temp2id1

:=

temp3代碼優(yōu)化器temp1

:=

id3

*

60.0id1

:=

id2

+

temp11.6代碼生成代碼生成器接受語義分析（或優(yōu)化處理）產(chǎn)生的中間代碼，并結(jié)合在前面各階段對(duì)源程序進(jìn)行分析和加工所得到的有關(guān)信息，將中間代碼翻譯為機(jī)器代碼或匯編碼。代碼生成階段的任務(wù)：為變量分配存儲(chǔ)單元寄存器分配生成與中間代碼等價(jià)的目標(biāo)代碼目標(biāo)代碼有如下形式：具有絕對(duì)地址的機(jī)器指令代碼匯編語言形式的目標(biāo)程序模塊結(jié)構(gòu)的機(jī)器指令。1.6代碼生成temp1

:=

id3

*

60.0id1

:=

id2

*

temp1代碼生成器MOVF

id3,

R2MULF

#60.0,

R2MOVF

id2,

R1ADDF

R2,

R1MOVF

R1,

id1.

.

..

.

.符

號(hào)

表1

position

.

.

.initialrate詞法分析器語法分析器語義分析器源程序中間代碼生成器代碼優(yōu)化器代碼生成器目標(biāo)程序出錯(cuò)管理器符號(hào)表管理器后三個(gè)階段對(duì)源程序進(jìn)行綜合源程序詞法分析器語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器目標(biāo)程序出錯(cuò)管理器符號(hào)表管理器1.7符號(hào)表管理在編譯過程中，需要經(jīng)常收集、記錄或查詢?cè)闯绦蛑兴霈F(xiàn)的各種量的有關(guān)屬性。編譯程序需要建立一批不同用途的表（如常數(shù)表、名字表、循環(huán)層次表），這些表稱為符號(hào)表。符號(hào)表管理程序：在編譯程序中，造表和查表的工作由一組專用的程序來完成，它們分別安插在編譯程序的有關(guān)部分，這一組程序就組成了相應(yīng)編譯程序的符號(hào)表管理程序1.7符號(hào)表管理rate23符號(hào)表的構(gòu)成：由若干記錄組成每條記錄由若干字段組成，用來存放與之相關(guān)的信息符

號(hào)

表position.

.

.名字1

initial信息.

.

..

.

.1.8錯(cuò)誤診斷和報(bào)告在編譯程序中，錯(cuò)誤是難免的。一個(gè)較完善的編譯程序應(yīng)具有廣泛的程序查錯(cuò)，能準(zhǔn)確地報(bào)告錯(cuò)誤的位置和類型，并具有一定的校錯(cuò)能力。錯(cuò)誤處理程序：在編譯系統(tǒng)的各個(gè)部分都可能有程序診斷的問題。通常在編譯系統(tǒng)的各個(gè)部分，視編譯工作的進(jìn)程和需要，分別插入一些用于進(jìn)行錯(cuò)誤診斷的程序段落。這些程序段落的總體就組成了該編譯系統(tǒng)的錯(cuò)誤處理程序。1.9

階段的分組詞法分析器語法分析器語義分析器源程序中間代碼生成器代碼優(yōu)化器代碼生成器目標(biāo)程序出錯(cuò)管理器符號(hào)表管理器前端后端1.9

階段的分組語法分析程序詞法分析程序語義分析及代碼生成程序遍指對(duì)源程序或其內(nèi)部表示從頭到尾掃視一次，并進(jìn)行有關(guān)的加工處理工作。源程序目標(biāo)程序1.10編譯器的編寫用匯編語言編寫編譯器用通用語言來編寫編譯器使用專門的編譯器編寫工具編寫

LEX、YACC、語法制導(dǎo)翻譯工具、自動(dòng)代碼生成器、數(shù)據(jù)流工具習(xí)

題列舉出你所使用過的所有計(jì)算機(jī)語言和所有的“翻譯”程序（編譯、解釋、匯編）從你使用過的編譯器中選擇一個(gè)最熟悉的，寫出從編寫到運(yùn)行一個(gè)應(yīng)用程序的全過程典型的編譯器可劃分成哪幾個(gè)主要的邏輯階段，各階段的主要功能是什么？第二章

詞法分析詞法分析器語法分析器記號(hào)取下一個(gè)記號(hào)符號(hào)表本章內(nèi)容詞法分析器：把構(gòu)成源程序的字符流翻譯成記號(hào)流，還完成和用戶接口的一些任務(wù)圍繞詞法分析器的自動(dòng)生成展開介紹正規(guī)式、狀態(tài)轉(zhuǎn)換圖和有限自動(dòng)機(jī)概念源程序3.1詞法記號(hào)及屬性3.1.1詞法記號(hào)、模式、詞法單元模式的非形式描述

varfor<或<=或=或…由字母開頭的字母數(shù)字串任何數(shù)值常數(shù)詞法記號(hào)

詞法單元例舉var

varfor

forrelation

<

,

<

=

,

=

,

…

id

sum,

count,

D5

num

3.1,

10,

2.8

E12literal符“seg.error”

引號(hào)“和”之間的任串，但引號(hào)本身除外3.1詞法記號(hào)及屬性DO

8

I3.

75DO8I3.

75DO

8

I3,

75歷史上詞法定義中的一些問題–忽略空格帶來的困難–關(guān)鍵字是否保留IF

THEN

THEN

THEN=ELSE；ELSE

…關(guān)鍵字、保留字和標(biāo)準(zhǔn)標(biāo)識(shí)符的區(qū)別3.1詞法記號(hào)及屬性3.1.2詞法記號(hào)的屬性position:=initial+rate

*

60的記號(hào)和屬性值：

id，指向符號(hào)表中position條目的指針

assign

_

op，id，指向符號(hào)表中initial條目的指針

add_op，+id，指向符號(hào)表中rate條目的指針

mul_

op,*num，整數(shù)值603.1詞法記號(hào)及屬性3.1.3詞法錯(cuò)誤–詞法分析器對(duì)源程序采取非常局部的觀點(diǎn)–難以發(fā)現(xiàn)下面的錯(cuò)誤fi

(a

==

f

(x)

)

…在實(shí)數(shù)是a.b格式下，可以發(fā)現(xiàn)下面的錯(cuò)誤

123.–緊急方式的錯(cuò)誤恢復(fù)錯(cuò)誤修補(bǔ)3.2詞法記號(hào)的描述與識(shí)別=

{0,1}串和語言字母表：符號(hào)的有限集合，

例：串：符號(hào)的有窮序列，例：0110,語言：字母表上的一個(gè)串集{

,0,00,000,…},

{

},–句子：屬于語言的串串的運(yùn)算–積（指數(shù)）

s0為–

連接

xy，s

=

s

=

s，si為si

-1s（i

>0）3.2詞法記號(hào)的描述與識(shí)別語言的運(yùn)算–和：L∪M

={s

|

s–連接：LM

={st

|

sL

或

s

M

}L

且

t

M}–

指數(shù)：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+3.2詞法記號(hào)的描述與識(shí)別3.2.2

正規(guī)式正規(guī)式用來表示簡(jiǎn)單的語言，叫做正規(guī)集正規(guī)式定義的語言{

}備注a{a}a(r)

|

(s)L(r)∪L(s)r和s是正規(guī)式(r)(s)L(r)L(s)r和s是正規(guī)式(r)*(L(r))*r是正規(guī)式(r)L(r)r是正規(guī)式((a)(b)*)|(c)可以寫成ab*|

c3.2詞法記號(hào)的描述與識(shí)別=

{a,

b}{a,

b}{aa,

ab,

ba,

bb}{aa,

ab,

ba,

bb}由字母a構(gòu)成的所有串集由a和b構(gòu)成的所有串集正規(guī)式的例子a

|

b(a

|

b)

(a

|

b

)aa

|

ab

|

ba

|

bba*(a

|

b)*復(fù)雜的例子(

00

|

11

|

(

(01

|

10)

(00

|

11)

(01

|

10)

)

)010011010000100000101110013.2詞法記號(hào)的描述與識(shí)別3.2.3正規(guī)定義對(duì)正規(guī)式命名，使表示簡(jiǎn)潔。d1

r1d2

r2.

.

.dn

rn各個(gè)di的名字都不同每個(gè)ri都是

{d1,

d2,

…,

di-1

}上的正規(guī)式3.2詞法記號(hào)的描述與識(shí)別正規(guī)定義的例子Pascal語言的標(biāo)識(shí)符集合letterdigitidA

|

B

|

…

|

Z

|

a

|

b

|

…

|

z0

|

1

|

…

|

9letter(letter|digit)*3.2詞法記號(hào)的描述與識(shí)別正規(guī)定義的例子Pascal無符號(hào)數(shù)集合，例1946,11.28,63.6E8,1.99Edigitdigits0

|

1

|

…

|

9digit

digit*optional_fractionoptional_exponent.digits|(E

(

+

|

|

)

digits

)

|digits

optional_fraction

optional_exponennum簡(jiǎn)化表示num digit+

(.digit+)?

(E(+|

)?

digit+)?3.2詞法記號(hào)的描述與識(shí)別正規(guī)定義的例子while

whiledo

dorelop

<

|

<

=

|

=

|

<

>

|

>

|

>

=id

letter

(letter

|

digit

)*num digit+

(.digit+)?

(E

(+

|

)?

digit+)?delimblank

|

tab

|

newlinews

delim+3.2詞法記號(hào)的描述與識(shí)別0562481

373.2.4轉(zhuǎn)換圖關(guān)系算符的轉(zhuǎn)換圖return(relop,

LE)return(relop,

NE)return(relop,

GE)return(relop,

GT)return(relop,

EQ)開始<=>=>**

return(relop,

LT)=otherother3.2詞法記號(hào)的描述與識(shí)別91011開始letter

other*標(biāo)識(shí)符和保留字的轉(zhuǎn)換圖letter或digitreturn(install_id(3.2詞法記號(hào)的描述與識(shí)別開始1213141617digitdigitdigit15digitdigitdigit18other.E+/digitotherother*19return(

install_num(

)

)無符號(hào)數(shù)的轉(zhuǎn)換圖num digit+

(.digit+)?

(E

(+

|

)?

digit+)?E3.2詞法記號(hào)的描述與識(shí)別2122開始delimother*空白的轉(zhuǎn)換圖delim

blank

|

tab

|

newlinews

delim+delim203.3

有限自動(dòng)機(jī)12開始a03.3.1不確定的有限自動(dòng)機(jī)（簡(jiǎn)稱NFA）一個(gè)數(shù)學(xué)模型，它包括:狀態(tài)集合S；輸入符號(hào)集合

；轉(zhuǎn)換函數(shù)move

:

S

(

{

})

P(S)；狀態(tài)s0是開始狀態(tài)；F

S是接受狀態(tài)集合。abb識(shí)別語言

(a|b)*ab的NFA3.3

有限自動(dòng)機(jī)12開始a0bb識(shí)別語言

(a|b)*ab的NFA輸

入

符

號(hào)ab0{0,

1}{0}1{2}2aNFA的轉(zhuǎn)換表狀

態(tài)3.3

有限自動(dòng)機(jī)例 識(shí)別aa*|bb*的NFA12開始0aabb343.3

有限自動(dòng)機(jī)3.3.2確定的有限自動(dòng)機(jī)（簡(jiǎn)稱DFA)一個(gè)數(shù)學(xué)模型，包括：狀態(tài)集合S；輸入字母表

；轉(zhuǎn)換函數(shù)move

:

S

S；唯一的初態(tài)

s

S；終態(tài)集合F

S；12開始a0abbab識(shí)別語言

(a|b)*ab的DFA3.3

有限自動(dòng)機(jī)例：識(shí)別

={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始41011010101010111000111000110003.3

有限自動(dòng)機(jī)0123開始4例：識(shí)別

={0,1}上能被能5整除的二進(jìn)制數(shù)03.3

有限自動(dòng)機(jī)0123開始41例：識(shí)別

={0,1}上能被能5整除的二進(jìn)制數(shù)03.3

有限自動(dòng)機(jī)0123開始41例：識(shí)別

={0,1}上能被能5整除的二進(jìn)制數(shù)003.3

有限自動(dòng)機(jī)0123開始41例：識(shí)別

={0,1}上能被能5整除的二進(jìn)制數(shù)0013.3

有限自動(dòng)機(jī)例：識(shí)別

={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始4100103.3

有限自動(dòng)機(jī)例：識(shí)別

={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始41001013.3

有限自動(dòng)機(jī)例：識(shí)別

={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始410001103.3

有限自動(dòng)機(jī)例：識(shí)別

={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始4100011013.3

有限自動(dòng)機(jī)例：識(shí)別

={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始41000110103.3

有限自動(dòng)機(jī)例：識(shí)別

={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始410010101013.3

有限自動(dòng)機(jī)例：識(shí)別

={0,1}上能被能5整除的二進(jìn)制數(shù)0123開始4100101010110102

=

10101112

=

7103.3

有限自動(dòng)機(jī)例：DFA，接受0和1的個(gè)數(shù)都是偶數(shù)的字符串31201111000

0開始偶0偶1奇0奇1奇0偶1偶0奇13.3

有限自動(dòng)機(jī)2開始0

13.3.3

NFA到DFA的變換子集構(gòu)造法DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合讀了輸入a1

a2

…an后，NFA能到達(dá)的所有狀態(tài)：s1,

s2,

…,

sk，則DFA到達(dá)狀態(tài){s1,

s2,

…,

sk}aba

b3.3

有限自動(dòng)機(jī)19開始0abab6782345狀態(tài)輸入符號(hào)ab3.3

有限自動(dòng)機(jī)19開始0abab6782345狀態(tài)輸入符號(hào)abAA

=

{0,

1,

2,

4,

7}3.3

有限自動(dòng)機(jī)19開始0abab6782345狀態(tài)輸入符號(hào)abABA

=

{0,

1,

2,

4,

7}B

=

{1,

2,

3,

4,

6,

7,

8}3.3

有限自動(dòng)機(jī)19開始0abab6782345狀態(tài)輸入符號(hào)abABBA

=

{0,

1,

2,

4,

7}B

=

{1,

2,

3,

4,

6,

7,

8}3.3

有限自動(dòng)機(jī)19開始0abab6782345狀態(tài)輸入符號(hào)abABCBA

=

{0,

1,

2,

4,

7}B

=

{1,

2,

3,

4,

6,

7,

8}C

=

{1,

2,

4,

5,

6,

7}3.3

有限自動(dòng)機(jī)19開始0abab6782345狀態(tài)輸入符號(hào)abABCBCA

=

{0,

1,

2,

4,

7}B

=

{1,

2,

3,

4,

6,

7,

8}C

=

{1,

2,

4,

5,

6,

7}3.3

有限自動(dòng)機(jī)19開始0abab6782345狀態(tài)輸入符號(hào)abABCBBCA

=

{0,

1,

2,

4,

7}B

=

{1,

2,

3,

4,

6,

7,

8}C

=

{1,

2,

4,

5,

6,

7}3.3

有限自動(dòng)機(jī)19開始0abab6782345狀態(tài)輸入符號(hào)abABCBBDCA

=

{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}3.3

有限自動(dòng)機(jī)19開始0abab6782345狀態(tài)輸入符號(hào)abABCBBDCDA

=

{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}3.3

有限自動(dòng)機(jī)19開始0abab6782345狀態(tài)輸入符號(hào)abABCBBDCBCDA

=

{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}3.3

有限自動(dòng)機(jī)19開始0abab6782345狀態(tài)輸入符號(hào)abABCBBDCBCDBCA

=

{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}3.3

有限自動(dòng)機(jī)開始a19開始0abab6782345輸入符號(hào)a

bbAB

CCB

bB

aDbACa

BBb

C

DDBa

C狀態(tài)3.3

有限自動(dòng)機(jī)BD開始aAabbabbCa12開始a0abbab19開始0abab6782345識(shí)別語言

(a|b)*ab的自動(dòng)機(jī)3.3

有限自動(dòng)機(jī)BD開始aAabbabbCa12開始a0abbab19開始0abab678234512開始a0bb識(shí)別語言

(a|b)*ab的自動(dòng)機(jī)a3.3

有限自動(dòng)機(jī)B開始aAabbaa,

bbDCaEb3.3.4

DFA的化簡(jiǎn)–死狀態(tài)左圖無須加死狀態(tài)，右圖加入死狀態(tài)E。BD開始aAabbabbCa3.3

有限自動(dòng)機(jī)BD開始aAabba可區(qū)別的狀態(tài)A和B是可區(qū)別的狀態(tài)

A和C是不可區(qū)別的狀態(tài)bbCa3.3

有限自動(dòng)機(jī)方法{A,

B,

C},

{D}move({A,

B,

C},

a}

=

{B}move({A,

B,

C},

b}

=

{C,

D}{A,

C},

{B},

{D}move({A,

C},

a}

=

{B}move({A,

C},

b}

=

{C}BD開始aAabbabbCa3.3

有限自動(dòng)機(jī)方法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開始aAabbabbCa12開始a0abbab3.4從正規(guī)式到有限自動(dòng)機(jī)從正規(guī)式建立識(shí)別器–從正規(guī)式構(gòu)造NFA（本節(jié)介紹）用語法制導(dǎo)的算法，它用正規(guī)式語法結(jié)構(gòu)來指導(dǎo)構(gòu)造過程。–把NFA變成DFA

（子集構(gòu)造法，已介紹）–將DFA化簡(jiǎn)（合并不可區(qū)別狀態(tài)，也已介紹）3.4從正規(guī)式到有限自動(dòng)機(jī)首先構(gòu)造識(shí)別 和字母表中一個(gè)符號(hào)的NFA開始識(shí)別正規(guī)式的NFAai

fif開始識(shí)別正規(guī)式a的NFA3.4從正規(guī)式到有限自動(dòng)機(jī)fi開始構(gòu)造識(shí)別主算符為選擇的正規(guī)式的NFAN

(s)N

(t)識(shí)別正規(guī)式s

|

t的NFA3.4從正規(guī)式到有限自動(dòng)機(jī)構(gòu)造識(shí)別主算符為連接的正規(guī)式的NFAiN

(s)f開始識(shí)別正規(guī)式st

的NFAN

(t)3.4從正規(guī)式到有限自動(dòng)機(jī)構(gòu)造識(shí)別主算符為閉包的正規(guī)式的NFAN

(s)f開始識(shí)別正規(guī)式s*

的NFAi3.4從正規(guī)式到有限自動(dòng)機(jī)對(duì)于加括號(hào)的正規(guī)式(s)，使用N(s)本身作為它的NFA。3.4從正規(guī)式到有限自動(dòng)機(jī)本方法產(chǎn)生的NFA有下列性質(zhì):N(r)的狀態(tài)數(shù)最多是r中符號(hào)和算符總數(shù)的兩倍。N(r)只有一個(gè)開始狀態(tài)和一個(gè)接受狀態(tài)，接受狀態(tài)沒有向外的轉(zhuǎn)換。–N(r)的每個(gè)狀態(tài)有一個(gè)用的符號(hào)標(biāo)記的指向其它結(jié)點(diǎn)的轉(zhuǎn)換，或者最多兩個(gè)指向其它結(jié)點(diǎn)的轉(zhuǎn)換。3.4從正規(guī)式到有限自動(dòng)機(jī)19開始0abab6782345r9r7r4r3r5*)(r1a|r2br6ar8b(a|b)*ab的分解3.4從正規(guī)式到有限自動(dòng)機(jī)19開始0abab6782345r9r7r4r3r5*)(r1a|r2br6ar8b(a|b)*ab的分解3.4從正規(guī)式到有限自動(dòng)機(jī)19開始0abab6782345r9r7r4r3r5*)(r1a|r2br6ar8b(a|b)*ab的分解3.4從正規(guī)式到有限自動(dòng)機(jī)19開始0abab6782345r9r7r4r3r5*)(r1a|r2br6ar8b(a|b)*ab的分解3.4從正規(guī)式到有限自動(dòng)機(jī)19開始0abab6782345r9r7r4r3r5*)(r1a|r2br6ar8b(a|b)*ab的分解3.4從正規(guī)式到有限自動(dòng)機(jī)19開始0abab6782345r9r7r4r3r5*)(r1a|r2br6ar8b(a|b)*ab的分解3.4從正規(guī)式到有限自動(dòng)機(jī)19開始0abab6782345r9r7r4r3r5*)(r1a|r2br6ar8b(a|b)*ab的分解3.4從正規(guī)式到有限自動(dòng)機(jī)2開始0

1(a|b)*ab的兩個(gè)NFA的比較aba

b19開始0abab67823453.4從正規(guī)式到有限自動(dòng)機(jī)小結(jié)：從正規(guī)式建立識(shí)別器的步驟–從正規(guī)式構(gòu)造NFA–把NFA變成DFA–將DFA化簡(jiǎn)存在其它辦法3.5

詞法分析器的生成器用Lex建立詞法分析器的步驟Lex編譯器Lex源程序lex.llex.yy.cC編譯器lex.yy.ca.outa.out輸入流記號(hào)序列3.5

詞法分析器的生成器Lex程序包括三個(gè)部分聲明％％翻譯規(guī)則％％輔助過程Lex程序的翻譯規(guī)則p1p2…pn{動(dòng)作1}{動(dòng)作2}…{動(dòng)作n}3.5

詞法分析器的生成器例---聲明部分%{/*

常量LT,LE,EQ,NE,GT,GE,WHILE,DO,ID,NUMBER,RELOP的定義*/%}/*正規(guī)定義*/[

\t

\n

]{delim}+[A

Za

z][0

9]{letter}({letter}|{digit})*delimwsletterdigitidnumber{digit}+(\

.{digit}+)?(E[+\

]?{digit}+)3.5

詞法分析器的生成器例---翻譯規(guī)則部分{ws}whiledo{id}{number}“

<

”“

<=

”“

=

”“

<>

”“

>

”“

>=

”{/*沒有動(dòng)作，也不返回*/}{return

(WHILE);}{return

(DO);}{yylval

=

install_id

(

);

return

(ID);}{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);}3.5

詞法分析器的生成器例---輔助過程部分install_

id

(

)

{/*

把詞法單元裝入符號(hào)表并返回指針。yytext指向該詞法單元的第一個(gè)字符，yyleng給出的它的長(zhǎng)度

*/}install_num

(

)

{/*類似上面的過程，但詞法單元不是標(biāo)識(shí)符而是數(shù)*/}本

章

要

點(diǎn)詞法分析器的作用和接口，用高級(jí)語言編寫詞法分析器等內(nèi)容，它們與詞法分析器的實(shí)現(xiàn)有關(guān)。掌握下面涉及的一些概念，它們之間轉(zhuǎn)換的技巧、方法或算法。非形式描述的語言

正規(guī)式正規(guī)式

NFA非形式描述的語言

NFANFADFADFA最簡(jiǎn)DFA–非形式描述的語言DFA（或最簡(jiǎn)DFA）例題1敘述下面的正規(guī)式描述的語言，并畫出接受該語言的最簡(jiǎn)DFA的狀態(tài)轉(zhuǎn)換圖。(1|01)*

0*–描述的語言是，所有不含子串001的0和1的串。３００１.１０start１２例題2a(a|b)(a|b)134567aabb用狀態(tài)轉(zhuǎn)換圖表示接收(a|b)的DFA。a2abbstart0例題2a(a|b)(a|b)134567aabb用狀態(tài)轉(zhuǎn)換圖表示接收(a|b)的DFA。a2abbstart0a例題2a(a|b)(a|b)134567aabb用狀態(tài)轉(zhuǎn)換圖表示接收(a|b)的DFA。a2abbstart0ba例題2a(a|b)(a|b)b134567aabb用狀態(tài)轉(zhuǎn)換圖表示接收(a|b)的DFA。a2abstart0baabbaab例題3寫出語言“所有相鄰數(shù)字都不相同的非空數(shù)字串”的正規(guī)定義。123031357106798035790123)

|

no_answer

(0

|

no_0

0

)

(no_0

0

)no_0

(1

|

no_0-1

1

)

(no_0-1

1

)(no_0

|(no_0-1

|)

|

no_1.

.

.no_0-8

9將這些正規(guī)定義逆序排列就是答案習(xí)

題2.4

(f)

(g)第一次

2.3,第二次2.7

(c)

(d),2.8(僅為2.8(c))，2.11修改算法2.4,

使之盡可能少用 轉(zhuǎn)換，并保持所產(chǎn)生的NFA只有一個(gè)接受狀態(tài)。第四章

語法分析詞法分析器記號(hào)取下一個(gè)記號(hào)源程序分析樹前端的其余部分分析器分析樹符號(hào)表本章內(nèi)容上下文無關(guān)文法自上而下分析和自下而上分析圍繞分析器的自動(dòng)生成展開4.1上下文無關(guān)文法4.1.1上下文無關(guān)文法的定義–正規(guī)式來定義一些簡(jiǎn)單的語言，能表示給定結(jié)構(gòu)的固定次數(shù)的重復(fù)或者沒有指定次數(shù)的重復(fù)。例：a

(ba)5,a

(ba)*–正規(guī)式不能用于描述配對(duì)或嵌套的結(jié)構(gòu)例：配對(duì)括號(hào)串的集合，{wcw

|

w是a和b的串}4.1上下文無關(guān)文法上下文無關(guān)文法是四元組（VT

,VN

,S,P）VT

:

終結(jié)符集合VN

:

非終結(jié)符集合S

:

開始符號(hào)P

:

產(chǎn)生式集合，

產(chǎn)生式形式

:

A例

(

{id,

+,

*,,

(,

)},

{expr,

op},

expr,

P

)exprexpr

(expr)idexpr

expr

op

exprexpr

exprop

+op

*4.1上下文無關(guān)文法例

(

{id,

+,

*,,

(,

)},

{expr,

op},

expr,

P

)exprexpr

(expr)idexpr

expr

op

exprexpr

exprop

+op

*簡(jiǎn)化表示E

|

idE

E

A

E

|

(E

)

|A

+

|

*4.1上下文無關(guān)文法4.1.2

推導(dǎo)–把產(chǎn)生式看成重寫規(guī)則，把符號(hào)串中的非終結(jié)符用其產(chǎn)生式右部的串來代替。E

E

+

E

|

E

*

E

|

(E

)

|E

(E)

(E

+

E)E

|

id(id

+

E)(id

+例E概念–上下文無關(guān)語言、等價(jià)的文法、句型記號(hào)S

*

、S+

w4.1上下文無關(guān)文法E

E

+

E

|

E

*

E

|

(E

)

|

E

|

id最左推導(dǎo)E

Elm

lm

lm(E)

(E

+

E)(id

+

E)lm

lm(id

+

id)最右推導(dǎo)（規(guī)范推導(dǎo)）E

E(E)rm

rm

rm(E

+

E)rm(E

+

id)rm(id

+

id)4.1上下文無關(guān)文法4.1.3分析樹E

EEE()EEE()EEEE+E()EEE+EidE()EE+EidEid4.1上下文無關(guān)文法4.1.3二義性E

E

*id

*EEEE

+

EE

*

E

+Eid

*E

+

Eid

*

E

+

Eid

*id

*id

+

Eid

+

idid

*

id

+

Eid

*

id

+

id4.1上下文無關(guān)文法4.1.3二義性E*E+EEidididE

E

*id

*EEEE

+

EE

*

E

+Eid

*E

+

Eid

*

E

+

Eid

*id

+

Eid

*

id

+

Eid

*Eid

+

idid

*

id

+

idEEidE*E+Eidid4.2

語言和文法文法的優(yōu)點(diǎn)–文法給出了精確的，易于理解的語法說明4.2

語言和文法文法的優(yōu)點(diǎn)–文法給出了精確的，易于理解的語法說明–自動(dòng)產(chǎn)生高效的分析器4.2

語言和文法文法的優(yōu)點(diǎn)–文法給出了精確的，易于理解的語法說明–自動(dòng)產(chǎn)生高效的分析器–可以給語言定義出層次結(jié)構(gòu)4.2

語言和文法文法的優(yōu)點(diǎn)–文法給出了精確的，易于理解的語法說明–自動(dòng)產(chǎn)生高效的分析器–可以給語言定義出層次結(jié)構(gòu)–以文法為基礎(chǔ)的語言的實(shí)現(xiàn)便于語言的修改4.2

語言和文法文法的優(yōu)點(diǎn)–文法給出了精確的，易于理解的語法說明–自動(dòng)產(chǎn)生高效的分析器–可以給語言定義出層次結(jié)構(gòu)–以文法為基礎(chǔ)的語言的實(shí)現(xiàn)便于語言的修改文法的問題–文法只能描述編程語言的大部分語法4.2

語言和文法4.2.1

正規(guī)式和上下文無關(guān)文法的比較正規(guī)式(a|b)*ab4.2

語言和文法4.2.1

正規(guī)式和上下文無關(guān)文法的比較正規(guī)式(a|b)*ab12開始a0abb4.2

語言和文法4.2.1

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

a

A0

|

b

A0

|

a

A1

A1

b

A2A212開始a0abb4.2

語言和文法4.2.2分離詞法分析器理由為什么要用正規(guī)式定義詞法–詞法規(guī)則非常簡(jiǎn)單，不必用上下文無關(guān)文法。4.2

語言和文法4.2.2分離詞法分析器理由為什么要用正規(guī)式定義詞法–詞法規(guī)則非常簡(jiǎn)單，不必用上下文無關(guān)文法。–對(duì)于詞法記號(hào)，正規(guī)式描述簡(jiǎn)潔且易于理解。4.2

語言和文法4.2.2分離詞法分析器理由為什么要用正規(guī)式定義詞法–詞法規(guī)則非常簡(jiǎn)單，不必用上下文無關(guān)文法。–對(duì)于詞法記號(hào)，正規(guī)式描述簡(jiǎn)潔且易于理解。–從正規(guī)式構(gòu)造出的詞法分析器效率高。4.2

語言和文法把詞法分析從語法分析中分離出來的理由–簡(jiǎn)化設(shè)計(jì)4.2

語言和文法把詞法分析從語法分析中分離出來的理由–簡(jiǎn)化設(shè)計(jì)–編譯器的效率會(huì)改進(jìn)4.2

語言和文法把詞法分析從語法分析中分離出來的理由–簡(jiǎn)化設(shè)計(jì)–編譯器的效率會(huì)改進(jìn)–編譯器的可移植性加強(qiáng)4.2

語言和文法把詞法分析從語法分析中分離出來的理由–簡(jiǎn)化設(shè)計(jì)–編譯器的效率會(huì)改進(jìn)–編譯器的可移植性加強(qiáng)–便于編譯器前端的模塊劃分4.2

語言和文法4.2.3

驗(yàn)證文法產(chǎn)生的語言G

:S

(S

)S

|

L(G)=配對(duì)的括號(hào)串的集合4.2

語言和文法4.2.3

驗(yàn)證文法產(chǎn)生的語言G

:S

(S

)S

|

L(G)=配對(duì)的括號(hào)串的集合按推導(dǎo)步數(shù)進(jìn)行歸納：推出的是配對(duì)括號(hào)串4.2

語言和文法4.2.3

驗(yàn)證文法產(chǎn)生的語言G

:S

(S

)S

|

L(G)=配對(duì)的括號(hào)串的集合按推導(dǎo)步數(shù)進(jìn)行歸納：推出的是配對(duì)括號(hào)串–歸納基礎(chǔ)：S歸納假設(shè)：少于n步的推導(dǎo)都產(chǎn)生配對(duì)的括號(hào)串歸納步驟：n步的最左推導(dǎo)如下：S

(S

)S

*

(x)

S

*

(x)

y4.2

語言和文法4.2.3

驗(yàn)證文法產(chǎn)生的語言G

:S

(S

)S

|

L(G)=配對(duì)的括號(hào)串的集合按串長(zhǎng)進(jìn)行歸納：配對(duì)括號(hào)串可由S推出4.2

語言和文法4.2.3

驗(yàn)證文法產(chǎn)生的語言G

:S

(S

)S

|

L(G)=配對(duì)的括號(hào)串的集合按串長(zhǎng)進(jìn)行歸納：配對(duì)括號(hào)串可由S推出–歸納基礎(chǔ)：S歸納假設(shè)：長(zhǎng)度小于2n的都可以從S推導(dǎo)出來歸納步驟：考慮長(zhǎng)度為2n(n

1)的w

=

(x)

yS

(S

)S

*

(x)

S

*

(x)

y4.2

語言和文法4.2.4

適當(dāng)?shù)谋磉_(dá)式文法用一種層次觀點(diǎn)看待表達(dá)式

id

*

id

*(id+id)+id

*

id+id4.2

語言和文法4.2.4

適當(dāng)?shù)谋磉_(dá)式文法用一種層次觀點(diǎn)看待表達(dá)式

id

*

id

*(id+id)+id

*

id+id

id

*

id

*

(id+id)4.2

語言和文法4.2.4

適當(dāng)?shù)谋磉_(dá)式文法用一種層次觀點(diǎn)看待表達(dá)式

id

*

id

*(id+id)+id

*

id+id

id

*

id

*

(id+id)文法expr

expr

+

term

|

term4.2

語言和文法4.2.4

適當(dāng)?shù)谋磉_(dá)式文法用一種層次觀點(diǎn)看待表達(dá)式

id

*

id

*(id+id)+id

*

id+id

id

*

id

*

(id+id)文法exprtermexpr

+

term

|

term

term

*

factor

|

factor4.2

語言和文法4.2.4

適當(dāng)?shù)谋磉_(dá)式文法用一種層次觀點(diǎn)看待表達(dá)式

id

*

id

*(id+id)+id

*

id+id

id

*

id

*

(id+id)文法exprtermfactorexpr

+

term

|

termterm

*

factor

|

factorid

|

(expr)4.2

語言和文法exprtermfactorexpr

+

term

|

termterm

*

factor

|

factorid

|

(expr)exprtermfactoridterm*termfactorfactor

idid*expridexprtermididterm*+termfactor

factorfactorid

*

id

*

id

和

id

+

id

*

id

的分析樹4.2

語言和文法4.2.5消除二義性stmtif

expr

then

stmt|

if

expr

then

stmt

else

stmt|

other句型：if

expr

then

if

expr

then

stmt

else

s4.2

語言和文法4.2.5消除二義性stmtif

expr

then

stmt|

if

expr

then

stmt

else

stmt|

other句型：if

expr

then

if

expr

then

stmt

else

st兩個(gè)最左推導(dǎo)：stmtif

expr

then

stmtif

expr

then

if

expr

then

stmt

else

s4.2

語言和文法4.2.5消除二義性stmtif

expr

then

stmt|

if

expr

then

stmt

else

stmt|

other句型：if

expr

then

if

expr

then

stmt

else

st兩個(gè)最左推導(dǎo)：stmtstmtif

expr

then

stmtif

expr

then

if

expr

then

stmt

else

sif

expr

then

stmt

else

stmtif

expr

then

if

expr

then

stmt

else

s4.2

語言和文法無二義的文法stmtmatched

_stmt|

unmatched_stmtmatched_stmtif

expr

then

matched_stmtelse

matched_stmt|

otherunmatched_stmt

if

expr

then

stmt|

if

expr

then

matched_stmtelse

unmatched_stmt4.2

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

+Aa4.2

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

+Aa直接左遞歸–串的特點(diǎn)A

Aa

|bba

.

.

.

a4.2

語言和文法4.2.6消除左遞歸文法左遞歸A+Aa直接左遞歸AAa

|b–

串的特點(diǎn)

ba

.

.

.

a消除直接左遞歸Ab

AAa

A|4.2

語言和文法例算術(shù)表達(dá)文法EE

+

T

|

T（

T

+

T

.

.

.

+

T

）TT

*

F

|

F（

F

*

F

.

.

.

*

F

）F(

E

)

|

id4.2

語言和文法例算術(shù)表達(dá)文法EE

+

T

|

T（

T

+

T

.

.

.

+

T

）TT

*

F

|

F（

F

*

F

.

.

.

*

F

）F(

E

)

|

id消除左遞歸后文法ETEE+

TE|TFTT*

F

T|F

(

E

)

|

id4.2

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

Aa

|

bA

Sd

|4.2

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

Aa

|

bA

Sd

|先變換成直接左遞歸S

Aa

|

bA

Aad

|

bd

|4.2

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

Aa

|

bA

Sd

|先變換成直接左遞歸S

Aa

|

bA

Aad

|

bd

|再消除左遞歸S

Aa

|

bA

bd

A

|

AA

adA

|4.2

語言和文法4.2.7

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

1

|24.2

語言和文法4.2.7

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

1

|2A提左因子A

A1

|24.2

語言和文法例 懸空else的文法stmtif

expr

then

stmt

else

stmt|

if

expr

then

stmt|

other4.2

語言和文法例 懸空else的文法stmtif

expr

then

stmt

else

stmt|

if

expr

then

stmt|

other提左因子stmtif

expr

then

stmt

optional_else_|

otheroptional_else_part

else

stmt|4.2

語言和文法4.2.8

非上下文無關(guān)的語言結(jié)構(gòu)L1

={wcw

|

w屬于(a

|

b)*}–

標(biāo)識(shí)符的聲明應(yīng)先于其引用的抽象4.2

語言和文法4.2.8

非上下文無關(guān)的語言結(jié)構(gòu)L1

={wcw

|

w屬于(a

|

b)*}–

標(biāo)識(shí)符的聲明應(yīng)先于其引用的抽象L2

=

{anbmcndm

|

n

0,

m

0}–形參個(gè)數(shù)和實(shí)參個(gè)數(shù)應(yīng)該相同的抽象4.2

語言和文法4.2.8

非上下文無關(guān)的語言結(jié)構(gòu)L1

={wcw

|

w屬于(a

|

b)*}–

標(biāo)識(shí)符的聲明應(yīng)先于其引用的抽象L2

=

{anbmcndm

|

n

0,

m

0}–形參個(gè)數(shù)和實(shí)參個(gè)數(shù)應(yīng)該相同的抽象L3

=

{anbncn

|

n

0}–早先排版描述的一個(gè)現(xiàn)象的抽象4.2

語言和文法L1

=

{wcwR

|

w

(a|b)*}S

aSa

|

bSb

|

c4.2

語言和文法L1

=

{wcwR

|

w

(a|b)*}L2S

aSa

|

bSb

|

c=

{a

nbmcmdn

|

n

1,

m

1

}S

aSd

|

aAdA

bAc

|

bc4.2

語言和文法L1

=

{wcwR

|

w

(a|b)*}L2L

2S

aSa

|

bSb

|

c=

{a

nbmcmdn

|

n

1,

m

1

}S

aSd

|

aAdA

bAc

|

bc=

{a

nbncmdm

|

n

1，m

1

}S

ABaAb

|

abcBd

|

cd4.2

語言和文法L3

={a

nb

n

|

n

1

}S

aSb

|

ab4.2

語言和文法L3

={a

nb

n

|

n

1

}S

aSb

|

abL3

是不能用正規(guī)式描述的語言的一個(gè)范例4.2

語言和文法L3

={a

nb

n

|

n

1

}S

aSb

|

abL3

是不能用正規(guī)式描述的語言的一個(gè)范例–

若存在接受L3

的DFA

D，狀態(tài)數(shù)為k個(gè)。4.2

語言和文法L3

={a

nb

n

|

n

1

}S

aSb

|

abL3

是不能用正規(guī)式描述的語言的一個(gè)范例若存在接受L3

的DFA

D，狀態(tài)數(shù)為k個(gè)。設(shè)D讀完

,

a,

aa,

…,

ak

分別到達(dá)狀態(tài)s0,

s1,

…,4.2

語言和文法L3

={a

nb

n

|

n

1

}S

aSb

|

abL3

是不能用正規(guī)式描述的語言的一個(gè)范例若存在接受L3

的DFA

D，狀態(tài)數(shù)為k個(gè)。設(shè)D讀完

,

a,

aa,

…,

ak

分別到達(dá)狀態(tài)s0,

s1,

…,–至少有兩個(gè)狀態(tài)相同，例如是si和sj，則ajbi屬于L34.2

語言和文法L3

={a

nb

n

|

n

1

}S

aSb

|

abL3

是不能用正規(guī)式描述的語言的一個(gè)范例若存在接受L3

的DFA

D，狀態(tài)數(shù)為k個(gè)。設(shè)D讀完

,

a,

aa,

…,

ak

分別到達(dá)狀態(tài)s0,

s1,

…,–至少有兩個(gè)狀態(tài)相同，例如是si和sj，則ajbi屬于L3sifs0標(biāo)記為ai的路徑…。。。標(biāo)記為aji的路徑…。。。標(biāo)記為bi的路徑…。。。4.2

語言和文法4.2.9

形式語言鳥瞰文法G

=(VT

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

，

,(VN

VT)*,

|4.2

語言和文法4.2.9

形式語言鳥瞰文法G

=(VT

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

，

,(VN

VT)*,

|短語文法4.2

語言和文法4.2.9

形式語言鳥瞰文法G

=(VT

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