編譯方法、技術(shù)與實(shí)踐課件：詞法分析和語法分析

詞法分析和語法分析

詞法分析和語法分析(一)?詞法分析概要?正則表達(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è)詞素?常見的做法O

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

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

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

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

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

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

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

具有的形式?可以用正則表達(dá)式來表示第一步：如何描述詞素？詞素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的長度|s|O

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

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

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

、ε)O

后綴：從串的開始處刪除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ùn)算語言：串的集合相關(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è)長度為2的串的集合L4

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

U

D)*:D+

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

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

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

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

set)?每個(gè)正則表達(dá)式r可以描述一個(gè)語言L(r)，也即其定義的正則集合?例如，C語言標(biāo)識(shí)符的語言，可以用如下正則表達(dá)式來表示：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))可以改寫為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表示同樣的語言，則r=s?代數(shù)定律?對(duì)正則表達(dá)式命名，使表示簡潔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語言的標(biāo)識(shí)符集合letter

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

→0|1|…|

9id

→letter(letter|digit)*正則定義實(shí)例?Pascal無符號(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è)例子的簡化表示正則表達(dá)式的擴(kuò)展?字母表{a,b}上以aa結(jié)尾的所有字符串。?能被4整除的所有二進(jìn)制數(shù)。練習(xí)?正則表達(dá)式是一種描述手段，通常用來描述程序語言的詞法符號(hào)。?很多編輯器支持正則表達(dá)式?工具GREP附注正則表達(dá)式可以由較小的正

