編譯方法、技術(shù)與實(shí)踐課件：詞法分析與語(yǔ)法分析（一）

詞法分析和語(yǔ)法分析(一)?詞法分析概要?正則表達(dá)式?有限狀態(tài)自動(dòng)機(jī)?從NFA到DFA的轉(zhuǎn)換?狀態(tài)最小化算法提綱Oposition=initial+rate*60<id,1>

<=,>

<id,2>

<+,>

<id,3>

<*,>

<number,

4>

詞法分析

一個(gè)實(shí)例?詞法分析是讀入源程序的輸入字符、將它們組成詞素，生成并輸出一個(gè)詞法單元序列，每個(gè)詞法單元對(duì)應(yīng)于一個(gè)詞素?常見(jiàn)的做法O

由語(yǔ)法分析器調(diào)用，需要的時(shí)候不斷讀取、生成詞法單元O

可以避免額外的輸入輸出?在識(shí)別出詞法單元之外，還會(huì)完成一些不需要生成詞法單元的簡(jiǎn)單處理，比如刪除注釋、將多個(gè)連續(xù)的空白字符壓縮成一個(gè)字符詞法分析器作用等?詞法單元(Token)：O

包含單元名(Token-name)和可選的屬性值(attribute-value)O

單元名是表示某種詞法單位抽象符號(hào)。語(yǔ)法分析器通過(guò)單元名即可確定詞法單元序列的結(jié)構(gòu)。?詞素(Lexeme)O

源程序中的字符序列，它和某類詞法單元的模式匹配，被詞法分析器識(shí)別為該詞法單元的實(shí)例。詞法分析相關(guān)概念詞法單元示例?一個(gè)模式匹配多個(gè)詞素時(shí)，必須通過(guò)屬性來(lái)傳遞附加的信息。屬性值將被用于語(yǔ)義分析、代碼生成等階段。?不同的目的需要不同的屬性。因此，屬性值通常是一個(gè)結(jié)構(gòu)化數(shù)據(jù)。?詞法單元id的屬性O(shè)

詞素、類型、第一次出現(xiàn)的位置、

…詞法單元的屬性詞法單元示例(名和屬性值)詞法單元模式(Pattern)?詞法單元對(duì)應(yīng)的詞素可能

具有的形式?可以用正則表達(dá)式來(lái)表示第一步：如何描述詞素？詞素Specification?詞法分析概要?正則表達(dá)式?有限狀態(tài)自動(dòng)機(jī)?從NFA到DFA的轉(zhuǎn)換?狀態(tài)最小化算法提綱?字母表：一個(gè)有限的符號(hào)集合O

二進(jìn)制{0，1}O

ASCIIO

UnicodeO

典型的字母表包括字母、數(shù)位和標(biāo)點(diǎn)符號(hào)?串：字母表中符號(hào)組成的一個(gè)有窮序列O

串s的長(zhǎng)度|s|O

空串ε，長(zhǎng)度為0的串?語(yǔ)言：給定字母表上一個(gè)任意的可數(shù)的串的集合O

語(yǔ)法正確的C程序的集合，英語(yǔ)，漢語(yǔ)相關(guān)概念?和串有關(guān)的術(shù)語(yǔ)(banana)O

前綴：從串的尾部刪除0個(gè)或多個(gè)符號(hào)后得到的串(ban、banana

、ε)O

后綴：從串的開(kāi)始處刪除0個(gè)或多個(gè)符號(hào)后得到的串(nana、banana、ε)O

子串：刪除串的某個(gè)前綴和某個(gè)后綴得到的串(banana、nan

、ε)O

真前綴、真后綴、真子串：既不等于原串，也不等于空串的前綴、后綴、子串O

子序列：從原串中刪除0個(gè)或者多個(gè)符號(hào)后得到的串(baan)相關(guān)概念?串的運(yùn)算O

連接(concatenation)：x和y的連接時(shí)把y附加

到x的后面形成的串，記作xy。?x=dog，y=house，xy=doghouseO

指數(shù)運(yùn)算(冪運(yùn)算)：s0=ε，s1=s

，si=si-

1s；?x=dog，x0=ε，x1=dog，x3=dogdogdog相關(guān)概念?語(yǔ)言上的運(yùn)算語(yǔ)言：串的集合相關(guān)概念L+

=

U

1

LiL={A,B,……,Z,a,b,……,z}D={0,1,……,9}LUD:{A,B,……,Z,a,b,……,z,0,1,……,9}LD

