Return to Video

04-45 Prisoner Example

  • 0:00 - 0:04
    Now, one of the big draws of having a universal parser like this
  • 0:04 - 0:10
    was that I could fill in any context-free grammar and check any string of tokens against it.
  • 0:10 - 0:14
    For example, here I've defined a new grammar that accepts the word "prisoner"
  • 0:14 - 0:17
    followed by a list of numbers.
  • 0:17 - 0:21
    N is a list of numbers. It's at least 1, but you can have more.
  • 0:21 - 0:24
    This is a recursive rule so we can have as many as we want,
  • 0:24 - 0:29
    and I've gotten lazy. We only put in 0, 1, 2, 3, 4, 5, 6, but I could go all the way 7, 8, 9, 10.
  • 0:29 - 0:32
    One of my favorite prisoners is number 6.
  • 0:32 - 0:38
    Let's go see if this string, prisoner 6, is accepted by this grammar.
  • 0:38 - 0:42
    Here the chart is a bit bigger, because we have sort of a separate state for each one of these.
  • 0:42 - 0:45
    This makes us glad that the computer is doing the memorization
  • 0:45 - 0:47
    instead of us doing it by hand.
  • 0:47 - 0:49
    But down here at the end we accept.
  • 0:49 - 0:53
    By contrast if I just have the word "prisoner," this shouldn't work,
  • 0:53 - 0:57
    because this list requires 1 or more integers.
  • 0:57 - 1:00
    And in fact down here we can see that it is not accepted.
  • 1:00 - 1:02
    Let's do just one more of these.
  • 1:02 - 1:05
    If there were another prisoner vying for the affection of my heart,
  • 1:05 - 1:07
    I'd ask you to bring me prisoner 24601.
  • 1:07 - 1:11
    Perhaps his time is up and his parole has begun.You know what that means.
  • 1:11 - 1:13
    Let's check and see if the string is accepted by the language of the grammar.
  • 1:13 - 1:18
    Here, all the way down at the end of the day, we see that prisoner 24601,
  • 1:18 - 1:22
    famously Jean Valjean from Victor Hugo's Les Miserables,
  • 1:22 - 1:26
    a nice piece of French literature, is accepted by the language of this grammar.
  • 1:26 - 1:35
    But we have a large number of chart states--5, 4, 3, 2, 1, 0--to accept this string.
  • 1:35 - 1:39
    Let's do one more of these just to show off our very arbitrary power.
  • 1:39 - 1:41
    Now I've put in the B grammar from before.
  • 1:41 - 1:45
    We know how this one is supposed to work because we did it out together on paper.
  • 1:45 - 1:50
    The input string I've put in is abbc, and that string is in the language of the grammar.
  • 1:50 - 1:53
    If I forget one of the b's, we expect it not to be.
  • 1:53 - 1:56
    When I forget one of the b's it is not in the language of the grammar.
  • 1:56 - 1:59
    The real trick is basically that you have done it.
  • 1:59 - 2:04
    This is enough of a parser to be given a formal grammar for JavaScript or HTML
  • 2:04 -
    and determine if a string, a webpage, a program is in that language. This is very exciting.
Title:
04-45 Prisoner Example
Description:

dummy description

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
02:10
Amara Bot added a translation

English subtitles

Revisions