编译原理自下而上语法分析

1、编译原理自下而上语法分析编译原理自下而上语法分析编译原理自下而上语法分析编译原理自下而上语法分析步骤步骤动作动作(1)S aAcBe(2)A b (3)A Ab(4)B d该分析过程反复执行该分析过程反复执行“移进移进”和和“归约归约”两个动作，直到栈中只有开始符号为止。两个动作，直到栈中只有开始符号为止。ab aA ab A aA ac A adc A aBc A aeBc A aS编译原理自下而上语法分析AABSAbAbAAbAAbBdBdSaAcBeSaAcBe(1)S aAcBe(2)A b (3)A Ab(4)B d编译原理自下而上语法分析编译原理自下而上语法分析编译原理自下而上语法

2、分析*+*编译原理自下而上语法分析编译原理自下而上语法分析编译原理自下而上语法分析编译原理自下而上语法分析S()TTS,T,S(T)a(T)T,S编译原理自下而上语法分析(1)S aAcBe(2)A b (3)A Ab(4)B d(2) Ab(3)A AbaAbcdeaAcde(4)B d(1)S aAcBeaAcBeS编译原理自下而上语法分析编译原理自下而上语法分析SaAcBeAbdSaAcBeAbbdSaAcBe编译原理自下而上语法分析编译原理自下而上语法分析编译原理自下而上语法分析编译原理自下而上语法分析E-E+T | TT-T*F | FF-(E) | ii i1 1 + i + i2

3、 2 * * i i3 3FTEFTFTE编译原理自下而上语法分析编译原理自下而上语法分析+编译原理自下而上语法分析例：例：EE+E | E*E | (E) | i 证明不是证明不是OPG文法。文法。因为：因为：EE+E ， EE*E 则有则有 + *又因为：又因为：EE*E, EE+E 则有则有 + *所以不是算符优先文法。所以不是算符优先文法。编译原理自下而上语法分析+ + +编译原理自下而上语法分析+ + +编译原理自下而上语法分析编译原理自下而上语法分析编译原理自下而上语法分析编译原理自下而上语法分析编译原理自下而上语法分析ET | E+TTF | T*FFi | (E)EE + TF

4、iTT * F编译原理自下而上语法分析EET+E+TFTT*FPi根据语法树可知：根据语法树可知：句型句型#T+T*F+i#的短语有：的短语有：T 相对非终结符相对非终结符E的短语的短语T*F 相对非终结符相对非终结符T的短语的短语T+T*F 相对非终结符相对非终结符E的短语的短语i 相对非终结符相对非终结符P、F、T的短语的短语T+T*F+i 相对非终结符相对非终结符E的短语的短语根据素短语的定义可知：根据素短语的定义可知： i和和T*F为素短语。为素短语。其中：其中：T+T*F (含含T*F素短语素短语)、 T+T*F+i (含含T*F素短语素短语) 和和 T(不含终结符不含终结符)也不是素短语也不是素短语T*F为最左素短语。为最左素短语。编译原理自下而上语法分析编译原理自下而上语法分析编译原理自下而上语法分析求求i+ii+i* *i i的算符优先分析过程的算符优先分析过程栈栈 输入缓冲区输入缓冲区# # i+i i+i* *i#i# #i +i+i* *i#i#F +i+i* *i#i#F+ i i* *i#i#F+i * *