## 03-16 More Digits

• 0:00 - 0:07
In the past few units we've used regular expressions to classify or layout sets of strings.
• 0:07 - 0:15
It turns out that grammars can encode all of these regular languages or regular expressions
• 0:15 - 0:17
that we've been working with previously.
• 0:17 - 0:20
Here I've written a grammar for number that's going to recognize
• 0:20 - 0:25
exactly the same language, exactly the same set of strings as the regular expression above.
• 0:25 - 0:30
We can rewrite number to be a digit followed by more digits.
• 0:30 - 0:35
This construction is meant to mimic or get the same idea as this plus.
• 0:35 - 0:37
We need at least one, but we could have some more.
• 0:37 - 0:40
Down here I've just listed out all of the digits longhand.
• 0:40 - 0:44
Well, I haven't on this particular page but you could imagine I could write out
• 0:44 - 0:48
2 through 8 as optional alternate re-write rules in our grammar.
• 0:48 - 0:51
More digits is where a lot of the action happens.
• 0:51 - 0:56
One possibility is that we have one digit followed by potentially even more,
• 0:56 - 0:59
and another is that we give up.
• 0:59 - 1:04
I could write epsilon. This means more_digits goes to nothing.
• 1:04 - 1:07
For example, down here at the bottom, I have a derivation
• 1:07 - 1:11
starting with number getting to the number 42.
• 1:11 - 1:16
Number goes to digit more-digits, using our first rule--rule number one.
• 1:16 - 1:22
Then we're going to turn more digits into digit more_digit, using rule number 2.
• 1:22 - 1:27
Then--oh my gosh, classic professor mistake--you cannot take me anywhere.
• 1:27 - 1:30
Shwoop--oh look. It wraps. That that amazing.
• 1:30 - 1:36
The from digit digit more_digits, we're going to turn more_digits into the empty string,
• 1:36 - 1:40
using rule three. Now we're left with digit digit nothing.
• 1:40 - 1:44
I'm going to turn that second digit into a 2--this empty string isn't really there.
• 1:44 -
Then I'll turn that first digit into a four. Huzzah.
Title:
03-16 More Digits
Description:

dummy description

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