Return to Video

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
Amara Bot added a translation

English subtitles

Revisions