則表達(dá)式遞歸構(gòu)建?如何定義你的語言？有關(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

首先通過正則定義來描述各種詞法單元的模式O

定義ws→(blank|tab|newline)+來消除空白?詞法分析器識(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í)別詞素的過程中可能出現(xiàn)的情況?狀態(tài)看作是已處理部分的總結(jié)?某些狀態(tài)為接受狀態(tài)或最終狀態(tài)，表明已經(jīng)找到詞素?加上*的接受狀態(tài)表示最后讀入的符號(hào)不在詞素中?開始狀態(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離開，

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

在符號(hào)表中預(yù)先填寫保留字，并指明它們不是普通標(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:沒有標(biāo)記為ε的邊?相同：都可以識(shí)別正則語言，兩者之間存在等價(jià)性?不同：O

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

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

且僅有一條離開該狀態(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被指定為開始狀態(tài)/初始狀態(tài)O

S的一個(gè)子集F被指定為接受狀態(tài)不確定的有窮自動(dòng)機(jī)(NFA)?狀態(tài)集合S={0,1,2,3}?開始狀態(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)換圖中存在一條從開始狀態(tài)到某個(gè)接受狀態(tài)的路徑，使得該路徑中各條邊上的標(biāo)號(hào)組成符號(hào)串x

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

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

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

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

沒有ε之上的轉(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，即它們接

受同樣的語言確定有窮自動(dòng)機(jī)(DFA)?假設(shè)輸入符號(hào)就是字符串中的符號(hào)；?Nextchar讀入下一個(gè)字符(符號(hào))?move給出了離開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á)式可以簡潔、精確地描述詞法單元的模式?進(jìn)行模式匹配時(shí)，模擬DFA的執(zhí)行比模擬NFA更為簡單有效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開始狀態(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è)接受相同語言的DFADs表示N中的單個(gè)狀態(tài)，T代表N的一個(gè)狀態(tài)集NFA轉(zhuǎn)換成DFA-子集構(gòu)造法?D的開始狀態(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è)圖搜索過程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)換的示例?開始狀態(tài)：A?接受狀態(tài)：

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

N，其開始狀態(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開頭和結(jié)尾的任意串。?用正則表達(dá)式表示字母表{a,b}上由a、b組成，且不連續(xù)出現(xiàn)兩個(gè)a的所有句子的集合，并給出接受該語言的DFA。練習(xí)?詞法分析概要?正則表達(dá)式?有限狀態(tài)自動(dòng)機(jī)?從NFA到DFA的轉(zhuǎn)換?狀態(tài)最小化算法提綱?DFA化簡：狀態(tài)數(shù)最小化?等價(jià)的DFA可能具有不同的狀態(tài)個(gè)數(shù)?任何正則語言都有一個(gè)唯一的(不計(jì)同構(gòu))狀態(tài)

數(shù)目最少的DFA基于DFA的模式匹配器的優(yōu)化?

原理：將一個(gè)DFA的狀態(tài)集合分劃成多個(gè)組，每個(gè)組中的各狀態(tài)之間相互不可區(qū)分，然后將每個(gè)組中的狀態(tài)合

并成狀態(tài)最少DFA的一個(gè)狀態(tài)?可區(qū)分的定義：O

如果分別從狀態(tài)s和狀態(tài)t出發(fā)，沿著標(biāo)號(hào)為x的路徑到達(dá)的兩個(gè)狀態(tài)只有一個(gè)是接受狀態(tài)，稱為x區(qū)分狀態(tài)s和tO

如果存在能夠區(qū)分s和t的串，那么它們就是可區(qū)分的A和C是可區(qū)

分的嗎？空串區(qū)分了E和其它狀態(tài)

bb區(qū)分了A和BDFA狀態(tài)最小化1.設(shè)置初始分劃П={S-F,F}2.迭代，不斷分劃：

for(П中的每個(gè)元素G){細(xì)分G，使得G中的s

、t仍然在同一組中

iff對(duì)任意a，s,t都到達(dá)П中的同一組；Пnew=將П中的G替換為細(xì)分得到的小組；}3.如果Пnew==П，令Пfinal==П，轉(zhuǎn)步驟4；否則П==Пnew

，轉(zhuǎn)步驟2；最小化算法(分劃部分)4.在Пfinal

的每個(gè)組中選擇一個(gè)狀態(tài)作代表，

作為最小DFA的狀態(tài)O

開始狀態(tài)就是中包含原開始狀態(tài)的組的代表O

接受狀態(tài)就是包含了原接受狀態(tài)的組的代表O

轉(zhuǎn)化關(guān)系構(gòu)造如下：?如果s是中G的代表，而s在a上的轉(zhuǎn)換到達(dá)t，而t所在組的代表為r，那么最小DFA中有從s到r的、

在a上的轉(zhuǎn)換最小化算法(構(gòu)造部分)?位于Пfinal

的同一組中的狀態(tài)不可能被任意

串區(qū)分?Пfinal

的不同組的狀態(tài)之間是可區(qū)分的DFA最小化的正確性證明?初始分劃：{A,B,C,D}{E}?處理{A,B,C,D}，b把它細(xì)分為{A,B,C}{D}?處理{A,B,C}，b把它細(xì)分為{A,C}{B}?分劃完畢。選取A,B,D和E作為代表，構(gòu)造得到最小DFADFA最小化的例子詞法分析與語法分析(二)?語法分析概要?上下文無關(guān)文法?自頂向下的語法分析算法?自底向上的語法分析算法?詞法分析和語法分析的實(shí)踐技術(shù)提綱描述分析?程序設(shè)計(jì)語言源程序的構(gòu)成：語法結(jié)構(gòu)引言O(shè)position=initial+rate*60<id,1>

<=,>

<id,2>

<+,>

<id,3>

<*,>

<number,4>一個(gè)實(shí)例語法分析?文法：一種用于描述程序設(shè)計(jì)語言語法的表示方法，能夠自然地描述程序設(shè)計(jì)語言構(gòu)造的層次化語法結(jié)構(gòu)O

文法給出了一個(gè)程序設(shè)計(jì)語言的精確易懂的語法規(guī)約O

可以基于文法構(gòu)造語法分析器，幫助確定源程序的語法結(jié)構(gòu)O

語法結(jié)構(gòu)有助于把源程序翻譯為正確的目標(biāo)代碼 O

文法的擴(kuò)展性，有助于迭代的語言演化引言?輸入：詞法分析器輸出的詞法單元序列?輸出：語法樹表示?語法分析器功能：O

驗(yàn)證輸入源程序的合法性，輸出良構(gòu)程序的語法結(jié)構(gòu)O

對(duì)于病構(gòu)的程序，能夠報(bào)告語法錯(cuò)誤，進(jìn)行錯(cuò)誤恢復(fù)?語法分析器的類型：

從左到右掃描字符

O

通用型

O

自頂向下：通常處理LL文法O

自底向上：通常處理LR文法語法分析器?類型檢查，語義分析，翻譯生成中間代碼等往往和語法分析過程交錯(cuò)完成，實(shí)踐中往往和語法分析放入一個(gè)模塊，圖上用“前端的其余部分”表示上述活動(dòng)語法分析器?錯(cuò)誤難以避免?編譯器需要具有處理錯(cuò)誤的能力?程序中可能存在不同層次的錯(cuò)誤O

詞法錯(cuò)誤O

語法錯(cuò)誤O

語義錯(cuò)誤O

邏輯錯(cuò)誤?語法錯(cuò)誤相對(duì)容易發(fā)現(xiàn)，語義和邏輯錯(cuò)誤較難精確的檢測到?語法分析器中錯(cuò)誤處理程序的設(shè)計(jì)目標(biāo)O

清晰準(zhǔn)確地報(bào)告出現(xiàn)錯(cuò)誤，并指出錯(cuò)誤的位置O

能從當(dāng)前錯(cuò)誤中恢復(fù)，以繼續(xù)檢測后面的錯(cuò)誤O

盡可能減少處理正確程序的開銷語法錯(cuò)誤的處理?錯(cuò)誤恢復(fù)O

當(dāng)預(yù)測分析器報(bào)錯(cuò)時(shí)，表示輸入的串不是句子O

對(duì)于使用者而言，希望預(yù)測分析器能夠進(jìn)行恢復(fù)處理后繼續(xù)語法分析過程，以便在一次分析中找到更多的語法錯(cuò)誤O

但是有可能恢復(fù)得并不成功，之后找到的語法錯(cuò)誤有可能是假的O

進(jìn)行錯(cuò)誤恢復(fù)時(shí)可用的信息：棧里面的符號(hào)，待分析的符號(hào)?兩類錯(cuò)誤恢復(fù)方法O

恐慌模式O

短語層次的恢復(fù)預(yù)測分析中的錯(cuò)誤恢復(fù)?基本思想O

語法分析器忽略輸入中的一些符號(hào)，直到出現(xiàn)由設(shè)計(jì)者選定的某個(gè)同步詞法單元O

解釋?語法分析過程總是試圖在輸入的前綴中找到和某個(gè)非終結(jié)符號(hào)對(duì)應(yīng)的串；出現(xiàn)錯(cuò)誤表明現(xiàn)在已經(jīng)不可能找到這個(gè)非終結(jié)符號(hào)(程序結(jié)構(gòu))的串?如果編程錯(cuò)誤僅僅局限于這個(gè)程序結(jié)構(gòu)，那么我們可以考慮跳過這個(gè)程序結(jié)構(gòu)，假裝已經(jīng)找到了這個(gè)結(jié)構(gòu)；然后繼續(xù)進(jìn)行語法分析處理 O

同步詞法單元就是這個(gè)程序結(jié)構(gòu)結(jié)束的標(biāo)志恐慌模式?在預(yù)測語法分析表的空白條目中插入錯(cuò)誤處理例程的函數(shù)指針?例程可以改變、插入或刪除輸入中的符號(hào)；發(fā)出適當(dāng)?shù)腻e(cuò)誤消息短語層次的恢復(fù)LL類文法

(無左遞歸)

自頂向下分析LR文法類

自底向上分析代表性文法?語法分析概要?上下文無關(guān)文法?自頂向下的語法分析算法?自底向上的語法分析算法?詞法分析和語法分析的實(shí)踐技術(shù)提綱?上下文無關(guān)文法(ContextFreeGrammar,CFG)?上下文無關(guān)文法是一種能夠很好描述程序設(shè)計(jì)語言的表示方法stmt

t

if(expr)stmt

else

stmtexpr

t……stmt

t……上下文無關(guān)文法?一個(gè)CFG由以下幾個(gè)部分構(gòu)成O

終結(jié)符號(hào)?組成串的基本符號(hào)，與“詞法單元名字”同義O

非終結(jié)符號(hào)?語法變量，表示特定串的集合?給出了語言的層次結(jié)構(gòu)，這種層次結(jié)構(gòu)是語法分析和翻譯的關(guān)鍵O

一個(gè)開始符號(hào)?某個(gè)特定的非終結(jié)符號(hào)，其表示的串集合是這個(gè)文法生成的語言O(shè)

一組產(chǎn)生式?描述將終結(jié)符號(hào)和非終結(jié)符號(hào)組合成串的方法?產(chǎn)生式左部(頭)是一個(gè)非終結(jié)符號(hào)?符號(hào)“→”?一個(gè)由零個(gè)或多個(gè)終結(jié)符號(hào)與非終結(jié)符號(hào)組成的產(chǎn)生式右部(體)上下文無關(guān)文法的定義?什么是上下文？O

在應(yīng)用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)時(shí)，前后已經(jīng)推導(dǎo)出的部分結(jié)果就是上下文；O

上下文無關(guān)的意思的，只要文法的定義里有某個(gè)產(chǎn)生式，不管一個(gè)非終結(jié)符前后的串是什么，就可以應(yīng)用相應(yīng)的產(chǎn)生式進(jìn)行推導(dǎo)?文法的分類：O

上下文有關(guān)文法O

上下文無關(guān)文法上下文有關(guān)文法與上下文無關(guān)文法?一個(gè)簡單的上下文無關(guān)文法例子O

Sent->S

V

OO

S->人|天O

V->吃|

下O

O->雨|雪

|飯|肉其中英文字母都是非終結(jié)符(SVO

分別表示主謂

賓)，漢字都是終結(jié)符。上下文有關(guān)文法與上下文無關(guān)文法?一個(gè)簡單的上下文無關(guān)文法例子O

Sent->S

V

OO

S->人|天O

V->吃|

下O

O->雨|雪

|飯|肉上下文有關(guān)文法與上下文無關(guān)文法?這個(gè)文法可以生成多少個(gè)句子？?一個(gè)簡單的上下文無關(guān)文法例子O

Sent->S

V

OO

S->人|天O

V->吃|

下O

O->雨|雪

|飯|肉?“天吃肉”。其(最左)推導(dǎo)過程為：Sent->SVO->天VO->天吃O(shè)->天吃肉上下文有關(guān)文法與上下文無關(guān)文法?一個(gè)簡單的上下文有關(guān)文法例子O

Sent->S

V

OO

S->人|天O

人V->人吃O(shè)

天V->天下O

下O->下雨

|下雪O

吃O(shè)->吃飯

|吃肉其中英文字母都是非終結(jié)符(SVO

分別表示主謂

賓)，漢字都是終結(jié)符。上下文有關(guān)文法與上下文無關(guān)文法?一個(gè)簡單的上下文有關(guān)文法例子O

Sent->S

V

OO

S->人|天O

人V->人吃O(shè)

天V->天下O

下O->下雨

|下雪O

吃O(shè)->吃飯

|吃肉上下文有關(guān)文法與上下文無關(guān)文法?這個(gè)文法可以生成多少個(gè)句子？?一個(gè)簡單的上下文有關(guān)文法例子O

Sent->S

V

OO

S->人|天O

人V->人吃O(shè)

天V->天下O

下O->下雨

|下雪O

吃O(shè)->吃飯

|吃肉?Sent->SVO->人VO->人吃O(shè)->人吃飯其中第三步推導(dǎo)是這樣的：非終結(jié)符V

的上文是“人”，因此可以應(yīng)用“人V->人吃”這條產(chǎn)生式，得到“人VO->人吃O(shè)”。

第四步也類似。

上下文有關(guān)文法與上下文無關(guān)文法用于描述算術(shù)表達(dá)式的文法定義?終結(jié)符號(hào)：ab+3id…?非終結(jié)符號(hào):A

B

C…,

S,

stmt?文法符號(hào):X

Y…?終結(jié)符號(hào)串:u

v

w…?文法符號(hào)串:α

β

…?不同可選體:α

1

α2

α3

…?開始符號(hào):

S符號(hào)表示約定?產(chǎn)生式又可稱為重寫規(guī)則(Rewritingrule)?推導(dǎo)O

將待處理的串中的某個(gè)非終結(jié)符號(hào)替換為這個(gè)非終結(jié)符號(hào)的某個(gè)產(chǎn)生式的體O

從開始符號(hào)出發(fā)，不斷進(jìn)行上面的替換，就可以得到文法的不同句型?推導(dǎo)的實(shí)例O

文法:E

→-E|E+E|E*E|(E)|idO從E到-(id)的推導(dǎo)序列：E=>-E=>-(E)=>-(id)推導(dǎo)?推導(dǎo)的一般性定義O

如果A→γ是一個(gè)產(chǎn)生式，那么αAβ

αγβ?經(jīng)過零步或者多步推導(dǎo)出：O

對(duì)于任何串α,ααO

如果αβ且βγ，那么αγ?經(jīng)過一步或者多步推導(dǎo)出：O

αβ且α不等于β等價(jià)于αβ?最左(右)推導(dǎo)推導(dǎo)?符號(hào)：?文法實(shí)例E

t

E+E|E*E|-E|(E)|

id

從上述文法推導(dǎo)出串–(id+id)推導(dǎo)的例子?句型(sentential

form)：O

如果Sα，那么α就是文法的一個(gè)句型O

可能既包含非終結(jié)符，又包含終結(jié)符號(hào)；可以是空串?句子(sentence)O

文法的句子就是不包含非終結(jié)符號(hào)的句型?語言O(shè)

文法G的語言就是G的句子的集合，記為L(G)O

ω在L(G)中當(dāng)且僅當(dāng)ω是G的句子，即S

ω句型/句子/語言?從推導(dǎo)的角度看，語法分析的任務(wù)是：接受一個(gè)終結(jié)符號(hào)串作為輸入，找出從文法的開始符號(hào)推導(dǎo)出這個(gè)串的方法E

t

E+E|E*E|-E|(E)|

id推導(dǎo)出串–(id+id*id)推導(dǎo)的問題?推導(dǎo)中可能遇到的兩個(gè)問題O

每一步替換哪個(gè)非終結(jié)符號(hào)？O

若以這個(gè)非終結(jié)符號(hào)為頭的產(chǎn)生式有多個(gè)，用哪個(gè)產(chǎn)生式的右部替換？E

t

E+E|E*E|-E|(E)|

id推導(dǎo)出串–(id+id*id)推導(dǎo)的問題?通常使用兩種方式進(jìn)行推導(dǎo)O

最左推導(dǎo)：總是選擇每個(gè)句型的最左非終結(jié)符號(hào)。記作O

最右推導(dǎo)：總是選擇最右邊的非終結(jié)符號(hào)。記作?每個(gè)最左推導(dǎo)步驟可以寫成

，,應(yīng)用產(chǎn)生式:?最左句型：S是文法G的識(shí)別符號(hào)，如果

G的最左句型非終結(jié)符號(hào)的替換順序?如果經(jīng)過最左推導(dǎo)得到，記作，則是?推導(dǎo)的圖形表示形式O

根結(jié)點(diǎn)的標(biāo)號(hào)是文法的開始符號(hào)O

每個(gè)葉子結(jié)點(diǎn)的標(biāo)號(hào)是非終結(jié)符號(hào)、終結(jié)符號(hào)或εO

每個(gè)內(nèi)部節(jié)點(diǎn)的標(biāo)號(hào)是非終結(jié)符號(hào)O

每個(gè)內(nèi)部結(jié)點(diǎn)表示某個(gè)產(chǎn)生式的一次應(yīng)用?內(nèi)部結(jié)點(diǎn)的標(biāo)號(hào)為產(chǎn)生式頭，結(jié)點(diǎn)的子結(jié)點(diǎn)從左到右是產(chǎn)生式的體?有時(shí)允許樹的根不是開始符號(hào)(對(duì)應(yīng)于某個(gè)短語)?樹的葉子組成的序列是根的文法符號(hào)的句型?一棵分析樹可對(duì)應(yīng)多個(gè)推導(dǎo)序列，但是分析樹和最左(右)推導(dǎo)序列之間具有一一對(duì)應(yīng)關(guān)系語法分析樹?推導(dǎo)的圖形表示形式，樹上看不出來推導(dǎo)的順序?能夠反映串的語法層次結(jié)構(gòu)?語法分析樹O

內(nèi)部節(jié)點(diǎn)：對(duì)應(yīng)于一個(gè)非終結(jié)

符號(hào)O

子節(jié)點(diǎn)：對(duì)應(yīng)于其父節(jié)點(diǎn)為頭

的產(chǎn)生式體O

葉子節(jié)點(diǎn)：可以是終結(jié)符號(hào)或

非終結(jié)符號(hào)，從左到右排列可

以得到一個(gè)句型，稱為這棵樹

的結(jié)果語法分析樹?對(duì)于推導(dǎo)中的每個(gè)句型i

，我們都可以構(gòu)

造出一個(gè)結(jié)果為i

的語法樹O

構(gòu)造過程是對(duì)i的一次歸納過程O

在推導(dǎo)的第i步，對(duì)i

應(yīng)用規(guī)則推導(dǎo)和語法樹O

假設(shè)已經(jīng)構(gòu)造出?假設(shè)有推導(dǎo)序列：O

A=>α1=>α2

=>…=>

αn?算法：O

初始化：α1的分析樹是標(biāo)號(hào)為A的單個(gè)結(jié)點(diǎn)O

假設(shè)已經(jīng)構(gòu)造出αi-1=X1X2

…Xk的分析樹，且αi-1

到αi的推導(dǎo)是將Xj替換為β，那么在當(dāng)前分析樹中找出第j個(gè)非ε結(jié)點(diǎn)，向這個(gè)結(jié)點(diǎn)增加構(gòu)成β的子結(jié)點(diǎn)。(如果β=ε，則增加一個(gè)標(biāo)

號(hào)為ε的子結(jié)點(diǎn))從推導(dǎo)序列構(gòu)造分析樹推導(dǎo)與語法樹的例子?如果一個(gè)文法可以為一個(gè)句子生成多棵不同的語法分析樹，則該文法為二義性文法?通常情況下，我們需要無二義性的文法二義性文法?程序設(shè)計(jì)語言的文法通常都應(yīng)該是無二義性的O

否則就會(huì)導(dǎo)致一個(gè)程序有多種“正確”的解釋。O

比如文法：E

→-E|E+E|E*E|(E)|

id的句子a+b*c?但有些二義性的情況可以方便文法或語法分析器的設(shè)計(jì)O

需要消二義性規(guī)則來剔除不要的語法分析樹O

比如：先乘除后加減二義性?例子：stmt

→if

expr

then

stmt|if

expr

then

stmt

else

stmt|other?if

E1

then

if

E2

then

S1

else

S2

的兩棵語法樹?這個(gè)文法是可以被改造成等價(jià)的無二義性的文法文法的二義性?語言是由文法的開始符號(hào)出發(fā)，能夠推導(dǎo)得到的所有句子的集合?文法G:

S

→

aS|a|b,

L(G)={ai(a|b),

i>=0}?文法G：S

→

aSb|abL(G)={anbn,

n>=1}?文法G：S

→

(S)S|εL(G)={所有具有對(duì)稱括號(hào)對(duì)的串}文法及其生成的語言?驗(yàn)證文法G生成語言L可以幫助我們了解文法可以生成什么樣的語言?基本步驟：O

首先證明L(G)L：G生成的每個(gè)串都在L中O

然后證明L

L(G)：L的每個(gè)串都能由G生成O

一般使用數(shù)學(xué)歸納法?證明L(G)L：按照推導(dǎo)序列長度進(jìn)行數(shù)學(xué)歸納?證明L

L(G)：按照符號(hào)串的長度來構(gòu)造推導(dǎo)序列?實(shí)例：文法G：S→(S)S|ε,L(G)={所有具有對(duì)稱括號(hào)對(duì)

的串}驗(yàn)證文法生成的語言?程序設(shè)計(jì)語言所需要的文法O

上下文無關(guān)文法足夠用來描述語法嗎？?標(biāo)識(shí)符必須先聲明后使用O

語法分析器能夠完全按照上下文無關(guān)文法來構(gòu)造嗎？?二義性、左遞歸的文法可能給語法分析器造成很大麻煩?可以怎么做？O

改造語法分析器，添加語義規(guī)則，使它可以做得更多O

改造上下文無關(guān)文法，消除二義性和左遞歸文法的設(shè)計(jì)?在進(jìn)行高效的語法分析之前，需要對(duì)文法做以下處理O

消除二義性?文法的二義性：文法可以為一個(gè)句子生成多顆不同的

樹O

消除左遞歸?左遞歸：文法中一個(gè)非終結(jié)符號(hào)A使得對(duì)某個(gè)串α，存在一個(gè)推導(dǎo)，則稱這個(gè)文法是左遞歸的O

提取左公因子很重要文法的設(shè)計(jì)?一些二義性文法可以被改成等價(jià)的無二義性的文法?例子：stmt

→if

expr

then

stmt|if

expr

then

stmt

else

stmt

|other?if

E1

then

if

E2

then

S1

else

S2

的兩棵語法樹消除文法的二義性?改寫文法，基本思想:在一個(gè)then和一個(gè)else之間出現(xiàn)的語句必須是“已匹配的”。也就是說then和else中間的語句不能以一個(gè)尚未匹配的then結(jié)尾?解決方案：引入新的非終結(jié)符號(hào)matched_stmt，用來區(qū)分是否是成對(duì)的then/else消除文法的二義性(續(xù))?通常并不是通過改變文法來消除二義性?二義性的消除方法沒有規(guī)律可循消除文法的二義性(續(xù))?左遞歸的定義O

文法中一個(gè)非終結(jié)符號(hào)A使得對(duì)某個(gè)串α，存在一個(gè)推導(dǎo)，則稱這個(gè)文法是左遞歸的?立即左遞歸O

如果存在A→

Aα,則稱為立即左遞歸?為什么要消除左遞歸？O

自頂向下的語法分析技術(shù)不能處理左遞歸的文法?立即左遞歸的消除實(shí)例：A

→

β

A’A’

→

αA’

|

ε消除左遞歸A

→

Aα

|

β首先對(duì)A產(chǎn)生式分組(所有αi不等于ε，βi不

以A開頭)可以替換為?由A生成的串總是以某個(gè)βi開頭，

然后跟上零個(gè)或者多個(gè)αi的重復(fù)?假設(shè)非終結(jié)符號(hào)A存在立即左遞歸的情形，假設(shè)以A為左部的規(guī)則有：立即左遞歸的消除?替換A

→

β1

A’|β2

A’|…|βn

A’A’→

α1

A’|α2

A’|…|αm

A’

|ε?A

→Aα1

|Aα2

|…|Aαm

|β1

|β2

|…|βn?分組消除立即左遞歸Aα1

|Aα2

|…|

Aαmβ1

|β2

|…|βnA

→|立即左遞歸消除示例?消除立即左遞歸的方法并不能消除因?yàn)閮刹交蚨嗖酵茖?dǎo)而產(chǎn)生的左遞歸?文法：S→Aa|b,A→Ac|Sd|ε?S=>Aa=>Sda?如何消除？消除多步左遞歸?輸入：沒有環(huán)Ai

