③#与其它终结符的关系：（相当于加了一条产生式S”一#S#) a#·文法所有句型的头终结符（含(）一非终结符开头的情况)即#<·FIRSTVT(S b文法中所有句型的尾终结符（含(）一非终结符结尾的情况)·>#，即LASTVT(S)·>≥# 例1P103S→#S# 例2①=·：(=)#=·# ②i<·FIRSTVT)={a,（ ③LASTVT(S)·>i{i,a,)J <·(《·FIRSTVT(T)=+,i,a,0 ·>LASTVT(D) ·( a,) (<FIRSTVT(S)=i,a. LASTVT(T)·>) {a,)} +<.FIRSTVT(S)=i a. LASTVT(S)·>) i.a.)1 .FIRSTVT(S)=i.a. LASTVT(T)·>+ {+,i.a,)} LASTVT(S)·># 构造优先关系表： i a < < 。> <。 < <· < < < = 其中空格表示错误关系，报错如果表中没有一个单元格有两种优先关系则说明文法是算符 优先文法 四素短语：P110 是一个短语，包含至少一个终结符，除自身不包含其它素短语 例1P110
1 ③#与其它终结符的关系：（相当于加了一条产生式 S’→#S#） a #<·文法所有句型的头终结符（含（）一非终结符开头的情况）即#<·FIRSTVT(S) b 文法中所有句型的尾终结符（含（）一非终结符结尾的情况）·>#，即 LASTVT（S）·># 例 1 P103 S’→#S# 例 2 ① =· ：（=·） #=·# ②i <·FIRSTVT(D)={a,( } ③LASTVT(S) ·>i {i,a, ）} <·(<·FIRSTVT(T)={+,i,a,(} ·>LASTVT(D) ·>( {a, ）} (<·FIRSTVT(S)={i,a,(} LASTVT(T) ·>) {a, ）} +<·FIRSTVT(S)={i,a,( } LASTVT(S) ·>) {i,a, ）} #<·FIRSTVT(S)={i,a,( } LASTVT(T) ·>+ {+,i,a, ）} LASTVT(S) ·># 构造优先关系表： i ( ) a + # i ·> <· ·> <· ·> ·> ( <· <· =· <· <· ) ·> ·> ·> ·> ·> a ·> ·> ·> ·> ·> + <· <· ·> <· ·> # <· <· <· =· 其中空格表示错误关系，报错 如果表中没有一个单元格有两种优先关系则说明文法是算符 优先文法 四 素短语：P110 是一个短语，包含至少一个终结符，除自身不包含其它素短语 例 1 P110
例2.GE]E一>E+TTT->T*FFF->P+FPP->E)M看符号串P*P+i是否是合法句 EE+T-E+F->E+P->E+i=>T+i-T*F+iTP+i=>F*P+iP+P+i 短语：PP+i(E) 简单短语： 素短语：Pp P+P(E,T) PI(F) PI(E,T) P2(F) 最左素短语： P2(F) i(P) p*P i(P.F.T) 句柄P1(F p :算符优先文法可看非终结符，“最左素短语就相当于原来的句柄，即先规约最左素短语。 P111.优先关系决定最左素短语。 五.算符优先分析算法：设GS-(Vn,VPS)为算符优先文法 (1)由文法G(S)构造优先关系矩阵。 (2)设置一个符号栈S。存放已规约的或待形成最左素短语的符号串，另设一个工作单元 R,存放当前的待输入符号。 (3)用移进一规约的方法，当符号栈S的栈顶形成不规约串一最左素短语时，进行规约， 耳体方法加下： ①分析开始时，S中只有一个符号“#”，R中存放输入串（源程序）的第一个终结符 ②查优先关系矩阵，比较符号栈中最靠栈顶的终结符（假设为）与R中的终结符（假设为 b)的优先关系： )若a,b之间无优先关系，则出错并退出分析程序。 ii) 若a<·b或a=·b,则将b进栈，指针后移，R中存放下一个待输入终结符，重复 若a·b,则表明此时栈项已形成最左素短语（且其右界已空）转③ ③.从S中普栈顶的终结符X开始，依次向前（向栈底方向）与最远 的终结符比较，若Xn1=Xa,则继续比较X2和X1,如比较反复， 直至X<X,(i=l,2,.,n设X-#)为止。 于是最左来短语的左界已确定，此时最古来短语为从N:开始(N:为 在X之前临X的非终结符，若为N=e,则从X开始)一直到找顶 的符号串：Ni、X、N+I、X+I、Nn、Xn、Nn+1. 2
2 例 2. G[E]:E－>E+T/T T－>T*F/F F－>P+F/P P－>(E)/I 看符号串 P*P+i 是否是合法句 型。 E=>E+T=>E+F=>E+P=>E+i=>T+i=>T*F+i=>T*P+i=>F*P+i=>P*P+i E 短语：P*P+i(E) 简单短语： 素短语：P*P P*P(E,T) P1(F) i E + T P1(F,T) P2(F) 最左素短语： P2(F) i(P) P*P T F i(P,F,T) 句柄 P1(F) T * F P F P2 i P1 ∵算符优先文法可看非终结符，∴最左素短语就相当于原来的句柄，即先规约最左素短语。 P111. 优先关系决定最左素短语。 五. 算符优先分析算法：设 G[S]=(Vn,Vt,P,S)为算符优先文法 （1）由文法 G（S）构造优先关系矩阵。 （2）设置一个符号栈 S。存放已规约的或待形成最左素短语的符号串，另设一个工作单元 R，存放当前的待输入符号。 （3）用移进—规约的方法，当符号栈 S 的栈顶形成不规约串—最左素短语时，进行规约， 具体方法如下： ①分析开始时，S 中只有一个符号“＃”，R 中存放输入串（源程序）的第一个终结符。 ②查优先关系矩阵，比较符号栈中最靠栈顶的终结符（假设为 a）与 R 中的终结符（假设为 b）的优先关系： i） 若 a，b 之间无优先关系，则出错并退出分析程序。 ii） 若 a<·b 或 a=·b，则将 b 进栈，指针后移，R 中存放下一个待输入终结符，重复 ②。 iii） 若 a·>b，则表明此时栈顶已形成最左素短语（且其右界已空）转③ ③.从 S 中普栈顶的终结符 Xn开始，依次向前（向栈底方向）与最远 的终结符比较，若 Xn-1=Xn，则继续比较 Xn-2 和 Xn-1，如比较反复， 直至 Xi-1<Xi，（i=1，2，.，n 设 X0=#）为止。 于是最左来短语的左界已确定，此时最古来短语为从 Ni 开始（Ni 为 在 Xi之前临 Xi的非终结符，若为 Ni=ε，则从 Xi开始）一直到找顶 的符号串：Ni、Xi、Ni+1、Xi+1、.Nn、Xn、Nn+1
④.文法G[S]的产生式集中，选择其右P具有NXN+1Xi.NnXaNnt! 形式的规则进行归约（注意：此时非终结符号不必完全相同）：弹击 符号栈栈顶的最左来短语相应规则的左部非终结进栈，若此时分析栈 中只有#和文法的一个非终结符，且待分析符号串只剩#（即R中符 号为#)，则表明分析成功，所分析的串是文法句子退出分析程序：否 则，重复②。 例1、Po,表6.8 例2、G[S]:S→D(R)IDR-→R:P|PP→S|iD→i分析i(i: i) D FIRSTUT (S)=(()UFIRSTUT (D)=((,i) FIRSTUT (R)=(;}UFIRSTUT (P)=(;,(i) FIRSTUT (P)=FIRSTUT (S)U(i)=((,i) FIRSTUT (D)=(i) LASTUT (S)=())ULASTUT (D)=(),i) LASTUT (R)=(;ULASTUT (P)=(:,i, LASTUT (R)=(i)ULASTUT (S)=(i,) LASTUT(D)=【i) ②加一条S'→#S# (=)#=#一(K·F1 RSTUT(R) LASTUT(D)·>( :<·F1 RSTUT(P) ·> LASTUT(R)·>) #·F1 RSTUT(S) LASTUT(R)·>: LASTUT(R)·>#
3 ④.文法 G［S］的产生式集中，选择其右 P 具有 NiXiNi+1Xi+1.NnXnNn+1 形式的规则进行归约（注意：此时非终结符号不必完全相同）：弹击 符号栈栈顶的最左来短语相应规则的左部非终结进栈，若此时分析栈 中只有#和文法的一个非终结符，且待分析符号串只剩#（即 R 中符 号为#），则表明分析成功，所分析的串是文法句子退出分析程序；否 则，重复②。 例 1、P110，表 6.8 例 2、G［S］：S→D（R）｜DR→R;P｜P P→S｜i D→i 分析 i（i； i） 1 F1RST∪T（S）=﹛(﹜∪FIRST∪T（D）=﹛(，i﹜ F1RST∪T（R）=﹛;﹜∪FIRST∪T（P）=﹛;，(，i﹜ F1RST∪T（P）= FIRST∪T（S）∪﹛i﹜=﹛(，i﹜ FIRST∪T（D）=﹛i﹜ LAST∪T（S）=﹛)﹜∪LAST∪T（D）=﹛)， i﹜ LAST∪T（R）=﹛;﹜∪LAST∪T（P）=﹛;， i，)﹜ LAST∪T（R）=﹛i﹜∪LAST∪T（S）=﹛i，)﹜ LAST∪T（D）=﹛i﹜ 2 加一条 S＇→# S # （=） # = # (<• F1RST∪T（R） LAST∪T（D）·>( <· ;<• F1RST∪T（P） ·> LAST∪T（R）·>） #<• F1RST∪T（S） LAST∪T（R）·>; LAST∪T（R）·>#
( i # ( ·> 。> ·> ·> ·> 。> 。> 。> ∴此文法是算符优先文法。 ③步骤 符号栈输入串 iii)# 2 #i (i:i# i·>(#<·i则i归约 3 P或#D (工i# #人·( 4 #P( ii)# #P(i ;讲 i·>j(〈·Ii归约 6 #P(P ;i)# (K·j #P(P, i)# #粗(P;i )#i·)j〈·i∴.i归约 9 #P (P.P )#j·>)(《·jP;P归约 10 #P(R )#(曰) #P(R) )·>#,(=),#K·(.∴(R)归约 12 ∴.此串是文法的句子 判断i是否句子
4 ( ) ; i # （ <· = <· <· ） ·> ·> ·> ; <· ·> ·> <· i ·> ·> ·> ·> # <· <· = ∴此文法是算符优先文法。 ③ 步骤 符号栈 输入串 1 # i(i;i)# 2 #i (i;i)# i·>( #<·i 则 i 归约 3 #P 或#D (i;i)# # <·（ 4 #P（ i;i)# 5 #P（i ;i# i·>j ( <·I ∴i 归约 6 #P（P ;i）# (<·j 7 #P（P; i）# 8 #P（P;i ）# i·>) j <·i ∴i 归约 9 #P（P;P ）# j·>) (<·j ∴P ; P 归约 10 #P(R ）# (=) 11 #P(R) # )·>#, (=),#<·(∴(R) 归约 12 #S # ∴ 此串是文法的句子. 判断 i;i 是否句子
i讲 2 #i ;讲 i·>:#<·ii归约 3 #P 经 #与，无关.Error .此串不是文法的句子 实验： 实验一：源程序例表程序 任意读一程序，结果加行号，若超过多少行，加页号，显示标题，日期， 时间 实验二：简单记号扫描程序 简单记号（单词）：单词（全由字母组成）、数（全由数字组成）、句点。 结果显示为二元式 实验三：源代码压缩程序 回车，换行，Tb等多余字符都去掉，其中用空格区分 实验四：扫描器 区分的单词，包括保留字等。 第六章LR(K)分析法 P17,LR自底向上规范归约，不带回溯，准确，每步都是对当 前句型找句柄。 L:从左到右扫描。R:最右推导的逆过程.K:向前看的符号数大 多数上下文无关文法（二型文法）都是LR类文法，对文法的限制少， 但同时对它的分析也相应最复杂
5 1 # i;i# 2 #i ;i# i·>; #<·i ∴i 归约 3 #P ;i# #与; 无关. Error ∴ 此串不是文法的句子. 实验: 实验一: 源程序例表程序 任意读一程序,结果加行号,若超过多少行,加页号,显示标题,日期, 时间 实验二: 简单记号扫描程序 简单记号(单词): 单词(全由字母组成)、数(全由数字组成)、句点。 结果显示为二元式 实验三: 源代码压缩程序 回车，换行，Tab 等多余字符都去掉，其中用空格区分 实验四: 扫描器 区分的单词，包括保留字等。 第六章 LR（K）分析法 P117. LR 自底向上 规范归约，不带回溯，准确，每步都是对当 前句型找句柄。 L：从左到右扫描. R：最右推导的逆过程. K：向前看的符号数大 多数上下文无关文法（二型文法）都是 LR 类文法，对文法的限制少， 但同时对它的分析也相应最复杂