编译原理5.2.2-算符优先分析算法.ppt

第五章 语法分析,5.1 自下而上分析基本问题 5.2 算符优先分析 5.3 LR分析 5.4 YACC,5.2.2 算符优先分析算法,1、算符文法 的两个性质* 2、算符文法 句型 的一般形式 3、算符文法 短语 的一般形式 4、算符优先文法 句型 的性质 5、算符优先文法 的 可归约串 6、素短语、最左素短语 7、算符优先分析算法,1、算符文法 的两个性质*,性质1: 在算符文法中任何 句型 都不包含两个相邻的非终结符. 性质2: 如果Ab或(bA)出现在算符文法的句型中, AVN ，bVT, 则中任何含b的短语必含有A.,2、算符文法 句型 的一般形式,# N1a1N2a2 . Nnan Nn+1 # Ni 为非终结符或空， ai 为终结符 根据算符文法性质 1,句型: # N1a1N2a2 . Nnan Nn+1 #,短语: Niai . ajNj+1 或 Ni 根据算符文法性质 2,3、算符文法 短语 的一般形式,4、算符优先文法 句型 的性质,如果aNb(或ab)出现在句型r中, 则a和b之间有且只有 一种优先关系, 若a b , 则在r中 必有 含b而不含a的短语存在。 若a b , 则在r中 必有 含a而不含b的短语存在。 若a b , 则在r中 含有a的短语必含有b，反之亦然。,句型: # N1a1N2a2 . Nnan Nn+1 #,ai-1 ai ai+1 aj-1 aj aj+1,5、算符优先文法 的可归约串,短语: Niai . ajNj+1 或 Ni,可归约串,6、素短语、最左素短语,设文法G(上下文无关文法)， 其句型的素短语 是一个短语， 它至少包含一个终结符， 并除自身外不包含其它素短语. 最左边的素短语称最左素短语.,补充例,EE+T | T TT*F | F FPF | P P(E) | i 句型 #T+T*F+i#,短语: T+T*F+i , T+T*F , i , T, T*F 素短语: i , T*F 最左素短语: T*F,7、算符优先分析算法 p93,k:=1; Sk:= # REPEAT UNTIL a= #,1,#,REPEAT 把下一个符号读入a中; IF SkVT THEN j:= k ELSE j:=k-1; WHILE Sj a DO /归约 REPEAT Q:= Sj; IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q; 把Sj+1.Sk 归约为某个N; k:=j+1; Sk:=N; IF Sj a OR Sj a /移进 BEGIN k:=k+1; Sk:=a END ELSE ERROR UNTIL a= #,j指向栈顶或次栈顶的终结符,EE+T | T TT*F | F FPF | P P(E) | i,补充例 1: 写出句型 #T+T*F+i# 的算符优先分析过程,求出算符优先关系表 (p90 表5.1),算符优先分析 归约过程,移进,#T,+T*F+i#,移进,#T+,T*F+i#,移进,#T+T,#T+T*,F+i#,#T+T*F,+i#,归约 T*F,T+T*F+i#,*F+i#,移进,移进,#T+N,+i#,归约 T+N,#N,+i#,移进,#N+,i#,移进,#N+i,#,归约 i,#N+N,#,归约 N+N,#N,#,接受,算符优先分析 语法树的框架,N,+,N,i,N,+,N,T,*,F,T,算符优先分析 语法树的框架,N,+,N,i,N,+,N,T,*,F,T,语法树,算符优先分析过程跳过了对单非终结符的归约 所以: 算符优先分析过程不是规范归约,补充例 2: 写出 规范归约分析过程 和 算符优先分析过程,EE+T | T TT*F | F F(E) | i 输入串 i+i#,语法树,求出算符优先关系表,EE+T | T TT*F | F F(E) | i,参考 (p90 表5.1),算符优先分析 归约过程,移进,#i,+i#,归约 i,#N,+i#,移进,#N+,i#,移进,#N+i,#,归约 i,#N+N,#,归约 N+N,#N,#,接受,算符优先分析 语法树的框架,N,+,N,i,N,i,规范归约过程,语法树,移进,#i,+i#,归约 Fi,#F,+i#,归约 TF,#T,+i#,归约 ET,#E,+i#,移进,#E+,i#,移进,#E+i,#,归约 Fi,#E+F,#,归约 TF,#E+T,#,归约 EE+T,#E,#,接受,算符优先分析 语法树的框架,语法树,补充: 算符优先分析法的局限性,G: SS;D|D DD(T)|H Ha|(S) TT+S|S,课后