自底向上優(yōu)先分析法(2)-閱讀頁(yè)
2025-06-03 02:19本頁(yè)面
【正文】 存句型前端的 S棧和輸入串后端的 T隊(duì)列； ,然后用 Sj1,Sj1+1,… Si去查生產(chǎn)式表， 若查到有相同右部的產(chǎn)生式即 U Sj1,Sj1+1,… Si, 則從棧中退掉子串 Sj1,Sj1+1,… Si， 并把 U進(jìn)棧；然后轉(zhuǎn) (2)。 (5) 若 T(j)=‘’,并且 S棧的內(nèi)容為 Z(Z為文法開(kāi)始符號(hào) )則正確停機(jī)。 (1) 置初始狀態(tài)： S(1):=‘’, i:=1, j:=1 (2) 若 S(i)與 T(j)無(wú)任何關(guān)系，則出錯(cuò)停機(jī)。 ＝ ﹒ ﹒ ﹤ (4) 若 S(i) T(j) 則從 S棧頂開(kāi)始往前棧串 Sj1 ,Sj1+1,…, Si ﹥ ﹒ 其中 Sj1為第一個(gè)使 Sj11 Sj1 ﹒ ﹤ 此五部分是語(yǔ)法分析所涉及到的幾部分 分析棧和輸入流中的內(nèi)容合起來(lái)表示當(dāng)前被歸約的句型，每步的動(dòng)作將由棧頂符號(hào)和當(dāng)前的輸入符的優(yōu)先關(guān)系矩陣來(lái)確定，如果兩種符號(hào)之間不存在優(yōu)先關(guān)系，則表示輸入符是錯(cuò)誤的；而產(chǎn)生式表則用來(lái)確定歸約時(shí)應(yīng)選用的產(chǎn)生式。 在歸約過(guò)程中只要找到可歸約串就歸約 ， 并不考慮歸約到那個(gè)非終結(jié)符名 ， 算符優(yōu)先分析的可歸約串不一定是規(guī)范句型的句柄 ， 所以算符優(yōu)先歸約不是規(guī)范歸約 。 例 :若有文法 G為： (1)E→E+E (2)E→E*E (3)E→i 考察對(duì)輸入串 i1+i2*i3的歸約過(guò)程 。 例 :下面給出一個(gè)表達(dá)式的文法為： E→E+E|E － E|E*E|E/E|E↑E|(E)|i 本文法是二義性的 ， 由于人為地規(guī)定了算符之間的優(yōu)先級(jí)別和同一個(gè)級(jí)別中的結(jié)合性質(zhì) ， 所以可能構(gòu)造出確定的分析過(guò)程 。遵循右結(jié)合。服從左結(jié)合。服從左結(jié)合。(39。)39。對(duì)于句子括號(hào) 39。號(hào)規(guī)定與它相鄰的任何運(yùn)算符的優(yōu)先性都比它大。 綜上所述，我們可對(duì)表達(dá)式運(yùn)算符的優(yōu)先關(guān)系構(gòu)造如表 。 ＜ ＜ ＜ ＞ ＞ ＞ ＞ ＞ ＞ ＞ ) ＜ ＜ ＜ ＜ ＞ ＜ ＞ ＜ ＞ ＞ ＞ ↑ ＞ ＞ ＞ ＜ ＞ ＜ ＞ ＞ ＞ * ＜ ＞ ＞ ＜ ＞ ＜ ＞ ＜ ＞ + i ) ( ↑ / * + 很顯然所給表達(dá)式文法是二義性的，但我們?nèi)藶橹庇^地給出運(yùn)算符之間的優(yōu)先關(guān)系，由優(yōu)先關(guān)系表 系是唯一的，有了這個(gè)優(yōu)先關(guān)系表我們對(duì)前面表達(dá)式的輸入串i1+i2*i3歸約過(guò)程就能唯一確定了，也就是說(shuō)在表 6）步時(shí)，棧中出現(xiàn)了 E+E，可歸約為 E，但當(dāng)前輸入符為 39。由于規(guī)定 + ＜ 這里只簡(jiǎn)單介紹直觀算符優(yōu)先分析法，僅僅是為了易于理解算符優(yōu)先分析法的概念，后面將介紹對(duì)任意給定的一個(gè)文法如何按形式算法的規(guī)則計(jì)算算符之間的優(yōu)先關(guān)系。 例如：表達(dá)式文法 E→E+E|E*E|(E)|i 其中任何一個(gè)產(chǎn)生式中都不包含兩個(gè)非終結(jié)符相鄰的情況，因此該文法是算符文法。 性質(zhì) 2： 如果 Ab或 (bA)出現(xiàn)在算符文法的句型 γ 中，其中A∈ VN ， b∈ VT，則 γ 中任何含 b的短語(yǔ)必含有 A。 b)若 a∈ FIRSTVT(B)且有產(chǎn)生式 A→B ? 則有 a∈ FIRSTVT(A)。＞ 、 ＜ b當(dāng)且僅當(dāng) G中含有形如 A→ ? aB? 的產(chǎn)生式 ， 且 B+推導(dǎo) b? 或 B+推導(dǎo) Cb? ③ a 算符優(yōu)先文法 定義 ： 設(shè)有一不含 ε 產(chǎn)生式的算符文法 G，如果對(duì)任意兩個(gè)終結(jié)符對(duì) a， b之間至多只有 和 三種關(guān)系中的一種成立，則稱 G是一個(gè)算符優(yōu)先文法。 b)＜ b成立 。＞ 關(guān)系 : 計(jì)算每個(gè)非終結(jié)符 B的 LASTVT(B)， 在如下形式的產(chǎn)生式 A→ ? Bb? 中，對(duì)每一 a∈ LASTVT(B)，有 a 例 ：現(xiàn)在可用上述算法計(jì)算下列表達(dá)式文法的算符優(yōu)先關(guān)系 。） 39。 和 集合中的其它元素可根據(jù)定義由產(chǎn)生式直接計(jì)算。 b) ＜ FIRSTVT(E) + T 則有： + ＜ FIRSTVT(F) ↑ F 則有： ↑ ＜ FIRSTVT(E) c)＞ E + 則有： LASTVT(E) ＞ * P↑ 則有： LASTVT(P) ＞ ) 從而可以構(gòu)造優(yōu)先關(guān)系矩陣為表 。 ＜ ＜ ＞ ＞ ＜ ＜ ＞ ( ＞ ＞ ＞ ＜ ＞ ↑ ＞ ＜ ＜ ＞ ＞ ＜ ＜ ＞ + ) ( i ↑ * + 本 章 作 業(yè) ? P122： 1 (1)(2)
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1