We want to now use an external stack for simulation. And then we have a parse table. And the grammar is encoded in the table of form. And then what we did was we started looking at how this parser works. We actually took an example. And we took an example of parse table in the grammar. Before that, we did certain transformations on the grammar. And the parse table actually is indexed by non-terminals and terminals of the language. And for each of the combinations of non-terminals and terminals, we determine what is the action to be taken and that action is encoded in the table itself. And this is the grammar to begin with. This is the expression grammar from which we have removed the left recursion. And then this is how the table looks for the non-letters in law. So what this table is saying is that I have this indexing on non-terminals and indexing on terminals. Dollar is a special symbol, which sits at the end of the input string and at the bottom of the stack. And what we want to say is that if this is a symbol on top of the stack, and this is my lookahead symbol, then expand using this rule. And all the entries corresponding to these rules, they are corresponding to expansion and all the entries corresponding to the blanks. They have error states, which say that if this is my top of stack symbol and this is my lookahead, then input string is incorrect. We cannot do parsing from that point. And then we looked at the parsing algorithm. So parsing algorithm bars that whenever we have a situation where we can do expansion, that means top of the stack is a non-terminal and lookahead symbol is obviously a terminal, then I'll expand this rule. And when I say I expand by this rule, what that means is that I'm going to pop this symbol from the stack and I'm going to push the right hand side of the rule in the reverse order on the stack. And whenever top of stack is going to be a terminal symbol and it matches the input symbol, then I'm going to advance the input by one. I'm going to discard what is in the top of the stack. And if both bottom of the stack and the lookahead symbol, they have dollar, then we stop saying that this string has been accepted, otherwise this is an error state. So this is what my parsing does, that we match top of the stack. If it is dollar, then we halt. If it is terminal, then we pop and implement input point by one. And if it is non-terminal, then I must expand by a rule. And when I expand by this rule, what that means is I'm popping X from the stack and I'm pushing UVW in reverse order on the stack. And otherwise I'm going to go into an error state. So this is what we were discussing in the previous class. And then we took an example of saying that if this is my initial condition and this is the string I'm trying to parse, then how do I go about doing it? And we go about doing it by saying that my initial condition is dollar is sitting at the bottom of the stack. Then this is the start symbol and this is the string to be parsed, which is an input of dollar. And when I say that top of stack is E and my look ahead is ID, then I go and look at. So let me take this parse table and then we look at EID which says pop E from the stack and push, TE prime in the reverse order on the stack. So those of you who miss this part, please go back and study this part. And what we are going to do now is that once we know what the algorithm is, then we want to construct. So we went through this example completely and we finally reached a state where we came to a hot state where top of stack was dollar, input is dollar, etc. This is where the parsing terminates. So next task in front of us is that now we want to construct the parse table. So there are two parts, so let me go back to the parser once again. And here we said that this is the parser, we have discussed this algorithm. And this parse table which is encoding off this grammar into a table or form like this, this is what you want to understand now. That how we are going to take this grammar and convert this into a table. Is it making sense or you want me to take another extra class and repeat everything what we did in the previous class? So we will then move on from this part. Okay, so what we are going to do now is let's take this grammar. Which is this grammar and then see how do I convert this grammar into a table or form. So this is my grammar which I'll keep using. So let me just write it as I go through this set of slides. So e prime is going to plus e prime or epsilon and then t is going to f t prime and t prime is going to power f t prime or epsilon. And f is going to bracket an expression of i t, this is what my grammar is. And what we'll start doing is we'll start analyzing this grammar. And then we will come to somehow see that this grammar can be actually rewritten into a form like this which will help me doing the parser. That is the part which is immediately in front of us. So how do we start doing it? So first thing we start in looking at was, we said we are going to define what we know as a set of first symbols. Now I'm also going to define another set of symbols which I call as follow symbols. And then I will define how do I compute first and follow sets. But basically what this means is that if I say that there is some start symbol which is s which is deriving w which is a string in my language. And then some other symbols let's say a which is a non-terminal which derives this part of the string. Now I say that since a derives this symbol and obviously this is a string of terminals. Let me say that the first symbol that can occur any derivation starting from a that I'm going to call as the first symbol. And whatever is the symbol which can come into a string which is or which come immediately after the string which is derived from a that I'm going to call as follow symbol. And what we need to do is we need to compute for all the non-terminals here the first and the follow sets. And once I compute this then I'll show you that using that information how I'm going to put this information in a tabular form so that I can then do parking from that point on this.  How do we compute first set and how do we compute follow sets? So let's start by computing the first sets. So I'll keep this definition in front of you and then slowly I will try to develop the algorithm for this. Now this is that if I start any derivation from a non-terminal then let me just find out what are the possible sets of or what is the possible set of terminal symbols which can come. So let's look at this. If I start a derivation from E then what are the possible terminal symbols which can come into a string which can be derived from E. Now how many rules do I have for E? Only one rule which says E goes to T prime. That means if I'm trying to compute first of E then since T comes in the beginning it must be same as first of T cannot be anything else. And therefore we say that this is first of T and if I now look at productions of T there is only one production corresponding to T which says T goes to F T prime. Which means that any string which can be derived from T must start from something which is in first of F. Cannot be anything else. And therefore we say that this is going to be same as first of F. And then if I look at first of F what are the terminal symbols which can come in the beginning of any derivation starting from F. Left parenthesis and id. These are the only two symbols which can come into any string which can be derived from F. So therefore I say that this is nothing but left parenthesis and id. So first of E first of T and first of F they are the same and this is the set. Now what about first of E prime? So I am doing this computation for all the non-terminal thing my ground. So if I say first of E prime, sorry so let me first compute first of E prime let me go in that order. So if I look at first of E prime how many productions do I have for E prime? Two productions. So this says E prime goes to plus T prime or this says E prime goes to X prime. So what are the symbols which can come into any string which can be derived from E prime? So basically this is nothing but plus and epsilon. Now this I will discuss in little more detail. Because how do I get epsilon here? This is slightly tricky. What this means is that E prime can derive epsilon. So the way to interpret this is that E prime when I say that E prime plus is in the first of E prime what that means is that if I start deriving from strings which start with E prime then string must begin with plus but E prime can also derive epsilon. Now when I say it can derive epsilon I have to look now slightly more general. So suppose I say I have a situation like this which says A1 goes to X1, X2 or to say Xn. And I am trying to compute first of A. Now what is first of A? First of A first of X1. So now you have already got it. So it is first of X1 but if X1 derives epsilon suppose I have a production of this form it says X1 derives epsilon. Then it is possible that in some derivation I can say A derives X1, X2 up to this and then I say X1 derives epsilon and then anything which is beginning with X2 can also be part of this. So therefore we do not say that first of A is equal to first of X1 but what we say is first of A contains X1 except but if first of X1 contains epsilon which means I have this production then it also contains. So I will now take a union it contains first of X2 and now it is possible that I have a production of this form which says X2 also goes to epsilon that is possible. So then I will say this contains first of X2 except epsilon and I will keep on doing this. And if all of first of X1, first of X2 and first of Xn all of them contain epsilon in the first symbol then I will say that A can therefore derive epsilon and therefore epsilon is also containing first of A. So this is the logic I am using here that first of E prime contains plus and epsilon and if I now look at first of T prime, what is first of T prime? Star and epsilon. I have only two productions T prime going to star of T prime and T prime going to epsilon. So now it will be, so this is what my first X are for all the non-terminals in the language. Now let us get on to computation of the follow sets. So let me keep this figure because that is going to give you some hints of how I am going through the computation of the follow set. So suppose S is my star symbol and I say that S is deriving any string in the language I have. Yes, W is any string in the language which can be derived from S as is the star symbol in my grammar. Then what is containing follow of S? Look at this figure. Now what are the symbols which can follow W? Because that will be follow of S. I introduced a special symbol remember. So dollar always is in follow of S. That is why I introduced dollar. We do not want to worry about end of string and so on. And we are saying that always we are saying by putting a special symbol here dollar is in follow of S. That is the first definition. That is the first initiation or first initialization. So always take the star symbol of your grammar and say that dollar is in follow of that star symbol. And remember that since you are doing the top down parsing, we will start from top down and keep on computing all these follow sets. Now let me look at patterns. So my first tool is dollar is in follow of S. Now suppose I have a pattern like this. A goes to suppose I have a pattern like this. And I want to compute the follow of B. Then what is follow of B? Follow of B contains beta. Follow of B contains beta. Beta is a string of terminals and non-terminal. It contains first of beta. So follow of B. If beta goes to epsilon, then follow of B also contains first follow of A. So we will come to that later. First thing we are saying is that follow of B contains first of beta except epsilon. See in follow sets epsilon is trivial. I mean after any symbol you can just put an epsilon there and say this is in follow of. So I can purely put any number of epsilon. And therefore you will notice that follow sets actually do not contain epsilon. The first which contains epsilon is because it can derive epsilon. So if I have a pattern like this, then I will say follow of B contains first of beta except epsilon. Everyone agrees with this? Everyone is comfortable with this? Next pattern. It was just brought out. If I have a pattern like this and beta derives epsilon. Then what will happen? I will now say that follow of B contains whatever is in follow of B. And I can have only one more pattern. The pattern is if I say A goes to alpha B, where B is another number. Then again the same rule will apply and I will say that follow of B contains everything in follow of A. So it is A which is deriving alpha B. So my pattern is something like this. A derives alpha B. And this is therefore this was my initialization. So I started with the start symbol. Then I am going down in the tree. Follow of A will contain follow of B. From the context. We can derive something like this. So follow of B contains. Can you think of any other pattern? Actually I have taken care of all the pattern where non-terminal occurs at the end. Non-terminal occurs in the middle. Where epsilon is not followed by the non-terminal or non-terminal occurs in the middle. And epsilon is followed by this non-terminal. There is no other pattern I can think of. So using this and exactly what I am writing here is derived from just this figure. If you can conceptually understand what this figure is saying. Then these rules are nothing but just a conversion of what we are seeing in this video. So now a trick. And that trick is that if you see rule number 3 and rule number 4. Here I am defining following terms of following. And therefore what may happen is that I compute one follow set. And then I look at another rule which again is going to change the follow set. This is a recursive definition. So what may happen is that if I keep on computing this. I must recompute it again. Because it is possible that depending upon the order of the rules I pick up. These follow sets can change. And I must recompute follow sets using rule number 3 and 4. So long as I cannot really add anything new. But can I go into infinite loop because of this. I can keep on computing and I never stop. Is that possible? Yes, no. So look at this context. Every time what is it that I am doing? I am adding something. I am never removing anything from the follow set. I am only adding. And then if I add something and how many terminal symbols I can have in my grammar. Is that known? There is not a bound on that. So is it monotonic function? If it is monotonic then you know that it will converge. So I do not have to worry about saying that I can keep on computing this. And I may never terminate. So either I am adding something or I am keeping it constant. But since I know if I keep on adding I can only reach the maximum number of non-terminals. And therefore I have to stop there. So let us compute now follow sets of same grammar. And let us compute the follow sets. Let me do one thing. Let me remove this screen and let me just do the computation of the same grammar. And then construct the pass table right away. Because once I compute first the follow set and converting this into a pass table is straight forward. So let me write all the symbols here. And symbols are E, E prime, T, C prime, left. And if I apply rule number one. So what I am going to do is I have written the four rules here. And I keep on applying them again and again. So if I apply the first rule. First rule says E is my start symbol and therefore dollar is in follow. That is what the first rule is saying. Nothing. Second rule says now look at patterns where a non-terminal occurs somewhere in the middle. So I am now looking at this pattern. Where I say that T occurs somewhere. It has a symbol which is on the right hand side. And using this rule when I apply rule number two. I will say that everything in first of E prime except epsilon is in follow of T. That is what this rule says. So let us look at first of E prime which I have already computed here. Which is plus and epsilon. So follow of T will contain plus. Remember everything except epsilon. What about this? Here there is again a non-terminal. But this pattern is same so it is not going to add anything. Now what about this? I will say that follow of F contains everything in first of T prime except epsilon. Now what is first of T prime? First of T prime is star epsilon. So follow of F will contain star. And this pattern does not give me anything new. This is the same pattern. And what about this? Follow of E will contain right parenthesis. So follow of E will also contain right parenthesis. This applies the third rule. And third rule says, so just mechanically go about applying these rules. And third rule says that look for patterns where B occurs or a non-terminal occurs somewhere in the middle. But the right hand side of the non-terminal is epsilon. So if I apply the third rule this says this one, this pattern. This says E prime goes to epsilon. So first of, follow of T will contain everything in follow of E. So follow of T will contain everything in follow of E which is dollar and right parenthesis. I have already computed follow of E. And that is where you see the problem starts coming. That I will have to go over and over again. Because one follow is defined in terms of another problem. And if I look at this, this says follow of T because E prime derives epsilon. Therefore follow of T will contain everything in follow of E prime. So follow of T will contain everything in follow of E prime which is empty so far. So it does not get anything added. What about this? This says follow of F will contain everything in follow of T. Because T prime is deriving epsilon. So what is follow of T plus dollar right parenthesis. So follow of F will contain plus dollar right parenthesis. And what about this one? This one says because T prime derives epsilon. Therefore follow of F will contain everything in follow of T prime which does not add anything. What about this? Can I apply this rule on this pattern? No. No. Because this is not none. What about this? This is not a non-terminal. So I stop. Now I apply rule number 4. And in rule number 4, I am looking at patterns where I say that a non-terminal is in the rightmost position. So here is a non-terminal which is in rightmost position. So follow of E prime will contain everything in follow of E. So this will be dollar right parenthesis. And here it says follow of E prime contains everything in follow of E prime. It is trivial. Follow of T prime contains everything in follow of T. So this will contain now plus dollar right parenthesis. And this one says follow of T prime contains follow of T prime does not add anything. Here I do not have any non-terminal on the right function. So I stop. Now this rule number 3 and 4 have to be applied again and again to recompose. Still I know that I cannot add anything more to the set. So it is application of the rules clear what we are doing here. Now let me simultaneously start making the part here. So my past table remember that it was indexed by the symbols which were E, E prime, T, T prime, S which were my non-terminal symbols. And then it was also indexed by all the terminal symbols. So what are my terminal symbols? Terminal symbols in this case are id plus star left parenthesis, right parenthesis and dollar which is something I have introduced. So I have plus star left parenthesis, right parenthesis id and then dollar. So now what we say is that because we are saying that E goes to id. Now what that means is really that look at all possible patterns. Look at all possible rules and if I have a rule like this which says E goes to alpha. Then what this means is that if I now have a table and I look at A and first of alpha. So I am looking at corresponding to this rule. I am looking at an entry in the table which corresponds to this non-terminal and anything first of alpha. What should be the entry in the table corresponding to this entry? All I am saying here is that what is the entry corresponding to? This saying that if I, this is top of my stack and this is the look ahead symbol. Then what should I do? Did I have using this particular rule? So corresponding to this entry in the parse table corresponding to this non-terminal and for all first of alpha except epsilon use this rule for derivation. So when I start using this rule what it says is that if I look at first of E. First of E contains left parenthesis and id. So E goes to TE prime is the rule here because all I am saying is that corresponding to this and left parenthesis this rule I have. Now this also telling you something very interesting and that interesting thing is that all valid strings in this language must start either from id or from left parenthesis. They cannot start from either plus or multiplication of right parenthesis. That will be all. E prime says that all valid strings which can be derived from E prime must start with plus. So forget about epsilon productions for the time. So this says that if I now look at first of this that is plus. So E prime and plus is going to give me a rule which says E prime goes to plus E prime. What about this rule? This says T goes to F T prime and what is first of F? First of F is left parenthesis and id. So corresponding to T I will say that T id is going to T goes to F T prime and left parenthesis is here. So this says T goes to. What about this rule? This says T prime goes to star F T prime. That means whenever I see star and this is the non-terminal then I can use this rule. So this says T prime and star is here. So this is T prime goes to star F T prime. So just align this. This is roughly here. This corresponds to plus. This corresponds to left parenthesis and so on. So if I look at this rule which says F goes to bracketed expression then what do I do? What rule do I use? And what is the entry I am making here? So corresponding to F and left parenthesis I will say F goes to bracketed expression and corresponding to F id I say F goes to I. So just by looking at the first set I can make these entries in my past table. I don't want to do anything else. Is this clear? Now let's come to epsilon productions. How it says that somewhere E prime goes to epsilon. I don't have any entry because there is a rule. Possibly there will be an entry corresponding to E prime going to epsilon. Now what are the situations under which the concept will be now visualized. So I am not giving you algorithm. Algorithm I can describe much later. Conceptually if you can understand that will be much clear. So what are the situations under which E prime goes to an epsilon? So look at a situation like this. Again from the derivation point of view that if I say somewhere A goes to so let me slightly redraw this figure and little more space. So somewhere I have a situation like this. A goes to let's say some alpha and let's say E prime and then E prime goes to epsilon and alpha is something. What are the situations under which I will use this production which says that E prime goes to epsilon? No other production is working. That's too vague. Because when you say no other production is working what that means is that I can make those entries only when I am parsing this thing. But I make parsed table before I start the parser. Before I start the processing of parser. Goes to id. E prime can never go to id. There is no room. Right? So if I encounter id and the terminal symbol is E prime not terminal symbol is E prime then I will use epsilon. But in input I will see only terminal symbols. I will never see any non-terminal symbols. No. I write E prime and I saw id. Then I will use E prime. But that's another. You said something. What are you saying? So when I see a symbol in follow of E prime then I know that I can just throw E prime reduce it to epsilon because that's a valid entry. Remember that I talked about sentential forms. I am saying that what are the possible all possible innovations which can happen from this. So I must all the time have valid sentential forms. So therefore in any valid sentential form I am capturing this information either by first or follow sets. So now I am saying that in case E prime goes to epsilon then look at follow set of E prime. And in that entry so I say that if I have an entry like this A prime going to epsilon then look at entry corresponding to this and follow off and that entry is going to be. Can you see this? What is happening here? So this is all I need to do. That's why I computed follow sets. So now if I see that I have a production which says E prime goes to epsilon let me look at what is the follow set of E prime. And if I say follow set of E prime is dollar like parenthesis then I say corresponding to this E prime goes to epsilon and E prime goes to epsilon. Because these are the two symbols which are in follow of E prime. Similarly I will say I have a production which says E prime goes to epsilon. So I look at follow set of E prime and I say that corresponding to plus so where is E prime corresponding to plus I will say E prime going to epsilon corresponding to right parenthesis E prime going to epsilon and corresponding to right parenthesis corresponding to dollar E prime going to epsilon. See I did not take you through next level of application of three and four. I mean that you can do. But basically this is the logic I use for construction of the past case. And this is really what I have done. I started with this grammar. Then I computed my first sets. I compute my follow sets and I encode this first and follow information. This tells you all value substantial forms which can come in this language and rest of it can be just tagged as an error state. Because anything else will say that this is not a value substantial form and therefore should be discarded. It should be flagged as an error state. Questions? Anything else? If something is not clear ask me now. So just by pre-processing this information computing first and follow sets and everything comes from just this figure. Really there is nothing else. If you can just remember this that I deriving this particular string and part of it derived from A and here is first and here is follow then everything can be just visualized and everything can be encoded from this. Now let me come to a different situation. Now suppose you encounter a situation where somewhere, so let's take this particular set. Now you encounter a situation where you say that top of my stack is replying. My input is star. What does that mean? It's an error, right? Still flagging error. But then what will you do beyond that? Will you stop the process of parsing and say your input is incorrect or will you do something more? You said recover, right? So we were saying that at some point of time it's not sufficient to say that I have an error but it is what is required is that I should recover from that error and should do more parsing and find more and more error. Now what does recovery mean? I've got into a situation where I say that my input is let's say star and my top of stack is replying. This is my input pointer, this is my stack pointer and parser says I have reached an error state, right? So how will parser continue from here? Has reached an error state? How do I continue? I can continue only by if I reach one of these entries. Now how can I reach one of these entries? I must manipulate my stack and input to reach one of these entries. So first attempt, okay? Suppose I say I know that this input is incorrect. So look at this. Suppose I'm trying to parse clear up a little more space. Suppose I'm trying to parse p plus star i. Now I'm not trying to guess the intention of the user. I'm not trying to guess because I already know this is incorrect. And by guessing I may create more mess. But I want to find more and more errors. There's no guarantee that I'll be able to give all right errors. But suppose I say id has been consumed plus has been consumed then I see star here. What I was expecting was something else. I could either have got an id here or I could have got a left parenthesis here. So if I discard this input and I reach this, can I continue parsing? I can, right? So what is the general principle therefore? What are the symbols I have on this card? Till you hit a symbol which is in first off, e-time. So if I say that my top of stack is e-time and I have reached an error state, I say start discarding symbols. Till you hit a symbol which is in first off the non-terminal which is on top of stack and then I'll find an entry corresponding to that in the pass table and hopefully I'll be able to continue parsing from there. That is one step. So is that it? By discarding part of the input I can continue parsing. So another way, so if I pick up an example from programming languages. So suppose I have statement one followed by semi-colon statement two followed by semi-colon statement three statement four, okay? Now suppose, or let me say there is a semi-colon here but let's say this statement was something like this, okay? And I found that something is missing here, okay? Then what makes me look at this is let me discard this input, okay? And when I hit here, okay? Then hopefully I'll be able to continue parsing from that one, okay? Now remember that when we talk of error recovery there is no hard and fast tool which you say that I'll be able to recover from this error because it is possible that the idea of recovery I may actually discard more errors, okay? And in some situation worst cases I may reach end of the program, okay? But this strategy is telling me that at least there is a hope that I'll be able to recover from this and continue parsing, okay? So first strategy we use is that if top of stack symbol is A then discard input till I hit something which is in first of A and then try to continue parsing from there. That is one, okay? Can somebody suggest me? One more strategy, please? So another strategy is continue discarding input till you hit a symbol which is in follow-off A and then pop A and try to continue parsing from there. So these are the two strategies which are used and this is also known as panic mode error recovery where we say that I will either discard some symbols. Now can I keep that as part of my parsed level? What are the symbols? Because I know the first and follow-offs, right? So I can always compute that if I'm using now follow-offs, okay? I can say I know follow-off E and what are the symbols which are in follow-off E? Follow-off E contains trite parenthesis and dollar. So let me say I call that as a sync symbol. So I'm saying if I get into error state then I can sync on this and syncing on this means that keep looking for symbol which is in the sync set then pop this symbol and continue parsing from there. Works, okay? So these are the two strategies which are commonly used. The other strategies people have worked on so there is a lot of literature which may be available if you see where you will find that people will try to guess intent of the user and will try to correct but that's really the dangerous area and not many compilers try to do that, okay? And therefore the common error recovery mode that is used is that first you try to find a symbol which is in first off top of stack discard everything up to that symbol from the input try to continue parsing and the second strategy is look for a symbol which is in follow-off what is on top of stack pop this symbol and try to continue parsing from there. That's all about top-down parsing. So now we know how the parser works now we know how to take a grammar modify the grammar to remove all kind of recursion from that convert that into a parse table and how to do error recovery what more do we want? there is nothing else we need to talk about so let me now quickly take you through this slide size sort of discarded and then so in the slides you will find the same thing what we have discussed here and I will just take you through that so it will give you little more structure than what I was discussing in the book alright so first I compute first x so we say that x is a terminal if it's a terminal symbol then first of x is t value x and if there is a production of this form then we say epsilon is in first of x and if I have a situation which says x goes to y1 to yk and each of y1 is yi is included in first of x epsilon and if all of the yi's contain epsilon then we say that first of x also contains epsilon so this is what we did in the computation of first set and this is what I just computed that first of e, t and f is left parenthesis and id and first of e prime and first of t prime are these sets and then we computed follow sets so we said dollar is in follow of s which is the start symbol and then I looked at various patterns which says a goes to alpha b beta a goes to alpha beta and it goes to alpha b beta where first of beta contains epsilon and then we computed follow sets and for the same grammar this is the follow set we come out with and once we have these follow sets we construct parts table and what do we say that for all rules of this form a goes to alpha we say that if a is in first of alpha then I am going to include it here and for all symbols if epsilon is in first of a then I am going to use b here which is in follow of a and any grammar which has a pass table without any multiple entries is also called l l 1 grammar so in this case my look ahead is one so this is another test which is used that you actually construct a pass table and see whether you have multiple entries for some grammars you will not be able to construct a pass table with only single entries in each set so a grammar whose pass table has no multiple entries is also known as l l 1 and these are the various generators which are available to us which are top down parsers antler is one very popular parser but then there is l l jn l l next jn and then you can search on that so there is something called a tiny parser generator y parser generator slk and so on so these are all top down parsers which are available to us error handling if we stop at the first error and just give an error message that may be very friendly to us as compiler writer definitely is not something which is desirable from the user's point of view so we must do error recovery and every compiler actually recovers from errors and tries to identify as many errors as possible so panic mode so I will straight away take you to what I discussed you can read rest of it there are many methods of doing error recovery so nobody actually will try to do correction except some compilers where you say that anything can be compiled like plc had a compiler where they were saying doesn't matter what you write they will try to always compile it by guessing your intentions was not very successful so error recovery the way it works in ll1 parser we have just discussed error circuit when you have a pass table entry which is empty and so skip symbols in the input until you see a selected set of tokens which is in sync set and what are these tokens I can either place symbols which are in follow of a in the sync set then skip terminals until you see something in follow of a pop a and continue parsing from there or add symbols which are in first of a in the sync set and then it is possible to resume parsing according to it if you can then skip symbols till you get something in the sync set right so this is we are going to stop today next class we are going to start bottom


