GRAMMARS Trong hai tài liệu phát qua, chúng tôi đã gặp hai cách tương đương để mô tả mô Bản tin, chúng ta sẽ thấy một cách mạnh mẽ hơn, được gọi là bối cảnh, ngữ pháp miễn phí (hay "ngữ pháp"), theo nghĩa là họ có thể mô tả các ngôn ngữ hơn so với hai người khác. Giả sử chúng ta muốn xác định các biểu thức số học có liên quan đến | INTRODUCTION TO COMPUTER SCIENCE HANDOUT 9. GRAMMARS K5 K6 Computer Science Department Văn Lang University Second semester -- Feb 2002 Instructor Trăn Đức Quang Major themes 1. Context-Free Grammars 2. Languages from Grammars Reading Sections and . CONTEXT-FREE GRAMMARS In the last two handouts we met the two equivalent ways to decribe patterns. In this handout we shall see another even more powerful way called context-free grammars or grammars in the sense they can describe more languages than the two others. Suppose we want to define arithmetic expressions that involve 1. The four binary operators - and 2. Parentheses for grouping and 3. Operands that are numbers. The usual definition is of the form BASIS. A number is an expression. INDUCTION. If E is an expression then each of the following is also an expression. 1. E . That is we may place parentheses around an expression to get a new expression. 2. E E. That is two expressions connected by a plus sign is an expression. 3. E - E. This and the next two rules are analogous to 2 with the other operators. 4. E E. 5. E E. 50 INTRODUCTION TO COMPUTER SCIENCE HANDOUT 9. GRAMMARS To be more succinct and concise we can use a grammar to define our expressions 1 Expression number 2 Expression Expression 3 Expression Expression Expression 4 Expression Expression Expression 5 Expression Expression Expression 6 Expression Expression Expression The symbol Expression is called a syntactic category or a variable which stands for any arithmetic expression. The symbol means can be composed of. For example rule 2 states that an expression can be composed of a left parenthesis followed by any string that is an expression followed by a right parenthesis. There are three kinds of symbols that appear in grammars. 1. The first are metasymbols symbols that play special roles and do not stand for themselves. The only example we have seen so far is the symbol which is used to seperate the syntactic category being defined from