：520個(gè)長(zhǎng)度為2的串的集合L4

：所有由四個(gè)字母構(gòu)成的串的集合L*：所有字母構(gòu)成的集合，包括ε。L(L

U

D)*:D+

:語(yǔ)言的一些實(shí)例?正則表達(dá)式O

一種描述詞素模式的重要表示方法?正則表達(dá)式可以高效、簡(jiǎn)潔地描述處理詞法單元時(shí)用到的模

式類型?可以描述所有通過(guò)對(duì)某個(gè)字母表上的符號(hào)應(yīng)用運(yùn)算符而得到

的語(yǔ)言。其定義的集合叫做正則集合(regular

set)?每個(gè)正則表達(dá)式r可以描述一個(gè)語(yǔ)言L(r)，也即其定義的正則集合?例如，C語(yǔ)言標(biāo)識(shí)符的語(yǔ)言，可以用如下正則表達(dá)式來(lái)表示：letter_(letter_|digit)*正則表達(dá)式重要?正則表達(dá)式可以由較小的正則表達(dá)式遞歸構(gòu)建(字母表Σ上的正則表達(dá)式的定義)O

基本部分?ε是一個(gè)正則表達(dá)式，L(ε)={ε}?如果a是Σ上的一個(gè)符號(hào)，那么a是正則表達(dá)式，L(a)={a}O

歸納步驟：?選擇：(r)|(s)，L((r)|(s))=L(r)U

L(s)；?連接：(r)(s)，L((r)(s))=L(r)L(s)；?閉包：(r)*，L((r)*)=(L(r))*；?括號(hào)：(r)，L((r))=L(r)?運(yùn)算的優(yōu)先級(jí)：*>連接符>|(a)|((b)*(c))可以改寫(xiě)為a|b*c正則表達(dá)式?Σ={a,b}?L(a|b)={a,b}?L((a|b)(a|b))={aa,ab,ba,bb}?L(a*)={ε,a,aa,aaa,aaaa,……}?L((a|b)*)={ε,a,b,aa,ab,ba,bb,aaa,aab,……}?L(a|a*b)={a,b,ab,aab,aaab,…}?P76,

練習(xí)3.2.2O

((ε|a)b*)*正則表達(dá)式實(shí)例正則表達(dá)式的性質(zhì)?等價(jià)性O(shè)

如果兩個(gè)正則表達(dá)式r和s表示同樣的語(yǔ)言，則r=s?代數(shù)定律?對(duì)正則表達(dá)式命名，使表示簡(jiǎn)潔d1

→r1d2

→r2...dn

→

rn?各個(gè)di不在字母表中，且名字都不同?每個(gè)ri都是{d1

,d2

,…,di-

1

}上的正則表

達(dá)式

正則定義?各個(gè)di在Σ上的正則表達(dá)式如下：O

d1

的正則表達(dá)式即r1O

將r2

中的d1

替換為r1

，得到d2

的正則表達(dá)式O

………

…O

將ri

中的d1,d2,…,di-

1

替換為各自的正則表達(dá)式，得到di

的正則表達(dá)式?注意：替換的時(shí)候不能破壞替換進(jìn)去的di

的完整性正則定義?C語(yǔ)言的標(biāo)識(shí)符集合letter

→A|B|…|Z|a|b|…|z|_digit

→0|1|…|

9id

→letter(letter|digit)*正則定義實(shí)例?Pascal無(wú)符號(hào)數(shù)集合，例如：1946,11.28,

63.6E8,1.99E?6digit

→0|1|…|

9digits

→digit

digit*optional_fraction

→.digits|coptional_exponent

→(E(+|?|

c)digits)|

cnum→digitsoptional_fractionoptional_exponent正則定義實(shí)例?基本運(yùn)算符：并連接閉包?

擴(kuò)展運(yùn)算符O一個(gè)或多個(gè)：r+

,等價(jià)于rr*O零個(gè)或一個(gè)：r?，等價(jià)于3|rO字符類[abc]等價(jià)于a|b|c,[a-z]等價(jià)于a|b|…|z?

前面兩個(gè)例子的簡(jiǎn)化表示正則表達(dá)式的擴(kuò)展?字母表{a,b}上以aa結(jié)尾的所有字符串。?能被4整除的所有二進(jìn)制數(shù)。練習(xí)?正則表達(dá)式是一種描述手段，通常用來(lái)描述程序語(yǔ)言的詞法符號(hào)。?很多編輯器支持正則表達(dá)式?工具GREP附注正則表達(dá)式可以由較小的正