Life is short. Make the most of all the opportunities you get. Make sure you read and read deeply. Be braver. Be an optimistic person. Just be very open. Explore the needs of the community. Get involved and get connected. Be brave. Don't be scared. Life is an opportunity. You have to have the dream. Studies is the most important thing in your life. Keep trying. Never quit. Be passionate. Apply for an Australian Award. Let's close it. Never give up. Keep dreaming. Don't be scared. Just go for it. To make the most of the opportunities that come before me. To work hard and achieve the dream and to come to Australia for studies, to advance. See what's around you and if you can see a gap, feel the gap.


Hey, hello everybody, and welcome to Batchy Talk. I am Andrew, the security guy, and Gordo the Texar is busy, so he's not here today. Angus went with him, but I got a great guest for you, Mr. Rodney Thayer is here, security analyst, security expert, all things security, and we're going to talk a lot about penetration testing today, and some of the, maybe more behind the scenes things that you don't know, so stick around for this. Rodney, thanks for coming, brother. I appreciate you coming in on a short lease there. So I know you've been on before, but go ahead and give our guests a little bit of your background, kind of where you grew up and some of that stuff. So we grew up in Massachusetts. Sorry. Been doing, hey, you know, I moved to California, so you know, I don't do snow no more. So been doing computer stuff for decades, starting since the 70s. Did you have computers then? Yeah, they only had zeros, we had to pound and flat with rocks to make ones. That's kind of the way it worked. So I've been doing software development and networking, and then got into encryption, and then from there got into doing security stuff. And you know, there's something in water in Massachusetts, something about the Redcoats in 1776 and all that. So it turns out I'm really good at thinking like a bad guy, so I get on the computer security, cybersecurity side of things. Okay. And so you've been out of Hawaii before, done some work out here as well. I know we've got a project now, which is fun. All right. Well, we wanted to get into for our audience today, really into penetration testing. And this is a piece that sounds maybe meaner than it is, but it's really a tool to help people understand what they've got, what their attack surface is.  And I thought we'd just sort of walk through that and let Rodney sort of give you the what that piece is about and what happens in that space. So we tend to start with what's called reconnaissance. You know, hackers don't just show up and start doing things. They're smart and they like to look and see what's available. So in your perspective, what goes on in that reconnaissance phase? You know, what are you looking at for a client? So this is all in cyberspace. So we're doing things looking at networks and websites and email and things like that. But you do the equivalent thing you would do in the real world, meet space as the hackers would say. So you go around and look for places where there are weaknesses, chinks in the armor. You know, if you were a bad guy walking down the street in the middle of the night, throw a row of shops, you check all the door knobs, see if somebody left the door unlocked. So you do things like that, try to figure out through something that was unsecured or something that was in the internet case, is there something misconfigured? Because if they got one thing wrong, if they screwed up how they set up their website for one thing, they may also have other things configured wrong. And you can therefore, you can start to identify weaknesses and things. So in the reconnaissance phase, you probably wouldn't attack, but you maybe would just begin to formulate the types of attacks you were going to do.  And certain cases. There's homework. Hacker homework. Yes. Yes. Hackers like everybody else use Google.  And, you know, the vendor might very proudly publish their manual online, complete with the default passwords for the gear. So, you know, if it's, you know, Billy Bob's Wiggy Bob, I'd go look that up online and find the default passwords. And so then I could have armed with that information to go back and try to use that for the attack. I see. Yeah. A lot of times they'll give you like password length or type. And so, you kind of know what you have to do if you're going to brute force it or something. And again, this goes back to the, you're kind of doing recon time things. If you, if you find people using four character passwords, then they've got weak passwords. So you can kind of, you now know that there, there are things about their design of the system or at least the way it was deployed that might be issues. So reconnaissance reveals a lot. So, so what you've done this reconnaissance, the next phase in the kill chain is this intrusion portion. And what does that look like? Are we trying to go deep at this point or? At that point, what you're trying to do is get inside the network that you're trying to attack or the infrastructure is a sort of a better way to look at it. You know, these days, there's many, many networks in like inside a building or in a bank or any kind of organization. So you're trying to get inside the network somewhere so that you have a toehold and probably do more attacks from that. Oh, so get in there and then you're going to maybe hat out or plant something. Right, or plant something or use that as a place where you can, you can reach even further inside the infrastructure. And would this always be like done from behind the keyboard remotely or would you possibly have entered a facility in this intrusion phase? Going into the facility, that would require work, dude.   Okay. So the, because everything's connected on the internet, it's often done not physically at the location. Okay. So you, but you have to be connected to things through the internet. And, you know, the internet isn't like, you know, I didn't have to swim here from California, but I did have to ride in an airplane for five hours. Sure. But, you know, you're only like a hundred milliseconds away if I've been trying to do it through the network. Yeah, internet. So you could be anywhere and get a great distance. And so, but what's our intrusions done and we've gotten this toehold or we've, we've opened a door that we can get in and out of pretty readily. This exploitation phase is what they talk about next in the kill chain. So what, what am I going to do then, you know, when I, when I start to exploit this, this, these vulnerabilities, I guess that I've found. Yeah. Well, you, between the recon and the, and the initial penetration into the, into the site, you'd go identify what kind of targets are, are most likely either the ones that are easiest to go after, or the ones that are the highest value. Okay. So you end up doing sort of a triage kind of thing. And again, these are hackers. So the triage, it's not like the military where we do a calculation on all this. It's, it can be something like, you know, I'm bored, I want to go to dinner, or I'm only going to do the quick ones. So you can have some kinds of attention span issues of the hackers sometimes.  You get more of a, you know, the good guys who are trying to defend things can get, get some information out of that, get a little bit of signal. Ah. So in the exploitation phase, it's maybe they're a little more vulnerable to being caught or a little more vulnerable to revealing that they're there and you may, you may find them in this phase. So, so I'm in, I've found some, some, some stuff I want to get. I found some exploitable material. Maybe I can sell this information or whatever's. The next thing we talk about in the Kielce is privilege escalation. So what am I going to try to do there?  Okay. Like if you're in a Windows environment, if somebody forgot and set up a file share with a bunch of documents in it, which isn't protected, but one of the documents is all the passwords in the firewalls. Okay. And believe it or not, people do things like this. So you would go look for any information or weaknesses you can use to change from being a regular user into some sort of privilege user or users on other kinds of systems. So like if you're in a bank, you know, you'd get into the ATM and then you try to get past the ATM to get into the good machine in the back room that can transfer millions of dollars. I see. So you're trying to, trying to increase your privilege within the customer, the victim's network. So like they call it's like a super user or an admin or administrative user or something like that. So if you see a bumper sticker in a car that says got root, you should be worried. Is that right? That's not the guy you want roaming your neighborhood and jumping on your Wi-Fi network. Right. Is, is this worth spending time on? I mean, if someone in certain environments, is it more valid? Because if you've, but you're past the exploitation, you're kind of available to be in caught. So would you spend a lot of time trying to escalate yourself? Can you hide yourself once you do that? Well, you try to do whatever the easy targets are. Again, you're trying to do triage stuff. Depending on what the adversary is going after and how valuable the target is, they may set up so they can take their time doing it. So like if you're going after a big retail operation and you think you can get your hands on millions and millions of credit cards, it would be worth taking the time to set up, set up some exploits, try to set up some back doors that you can get back in later because they may or may not be able to detect that kind of stuff. I see. So then, and then, you know, if you can get that thing set up so you can take your time, that would do that. So what does it look like, you know, from the keyboard perspective to this hacker as he's moving around? Is he adept at, at knowing where he is, at seeing other machines and what type of operating systems they have and things like that? Are there tools that he's using? There's tools that are using the most specific machines and you end up with specialties. It's, you know, it's, it's like a lot of other things. They're specialists. So they're, you know, they're Mac hackers and Android hackers and Windows hackers and Linux hackers. So do they team up if I'm hacking? I need a, I need a Unix guy. I just called my buddy Unix and said, hey, can you help me hack this thing? Well, they'll also team up in specialties. So like I do the recon thing and the initial access because with my engineering background, I can see the weaknesses more than some 20 year old punk who actually is good at writing exploits because, you know, they'll say up all night and write the code and I've read a sleep. Okay. So you end up with specialty combination teams. Interesting. Interesting. And so I guess that brings us to this next phase of the kill chain is we're talking about the lateral movement. So, so I've gotten in the network. I've maybe taken some stuff that helps me learn more about the network. I've escalated some of my privileges and now I need, now I want to move around. And as this shows, you know, they, I know they talked about, I think, target how they initially got into a POS vendor, got them in a system and they were able to move out throughout the entire like credit card system, things like that. So is that lateral movement or are we moving anywhere that I can get to? So, well, they look around to see what's available for targets. Okay. And no pun intended. And so they, you would find, you would be things you've been trying to look for, like you might be looking for credit card data or you might be looking for financial information. Or if you're in a hospital, you're trying to find the, you know, combination codes to the drug closet or something. Okay. Or healthcare records or whatever you can sell. Yeah, but you're also, you're trying to monetize the experience probably. So if you're in a retailer and you find the drug closet combination, you'll probably grab a copy of that so you can sell that tool. I see.  And the lateral thing is that, yeah, they move around between different kinds of systems. So like in the target case that we're going after the vendor who sold them air conditioning equipment. Right. And they move from that to the, to the corporate network. And they move from that to the cash register and POS system. POS networks. Yeah, yeah. It was an HVAC vendor. Yeah, they brought them in the door. So would you, would you try to jump on another vendor? Say if you're in there and you see a guy plug in and he doesn't know what he's doing and you can jump on him and go out the door with him to someplace else? Yeah, yeah. Okay.  And, you know, when they pull into the next bank, they're doing the firewall install for you. They probably be sloppy there too. I see. Okay. So you can profile the victims and sort of see if they have patterns that you can use repeatedly.  And so this is just trying to not be found. So you're staying there. You don't want to be found? Or maybe you've left and you still don't want to be found? What do these tracks look like? So you do things like you would make sure there's no logs left behind. If you log in, you delete all the logs or something. You'd make sure that as little as possible, there's little information is possible of anything you attempted to log into. So this is why when we give security advice, we want to make sure people have enough instrumentation in their network so they know about failed login attacks. I see. So, you know. So this is when you were trying different passwords and it didn't work. That should show up. That should show up. That should come up with an error and that should be logged somewhere. Okay. And is it a common practice for network administrators to alarm on that kind of thing so that they see that behavior in their network? Or is it the kind of thing that's easy to get? It's not common enough. It's getting better. I see. Used to be people would never log these things because they would just get continuous alarms from normal users, you know, mistype the password once kind of things. So the false alarm rate used to be the issue. Nowadays, you can get more and more sophisticated equipment so it can help you deal with the false alarm. So, you know, when you try to log in your bank account once and type the password wrong, yeah, whatever. When they see me log in 72 times from Hawaii to my California bank account. Within two seconds. Within two seconds. Because it's a machine doing that. Yeah. They would decide that was an odd behavior and there's equipment that would flag that. And then you're trying to make sure that whoever has to look at these alarms has a reasonable alarm data to look at. They're not having to look at false alarms. Sure. Okay.  And so we're, so we've gotten in, we've hidden ourselves, we deleted the fact that we're there. Presumably they could maybe figure out who you were, forensic investigator could follow the data about you backwards.  If you were, if you're silly enough to do a tax from your home network, yes, then some people occasionally do that. Yeah.  But yeah, they would be able to track you back to the addresses. There's a lot of techniques to hide where you are on the internet. Sure. You know, being in the Starbucks is in fact probably pretty good hiding. If it's like five states over, not the one up the street. Well, if it's five states over and they don't find you for a month, then that Starbucks, whatever logging they've got in that probably has been flushed out. It's gone. Okay. That kind of thing. So, so what's your hidden now? The next, the next piece of the kill chain is this denial of service that they talk about. So where resources have become unavailable for like a legitimate user. And so what's the idea there? Because it seems like there'd be notification that something's wrong. Well, so the causing the denial of service by itself can have value if you're the bad guy. Oh, I see.  Maybe someone's paying you. Maybe you're trying to hassle a company that has operators who get book orders on the phone. Okay.  So the competitor would pay you to shut down the phone system. So that company would lose money. So just the act of having the lost resources can be the target. The other thing is if you have denial of service, then you've got, you know, you're in the middle of a storm, everything's dark and you can then go after things and people wouldn't see it. So if there's a denial of service and I'm causing failed login attempts, they're not going to notice those in the middle of the millions of other kinds of errors. Got you. So we're talking about the cyber kill chain right now with Rodney Thayer and we're going to take a short break. We'll be right back. Thank you. I'm a licensed marriage and family therapist and I'm the host of Shrink Wrapped Hawaii where I talk to other shrinks. Did you ever want to get your head shrunk? Well, this is the best place to come to pick one. I've been doing this. We must have 60 shows with a whole bunch of shrinks that you can look at. I'm here on Tuesdays at three o'clock every other Tuesday. I hope you are too. Aloha. Freedom is all of these and more regardless of your ability. Diveheart wants to help you escape the bonds of this world and defy gravity. Since 2001, Diveheart has helped children, adults and veterans of all abilities go where they have never gone before. Diveheart has helped them transition to their new normal. Search diveheart.org and share our mission with others and in the process help people of all abilities imagine the possibilities in their lives. Hey, welcome back to Batchitalk, Andrew, the security guy. I'm sorry, Gordo is not here. Angus isn't here, but Mr. Rodney Thayer is. We are talking about penetration testing.  This is the Oceanus 11 scenario. We've got all the gold out of the basement. Now we've got to put it in the pickup truck and get away with it. So exfiltration, this is where, you know, the bad news is we're all copying military terms and everybody knows what they mean now. So exfiltration is the opposite of infiltration. So it's when you've got something on the inside and you've got to sneak it out the door. So like you're trying to get all the credit card numbers and take them back outside the network or steal the company's trade secrets. And I guess you could still get caught at that point. You could still get caught.  So you combine all these skills together. So you want to make sure you cover your tracks as much as possible or leave as much damage as possible so they're too busy cleaning it up. Wow. So the penetration test is designed to sort of detect these opportunities in the kill chain inside of place. So a whitehead hacker like yourself goes into an organization and do you kind of go through these steps, kind of mimic these steps? You do a combination of going through these steps and for each step of the process identifying where the network you're looking at, where it might have some weakness that these things might apply.  You might just do recon. And the idea is to try to find the information that would be helpful to the people who own the network to actually defend it. Define loose ends. So maybe you give them a report back just after the recon piece and say, hey, this is some stuff I found. I could do this or that.  So you might do the recon and then go back and talk to the network group and say, hey folks, we found XYZ kind of a problem on this server. And you'd be a reasonable person about it. They may actually turn to their team and say, look, we've got 52 servers like that. Let's go check all of them. Wow. So you're trying to help people improve their defenses and be able to be able to have a better chance of surviving the next attack. Yeah, because the attacks don't stop. That's for sure. So can you share? I know you do a lot of government. I know you do a lot of things you can't talk about. Can you give us some examples of organizations that you've engaged in that you found stuff just really bad or really good or what type? Give us a couple of juicy bits. Let's see, juicy bits. So it's 2017 and we've been doing things like pen testing for 15 years, 20 years, depending on how you want to measure it. So there's a lot of this stuff that it's kind of shocking. It still happens. People still use short passwords. You can buy a Raspberry Pi for $35 and run a program on it that can crack four-digit passwords if they were all numbers in like two minutes. So it doesn't require giant supercomputers anymore. So it's a hacking's easier? Hacking's easier. So you don't have to be perhaps as gifted as yourself. Right. So the technology of doing hacking has been around for a while and it's evolving. And some of these tools can be used for good and bad. It's the same thing as anything else. If I take a paperclip and I straighten it out and I use it to pop the CD-ROM out of your old-fashioned PC with a CD in it, right? It's like then I'm your tech and I'm helping you. If I take the same paperclip, stick it in the lock, try to fiddle the pins and all that, then I'm doing the lockpick. So it depends on how you use it. The tool has multiple uses. The tool has multiple uses, yes. But the tools are getting more and more sophisticated. So they can do that. They can also automate the whole process. The recon, find things, penetrate, lateral, all that kind of stuff. So this is a piece of software that you can eat yet? It's a piece of software. You can buy these things, sometimes get them for free. And so you don't have to be that competent to run these things. Wow. So I've seen examples on the dark web of guys selling some malware services and a DDoS as a service and things like that. So these attacks are automated. Yeah, so what you need is a bad attitude and a credit card. Or maybe it's a Bitcoin if you're buying it.  So kind of things I found, a bad finding, short passwords. There's a lot of tools that can break weak encryption. It used to be, in the late 90s, we would talk about how encryption algorithms were really hard to break and you need millions and millions of computers and nobody could do it. And nowadays, with Google and Amazon and all these other things, people talk about things like 20,000 cores being available at one time, a core being one computer. And so you can get massive computing power. And so things we used to think were easy, were difficult problems that would protect us, that difficult computing situations that would protect us, they're not so difficult anymore. So that's what people are getting more and more sensitive to using strong encryption. I see. And you'll notice like the browsers are getting more, I call it militant, but the browsers are getting more and more active at giving you warnings when you're using weak cash algorithms. If you don't get the lock, if you're not using TLS, there's no encryption on your website when you go there. And you'll get lots of warnings and pop-up warnings and things. So yeah, hopefully there are clear messages for end users to use. The other thing that goes on to this day is that some of the error messages are really arcane. So people will call me up and say, this dialogue box said, this sentence, what does that mean? And you can't tell. You trust it, right? If I get messages like that, I don't believe any of it. That's part of it. Close it, I'll turn it off. Whatever's happening there, I don't need it. Right, all those wonderful things you can do with a browser to render different things, animation, all this other stuff. Yes, that's just like that's another tool you can use maliciously. Yeah, I don't know if our user basically understands that you can embed malware in an image. You can embed code into videos. So in modern times, we don't just have static information like a picture. It's not just a picture. It's a bunch of bits and there may actually be programs or other kinds of information attached to it. Word documents is another example. People will attach macros to these things. And this is trying to help people do work. So you might have extremely complicated macros in a spreadsheet you're using to talk to your accountant, calculating profits, all sorts of things like that. The same sort of mechanisms can be potentially used maliciously. I see. So and then delivered to you via your email inbox or by some link or something. Somebody gave you an USB file that you plugged in. Oh, never do that. Yeah, never do that. So do you find a lot of open networks that are people disabling USB in the world you see or is it still just a problem, really? No. I collect stories about how the, oh yes, it's a secure network. Right up till the day they call me to, you know, march me into the command center to help take the virus off their computer they're using in their air traffic control system or something. It came in via USB. Came in via somebody with USB. Okay. Wow. So what else have you been working on? I mean, so we've seen a lot of, I mean, healthcare has been attacked really badly. The financial sector obviously stays under constant attack. What's your experience in those markets? Have you been called in on some of these? Yeah. The beginning is that they're all running the standard kind of computers. So they've got to go through, they have all the same challenges everybody else has. So people running a bank have to worry about things like are their windows machines patched and do they have proper firewalls and other kinds of issues like if there are people with cell phones, are they using them to share data over the public network that they shouldn't be. So we get those kinds of things in the most sensitive of institutions. Wow. Yeah. And you know, we sort of saw, you know, some of what you mentioned, I know we were on the call with Jay Fidel for Think Tech on Monday talking about WannaCrypt, which, you know, really just people just didn't patch their stuff or they used old un-patchable stuff. You know, is that common? Do you see a lot of people with older, firmer, I mean, businesses try to, you know, extend their investment, right? Is what they would say. Well, they try to extend their investment. The other thing is that they're more and more their business is relying on networking or internet access. So, you know, people have a storefront on the internet. They may actually still have a physical storefront, but that's getting pretty rare. So their whole business is running through the internet. And the good part of it is that all of the back end services, insurance, bookkeeping, you know, compliance rules, all this stuff is looking at that more and more. So they're more and more business drivers to do things securely.  So it's now getting to the point where, you know, if your network gets hacked, you know, the board of directors might get sued. So, you know, now the big bosses, you know, potentially personally at risk if there were an issue. So they think about the risk. Is that swinging some of the calls that you get, you know, the opportunities you get invited into now? Is it coming from the board instead of the IT department? We get to use four letter words to start with R. It's called risk. Yes. And yes, it doesn't matter how technical or non-technical the CEO is, when you start talking about the risk issues, they will probably listen. And that's getting better and better. People are learning that that's important and there's more and more attention being paid to this. Yeah. Do you think that we're prone to, you know, like just as, let's just say, rampant of hacking opportunities as WannaCrypt was, do you think there's still more of that to come for the industry that's not prepared? Yeah. And do you think patches will help or do you think there will be, because this was an attack against older systems and unpatched systems, do you think? WannaCrypt was catching people with bad habits, having bad habits and using old equipment. So, you know, whether or not you have hackers to worry about, you should be doing backups if you're information. And this is, you know, I live in California.  You know, your building might fall down. You probably should deal with that. You should probably make sure your records, you have a copy somewhere else, preferably not on the fault line. So, you know, and these kinds of good habits have been people known about these, you know, at least since they've been using computers, you know, are people just lazier, or is there just so much more to do? People are so used to highly reliable equipment that they, you know, people will keep their entire life on their cell phone and never do a backup.  Ten years, you know, you've got still got the pictures on your cell phone, you never have a copy. So people, people have gotten out of the habit of doing backups, what little happens to it. The other thing that's happening now is people want to share more and more information, social networking, all that stuff. And when they share more information, they're more vulnerable, potentially more vulnerable, because you're providing more and more detail. So, you know, it's a bad idea to use your dog's name as a password.  And if you make your dog's name, your password, people would notice that. No, you think. You think. So penetration testing is alive and well. If you need some whitehead help, if you need some help at all, go find it.  Andrew, the security guy, we're going to sign off. Roddy, thank you so much for being here. Hope to get you back in here soon. Aloha, everybody.