自底向上分析把一個(gè)輸入符號(hào)串逐步歸約到文法的開始符-文庫吧資料
2025-07-27 08:47本頁面
【正文】 $ 歸約 $ E+E * E *id$ 移進(jìn) $ E+E * id*id$ 移進(jìn) $ E+id +id*id$ 歸約 $ E 棧 關(guān)系 輸入 動(dòng)作 $ ? ? ? 歸約 使用下面的 優(yōu)先關(guān)系表，分析過程如下： id + * $id 找可歸約串 的右端； 2 id id id 之間的符號(hào)串是待歸約的符號(hào)串。 ＄ 句型中 * + 在句型中加入優(yōu)先關(guān)系，例如： id+id*id ＄ ai, ai 中至多有一個(gè)成立。假設(shè)在 ai和 ai+1之 間三個(gè)關(guān)系 2. 決定優(yōu)先關(guān)系方法： （ a） 直觀方法：代數(shù)規(guī)則； （ b） 對于一個(gè)無二義性文法，有機(jī)械方法。（，（ b并不一定意味著 b 終結(jié)符號(hào) a與 b之間的優(yōu)先關(guān)系有三種： a ?? b 表示 a的優(yōu)先級(jí)低于 b a ? b 表示 a的優(yōu)先級(jí)等于 b a ?? b 表示 a的優(yōu)先級(jí)大于 b ? 注意： 1. 算術(shù)關(guān)系 “ ” ,“ =”和“ ”與優(yōu)先關(guān)系具有十分不同的性質(zhì)。上述歸約過程中起決定作用的是相鄰兩個(gè)終結(jié)符號(hào)之間的優(yōu)先關(guān)系 。 二 .算符優(yōu)先分析的基本思路 由于文法 (4. 13)是一個(gè)二義文法，它的句子 往往有不同的規(guī)范推導(dǎo)，按傳統(tǒng)的習(xí)慣規(guī)定優(yōu)先級(jí)從高到低為：乘冪運(yùn)算符，乘、除運(yùn)算符，加、減運(yùn)算符；同級(jí)運(yùn)算符服從左結(jié)合原則；有括號(hào)時(shí)，先括號(hào)內(nèi)后括號(hào)外。 () E→ EAE|(E)|E|id A→ ＋ |－ |*|/| ? 不是算符文法。 算符優(yōu)先分析法 概述 一 . 算符文法的定義 二 . 算符優(yōu)先分析法的基本思想 利用 算符優(yōu)先關(guān)系尋找右句型的可歸 約串 算符優(yōu)先關(guān)系表的構(gòu)造 優(yōu)先函數(shù) 總結(jié) 一 . 算符文法的定義 定義 設(shè) G是一個(gè)文法 ,如果 G中不存在形 如 A??及 A→ ?BC?的產(chǎn)生式 (其中 A,B,C?VN , ?,? ?(VN? VT)*且其中不含有 相鄰非終結(jié)符號(hào)） ,即 G中沒有右部為 ?或右部具有相鄰非終 結(jié)符號(hào)的產(chǎn)生式 ,則稱 G為算符文法。如在表 (a)的前三步中可以看到 ?， a及ab都是符號(hào)串 abbcde的活前綴。 分析過程的每一步驟，棧里的文法符號(hào)串加上剩余輸入符號(hào)串恰好是一個(gè)規(guī)范句型。然后，繼續(xù)向棧里移進(jìn)符號(hào)，重復(fù)這個(gè)過程，直至最終形成如下格局： 棧 輸入 ＄ S ＄ G[s]: S?aAcBe A ?b?Ab B ?d 步驟 棧 輸入 動(dòng)作( 1) $ a b b c d e $ 移進(jìn)( 2 ) $a b
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1