1 00:00:03,440 --> 00:00:08,767 In this video, we're gonna continue our discussion of parsing with the idea of a 2 00:00:08,767 --> 00:00:17,962 derivation. So a derivation is a sequence of productions so beginning with the start 3 00:00:17,962 --> 00:00:22,960 symbol, we can apply productions one at a time. In sequence and that produces a 4 00:00:22,960 --> 00:00:29,181 derivation. And a derivation can be drawn in a different way instead of as a linear 5 00:00:29,181 --> 00:00:35,023 sequence of replacements, we can draw it as a tree. So for example, if I have a 6 00:00:35,023 --> 00:00:41,015 nonterminal x it appears in a derivation, then when I replace x, I can represent 7 00:00:41,015 --> 00:00:47,459 that by making the children Of x, the left hand side of the rule that I used to 8 00:00:47,459 --> 00:00:54,319 replace x. So I applied production x goes to y1 to yn, I add the y1 to yn is 9 00:00:54,319 --> 00:01:01,362 children of x in the tree that I'm building up. Let's do an example. Here is 10 00:01:01,362 --> 00:01:06,100 our simple grammar of arithmetic expressions and let's consider this 11 00:01:06,100 --> 00:01:11,388 particular string id id + id. So what we're going to do now is we're going to 12 00:01:11,388 --> 00:01:17,224 parse this string and we're going to show how to produce a derivation for the string 13 00:01:17,224 --> 00:01:24,834 and also at the same time build the tree. And here it is, Over here, there is 14 00:01:24,834 --> 00:01:30,585 derivation beginning in e and ending in the string that we're interested in with 15 00:01:30,585 --> 00:01:36,691 one production applied each step along the way and here is the corresponding tree and 16 00:01:36,691 --> 00:01:43,057 this is called a parse tree. This is a parse tree of this expression or this 17 00:01:43,057 --> 00:01:48,485 input string. So let's walk through this derivation in detail. The right side in 18 00:01:48,485 --> 00:01:53,982 red, we're going to have the tree that we're building up. And on the left side in 19 00:01:53,982 --> 00:01:59,479 blue, we're going to have the steps in the derivation that we've taken so far. So 20 00:01:59,479 --> 00:02:05,182 initially, our derivation consists of just the start symbol e and our tree consists 21 00:02:05,182 --> 00:02:11,236 of just the root which is also the start symbol. So the first step is that we have 22 00:02:11,236 --> 00:02:17,723 a production e goes to e + e and what that means is over on the tree, we take the 23 00:02:17,723 --> 00:02:24,404 root of the tree and we make, we give it three children e + ne. So now, we replace 24 00:02:24,404 --> 00:02:31,631 the first t by e z. We use the production e goes to e z and that means 25 00:02:31,631 --> 00:02:38,183 we take the first e in the tree and we give it to three children, e 26 00:02:38,183 --> 00:02:45,322 [inaudible]. Continuing along we take the fi rst e here that remains in this 27 00:02:45,322 --> 00:02:51,628 expression and we replace it by id which means we make id a child of the left most 28 00:02:51,628 --> 00:02:57,395 e in the tree that we're building. And then we replace the second e by id using 29 00:02:57,395 --> 00:03:02,846 the production e goes to id and finally, we use the same thing with the third e and 30 00:03:02,846 --> 00:03:08,100 now, we have completed our Parse Tree. So here again, from the start symbol to the 31 00:03:08,100 --> 00:03:13,617 string, we were interested in parsing and in the process we built up this Parse Tree 32 00:03:13,617 --> 00:03:19,791 of the expression. Now there are lots of interesting things to say about parse 33 00:03:19,791 --> 00:03:24,823 trees. So first of all, parse trees have terminals at the leaves and nonterminals 34 00:03:24,823 --> 00:03:29,730 at the interior nodes and furthermore, in-order traversal of the leaves is the 35 00:03:29,730 --> 00:03:34,951 original input. So let's back up and look at our example and confirm all this. If we 36 00:03:34,951 --> 00:03:41,027 look at the leaves, we can see that they are all terminals, Okay? And the interior 37 00:03:41,027 --> 00:03:46,347 nodes are all nonterminals. In this case, it's only one nonterminal in our language, 38 00:03:46,347 --> 00:03:51,473 all the interior nodes are e and the leaves are the terminals of the string. 39 00:03:51,473 --> 00:03:56,469 And then we can see if we do an inward reversal of the leaves, we get exactly 40 00:03:56,469 --> 00:04:01,705 this input string that we started with. Furthermore, the Parse Tree shows the 41 00:04:01,705 --> 00:04:06,270 association of the operations and the input string does not. So you may notice 42 00:04:06,270 --> 00:04:11,127 here that the way that this Parse Tree is constructed, the times binds more tightly 43 00:04:11,127 --> 00:04:16,026 than the plus because the times is a sub-tree. Of the tree containing plus. And 44 00:04:16,026 --> 00:04:21,887 so this means that we would do the e e first before we would add e and some, some 45 00:04:21,887 --> 00:04:26,781 of you may have wondered well, how did I know. To pick this Parse Tree because 46 00:04:26,781 --> 00:04:31,258 actually if you think about it, there's another derivation. Actually there are 47 00:04:31,258 --> 00:04:36,015 several derivations that will give me a different Parse Tree where the plus, where 48 00:04:36,015 --> 00:04:40,829 the times is towards the root and the plus is nested inside the times. So let's not 49 00:04:40,829 --> 00:04:45,530 worry about that for right now, and let's just say that somehow we knew that this 50 00:04:45,530 --> 00:04:50,120 was the Parse Tree we wanted and I gave you a derivation that produces that Parse 51 00:04:50,120 --> 00:04:55,248 Tree. Continuing on, the previous derivation I showed you is actually a very 52 00:04:55,248 --> 00:05:00,047 special derivation. It's what's called a leftmost derivation where each step will 53 00:05:00,047 --> 00:05:04,847 replace the leftmost nonterminal in our string of terminals and nonterminals. And 54 00:05:04,847 --> 00:05:09,647 there's a natural and equivalent notion of a rightmost derivation and here it is. 55 00:05:09,647 --> 00:05:14,123 Here is a rightmost derivation for the same string. Again, beginning with the 56 00:05:14,123 --> 00:05:18,660 start symbol ending with a string we're interested in. And notice that at each 57 00:05:18,660 --> 00:05:23,079 step, we're replacing the rightmost non-terminal. So here, we replace the only 58 00:05:23,079 --> 00:05:27,790 non-terminal e and we get e + c. And then in the second step, we replace the second 59 00:05:27,790 --> 00:05:32,143 non-terminal e with id and so on for the rest of the string. So let's just 60 00:05:32,143 --> 00:05:36,709 illustrate this entirely with our little picture here of the tree and the 61 00:05:36,709 --> 00:05:41,336 derivation simultaneously so once again over here is our tree and this is the 62 00:05:41,336 --> 00:05:46,456 root, the start symbol e and, and in blue is our derivation so we begin by replacing 63 00:05:46,456 --> 00:05:51,453 e by e + e. That's the only nonterminal so it's the rightmost one and then working 64 00:05:51,453 --> 00:05:56,019 from the right side of the tree, we replace the right e by id and then the 65 00:05:56,019 --> 00:06:01,674 left id gets replaced by e z. And now the right most e that remains is replaced 66 00:06:01,674 --> 00:06:09,381 by id and finally the only e that remains is also replaced by id. Now I want to 67 00:06:09,381 --> 00:06:15,150 point out that the rightmost and leftmost derivations I showed you have exactly the 68 00:06:15,150 --> 00:06:20,712 same Parse Tree. And, this was not an accident. Every Parse Tree has a rightmost 69 00:06:20,712 --> 00:06:26,481 and a leftmost derivation. It's just about the order in which the branches are added. 70 00:06:26,481 --> 00:06:31,768 So for example, if I have the first production e goes to e + e, now I have a 71 00:06:31,768 --> 00:06:36,630 choice on how to build my tree. I can either work on. This sub-tree or I can 72 00:06:36,630 --> 00:06:41,088 work on that sub-tree. And if I build this one first, that will be a rightmost 73 00:06:41,088 --> 00:06:45,780 derivation. If I continue to always work on the rightmost non-terminal of course, 74 00:06:45,780 --> 00:06:50,724 And if I work on this one first, I can use that to do a leftmost derivation. Now it's 75 00:06:50,724 --> 00:06:55,560 important also to realize that there are many derivations besides rightmost and 76 00:06:55,560 --> 00:07:00,155 leftmost. I could, I could choose non-terminals in some random order to do 77 00:07:00,155 --> 00:07:05,233 my replacements. But th e rightmost and leftmost ones are the ones that we're most 78 00:07:05,233 --> 00:07:11,555 concerned with. So to summarize, we're not just interested in whether a string is in 79 00:07:11,555 --> 00:07:16,821 the language of a particular context-free grammar, we need to have a Parse Tree for 80 00:07:16,821 --> 00:07:22,215 that string. And, a derivation defines a Parse Tree but it turns out that one Parse 81 00:07:22,215 --> 00:07:27,228 Tree in general has many derivations and in particular, we're interested in the 82 00:07:27,228 --> 00:07:32,495 leftmost and rightmost derivations. These are the two kinds of derivations that are 83 00:07:32,495 --> 00:07:34,780 important in parser implementations.