編譯原理簡明教程（第3版）-課件 第5章 語法分析-自頂向下

新工科建設·計算機類系列教材

免費提供編譯原理16目錄第一章

概述第二章形式語言理論基礎第三章自動機理論基礎第四章詞法分析第五章語法分析—自頂向下分析方法第六章語法分析—自底向上分析方法第七章語義分析及中間代碼的生成第八章代碼優化第九章目標代碼的生成第十章符號表和出錯處理第十一章

面向對象語言的編譯第十二章

并行編譯技術第十三章

并行編譯技術25語法分析

----自頂向下分析方法學習目標自上而下語法分析的基本思想自上而下語法分析面臨的問題及解決方法消除左遞歸的方法First集、Follow集、Select集的求法LL（1）分析方法遞歸子程序分析方法3語法分析是編譯過程的核心部分。

-----在詞法分析識別出單詞符號串的基礎上，分析并判定程序的語法結構是否符合語法規則。語法分析自頂向下如LL(k)，遞歸下降分析法等自底向上如LR(K)，簡單優先分析法等4

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

從文法的開始符號出發,向下推導,看能否推出待分析的符號串,如果能推出,說明該符號串是符合語言語法的句子,否則不是句子。61231.從文法的開始符號出發2.

向下推導3.推導出句子

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

Bcd|cBd判斷abccdd是否是句子。(1)自頂向下構造語法樹SABabcBdcd(2)推導SABAcBd

Accdd

abccdd75.1.2三種終結符號集1.First集(首符號集)

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

First(β)={a|βay,a∈VT,y∈V*}特別,若β=ε,則First(β)=Φ*例：G[S]：SApSBqAa|cAFirst(dB)=c6fqpzgv7yBb|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],非終結符號U的向前看集

Follow(U)={a|S

…Ua…,a∈VTU{#}}

特別,當a=ε時,視U后面的符號為”#”****∵E

E,E

E+T,E

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

β

則該規則的可選集為:11例:對于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自頂向下語法分析難點1.左遞歸問題例:G[S]:

SSa|b

分析baaSS

S

S

S

SbSaSaSaSaSa

bSaSaSab…14分析時可能出現:

(1)回溯

(2)死循環,在沒有對當前輸入符號匹配就進入處理S的過程，無法確定什么時候才用Sb替換,

造成死循環.解決方法:

文法的實用限制(算法6)消除左遞歸擴充的BNF表示法152.回溯問題

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

在自頂向下分析過程中，對候選式的選擇可根據當前輸入符號來決定.16首先:對每條規則A

β,

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

Follow(A)β=ε當β≠ε時,對于當前輸入符號a,若

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

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

BbaA|c

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

分析符號串bbabaacAbA

bbA

bbaB

bbabaA

bbabaaB

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

(2)首符號相同即對于A

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

α(x1|x2...|xn)進一步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確定的自頂向下語法分析思想22不確定的自頂向下分析思想例:G[S]:SxAy

Aab|a

分析xay是否句子

SxAy

a(3)SxAy

(1)SxAy

ab(2)分析過程:(1)(2)(1)(3)出現回溯.23例:

G[E]:ET|EATTF|TMFF(E)|i分析符號串i+i*iA+|-M*|/24推導: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

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

LL(k)是一種確定的自頂向下分析法:掃描輸入串,同時從文法的識別符號開始產生句子的最左推導,每一步推導時向前看k個符號,以確定當前應選規則.k=1,即LL(1),簡單易懂,應用較多.265.2.1LL(1)語法分析思想例:

G[S]:SaBc|bB

BbB|d

對句子abbdc進行分析.

從左到右掃描abbdc,對照規則，對第一個字符a,只能用

SaBc,第二個符號b,只能用BbB

SaB

cbB

bB

d

由此,LL(1)的基本思想就是根據輸入串的當前符號唯一確定所選規則進行推導.

abbBcabbdcSaBc

abBc275.2.2LL(1)語法分析方法的邏輯結構a1a2a3…ai…am#輸入串

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

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

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

若x1≠

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

BbB|eB|d

分析abbdc#設計文法的分析表:

abcdeAAaBcBBbBBdBeB325.2.3LL(1)分析方法分析棧輸入符號產生式匹配刪除#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)分析器工作過程(2)LL(1)語法分析表的構造

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

C:繼續讀入下一字符

R:重讀當前字符RE(β):用β的逆串替換棧頂符號.34構造LL(1)分析表的算法如下:35

36例:G’[A]:AaBc

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

#cc# ε/C

## succ39例5－6表達式文法G[E]：E→EAT|TT→TMF|FF→(E)|iA→+|-M→*|/消除左遞歸求select集構造分析表分析符號串40例5－61.消除左遞歸41例5－62.求select集423.構造分析表434.分析符號串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)文法。構造出的分析表含有多重定義?！?Φ∩≠Φ46注：有些不是LL(1)文法的文法，經過修改（如左提左因子，消除左遞歸等）可化為LL(1)文法，但并不是所有的非LL(1)文法都能改造為LL(1)文法。47例對于文法G[Z]:

ZAU|BR

AaAU|b

BaBR|b

Uc

Rd

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

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

485.3遞歸下降語法分析方法5.3.1遞歸下降語法分析方法的實現思想是一種確定的自頂向下分析法。又稱遞歸子程序分析法。思想：對文法中每個非終結符（代表語法成分）編寫一個子程序（或遞