第四部分第五七章語(yǔ)法分析

第四部分第五七章語(yǔ)法分析第一頁(yè)，共一百九十八頁(yè)，2022年，8月28日第四部分內(nèi)容4.1自頂向下分析方法（第5章）4.2遞歸下降分析(遞歸子程序法)（第5章）4.3LL(1)分析方法（第5章）4.4自底向上分析方法（第6章）4.5算符優(yōu)先分析法（第6章）4.6LR分析方法（第7章）第二頁(yè)，共一百九十八頁(yè)，2022年，8月28日一、語(yǔ)法分析是編譯過(guò)程的核心部分語(yǔ)法分析的任務(wù)：按照文法，從源程序符號(hào)串中識(shí)別出各類語(yǔ)法成分，同時(shí)進(jìn)行語(yǔ)法檢查，為語(yǔ)義分析和代碼生成做準(zhǔn)備。語(yǔ)法分析程序的定義：執(zhí)行語(yǔ)法分析任務(wù)的程序稱為語(yǔ)法分析程序，也稱為語(yǔ)法分析器，它是編譯程序的主要部分之一。語(yǔ)法分析方法的分類：分成兩大類。自頂向下分析和自底向上分析。第三頁(yè)，共一百九十八頁(yè)，2022年，8月28日二、語(yǔ)法分析的數(shù)學(xué)模型——下推自動(dòng)機(jī)（1）下推機(jī)的邏輯結(jié)構(gòu)PDA的讀、寫、狀態(tài)轉(zhuǎn)移動(dòng)作決定于以下三個(gè)因素：當(dāng)前所處狀態(tài)讀頭所指符號(hào)下推棧棧頂符號(hào)一個(gè)輸入串能為PDA所接受，僅當(dāng)輸入串讀完，下推棧變空；或者輸入串讀完，控制器到達(dá)某些終態(tài)。有限狀態(tài)控制器輸入帶輸出帶下推棧下推自動(dòng)機(jī)邏輯結(jié)構(gòu)第四頁(yè)，共一百九十八頁(yè)，2022年，8月28日（2）下推機(jī)的定義下推自動(dòng)機(jī)是一個(gè)七元組M=(Q,Σ,H,δ,q0,z0,F)，其中：Q是控制器的有限狀態(tài)集；Σ是輸入字母表；H是下推棧內(nèi)字母表；δ是Q×(Σ∪{ε})×H到Q×H*的有限子集映射；q0∈Q是控制器的初始狀態(tài)；z0∈H是下推棧的棧初始符；F為Q的子集，是控制器的終態(tài)集。第五頁(yè)，共一百九十八頁(yè)，2022年，8月28日（3）說(shuō)明映射函數(shù)δ描述PDA動(dòng)作與狀態(tài)的變化

δ(q,a,z)={(q1,γ1),(q2,γ2),…,(qn,γn)}

其中q,qi(1≤i≤n)∈Q,a∈Σ*,z∈H

含義：控制器當(dāng)前狀態(tài)為q，下推棧棧頂符號(hào)為z，輸入符號(hào)為a(可為空)情況下，狀態(tài)轉(zhuǎn)換到序偶集(qi,γi),qi為下一狀態(tài)，γi為代替z的棧頂符號(hào)串。映射函數(shù)δ不是單值映射，且下推機(jī)有兩種接受狀態(tài)：串讀完進(jìn)入終態(tài)和串讀完?？?。例子：LL(1)語(yǔ)法分析器與PDA的對(duì)應(yīng)關(guān)系 設(shè)CFGG=（VN，Σ，P，S），構(gòu)造一個(gè)不確定的PDA M=（Q，Σ，H，δ，q0

，z0

，F(xiàn)），其中Q=F={q0}；H=VN∪

Σ；z0=S;δ映射關(guān)系的構(gòu)造方法如下： 對(duì)于形如Aω

產(chǎn)生式，有δ(q,ε,A)=(q,ω)，

δ(q,a,a)=(q,ε)其中a∈Σ。第六頁(yè)，共一百九十八頁(yè)，2022年，8月28日4.1自頂向下分析方法4.1.1帶回溯的自頂向下的分析方法4.1.2存在的問(wèn)題及解決方法第七頁(yè)，共一百九十八頁(yè)，2022年，8月28日4.1.1帶回溯的自頂向下的分析方法思路：對(duì)任一輸入符號(hào)串，通過(guò)一切可能的辦法，從樹(shù)根結(jié)點(diǎn)(識(shí)別符號(hào))出發(fā)，根據(jù)文法自上而下地為輸入串建立一棵語(yǔ)法樹(shù)；或者說(shuō)，從識(shí)別符號(hào)開(kāi)始，根據(jù)文法試圖為輸入串建立一個(gè)推導(dǎo)序列。特點(diǎn)：是自頂向下分析的一般方法，分析過(guò)程的本質(zhì)是一種試探過(guò)程。第八頁(yè)，共一百九十八頁(yè)，2022年，8月28日以上文法沒(méi)有左遞歸，且有以下兩個(gè)特點(diǎn)：

(1)每個(gè)產(chǎn)生式的右部都由終結(jié)符號(hào)開(kāi)始。

(2)如果兩個(gè)產(chǎn)生式有相同的左部，那么它們的右部由不同的終結(jié)符開(kāi)始。

舉例（1）確定的自頂向下分析第九頁(yè)，共一百九十八頁(yè)，2022年，8月28日以上文法沒(méi)有左遞歸，且有以下特點(diǎn)：

(1)產(chǎn)生式的右部不全是由終結(jié)符開(kāi)始。

(2)如果兩個(gè)產(chǎn)生式有相同的左部，其右部是由不同的終結(jié)符或非終結(jié)符開(kāi)始。

(3)文法中無(wú)空產(chǎn)生式。

第十頁(yè)，共一百九十八頁(yè)，2022年，8月28日以上推導(dǎo)過(guò)程的特點(diǎn)：在第二步到第三步的推導(dǎo)中，即abAS=>abS時(shí)，因?yàn)楫?dāng)前輸入符號(hào)為d，而最左非終結(jié)符A的產(chǎn)生式右部的開(kāi)始符號(hào)集合都不包含d，但A可以推出空，所以d的匹配任務(wù)就只能依賴于A后面的符號(hào)，所以選用產(chǎn)生式“A空”進(jìn)行推導(dǎo)，句型中緊跟A后面的符號(hào)為S，S產(chǎn)生式右部的開(kāi)始符號(hào)中包含了d，所以可匹配。

第十一頁(yè)，共一百九十八頁(yè)，2022年，8月28日假定有文法G[S]：(1)S::=cAd(2)A::=ab|a 對(duì)輸入串w=cad。要求自上而下地構(gòu)造w的語(yǔ)法樹(shù)。解決過(guò)程：（2）非確定的自頂向下分析第十二頁(yè)，共一百九十八頁(yè)，2022年，8月28日分析：通過(guò)上述解答過(guò)程可以看出：自頂向下地為輸入符號(hào)串w建立語(yǔ)法樹(shù)的過(guò)程實(shí)際上就是設(shè)法建立w的一個(gè)最左推導(dǎo)序列。比如對(duì)于上例中的輸入串w可以通過(guò)如下的推導(dǎo)過(guò)程將其推導(dǎo)出來(lái)：

S=>cAd=>cad

由于對(duì)輸入串是自左向右掃描的，因此用最左推導(dǎo)，只有用最左推導(dǎo)，才能保證按掃描順序去匹配輸入串。第十三頁(yè)，共一百九十八頁(yè)，2022年，8月28日問(wèn)題：缺陷：不能處理左遞歸文法(教材P88圖5.6、圖5.7)。缺點(diǎn)：存在回溯，算法效率低。（另：更多例子參閱教材P91）第十四頁(yè)，共一百九十八頁(yè)，2022年，8月28日4.1.2存在的問(wèn)題及解決方法一、左遞歸問(wèn)題 ①直接左遞歸 ②間接左遞歸二、回溯問(wèn)題 實(shí)現(xiàn)不帶回溯的自頂向下分析的條件 ①文法非左遞歸 ②首符號(hào)集不相交第十五頁(yè)，共一百九十八頁(yè)，2022年，8月28日(一)左遞歸問(wèn)題（P88）①直接左遞歸 自頂向下分析方法不能處理具有左遞歸性的文法的原因：例如∶規(guī)則U::=U…是一條左遞歸規(guī)則，為了實(shí)現(xiàn)用U…匹配輸入串，又會(huì)遇到要用U去匹配。故又要啟用上述規(guī)則的右部符號(hào)串U…來(lái)完成匹配工作。如此循環(huán)下去而無(wú)法終止。第十六頁(yè)，共一百九十八頁(yè)，2022年，8月28日方法：用第二章中介紹的重復(fù)和選擇表示法(擴(kuò)充的BNF表示)去改寫左遞歸規(guī)則。例如：規(guī)則：E::=E+T|T 改寫為： E::=T{+T} 規(guī)則： T::=T*F|T/F|F 改寫為： T::=F{*F|/F}