則表達(dá)式遞歸構(gòu)建?如何定義你的語(yǔ)言？有關(guān)實(shí)驗(yàn)詞素詞法單元狀態(tài)轉(zhuǎn)換圖、有限自動(dòng)機(jī)識(shí)別一個(gè)串是否屬于某個(gè)正則集

Implementation

第二步：如何識(shí)別詞法單元？?詞法分析概要?正則表達(dá)式?有限狀態(tài)自動(dòng)機(jī)?從NFA到DFA的轉(zhuǎn)換?狀態(tài)最小化算法提綱?詞法分析器要求能夠檢查輸入字符串，

在前綴中找出和某個(gè)模式匹配的詞素O

首先通過(guò)正則定義來(lái)描述各種詞法單元的模式O

定義ws→(blank|tab|newline)+來(lái)消除空白?詞法分析器識(shí)別到這個(gè)模式時(shí)，不返回詞法單元，繼續(xù)識(shí)別其它模式詞法單元的識(shí)別?狀態(tài)轉(zhuǎn)換圖是詞法分析器的重要組件之一?可以將正則表達(dá)式轉(zhuǎn)換成狀態(tài)轉(zhuǎn)換圖?狀態(tài)轉(zhuǎn)換圖(transition

diagram)O

狀態(tài)(state)：表示在識(shí)別詞素的過(guò)程中可能出現(xiàn)的情況?狀態(tài)看作是已處理部分的總結(jié)?某些狀態(tài)為接受狀態(tài)或最終狀態(tài)，表明已經(jīng)找到詞素?加上*的接受狀態(tài)表示最后讀入的符號(hào)不在詞素中?開(kāi)始狀態(tài)(初始狀態(tài))：用start邊表示O

邊(edge)：從一個(gè)狀態(tài)指向另一個(gè)狀態(tài)；邊的標(biāo)號(hào)是一個(gè)或者多個(gè)符號(hào)?如果當(dāng)前符號(hào)為s，下一個(gè)輸入符號(hào)為a，就沿著從s離開(kāi)，

標(biāo)號(hào)為a的邊到達(dá)下一個(gè)狀態(tài)狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖的例子?在很多程序設(shè)計(jì)語(yǔ)言中，保留字也符合標(biāo)識(shí)符的模式，識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖也會(huì)識(shí)別保留字?解決方法O

在符號(hào)表中預(yù)先填寫(xiě)保留字，并指明它們不是普通標(biāo)識(shí)符O

為關(guān)鍵字/保留字建立單獨(dú)的狀態(tài)轉(zhuǎn)換圖。并設(shè)定保留字的優(yōu)先級(jí)高于標(biāo)識(shí)符保留字和標(biāo)識(shí)符的識(shí)別其它的狀態(tài)轉(zhuǎn)換圖其它的狀態(tài)轉(zhuǎn)換圖?Finite-state

machines

can

model

a

large

number

of

problems,

among

which

are

electronic

design

automation,

communication

protocol

design,

parsing

and

other

engineering

applications.

In

biology

and

artificial

intelligence

research,

state

machines

or

hierarchies

of

state

machines

are

sometimes

used

to

describe

neurological

systems,

and

in

linguistics

they

can

be

used

to

describe

the

grammars

of

natural

languages.Finite-statemachines?本質(zhì)上等價(jià)于狀態(tài)轉(zhuǎn)換圖?區(qū)別在于：O

自動(dòng)機(jī)是識(shí)別器，對(duì)每個(gè)輸入串回答yes

orno?分為兩類O

不確定的有窮自動(dòng)機(jī)(Nondeterministic

FiniteAutomaton

，NFA)O

確定的有窮狀態(tài)自動(dòng)機(jī)(Deterministic

FiniteAutomaton

，DFA)重要有窮自動(dòng)機(jī)O

NFA:可以有邊的標(biāo)號(hào)是εO

DFA:沒(méi)有標(biāo)記為ε的邊?相同：都可以識(shí)別正則語(yǔ)言，兩者之間存在等價(jià)性?不同：O

NFA:一個(gè)符號(hào)標(biāo)記離開(kāi)同一狀態(tài)的多條邊O

DFA:對(duì)于每個(gè)狀態(tài)和字母表中的每個(gè)字符，有

且僅有一條離開(kāi)該狀態(tài)、以該符合為標(biāo)號(hào)的邊不確定vs.確定?NFA由以下幾部分組成O

一個(gè)有窮的狀態(tài)集合SO

