Lexical Analyzer (Solved Problems) – Set 2 (YouTube Video Transcript)

(00:00:00) Your YouTube transcript will appear here (00:00:06) hello everyone and welcome back (00:00:09) we have been dealing with salt problems (00:00:11) on lexical analyzer since the last (00:00:13) session (00:00:14) today we will continue the same (00:00:16) so without any further ado let's get to (00:00:19) learning (00:00:21) coming to the outcome of the session (00:00:23) today we will observe two more solve (00:00:25) problems on lexical analyzer (00:00:29) consider this question in a compiler (00:00:32) keywords of a language are recognized (00:00:34) during (00:00:35) so we are to find out during which phase (00:00:38) keywords are recognized (00:00:40) before getting to the options let me (00:00:42) remind you that keywords are actually (00:00:44) tokens (00:00:46) coming to the first option (00:00:48) parsing of the program well parsing is (00:00:51) done in the syntax analysis phase (00:00:53) and there the inputs are the tokens so (00:00:57) keyword being a token (00:00:58) should be recognized before that (00:01:01) next option is the code generation (00:01:04) optimized code is taken as input in that (00:01:07) phase and as an output assembly language (00:01:10) code should be generated so keywords (00:01:13) have to be recognized way before that (00:01:16) option c (00:01:17) the lexical analysis of the program is (00:01:20) actually the phase where the keywords (00:01:22) are recognized (00:01:24) if you remember during the session (00:01:26) introduction to lexical analyzer we (00:01:29) observed how the dfa helped us to (00:01:31) recognize the keyword if (00:01:34) so this is the correct choice (00:01:37) now data flow analysis is performed (00:01:39) during code optimization on the program (00:01:42) flow graph (00:01:43) so it is never going to recognize the (00:01:45) tokens rather it analyzes the flow (00:01:49) control of the program (00:01:50) we will learn about this in details in (00:01:52) that code optimization chapter (00:01:55) let's now move on to the next one (00:01:59) consider this question a lexical (00:02:01) analyzer uses the following patterns to (00:02:04) recognize three tokens t1 t2 and t3 over (00:02:09) the alphabets a b and c (00:02:13) so these are t1 t2 and t3 (00:02:16) these are actually regular expressions (00:02:18) but they are represented in a different (00:02:20) style worry not we will understand it (00:02:24) see (00:02:25) we have been provided with some notes to (00:02:27) decode it (00:02:28) note that x followed by question mark (00:02:31) means zero or one occurrence of the (00:02:35) symbol x (00:02:37) note also that the analyzer outputs the (00:02:39) token that matches the longest possible (00:02:42) prefix (00:02:43) well we will understand this part later (00:02:47) now if the string bbaac (00:02:51) abc is processed by the analyzer (00:02:55) which one of the following is the (00:02:56) sequence of the tokens it outputs (00:02:59) and these are the options given (00:03:03) now allow me to first simplify these (00:03:05) modified rejects is for you (00:03:08) remember x followed by question mark (00:03:11) means zero or one occurrence of the (00:03:13) symbol x (00:03:15) following these conventions (00:03:17) t1 t2 and t3 becomes actually this (00:03:22) let me explain (00:03:23) in t1 a question mark means (00:03:26) this reg exportion may not follow any a (00:03:30) symbol that is zero occurrence or it may (00:03:33) follow one a symbol that is one (00:03:36) occurrence (00:03:37) so t one is actually (00:03:39) b or c whole star (00:03:42) this is the clean star closure which (00:03:44) means this can generate either nothing (00:03:47) or any number of b's and c's in any (00:03:50) sequence (00:03:51) and that sequence will be followed by a (00:03:54) single a symbol (00:03:56) or (00:03:57) a followed by none or any number of b's (00:04:00) and c's followed by a single a (00:04:04) similarly for t2 (00:04:06) none or any number of a's or c's is (00:04:10) followed by a single b (00:04:12) or (00:04:13) b followed by none or any number of a's (00:04:16) or c's followed by a single b (00:04:20) for t3 (00:04:22) bra clean star closure followed by c (00:04:26) or (00:04:27) c followed by none or any number of b's (00:04:31) or is followed by a single c (00:04:34) this one signifies zero occurrence of c (00:04:37) as a prefix of the reject portion (00:04:40) and this one on the other hand signifies (00:04:43) one occurrence of c as a prefix to the (00:04:46) same range exposition (00:04:48) now what we will do (00:04:50) we will observe (00:04:51) which one of these token sequences can (00:04:54) represent this string (00:04:56) bbaacabc (00:04:59) thereafter we will deal with the later (00:05:01) part (00:05:04) let's consider option a t1 t2 t3 (00:05:09) let's take a look at t1 first (00:05:12) the string begins with b (00:05:15) now from t1 if we consider this reg (00:05:18) exportion (00:05:19) we can represent bba of this string (00:05:22) using t1 (00:05:24) why so (00:05:25) because from this (00:05:26) b or c whole star we can derive two b's (00:05:31) and no c's followed by a single a (00:05:35) coming to t2 the remaining portion of (00:05:38) the string begins with a (00:05:41) so if we consider this regexportion (00:05:44) we can represent aca b using t2 (00:05:49) how (00:05:50) because (00:05:51) or c whole star can help us achieve ac a (00:05:55) and this b will generate the b following (00:05:58) aca (00:06:00) now consider t3 (00:06:02) in the string only the symbol c is left (00:06:06) now if we select this regex portion we (00:06:08) will end up having at least two c's (00:06:11) that's why we are going to choose this (00:06:14) one instead (00:06:15) so if b or c (00:06:17) whole star derives nothing we can still (00:06:20) have this c (00:06:21) so t3 can represent c (00:06:26) so (00:06:26) using t1 t2 t3 we can represent the (00:06:33) string now option b is t1 t1 t3 (00:06:38) let's observe the string for that (00:06:41) considering t1 using this regex portion (00:06:44) of t1 we can represent bba like the last (00:06:48) one (00:06:50) now we again have t1 and the remaining (00:06:53) portion of the string begins with a (00:06:55) now if we use this reg exportion it will (00:06:59) help us achieve aca that is a followed (00:07:03) by a c generated from b or c whole star (00:07:06) followed by a (00:07:08) consider t3 (00:07:10) we have only bc left in the string (00:07:14) if we select this portion from b or a (00:07:17) whole star we can derive b only (00:07:21) and the following c will give us bc (00:07:25) so using option b that is t1 t1 t3 we (00:07:30) can also represent the string (00:07:34) now next in line is t2 t1 t3 (00:07:38) let's consider that (00:07:40) observe the string again it's got two (00:07:43) b's at the beginning (00:07:45) now in case of t2 (00:07:47) using this portion we can generate bb (00:07:51) because b followed by nothing which is (00:07:54) generated by this a or c whole star (00:07:57) followed by b will give us two b's (00:08:01) coming to t1 the string now has two a's (00:08:05) in the beginning of its remaining (00:08:06) portion (00:08:08) and from this regex portion of t1 we can (00:08:11) generate two a's that is a followed by (00:08:14) nothing from this b or c whole star (00:08:17) followed by a (00:08:20) now the next one is t3 (00:08:22) observe the remaining portion of the (00:08:24) string (00:08:25) it is having c a b c (00:08:28) which can be generated from this regex (00:08:31) portion of t3 right (00:08:34) so using option c we also can represent (00:08:37) this string (00:08:41) now option d says d3 t3 (00:08:44) let's observe the string for that one as (00:08:46) well (00:08:47) if we consider first t3 (00:08:50) observe the string it is beginning with (00:08:52) b so clearly this rejects portion will (00:08:55) represent (00:08:56) bbaac that is two consecutive b's (00:09:00) followed by two consecutive a's will be (00:09:02) generated by this b or a whole star (00:09:06) and this c will generate the c at the (00:09:08) end of that (00:09:10) coming to the next t3 (00:09:12) if we observe the remaining portion of (00:09:14) the string we have abc (00:09:18) this can also be generated from this reg (00:09:20) exportion of t3 only br a whole star (00:09:24) will help us represent a b (00:09:26) and the c will represent the c at the (00:09:29) end of the string (00:09:30) so using t3 t3 we can also represent the (00:09:34) string (00:09:38) so basically all these sequences can (00:09:41) represent the string (00:09:43) let's have their representations (00:09:49) now focus on the second note (00:09:51) it says the analyzer outputs the token (00:09:54) that matches the longest possible prefix (00:09:57) so in case of option a and b (00:10:00) the prefixes have three characters (00:10:03) in case of c the prefix has only two (00:10:06) characters (00:10:08) only in case of d the prefix has one two (00:10:12) three four five that is five characters (00:10:15) so yes this is the token the lecture (00:10:18) will produce as output (00:10:22) so for this question option d is the (00:10:25) only correct choice (00:10:28) so in this session we have solved two (00:10:31) more problems on lexical analyzer (00:10:37) all right people that will be all for (00:10:39) this session (00:10:41) in the next session we will observe (00:10:42) various errors and their recovery in (00:10:45) terms of lexical analysis so i hope to (00:10:48) see you in the next one thank you all (00:10:50) for watching (00:10:51) [Music] (00:10:51) [Applause] (00:10:54) [Music] (00:11:02) you