語法分析教學(xué)內(nèi)容

語法分析上下文無關(guān)文法4.1~4.34.1上下文無關(guān)文法4.1.1上下文無關(guān)文法的定義正則式能定義一些簡單的語言，能表示給定結(jié)構(gòu)的固定次數(shù)的重復(fù)或者沒有指定次數(shù)的重復(fù) 例：a(ba)5,a(ba)*正則式不能用于描述配對或嵌套的結(jié)構(gòu) 例1：配對括號串的集合 例2：{wcw|w是a和b的串}

4.1上下文無關(guān)文法上下文無關(guān)文法是四元組（VT,VN,S,P）VT

: 終結(jié)符集合VN

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

: 產(chǎn)生式集合，產(chǎn)生式形式:A

例({id,+,,,(,)},{expr,op},expr,P)expr

expr

op

expr expr(expr)expr

expr expr

idop+ op

4.1上下文無關(guān)文法簡化表示expr

expr

op

expr |

(expr)|

expr|idop+|簡化表示E

EAE|(E)|E|idA+|4.1上下文無關(guān)文法文法書寫上的約定終結(jié)符字母表中的小寫字母，如a，b，c黑體串，如id,while數(shù)字0,1,…,9標(biāo)點符號，如括號，逗號等運算符號，如+,-等非終結(jié)符字母表中的大寫字母，如A,B,C字母S，并且通常代表開始符號小寫字母的名字（斜體），如expr,stmt4.1上下文無關(guān)文法文法書寫上的約定字母表中后面的大寫字母，如X，Y，Z，可以是終結(jié)符或非終結(jié)符字母表中后面的小寫字母，如u，v

…z可代表終結(jié)符號串小寫希臘字母，如a，b，可代表文法的符號串對于Aa1，Aa2，...

Aan可以寫成

Aa1|a2|…

|an4.1上下文無關(guān)文法4.1.2

推導(dǎo)（自頂向下）把產(chǎn)生式看成重寫規(guī)則，把符號串中的非終結(jié)符用其產(chǎn)生式右部的串來代替例 E

E+E|E

E|(E)|

E|idE

E

(E)

(E+E)

(id+E)(id+id)概念 S*、S+w

，于是**

b，且b

γ,則*

γ

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

推導(dǎo)概念 上下文無關(guān)語言A→γ,且a、b是任意符號串，則aAb

aγb由上下文無關(guān)文法生成的語言是上下文無關(guān)語言等價的文法如果兩個文法產(chǎn)生同樣的語言，則兩個文法等價句型文法G的開始符為S，S*，可能含有非終結(jié)符，則叫做文法G的句型。4.1上下文無關(guān)文法例E

E+E|E

E|(E)|

E|id

最左推導(dǎo) E lm

Elm

(E)lm

(E

+E)

lm

(id+E)lm(id+id)最右推導(dǎo) E rm

Erm

(E)rm

(E+E)

rm

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

E+E|E

E|(E)|

E|idEE()EEE+idid4.1上下文無關(guān)文法4.1.4二義性idid+id E

E

E

E

E+E idE

E

E+E

id

E+E id

E+E

idid+E idid+E idid+id idid+id 兩個不同的最左推導(dǎo)4.1上下文無關(guān)文法4.1.4二義性idid+id E

E

E

E

E+E idE

E

E+E

id

E+E id

E+E

idid+E idid+E idid+id idid+id 兩棵不同的語法樹EEE*+EEidididEEidE*+EEidid4.2語言和文法文法的優(yōu)點

文法給出了精確的，易于理解的語法說明自動產(chǎn)生高效的分析器可以給語言定義出層次結(jié)構(gòu)以文法為基礎(chǔ)的語言的實現(xiàn)便于語言的修改文法的問題文法只能描述編程語言的大部分語法，不能描述語言中上下文有關(guān)的語法特征4.2

語言和文法4.2.1

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

a

A0|bA0|a

A1A1

b

A2A2

12開始a0abb4.2

語言和文法4.2.2分離詞法分析器理由為什么要用正則式定義詞法

