-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path2007.txt
203 lines (146 loc) · 6.23 KB
/
2007.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
From: Takuo Watanabe <[email protected]>
Date: Wed, 25 Apr 2007 15:38:59 +0900
Subject: 4年生向けプログラミングプロジェクト
--
ちょっとおそくなりましたが，新4年生むけに毎年行って
いるプログラミングプロジェクトの案内です．
問題：Scheme（サブセット）のインタプリタを作成してください．
作成する Scheme の文法と，最低限用意する関数を以下に挙げます．
今年は比較的フルセットに近い構文になっているため，記述言語は
Schemeとします．ただし作成したインタプリタ上で作成したインタ
プリタが実行できるようにしてください．
期間は約１ヶ月とします．できあがったらデモをしてもらいます．
余裕があったら，call-with-current-continuation, バッククオート，
マクロなどを実装してみてください．
A. 文法
非終端記号:
大文字[A-Z]で始まる名前
終端記号:
開き括弧 (
閉じ括弧 )
ピリオド .
小文字[a-z]で構成される名前
シングルクオート ' で囲まれた文字列
X* 要素Xの0個以上のくりかえし
X+ 要素Xの1個以上のくりかえし
[X] 要素Xは高々1個
Toplevel ::= Exp
| Define
| (load String) ファイルの内容を読み込む
Define ::= (define Id Exp)
| (define (Id Id*) Body)
Exp ::= Const 定数
| Id 変数
| (lambda Arg Body) λ抽象
| (Exp Exp*) 関数適用
| (quote S-Exp) クオート (注1)
| (set! Id Exp) 代入
| (let [Id] Bindings Body) let
| (let* Bindings Body) let* (注2)
| (letrec Bindings Body) letrec
| (if Exp Exp Exp) 条件式(if)
| (cond (Exp Exp+)* [(else Exp+)]) 条件式(cond)
| (and Exp*) 条件式(and)
| (or Exp*) 条件式(or)
| (do ((Id Exp Exp)*) (Exp Exp*) Body) 繰り返し
Body ::= Def* Exp+
Arg ::= Id
| (Id* [Id . Id])
Bindings ::= ((Id Exp)*)
S-Exp ::= Const
| Id
| (S-Exp* [S-Exp . S-Exp])
Const ::= Num
| Bool
| String
| ()
Num: 最低限10進整数はサポートすること
Bool ::= '#t'
| '#f'
String: ダブルクオートで囲まれた文字列 (注3)
Id ::= [0-9A-Za-z!$%&*+-./<=>?@^_]+ (注4)
(注1) (quote X) だけでなく 'X という記法もサポートすること．
(注2) let* は let の0個以上の繰り返しではなく let* という名前である．
(注3) バックスラッシュ \ によるエスケープをサポートすること．
(注4) 数値となるものをのぞくこと．
B. 関数（最低限）
整数
number?, +, -, *, /, =, <, <=, >, >=
リスト
null?, pair?, list?, symbol?
car, cdr, cons, list, set-car!, set-cdr!, length, memq, last, append
ブール値
boolean?, not
文字列
string?, string-append,
symbol->string, string->symbol, string->number, number->string
関数
closure?
比較
eq?, neq?, equal?
-----
From: Takuo Watanabe <[email protected]>
Date: Wed, 25 Apr 2007 16:34:50 +0900
Subject: Re: 4年生向けプログラミングプロジェクト
--
いくつかミスがあったので訂正します．
1. 文法にいくつかミスがあったので訂正したものを本メール末尾につけます．
2. 実装すべき関数の closure? は，procedure? のまちがいです．
3. あと，作成するインタプリタの要件に以下を加えます．
・構文に合致しない入力はエラーとすること．
・実行時エラーによってインタプリタが停止してしまわないようにすること．
-- takuo
A. 文法
非終端記号:
大文字[A-Z]で始まる名前
終端記号:
開き括弧 (
閉じ括弧 )
ピリオド .
小文字[a-z]で構成される名前
シングルクオート ' で囲まれた文字列
X* 要素Xの0個以上のくりかえし
X+ 要素Xの1個以上のくりかえし
[X] 要素Xは高々1個
Toplevel ::= Exp
| Define
| (load String) ファイルの内容を読み込む
Define ::= (define Id Exp)
| (define (Id Id* [. Id]) Body)
Exp ::= Const 定数
| Id 変数
| (lambda Arg Body) λ抽象
| (Exp Exp*) 関数適用
| (quote S-Exp) クオート (注1)
| (set! Id Exp) 代入
| (let [Id] Bindings Body) let
| (let* Bindings Body) let* (注2)
| (letrec Bindings Body) letrec
| (if Exp Exp Exp) 条件式(if)
| (cond (Exp Exp+)* [(else Exp+)]) 条件式(cond) (注3)
| (and Exp*) 条件式(and)
| (or Exp*) 条件式(or)
| (do ((Id Exp Exp)*) (Exp Exp*) Body) 繰り返し
Body ::= Define* Exp+
Arg ::= Id
| (Id* [Id . Id])
Bindings ::= ((Id Exp)*)
S-Exp ::= Const
| Id
| (S-Exp* [S-Exp . S-Exp])
Const ::= Num
| Bool
| String
| ()
Num: 最低限10進整数はサポートすること
Bool ::= '#t'
| '#f'
String: ダブルクオートで囲まれた文字列 (注4)
Id ::= [0-9A-Za-z!$%&*+-./<=>?@^_]+ (注5)
(注1) (quote X) だけでなく 'X という記法もサポートすること．
(注2) let* は let の0個以上の繰り返しではなく let* という名前である．
(注3) 節は(else節を含めて)最低1個はあること．else節は高々1個とすること．
(注4) バックスラッシュ \ によるエスケープをサポートすること．
(注5) 数値となるものをのぞくこと．