改寫后的文法消除了直接左遞歸，且改寫前后的文法是等價(jià)的。第十七頁(yè)，共一百九十八頁(yè)，2022年，8月28日將直接左遞歸規(guī)則轉(zhuǎn)換成使用重復(fù)表示法的等價(jià)規(guī)則的處理原則：1.規(guī)則1(提取因子)：當(dāng)出現(xiàn)規(guī)則U::=xy|xw|…|xz時(shí)，用規(guī)則U::=x(y|w|…|z)代替。其中，圓括號(hào)是元符號(hào)。特例：對(duì)規(guī)則U::=x|xy，則轉(zhuǎn)換為U::=x(y|ε)，其中ε是空符號(hào)。第十八頁(yè)，共一百九十八頁(yè)，2022年，8月28日2.規(guī)則2令U::=x|y|…|z|Uv是一組規(guī)則，它具有一個(gè)直接左遞歸右部且位于最后。該規(guī)則表明：語(yǔ)法類U的成員是由x或y或…或z其后隨有零個(gè)或多個(gè)v組成的。因此，可以把這組規(guī)則等價(jià)變換成U::=(x|y|…|z){v}。第十九頁(yè)，共一百九十八頁(yè)，2022年，8月28日算法：使用規(guī)則1，通過(guò)提取因子將規(guī)則改寫成滿足以下要求的形式：相對(duì)于某個(gè)非終結(jié)符號(hào)，至多只有一個(gè)直接左遞歸的右部；使用規(guī)則2，將規(guī)則改寫為不含直接左遞規(guī)的擴(kuò)充的BNF形式，以消除直接左遞歸。第二十頁(yè)，共一百九十八頁(yè)，2022年，8月28日例題：1.規(guī)則：E::=E+T|T（1）變形為：E::=T|E+T（2）由規(guī)則2，改寫為：E::=T{+T}2.規(guī)則：T::=T*F|T/F|F（1）規(guī)則1，改寫為：T::=F|T(*F|/F)（2）規(guī)則2，改寫為：T::=F{(*F|/F)}（3）刪去圓括號(hào)為：T::=F{*F|/F}第二十一頁(yè)，共一百九十八頁(yè)，2022年，8月28日②間接左遞歸要求：（1）文法沒(méi)有回路(即沒(méi)有形如A=>A的推導(dǎo))（2）不存在形如：A::=ε的規(guī)則。則可以按下述算法消除文法的左遞歸性。第二十二頁(yè)，共一百九十八頁(yè)，2022年，8月28日消除左遞歸算法(1)：①把G的非終結(jié)符整理成某種順序A1,A2,…,An。②fori:=1step1untilndobeginforj:=1step1untili-1do 把每個(gè)形如Ai::=Ajr的規(guī)則替換成 Ai::=δ1r│δ2r│…│δkr， 其中Aj::=δ1│δ2│…│δk是當(dāng)前的全部Aj規(guī)則；消除Ai規(guī)則中的直接左遞歸end③化簡(jiǎn)由②所得的文法，刪除所有多余規(guī)則。第二十三頁(yè)，共一百九十八頁(yè)，2022年，8月28日例題：有文法G[S]：S::=Qc|cQ::=Rb|b R::=Sa|a解：該文法有間接左遞歸。例如有S=>Qc=>Rbc=>Sabc + 即S=>Sabc（1）首先將非終結(jié)符號(hào)排列成：R，Q，S的順序。（2）將R代入Q得：Q::=Sab|ab|b將Q代入S得：S::=Sabc|abc|bc|c消除S的直接左遞歸：S::=(abc|bc|c){abc}（3）處理后的文法為：S::=(abc|bc|c){abc}Q::=Sab|ab|b R::=Sa|a

化簡(jiǎn)后的文法為：S::=(abc|bc|c){abc}第二十四頁(yè)，共一百九十八頁(yè)，2022年，8月28日消除左遞歸算法(2)[1]設(shè)G是一上下文無(wú)關(guān)文法，Vn＝{X1,X2,…Xn}，對(duì)每個(gè)形如Xi∷＝γ1|γ2|…|γm的產(chǎn)生式，根據(jù)γ的開(kāi)始符號(hào)作如下等價(jià)變換：（1）將“|”表示成“＋”，“∷＝”表示成“＝”（2）以非終結(jié)符號(hào)Xi引導(dǎo)的γi表示成：Xiαi（3）以終結(jié)符號(hào)引導(dǎo)的所有γi之“和”看成常數(shù)項(xiàng)，表示成：βi變形后的產(chǎn)生式為：Xi＝X1α1i+X2α2i+…+Xnαni+βi（如產(chǎn)生式不含有以Xi打頭的候選式，則相應(yīng)的系數(shù)α為φ）產(chǎn)生式集可表示為：

α11α12α1n

α21（X1，X2，…，Xn）＝（X1，X2，…，Xn）＋（β1，β2

，…βn）

αn1αnn

即：X=XA+B，且其通解為：X=BA*化簡(jiǎn)X=BA*

？[1]j蔣立源.編譯原理[M].西北工業(yè)大學(xué)出版社.P91－94第二十五頁(yè)，共一百九十八頁(yè)，2022年，8月28日消除左遞歸算法(2)設(shè)：

z11z12z1nεφφz21φεA*=Z=I=zn1znnφ

ε則可得以下矩陣方程組：

X=BZZ=I+AZ解以上方程組并化簡(jiǎn)即可得到不含左遞規(guī)的文法例題：S->Sa|Ab|aA->Sc第二十六頁(yè)，共一百九十八頁(yè)，2022年，8月28日第二十七頁(yè)，共一百九十八頁(yè)，2022年，8月28日(二)回溯問(wèn)題（P91）（1）消除回溯的理由前面介紹的帶回溯的自頂向下的分析方法實(shí)際上采用了一種窮盡一切可能的選擇試探法（三種回溯情形舉例：教材P91），回溯需要記住每一步分析的現(xiàn)場(chǎng)，浪費(fèi)時(shí)間和空間，因此，效率低，代價(jià)高。要構(gòu)造一個(gè)行之有效的自頂向下的語(yǔ)法分析程序，就必須消除回溯。（2）消除回溯的思路為了避免回溯，要求對(duì)文法的任何非終結(jié)符號(hào)，主要是對(duì)那些規(guī)則右部有多個(gè)選擇(候選式)的非終結(jié)符號(hào)，當(dāng)要用它去匹配輸入串時(shí)，能夠根據(jù)所面臨的輸入符號(hào)準(zhǔn)確地選用一個(gè)候選式去執(zhí)行匹配任務(wù)，并且工作的結(jié)果應(yīng)是確定的。即若此選擇匹配輸入串成功，那么這種匹配一定正確無(wú)誤；若此選擇無(wú)法完成匹配任務(wù)，則任何其他的選擇也肯定無(wú)法完成。第二十八頁(yè)，共一百九十八頁(yè)，2022年，8月28日（3）消除回溯的方法——預(yù)測(cè)與提左因子1、預(yù)測(cè)預(yù)測(cè)就是根據(jù)讀入的符號(hào)選擇滿足一定條件的候選式：使其第一個(gè)符號(hào)與讀頭下的符號(hào)相同，或該候選式可推導(dǎo)出的第一個(gè)符號(hào)與讀頭下符號(hào)相同。所以，對(duì)文法有如下要求：令G是一個(gè)不含左遞歸的文法，對(duì)每條規(guī)則中的每個(gè)候選式α定義它的終結(jié)首符集

First(α)={a|α=*>a…,a∈VT}第二十九頁(yè)，共一百九十八頁(yè)，2022年，8月28日設(shè)A∈VN，且Aα|β，如當(dāng)前用A去匹配輸入串，且輸入符號(hào)為a時(shí)，對(duì)A的候選式的選擇可以分成以下四種情況(當(dāng)A不能推出ε時(shí))：(1)若a∈First(α),而a!∈First(β)，選Aα;(2)若a!∈First(α),而a∈First(β)，選Aβ;(3)若a!∈First(α),而a!∈First(β)，輸入有錯(cuò)；(4)若a∈First(α),同時(shí)a∈First(β)，終結(jié)符首集兩兩相交，則需要改寫文法。第三十頁(yè)，共一百九十八頁(yè)，2022年，8月28日2、改造文法方法：提取公共左因子（a）假定關(guān)于非終結(jié)符A的產(chǎn)生式是：

Aαβ1|αβ2|…|αβn

那么可改寫成兩條規(guī)則：

AαA’

A’β1|β2|…|βn

（b）一般情況，若有關(guān)A的產(chǎn)生式是：

Aαδ1|αδ2|βδ3|βδ4|β

則可寫成：

AαA’|βA” A’δ1|δ2

A”δ3|δ4|ε

第三十一頁(yè)，共一百九十八頁(yè)，2022年，8月28日結(jié)論：

即當(dāng)規(guī)則右部具有n個(gè)選擇，從每一個(gè)選擇出發(fā)，都可以推導(dǎo)出一個(gè)以上的終結(jié)符號(hào)串。為了避免回溯，就要保證當(dāng)用非終結(jié)符號(hào)A去匹配輸入串時(shí)，能夠根據(jù)當(dāng)前讀入的符號(hào)準(zhǔn)確地選用它的一個(gè)候選式執(zhí)行任務(wù)。即對(duì)文法的要求是：對(duì)任意一個(gè)非終結(jié)符號(hào)，當(dāng)對(duì)應(yīng)的規(guī)則右部有多個(gè)選擇時(shí)，由各個(gè)選擇所推出的終結(jié)符號(hào)串的首符號(hào)集合要兩兩不相交。當(dāng)文法不滿足避免回溯的條件時(shí)，可以改寫文法，對(duì)規(guī)則右部反復(fù)提取左因子。第三十二頁(yè)，共一百九十八頁(yè)，2022年，8月28日

例題：規(guī)則：U::=xV|xW，（1）改寫為：U::=x(V|W)