詞法規(guī)則非常簡單，不必用上下文無關(guān)文法對于詞法記號，正則式描述簡潔且易于理解從正則式構(gòu)造出的詞法分析器效率高4.2

語言和文法從軟件工程角度看，詞法分析和語法分析的分離有如下好處簡化設(shè)計編譯器的效率會改進(jìn)編譯器的可移植性加強便于編譯器前端的模塊劃分4.2

語言和文法能否把詞法分析并入到語法分析中，直接從字符流進(jìn)行語法分析若把詞法分析和語法分析合在一起，則必須將語言的注解和空白的規(guī)則反映在文法中，文法將大大復(fù)雜注解和空白由自己來處理的分析器，比注解和空格已由詞法分析器刪除的分析器要復(fù)雜得多4.2

語言和文法4.2.3

驗證文法產(chǎn)生的語言G:S

(S)S|L(G)=配對的括號串的集合4.2

語言和文法4.2.3

驗證文法產(chǎn)生的語言G:S

(S)S|L(G)=配對的括號串的集合按推導(dǎo)步數(shù)進(jìn)行歸納：推出的是配對括號串歸納基礎(chǔ)：S

歸納假設(shè)：少于n步的推導(dǎo)都產(chǎn)生配對的括號串歸納步驟：n步的最左推導(dǎo)如下：

S(S)S*(x)S*(x)y4.2

語言和文法4.2.3

驗證文法產(chǎn)生的語言G:S

(S)S|L(G)=配對的括號串的集合按串長進(jìn)行歸納：配對括號串可由S推出歸納基礎(chǔ)：S

歸納假設(shè)：長度小于2n的都可以從S推導(dǎo)出來歸納步驟：考慮長度為2n(n

1)的w=(x)y

S(S)S*(x)S*(x)y4.2

語言和文法4.2.4適當(dāng)?shù)谋磉_(dá)式文法用一種層次觀點看待表達(dá)式 idid(id+id)+idid+id4.2

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

idid(id+id)+idid+id

id

id

(id+id)

文法 expr

expr+term|term term

term

factor|factor

factor

id|(expr)4.2

語言和文法expr

expr+term|termterm

term

factor|factor

factor

id|(expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid+idid分析樹

ididid分析樹

4.2

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

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

elsestmt兩個最左推導(dǎo)：

stmtifexprthenstmt

ifexprthenifexprthenstmtelsestmt

stmtifexprthenstmtelsestmt

ifexprthenifexprthenstmtelsestmt

4.2

語言和文法

無二義的文法stmt

matched_stmt

|unmatched_stmtmatched_stmt

ifexprthenmatched_stmt

elsematched_stmt

|otherunmatched_stmt

ifexprthenstmt |ifexprthenmatched_stmt

elseunmatched_stmt4.2

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

α|βAβRRαR|ε4.2

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

直接左遞歸 AAa|b

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

bA A

aA|

4.2

語言和文法例

算術(shù)表達(dá)文法

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)|id4.2

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

Aa|b

A

Sd|先變換成直接左遞歸 S

Aa|b A

Aad|bd|

再消除左遞歸

SAa|b A

bdA

|A A

adA

|4.2

語言和文法4.2.7

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

1|2提左因子 A

A A

1|2

4.2

語言和文法例

懸空else的文法 stmt

ifexprthenstmt

elsestmt

|ifexprthenstmt |other 提左因子

stmt

ifexprthenstmt

optional_else_part |other

optional_else_partelsestmt |形式語言

產(chǎn)生式形式為：xAy->xy

產(chǎn)生式形式為：A->aB,A->a,A->

產(chǎn)生式形式為：A->⑶2型語言由2型文法定義⑵1型語言由1型文法定義⑴0型語言由0型文法定義

產(chǎn)生式形式為：->⑷3型語言由3型文法定義又稱無限制文法！又稱上下文有關(guān)文法！又稱上下文無關(guān)文法！又稱正規(guī)文法！【注】四類語言為包含關(guān)系，且有L0?L1?

L2?

L3；