問題4.46、問題4.47 – SICP（計算機プログラムの構造と解釈）その219

2009年07月15日
blog
sicp

問題4.46

set! で *unparsed* の先頭から解析をして語句を抜き取ってゆき解析結果を作るようになっているため、構文解析プログラムは amb の評価順序に依存している。

問題4.47

(parse-word verbs) に失敗すると (parse-verb-phrase) が無限ループに陥るために、構文解析に成功する間は動作するが、解析パターンが出尽くした後は "There are no more values of" のメッセージを出して終了することができず、プロンプトが返ってこなくなる。
一方、元の parse-verb-phrase 手続きでは、(parse-word verbs) に失敗した場合は maybe-extend は評価されずバックトラックする。

Louis Reasoner の提案する parse-verb-phrase 手続き

(define (parse-verb-phrase)
  (amb (parse-word verbs)
       (list 'verb-phrase
             (parse-verb-phrase)
             (parse-prepositional-phrase))))

元の parse-verb-phrase 手続き

(define (parse-verb-phrase)
  (define (maybe-extend verb-phrase)
    (amb verb-phrase
         (maybe-extend (list 'verb-phrase
                             verb-phrase
                             (parse-prepositional-phrase)))))
  (maybe-extend (parse-word verbs)))
計算機プログラムの構造と解釈
計算機プログラムの構造と解釈

posted with amazlet at 08.11.07
ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542
Amazon.co.jp で詳細を見る
«
»