（2）引入一個(gè)新的非終結(jié)符號(hào)Y，則規(guī)則變換成：

U::=xY Y::=V|W

改寫后的文法中，非終結(jié)符號(hào)U的右部只有一個(gè)選擇，而引入的新非終結(jié)符號(hào)Y具有兩個(gè)選擇V或W，且這兩個(gè)選擇所推出的終結(jié)符號(hào)串所組成的頭符號(hào)集合不相交。第三十三頁(yè)，共一百九十八頁(yè)，2022年，8月28日總結(jié)： 為了實(shí)現(xiàn)不帶回溯（確定）的自頂向下分析，對(duì)文法來(lái)說(shuō)，需要滿足下述兩個(gè)條件：①文法是非左遞歸的。②對(duì)文法的任一非終結(jié)符號(hào)，若對(duì)應(yīng)的規(guī)則右部有多個(gè)候選式時(shí)，那么，各選擇所推出的終結(jié)符號(hào)串的頭符號(hào)集合要兩兩不相交。第三十四頁(yè)，共一百九十八頁(yè)，2022年，8月28日4.2遞歸下降分析(遞歸子程序法)（一）基本思路

對(duì)文法中每個(gè)非終結(jié)符號(hào)U（分別代表一種語(yǔ)法成分）都編出一個(gè)子程序，以完成該非終結(jié)符號(hào)所對(duì)應(yīng)的語(yǔ)法成分的分析和識(shí)別任務(wù)。第三十五頁(yè)，共一百九十八頁(yè)，2022年，8月28日（二）非終結(jié)符號(hào)的語(yǔ)法分析子程序的功能

用該非終結(jié)符號(hào)的規(guī)則的右部符號(hào)串去匹配輸入串。分析過(guò)程：按文法規(guī)則自左向右地逐個(gè)處理每個(gè)文法符號(hào)，處理方法如下。(1)對(duì)規(guī)則中的終結(jié)符號(hào)直接與輸入匹配；(2)非終結(jié)符號(hào)則調(diào)用該符號(hào)的分析子程序來(lái)完成匹配，即當(dāng)編譯程序根據(jù)文法和當(dāng)前的輸入符號(hào)預(yù)測(cè)到下一個(gè)語(yǔ)法成分為U時(shí)，即預(yù)測(cè)到待匹配的輸入符號(hào)串可以和U推導(dǎo)出的符號(hào)串相匹配時(shí)，就確定U為子目標(biāo)，并調(diào)用分析和識(shí)別U的子程序來(lái)完成該子目標(biāo)的分析匹配工作。第三十六頁(yè)，共一百九十八頁(yè)，2022年，8月28日（三）特點(diǎn)

在分析和識(shí)別某個(gè)語(yǔ)法成份的過(guò)程中，有可能還要確立其它子目標(biāo)并調(diào)用相應(yīng)的分析子程序。只有在被調(diào)用的分析和識(shí)別某語(yǔ)法成分的子程序匹配輸入串成功并正確返回后，該語(yǔ)法成分的分析才能繼續(xù)進(jìn)行，并最終完成分析任務(wù)。所以該分析方法具有明顯的預(yù)測(cè)性特征，并在分析過(guò)程中向下確立多級(jí)子目標(biāo)。所以，該方法也被稱為面向預(yù)測(cè)和目標(biāo)的分析方法（Predictiveparser）。第三十七頁(yè)，共一百九十八頁(yè)，2022年，8月28日（四）例題

Z::=（U）|aUb U::=dZ|Ud|eProcedureZ;ifCLASS=‘（‘thenbegin nextsym; U; ifCLASS=‘）’then nextsym else errorend;elseifCLASS=‘a(chǎn)’thenbegin nextsym; U; ifclass=‘b’then nextsym else errorend;elseerror;第三十八頁(yè)，共一百九十八頁(yè)，2022年，8月28日ProcedureU;//首先要消除左遞歸：U::=(dZ|e)v8irrdtifCLASS=‘d’thenbegin nextsym; Z; whileCLASS=‘d’do nextsymend;elseifCLASS=‘e’thenbegin nexteym; whileCLASS=‘d’donextsymendelse error;第三十九頁(yè)，共一百九十八頁(yè)，2022年，8月28日4.3LL(1)分析方法基本思路：

相應(yīng)的語(yǔ)法分析將按自左至右的順序掃描輸入符號(hào)串，并在此過(guò)程中產(chǎn)生一個(gè)句子的最左推導(dǎo)。 其中第一個(gè)L表示從左向右掃描輸入符號(hào)串，第二個(gè)L表示生成最左推導(dǎo)，括號(hào)中的“1”，則表示在分析過(guò)程中，每進(jìn)行一步推導(dǎo)，只要向前查看一個(gè)輸入符號(hào)，便能確定當(dāng)前所應(yīng)選用的產(chǎn)生式(規(guī)則)。第四十頁(yè)，共一百九十八頁(yè)，2022年，8月28日4.3.1LL(1)分析器的邏輯結(jié)構(gòu)及工作過(guò)程（一）邏輯結(jié)構(gòu)（1）LL分析器的數(shù)學(xué)模型設(shè)CFGG=（VN，Σ，P，S），構(gòu)造PDA如下：M=（Q，Σ，H，δ，q0，z0，F(xiàn)），其中Q=F={q0}；H=VN∪Σ；z0=S；δ映射關(guān)系的構(gòu)造方法如下：對(duì)于形如Aω

產(chǎn)生式，有δ(q,ε,A)=(q,ω)，對(duì)于a∈Σ，

δ(q,a,a)=(q,ε)。

第四十一頁(yè)，共一百九十八頁(yè)，2022年，8月28日（2）LL分析器的邏輯結(jié)構(gòu)一個(gè)LL(1)分析器由一個(gè)總控程序、一張分析表和一個(gè)分析棧組成，其中：“輸入”即待分析的符號(hào)串。分析表M用一個(gè)矩陣(或二維數(shù)組)來(lái)表示，它概括了相應(yīng)文法的全部信息。矩陣的每一行與文法的一個(gè)非終結(jié)符號(hào)、終結(jié)符號(hào)或#相關(guān)聯(lián)，而每一列則與文法的一個(gè)終結(jié)符號(hào)或#相關(guān)聯(lián)。分析表元素M[A,a]指示分析器應(yīng)采取的動(dòng)作。其中A∈Vt∪Vn∪{#}，a∈Vt∪{#}第四十二頁(yè)，共一百九十八頁(yè)，2022年，8月28日（二）工作過(guò)程 第一步：分析開(kāi)始時(shí)，首先將符號(hào)#及文法的開(kāi)始符號(hào)S依次置于分析棧的底部，并把各指示器調(diào)整至起始位置，即初始格局為然后，反復(fù)執(zhí)行第二步的操作。第四十三頁(yè)，共一百九十八頁(yè)，2022年，8月28日第二步：設(shè)在分析的某一步，分析棧及余留的輸入符號(hào)串處于如下的格局：其中，X1，X2，…Xm為分析過(guò)程中所產(chǎn)生的文法符號(hào)，此時(shí)，可視棧頂符號(hào)Xm的不同情況，分別進(jìn)行如下操作：第四十四頁(yè)，共一百九十八頁(yè)，2022年，8月28日若Xm∈VN，則以Xm及ai組成符號(hào)對(duì)(Xm,ai)查分析表M。設(shè)M[Xm,ai]為一產(chǎn)生式，譬如說(shuō)Xm→UVW，此時(shí)將Xm從分析棧中退出，并將UVW按反序推入棧中(即用該產(chǎn)生式推導(dǎo))，從而得到新的格局但若M[Xm,ai]=“ERROR”，則調(diào)用出錯(cuò)處理程序進(jìn)行處理；第四十五頁(yè)，共一百九十八頁(yè)，2022年，8月28日若Xm=ai≠#，則表明棧頂符號(hào)已與當(dāng)前正掃描的輸入符號(hào)匹配，此時(shí)應(yīng)將Xm(即ai)從棧中退出，并將輸入符號(hào)指示器向前推進(jìn)一個(gè)位置；若Xm=ai=#，則表明輸入串已完全得到匹配，此時(shí)即可宣告分析成功而結(jié)束分析工作。第四十六頁(yè)，共一百九十八頁(yè)，2022年，8月28日分析流程如下：第四十七頁(yè)，共一百九十八頁(yè)，2022年，8月28日舉例：

原始文法：消除左遞歸：第四十八頁(yè)，共一百九十八頁(yè)，2022年，8月28日第四十九頁(yè)，共一百九十八頁(yè)，2022年，8月28日第五十頁(yè)，共一百九十八頁(yè)，2022年，8月28日4.3.2LL(1)分析表的構(gòu)造方法

LL(1)分析算法對(duì)不同的LL(1)文法都相同。即總控部分相同，僅僅是分析表不同，而且總控程序十分簡(jiǎn)單，容易實(shí)現(xiàn)。所以，LL(1)分析方法的核心是構(gòu)造LL（1）分析表。第五十一頁(yè)，共一百九十八頁(yè)，2022年，8月28日（一）定義符號(hào)串α的首符號(hào)集假定α是文法G的任一符號(hào)串，即α∈(VT∪VN)*，定義：

FIRST(α)={a|α=*>a…，a∈VT}特別是，若α=>ε，則規(guī)定：ε∈FIRST(α)，即FIRST(α)是從α可能推導(dǎo)出的所有開(kāi)頭終結(jié)符號(hào)或可能的ε。第五十二頁(yè)，共一百九十八頁(yè)，2022年，8月28日（二）定義非終結(jié)符的尾符號(hào)集假定S是文法的開(kāi)始符號(hào)，對(duì)于G的任何非終結(jié)符A，定義：