Ai和A→ε?輸出：一個(gè)等價(jià)的無左遞歸的文法?算法原理：O

給非終結(jié)符號(hào)排序，A1

,A2,

…,AnO

如果只有Ai

Aj

(i<j)，則不會(huì)有左遞歸O

如果發(fā)現(xiàn)Ai

Aj

(i>j)，代入

Aj

的當(dāng)前產(chǎn)生式，若替換后有Ai

的直接左遞歸，再消除消除算法?輸入：沒有環(huán)和ε產(chǎn)生式的文法G?輸出：等價(jià)的無左遞歸的文法?步驟：將文法的非終結(jié)符號(hào)任意排序?yàn)锳1,A2,…,Anfor

i=1to

n

do

{forj=1toi-1do{將形如Ai

→Ajγ的產(chǎn)生式替換為Ai

→61γ|62γ|…|6kγ，

其中Aj

→61

|62

|…|6k是以Aj為左部的所有產(chǎn)生式；

}消除Ai

的立即左遞歸；

}

通用的左遞歸消除方法1.內(nèi)層循環(huán)的每一次迭代保證了Ai

的產(chǎn)生式的右部首符號(hào)都比Aj更加靠后2.

當(dāng)內(nèi)層循環(huán)結(jié)束時(shí)，Ai

