tailieunhanh - INTRODUCTION TO COMPUTER SCIENCE - PART 10

PARSING Như chúng ta đã thảo luận ngắn gọn trong Bản tin trước, chúng ta có thể khám phá ra rằng một chuỗi thuộc về ngôn ngữ L (), đối với một số thể loại cú pháp, lặp đi lặp lại áp dụng sản xuất: | INTRODUCTION TO COMPUTER SCIENCE HANDOUT 10. PARSING K5 K6 Computer Science Department Văn Lang University Second semester -- Feb 2002 Instructor Trăn Đức Quang Major themes 1. Parse Trees 2. Constructing a Parse Tree Reading Section . PARSE TREES As we have briefly discussed in the previous handout we can discover that a string s belongs to the language L S for some syntactic category S by the repeated application of productions 1. Start with some strings derived from basis productions those that have no syntactic category in the body. 2. Then apply productions to strings already for various syntactic categories. Each application involves substituting strings for occurrences of the various syntactic categories in the body of the production and thereby constructing a string that belongs to the syntactic category of the head. 3. Eventually construct the string s by applying a production with S at the head. It is often useful to draw the proof that s is in L S as a tree which we call a parse tree. The nodes of a parse tree are labeled either by terminals by syntactic categories or by the symbol e. 1. The leaves are labeled only by terminal or e and 2. The interior nodes are labeled only by syntactic categories. 3. Every interior node v represents the application of a production. That is there must be some production such that a The syntactic category labeling v is the head of the production and b The labels of the children of v from the left form the body of the production. 54 INTRODUCTION TO COMPUTER SCIENCE HANDOUT 10. PARSING Here is the parse tree for the string 3 2 14 using the grammar in the Handout 9 but we have abbreviated the syntactic categories Expression Number and Digit to E N and D respectively. E E E N D E E E N N D N D 3 2 D 4 1 The string 3 2 14 is called the yield of the above parse tree. CONSTRUCTING A PARSE TREE To see how a parse tree can be build let us follow the construction of the parse tree shown in the figure. The grammar is .