編譯原理英文課件：Parsing-2

1、Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-1-Compiler Construction Principles & Implementation TechniquesDr. Zheng XiaojuanProfessorSoftware College of Northeast Normal UniversityApril. 2014Software College of Northeast Normal Univers

2、ity Compiler Construction Principles & Implementation Techniques-2-Knowledge Relation GraphDevelop a ParserSyntax definitionbasing onContext Free GrammarusingimplementTop-downBottom-upSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-3- 3 Co

3、ntext Free Grammar & Parsing3.1 The Parsing Process （語法分析過程）（語法分析過程）3.2 Context-free Grammars （上下文無關文法）（上下文無關文法）3.3 Parse Trees and Abstract Syntax Tree （語法分析樹和抽象語法樹）（語法分析樹和抽象語法樹）3.4 Ambiguous （二義性）（二義性）3.5 Syntax of Sample Language （簡單語言的語法）（簡單語言的語法）Software College of Northeast Normal University C

4、ompiler Construction Principles & Implementation Techniques-4-4 Top-down Parsing4.1 Overview of Top-down Parsing4.2 Three Important Sets4.3 Left Recursion Removal & Left Factoring4.4 Recursive-Descent Parsing4.5 LL(1) ParsingSoftware College of Northeast Normal University Compiler Construction Princ

5、iples & Implementation Techniques-5-4.1 Overview of Top-down Parsing Problem: Given CFG definition of the Syntax; Check whether a program is of well defined structure; Generate parse tree of the program; Main Idea Read sequence of tokens (source program); Start from the start symbol; Try to find a p

6、roper sequence of derivations, resulting in the sequence of token of the source program;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-6-ExampleP:(1) Z aBd(2) B d(3) B c(4) B bBa b c d句型句型輸入輸入動作動作 ZabcdDerive (1)aBdabcdMatchBdbcdDerive(4)

7、bBdbcdMatchBdcdDerive(3)cdcdMatchddMatchSucceedSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-7-4.1 Overview of Top-down Parsing Key problem: According to rest token sequence and the first non-terminal symbol, how to select a right produc

8、tion to make next derivation? Calculate Predict set for a production A a | S + A + a , where VT*, S is start symbol. Look ahead how many tokens? Current token (look ahead one token)Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-8-How to c

