問題4-45〜49

SICP

｢自然言語の構文解析｣というトピックに取り組んでいます。与えられた文章の構文を解析するようなparse-sentenceを読解します。
問題4-45。｢The professor lectures to the student in the class with the cat｣は、以下の五種類の出力が考えられます。かなり略してしまいましたが、雰囲気をつかめれば良いと思ったので、そのまま掲載してしまいます。それぞれの品詞ロジックには以下のような特性があり、それらを組み合わせた結果になります。

  • verb-phraseは、第一要素が｢別のverb-phrase｣か｢verbそのもの｣、第二要素は｢prep-phrase｣。
  • prep-phraseは、第一要素が｢simple-noun｣か｢noun-phrase｣、第二要素は｢prep-phrase｣。
  • noun-phraseは、第一要素が｢simple-noun｣で、第二要素は｢prep-phrase｣。
(sentence
 (simple-noun 'the 'professor)
 (verb-phrase
  (verb 'lecture)
  (prep-phrase (prep 'to)
               (noun-phrase
                (simple-none 'the 'student)
                (prep-phrase (prep 'in)
                             (noun-phrase
                              (simple-noun 'the 'class)
                              (prep-phrase (prep 'with)
                                           (simple-noun 'the 'cat))))))))

(sentence
 (simple-noun 'the 'professor)
 (verb-phrase
  (verb 'lecture)
  (prep-phrase (prep 'to)
               (noun-phrase
                (noun-phrase
                 (simple-noun 'the 'student)
                 (prep-phrase (prep 'in)
                              (simple-noun 'the 'class)))
                (prep-phrase (prep 'with)
                             (simple-noun 'the 'cat))))))

(sentence
 (simple-noun 'the 'professor)
 (verb-phrase
  (verb-phrase
   (verb 'lecture)
   (prep-phrase (prep 'to)
                (simple-phrase 'the 'student)))
  (prep-phrase (prep 'in)
               (noun-phrase
                (simple-noun 'the 'class)
                (prep-phrase (prep 'with)
                             (simple-noun 'the 'cat))))))

(sentence
 (simple-noun 'the 'professor)
 (verb-phrase
  (verb-phrase
   (verb 'lecture)
   (prep-phrase (prep 'to)
                (noun-phrase
                 (simple-noun 'the 'student)
                 (prep-phrase (prep 'in)
                              (simple-phrase 'the 'class)))))
  (prep-phrase (prep 'with)
               (simple-noun 'the 'cat))))

(sentence
 (simple-noun 'the 'professor)
 (verb-phrase
  (verb-phrase
   (verb-phrase
    (verb 'lecture)
    (prep-phrase (prep 'to)
                 (simple-noun 'the 'student)))
   (prep-phrase (prep 'in)
                (simple-noun 'the 'class)))
  (prep-phrase (prep 'with)
               (simple-noun 'the 'cat))))

問題4-46。ambが被演算子を左から右へ評価しないと何がまずいのか。今回の構文解析の場合、parse-verb-phraseやparse-noun-phraseでambが登場しますが、この中で(parse-prepositional-phrase)を行い、それが(verb-phrase)の構成要素としてlist化される順番が変わってしまうのではないかと思いました。例えば、右から左へと評価が進んだら、prepが登場する順番が逆になってしまうような気がします。
問題4-47。Louisの実装だと、ambで一つずつ探索が進むたびに、(parse-word verbs)が呼び出されてしまいます。parse-wordは、*unparsed*の先頭がverbsの要素の一つと一致したら、*unparsed*を先に進めてしまいますので、成功するのは最初の一回だけで、それ以降は正しくparseされない(requireが返ってこない)のではないかと思います。
問題4-48は、新しい品詞を扱えるようにせよとのことなので、飛ばしまいました。
問題4-49。ランダムな文章を生成するためのロジックを書けとのことです。おそらく、parse-wordの中のロジックを変更するだけで上手くいきます。*unparsed*を利用せず、渡されたword-listの第二引数を採用して、第三引数以降を、繰り上げていけばいいのではないでしょうか。

(define (parse-word word-list)
  (let ((found-word (cdar word-list)))
    (set-cdr! word-list (cddr word-list))
    (list (car word-list) found-word)))

このあたりについても、次のトピックのamb評価器実装を終えた時点で試してみたいと思っています。