Portuguese, Brazilian subtitles

← 04xps-03 Making Ambiguity Solution

04xps-03 Introduzindo Ambiguidade - Solução

Get Embed Code
3 Languages

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

  1. Temos aqui uma gramática que representa uma linguagem,
  2. um tipo de mistura, digamos, de Python e JavaScript.
  3. Ea tem muitas palavras-chave que são encontradas em diversas linguagens.
  4. Suponha que adicionamos uma nova regra.
  5. A questão que temos que responder é se, adicionando esta nova regra a esta gramática,
  6. a torna ambígua.
  7. Para nos lembrar: uma gramática é ambígua se existe um string na sua linguagem
  8. para o qual existem 2 árvores de derivação -- duas maneiras de percorrer a gramática -- que produzem este string.
  9. Como veremos mais tarde, isso é muito ruim quando queremos interpretar a linguagem,
  10. porque pode reultar em uma situação em que um string -- um programa,
  11. ou um documento HTML -- tem dois significados válidos,
  12. e portanto podemos escolher qualquer um deles,
  13. o que não é o que gostaríamos.
  14. Usamos linguagens precisas, como HTML e JavaScript,
  15. de modo que então sabemos exatamente o que queremos exibir,
  16. ou exatamante que ações queremos executar -- não queremos ambiguidade.
  17. Computadores não lidam muito bem com ambiguidade -- seus pequenos cérebros explodem.
  18. Podemos sentar aqui e pensar um pouco sobre isso,
  19. mas eu já vou mostrar um exemplo de um string que nos mostra que adicionar esta regra
  20. torna a gramática ambígua.
  21. Basta então verificar. Vamos fazer isso.
  22. Aqui está o string, e o que precisamos fazer é mostrar que existem 2 maneiras
  23. de gerar este string, usando esta gramática.
  24. Uma maneira é usar a construção if-the-else,
  25. onde este if, este then e este else casam aui, aqui e aqui.
  26. Isso significa que esta parte do string corresponde a este C,
  27. esta vai aqui, e esta vem deste E aqui à direita. Esta é uma maneira.
  28. A segunda maneira é usar if-then, fazer estes 2 símbolos,
  29. e então usar if-then-else,
  30. significando que isto corresponde a este S,
  31. isto corresponde a este E,
  32. e então temos um if-then-else como este S.
  33. Então temos 2 maneiras válidas de usar esta gramática para gerar o mesmo string.
  34. Isso mostra que a gramática se torna ambígua, quando adicionamos esta regra.
  35. Vamos ver outro caso.
  36. Suponha que adicionamos esta regra.
  37. B -> B B.
  38. Isso também é ambíguo.
  39. Digamos que temos print 4; print 4
  40. Temos 2 maneiras de gerar isso.
  41. Uma é começar com um B,
  42. daí vamos para S B,
  43. daqui vamos para print 4.
  44. Podemos substituir este B -- oh, eu me esqueci de adicionar isto.
  45. Podemos substituir este S com print 4.
  46. Uma maneira alternativa é basicamente similar,
  47. onde começamos com B e vamos para B B,
  48. mas agora substituímos cada B por S.
  49. Esta é nossa segunda maneira.
  50. Temos aqui mais 2 regras.
  51. Nenhuma dessas regras torna a gramática ambígua.
  52. Quando adicionamos a palavra-chave int, esta é a única maneira de obter um int.
  53. Portanto isto não será uma segunda maneria de gerar strings com int.
  54. O mesmo tipo de raciocínio se aplica aos parênteses.
  55. Esta é a única maneira de termos par6enteses,
  56. e não há uma segunda maneira aqui.
  57. Tudo o que isso faz é adicionar parênteses por fora de um comando.
  58. E podemos fazer isso quantas vezes quisermos --
  59. mas dado um número x de parênteses, aplicamos esta regra x vezes.
  60. Não tem nada muito intressante aqui.
  61. O fato de que eles casam é um ponto chave para isso.
  62. Se você tivesse parênteses em um lado e adiciona outra regra com parênteses do outro lado,
  63. então você pode talvez ter alguma ambiguidade, dependendo de como você expressa isto.
  64. Mas é assim que é. Vamos para esta última.
  65. Isso deve parecer familiar:
  66. acredito que vimos isto em aula, ou algo bastante similar a isto.
  67. e isto é definitivamente ambíguo.
  68. Vou mostrar um exemplo.
  69. Suponha que temos 1 + 2 + 3. Podemos gerar isto de 2 maneiras.
  70. Temos E -> E + E, E -> 1, e isto eventualmente vai para 2 + 3.
  71. Uma maneira alternativa é termos 2 do lado esquerdo, e então temos o 3.
  72. Embora o siginificado de + -- a associatividade de + --
  73. nos permita fazer isso em qualquer ordem, da perspectica de strings de uma linguagem,
  74. perspectiva de determiar se a gramática livre de contexto ;e ou não ambígua,
  75. o significado de + é irrelevante.