上次課程內(nèi)容回顧(編輯修改稿)
2024-08-14 00:56 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 9876F :( E )i dn u m5T:F4*,/,mode0 321L :E 。 Lε19 3 遞歸下降子程序 L → { E。 } E → T { (+| ) T } T → F { (*|/|mod) F } F → ( E ) | id | num procedure L is begin lookahead := lexan； while (lookahead/=eof)loop E。 match(39。39。)。 end loop。 end L。 procedure E is begin T。 while lookahead∈(+| ) loop match(lookahead)。 T。 end loop。 end E。 procedure F is begin case lookahead is 39。(39。 : match(39。(39。)。 E。 match(39。)39。)。 id : match(id)。 num : match(num)。 others : error(syntax error2)。 end case。 end F。 20 3 遞歸下降子程序（續(xù)） 再看左遞歸問(wèn)題： 若存在產(chǎn)生式 E → E + id， 則 E的遞歸下降子程序如下： procedure E is begin E。 match(39。+39。)。 match(id)。 end E。 此程序永不停機(jī) 。 include const int id=0。 void match(int x){}。 void E() { cout match E endl。 E()。 match(39。+39。)。 match(id)。 cout match + and id endl。 // 永遠(yuǎn)不執(zhí)行 } void main(){ E()。} 同樣，文法中的公共左因子也會(huì)給遞歸下降分析造成困難。 結(jié)束 （ 2022年 4月 3日 ） 21 上次課程內(nèi)容回顧 1. 形式語(yǔ)言與自動(dòng)機(jī)簡(jiǎn)介 2. 自上而下分析的一般方法：自上而下 (用推導(dǎo)的方法建立分析樹 )、從左到右 (掃描輸入序列 )； 3. 自上而下分析對(duì)文法的限制：不能有左遞歸和左因子 4. 消除左遞歸： ? 左遞歸與直接左遞歸（ 定義 ） ? 基本公式（替換 A→Aα|β 為 A →βA39。 A39。→αA39。|ε ） ? 消除直接左遞歸（ 算法 ）和消除左遞歸（ 算法 ） 5. 提取左因子：合并公共前綴（ 算法 ） 6. 遞歸下降分析（一個(gè)非終結(jié)符是一個(gè)子程序） ? 構(gòu)造文法的狀態(tài)轉(zhuǎn)換圖并且化簡(jiǎn)； ? 將轉(zhuǎn)換圖轉(zhuǎn)化為 EBNF表示； ? 從 EBNF構(gòu)造子程序。 22 預(yù)測(cè)分析器 非遞歸預(yù)測(cè)分析器的工作模式 預(yù)測(cè)分析器的核心概念： 1. 分析方法：格局與格局變換 2. 分析表 +驅(qū)動(dòng)器（模擬算法） 3. 預(yù)測(cè)分析表的構(gòu)造 4. LL（文法、語(yǔ)言、分析器） 驅(qū) 動(dòng) 器輸 入 記 號(hào) 流符號(hào)棧輸 出t o pi p( b ) 預(yù) 測(cè) 分 析 器 模 型預(yù) 測(cè) 分 析 表輸 入 記 號(hào) 流有 限 狀 態(tài)轉(zhuǎn) 移 控 制下推棧輸 出t o pi p( a ) 下 推 自 動(dòng) 機(jī) 模 型23 1 預(yù)測(cè)分析表 L →E 。L|ε E →TE39。 E39?！?TE39。| TE39。|ε T →FT39。 T39?！?FT39。|/FT39。|mod FT39。|ε F →(E)|id|num id num + * / mod ( ) 。 L E。L E。L E。L ε E TE39。 TE39。 TE39。 E39。 +TE39。 TE39。 ε ε T FT39。 FT39。 FT39。 T39。 ε ε *FT39。 /FT39。 mod FT39。 ε ε F id num (E) 文法： L→E 。L|ε E→E+T|E T|T T→T*F|T/F|T mod F|F F→(E)|id|num M[A, a]的內(nèi)容： 若當(dāng)前棧頂是非終結(jié)符 A，下一輸入終結(jié)符是 a，則 M[A, a]指示下一步動(dòng)作。 構(gòu)造 分析表 (M[A, a])： 24 2 工作方式 放幻燈的方式： 1. 每張 “ 幻燈片 ” 稱為一個(gè) 格局 。 2. 分析從某個(gè) 初始格局 開始，經(jīng)過(guò)一系列的 格局變化 ，最終到達(dá) 接收格局 ，表明分析成功； 3. 或者到達(dá) 出錯(cuò)格局 ，表明發(fā)現(xiàn)一個(gè)語(yǔ)法錯(cuò)誤。 格局： 格局是一個(gè)三元組 （ 棧內(nèi)容 ， 當(dāng)前剩余輸入 ， 改變格局的動(dòng)作 ） ^top ^ip 改變格局的動(dòng)作： ① 匹配終結(jié)符： 若 ^top=^ip(但 ≠ )， 則 pop且 next(ip)； ② 展開非終結(jié)符： 若 ^top= X且 M[X, a]=α(X→α) ， 則 pop且 push(α) ； ③ 報(bào)告分析成功： 若 ^top=^ip=， 則分析成功并結(jié)束 ； ④ 報(bào)告出錯(cuò)： 其它情況，調(diào)用錯(cuò)誤恢復(fù)例程。 驅(qū) 動(dòng) 器輸 入 記 號(hào) 流符號(hào)棧輸 出t o pi p( b ) 預(yù) 測(cè) 分 析 器 模 型預(yù) 測(cè) 分 析 表25 3 驅(qū)動(dòng)器算法 算法 非遞歸的預(yù)測(cè)分析 輸入 輸入序列 ω 和文法 G的預(yù)測(cè)分析表 M 輸出 若 ω∈L(G) ， 得到 ω 的一個(gè)最左推導(dǎo)；否則指出一個(gè)錯(cuò)誤 方法 初始格局為 : （ S， ω ， 分析器的第一個(gè)動(dòng)作 ） 令 ip指向 ω 中的第一個(gè)終結(jié)符 ， top指向 S。 loop x := top^。 a := ip^。 exit when x=。 分析成功 end loop。 ■ if x ∈ T then if x=a then pop(x)。 next(ip)。 匹配終結(jié)符 else error(1)。 出錯(cuò)：棧頂終結(jié)符不是 a end if。 else if M[x, a] = X→Y 1Y2...Yk then pop(X)。 push(YkYk1...Y2Y1)。展開產(chǎn)生式 else error(2)。 出錯(cuò)：產(chǎn)生式不匹配 end if。 end if。 26 loop x := top^。 a := ip^。 if x ∈ T then if x=a then pop(x)。 next(ip)。 匹配終結(jié)符 else error(1)。 出錯(cuò)：棧頂終結(jié)符不是 a end i
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1