Scheme - 超言語的抽象(Schemeの変形 - 非決定性計算(非決定性プログラムの例(自然言語の構文解析(評価の順序))))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著) ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著) Julie Sussman (原著)
Gerald Jay Sussman (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の4(超言語的抽象)、4.3(Schemeの変形 - 非決定性計算)、4.3.3(非決定性プログラムの例)、自然言語の構文解析、問題 4.46.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 4.46.

構文解析のparse-wordは、文を左から右に解析していくので、被演算子を異なる順で評価すると、うまく動作しなくなる。

例。

(define nouns '(noun cat))

(define verbs '(verb eats))

(define articles '(article the))

(define (parse-sentence)
  (list 'sentence)
  (parse-noun-phrase)
  (parse-word verbs))

(define (parse-noun-phrase)
  (list 'noun-phrase
        (parse-word articles)
        (parse-word nouns)))

(define (parse-word word-list)
  (require (not (null? *unparsed*)))
  (require (memq (car *unparsed*) (cdr word-list)))
  (let ((found-word (car *unparsed*)))
    (set! *unparsed* (cdr *unparsed*))
    (list (car word-list) found-word)))

(define *unparsed* '())

(define (parse input)
  (set! *unparsed* input)
  (let ((sent (parse-sentence)))
    (require (null? *unparsed*))
    sent))

(parse '(the cat etas))

'*unparsed*: '(the cat eats)
sent: (list 'sentence
            (parse-noun-phrase)
            (parse-word verbs))

;; 右の(parse-word verbs)から評価する
(parse-word '(verb eats))

(require (not (null? *unparsed*:)))
;; 成功
(require (memq (car *unparsed*) (cdr word-list)))
(require (memq 'the '(eats))) #f
;; 失敗
;; 結果は無し

;; 左から右に評価する場合。
(parse-noun-phrase)

(list 'noun-phrase
      (parse-word articles)
      (parse-word nouns))

(parse-word articles)

(parse-word '(article the))

(require (not (null? '(article the))))
;; 成功

(require (memq (car *unparsed*) (cdr '(article the))))
(require (memq 'the) '(the))
;; 成功

;; found-word: 'the

(set! *unparsed* (cdr *unparsed*))
;; *unparsed*: '(cat eats)

(list 'article 'the)

;; (parse-word nouns)の評価
(parse-word '(noun cat))

(require (not (null? '(noun cat))))
;; 成功

(require (memq 'cat '(ct)))
;; 成功

;; found-word: 'cat
(set! *unparsed* (cdr *unparsed*))
;; *unparsed*: '(eats)

(list 'noun 'cat)

(list 'noun-phrase
      '(article the)
      '(noun cat))

(parse-word verbs)

(parse-word '(verb eats))

(require (not (null? '(verb eats))))
;; 成功

(require (memq 'eats '(eats)))
;; 成功

;; found-word: 'eats

(set! *unparsed* (cdr *unparsed*))
;; *unparsed* '()

(list 'verb 'eats)

;; よって、(parse-sentence)を評価すると
(list 'sentence
      (list 'noun-phrase
            '(article the)
            '(noun cat))
      (list 'verb eats))

'(sentence
  (noun-phrase (article the) (noun cat))
  (verb eats))