Portuguese, Brazilian subtitles

← 05xps-01 Parsing States Solution

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

Get Embed Code
3 Languages

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

  1. Bem vindo à solução do exercício 2.
  2. Nesta primeira questão, vamos ver como raciocinar sobre o estado da tabela,
  3. quando fazemos o parsing de um token, em uma dada gramática.
  4. Aqui, temos uma gramática que define chamadas de função em JavaScript.
  5. Digamos que eu tenha uma função -- pow -- que computa a potência de um número,
  6. elevado a outro número -- isso não importa de fato.
  7. A idéia é que esta função computa 5 elevado a 6,
  8. mas o que importa são os tokens aqui.
  9. E para mostrar que este string está nesta gramática, vamos caminhar sobre ele.
  10. Escrevi aqui nossa primeira regra inicial: S -> id (
  11. OPTARGS ).
  12. id, neste caso, é pow, e então temos 2 parênteses,
  13. e os argumentos, no caso do nosso exemplo, são 5 e 6.
  14. Não precisamos ter nada aqui -- como indica o nome, isso é opcional --
  15. poderia ser o string vazio; mas nós temos argumentos.
  16. Neste caso, temos que ter algum tipo de expressão,
  17. ou uma expressão seguida de vírgula, com mais argumentos.
  18. E, neste caso, temos 2 -- então, OPTARGS -> ARGS.
  19. Não é vazio, então será esta regra.
  20. E então, de ARGS, vamos para esta regra,
  21. onde exp será 5,
  22. temos a vírgula, que casa com a nossa vírgul,.
  23. e o retante da regra é ARGS, que vai para --
  24. como este é nosso último argumento, vai apenas para exp, que é 6.
  25. E pudemos então casar este string com a gramática,
  26. usando este conjunto de regras de reescrita.
  27. Então, acabei de demonstar como esta gramática casa com chamadas de funçãm em JavaScript.
  28. Mas não é exatamente isso que é solicitado na questão.
  29. A questão pergunta sobre a tabela.
  30. Vamos ver o que acontece quando fazemos parsing de um certo conjunto de tokens.
  31. Ao invés de escrever o próprio string, tenho apenas os tokens relevantes.--
  32. e, para o problema de parsing, é só isso que nos importa.
  33. Isto pode ser casado com o que tínhamos antes,
  34. mas o que nos importa são os tokens.
  35. Quando eu faço parsing disso, o que queremos saber é:
  36. O que está em chart[2], a terceira posição da tabela?
  37. E nos foi dado um conjunto de regras que podem estar na tabela.
  38. Eu vou examinar cada uma rapidamente. Aqui estão nossas opções.
  39. Estamos tentando determinar -- lembre-se -- o que está na segunda entrada da nossa tabela,
  40. quando fazemos parsing desta lista de tokens, nesta gramática.
  41. E como é uma questão, eu não devom esquecer o símbolo de interrogação.
  42. Existem 2 maneiras de resolver isso.
  43. A primeira é você construir a tabela à mão.
  44. Isso é o que vamos fazer, porque é mais fácil para explicar o que está acontecendo.
  45. Uma alternativa, igualmente válida, é usar o código que escrevemos em aula,
  46. e modificá-lo para imprimir cada estado da tabela.
  47. Isso é provavelmente o que você deveria fazer, se tivesse que responder a várias questões como essa.
  48. Mas, como eu disse, para efeito de explicar a resposta, vamos resolver à mão.
  49. Ok. Aqui está nossa entrada, e aqui está nossa gramática.
  50. Queremos saber o que está em chart[0].
  51. Não lemos nada ainda, portanto, estamos no início
  52. da regra de reescrita inicial.
  53. Incluimos isso em chart[0].
  54. Então, agora estamos em chart[1], e já lemos o primeiro token -- id.
  55. Vamos apenas fazer shift nesta regra, porque id é o primeiro token desta regra.
  56. E isto vem de 0.
  57. Então, agora é o momento da verdasde: chart[2].
  58. Vamos ver o que podemos fazer.
  59. Vamos olhar o token -- é ( -- e vamos fazer shift.
  60. Então, aqui existem 2 possibilidades.
  61. Uma é que OPTARGS seja vazio --
  62. ainda não sabemos, porque não vimos ainda o resto da lista de tokens da entrada.
  63. Neste caso, vamos passar OPTARGS.
  64. Existe também a possibilidade de que OPTARGS não seja vazio,
  65. o que é, de fato, o que acontece na nossa lista de entrada.
  66. Então, vamos escrever esses 2 casos.
  67. Aqui, eu avancei sobre OPTARGS,
  68. presumindo que ele seja vazio, como nesta regra aqui.
  69. Então, temos outra opção, onde OPTARGS não é vazio,
  70. e vamos ter que processá-lo.
  71. Então, olhando esta primeira regra, em nossa tabela temos OPTARGS vazio.--
  72. nós temos que garantir que isso seja adicionado:
  73. introduzimos isso em chart[2].
  74. Temos outro caso, em que OPTARGS não é vazio,
  75. e temos que ir para ARGS agora.
  76. Então, escrevi aqui as 2 regras para ARGS,
  77. e, como ainda não lemos o próximo token, não sabemos nada
  78. para poder avançar em qualquer dessas regras,
  79. então estamos no início de cada regra.
  80. Presumivelmente, o próximo estado na tabela irá fazer shift sobre a nova expressão.
  81. Então, agora temos tudo o que precisamos para responder à questão:
  82. apenas vamos marcar as opções que estão em chart[2].