Subtitles translated from English Showing Revision 2 created 01/31/2013 by Lucilia Figueiredo.

1. Title:
   05xps-01 Parsing States Solution
2. Description:

   05xps-01 Estados do Parser - Solução

3. 0 0:00 - 0:02
   Bem vindo à solução do exercício 2.
4. 2000 0:02 - 0:06
   Nesta primeira questão, vamos ver como raciocinar sobre o estado da tabela,
5. 6000 0:06 - 0:09
   quando fazemos o parsing de um token, em uma dada gramática.
6. 9000 0:09 - 0:13
   Aqui, temos uma gramática que define chamadas de função em JavaScript.
7. 13000 0:13 - 0:18
   Digamos que eu tenha uma função -- pow -- que computa a potência de um número,
8. 18000 0:18 - 0:20
   elevado a outro número -- isso não importa de fato.
9. 20000 0:20 - 0:23
   A idéia é que esta função computa 5 elevado a 6,
10. 23000 0:23 - 0:27
    mas o que importa são os tokens aqui.
11. 27000 0:27 - 0:30
    E para mostrar que este string está nesta gramática, vamos caminhar sobre ele.
12. 30000 0:30 - 0:35
    Escrevi aqui nossa primeira regra inicial: S -> id (
13. 35000 0:35 - 0:37
    OPTARGS ).
14. 37000 0:37 - 0:41
    id, neste caso, é pow, e então temos 2 parênteses,
15. 41000 0:41 - 0:45
    e os argumentos, no caso do nosso exemplo, são 5 e 6.
16. 45000 0:45 - 0:48
    Não precisamos ter nada aqui -- como indica o nome, isso é opcional --
17. 48000 0:48 - 0:51
    poderia ser o string vazio; mas nós temos argumentos.
18. 51000 0:51 - 0:54
    Neste caso, temos que ter algum tipo de expressão,
19. 54000 0:54 - 0:58
    ou uma expressão seguida de vírgula, com mais argumentos.
20. 58000 0:58 - 1:02
    E, neste caso, temos 2 -- então, OPTARGS -> ARGS.
21. 62000 1:02 - 1:04
    Não é vazio, então será esta regra.
22. 64000 1:04 - 1:08
    E então, de ARGS, vamos para esta regra,
23. 68000 1:08 - 1:10
    onde exp será 5,
24. 70000 1:10 - 1:12
    temos a vírgula, que casa com a nossa vírgul,.
25. 72000 1:12 - 1:16
    e o retante da regra é ARGS, que vai para --
26. 76000 1:16 - 1:21
    como este é nosso último argumento, vai apenas para exp, que é 6.
27. 81000 1:21 - 1:25
    E pudemos então casar este string com a gramática,
28. 85000 1:25 - 1:28
    usando este conjunto de regras de reescrita.
29. 88000 1:28 - 1:33
    Então, acabei de demonstar como esta gramática casa com chamadas de funçãm em JavaScript.
30. 93000 1:33 - 1:35
    Mas não é exatamente isso que é solicitado na questão.
31. 95000 1:35 - 1:38
    A questão pergunta sobre a tabela.
32. 98000 1:38 - 1:43
    Vamos ver o que acontece quando fazemos parsing de um certo conjunto de tokens.
33. 103000 1:43 - 1:46
    Ao invés de escrever o próprio string, tenho apenas os tokens relevantes.--
34. 106000 1:46 - 1:49
    e, para o problema de parsing, é só isso que nos importa.
35. 109000 1:49 - 1:51
    Isto pode ser casado com o que tínhamos antes,
36. 111000 1:51 - 1:54
    mas o que nos importa são os tokens.
37. 114000 1:54 - 1:57
    Quando eu faço parsing disso, o que queremos saber é:
38. 117000 1:57 - 2:01
    O que está em chart[2], a terceira posição da tabela?
39. 121000 2:01 - 2:05
    E nos foi dado um conjunto de regras que podem estar na tabela.
40. 125000 2:05 - 2:08
    Eu vou examinar cada uma rapidamente. Aqui estão nossas opções.
41. 128000 2:08 - 2:12
    Estamos tentando determinar -- lembre-se -- o que está na segunda entrada da nossa tabela,
42. 132000 2:12 - 2:17
    quando fazemos parsing desta lista de tokens, nesta gramática.
