Return to Video

04-45 Prisoner Example

  • 0:00 - 0:04
    このような汎用構文解析プログラムの利点は
  • 0:04 - 0:10
    どの文脈自由文法でもトークン列が
    言語に含まれるかを調べられることです
  • 0:10 - 0:14
    例としてPrisonerのあとに
    数字のリストが続く文字列を
  • 0:14 - 0:16
    受理する文法を書きました
  • 0:16 - 0:20
    Nが数字のリストで最低1つですが
  • 0:20 - 0:24
    再帰的規則なのでいくらでも増やせます
  • 0:24 - 0:29
    数字は0~6までしか書いていませんが
    7~10を加えることも可能です
  • 0:29 - 0:32
    お気に入りは囚人番号6です
  • 0:32 - 0:38
    Prisoner、6の文字列が
    文法に受理されるか見てみましょう
  • 0:38 - 0:42
    各数字に対して状態があるので
    表が大きくなりました
  • 0:42 - 0:47
    こういう時はコンピュータが計算してくれて
    ありがたいです
  • 0:47 - 0:49
    無事に受理されました
  • 0:49 - 0:53
    Prisonerという単語だけでは受理されないはずです
  • 0:53 - 0:57
    文法は1つ以上の数字を要求するからです
  • 0:57 - 1:00
    予想どおり受理されませんでした
  • 1:00 - 1:02
    別の例をお見せします
  • 1:02 - 1:05
    他の囚人を呼び出しましょう
  • 1:05 - 1:07
    囚人番号24601!
  • 1:07 - 1:10
    仮釈放になるのかもしれません
  • 1:10 - 1:14
    この文字列は文法の言語に含まれるでしょうか?
  • 1:14 - 1:18
    Prisoner 24601は見つかりました
  • 1:18 - 1:22
    ヴィクトル・ユーゴー作
    「レ・ミゼラブル」に出てくる囚人
  • 1:22 - 1:26
    ジャン・バルジャンは文法の言語に含まれました
  • 1:26 - 1:28
    この文字列を受理するのに
  • 1:28 - 1:35
    5、4、3、2、1、0と大きな表が作られました
  • 1:35 - 1:39
    最後にこのプログラムの
    汎用度の高さをお見せします
  • 1:39 - 1:41
    以前紹介したBの文法です
  • 1:41 - 1:45
    これがうまくいくことは確認済みです
  • 1:45 - 1:50
    入力した文字列a、b、b、cは
    文法の言語に含まれます
  • 1:50 - 1:53
    bを1つでも抜かせば含まれないはずです
  • 1:53 - 1:56
    このとおり含まれません
  • 1:56 - 2:00
    ここで重要なのは
    あなたが作った構文解析プログラムは
  • 2:00 - 2:04
    JavaScriptや
    HTMLの形式文法を与えられて
  • 2:04 - 2:11
    文字列やWebページがそれらの言語に含まれるかを
    十分に判定できるということです
Title:
04-45 Prisoner Example
Description:

dummy description

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

Japanese subtitles

Revisions