Return to Video

General Concepts Solution - Programming Languages

  • 0:00 - 0:04
    Hello, I am Peter Chapman, your assistant instructor for
  • 0:04 - 0:08
    this course on programming languages, "Building a Web Browser."
  • 0:08 - 0:11
    You may have seen me on the forums and kind of managing
  • 0:11 - 0:14
    the course in general, but one of the major things I do,
  • 0:14 - 0:18
    helping you learn this material, is going over the homework answers.
  • 0:18 - 0:22
    With that said, let's get started with the first problem on the first homework assignment,
  • 0:22 - 0:28
    and that is a multiple choice question on general concepts covered in the first lecture.
  • 0:28 - 0:33
    Statement 1 says, "Web pages can control their behavior and appearance
  • 0:33 - 0:35
    through embedded JavaScript."
  • 0:35 - 0:38
    This is definitely true.
  • 0:38 - 0:42
    Almost any web page that you use on a daily basis
  • 0:42 - 0:46
    has tons of JavaScript that make things nice and interactive and speedy.
  • 0:46 - 0:49
    If you were to visit, say, our web site without JavaScript enabled,
  • 0:49 - 0:51
    there would be almost nothing you can do.
  • 0:51 - 0:54
    Nothing would load. Nothing would be interactive.
  • 0:54 - 0:58
    And it's really not an overstatement that JavaScript is the basis
  • 0:58 - 1:00
    for modern web applications.
  • 1:00 - 1:04
    Statement 2, "While English sentences can be broken up into words,
  • 1:04 - 1:06
    HTML and JavaScript cannot."
  • 1:06 - 1:08
    This statement is false.
  • 1:08 - 1:12
    Let's look at a piece of HTML to show you why.
  • 1:12 - 1:17
    Here we can break up this sample bit of HTML into smaller pieces,
  • 1:17 - 1:20
    namely the beginning of the bold tag,
  • 1:20 - 1:24
    the actual text that says "Irvin," and the ending of the bold tag.
  • 1:24 - 1:27
    Individually, each of these things has meaning
  • 1:27 - 1:34
    in the same way that the sentence above, the word and,
  • 1:34 - 1:40
    allows HTML and JavaScript to together be applied to the cannot.
  • 1:40 - 1:42
    Some of these words have semantic meaning.
  • 1:42 - 1:44
    Others are more syntactic structure.
  • 1:44 - 1:50
    But nonetheless, they're words, just in a different language.
  • 1:50 - 1:54
    Statement 3, "For every Python program that calls re.findall(), there is another
  • 1:54 - 1:59
    Python program that does not call re.findall() but still obtains the same results."
  • 1:59 - 2:01
    As it turns out, this statement is true.
  • 2:01 - 2:06
    Before I deal with re.findall(), let's think of an alternative example and build up to that.
  • 2:06 - 2:10
    Let's say instead of wanting to do find all, we just want to find one.
  • 2:10 - 2:14
    That is, given a regular expression and an input text,
  • 2:14 - 2:17
    we want to determine whether or not the text matches
  • 2:17 - 2:20
    exactly the regular expression, and we can do this
  • 2:20 - 2:23
    using the tools that we developed in lecture, particularly
  • 2:23 - 2:25
    the procedure fsmsim.
  • 2:25 - 2:29
    What we have to do is create a finite state machine representation
  • 2:29 - 2:33
    for this regular expression, and that's pretty straightforward.
  • 2:33 - 2:37
    We process the input text on this state machine using fsmsim,
  • 2:37 - 2:40
    so you'd have to represent the state machine using the map
  • 2:40 - 2:44
    that we described in lecture, and if the input text ends on an accepting state,
  • 2:44 - 2:48
    then we can say we've found one match,
  • 2:48 - 2:53
    so that's how we use fsmsim to find matches for the regular expression.
  • 2:53 - 2:55
    But find all does something a little different.
  • 2:55 - 2:57
    Let's say you had this code.
  • 2:57 - 3:00
    This statement takes in a regular expression, the map numbers,
  • 3:00 - 3:04
    and an input string that contains 2 numbers, 12 and 34.
  • 3:04 - 3:07
    What find all is going to return looks like this.
  • 3:07 - 3:10
    It's going to return 2 strings, 12 and 34,
  • 3:10 - 3:13
    so we can use fsmsim to do kind of one matching.
  • 3:13 - 3:16
    If we were just given the string 12, then we could do that,
  • 3:16 - 3:20
    but we want to do a little different style of interpretation with find all,
  • 3:20 - 3:23
    and we can still use fsmsim just with a little more effort.
  • 3:23 - 3:27
    So let's say we have our black box fsmsim.
  • 3:27 - 3:31
    And it has a representation for that regular expression.
  • 3:31 - 3:34
    We also have our string that consists of 5 characters.
  • 3:34 - 3:38
    What we're going to do is we're going to feed in the first character
  • 3:38 - 3:41
    into our regular expression simulator.
  • 3:41 - 3:44
    One matches the regular expression,
  • 3:44 - 3:48
    so so far we have a match for 1.
  • 3:48 - 3:52
    In order to match larger strings, we're going to try adding one more character,
  • 3:52 - 3:55
    and we're going to feed in 12 to our regular expression simulator.
  • 3:55 - 3:58
    12 matches, so far, so good.
  • 3:58 - 4:00
    Now we're going to try 12+.
  • 4:00 - 4:06
    12+ doesn't match, so we've realized that 12 is the largest possible
  • 4:06 - 4:10
    prefix that will match this regular expression, and it's going to be one of the results.
  • 4:10 - 4:14
    We're going to go back, and we're just going to try +.
  • 4:14 - 4:16
    + doesn't work.
  • 4:16 - 4:18
    We're going to try +3. That doesn't work either.
  • 4:18 - 4:22
    That's not a number, and +34, which also doesn't work.
  • 4:22 - 4:25
    We're going to give up on the +, and we're going to do the 3.
  • 4:25 - 4:28
    3 matches. Now we can try the 4.
  • 4:28 - 4:32
    34 matches, and since that's all the characters left in this string, we're done.
  • 4:32 - 4:36
    And that's kind of how we can use fsmsim to simulate
  • 4:36 - 4:38
    the same exact functionality of find all.
  • 4:38 - 4:42
    Statement 4, "Every regular expression that involves neither
  • 4:42 - 4:47
    + nor * matches a finite set of strings."
  • 4:47 - 4:49
    This is true.
  • 4:49 - 4:51
    In the regular expressions that we define in class,
  • 4:51 - 4:56
    the only repetition is through + and *.
  • 4:56 - 4:59
    We can do some fancy things still such as or
  • 4:59 - 5:03
    or optional characters, but that doesn't even get us near
  • 5:03 - 5:08
    the possibilities that these repeating operators can give us.
  • 5:08 - 5:10
    I can enumerate a lot of different types in my regular expression,
  • 5:10 - 5:14
    a lot of different strings, but it's never going to be infinite.
  • 5:14 - 5:17
    And so if you don't have the + or the *,
  • 5:17 - 5:19
    you're stuck with a finite set of strings.
  • 5:19 - 5:23
    It may be a very large finite set, but it's still finite.
Title:
General Concepts Solution - Programming Languages
Description:

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
05:24

English subtitles

Revisions Compare revisions