资源描述：
《编译原理5.2.2-算符优先分析算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章语法分析5.1自下而上分析基本问题5.2算符优先分析5.3LR分析5.4YACC5.2.2算符优先分析算法1、算符文法的两个性质*2、算符文法句型的一般形式3、算符文法短语的一般形式4、算符优先文法句型的性质5、算符优先文法的可归约串6、素短语、最左素短语7、算符优先分析算法1、算符文法的两个性质*性质1:在算符文法中任何句型都不包含两个相邻的非终结符.性质2:如果Ab或(bA)出现在算符文法的句型γ中,A∈VN，b∈VT,则γ中任何含b的短语必含有A.2、算符文法句型的一般形式#N1a1N2a2...NnanNn+1#Ni为非终结符或空，ai为
2、终结符根据算符文法性质1句型:#N1a1N2a2...NnanNn+1#短语:Niai...ajNj+1或Ni根据算符文法性质23、算符文法短语的一般形式4、算符优先文法句型的性质如果aNb(或ab)出现在句型r中,则a和b之间有且只有一种优先关系,若ab,则在r中必有含b而不含a的短语存在。若ab,则在r中必有含a而不含b的短语存在。若ab,则在r中含有a的短语必含有b，反之亦然。句型:#N1a1N2a2...NnanNn+1#ai-1aiai+1…aj-1ajaj+15、算符优先文法的可归约串短语:Niai...ajNj+1或Ni可归约串6、素短语
3、、最左素短语设文法G(上下文无关文法)，其句型的素短语是一个短语，它至少包含一个终结符，并除自身外不包含其它素短语.最左边的素短语称最左素短语.补充例E→E+T
4、TT→T*F
5、FF→P↑F
6、PP→(E)
7、i句型#T+T*F+i#短语:T+T*F+i,T+T*F,i,T,T*F素短语:i,T*F最左素短语:T*FEE+TE+TT*FTFiP7、算符优先分析算法p93k:=1;S[k]:=‘#’REPEAT……UNTILa=‘#’1#REPEAT把下一个符号读入a中;IFS[k]∈VTTHENj:=kELSEj:=k-1;WHILES[j]aDO//归约{
8、REPEATQ:=S[j];IFS[j-1]∈VTTHENj:=j-1ELSEj:=j-2UNTILS[j]Q;把S[j+1]...S[k]归约为某个N;k:=j+1;S[k]:=N;}IFS[j]aORS[j]a//移进BEGINk:=k+1;S[k]:=aENDELSEERRORUNTILa=‘#’j指向栈顶或次栈顶的终结符寻找可归约串E→E+T
9、TT→T*F
10、FF→P↑F
11、PP→(E)
12、i补充例1:写出句型#T+T*F+i#的算符优先分析过程求出算符优先关系表(p90表5.1)+*↑i()#+*↑i()#算符优先分析归约过程步骤符号栈优先关系剩余
13、输入串动作1#23456789101112移进#T+T*F+i#移进#T+T*F+i#移进#T+T#T+T*F+i##T+T*F+i#归约T*FT+T*F+i#*F+i#移进移进#T+N+i#归约T+N#N+i#移进#N+i#移进#N+i#归约i#N+N#归约N+N#N#接受算符优先分析 语法树的框架N+NiN+NT*FT算符优先分析 语法树的框架N+NiN+NT*FTEE+TE+TT*FTFiP语法树算符优先分析过程跳过了对单非终结符的归约所以:算符优先分析过程不是规范归约补充例2:写出规范归约分析过程 和算符优先分析过程E→E+T
14、TT→T*F
15、F
16、F→(E)
17、i输入串i+i#EE+TTFiFi语法树求出算符优先关系表E→E+T
18、TT→T*F
19、FF→(E)
20、i+*i()#+*i()#参考(p90表5.1)算符优先分析归约过程步骤符号栈优先关系剩余输入串动作1#i+i#234567移进#i+i#归约i#N+i#移进#N+i#移进#N+i#归约i#N+N#归约N+N#N#接受算符优先分析 语法树的框架N+NiNi规范归约过程步骤符号栈剩余输入串动作1#i+i#2345678910EE+TTFiFi语法树移进#i+i#归约F→i#F+i#归约T→F#T+i#归约E→T#E+i#移进#E+i#移进#E+i
21、#归约F→i#E+F#归约T→F#E+T#归约E→E+T#E#接受算符优先分析 语法树的框架F+FiFiEE+TTFiFi语法树补充:算符优先分析法的局限性G:S→S;D
22、D D→D(T)
23、HH→a
24、(S) T→T+S
25、S;()a+#;()a+#课后思考:1.给出输入串#(a+a)#的算符优先分析过程2.#(a+a)#是文法的句子吗?5.2.3优先函数*5.2.4算符优先分析中的出错处理*作业：p133－13.(1)(2)(4)
