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 * *