自底向上優(yōu)先分析法(2)-wenkub.com
2025-05-10 02:19 本頁面
【正文】 ＞ + ) ( i ↑ * + ＜ ＞ ＞ ＜ ＞ ＞ ＜ ＞ ＜ ＞ * P↑ 則有： LASTVT(P) FIRSTVT(E) c) FIRSTVT(E) + T 則有： + ＜ 集合中的其它元素可根據(jù)定義由產(chǎn)生式直接計(jì)算。 ） 39。 b成立 。 算符優(yōu)先文法 定義 ： 設(shè)有一不含 ε 產(chǎn)生式的算符文法 G，如果對任意兩個(gè)終結(jié)符對 a， b之間至多只有 b當(dāng)且僅當(dāng) G中含有形如 A→ ? aB? 的產(chǎn)生式 ， 且 B+推導(dǎo) b? 或 B+推導(dǎo) Cb? ③ a b)若 a∈ FIRSTVT(B)且有產(chǎn)生式 A→B ? 則有 a∈ FIRSTVT(A)。 例如：表達(dá)式文法 E→E+E|E*E|(E)|i 其中任何一個(gè)產(chǎn)生式中都不包含兩個(gè)非終結(jié)符相鄰的情況，因此該文法是算符文法。由于規(guī)定 + ＜ ＞ + i ) ( ↑ / * + ＞ ＜ ＞ ＜ ＜ ＞ ＞ ＜ ＞ ＞ ↑ ＞ ＞ ＜ ＜ ＞ ) ＜ ＞ ＞ ＞ ＜ ＜ 號規(guī)定與它相鄰的任何運(yùn)算符的優(yōu)先性都比它大。)39。服從左結(jié)合。遵循右結(jié)合。 例 :若有文法 G為： (1)E→E+E (2)E→E*E (3)E→i 考察對輸入串 i1+i2*i3的歸約過程 。 ＝ ﹒ ﹒ ﹤ (4) 若 S(i) T(j) 則從 S棧頂開始往前棧串 Sj1 ,Sj1+1,…, Si ﹥ ﹒ 其中 Sj1為第一個(gè)使 Sj11 Sj1 ﹒ ﹤ 此五部分是語法分析所涉及到的幾部分 分析棧和輸入流中的內(nèi)容合起來表示當(dāng)前被歸約的句型，每步的動作將由棧頂符號和當(dāng)前的輸入符的優(yōu)先關(guān)系矩陣來確定，如果兩種符號之間不存在優(yōu)先關(guān)系，則表示輸入符是錯(cuò)誤的；而產(chǎn)生式表則用來確定歸約時(shí)應(yīng)選用的產(chǎn)生式。 (5) 若 T(j)=‘’,并且 S棧的內(nèi)容為 Z(Z為文法開始符號 )則正確停機(jī)。 Si1 Si Si Si+1 Si+2 …=S j Sj Sj+1 ｝ ＝ ﹒ ﹒ ﹤ ﹥ ﹒ ＝ ﹒ ＝ ﹒ 分析算法的要點(diǎn)： STEP 3: 用 SiSi+1… Sj去查產(chǎn)生式表的右部，并用相應(yīng)的左 部符號代替 (歸約 )句柄 Si… Sj， 若查不到，則為出錯(cuò) 。 而給定一個(gè)句型 X，尋找它的句柄是這樣進(jìn)行的：從左向右進(jìn)行掃描，每次只查看兩個(gè)相鄰的文法符號，并由此得知什么時(shí)候查到句柄的尾 Sj， 然后再返過頭來向句型左端進(jìn)行加工，仍然只查看相鄰的兩個(gè)運(yùn)算符，找出句柄的頭 Si。 其定義為： 例：設(shè)有文法 Gz： Z → bMb M→a︱ ( L L→Ma) 則可根據(jù)定義求出其優(yōu)先矩陣來（如下） M〔 Si， Sj〕 = 空 當(dāng) Si與 Sj無關(guān)系 (不相鄰出現(xiàn) )時(shí) 當(dāng) Si Sj 當(dāng) Si Sj 當(dāng) Si Sj ＝ ﹒ ﹒ ﹤ ﹥ ﹒ ＝ ﹒ ﹒ ﹤ ﹥ ﹒ 優(yōu)先關(guān)系矩陣 ： Z → bMb M→a︱ (L L→Ma) Z b M b a Z b M b ( L Z b M b ( L M a ) ＞ ＞ ) = ＞ ＞ a ＜ ＜ ＜ ( ＜ ＜ = b ＞ ＞ L = = M Z Z M L b ( a ) . . . . . . . . . . . . . . . = . ? 構(gòu)造優(yōu)先矩陣的一種簡便方法： STEP 1 對每個(gè)非終極符 W求下面兩種集合： STEP 2 對每個(gè)符號對 Si,Sj填寫優(yōu)先關(guān)系矩陣元素 (其中 W,V∈ VN): Z M L HEAD b ( ,a M ,( ,a LAST b ) ,L ,a ) 如對 Ga我們有： Z → bMb M→a︱ ( L
高考資料相關(guān)推薦
鄂ICP備17016276號-1