計算機プログラムの構造と解釈[第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))
0 コメント:
コメントを投稿