9、alculate the predict set for each production?Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-9-4.2 Three Important Sets First Set(first集集) for a string with non-terminal and terminal symbols; First( )(non-terminal的的first集）集） Follow Set(fol

10、low集集) for a non-terminal symbol A; Follow(A) Predict Set(預測集預測集) for a production; Predict(A )Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-10-First Set (first集集) Definition: First( ) = a | *a , a VT, if * then First( )= First( ) How to

11、 calculate First( )? = , First( ) = = a, a VT, First( ) = a = A, A VN, First( ) = First(A) = X1 X2 Xi-1 Xi XnSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-11- S = A | A * , A VN For each terminal symbol a, First(a) = a For each symbol X,

12、 calculate First(X) VN=A1, , An , calculate First(Ai)(1)初始化初始化, First(Ai) =;(2)for i =1 to n 對于對于A Ai i的每個產生式的每個產生式, , - if Ai , First(Ai) = First(Ai) ; - if Ai Y1 . Ym, Y1 ,. ,Ym S , First(Ai) = First(Ai) First(Y1) . First(Ym) - if Ai Y1 . Ym, Y1 ,. ,Yj-1 S , Yj S First(Ai) = First(Ai) First(Y1) .

13、First(Yj-1)- First(Yj)(the reason of minus is Ai can have empty)(3) Repeat (2) until 每個每個First(Ai)沒有變化沒有變化( (收斂收斂).).Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-12-ExampleP:(1) E TE(2) E + TE(3) E (4) T FT(5) T * F T(6) T (7) F (E)(8)

14、F i(9) F nS = E, TEi, n , ( E + , T i, n , ( T *, F i, n , ( Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-13- S = A | A * , A VN For each terminal symbol a, First(a) = a For a string , calculate First( ) For each non-terminal symbol A,

15、First(A) = X1 X2 Xi-1 Xi Xn- if X1 ,. ,Xn S , First( ) = First( ) First(X1) . First(Xm) - if X1 ,. ,Xi-1 S , Yi S First( ) = First( ) First(X1) . First(Xj-1)- First(Xj)Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-14-ExampleP:(1) E TE(2)

16、 E + TE(3) E (4) T FT(5) T * F T(6) T (7) F (E)(8) F i(9) F nEi, n , ( E + , T i, n , ( T *, F i, n , ( First(ETE) =First(TE) =Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-15-4.2 Three Important Sets First Set(first集集) for a string with

17、 non-terminal and terminal symbols; First( ) Follow Set(follow集集) for a non-terminal symbol A; Follow(A) Predict Set(預測集預測集) for a production; Predict(A ) Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-16-Follow Set (follow集集) Definition:

18、 Follow(A) = a | S +Aa, a VT, if S+ A, then Follow(A)= Follow(A) # # represents the end of the string(0) Z cAb(1) A a的的First(A) ？(2) A 的的First(A) ？Z cAb cab?通過求產生式（通過求產生式（1）First(A) =a確定選擇產生式（確定選擇產生式（1）Z cAb cb? 通過求產生式（通過求產生式（2） Follow (A) =b確定選擇產生式（確定選擇產生式（2）Software College of Northeast Normal Uni

19、versity Compiler Construction Principles & Implementation Techniques-17-Follow Set (follow集集) How to calculate Follow(A), A VN(1)初始化初始化, A VN, Follow(A) = (2)Follow(S) = #(3)對于每個產生式對于每個產生式A If there is no non-terminal symbol in , skip; If = B , B VN, Follow(B) = Follow(B) (First( )- ) If First( ), F

20、ollow(B) = Follow(B) Follow(A) If = B, Follow(B) = Follow(B) Follow(A)(4) Repeat (3) until all follow sets do not change any more;A BZ cAb c BbSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-18-ExampleEi, n , ( E + , T i, n , ( T *, F i, n

21、 , ( P:(1) E TE(2) E + TE(3) E (4) T FT(5) T * F T(6) T (7) F (E)(8) F i(9) F nE#, )E#, )T+, ), #T+, ), #F*, +, ), #Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-19-4.2 Three Important Sets First Set(first集集) for a string with non-termin

22、al and terminal symbols; First( ) Follow Set(follow集集) for a non-terminal symbol A; Follow(A) Predict Set(預測集預測集) for a production; Predict(A ) Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-20-Predict Set (predict集集) Definition: Predict(

23、A ) = first( ), if first( ); Predict(A ) = (first( )- ) follow(A), if first( ); Predict(A ) = follow(A), Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-21-ExampleEi, n , ( E + , T i, n , ( T *, F i, n , ( P:(1) E TE(2) E + TE(3) E (4) T F

24、T(5) T * F T(6) T (7) F (E)(8) F i(9) F nE#, )E#, )T+, ), #T+, ), #F*, +, ), #first集集follow集集First(TE)=i, n,( First(+TE)=+Follow(E)=#, )First(FT)=i,n,( First(*FT)=*Follow(T)= ),+, # First(E)= ( First(i)=iFirst(n)=nSoftware College of Northeast Normal University Compiler Construction Principles & Imp

25、lementation Techniques-22-Top-down parsing Precondition for Top-down parsing (look ahead one symbol) 自頂向下語法分析方法的前提條件自頂向下語法分析方法的前提條件 G = (VT, VN, S, P) For any A VN, For any two productions of A, Predict(A 1) Predict(A 2) = (同一個非終極符的任意兩個產生式的同一個非終極符的任意兩個產生式的predictpredict集合互不相交集合互不相交) ) 這個條件保證這個條件保證:

26、:針對當前的符號和當前的非終極符針對當前的符號和當前的非終極符, ,可可以選擇唯一的產生式來進行推導以選擇唯一的產生式來進行推導; ; Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-23-ExampleP:(1) Z aBd a(2) B d d(3) B c c(4) B bB ba b c d句型句型輸入輸入動作動作 ZabcdDerive (1)aBdabcdMatchBdbcdDerive(4)bBdbcdMatch

27、BdcdDerive(3)cdcdMatchddMatchSucceedSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-24-Knowledge Relation GraphTop-down parsingSyntax definitionbasing onCFGusingcheck preconditionPredict(A)first( )follow(A)YesRecursive-descent LL(1)Impleme

28、ntSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-25-4.3 Left Recursion Removal & Left Factoring 消除左遞歸消除左遞歸 直接左遞歸直接左遞歸 間接左遞歸間接左遞歸 消除公共前綴消除公共前綴 提取公共前綴提取公共前綴Software College of Northeast Normal University Compiler Construction Principles & I

29、mplementation Techniques-26-4.4 Recursive-Descent Parsing Main Idea: For each non-terminal symbol, generate one parsing sub-routine(語法分析子過程語法分析子過程) ) according to its productions; 遞歸下降法遞歸下降法: : 針對滿足針對滿足分析條件分析條件的的CFG;CFG; “遞歸遞歸”: :由于產生式的遞歸導致分析子程序的遞歸由于產生式的遞歸導致分析子程序的遞歸; ; “下降下降”: :自頂向下分析自頂向下分析; ; Disad

30、vantages: Restriction on CFG is too strict; inefficient because of too many function calls;Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-27-4.4 Recursive-Descent Parsing The goal of parsing Check whether the input string belongs to the l

31、anguage of CFG; Two actions match(a): to check current symbol, if match, read next symbol; Derivation: select the productionSoftware College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-28-ExampleP:(1) Z aBd a(2) B d d(3) B c c(4) B bB bZ ( )if token =

32、a match(a); B( ); match(d); else error( );B ( ) case token of d: match(d);break; c: match(c); break; b: match(b); B( ); break; other: error( );a b c dmain( ) read(token); Z( )Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-29-General Proce

33、ss G = (VT, VN, S, P) Predefined function: void match(a: VT) Global variable: token: VT Input string: str For each A VN, A 1| n A( ) case token of Predict(A 1): SubR( 1) ; break; Predict(A n): SubR( n) ; break; other: error; Software College of Northeast Normal University Compiler Construction Princ

34、iples & Implementation Techniques-30-General Processvoid match(a: VT) if token = a token = readNext(str); else error();SubR( ): = X1 X2 XnIf Xi VT, match(Xi)If Xi VN, Xi();SubR( ): = Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-31-Some

35、Notes Not real parsing program, but algorithm; More detailed issues need to be considered Dealing with errors Building parse treeHow to deal with these issues?Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-32-Building Parse Tree Data stru

36、cture ParseTree Operations ParseTree BuildRoot(symbol: VT); ParseTree BuildOneNode(symbol: VT VN) AddOneSon(father:*ParseTree, son:*ParseTree ) SetNum(Node:*ParseTree, n:int)符號符號 兒子個數(shù)兒子個數(shù) 兒子指針兒子指針Software College of Northeast Normal University Compiler Construction Principles & Implementation Techniques-33