FOLLOW(A)={a|S=*>…Aa…,a∈VT}特別是，若S=*>…A，則規(guī)定#∈FOLLOW(A)。即FOLLOW(A)是所有句型中能夠緊接A之后的終結(jié)符或#。（三）定義SELECT集（教材P78）對(duì)文法的產(chǎn)生式X→α，如α≠*>ε，則SELECT(X→α)＝FIRST(α)如α=*>ε，則SELECT(X→α)＝

(FIRST(α)–{ε})∪FOLLOW(X)第五十三頁(yè)，共一百九十八頁(yè)，2022年，8月28日（四）構(gòu)造First集的算法1．定義法若X∈VT，則FIRST(X)={X}。若X∈VN，對(duì)形如X→aα的產(chǎn)生式(a∈VT)，或形如X→ε的產(chǎn)生式，把a(bǔ)或ε加進(jìn)FIRST(X)。設(shè)G中有形如X→Y1Y2…Yk的產(chǎn)生式，若Y1∈VN，則把FIRST(Y1)中的一切非ε的符號(hào)加進(jìn)FIRST(X)；對(duì)于一切2≤i≤k，若Y1，Y2…Yi-1均為非終結(jié)符，且ε∈FIRST(Yj)，1≤j≤i-1，則將FIRST(Yi)中的一切非ε的符號(hào)加進(jìn)FIRST(X)；若對(duì)一切1≤j≤k，均有ε∈FIRST(Yj)，則將ε加進(jìn)FIRST(X)。第五十四頁(yè)，共一百九十八頁(yè)，2022年，8月28日２．關(guān)系圖法（1）首先求出能推出ε的非終結(jié)符號(hào)第五十五頁(yè)，共一百九十八頁(yè)，2022年，8月28日（2）然后按照下面步驟求解第五十六頁(yè)，共一百九十八頁(yè)，2022年，8月28日 對(duì)于文法G的任一符號(hào)串α=X1X2…Xn可按如下的步驟構(gòu)造相應(yīng)的FIRST(α)。置FIRST(α)=φ；把FIRST(X1)中的一切非ε符號(hào)加進(jìn)FIRST(α)；依次進(jìn)行下述操作：若ε∈FIRST(X1)，將FIRST(X2)中的一切非ε的符號(hào)加進(jìn)FIRST(α)；若ε屬于FIRST(X1)及FIRST(X2)，將FIRST(X3)中一切非ε的符號(hào)加進(jìn)FIRST(α)；以此類推。最后，若對(duì)于1≤i≤n，ε∈FIRST(Xi)，則將ε加進(jìn)FIRST(α)。第五十七頁(yè)，共一百九十八頁(yè)，2022年，8月28日（五）構(gòu)造Follow集的算法1．定義法對(duì)于文法的開(kāi)始符號(hào)，令#∈FOLLOW(S)。若G中有形如A→αBβ的產(chǎn)生式，且β≠ε，則將FIRST(β)中的一切非ε符號(hào)加進(jìn)FOLLOW(B)。(即FOLLOW不含ε)若G中有形如A→αB或A→αBβ的產(chǎn)生式，且ε∈FIRST(β)，則FOLLOW(A)中的全部元素均屬于FOLLOW(B)。第五十八頁(yè)，共一百九十八頁(yè)，2022年，8月28日2．關(guān)系圖法第五十九頁(yè)，共一百九十八頁(yè)，2022年，8月28日（六）構(gòu)造分析表的算法分析表M是一個(gè)二維表，每一行對(duì)應(yīng)一個(gè)文法符號(hào)，每一列對(duì)應(yīng)一個(gè)終結(jié)符號(hào)，元素的賦值規(guī)則如下：（1）對(duì)規(guī)則A→α，F(xiàn)RIST（α）中的每一終結(jié)符a，置M[A,a]=“POP，PUSH（α’）”。其中α’為α的倒置。若ε∈FIRST（α），則對(duì)屬于FOLLOW(A)的每一終結(jié)符號(hào)b或#，置M[A,b]=“A→ε”。（2）把M中所有M[a,a]置為“POP，NEXTSYM”。（3）把M中所有不能按以上規(guī)則定義的元素均置為“ERROR”（出錯(cuò)）。

簡(jiǎn)化表示：可以省略分析表中所有終結(jié)符號(hào)對(duì)應(yīng)的行。第六十頁(yè)，共一百九十八頁(yè)，2022年，8月28日定義：一個(gè)文法G，若它的分析表M不含多重定義元素，則稱它是一個(gè)LL(1)文法。一個(gè)LL(1)文法是無(wú)二義的，它所定義的語(yǔ)言恰好就是它的分析表M所能識(shí)別的全部句子?？梢宰C明，一個(gè)文法G是LL(1)文法，當(dāng)且僅當(dāng)對(duì)于G的每一個(gè)非終結(jié)符A的任何兩條不同規(guī)則A::=α|β，下面的條件成立：（1）FIRST(α)∩FIRST(β)=φ，即由α和β推導(dǎo)不出以同一終結(jié)符a為首字符的符號(hào)串；且不應(yīng)該都能推出空字符ε。（2）假若β=*>ε，則FIRST(α)∩FOLLOW(A)=φ；即若β=*>ε，則α所能推出的串的首符號(hào)不應(yīng)在FOLLOW(A)中。教材P78:（即SELECT(A::=α)與SELECT(A::=β)不相交，且兩者不能同時(shí)推出ε）第六十一頁(yè)，共一百九十八頁(yè)，2022年，8月28日主要結(jié)論：任何LL(1)文法都是無(wú)二義性的。若一文法中含有左遞歸的非終結(jié)符號(hào)，則它必然是非LL(1)文法。存在一種算法，它能判定任一文法是否為L(zhǎng)L(1)文法。存在一種算法，它能判定任意兩個(gè)LL(1)文法是否產(chǎn)生相同的語(yǔ)言。不存在這樣的算法，它能判定任意上下文無(wú)關(guān)語(yǔ)言能否由LL(1)文法產(chǎn)生。非LL(1)語(yǔ)言是存在的。第六十二頁(yè)，共一百九十八頁(yè)，2022年，8月28日一、非LL（1）文法的改造

（四種改造情形舉例：教材P85）,ε第六十三頁(yè)，共一百九十八頁(yè)，2022年，8月28日二、非LL（1）文法第六十四頁(yè)，共一百九十八頁(yè)，2022年，8月28日4.4自底向上分析方法（一）基本思路

自底向上的分析方法，也稱為“移進(jìn)—?dú)w約”法，這種方法的一般過(guò)程是：設(shè)置一個(gè)寄存符號(hào)的先進(jìn)后出棧，稱為符號(hào)棧，用來(lái)記錄分析的歷史和指示分析的下一步動(dòng)作。第六十五頁(yè)，共一百九十八頁(yè)，2022年，8月28日（二）分析過(guò)程

在分析進(jìn)行時(shí)，把輸入符號(hào)一個(gè)個(gè)地按掃描順序移進(jìn)棧里，當(dāng)棧頂符號(hào)串形成一個(gè)句柄(為某條規(guī)則的右部)時(shí)，就進(jìn)行一次歸約，把棧頂構(gòu)成句柄的那個(gè)符號(hào)串用相應(yīng)規(guī)則左部的非終結(jié)符號(hào)來(lái)代替。接著再檢查在棧頂是否又出現(xiàn)了新的句柄，若出現(xiàn)新的句柄，就再進(jìn)行歸約；若沒(méi)有形成新的句柄，則再?gòu)妮斎敕?hào)串移進(jìn)新的符號(hào)，……，如此繼續(xù)直到整個(gè)輸入符號(hào)串處理完畢。最終如棧底為識(shí)別符號(hào)，則所分析的輸入符號(hào)串為合法的句子，報(bào)告成功；否則，是不合法的符號(hào)串，報(bào)告錯(cuò)誤。第六十六頁(yè)，共一百九十八頁(yè)，2022年，8月28日例1：有文法G[S]： (1)S::=aAcBe (2)A::=b (3)A::=Ab (4)B::=d分析符號(hào)串a(chǎn)bbcde第六十七頁(yè)，共一百九十八頁(yè)，2022年，8月28日步驟棧內(nèi)輸入串輸出帶動(dòng)作0#abbcde#1#abbcde#移進(jìn)2#abbcde#移進(jìn)3#aAbcde#2歸約4#aAbcde#移進(jìn)5#aAcde#2,3歸約6#aAcde#移進(jìn)7#aAcde#移進(jìn)8#aAcBe#2,3,4歸約9#aAcBe#移進(jìn)10#S#2,3,4,1歸約11識(shí)別成功abbcde的移進(jìn)－歸約過(guò)程：第六十八頁(yè)，共一百九十八頁(yè)，2022年，8月28日abbcde語(yǔ)法樹(shù)的構(gòu)造過(guò)程：第六十九頁(yè)，共一百九十八頁(yè)，2022年，8月28日（三）關(guān)鍵問(wèn)題在自底向上分析中，如何尋找或確定一個(gè)句型的句柄，是構(gòu)造一個(gè)自左向右掃描、自底向上分析方法必須要解決的一個(gè)關(guān)鍵問(wèn)題。 下面介紹較為常用的兩種方法： （1）算符優(yōu)先分析方法 （2）LR分析法第七十頁(yè)，共一百九十八頁(yè)，2022年，8月28日4.5算符優(yōu)先分析法4.5.1方法概述4.5.2直觀算符優(yōu)先分析法4.5.3算符優(yōu)先分析法的進(jìn)一步討論第七十一頁(yè)，共一百九十八頁(yè)，2022年，8月28日4.5.1方法概述思路：

