Cs419 lec4 lexical analysis using re

WELCOME TO A JOURNEY TO CS419 Dr. Hussien Sharaf Computer Science Department dr.sharaf@from-masr.com

DEFINITION OF A LANAGUAGE “L” ∑ is the set of alphabets * 1. Let ∑ ={x}, Then L = ∑ * In RE, we write x * 2. Let ∑ ={x, y}, Then L = ∑ * In RE, we write (x+y) 3. Kleene’s star “*” means any combination of letters of length zero or more. Note: Please study the appendix at the end of the lecture Dr. Hussien M. Sharaf 2

RE RULES Given an alphabet ∑, the set of regular expressions is defined by the following rules. 1. 2. For every letter in ∑, the letter written in bold is a regular expression. Λ- lamda or ε-epsilon is a regular expression. Λ or ε means an empty letter. If r1 and r2 are regular expressions, then so are: 1. 2. 3. 4. (r1) r1 r2 r1+r2 r1* and also r2* NOTE 1: r1+ is not a RE NOTE 2: spaces are ignored as long as they are not included in ∑ 3. Nothing else is a regular expression. Dr. Hussien M. Sharaf 3

RE-10.1 Example ∑ ={a, b}, What does L describe? * * - L = (a+b) a(a+b)  Any string of a's and b's Any string of a's and b's Single a - Give examples for words in L {a ab aab bab abb …..} Dr. Hussien M. Sharaf 4

RE-10.2 abbaab can be parsed in 3 ways a bbaab Λ a bbaab Dr. Hussien M. Sharaf abba a b abb a ab abb a ab abba a b 5

RE-11 Example ∑ ={a, b} - Formally describe all words with at least two a's. 1) L = b*ab*a(a + b)*  Start with a jungle of b's (or no b's) until we find the first a, then more b's (or no b's), then the second a, then we finish up with anything. - Give examples for words in L {abbbabb aaaaa bbbabbbbabab…..}  Dr. Hussien M. Sharaf 6

RE-12 Example ∑ ={a, b} - Formally describe all words with exactly two a's. 1) L = b*ab*ab* - Give examples for words in L {aab, baba, and bbbabbbab …..}  To make the word aab, we let the first and second b* become Λ and the last becomes b  Dr. Hussien M. Sharaf 7

RE-13.1 Example ∑ ={a, b} - Formally describe all words with at least one a and at least one b. 1) L = (a + b)*a(a + b)* b(a + b)*  = (anything) a(anything) b(anything) But (a+b)*a(a+b)*b(a+b)* expresses all words except words of the form some b’s (at least one) followed by some a’s (at least one). bb*aa* Dr. Hussien M. Sharaf 8

RE-13.1 2) L =(a+b)*a(a+b)*b(a+b)* + bb*aa* Thus: (a+b)*a(a+b)*b(a+b)* + (a+b)*b(a+b)*a(a+b)* = (a+b)*a(a+b)*b(a+b)* + bb*aa*  Notice that it is necessary to write bb*aa* because b*a* will admit words we do not want, such as aaa. Does this imply that (a+b)*b(a+b)*a(a+b)*= bb*aa*?? False Left side includes the word aba, which the expression on the right side does not. Dr. Hussien M. Sharaf 9

ASSIGNMENTS 1. 2. 3. [One week] Solve Compilers-Sheet_0General.pdf [One week] Solve Compilers_Sheet_1_RE.pdf [Two weeks] Implement an email validator using Python. a. b. c. Build a GUI using python Tkinter. The GUI must include at least two labels, a TextBox and a Button. The user is given a message on a label stating whether the email is a valid email or not. Dr. Hussien M. Sharaf 10

DEADLINE Thursday 28th of Feb is the deadline.  No excuses.  Don’t wait until last day.  TAs can help you to the highest limit within the next 3 days.  Dr. Hussien M. Sharaf 11

THANKS Dr. Hussien M. Sharaf 12