Japanese subtitles

← 05xps-01 Parsing States Solution

Get Embed Code
3 Languages

Showing Revision 1 created 10/23/2014 by Udacity.

  1. 宿題2の答えのコーナーへようこそ
  2. 最初の問題は
    トークンを与えられた文法で構文解析する時
  3. 構文解析の状態の表はどのようになるのか
    推論するものでした
  4. ここにJavaScriptの
    関数呼び出しの文法を書きました
  5. 関数powがあるとしましょう
    数のべき乗を求めるものです
  6. 内容はどうでもよいです
  7. この関数で5の6乗を求めることができますが
  8. 今はトークンだけに着目します
  9. この文字列が文法の言語に含まれるかを
    見ていきます
  10. ここに最初の規則を書きました
  11. Sがid、括弧、省略可能な引数になります
  12. この場合idはpowで これら2つの括弧が対応します
  13. この例では 引数は5と6です
  14. ここは省略可能ですので何もなくていいです
  15. 直接 空文字列に書き換えてもいいですが
    今回は引数があります
  16. 今回はexpにコンマが続き
  17. さらに引数が続くようなものとなります
  18. この場合 引数が2つあるので
    optargはargに書き換えられます
  19. 次も空ではないので この規則で書き換えます
  20. そうしてARGSからこの規則を用い
  21. expは5となります
  22. コンマはこのコンマと一致し
  23. 残りのARGSは
  24. これが最後の引数なので
    ただのexpに書き換えられ 6となります
  25. これで この文字列が文法から生成されることを
  26. 書き換え規則から示すことができました
  27. 今 JavaScriptの関数呼び出しが
    この文法に一致することを例で示しましたが
  28. 実は これは質問ではありません
  29. 質問は表についてです
  30. 今から あるトークン列を構文解析する時に
    何が起こるのかを調べます
  31. 実際に文字列を書くのではなく
    トークンについて調べるのです
  32. 構文解析のためには それさえわかればよいのです
  33. これは以前書いたpow(5,6)と一致しますが
  34. トークンについてのみ見ればいいです
  35. さて これを構文解析する時
    chart[2]には何が入っているか
  36. 表の3番目には何が入っているかを調べます
  37. 表に入っているものの候補として
    構文解析の状態が与えられています
  38. ざっと書きますね これが選択肢です
  39. 繰り返しになりますが
    この文法でこのトークン列を構文解析する時
  40. chart[2]に何が入っているのかを探します
  41. 質問ですから
    クエスチョンマークをつけておきましょう
  42. これを解く方法は2通りあります
  43. 1つは表を手で埋めていく方法です
  44. 何が起きているのか説明しやすいので
    今回はこの方法で行います
  45. 別の方法として
    講義で書いたコードを少し書き換えて使い
  46. 表の状態を出力するようにしてもいいです
  47. 何度もこの質問を聞かれるならば
    そうした方がいいでしょう
  48. しかし ここは答えの解説をする場なので
    今回は手でやります
  49. これが入力で これが文法です
  50. chart[0]に何が入るかを考えます
  51. まだ何も読んでいないので
  52. 最初の書き換え規則の一番始めに行きます
  53. これをchart[0]に加えます
  54. chart[1]に行き 1つのトークンidを読みました
  55. 規則の最初のトークンがidなので
    この状態からシフトをします
  56. ここも0から読み始めます
  57. さあ決定的瞬間 chart[2]です
  58. 何ができるか見てみましょう
  59. トークンを読むと左括弧です そこでシフトします
  60. すると2つの場合が考えられます
  61. まずOPTARGSが空の場合です
  62. まだ先のトークンを読み込んでいないので
    どうなるかわかりません
  63. この場合 OPTARGSを通りすぎることができます
  64. OPTARGSが空でない場合もありえます
  65. この入力だとそうなるでしょう
  66. 両方とも書き込んでみます
  67. この規則からOPTARGSが空になって
  68. OPTARGSを過ぎたものがこれです
  69. 他の場合としてOPTARGSが空でない場合があり
  70. これを処理していきます
  71. 文法規則どおり OPTARGSが
    空に書き換えられる場合があります
  72. これも加えなくてはなりません
  73. これはすでにchart[2]に書いてあります
  74. 別の場合 OPTARGSが
    空でないものに書き換えられるので
  75. 今度はARGSを見ていかなければなりません
  76. ARGSの規則を両方書き出しました
  77. 次のトークンをまだ読んでいないので
  78. どちらの状態についても先に読み進められず
  79. 規則の先頭にいます
  80. おそらく次の表の状態は
    新しいexpをシフトすることでしょう
  81. これで設問の答えに必要なものがそろいました
  82. これを見てchart[2]にあるものを調べられます