7
Aug

General Concepts Solution – Programming Languages


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

Tags: , , , , , , , ,

There are no comments yet

Why not be the first

Leave a Reply

Your email address will not be published. Required fields are marked *