的產(chǎn)生式的右部首符號(hào)不先于Ai3.消除立即左遞歸就保證了Ai

的產(chǎn)生式的右部首符號(hào)必然比Ai后。(不能有環(huán)和ε產(chǎn)生式)4.當(dāng)外層循環(huán)結(jié)束時(shí)，所有的產(chǎn)生式都是如此。使

用這些產(chǎn)生式當(dāng)然不會(huì)產(chǎn)生左遞歸的情形通用的左遞歸消除方法(續(xù))?S→Aa|b,A→Ac|Sd|ε?排序：SA?替換：O

i=1，沒有處理O

i=2,替換A→Sd

中的S

，得到A→Ac|Aad|bd|ε?消除立即左遞歸消除算法(示例)?在推導(dǎo)的時(shí)候，不知道該如何選擇(自頂向下算法會(huì)詳細(xì)描述)A

→

αA’A’→β1

|

β2A→αβ1

|

αβ2提取左公因子?輸入：文法G?輸出：一個(gè)等價(jià)的提取了左公因子的文法?方法：對(duì)于每個(gè)非終結(jié)符號(hào)A，找出它的兩個(gè)或多個(gè)可選項(xiàng)之間的最長公共前綴α，且α≠

ε，那么將A所有的產(chǎn)生式A→αβ1

