編譯原理簡(jiǎn)明教程（第3版）-課件 第5章 語(yǔ)法分析-自頂向下

新工科建設(shè)·計(jì)算機(jī)類系列教材

免費(fèi)提供編譯原理16目錄第一章

概述第二章形式語(yǔ)言理論基礎(chǔ)第三章自動(dòng)機(jī)理論基礎(chǔ)第四章詞法分析第五章語(yǔ)法分析—自頂向下分析方法第六章語(yǔ)法分析—自底向上分析方法第七章語(yǔ)義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號(hào)表和出錯(cuò)處理第十一章

面向?qū)ο笳Z(yǔ)言的編譯第十二章

并行編譯技術(shù)第十三章

并行編譯技術(shù)25語(yǔ)法分析

----自頂向下分析方法學(xué)習(xí)目標(biāo)自上而下語(yǔ)法分析的基本思想自上而下語(yǔ)法分析面臨的問(wèn)題及解決方法消除左遞歸的方法First集、Follow集、Select集的求法LL（1）分析方法遞歸子程序分析方法3語(yǔ)法分析是編譯過(guò)程的核心部分。

-----在詞法分析識(shí)別出單詞符號(hào)串的基礎(chǔ)上，分析并判定程序的語(yǔ)法結(jié)構(gòu)是否符合語(yǔ)法規(guī)則。語(yǔ)法分析自頂向下如LL(k)，遞歸下降分析法等自底向上如LR(K)，簡(jiǎn)單優(yōu)先分析法等4

目錄5.1自頂向下語(yǔ)法分析技術(shù)5.2LL(K)語(yǔ)法分析方法5.3遞歸下降語(yǔ)法分析方法5.4本章小結(jié)55.1自頂向下語(yǔ)法分析技術(shù)

從文法的開(kāi)始符號(hào)出發(fā),向下推導(dǎo),看能否推出待分析的符號(hào)串,如果能推出,說(shuō)明該符號(hào)串是符合語(yǔ)言語(yǔ)法的句子,否則不是句子。61231.從文法的開(kāi)始符號(hào)出發(fā)2.

向下推導(dǎo)3.推導(dǎo)出句子

5.1.1自頂向下語(yǔ)法分析思想例:文法G[S]:SABAab

Bcd|cBd判斷abccdd是否是句子。(1)自頂向下構(gòu)造語(yǔ)法樹(shù)SABabcBdcd(2)推導(dǎo)SABAcBd

Accdd

abccdd75.1.2三種終結(jié)符號(hào)集1.First集(首符號(hào)集)

定義:文法G[S]:字匯表V,則符號(hào)串β的首符號(hào)集

