Return to Video

04-46 Parse Trees

  • 0:00 - 0:06
    文字列の有効性を判定する手法は習得しましたが
    まだ足りないものがあります
  • 0:06 - 0:09
    上下逆さの解析木を覚えていますか?
  • 0:09 - 0:15
    HTMLやJavaScriptのプログラムを
    正しく解釈するためには
  • 0:15 - 0:19
    この解析木も必要になります
  • 0:19 - 0:23
    基本的な算術演算の文法を書きました
  • 0:23 - 0:28
    expはnumberやexp plus exp
    exp minus exp、not exp
  • 0:28 - 0:30
    -3のような形になります
  • 0:30 - 0:32
    解析木を作っていきます
  • 0:32 - 0:39
    +、-などの記号を使うこともできますが
    今回はplus、minus、notと表記しましょう
  • 0:39 - 0:43
    抽象構文木に使うデータ構造は
  • 0:43 - 0:47
    入れ子のタプルかPythonの入れ子のリストです
  • 0:47 - 0:51
    この規則を使ってexpをnumberに書き換えます
  • 0:51 - 0:56
    入力が5なら返すタプルは(“number”,5)です
  • 0:56 - 1:00
    同様に入力がnot 5であれば
  • 1:00 - 1:05
    (“not”,(“number”,5))を返します
  • 1:05 - 1:07
    入れ子に注意してください
  • 1:07 - 1:11
    numberが1なら“number”を文字列として
  • 1:11 - 1:16
    それが何であるか示し
    トークンの中身を入れて返します
  • 1:16 - 1:20
    notを含む規則のexpが2の場合
  • 1:20 - 1:25
    “not”のあとは2になります
  • 1:25 - 1:27
    ここが3なら…
  • 1:27 - 1:32
    binopとは二項演算子を意味する
    binary operatorの略で
  • 1:32 - 1:38
    四則演算で2つの引数の一方を左に
    他方を右に取る操作のことです
  • 1:38 - 1:42
    スペースを節約するためにまとめてbinopとします
  • 1:42 - 1:49
    3つ目のexpが何であれ“plus”のあとに
    部分木として入れタプルの一部としてください
  • 1:49 - 1:55
    以前Pythonで正規表現を使って
    トークンの規則を符号化した際
  • 1:55 - 2:01
    トークンを指定したあとで
    クォーテーションを取り除く処理などを行いました
  • 2:01 - 2:07
    同様に文法規則もPythonで表すことができます
  • 2:07 - 2:10
    まずは名前づけについて説明します
  • 2:10 - 2:16
    名前をつける際に便利なので
    接頭辞をつけますがこれは任意です
  • 2:16 - 2:22
    トークン化の規則を定義することを
    示すためにt_を使い
  • 2:22 - 2:27
    解析規則の定義にはp_を使います
  • 2:27 - 2:32
    分かりやすいように規則の左側が何かを書きます
  • 2:32 - 2:36
    これはexpがnumberの時にexpを解析する規則です
  • 2:36 - 2:42
    トークン化の規則が
    実はtを取る関数であったように
  • 2:42 - 2:46
    解析規則はpを取る関数です
  • 2:46 - 2:52
    (p)は解析木あるいは
    もっと正確に言うと解析木の集まりです
  • 2:52 - 2:57
    この規則はexp->numberに似ています
  • 2:57 - 3:02
    矢印を書く方法がないので
    慣例でコロンを代用しますが
  • 3:02 - 3:08
    expがNUMBERに
    書き換えられるという意味になります
  • 3:08 - 3:10
    クォーテーションを忘れないでください
  • 3:10 - 3:16
    次にPythonまたは構文解析の辞書に
    抽象構文木の作り方を教えます
  • 3:16 - 3:20
    p[0]は返す解析木です
  • 3:20 - 3:24
    数字は文法規則の要素を表し
  • 3:24 - 3:28
    コロン以外の要素すべてに割り振られます
  • 3:28 - 3:32
    expは0でNUMBERは1です
  • 3:32 - 3:37
    ここでexpとして扱いたい解析木は
  • 3:37 - 3:43
    “number”と実際のトークンの
    中身が入ったタプルです
  • 3:43 - 3:47
    もう1つの例を見れば理解が深まるでしょう
  • 3:47 - 3:51
    先ほど説明したとおり
    解析規則の定義にはp_をつけます
  • 3:51 - 3:54
    expの解析方法が続きます
  • 3:54 - 3:59
    expを解析する方法はいくつもあり
    number、not expも使えるので
  • 3:59 - 4:02
    アンダーバーのあとに特定します
  • 4:02 - 4:05
    続いて文法規則です
  • 4:05 - 4:07
    まるで英語のようです
  • 4:07 - 4:10
    コロンは矢印の代わりでしたね
  • 4:10 - 4:15
    その下に抽象構文木の作り方を書きました
  • 4:15 - 4:21
    expは0番でnotが1番
    そして最後のexpが2番となるので
  • 4:21 - 4:23
    0番の解析木を作ります
  • 4:23 - 4:30
    初めに“not”を入れて何の木かを示し
    次に2番の解析木を入れます
  • 4:30 - 4:34
    not 5という入力があったとしたら
  • 4:34 - 4:38
    これら2つの規則を正しい順序で適用します
  • 4:38 - 4:42
    上から順に適用していくと
    このような木が得られます
  • 4:42 - 4:45
    (“not”,(“number”,5))です
  • 4:45 - 4:47
    入れ子に注意しましょう
  • 4:47 - 4:49
    図でも表せます
  • 4:49 - 4:53
    タプルはこの図を
    Pythonのコードに符号化したものです
Title:
04-46 Parse Trees
Description:

dummy description

more » « less
Video Language:
English
Team:
Udacity
Project:
CS262 - Programming Languages
Duration:
04:54

Japanese subtitles

Revisions