《編譯原理5.1-自下而上分析基本問題.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理5.1-自下而上分析基本問題.ppt（21頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、第五章 語法分析 自下而上分析 Bottom-up Parsing 自下而上語法分析 優(yōu)先分析法 簡(jiǎn)單優(yōu)先分析法 * 算符優(yōu)先分析法 LR分析法 YACC 第五章 語法分析 5.1 自下而上分析基本問題 5.2 算符優(yōu)先分析 5.3 LR分析 5.4 YACC 5.1 自下而上分析基本問題 5.1.1 歸約 5.1.2 規(guī)范歸約簡(jiǎn)述 5.1.3 符號(hào)棧的使用和語法樹的表示 1. 自下而上分析過程 2. 自下而上分析面臨的問題 1. 自下而上分析過程 - 補(bǔ)充例 GS: ScAd Aab Aa 識(shí)別輸入串
2、 cabd 是否該文法的句子 S c A d a b 自下而上分析過程中的每一步，都是從當(dāng)前串 中選擇一個(gè)子串，將它歸約到某個(gè)非終結(jié)符號(hào) , 該子串稱為 “ 可歸約串 ” GS: ScAd Aab Aa c d a b A S S c A d a b 2. 自下而上分析面臨的問題 當(dāng)串中的某部分和某個(gè)產(chǎn)生式右部匹配時(shí) , 該不該歸約 ? 如何確定 可歸約串 ? a不是 可歸約串 ,ab是 可歸約串 可歸約串 最左素短語 句柄 算符優(yōu)先分析 規(guī)范規(guī)約 如何精確定義 “ 可歸約串 ” ? 本章核心 1. 采用哪一種自下而上分析方法
3、? 2. 如何定義可歸約串 ? 3. 如果在當(dāng)前符號(hào)串中確定可歸約串 ? 5.1.1 歸約 G: (1) SaAcBe (2) Ab (3) AAb (4) Bd 識(shí)別輸入串 abbcde# 是否該文法的句子 a b b c d e A A B S 例 : p83 a b b c d e A A B S G: (1) SaAcBe (2) Ab (3) AAb (4) Bd 輸入串 abbcde# 可行的實(shí)現(xiàn)方案 : 邊掃描 , 邊歸約 最左歸約 (規(guī)范歸約 ) 復(fù)習(xí)最左推導(dǎo)、最右推導(dǎo)、最左歸約、 最右歸約、規(guī)范推導(dǎo)、規(guī)范歸約的概念 a
4、G: (1) SaAcBe (2) Ab (3) AAb (4) Bd 輸入串 abbcde# b a A b c 何時(shí)移進(jìn) ,何時(shí)歸約 ?歸約誰 ? 如何確定 可歸約串 ? a a A a A a A c a A d c a A B c a A B e S 動(dòng) 作 移 進(jìn) 移 進(jìn) 歸 約 移 進(jìn) 歸 約 移 進(jìn) 歸 約 歸 約 移 進(jìn) 移 進(jìn) a b (2) b (3) c d (4) e (1) 圖 5.1 符號(hào)棧的變遷 移進(jìn) -歸約分析 用棧實(shí)現(xiàn)規(guī)范歸約 棧頂出現(xiàn)可歸約串即可歸約 5.1.2 規(guī)范歸約簡(jiǎn)述 1. 短語、直接短語、
5、句柄 的定義 2. 從句型的語法樹上找出句型的短語、 直接短語、句柄 3. 規(guī)范歸約與句柄的關(guān)系 精確定義規(guī)范歸約過程中的可歸約串 短語（ Phrase） S A, 且 A , 則稱 是 句型 相對(duì)于 非終結(jié)符 A 的短語 直接短語 (簡(jiǎn)單短語 , Simple phrase) S A, 且 A , 則稱 是 句型 相對(duì)于 規(guī)則 A 的直接短語 * + * 句柄 (Handle) 一個(gè)句型的 最左直接短語 稱為該句型的句柄 . 1. 定義 找出句型 i1*i2+i3 的所有 短語 , 直接短語 , 句柄 . G: ET | E+T TF
6、| T*F F(E) | i T F E E + T * F T F i1 i2 i3 短語 : i1, i2, i3, i1*i2, i1*i2+i3 直接短語 : i1, i2, i3, 句柄 : i1 一棵子樹的所有末端結(jié)點(diǎn)自 左至右排列起來就形成一個(gè) 相對(duì)子樹根的短語 . 2. 從語法樹中 p85 例 5.1 p85 例 5.2 找出句型 E+T*F+i 的所有 短語 , 直接短語 , 句柄 G: ET | E+T TF | T*F F(E) | i 短語 : E+T*F+i E+T*F, i , T*F 直接短語 : T*F, i 句柄 : T*F
7、E E + T F i E + T T * F G: (1) SaAcBe (2) Ab (3) AAb (4) Bd a b b c d e A A B S 例 : p83 a b a A b c a a A a A a A c a A d c a A B c a A B e S 移 進(jìn) 移 進(jìn) 歸 約 移 進(jìn) 歸 約 移 進(jìn) 歸 約 歸 約 移 進(jìn) 移 進(jìn) a b (2) b (3) c d (4) e (1) 圖 5.1 符號(hào)棧的變遷 規(guī)范歸約過程中的 可歸約串是句柄 3. 規(guī)范歸約與句柄的關(guān)系 規(guī)范歸約精確定義 P86 假定
8、 是文法 G的一個(gè)句子 , 如果序列 : n, n-1, , 0 滿足如下條件 , 則 n, n-1, , 0 是一個(gè)規(guī)范歸約 : (1) n = 是給定的句子 (2) 0 = S 是文法的開始符號(hào) (3) 對(duì)任何 i, 0
9、 a b a A b c a a A a A a A c a A d c a A B c a A B e S 移 進(jìn) 移 進(jìn) 歸 約 移 進(jìn) 歸 約 移 進(jìn) 歸 約 歸 約 移 進(jìn) 移 進(jìn) a b (2) b (3) c d (4) e (1) a b a A b c a a A a A a A c a A d c a A B c a A B e S 移進(jìn) 移進(jìn) 歸約 移進(jìn) 歸約 移進(jìn) 歸約 歸約 移進(jìn) 移進(jìn) a b (2) b (3 ) c d (4) e (1 ) 移進(jìn) -歸約分析 用棧實(shí)現(xiàn)規(guī)范歸約 GS: ScAd Aab Aa S c A d a b 分析過程詳見黑板 移進(jìn) -歸約分析器 :符號(hào)棧 + 輸入緩沖區(qū) 分析器的動(dòng)作 :移進(jìn) ,歸約 ,接受 ,出錯(cuò) 步驟 符號(hào)棧 輸入串 動(dòng)作 課后練習(xí) : p88 例 5.3 對(duì) i1*i2+i3的移進(jìn) -歸約分析 P89 語法樹的表示 - 穿線表 *
編譯原理5.1-自下而上分析基本問題.ppt