一個(gè)輸入符號(hào)集合Σ

(input

alphabet)O

轉(zhuǎn)換函數(shù)(transition

function)對(duì)于每個(gè)狀態(tài)和

Σ

U

{ε}中的符號(hào)，給出相應(yīng)的后繼狀態(tài)集合O

一個(gè)狀態(tài)S0被指定為開(kāi)始狀態(tài)/初始狀態(tài)O

S的一個(gè)子集F被指定為接受狀態(tài)不確定的有窮自動(dòng)機(jī)(NFA)?狀態(tài)集合S={0,1,2,3}?開(kāi)始狀態(tài)0?接受狀態(tài)集合{3}?轉(zhuǎn)換函數(shù)：O

(0,a)→{0,1}(0,b)→{0}(1,b)→2

(2,b)→3NFA的例子?NFA可以表示為一個(gè)轉(zhuǎn)換表O

表的各行對(duì)應(yīng)于狀態(tài)O

各列對(duì)應(yīng)于輸入符號(hào)和εO

表中的元素表示給定狀態(tài)在給定輸入下的后繼狀態(tài)

轉(zhuǎn)換表?一個(gè)NFA接受輸入字符串x，當(dāng)且僅當(dāng)對(duì)應(yīng)的

轉(zhuǎn)換圖中存在一條從開(kāi)始狀態(tài)到某個(gè)接受狀態(tài)的路徑，使得該路徑中各條邊上的標(biāo)號(hào)組成符號(hào)串x

(路徑中可能包含ε邊)?下圖對(duì)應(yīng)的NFA能夠接受aabb注意：只要存在從開(kāi)始狀態(tài)到接受狀態(tài)的路徑，符號(hào)串就認(rèn) 為被NFA接受

自動(dòng)機(jī)對(duì)輸入字符串的接受?由一個(gè)NFA

A定義(接受)的語(yǔ)言是從開(kāi)始狀態(tài)

到某個(gè)接受狀態(tài)的所有路徑上的符號(hào)串集合，稱自動(dòng)機(jī)與語(yǔ)言相應(yīng)的語(yǔ)言：L(aa*|bb*)為L(zhǎng)(A)?一個(gè)NFA被稱為DFA，如果O

沒(méi)有ε之上的轉(zhuǎn)換動(dòng)作O

對(duì)于每個(gè)狀態(tài)s和每個(gè)輸入符號(hào)a，有且只有一條標(biāo)號(hào)為a的邊?可以高效判斷一個(gè)串能否被一個(gè)DFA接受?每個(gè)NFA都有一個(gè)等價(jià)的DFA，即它們接

受同樣的語(yǔ)言確定有窮自動(dòng)機(jī)(DFA)?假設(shè)輸入符號(hào)就是字符串中的符號(hào)；?Nextchar讀入下一個(gè)字符(符號(hào))?move給出了離開(kāi)s，標(biāo)號(hào)為c的邊的目標(biāo)狀態(tài)如何模擬NFADFA的模擬?假設(shè)輸入為ababb，那么進(jìn)入的狀態(tài)序列

為0,1,2,1,2,3，返回yesDFA的例子詞素詞法單元我們已有的工具：1.RE2.DFA3.NFA?正則表達(dá)式可以簡(jiǎn)潔、精確地描述詞法單元的模式?進(jìn)行模式匹配時(shí)，模擬DFA的執(zhí)行比模擬NFA更為簡(jiǎn)單有效O

ε的模擬，難O

不確定性的模擬，難?因此，需要將正則表達(dá)式轉(zhuǎn)換為DFA?步驟：O

正則表達(dá)式到NFAO

NFA到DFA正則表達(dá)式到自動(dòng)機(jī)?詞法分析概要?正則表達(dá)式?有限狀態(tài)自動(dòng)機(jī)?從NFA到DFA的轉(zhuǎn)換?狀態(tài)最小化算法提綱?對(duì)NFA的模擬往往不如對(duì)DFA的模擬直接，

除非轉(zhuǎn)換花費(fèi)更多的時(shí)間?基本思想：DFA每個(gè)狀態(tài)<→NFA一個(gè)狀態(tài)集O“并行地模擬”NFA在遇到一個(gè)給定輸入串時(shí)可能執(zhí)行的所

有動(dòng)作O

構(gòu)造得到的DFA的每個(gè)狀態(tài)和NFA的狀態(tài)子集對(duì)應(yīng)O

DFA讀入a1

,a2