|αβ2

|...|αβn

|

γ替換為A→αA’|γA’→β1

|β2

|...|

βn提取左公因子算法對(duì)于S而言，最長的前綴是i

E

t

S，因此：提取左公因子?抽象語言L1={wcw|w在(a|b)*中}?這個(gè)語言不是上下文無關(guān)的語言?它抽象地表示了C或者Java中“標(biāo)識(shí)符先聲明后使用”的規(guī)則O

說明了C/Java這些語言不是上下文無關(guān)語言，不能使用上下文無關(guān)文法描述。O

通常用上下文無關(guān)文法描述其基本結(jié)構(gòu)，不能用文法描述的特性在語義分析階段完成。原因是上下文無關(guān)文法具有高效的處理算法。非上下文無關(guān)語言的構(gòu)造?語法分析概要?上下文無關(guān)文法?自頂向下的語法分析算法?自底向上的語法分析算法?詞法分析和語法分析的實(shí)踐技術(shù)提綱?自頂向下分析可以被看作是為輸入串構(gòu)造語法分析樹的問題，也可以看作一個(gè)尋找輸入串的最左推導(dǎo)的過程?問題O

在推導(dǎo)的每一步，對(duì)非終結(jié)符號(hào)A，應(yīng)用哪個(gè)產(chǎn)生式，以可能產(chǎn)生于輸入串相匹配的終結(jié)符號(hào)串自頂向下分析技術(shù)id+id*id的自頂向下分析?問題：對(duì)于非終結(jié)符號(hào)A，選擇哪一個(gè)產(chǎn)生式?一種通用的遞歸下降分析框架O

