Discrete Mathematics(II) Spring 2012 Lecture 5: Formation Tree and Parsing algorith Lecturer. yil 1 Overview In this lecture, we completely focus on syntax of proposition. And the term "proposition"does always mean well-defined proposition without explicit declaration The most important topic is to make sure the unique readability of a well defined proposition. And then a proposition is associated with a tree, called formation tree. Therefore, we find the properties of a well-defined proposition based on its tree form. Finally, we introduce a parsing algorithm to check the validity of a sequence of symbols, with a formation tree as a by-product 2 Some properties of proposition 2.1 Ambiguity In everyday language, we sometimes could speak some sentence which could be understood totally ith different meaning, which is called ambiguous Example 1. Consider the following sentences 1. The lady hit the man with an umbrella 2. He gave her cat food 3. They are looking for teachers of French, German and Japanese Once you read these sentences, you way wonder 1. Is the lady using an umbrella to hit or is she hitting a man who is carrying an umbrella? 2. Is he giving cat food to her or is he giving her cat some food? 3. Are they looking for teachers who can each teach one language or all three languages? You may find more examples. Here, the ambiguity is not caused by the meaning/ semantics of some word. The reason is just the way to group words in different approaches Similarly, you could encounter the same trouble when you write a piece of segment of code. The example is the way to nest if and else. You can also consider the following expression4/ 2 x 2 Without the help of parentheses, proposition could also run into the same problem. Consider the following exampleDiscrete Mathematics (II) Spring 2012 Lecture 5: Formation Tree and Parsing Algorithm Lecturer: Yi Li 1 Overview In this lecture, we completely focus on syntax of proposition. And the term “proposition” does always mean well-defined proposition without explicit declaration. The most important topic is to make sure the unique readability of a well defined proposition. And then a proposition is associated with a tree, called formation tree. Therefore, we find the properties of a well-defined proposition based on its tree form. Finally, we introduce a parsing algorithm to check the validity of a sequence of symbols, with a formation tree as a by-product. 2 Some properties of proposition 2.1 Ambiguity In everyday language, we sometimes could speak some sentence which could be understood totally with different meaning, which is called ambiguous. Example 1. Consider the following sentences: 1. The lady hit the man with an umbrella. 2. He gave her cat food. 3. They are looking for teachers of French, German and Japanese. Once you read these sentences, you way wonder: 1. Is the lady using an umbrella to hit or is she hitting a man who is carrying an umbrella? 2. Is he giving cat food to her or is he giving her cat some food? 3. Are they looking for teachers who can each teach one language or all three languages? You may find more examples. Here, the ambiguity is not caused by the meaning/semantics of some word. The reason is just the way to group words in different approaches. Similarly, you could encounter the same trouble when you write a piece of segment of code. The example is the way to nest if and else. You can also consider the following expression “4/2 × 2”. Without the help of parentheses, proposition could also run into the same problem. Consider the following example. 1