,…,an后到達(dá)的狀態(tài)對(duì)應(yīng)于從NFA開(kāi)始狀態(tài)出發(fā)沿著a1

,a2

,…,an可能到達(dá)的狀態(tài)集合?

理論上，最壞情況下DFA的狀態(tài)個(gè)數(shù)會(huì)是NFA狀態(tài)個(gè)數(shù)的指數(shù)多個(gè)。但是對(duì)于大部分應(yīng)用，NFA和相應(yīng)的DFA的狀態(tài)數(shù)量大致相同NFA轉(zhuǎn)換成DFA-子集構(gòu)造法?輸入：一個(gè)NFAN?輸出：一個(gè)接受相同語(yǔ)言的DFADs表示N中的單個(gè)狀態(tài)，T代表N的一個(gè)狀態(tài)集NFA轉(zhuǎn)換成DFA-子集構(gòu)造法?D的開(kāi)始狀態(tài)是ε-closure(s0)，D的接受狀態(tài)是所有至少包含了N的一個(gè)接受狀態(tài)的狀態(tài)集合。NFA轉(zhuǎn)換成DFA-子集構(gòu)造法?對(duì)NFA的任何狀態(tài)集合ε-closure(T)的計(jì)算?

一個(gè)圖搜索過(guò)程N(yùn)FA轉(zhuǎn)換成DFA-子集構(gòu)造法?A：=3-closure(0)={0,1,2,4,7}?B

：Dtran[A,a]=3-closure(move(A,a))=3-closure({3,8})={1,2,3,4,6,7,8}?C：Dtran[A,b]=3-closure(move(A,b))=3-closure({5})={1,2,4,5,6,7}?D：Dtran[B,b]=3-closure(move(B,b))={1,2,4,5,6,7,9}?……?E:Dtran[D,b]=3-closure(move(B,b))={1,2,4,5,6,7,10}NFA到DFA轉(zhuǎn)換的示例?開(kāi)始狀態(tài)：A?接受狀態(tài)：

ENFA到DFA轉(zhuǎn)換的示例?輸入：一個(gè)以文件結(jié)束符eof結(jié)尾的輸入串x，一個(gè)NFA

N，其開(kāi)始狀態(tài)是S0

，接受狀態(tài)集為F，轉(zhuǎn)換函數(shù)為move?輸出：如果N接受x，返回yes，否則返回no對(duì)NFA的運(yùn)行進(jìn)行模擬:子集構(gòu)造法?輸入：字母表Σ上的一個(gè)正則表達(dá)式r?輸出：一個(gè)接受L(r)的NFAN?基本思想O

根據(jù)正則表達(dá)式的遞歸定義，按照正則表達(dá)式的結(jié)構(gòu)遞歸地構(gòu)造出相應(yīng)的NFAO

算法分成兩個(gè)部分：?基本規(guī)則處理ε和單符號(hào)的情況?對(duì)于每個(gè)正則表達(dá)式的運(yùn)算，建立構(gòu)造相應(yīng)NFA正則表達(dá)式到NFA的方法?基本規(guī)則：O

表達(dá)式ε，轉(zhuǎn)換算法(1)表達(dá)式a，O?歸納規(guī)則O

正則表達(dá)式s和t的NFA分別是N(s)和N(t)Or=s|r，r的NFA

N(r)轉(zhuǎn)換算法(2)?歸納規(guī)則O正則表達(dá)式r=st，N(r)轉(zhuǎn)換算法(2)?歸納規(guī)則O

正則表達(dá)式r=s*,

N(r)轉(zhuǎn)換算法(3)O

r=(s),

N(r)=N(s)?正則表達(dá)式(a|b)*abb?第一個(gè)a對(duì)應(yīng)的NFA?第一個(gè)b對(duì)應(yīng)的NFA正則表達(dá)式到NFA的例子(1)正則表達(dá)式到NFA的例子(2)?第二個(gè)a的NFA?(a|b)的NFA正則表達(dá)式到NFA的例子(3)?(a|b)*的NFA?字母表{x,y}上以x開(kāi)頭和結(jié)尾的任意串。?用正則表達(dá)式表示字母表{a,b}上由a、b組成，且不連續(xù)出現(xiàn)兩個(gè)a的所有句子的集合，并給出接受該語(yǔ)言的DFA。練習(xí)?詞法分析概要?正則表達(dá)式?有限狀態(tài)自動(dòng)機(jī)?從NFA到DFA的轉(zhuǎn)換?狀態(tài)最小化算法提綱?DFA化簡(jiǎn)：