算符優(yōu)先分析法是仿照算術(shù)式的四則運(yùn)算過(guò)程而設(shè)計(jì)的一種語(yǔ)法分析方法。該方法首先要規(guī)定運(yùn)算符之間的優(yōu)先關(guān)系和結(jié)合性質(zhì)，然后利用這種關(guān)系，通過(guò)比較相鄰運(yùn)算符的優(yōu)先順序來(lái)確定句型的“句柄”和進(jìn)行歸約。特點(diǎn)：

簡(jiǎn)單直觀，最適用于表達(dá)式分析，宜于手工實(shí)現(xiàn)。第七十二頁(yè)，共一百九十八頁(yè)，2022年，8月28日例：有文法G[E]： E::=E+E|E-E|E*E|E/E|(E)|i試分析句子i+i-i*(i+i)根據(jù)運(yùn)算符優(yōu)先順序和結(jié)合原則的規(guī)定對(duì)句子i+i-i*(i+i)進(jìn)行歸約，歸約過(guò)程為：①#i+i-i*(i+i)# ②#E+i-i*(i+i)# ③#E+E-i*(i+i)#④#E-i*(i+i)# ⑤#E-E*(i+i)# ⑥#E-E*(E+i)#⑦#E-E*(E+E)# ⑧#E-E*(E)# ⑨#E-E*E#⑩#E-E# (11)#E#該歸約過(guò)程是唯一的。第七十三頁(yè)，共一百九十八頁(yè)，2022年，8月28日在上述的整個(gè)歸約過(guò)程中，起決定作用的是相鄰兩個(gè)終結(jié)符的優(yōu)先關(guān)系，所以應(yīng)用算符優(yōu)先分析法自底向上地分析句子，解決了前面提到的問(wèn)題，即：（1）可以只根據(jù)相鄰運(yùn)算符的優(yōu)先關(guān)系，就能方便地并且唯一地確定歸約的“句柄”；（2）同時(shí)還可以發(fā)現(xiàn)：該方法可以用來(lái)分析二義性文法所產(chǎn)生的語(yǔ)言。 上述文法是二義性的，但用算符優(yōu)先法分析其句子時(shí)，其歸約過(guò)程是唯一的。我們所規(guī)定的運(yùn)算符之間的優(yōu)先順序和左結(jié)合的原則，就是避免二義性的充分條件。第七十四頁(yè)，共一百九十八頁(yè)，2022年，8月28日4.5.2直觀算符優(yōu)先分析法（1）算符優(yōu)先分析的關(guān)鍵在于定義任何兩個(gè)可能相鄰的終結(jié)符a和b之間的優(yōu)先關(guān)系 要求對(duì)于任何兩個(gè)可能相繼出現(xiàn)的終結(jié)符a和b具有形式：“…ab…”或“…aQb…”，Q∈VN，定義a，b之間有3種關(guān)系：(1)a＜b a的優(yōu)先級(jí)低于b(2)a≈b a的優(yōu)先級(jí)等于b(3)a＞b a的優(yōu)先級(jí)高于b如果a和b在任何情況下不可能相繼出現(xiàn)，則a，b之間不可比，即無(wú)關(guān)系；要與算術(shù)中的‘<’或‘>’區(qū)分，a＞b并不意味著b＜a，比如棧內(nèi)的‘＋’大于棧外‘－’，同時(shí)棧內(nèi)‘－’也大于棧外‘＋’。第七十五頁(yè)，共一百九十八頁(yè)，2022年，8月28日優(yōu)先關(guān)系矩陣示例內(nèi)外+*↑

i()#+＞＜＜＜＜＞＞*＞＞＜＜＜＞＞↑

＞＞＜＜＜＞＞i＞＞＞＞＞(＜＜＜＜＜≈)＞＞＞＞＞#＜＜＜＜＜≈第七十六頁(yè)，共一百九十八頁(yè)，2022年，8月28日（2）直觀算符優(yōu)先分析法的基本步驟使用兩個(gè)工作棧OPTR（寄存運(yùn)算符）和OPND（存放“操作數(shù)”和“運(yùn)算結(jié)果”）；開(kāi)始，將OPTR棧底置為‘#’，輸入串尾設(shè)置右界符‘#’，OPND初始為空；令θ代表OPTR現(xiàn)行棧頂符號(hào)，a存放新輸入的符號(hào)；則分析算法的基本步驟如下：第七十七頁(yè)，共一百九十八頁(yè)，2022年，8月28日(1)把下一個(gè)輸入符號(hào)讀至a中；(2)若a為運(yùn)算數(shù)i，則把它壓入OPND，轉(zhuǎn)(1)；(3)若θ＞a，則調(diào)用θ的處理程序，處理子表達(dá)式E(1)θE(2)，同時(shí)，把θ從OPTR棧頂彈出，然后重新進(jìn)入(3)；(4)若θ≈a，則按優(yōu)先關(guān)系表有兩種可能： ①θ=‘（’，a=‘）’，此時(shí)彈出OPTR頂?shù)? ‘（’，放棄a中的‘）’，然后轉(zhuǎn)(1)； ②θ=a=‘#’，結(jié)束；(5)若θ＜a，把a(bǔ)移進(jìn)OPTR棧，轉(zhuǎn)（1）;(6)θ與a不存在優(yōu)先關(guān)系，則輸入串有錯(cuò)。第七十八頁(yè)，共一百九十八頁(yè)，2022年，8月28日4.5.3算符優(yōu)先分析法的進(jìn)一步討論(一)算符優(yōu)先文法定義1：設(shè)有一文法G，如果G中沒(méi)有形如U::=…VW…的規(guī)則，其中V和W是非終結(jié)符號(hào)，那么，就稱G為算符文法（OG文法）第七十九頁(yè)，共一百九十八頁(yè)，2022年，8月28日定義2 設(shè)G是一OG文法，并令a和b是任意兩個(gè)終結(jié)符號(hào)，U、V、W是非終結(jié)符號(hào)。終結(jié)符號(hào)的優(yōu)先關(guān)系定義如下：（1）a

≈b，當(dāng)且僅當(dāng)文法中有形如U::=…ab…或U::=…aVb…的規(guī)則；(a、b同時(shí)歸約)（2）a＜b，當(dāng)且僅當(dāng)文法中有形如U::=…aW…的規(guī)則，其中W=+>b…或W=+>Vb…；（b歸約在前）（3）a＞b，當(dāng)且僅當(dāng)文法中有形如U::=…Wb…的規(guī)則，其中W=+>…a或W=+>…aV。（a歸約在前）第八十頁(yè)，共一百九十八頁(yè)，2022年，8月28日三種優(yōu)先關(guān)系和歸約的先后順序的圖形解釋（參見(jiàn)教材P108）第八十一頁(yè)，共一百九十八頁(yè)，2022年，8月28日定義3

設(shè)有一OG文法，如果在任意兩個(gè)終結(jié)符號(hào)之間，在＜、＞和≈中至多只有一種關(guān)系成立，那么，這樣的OG文法稱為算符優(yōu)先文法(OPG文法)。第八十二頁(yè)，共一百九十八頁(yè)，2022年，8月28日(二)構(gòu)造優(yōu)先關(guān)系矩陣定義1

非終結(jié)符號(hào)U的FIRSTVT集合

FIRSTVT(U)={a|U=*>a…或U=*>Va…}定義2

非終結(jié)符號(hào)U的LASTVT集合

LASTVT(U)={a|U=*>…a或U=*>…aV}第八十三頁(yè)，共一百九十八頁(yè)，2022年，8月28日

（1）構(gòu)造FIRSTVT算法（LASTVT的構(gòu)造算法與此類似）ProcedureInsert(U,b);ifnotF[U,b]then Begin F[U,b]:=TRUE;Push(U,b);//把(U,b)下推進(jìn)STACK End第八十四頁(yè)，共一百九十八頁(yè)，2022年，8月28日主程序{F為2維數(shù)組，如b∈FIRSTVT(U)，則F[U,b]:=TRUE}

BEGINFor每個(gè)非終結(jié)符號(hào)U和終結(jié)符號(hào)bdo F[U,b]:=FALSE；{初始化為0}For每個(gè)形如U::=b…或U::=Vb…的規(guī)則 doInsert(U,b)WhileSTACK非空do Begin Pop(V,b){記STACK棧頂為(V,b)，彈出} For每條形如U::=V…的規(guī)則do Insert(U,b) EndofWhile;END第八十五頁(yè)，共一百九十八頁(yè)，2022年，8月28日例子：給定如下表達(dá)式文法G[E]:(0)E’→#E#，(1)E→E+T,(2)E→T,(3)T→T*F,(4)T→F,(5)F→P↑F|P,(6)P→(E),(7)P→i非終結(jié)符號(hào)的FIRSTVTLASTVT如右：第八十六頁(yè)，共一百九十八頁(yè)，2022年，8月28日（2）用圖形法求FIRSTVT的算法（教材P105）圖形法求解結(jié)果如右圖所示：第八十七頁(yè)，共一百九十八頁(yè)，2022年，8月28日（3）構(gòu)造優(yōu)先關(guān)系表算法

