【正文】 用 Aj→ δ1|δ2|...|δk 的右部 替換每個形如 Ai→ Ajγ 產(chǎn)生式中的 Aj, 得到新產(chǎn)生式 ： Ai→δ1γ|δ2γ|...|δkγ 。) E→E+E|E*E |(E)|E|id () What a mess! E E + TT T * FF F i di d i dEE + EE * Ei di d i dEE * EE + Ei di di d10 2 消除文法的左遞歸 文法： S→Aa|b A→Ac|Sd|ε S左遞歸 (但不是直接左遞歸 ) 因為： S=Aa=Sda 注意： 若 G產(chǎn)生句子的過程中出現(xiàn) A A的推導(dǎo)，則無法消除左遞歸 + = 核心思想： 將不是直接左遞歸的非終結(jié)符右部展開到其他產(chǎn)生式中 for i in 2..n loop for j in 1..i1 loop end loop?！?FT39。|ε (2) T →FT39。 (1) E39。 εi d * F T 39。 + T E 39。|ε 關(guān)鍵： 將實際文法符號對應(yīng)到 A、 α 和 β 具體到 E產(chǎn)生式 ： E +T|T A α β 9 ET E 39。 A39?！?FT39。) T →FT39?！?TE39。 方法 首先，整理 A產(chǎn)生式為如下形式 ： 8 1 消除文法的直接左遞歸 (續(xù) 1) 例 用算法 ： E →TE39。 | ... | α m A39?！?α 1 A39。 | ...|β n A39。 然后用下述產(chǎn)生式代替 A產(chǎn)生式 ： 若 α i為空，則形成一個有環(huán)的 A產(chǎn)生式 算法 消除直接左遞歸 A → β 1 A39?！罙39。 ■ 1 消除文法的直接左遞歸 考慮： A→Aα|β 產(chǎn)生的語言： βα* 替換為： A→βA39。 S c A d S c A d a bS c A d aAA α A α . . . . . .6 消除左遞歸 定義 若文法 G中的非終結(jié)符 A，對某個文法符號序列 α 存在推導(dǎo) A=+Aα ，則稱 G是 左遞歸 的。 ? 若有 A→ Aα ， (左遞歸 )，則死循環(huán)使分析無法進行下去。 ? 自上而下分析是一種 試探 的過程 ， 是反復(fù)使用不同產(chǎn)生式謀求與輸入序列匹配的過程 。={akbm|k， m， n≥1} （ a+b+c+ ） 例 L3可用下述 CSG描述 ： S→aSBC (1) S→aBC (2) CB→BC (3) aB→ab (4) bB→bb (5) bC→bc (6) cC→cc (7) 句子 akbkck 的推導(dǎo) ： S =...= ak1S(BC)k1 (by 1) = ak(BC)k (by 2) =...= akBkCk (by 3) = akbBk1Ck (by 4) =...= akbkCk (by 5) = akbkcCk1 (by 6) =...= akbkck (by 7) 結(jié)論： CSG、 CFG、 正規(guī)式能力遞減 但是： 能力越強的文法，其文法的設(shè)計和自動機的構(gòu)造越困難 因此： 語法分析僅用到 CFG（除特別指出，文法即指 CFG ） 再考察 L3： 4 自上而下語法分析 自上而下分析的一般方法 用推導(dǎo)的方法分析輸入序列 （ 記號流 ） ： ? 對任何一個輸入序列 ω ， 從 S開始進行最左推導(dǎo) ， 直到得到一個合法的句子或發(fā)現(xiàn)一個非法結(jié)構(gòu) 。={ambm|m,n≥1} （ A→AC A→aAb|ab C→cC|c ） L339。 ■ 文法、語言與自動機 文 法 語 言 自 動 機 短語文法 (0型 ) 短語結(jié)構(gòu)語言 圖靈機 CSG (1型 ) CSL 線性界線自動機 CFG (2型 ) CFL 下推自動機 正規(guī)文法 (3型 ) 正規(guī)集 有限自動機 定義 若文法 G=(N， T， P， S)的每個產(chǎn)生式 α→β 中 ， 均有 α∈(N∪T) *， 且至少含有一個非終結(jié)符 ， β∈(N∪T) *，則稱 G為 0型文法 。1 上次課程內(nèi)容回顧 一、二義性與二義性的消除 1. 造成二義性的原因－文法符號缺乏明確的優(yōu)先級和結(jié)合性 2. 消除二義性的方法： ? 改寫二義文法為無二義文法 ? 為文法符號規(guī)定優(yōu)先級和結(jié)合性 ? 改變語言的結(jié)構(gòu)或書寫方式 二、語言與文法的分類 1. 正規(guī)式 、 CFG、 CSG 2. 從計數(shù)問題看三者之間的關(guān)系 2 形式語言與自動機簡介 對 0型文法施加以下第 i條限制 ， 即得到 i型文法 。 1. G的任何產(chǎn)生式 α→β （ S→ε 除外 ） 滿足 |α|≤|β| ； 2. G的任何產(chǎn)生式形如 A→β ， 其中 A∈N ， β∈(N∪T) *； 3. G的任何產(chǎn)生式形如 A→a 或者 A→aB( 或者 A→Ba) ， 其中 A和 B∈N ， a∈T 。 3 形式語言與自動機簡介（續(xù)） L3={anbn|n≥1} L339。39。 ? 在推導(dǎo)的過程中 ， 從左到右 掃描輸入序列 ， 并試圖用一切可能的方法 ， 自上而下 建立它的分析樹 。 5 自上而下分析的一般方法（續(xù) 1） 例 用下述文法分析輸入序列 ω=cad ： S → cAd A → ab | a 問題： ? 若有 A→ α β 1|α β 2， (公共左因子 )，則會虛假匹配和大量回溯；造成分析效率低、語義動作難以恢復(fù)、以及出錯位置的報告不確切等。 重寫文法： 1. 消除左遞歸，以避免陷入死循環(huán)； 2. 提取左因子，以避免回溯。若 G中有形如 A→Aα 的產(chǎn)生式，則稱該產(chǎn)生式對 A直接左遞歸 。 A39。|ε 消除了一個直接左遞歸 7 1 消除文法的直接左遞歸 (續(xù) 1) A→ Aα 1|Aα 2|...|Aα m|β 1|β 2|...|β n 其中 α i非空 ， β j均不以 A開始 。 |β 2 A39。 A39。 | α 2 A39。 |ε ■ 輸入 G中所有的 A產(chǎn)生式 (含直接左遞歸 ) 輸出 等價的不含直接左遞歸的 G39。 (1) E39。|ε (2) (39。 (3) T39。|ε (4) F →(E) | F|id (5)..(7) E→E+T|T T→T*F|F () F→(E)| F|id