First(β)={a|βay,a∈VT,y∈V*}特別,若β=ε,則First(β)=Φ*例：G[S]：SApSBqAa|cAFirst(dB)=bennxrzBb|dBFirst(Ap)={a,c}First(Bq)={b,d}8例:G[E]:EE+T|TTT*F|FF(E)|i則:First(E+T)={(,i}First(T)={(,i}First(T*F)={(,i}First(F)={(,i}First((E))={(}First(i)={i}92.Follow集(向前看集)定義:文法G[S],非終結(jié)符號(hào)U的向前看集

Follow(U)={a|S

…Ua…,a∈VTU{#}}

特別,當(dāng)a=ε時(shí),視U后面的符號(hào)為”#”****∵E

E,E

E+T,E

(E)∴Follow(E)={#,+,)}Follow(T)={#,+,*,)}Follow(F)={#,+,*,)}103.Select集(可選集)定義:文法G[S],有規(guī)則A

β

則該規(guī)則的可選集為:11例:對(duì)于G[E]select(EE+T)=First(E+T)={(,i}select(ET)=First(T)={(,i}select(TT*F)=First(T*F)={(,i}select(TF)=First(F)={(,i}select(F(E))=First((E))={(}select(Fi)=First(i)={i}12例:G[S]:SaBc|bBBbB|d|εSelect(Bε)=Follow(B)={#,c}135.1.3自頂向下語(yǔ)法分析難點(diǎn)1.左遞歸問(wèn)題例:G[S]:

SSa|b

分析baaSS

S

S

S

SbSaSaSaSaSa

bSaSaSab…14分析時(shí)可能出現(xiàn):

(1)回溯

(2)死循環(huán),在沒(méi)有對(duì)當(dāng)前輸入符號(hào)匹配就進(jìn)入處理S的過(guò)程，無(wú)法確定什么時(shí)候才用Sb替換,

造成死循環(huán).解決方法:

文法的實(shí)用限制(算法6)消除左遞歸擴(kuò)充的BNF表示法152.回溯問(wèn)題

在分析中，假定被代換的最左非終結(jié)符A存在n條規(guī)則,Ax1|x2|…|xn，難以確定采用哪個(gè)規(guī)則，若從x1到xn逐個(gè)來(lái)試,則效率太低。A的候選式:x1,x2,…xn

在自頂向下分析過(guò)程中，對(duì)候選式的選擇可根據(jù)當(dāng)前輸入符號(hào)來(lái)決定.16首先:對(duì)每條規(guī)則A

β,

First(β)β≠ε求Select(Aβ)=

Follow(A)β=ε當(dāng)β≠ε時(shí),對(duì)于當(dāng)前輸入符號(hào)a,若

a∈First(β)則可選Aβ進(jìn)行推導(dǎo),但A有n個(gè)候選式,∴分兩種情況.17

(1)首符號(hào)不同例:G[A]:AaB|bA

BbaA|c

{First(aB)={a}}∩{First(bA)=}=Φ{First(baA)=}∩{First(c)={c}}=Φ

分析符號(hào)串bbabaacAbA

bbA

bbaB

bbabaA

bbabaaB

bbabaacFirst(xi)∩First(xj)=Φ(i≠j)若a∈First(xk),則選用Axk來(lái)推導(dǎo)18

(2)首符號(hào)相同即對(duì)于A

αx1|αx2...|αxn改為A

α(x1|x2...|xn)進(jìn)一步A

αBBx1|x2...|xn

First(xi)∩First(xj)≠Φ(i≠j)解決方法:“左提左因子”修改文法19例:U

αx1|αx2|x3|…|xn

且First(xi)∩First(xj)=Φ,(i,j≥3,i≠j)

First(xi)≠α,(i=3,4,…n)

采用

UαV|x3|…|xn

Vx1|x220例:G[S]:SifBthenS1elseS2|ifBthenS1

改為:

SifBthenS1TTelseS2|ε215.1.4確定的自頂向下語(yǔ)法分析思想22不確定的自頂向下分析思想例:G[S]:SxAy

Aab|a

分析xay是否句子

SxAy

a(3)SxAy

(1)SxAy

ab(2)分析過(guò)程:(1)(2)(1)(3)出現(xiàn)回溯.23例:

G[E]:ET|EATTF|TMFF(E)|i分析符號(hào)串i+i*iA+|-M*|/24推導(dǎo):E

T

F

i

T

TMF

FMF

iMF

i*F

i*i

EAT

EAF

TAF

FAF

i+i

TAT

i+T

i+TMF

i+i*i

++推導(dǎo)過(guò)程是一個(gè)不斷試探的過(guò)程,出現(xiàn)回溯現(xiàn)象，所以又稱帶回溯的自頂向下分析方法(效率低，代價(jià)高)原因:推導(dǎo)過(guò)程中有多個(gè)侯選式可供選擇.255.2LL(K)語(yǔ)法分析方法

LL(k)是一種確定的自頂向下分析法:掃描輸入串,同時(shí)從文法的識(shí)別符號(hào)開(kāi)始產(chǎn)生句子的最左推導(dǎo),每一步推導(dǎo)時(shí)向前看k個(gè)符號(hào),以確定當(dāng)前應(yīng)選規(guī)則.k=1,即LL(1),簡(jiǎn)單易懂,應(yīng)用較多.265.2.1LL(1)語(yǔ)法分析思想例:

G[S]:SaBc|bB

BbB|d

對(duì)句子abbdc進(jìn)行分析.

從左到右掃描abbdc,對(duì)照規(guī)則，對(duì)第一個(gè)字符a,只能用

SaBc,第二個(gè)符號(hào)b,只能用BbB

SaB

cbB

bB

d

由此,LL(1)的基本思想就是根據(jù)輸入串的當(dāng)前符號(hào)唯一確定所選規(guī)則進(jìn)行推導(dǎo).

abbBcabbdcSaBc

abBc275.2.2LL(1)語(yǔ)法分析方法的邏輯結(jié)構(gòu)a1a2a3…ai…am#輸入串

控制程序分析表分析器x1x2….xn#分析棧輸入串a(chǎn)1a2a3…am#,以定界符”#”作為結(jié)尾分析表:M[A,a](A為棧中元素,a為輸入字符285.2.3LL(1)語(yǔ)法分析方法1.LL(1)文法

對(duì)于文法G[S],其每個(gè)非終結(jié)符的不同規(guī)則具有不相交的select集.即對(duì)于Ux1|x2|…|xn,有select(Uxi)∩select(Uxj)=Φ,(i≠j)292.LL(1)語(yǔ)法分析表的生成LL(1)分析過(guò)程當(dāng)前句型的右端部分x1x2…xm#(xi∈V)待分析串的右端部分y1y2…yn#(yi∈VT)

x1x2…xm#305.2.3LL(1)分析方法分幾種情況:1)當(dāng)x1∈VN，由y1選擇相應(yīng)規(guī)則替換x12)當(dāng)x1∈VT,若x1=y1≠#,則說(shuō)明x1與y1匹配,分別刪去x1,y1,繼續(xù)分析.

若x1≠

y1,則說(shuō)明不匹配，進(jìn)行出錯(cuò)處理3)若x1=y1=#,說(shuō)明全部匹配,分析成功.LL(1)分析程序見(jiàn)P77--78315.2.3LL(1)分析方法例:G[A]:AaBc

BbB|eB|d

分析abbdc#設(shè)計(jì)文法的分析表:

abcdeAAaBcBBbBBdBeB325.2.3LL(1)分析方法分析棧輸入符號(hào)產(chǎn)生式匹配刪除#A abbdc##cBa abbdc# AaBc#cB bbdc#a#cBb bbdc# BbB#cB bdc#b#cBb bdc# BbB#cB dc#b#cd dc# Bd#c c#d# #c33(1)LL(1)分析器工作過(guò)程(2)LL(1)語(yǔ)法分析表的構(gòu)造

LL(1)分析表反映分析棧中元素與輸入串中元素的匹配關(guān)系.記M[A,a]幾個(gè)約定:

C:繼續(xù)讀入下一字符

R:重讀當(dāng)前字符RE(β):用β的逆串替換棧頂符號(hào).34構(gòu)造LL(1)分析表的算法如下:35

36例:G’[A]:AaBc

BbB|eB|d先求各規(guī)則的select集Select(AaBc)={a}Select(BbB)=Select(BeB)={e}Select(Bd)=bi61ain且c不出現(xiàn)在任何規(guī)則右部的首部.37構(gòu)造LL(1)分析表:abcde#ABc#cB/CB/Cε/CB/Cε/Csucc38分析abbedc的過(guò)程分析棧余留輸入串 動(dòng)作#Aabbedc# cB/C#cBbbedc#B/C#cBbedc# B/C#cBedc# B/C#cBdc# ε/C

#cc# ε/C

## succ39例5－6表達(dá)式文法G[E]：E→EAT|TT→TMF|FF→(E)|iA→+|-M→*|/消除左遞歸求select集構(gòu)造分析表分析符號(hào)串40例5－61.消除左遞歸41例5－62.求select集423.構(gòu)造分析表434.分析符號(hào)串44例文法G[S]S

abB

A

SC|BAA|εVN={S,A,B,C}B

AbAVT={a,b,c}C

B|c45判斷此文法是不是LL(1)文法:Select(SabB)={a}Select(ASC)={a}Select(ABAA)={a,b}Select(Aε)={a,b,#}Select(CB)={a,b}Select(Cc)={c}Selcet(BAbA)={a,b}

∴不是LL(1)文法。構(gòu)造出的分析表含有多重定義?！?Φ∩≠Φ46注：有些不是LL(1)文法的文法，經(jīng)過(guò)修改（如左提左因子，消除左遞歸等）可化為L(zhǎng)L(1)文法，但并不是所有的非LL(1)文法都能改造為L(zhǎng)L(1)文法。47例對(duì)于文法G[Z]:

ZAU|BR

AaAU|b

BaBR|b

Uc

Rd

First(AU)∩First(BR)={a,b}≠Φ

所以，不是一個(gè)LL(1)文法

485.3遞歸下降語(yǔ)法分析方法5.3.1遞歸下降語(yǔ)法分析方法的實(shí)現(xiàn)思想是一種確定的自頂向下分析法。又稱遞歸子程序分析法。思想：對(duì)文法中每個(gè)非終結(jié)符（代表語(yǔ)法成分）編寫(xiě)一個(gè)子程序（或遞