For每條規(guī)則U::=x1x2…xnDOFori:=1TOn-1DO BEGIN IFxi和xi+1均為終結(jié)符號(hào)THEN 置xi

≈xi+1； IFxi為終結(jié)符號(hào)而xi+1為非終結(jié)符THEN 置xi

≈xi+2； IFxi為終結(jié)符號(hào)而xi+1為非終結(jié)符THEN ForFIRSTVT(xi+1)中的每個(gè)bDO置xi

＜b； IFxi為非終結(jié)符號(hào)而xi+1為終結(jié)符THEN ForLASTVT(xi)中的每個(gè)aDO置a

＞

xi+1； End第八十八頁(yè)，共一百九十八頁(yè)，2022年，8月28日例：設(shè)文法G[S]的產(chǎn)生式為：

SaAcBe AAb|b BdFIRSTVT(S)={a}FIRSTVT(A)=FIRSTVT(B)=gyuy2xuLASTVT(S)={e}LASTVT(A)=LASTVT(B)=btt4kfeabcdea＜≈b＞＞c＜≈d＞e第八十九頁(yè)，共一百九十八頁(yè)，2022年，8月28日(三)算符優(yōu)先分析算法設(shè)計(jì)定義4

文法句型的素短語(yǔ)是滿足以下條件的一個(gè)短語(yǔ)，它至少包含一個(gè)終結(jié)符號(hào)，并且除它自身之外，不再包含其他素短語(yǔ)。第九十頁(yè)，共一百九十八頁(yè)，2022年，8月28日定理1 一個(gè)OPG句型的最左素短語(yǔ)是滿足下列條件的最左子串Njaj…NiaiNi+1

aj-1

＜aj aj

≈aj+1,aj+1

≈aj+2,…,ai-2

≈ai-1,

ai-1

≈ai

ai

＞ai+1出現(xiàn)在aj左端或ai右端的非終結(jié)符號(hào)一定屬于這個(gè)素短語(yǔ)。舉例：P116圖6.6、圖6.7第九十一頁(yè)，共一百九十八頁(yè)，2022年，8月28日例子：

P110與規(guī)范歸約的比較：第九十二頁(yè)，共一百九十八頁(yè)，2022年，8月28日繼續(xù)往前掃描尋找素短語(yǔ)尾找到素短語(yǔ)尾往棧底搜索找素短語(yǔ)頭找到素短語(yǔ)頭S為分析棧，k為棧頂指針。第九十三頁(yè)，共一百九十八頁(yè)，2022年，8月28日注意：

(1)在查找所應(yīng)歸約的最左素短語(yǔ)的過(guò)程中，沒(méi)有用到非終結(jié)符號(hào)，因此，在符號(hào)棧中放不放相應(yīng)的非終結(jié)符號(hào)，對(duì)分析過(guò)程中尋找最左素短語(yǔ)沒(méi)有影響。

(2)與歸約為某個(gè)非終結(jié)符號(hào)相對(duì)應(yīng)，語(yǔ)義程序分配一個(gè)工作單元來(lái)存放該子表達(dá)式的運(yùn)算結(jié)果。所以，對(duì)語(yǔ)義處理程序來(lái)說(shuō)，也不需要知道真正的非終結(jié)符號(hào)的名字。第九十四頁(yè)，共一百九十八頁(yè)，2022年，8月28日算符優(yōu)先函數(shù)及其構(gòu)造方法為什么要構(gòu)造優(yōu)先函數(shù)？

對(duì)具有n個(gè)終結(jié)符號(hào)（包括句子界符＃）的算符優(yōu)先文法，其優(yōu)先關(guān)系矩陣需要n2的存儲(chǔ)空間。是否可能將空間消耗控制在n的線性復(fù)雜度范圍內(nèi)。第九十五頁(yè)，共一百九十八頁(yè)，2022年，8月28日算符優(yōu)先函數(shù)及其構(gòu)造方法

把每一個(gè)終結(jié)符θ與一對(duì)整數(shù)f(θ)、g(θ)聯(lián)系在一起，其中f(θ)為終結(jié)符θ在棧內(nèi)時(shí)的優(yōu)先數(shù)，g(θ)為終結(jié)符θ在棧外的優(yōu)先數(shù)。 （1）f(θ)與g(θ)的值應(yīng)滿足如下關(guān)系若θ1＜θ2

則f(θ1)<g(θ2)若θ1≈θ2

則f(θ1)=g(θ2)若θ1＞θ2

則f(θ1)>g(θ2)2個(gè)優(yōu)先函數(shù)所需空間為2n第九十六頁(yè)，共一百九十八頁(yè)，2022年，8月28日（2）優(yōu)先表與優(yōu)先函數(shù)的關(guān)系1)優(yōu)先函數(shù)并不等價(jià)于優(yōu)先表，在優(yōu)先表中沒(méi)有關(guān)系的終結(jié)符對(duì)存在優(yōu)先函數(shù)。2)有些優(yōu)先表不存在對(duì)應(yīng)的優(yōu)先函數(shù)f和g。3)如果存在一對(duì)優(yōu)先函數(shù)，則存在無(wú)窮多對(duì)優(yōu)先函數(shù)。根據(jù)不同的算法從優(yōu)先表轉(zhuǎn)換推演出優(yōu)先函數(shù)時(shí)也可能得到不同的結(jié)果。第九十七頁(yè)，共一百九十八頁(yè)，2022年，8月28日（3）從優(yōu)先表轉(zhuǎn)換為優(yōu)先函數(shù)的算法算法一：逐次加1法1)對(duì)所有終結(jié)符a(包括#)，令f(a)=g(a)=c2)對(duì)所有終結(jié)符： 若a＞b且f(a)≤g(b)，則f(a):=g(b)+1

若a＜b且f(a)≥g(b)，則g(b):=f(a)+1

若a≈b且f(a)≠g(b)，則f(a)=g(b)=max(f(a)，g(b))3)重復(fù)步驟(2)直至f(a)，g(b)不再改變?yōu)橹?。如果f(a)或g(b)的任一值≥2n+c而步驟(2)還沒(méi)結(jié)束，表示優(yōu)先函數(shù)不存在。第九十八頁(yè)，共一百九十八頁(yè)，2022年，8月28日例：由G(E)文法的優(yōu)先表構(gòu)造優(yōu)先函數(shù)的過(guò)程/P118IO+*↑

i()#+＞＜＜＜＜＞＞*＞＞＜＜＜＞＞↑

＞＞＜＜＜＞＞i＞＞＞＞＞(＜＜＜＜＜≈)＞＞＞＞＞#＜＜＜＜＜≈第1步：f(+)與g(+)、g(*)、…g(#)比較，按算法調(diào)整對(duì)應(yīng)的f、g值；第2步：f(*)與g(+)、g(*)、…g(#)比較，按算法調(diào)整對(duì)應(yīng)的f、g值；…第n步：f(#)與g(+)、g(*)、…g(#)比較，按算法調(diào)整對(duì)應(yīng)的f、g值；第九十九頁(yè)，共一百九十八頁(yè)，2022年，8月28日以上優(yōu)先函數(shù)的計(jì)算迭代三次收斂。不難看出對(duì)優(yōu)先函數(shù)每個(gè)元素的值都增加同一個(gè)常數(shù)，優(yōu)先關(guān)系不變，所以同一個(gè)文法的優(yōu)先關(guān)系矩陣對(duì)應(yīng)的優(yōu)先函數(shù)可以不唯一。

但是也有一些優(yōu)先關(guān)系矩陣中的優(yōu)先關(guān)系是唯一的，卻不存在優(yōu)先函數(shù)。例如下面的優(yōu)先關(guān)系矩陣：第一百頁(yè)，共一百九十八頁(yè)，2022年，8月28日構(gòu)造算法二：Bell有向圖方法1)對(duì)每個(gè)終結(jié)符a（包括#），令其對(duì)應(yīng)兩個(gè)節(jié)點(diǎn)fa和ga，畫一張以所有fa和ga為節(jié)點(diǎn)的有向圖，如果a＞b或a≈b，就從fa畫一弧指向gb，若a＜b或a≈b，則從gb畫一弧指向fa；2)令f(a)等于節(jié)點(diǎn)fa可達(dá)的節(jié)點(diǎn)數(shù)(包括自身)，令g(a)等于節(jié)點(diǎn)ga可達(dá)的節(jié)點(diǎn)數(shù)(包括自身)；3)檢查構(gòu)造出來(lái)的f(a)和g(a)，若與優(yōu)先表符合則優(yōu)先函數(shù)存在，否則不存在。第一百零一頁(yè)，共一百九十八頁(yè)，2022年，8月28日Bell有向圖舉例：i*+#fg67654322第一百零二頁(yè)，共一百九十八頁(yè)，2022年，8月28日4.6LR分析方法4.6.1概述4.6.2LR(0)分析器4.6.3SLR(1)分析器4.6.4規(guī)范LR(1)分析器4.6.5規(guī)范LALR(1)分析器4.6.6語(yǔ)法分析程序的自動(dòng)生成工具—YACC第一百零三頁(yè)，共一百九十八頁(yè)，2022年，8月28日基本思路：