由一組過程組成，每個(gè)非終結(jié)符號(hào)對(duì)應(yīng)一個(gè)過程O

程序的執(zhí)行從開始符號(hào)對(duì)應(yīng)的過程開始O

每個(gè)過程的功能是：選擇一個(gè)產(chǎn)生式體，掃描相應(yīng)的句子。若遇到非終結(jié)符號(hào)，調(diào)用該符號(hào)對(duì)應(yīng)的過程自頂向下語法分析遞歸下降分析過程示例O

S

→

cAdO

A

→

ab

|

a?輸入串w

=

c

a

d?文法：?輸入串w

=

c

a

d?文法：遞歸下降分析過程示例O

S

→

cAdO

A

→

ab

|

a?輸入串w

=

c

a

d?文法：遞歸下降分析過程示例O

S

→

cAdO

A

→

ab

|

a匹配成功！遞歸下降分析過程示例O

S

→

cAdO

A

→

ab

|

a?輸入串w

=

c

a

d?文法：?可能需要回溯，或者說，可能需要重復(fù)掃描輸入?“在回到A時(shí)，我們必須把輸入指針重新設(shè)置到位置2，即我們第一次嘗試展開A時(shí)該指針指向的位置。這意味著A的過程必須將輸入指針存放在一個(gè)局部變量中。”?如果文法中存在左遞歸……?回溯(窮試?)顯然是笨辦法遞歸下降過程示例(續(xù))?試圖從開始符號(hào)推導(dǎo)出輸入符號(hào)串?以開始符號(hào)作為初始的當(dāng)前句型?每次為最左邊的非終結(jié)符號(hào)選擇適當(dāng)?shù)漠a(chǎn)生式O

