Return to Video

04-45 Prisoner Example

  • 0:00 - 0:04
    Uma das grandes vantagens de um parser universal como este
  • 0:04 - 0:10
    é que eu posso dar como entrada qualquer gramática livre de contexto e verificar qualquer string de tokens em relação a ela.
  • 0:10 - 0:14
    Por exemplo, defini aqui uma nova gramática, que aceita a palavra "Prisoner",
  • 0:14 - 0:17
    seguida de uma lista de números.
  • 0:17 - 0:21
    N é uma lista de números -- pelo menos 1 número, mas podem ser mais.
  • 0:21 - 0:24
    Esta é uma regra recursiva, portanto podemos ter tantos quantos quisermos --
  • 0:24 - 0:29
    e eu sou preguiçoso: apenas coloquei 0,1,2,3,4,5,6, mas poderia ter também 7,8,9.
  • 0:29 - 0:32
    Um dos meus favoritos é "Prisoner 6".
  • 0:32 - 0:38
    Vejamos se este string -- "Prisoner 6" -- é aceito por esta gramática.
  • 0:38 - 0:42
    Aqui, a tabela é um pouco maior, porque temos um estado separado para cada um destes.
  • 0:42 - 0:45
    Ficamos felizes porque é o computador que está fazendo a memorização,
  • 0:45 - 0:47
    ao invés de termos que fazer isso à mão.
  • 0:47 - 0:49
    Mas aqui, no final, aceitamos.
  • 0:49 - 0:53
    Por outro lado, se tenho apenas "Prisoner", isso não deve funcionar,
  • 0:53 - 0:57
    porque esta lista requer 1 ou mais dígitos.
  • 0:57 - 1:00
    De fato, podemos ver aqui que não é aceito.
  • 1:00 - 1:02
    Vamos fazer mais um teste;
  • 1:02 - 1:05
    se houver mais um prisoner disputando meu coração,
  • 1:05 - 1:07
    eu pediria que você troxesse o "Prisoner 24601" --
  • 1:07 - 1:11
    talvez seja a hora de dar a ele sua condicional.
  • 1:11 - 1:13
    Vamos ver se este string é aceito pela gramática.
  • 1:13 - 1:18
    Aqui, até o final do dia, vemos que "Prisoner 24601" --
  • 1:18 - 1:22
    o famoso Jean Valjean do romance Les Miserable de Victor Hugo, uma bela peça de literatura francesa --
  • 1:22 - 1:26
    é aceito pela linguagem desta gramática.
  • 1:26 - 1:35
    Mas temos um grande número de estados na tabela -- 5,4,3,2,1,0 -- para aceitar este string.
  • 1:35 - 1:39
    Vamos fazer mais um teste, para mostrar como nosso poder é arbitrário.
  • 1:39 - 1:41
    Agora, coloquei aqui a gramática B que vimos anteriormente.
  • 1:41 - 1:45
    Sabemos como ela deve funcionar, porque vimos antes juntos, no papel.
  • 1:45 - 1:50
    O string de entrada é "abbc", e este string está na linguagem da grama'tica.
  • 1:50 - 1:53
    Se eu esquecer um dos b's, esperamos que não esteja --
  • 1:53 - 1:56
    se eu esqueço um dos b's o string não está na linguagem da gramática.
  • 1:56 - 1:59
    A chave da solução foi o que você implementou.
  • 1:59 - 2:04
    Isso é suficiente para receber como entrada uma gramática formal de JavaScript e HTML
  • 2:04 -
    e determinar se um string, um página web, um programa, está na linguagem -- isso é muito legal!
Title:
04-45 Prisoner Example
Description:

04-45 Exemplo do Prisioneiro

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

Portuguese, Brazilian subtitles

Revisions