LR(K)分析器從左到右掃描所給定的輸入串，并以相反的方向構(gòu)造該輸入串的最右推導(dǎo)(Right-mostDerive即規(guī)范推導(dǎo))。LR(K)分析器根據(jù)分析棧的內(nèi)容以及向前查看輸入串中K個(gè)符號(hào)來(lái)決定分析動(dòng)作。特點(diǎn)：（1）分析器對(duì)源程序中錯(cuò)誤的診斷靈敏；（2）分析器對(duì)文法適應(yīng)性強(qiáng)，文法分析能力強(qiáng)；（3）分析器結(jié)構(gòu)復(fù)雜，K越大，相應(yīng)的分析器愈復(fù)雜。當(dāng)K＝0時(shí)，表示在確定分析動(dòng)作時(shí)不需向前查看符號(hào)，LR（0）分析器是LR分析器中最簡(jiǎn)單的一種。LR（0）分析器分析能力弱，實(shí)用性差，一般僅作為構(gòu)造更復(fù)雜的LR分析器的基礎(chǔ)。第一百零四頁(yè)，共一百九十八頁(yè)，2022年，8月28日LR分析器的邏輯結(jié)構(gòu)和工作原理

LR分析器的數(shù)學(xué)模型是下推自動(dòng)機(jī)。該下推機(jī)具有一個(gè)輸入機(jī)構(gòu)，一個(gè)分析棧和一個(gè)有窮的控制系統(tǒng)。一般來(lái)說(shuō)，其控制系統(tǒng)是一個(gè)具有多狀態(tài)的有窮狀態(tài)機(jī)。 總控程序輸入帶輸出帶下推棧下推自動(dòng)機(jī)邏輯結(jié)構(gòu)動(dòng)作表狀態(tài)轉(zhuǎn)移表4.6.1概述第一百零五頁(yè)，共一百九十八頁(yè)，2022年，8月28日1、下推自動(dòng)機(jī)的定義

M=〈θ，∑，Τ，R，q0，Z0

，F(xiàn)〉

θ：有窮狀態(tài)集

Τ

：堆棧字母表 ∑：輸入字母表

R：轉(zhuǎn)換關(guān)系

(θ×(∑∪{ε})×Τ)→(θ×Τ*) q0

：初態(tài)

Z0

：初始堆棧，符號(hào)Z0∈Τ F：為θ的子集，是控制器的終態(tài)集第一百零六頁(yè)，共一百九十八頁(yè)，2022年，8月28日2、有窮自動(dòng)機(jī)狀態(tài)的分類有窮狀態(tài)集Θ中的狀態(tài)分成3類①讀狀態(tài)，當(dāng)讀一個(gè)終結(jié)符或非終結(jié)符時(shí)，發(fā)生由一個(gè)狀態(tài)到另一狀態(tài)的狀態(tài)轉(zhuǎn)移。②歸約狀態(tài)，識(shí)別出當(dāng)前句型的活前綴的句柄部分。處于歸約狀態(tài)時(shí)，檢測(cè)出來(lái)的句柄將歸約為一個(gè)非終結(jié)符號(hào)。③識(shí)別狀態(tài)，輸入串被分析器成功識(shí)別。第一百零七頁(yè)，共一百九十八頁(yè)，2022年，8月28日3、LR(0)分析棧的結(jié)構(gòu)

LR(0)分析器的分析棧是一個(gè)符號(hào)對(duì)偶棧。對(duì)偶的第一個(gè)元素是文法符號(hào)。對(duì)偶的第二個(gè)元素是分析器掃描一個(gè)文法符號(hào)時(shí)所進(jìn)入的狀態(tài)。XmXm-1………X1#SmSm-1………S1S0文法符號(hào)狀態(tài)

第一百零八頁(yè)，共一百九十八頁(yè)，2022年，8月28日4、LR(0)分析過(guò)程

LR(0)分析器由總控程序和分析表兩部分組成。分析開(kāi)始時(shí)，棧內(nèi)的初始狀態(tài)為S0，即與分析器有關(guān)的有窮控制的開(kāi)動(dòng)狀態(tài)。（1）當(dāng)分析器處于讀狀態(tài)時(shí)，它將當(dāng)前掃描到的符號(hào)壓入堆棧，并執(zhí)行由所讀符號(hào)所指示的狀態(tài)轉(zhuǎn)移，并將該后繼狀態(tài)也壓入棧內(nèi)；（2）當(dāng)分析器處于歸約狀態(tài)時(shí)，將對(duì)偶棧中與句柄對(duì)應(yīng)的部分彈出進(jìn)行歸約，然后執(zhí)行讀操作，讀入歸約后的符號(hào)并壓入堆棧。如果歸約到的符號(hào)為識(shí)別符號(hào)，則分析器接受所給定的符號(hào)串并停機(jī)；否則，歸約生成的左部符號(hào)和當(dāng)前棧頂狀態(tài)將確定下一個(gè)狀態(tài)轉(zhuǎn)移。第一百零九頁(yè)，共一百九十八頁(yè)，2022年，8月28日一、初始情況二、一般過(guò)程分析棧輸入帶對(duì)應(yīng)“句型”S0#a1a2…an#

a1a2…an分析棧輸入帶對(duì)應(yīng)“句型”S0S1…Sm

#

X1…Xmaiai＋1…an#

X1…Xmaiai＋1…an第一百一十頁(yè)，共一百九十八頁(yè)，2022年，8月28日（1）Ifaction[sm,ai]=si(shiftsi)then分析格局變?yōu)椋?）Ifaction[sm,ai]=ri(Reducei)then表示用第i個(gè)產(chǎn)生式A→Xm-(k-1)…Xm進(jìn)行歸約，分析格局變?yōu)榉治鰲］斎霂0S1…Sm－k

#X1…Xm－kAaiai＋1…an#

分析棧輸入帶S0S1…SmSi#X1…Xmaiai＋1…an#

第一百一十一頁(yè)，共一百九十八頁(yè)，2022年，8月28日然后查goto表，Ifgoto[sm-k,A]=si

then

格局變?yōu)椋?）Ifaction[sm,ai]=accthen

分析成功分析棧輸入帶S0S1…Sm－kSi#X1…Xm－kAaiai＋1…an#

第一百一十二頁(yè)，共一百九十八頁(yè)，2022年，8月28日5、舉例（P124）文法G[S]：S→aAcBeA→bA→AbB→d第一百一十三頁(yè)，共一百九十八頁(yè)，2022年，8月28日注意：分析中只需要狀態(tài)棧信息1）因?yàn)榉治銎鞯挠懈F控制是確定的，所以文法符號(hào)可不必壓入棧內(nèi)。2）當(dāng)?shù)竭_(dá)一歸約狀態(tài)時(shí)，與該狀態(tài)對(duì)應(yīng)的句柄是確定的。第一百一十四頁(yè)，共一百九十八頁(yè)，2022年，8月28日4.6.2LR(0)分析器

LR(0)分析器是最簡(jiǎn)單的分析器，無(wú)需向前查看輸入符號(hào)即可確定分析器的動(dòng)作（如下面的分析表，棧頂狀態(tài)為0、2、3、5、7時(shí)采取移進(jìn)操作，狀態(tài)4、6、8、9時(shí)采取歸約操作，不需要查看輸入符號(hào)）。LR(0)分析器是構(gòu)造其它更為復(fù)雜的分析的基礎(chǔ)。第一百一十五頁(yè)，共一百九十八頁(yè)，2022年，8月28日

LR分析器為一個(gè)輸入串構(gòu)造一個(gè)最左歸約序列，即逆向構(gòu)造最右（規(guī)范）推導(dǎo)。最右推導(dǎo)序列的特征分析：考慮文法G，其開(kāi)始符號(hào)為S，對(duì)于輸入串x，其規(guī)范推導(dǎo)序列為：

S≠>α1≠>α2…≠>αm-1≠αm=x在推導(dǎo)序列中的每一步都具有形式

ψBt=>ψβ

t式中αi=ψBt，B→β是所使用的產(chǎn)生式，t∈Vt*。第一百一十六頁(yè)，共一百九十八頁(yè)，2022年，8月28日定義：規(guī)范句型的活前綴對(duì)于規(guī)范句型ψβt，β表示句柄，如果ψβ=u1u2…ur，那么稱符號(hào)串u1u2…ui(其中1≤i≤r)是句型ψβt的活前綴。其中包含了完整句柄的活前綴稱為可歸前綴，其它稱為子前綴（P125）。注意：由定義可知所有活前綴都不包括句柄右邊的任何符號(hào)(即t中的任何符號(hào))。第一百一十七頁(yè)，共一百九十八頁(yè)，2022年，8月28日要建立輸入串的最左歸約序列，分析器的一個(gè)基本的功能就是要能檢測(cè)當(dāng)前規(guī)范句型的句柄，即能夠識(shí)別出每一步規(guī)范推導(dǎo)ψBt=>ψβ

t中的ψβ（即規(guī)范句型的所有活前綴）。例子：文法G[S’]:（P126）[0]S’→S[1]S→aAcBe[2]A→b[3]A→Ab[4]B→d分析符號(hào)串a(chǎn)bbcde第一百一十八頁(yè)，共一百九十八頁(yè)，2022年，8月28日a 活前綴為：aab[規(guī)則2歸約] 可歸前綴：ab，句柄為：baAb[規(guī)則3歸約] 可歸前綴：aAb

，句柄為：AbaAc 活前綴為：aAcaAcd[規(guī)則4歸約] 可歸前綴：aAcd

，句柄為：daAcBe[規(guī)則1歸約]可歸前綴：aAcBe

，句柄為：aAcBe

以上規(guī)范歸約對(duì)應(yīng)的最右推導(dǎo)如下：S≠>

aAcBe.→aAcb.e→aA.cde→aAb.cde→aA.bcde→ab.bcde→.abbcde