通過查看下一個(gè)輸入符號(hào)來選擇這個(gè)產(chǎn)生式O

有多個(gè)可能的產(chǎn)生式時(shí)預(yù)測分析法無能為力?比如文法：E

→+EE

|-EE|id；輸入為+id-id

id?當(dāng)兩個(gè)產(chǎn)生式具有相同的前綴時(shí)無法預(yù)測O文法：stmt

→if

expr

then

stmt

else

stmt|if

expr

then

stmtO輸入：if

a

then…O新文法：stmt

→ifexprthen

stmt

elsePartO

elsePart

→else

stmt

|ε?需要提取公因子預(yù)測分析法簡介?一種確定性的、無回溯的分析技術(shù)?在每一步選擇正確的產(chǎn)生式

例1：文法G(S)：S→

pAS→qBA→cAdA→a

輸入串

W=pccadd消除二義性

消除左遞歸

提取左公因子預(yù)測分析技術(shù)

例2：文法G(S)為：S

→Ap

S

→

Bq

A

→a∣cA

B→

b∣dB

輸入W=ccap預(yù)測分析技術(shù)(續(xù))?通過在輸入中向前看固定多個(gè)符號(hào)來選擇正確的產(chǎn)生式?通常情況下，我們只需要向前看一個(gè)符號(hào)O