43. 137000 2:17 - 2:20
    E como é uma questão, eu não devom esquecer o símbolo de interrogação.
44. 140000 2:20 - 2:22
    Existem 2 maneiras de resolver isso.
45. 142000 2:22 - 2:26
    A primeira é você construir a tabela à mão.
46. 146000 2:26 - 2:29
    Isso é o que vamos fazer, porque é mais fácil para explicar o que está acontecendo.
47. 149000 2:29 - 2:34
    Uma alternativa, igualmente válida, é usar o código que escrevemos em aula,
48. 154000 2:34 - 2:37
    e modificá-lo para imprimir cada estado da tabela.
49. 157000 2:37 - 2:41
    Isso é provavelmente o que você deveria fazer, se tivesse que responder a várias questões como essa.
50. 161000 2:41 - 2:46
    Mas, como eu disse, para efeito de explicar a resposta, vamos resolver à mão.
51. 166000 2:46 - 2:48
    Ok. Aqui está nossa entrada, e aqui está nossa gramática.
52. 168000 2:48 - 2:51
    Queremos saber o que está em chart[0].
53. 171000 2:51 - 2:54
    Não lemos nada ainda, portanto, estamos no início
54. 174000 2:54 - 2:57
    da regra de reescrita inicial.
55. 177000 2:57 - 3:02
    Incluimos isso em chart[0].
56. 182000 3:02 - 3:06
    Então, agora estamos em chart[1], e já lemos o primeiro token -- id.
57. 186000 3:06 - 3:11
    Vamos apenas fazer shift nesta regra, porque id é o primeiro token desta regra.
58. 191000 3:11 - 3:14
    E isto vem de 0.
59. 194000 3:14 - 3:18
    Então, agora é o momento da verdasde: chart[2].
60. 198000 3:18 - 3:20
    Vamos ver o que podemos fazer.
61. 200000 3:20 - 3:24
    Vamos olhar o token -- é ( -- e vamos fazer shift.
62. 204000 3:24 - 3:27
    Então, aqui existem 2 possibilidades.
63. 207000 3:27 - 3:30
    Uma é que OPTARGS seja vazio --
64. 210000 3:30 - 3:34
    ainda não sabemos, porque não vimos ainda o resto da lista de tokens da entrada.
65. 214000 3:34 - 3:37
    Neste caso, vamos passar OPTARGS.
66. 217000 3:37 - 3:40
    Existe também a possibilidade de que OPTARGS não seja vazio,
67. 220000 3:40 - 3:43
    o que é, de fato, o que acontece na nossa lista de entrada.
68. 223000 3:43 - 3:45
    Então, vamos escrever esses 2 casos.
69. 225000 3:45 - 3:48
    Aqui, eu avancei sobre OPTARGS,
70. 228000 3:48 - 3:51
    presumindo que ele seja vazio, como nesta regra aqui.
71. 231000 3:51 - 3:55
    Então, temos outra opção, onde OPTARGS não é vazio,
72. 235000 3:55 - 3:57
    e vamos ter que processá-lo.
73. 237000 3:57 - 4:03
    Então, olhando esta primeira regra, em nossa tabela temos OPTARGS vazio.--
74. 243000 4:03 - 4:05
    nós temos que garantir que isso seja adicionado:
75. 245000 4:05 - 4:07
    introduzimos isso em chart[2].
76. 247000 4:07 - 4:10
    Temos outro caso, em que OPTARGS não é vazio,
77. 250000 4:10 - 4:12
    e temos que ir para ARGS agora.
78. 252000 4:12 - 4:15
    Então, escrevi aqui as 2 regras para ARGS,
79. 255000 4:15 - 4:17
    e, como ainda não lemos o próximo token, não sabemos nada
80. 257000 4:17 - 4:19
    para poder avançar em qualquer dessas regras,
81. 259000 4:19 - 4:21
    então estamos no início de cada regra.
82. 261000 4:21 - 4:28
    Presumivelmente, o próximo estado na tabela irá fazer shift sobre a nova expressão.
83. 268000 4:28 - 4:32
    Então, agora temos tudo o que precisamos para responder à questão:
84. 272000 4:32 -
    apenas vamos marcar as opções que estão em chart[2].