【正文】 T i F T F T P + E T i F P P i P 優(yōu)先函數(shù) ? 把每個(gè)終結(jié)符 ?與兩個(gè)自然數(shù) f(?)與 g(?)相對(duì)應(yīng)，使得 ?若 ?1 ≮ ?2，則 f(?1) g(?2) ?若 ?1 ≒ ?2，則 f(?1) = g(?2) ?若 ?1 ≯ ?2，則 f(?1) g(?2) f稱為入棧優(yōu)先函數(shù) ， g稱為比較優(yōu)先函數(shù) 。 ?(3) 給出輸入串 (a,(a,a))的算符優(yōu)先分析過程。 S[k]:=a END ? 17 ELSE ERROR /*調(diào)用出錯(cuò)診察程序 */ ? 18 UNTIL a=‘’ 算符優(yōu)先分析算法 ? 在算法的工作過程中，若出現(xiàn) j減 1后的值小于等于 0時(shí)，則意味著輸入串有錯(cuò)。 構(gòu)造優(yōu)先表的算法 是： ? FOR 每條產(chǎn)生式 P→X1X2… Xn DO FOR i:=1 TO n1 DO BEGIN IF Xi和 Xi+1均為終結(jié)符 THEN 置 Xi≒ Xi+1 IF i?n2且 Xi和 Xi+2都為終結(jié)符 但 Xi+1為非終結(jié)符 THEN 置 Xi≒ Xi+2； IF Xi為終結(jié)符而 Xi+1為非終結(jié)符 THEN FOR FIRSTVT(Xi+1)中的每個(gè) a DO 置 Xi≮ a； IF Xi為非終結(jié)符而 Xi+1為終結(jié)符 THEN FOR LASTVT(Xi)中的每個(gè) a DO 置 a≯ Xi+1 END 算符優(yōu)先文法及優(yōu)先表構(gòu)造 ? 例 : 考慮下面的文法 G[E]： (1) E→E+T | T (2) T→T*F | F (3) F→P ? F | P (4) P→(E) | i 1. 計(jì)算文法 G的 FIRSTVT和 LASTVT。 ???? 算符優(yōu)先文法及優(yōu)先表構(gòu)造 ? 例 :考慮下面的文法 G[E]： (1) E→E+T | T (2) T→T*F | F (3) F→P ? F | P (4) P→(E) | i ?由第 (4)條規(guī)則，有 ‘ (’ ≒ ‘)’； ?由規(guī)則 E→E＋ T和 T?T*F， 有 ＋ ≮ *； ?由 (2)和 (3)，可得 * ≮ ↑； ?由 (1)E→E＋ T和 E ? E+T，可得 + ≯ +； ?由 (3)F→P?F和 F ? P?F，可得 ↑ ≮ ↑。但是若在語法分析器中實(shí)現(xiàn)剪句柄，則有兩個(gè)問題必須解決： ?① 確定右句型中將要?dú)w約的子串 (確定句柄 )； ?② 確定如何選擇 正確的產(chǎn)生式進(jìn)行歸約 。 ? E ? E+T ? E+F ? E+i3 ? T+i3 ? T*F+i3 ? T*i2+i3 ? F*i2+i3 ? i1*i2+i3 ? 短語： i1， i2， i3， i1*i2， i1*i2+i3 ? 直接短語： i1， i2， i3 ? 句柄： i1 規(guī)范歸約簡(jiǎn)述 ? 可 用句柄來對(duì)句子進(jìn)行歸約 ? 例： 設(shè)文法 G[S]： (1) S ? aAcBe (2) A ? b (3) A ? Ab (4) B ? d 句型 歸約規(guī)則 abbcde (2) A ? b aAbcde (3) A ? Ab aAcde (4) B ? d aAcBe (1) S ? aAcBe S b d b a c e S A B A 規(guī)范歸約簡(jiǎn)述 ? 定義：假定 ?是文法 G的一個(gè)句子，我們稱序列 ?n， ?n1， ? ， ?0 是一個(gè) 規(guī)范歸約 ，如果此序列滿足： ? 1 ?n= ? ? 2 ?0為文法的開始符號(hào)，即 ?0=S ? 3 對(duì)任何 i， 0 ? i ? n， ?i1是從 ?i經(jīng)把句柄替換成為相應(yīng)產(chǎn)生式左部符號(hào) 而得到的。如果規(guī)定算符的優(yōu)先次序，并按這種規(guī)定進(jìn)行歸約，則歸約過程是 唯一 的。 ? 棧 STACK，把所有初值為真的數(shù)組元素 F[P， a]的符號(hào)對(duì) (P， a)全都放在 STACK之中。 S[k]:=‘’。 ?2 對(duì)每個(gè)結(jié)點(diǎn)都賦予一個(gè)數(shù)， 此數(shù)等于從該結(jié)點(diǎn)出發(fā)所能到達(dá)的結(jié)點(diǎn) (包括出發(fā)點(diǎn)自身 )。 ?3 檢查所構(gòu)造出來的函數(shù) f和 g是否與原來的關(guān)系矛盾。 ? 5 WHILE S[j]≯ a DO ? 6 BEGIN ? 7 REPEAT ? 8 Q:=S[j]。對(duì)于每個(gè)形如 P→Q… 的產(chǎn)生式，若 F[P， a]為假，則變其值為真且將 (P， a)推進(jìn) STACK棧。 算符優(yōu)先分析 ? 定義任何兩個(gè)可能相繼出現(xiàn)的終結(jié)符 a與 b的優(yōu)先關(guān)系 ： 三種關(guān)系 a ≮ b a的優(yōu)先級(jí)低于 b a ≒ b a的優(yōu)先級(jí)等于 b a ≯ b a的優(yōu)先級(jí)高于 b ? 注意 ：與數(shù)學(xué)上的 、 、 =不同， a ≮ b并不意味著 b ≯ a ? 算符優(yōu)先文法及優(yōu)先表構(gòu)造 ? 一個(gè)文法，如果它的任一 產(chǎn)生式的右部都不含兩個(gè)相繼 (并列 )的非終結(jié)符 ，即不含如下形式的產(chǎn)生式右部： … QR… 則我們稱該文法為 算符文法 。 ? 規(guī)范歸約是關(guān)于是一個(gè)最右推導(dǎo)的逆過程 ?最左歸約 規(guī)范推導(dǎo) ? 由規(guī)范推導(dǎo)推出的句型稱為 規(guī)范句型 。該推導(dǎo)即分析樹 “ 剪句柄 ”的全過程。對(duì)于任何一對(duì)終結(jié)符 a、 b，我們說： 1. a≒ b 當(dāng)且僅當(dāng)文法 G中含有形如P→… ab… 或 P→… aQb… 的產(chǎn)生式； ? 如果一個(gè)算符文法 G中的任何終結(jié)符對(duì) (a，b)至多只滿足下述三關(guān)系之一： a ≒ b， a ≮ b， a ≯ b 則稱 G是一個(gè) 算符優(yōu)先文法 。 FIRSTVT(P)＝ {a | F[P， a]=TRUE} ? 同理，可構(gòu)造計(jì)算 LASTVT的算法。 ? 13 S[k]:=N ? 14 END OF WHILE。 優(yōu)先函數(shù) 優(yōu)先函數(shù) f+