↑↑↑↑↑↑↑第一百一十九頁(yè)，共一百九十八頁(yè)，2022年，8月28日識(shí)別活前綴的NFA第一百二十頁(yè)，共一百九十八頁(yè)，2022年，8月28日化簡(jiǎn)NFA引入共同的初態(tài)結(jié)點(diǎn)X，用ε弧聯(lián)結(jié)得到圖7.3?；?jiǎn)后得到圖7.4第一百二十一頁(yè)，共一百九十八頁(yè)，2022年，8月28日例子文法G：

E→T|E+T|E－T T→i|(E)引入一個(gè)新的開(kāi)始符號(hào)S，得到拓廣文法G’：

S→E# E→T|E+T|E－T T→i|(E)其中符號(hào)#為文法G所產(chǎn)生的終結(jié)符號(hào)串的右界符。考察句型：E-(i+i)#，建立其規(guī)范推導(dǎo)如下：S→E-T?！鶨-(E)?！鶨-(E+T)?！鶨-(E+i)?！鶨-(T+i)?！鶨-(

i＋i)＃根據(jù)定義：E、E-、E-(、E-(i均為該句型的活前綴，E-(

i為可歸前綴。拓展文法的目的：使文法只有一個(gè)以識(shí)別符號(hào)作為左部的產(chǎn)生式，從而使構(gòu)造出來(lái)的分析器有唯一的接受狀態(tài)。i為句柄第一百二十二頁(yè)，共一百九十八頁(yè)，2022年，8月28日活前綴及可歸前綴的一般計(jì)算方法（P128）定義規(guī)范句型中非終結(jié)符號(hào)A的左串集合為L(zhǎng)C（A）推論：如文法中有產(chǎn)生式B→γAδ，則有第一百二十三頁(yè)，共一百九十八頁(yè)，2022年，8月28日根據(jù)以上推論和文法列出前綴集合方程[0]S’→S[1]S→aAcBe[2]A→b[3]A→Ab[4]B→d第一百二十四頁(yè)，共一百九十八頁(yè)，2022年，8月28日求解前綴集合方程第一百二十五頁(yè)，共一百九十八頁(yè)，2022年，8月28日一、LR(0)項(xiàng)目LR(0)項(xiàng)目定義文法G的一個(gè)項(xiàng)目是一個(gè)在右部符號(hào)串中標(biāo)有一圓點(diǎn)的產(chǎn)生式，其形式為：A→α1·α2其中A→α1α2為G的一個(gè)產(chǎn)生式。對(duì)空產(chǎn)生式A→ε，其LR(0)項(xiàng)目只有一個(gè)為A→．項(xiàng)目的意義在于它可以表示分析的進(jìn)程，圓點(diǎn)是項(xiàng)目中標(biāo)識(shí)分析進(jìn)度的一種記號(hào)，圓點(diǎn)前面的部分是已經(jīng)分析過(guò)的內(nèi)容，后面的部分表示下面將要分析的內(nèi)容，顯然圓點(diǎn)后面的部分帶有明顯的預(yù)期特征。根據(jù)項(xiàng)目的特點(diǎn)，可以將LR（0）項(xiàng)目劃分成三種類型：（1）A→α1·aα2

其中a∈Vt

稱為移進(jìn)項(xiàng)目；（2）A→α1·Xα2

其中X∈Vn

稱為待約項(xiàng)目；（3）A→α·

稱為歸約項(xiàng)目；舉例：一般情況下，一個(gè)產(chǎn)生式可以有幾個(gè)項(xiàng)目。例如，產(chǎn)生式E→E－T有下面四個(gè)項(xiàng)目：

E→·E－T E→E．－T E→E－．T E→E－T．第一百二十六頁(yè)，共一百九十八頁(yè)，2022年，8月28日二、有效性

LR分析器的有窮控制機(jī)構(gòu)的任務(wù)是識(shí)別規(guī)范句型的句柄。因此，只有包含在規(guī)范句型中的LR（0）項(xiàng)目才是合法有效的。一個(gè)項(xiàng)目A→α1·α2對(duì)于某個(gè)規(guī)范句型ψα1·α2t的活前綴ψα1是有效的，當(dāng)且僅當(dāng)存在某個(gè)最右推導(dǎo)。

S≠>ψAt≠>ψα1·α2t其中t是終結(jié)符號(hào)串。第一百二十七頁(yè)，共一百九十八頁(yè)，2022年，8月28日舉例：一般來(lái)說(shuō)，活前綴與有效項(xiàng)目是多對(duì)多關(guān)系。例如，具有如下產(chǎn)生式的LR(0)文法 S→E# E→T|E+T|E－T T→i|(E)項(xiàng)目E→E－．T，T→．i和T→．(E)對(duì)活前綴E－全都是有效的，即一個(gè)活前綴對(duì)應(yīng)多個(gè)有效項(xiàng)目。如最右推導(dǎo)： S=>E#=>E－．T#證明項(xiàng)目E→E－．T對(duì)E－是有效的。第一百二十八頁(yè)，共一百九十八頁(yè)，2022年，8月28日最右推導(dǎo)： S=>E#=>E－T#=>E－．i#證明項(xiàng)目T→．i對(duì)E－也是有效的。最右推導(dǎo)： S=>E#=>E－T#=>E－．(E)#證明項(xiàng)目T→．(E)對(duì)E－是有效的。請(qǐng)舉出一個(gè)有效項(xiàng)目對(duì)應(yīng)多個(gè)活前綴的例子？第一百二十九頁(yè)，共一百九十八頁(yè)，2022年，8月28日三、LR(0)分析器實(shí)現(xiàn)思路

LR分析器的基本功能是識(shí)別當(dāng)前句型的句柄，LR（0）項(xiàng)目刻畫了當(dāng)前句型的句柄被分析的程度（句柄完全在分析棧外；句柄的一部分已經(jīng)進(jìn)入分析棧；句柄全部進(jìn)入分析棧），通過(guò)建立LR（0）項(xiàng)目集與分析器的每個(gè)狀態(tài)之間的聯(lián)系，構(gòu)造LR（0）分析器的有窮控制機(jī)構(gòu)。第一百三十頁(yè)，共一百九十八頁(yè)，2022年，8月28日識(shí)別活前綴的有限自動(dòng)機(jī)構(gòu)造方法（方法1：直接法P131）（1）求出文法的所有LR(0)項(xiàng)目（2）按照一定規(guī)則構(gòu)造NFA1.確定狀態(tài)結(jié)點(diǎn)每一個(gè)LR(0)項(xiàng)目都是結(jié)點(diǎn)，且為活前綴識(shí)別狀態(tài)，圓點(diǎn)在最右的項(xiàng)目為句柄識(shí)別狀態(tài)。

2.生成轉(zhuǎn)移弧線第一百三十一頁(yè)，共一百九十八頁(yè)，2022年，8月28日（3）將NFA確定化得到DFA

例子：P131（圖7.7－7.8）第一百三十二頁(yè)，共一百九十八頁(yè)，2022年，8月28日四、LR(0)項(xiàng)目集規(guī)范族的構(gòu)造（識(shí)別活前綴的有限自動(dòng)機(jī)構(gòu)造方法2）首先，將項(xiàng)目S→.α將作為有窮狀態(tài)控制的開(kāi)始狀態(tài)，其中S為文法的開(kāi)始符號(hào)。項(xiàng)目S→.α反映了此時(shí)分析器還沒(méi)有識(shí)別任何(非空)活前綴。然后、需要對(duì)項(xiàng)目集中的該初始項(xiàng)目進(jìn)行閉包(closure)運(yùn)算。為了獲得一個(gè)項(xiàng)目A→α1·Xα2的閉包(X為非終結(jié)符號(hào))，應(yīng)該將形式為X→.λ的項(xiàng)目添加到該項(xiàng)目集中。第一百三十三頁(yè)，共一百九十八頁(yè)，2022年，8月28日一）閉包(closure)運(yùn)算定義設(shè)I為一項(xiàng)目集，定義CLOSURE(I)如下：（1）I中的每一個(gè)項(xiàng)目都屬于CLOSURE(I)。（2）如項(xiàng)目A→α1·Xα2屬于CLOSURE(I)，且X為非終結(jié)符號(hào)，則將形式為X→.λ的項(xiàng)目添加到CLOSURE(I)中。（3）重復(fù)（1）和（2），直到CLOSURE(I)封閉為止。二）后繼項(xiàng)目定義令項(xiàng)目A→α.Xβ是對(duì)應(yīng)某個(gè)狀態(tài)U的項(xiàng)目集中的一個(gè)項(xiàng)目，則稱項(xiàng)目A→αX.β為其后繼項(xiàng)目，其中X為文法字匯表中的任一符號(hào)。三）狀態(tài)轉(zhuǎn)移 當(dāng)掃描一輸入符號(hào)或者分析器處于歸約狀態(tài)時(shí)，則在LR分析器的有窮控制中將發(fā)生狀態(tài)轉(zhuǎn)移。在分析器的構(gòu)造過(guò)程中，讀操作是建立新?tīng)顟B(tài)的一種手段。因?yàn)轫?xiàng)目A→α.Xβ的后繼項(xiàng)目A→αX.β將與機(jī)器中另一狀態(tài)V相聯(lián)系。所以，讀操作對(duì)所掃描的符號(hào)X將定義由狀態(tài)U到狀態(tài)V的狀態(tài)轉(zhuǎn)移。第一百三十四頁(yè)，共一百九十八頁(yè)，2022年，8月28日舉例：具有如下產(chǎn)生式的LR(0)文法 S→E# E→T|