遞歸下降分析一般只適合于每個(gè)子表達(dá)式的第一個(gè)終結(jié)符能夠?yàn)楫a(chǎn)生式選擇提供足夠信息的那些文法?給出兩個(gè)與文法相關(guān)的兩個(gè)函數(shù)O

FIRSTO

FOLLOW?基于上述兩個(gè)函數(shù)，可以根據(jù)下一個(gè)輸入符號(hào)來選擇應(yīng)用哪個(gè)產(chǎn)生式預(yù)測分析技術(shù)(續(xù))?在自頂向下的分析技術(shù)中，通常使用向前看幾個(gè)符號(hào)來唯一地確定產(chǎn)生式(這里假定只看一個(gè)符

號(hào))?當(dāng)前句型是xAβ，而輸入是xa…。那么選擇產(chǎn)生式A→α的必要條件是下列之一：O

Αε，且β以a開頭；也就是說在某個(gè)句型中a跟在A之后；O

Α

a…；O

如果按照這兩個(gè)條件選擇時(shí)能夠保證唯一性，那么我們就可以避免回溯。?因此，我們定義FIRST和FOLLOWFIRST和FOLLOW(1)很重要?FIRST(α)：O

可以從α推導(dǎo)得到的串

的首符號(hào)的集合；O

如果αε，那么ε也在FIRST(α)中；?

FOLLOW(A)：O

可能在某些句型中緊跟

在A右邊的終結(jié)符號(hào)的

集合。FIRST和FOLLOW(2)?定義：可從α推導(dǎo)得到的串的首符號(hào)的集合，其中α是任意的文法符號(hào)串。如果α

ε，那么ε也在FIRST(α)中?FIRST函數(shù)的意義O

如果兩個(gè)A產(chǎn)生式A

→

α

|

β，其中First(α)和

First(β)是不相交的集合。下一個(gè)輸入符號(hào)是a

，

若a∈First(α)，則選擇A

→

α

，若a∈First(β)，則選擇A

→

βO

用于預(yù)測產(chǎn)生式的選擇FIRST(α)?對(duì)于文法符號(hào)X的FIRST(X)，通過不斷應(yīng)用下

列規(guī)則，直到?jīng)]有新的終結(jié)符號(hào)或者ε可以加入到任何FIRST集合為止O

如果X是終結(jié)符號(hào)，那么FIRST(X)={X}O

如果X是非終結(jié)符號(hào)，且有規(guī)則X

t

a…,那么將a添加到FIRST(X)中;如果X

t

c，那么c也在FIRST(X)中O

對(duì)于規(guī)則X

t

Y1Y2

…Yn

，把FIRST(Y1)中的非c符號(hào)添加到FIRST(X)中。如果c在FIRST(Y1)中，把FIRST(Y2)中

的非c符號(hào)添加到FIRST(X)中…；如果c在FIRST(Yn)中，

把c添加到FIRST(X)中First的計(jì)算?對(duì)于文法符號(hào)串X1X2

…Xn

的First集合O

向First(X1X2

…Xn)加入First(X1)中所有的非ε符號(hào)。O

如果ε在First(X1)中，再加入First(X2)中的所有非ε符號(hào)。如果ε在First(X1)和First(X2)中，再加入First(X3)中的所有非ε符號(hào)。依次類推。O

如果對(duì)所有的i

(1到n)，ε都在First(Xi)中，則

ε加入First(X1X2

…Xn)中。First的計(jì)算(續(xù))?

First(F)=First(T)=First(E)={(,id}?

First(E’)={+,ε}?

First(T’)={*,ε}?First(TE’)=First(T)={(,id}?First(+TE’)={+}?……First的計(jì)算示例

First(S)

={a,

b,

c}

First(A)

=

{a,

ε

}

First(B)

=



First(C)

=

{c}

First(D)

=

2c64kgeO

S