自底向上優(yōu)先分析法(2)-文庫吧資料
2025-05-22 02:19本頁面
【正文】 ＜ ＜ ＜ 表 算符優(yōu)先關系表 ＜ 此外，對運算對象的終結符 i其優(yōu)先級最高。39。規(guī)定括號的優(yōu)先性大于括號外的運算符，小于括號內的運算符，內括號的優(yōu)先性大于外括號。 39。 ④ 對 39。 ③ +， 優(yōu)先級最低。 ② *,/ 優(yōu)先級其次。 我們可以對此表達式的文法按公認的計算順序規(guī)定優(yōu)先級和結合性如下： ① ↑ 優(yōu)先級最高。 解： 歸約 過程見分析過程表 ： P106頁 在分析到第 6步時，棧頂?shù)姆柎疄?E+E，若只從移進 歸約的角度講，棧頂已出現(xiàn)了產(chǎn)生式 (1)的右部，可以進行歸約，但從通常四則運算的習慣來看應先乘后加，所以應移進，這就提出了算符優(yōu)先的問題。算符優(yōu)先分析的可歸約串是當前符號棧中的符號和剩余的輸入符號構成句型的最左素短語 。 分析棧 S Si 輸入流 Tj 語法分析程序 優(yōu)先關系矩陣 產(chǎn)生式表 算符優(yōu)先分析 算符優(yōu)先分析的基本思想是只規(guī)定算符 (廣義為終結符 )之間的優(yōu)先關系 ， 也就是只考慮終結符之間的優(yōu)先關系 ， 不考慮非終結符之間的優(yōu)先關系 。 (3) 若 S(i) T(j)或 S(i) T(j)， 則把 T(j)送入 S棧中，讀下一符，轉（ 2）。否則，出錯停機。 若查不到轉出錯處理。 STEP 4：重復上述過程，直至歸約完為止。 證明：略 。此時就可以進行歸約了。 簡單優(yōu)先文法分析算法的主要思想是找出句柄并歸納之。 (2)任意兩個產(chǎn)生式具有不同右部。其定義如下： 當且僅當存在形如下面的產(chǎn)生式 U→ … SiSj … Si Sj ＝ ﹒ 當且僅當存在形如下面的產(chǎn)生式 U→… SiW… 的生產(chǎn)式， 且有 W Sj… Si Sj + ? ﹒ ﹤ 當且僅當存在形如下面的產(chǎn)生式 U→… VW… 的生產(chǎn)式 , 且有 V … Si和 W Sj… Si Sj + ? * ? ﹥ ﹒ 在實際使用這些優(yōu)先關系去識別句子時，我們希望采用一種簡潔的方法去表示這些關系，優(yōu)先關系矩陣是一種常用的方式。 這種方法的基本思想為： 首先規(guī)定文法符號之間的優(yōu)先關系，然后再利用這種關系，通過比較句型中兩個相鄰的符號之間的優(yōu)先關系來確定句型的“ 句柄 ” 并進行歸約。還有先括號內后括號外的規(guī)定。這個法則的主要方面就是規(guī)定運算符之間的優(yōu)先順序。這種方法特別有利于分析表達式。 報錯：處理錯誤。 歸約：把分析棧頂?shù)木浔鷼w約為一非終極符。而不同的自底向上方法給出不同的判定方法。例如，在第 14步對棧頂為T，它是 E的一候選式，但它不是句柄，不能歸約成 E。 二、分析過程圖表： 為了具體實現(xiàn)上的方便，我們仍統(tǒng)一約定以 “ ”作為輸入串的左右分界符（開始和結束標志）。 例：考慮文法 G(E)： E→E +T |T T→T*F | F F→i| (E) 并假定輸入串為（ i+i)*i，考察 自底向上的分析過程。 接著再檢查在棧頂是否又出現(xiàn)了新的句柄，則再進行歸約，直至整個輸入符號串處理完。其作用是用來記錄分析的歷史和指示分析的下一步動作。我們首先介紹自底向上分析的一般過程，再介紹兩種常用的分析技術：簡單優(yōu)先分析法和 LR分析方法。 所以，任何自底向上分析方法的關鍵就是要找出當前句型的句柄，然后根據(jù)產(chǎn)生式判別將它歸約成什么樣的非終結符號。第 6章 自底向上優(yōu)先分析法 概述 原理 :在采用 自左向右 掃描， 自底向上 分析的前提下，該類 分析方法是從輸入符號串入手，通過反復查找當前句 型的句柄（最左簡單短語），并使用文法的產(chǎn)生式把 句柄歸約成相應的非終結符來一步步地進行分析的。 最終把輸入串歸約成文法的開始符號，表明分析成功。 下面，我們結合具體的實現(xiàn)方法，介紹在分析過程中如何來識別句柄的。 一、自底向上分析的一般過程： 先設置一個寄存符號的棧，稱為分析棧。分析進行時，把輸入符號一個一個地按掃描順序移進棧中，當棧頂符號形成一個句柄（即為某產(chǎn)生式的右部）時，就進行一次歸約，即把棧頂構成句柄的那個符號串用相應的產(chǎn)生式左部符號來替換 。最終如果棧頂為文法的開始符號，則所分析的輸入符號串為合法的符號串，報告分析成功 ,否則，是不合格的符號串，報告錯誤。 例：考慮文法 G(E)： E→E +T |T
高考資料相關推薦
鄂ICP備17016276號-1