## 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