Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
10ステップで作るお手軽インタプリタ開発
Search
Ushitora Anqou
October 22, 2018
Programming
3
1k
10ステップで作るお手軽インタプリタ開発
10ステップで、フィボナッチ数列が再帰により計算できる程度のインタプリタをつくります。レポジトリは以下です。
https://github.com/ushitora-anqou/simplinterp
Ushitora Anqou
October 22, 2018
Tweet
Share
More Decks by Ushitora Anqou
See All by Ushitora Anqou
Oblivious Online Monitoring for Safety LTL Specification via Fully Homomorphic Encryption
anqou
1
880
F*でプログラムの正しさを証明する
anqou
1
1.1k
「自作CPUでサイゼリヤ問題」を支える技術
anqou
2
330
ぼくのかんがえたさいきょうのマリオAI
anqou
1
560
seccamp2018でセルフホストCコンパイラをつくった
anqou
8
5.4k
Other Decks in Programming
See All in Programming
AI時代のプログラミング教育 / programming education in ai era
kishida
23
21k
Firebase Dynamic Linksの代替手段を自作する / Create your own Firebase Dynamic Links alternative
kubode
0
180
ニックトレイン登壇資料
ryotakurokawa
0
140
php-fpm がリクエスト処理する仕組みを追う / Tracing-How-php-fpm-Handles-Requests
shin1x1
5
830
フロントエンドテストの育て方
quramy
9
2.6k
NestJSのコードからOpenAPIを自動生成する際の最適解を探す
astatsuya
0
190
パスキーのすべて / 20250324 iddance Lesson.5
kuralab
0
130
新卒から4年間、20年もののWebサービスと 向き合って学んだソフトウェア考古学
oguri
8
6.8k
CTFのWebにおける⾼難易度問題について
hamayanhamayan
1
990
CRE Meetup!ユーザー信頼性を支えるエンジニアリング実践例の発表資料です
tmnb
0
360
Modern Angular:Renovation for Your Applications @angularDays 2025 Munich
manfredsteyer
PRO
0
140
本当だってば!俺もTRICK 2022に入賞してたんだってば!
jinroq
0
250
Featured
See All Featured
Git: the NoSQL Database
bkeepers
PRO
429
65k
Thoughts on Productivity
jonyablonski
69
4.5k
Making the Leap to Tech Lead
cromwellryan
133
9.2k
GraphQLとの向き合い方2022年版
quramy
45
14k
A Tale of Four Properties
chriscoyier
158
23k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
356
30k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
507
140k
Speed Design
sergeychernyshev
28
860
What’s in a name? Adding method to the madness
productmarketing
PRO
22
3.4k
How GitHub (no longer) Works
holman
314
140k
Fashionably flexible responsive web design (full day workshop)
malarkey
407
66k
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
60k
Transcript
10 εςοϓͰͭ͘Δ ͓खܰΠϯλϓϦλ։ൃ ࠡ ᲒᲶ @ushitora anqou 1
Δ͜ͱ • ؆୯ͳΠϯλϓϦλΛ C ݴޠͰॻ͘ɻ • ϑΟϘφονྻΛܭࢉͰ͖Δɻ • Strongly inspired
by https://youtu.be/JAtN0TGrNE4 2
Θ͔ͬͯ΄͍͜͠ͱ • ݴޠॲཧܥݴ͏΄Ͳ͘͠ͳ͍ɻ • ཧࡶ͕࣮ͩ͢ΕΘ͔Δɻ • ΈΜͳ C ίϯύΠϥΛͭ͘Ζ͏ʂ 3
ιʔε https://github.com/ ushitora-anqou/ simplinterp 4
5
6
7
ΠϯλϓϦλͬͯͳΜͩΖ͏ ΠϯλϓϦλʢӳ: interpreterʣͱ ɺϓϩάϥϛϯάݴޠͰॻ͔Ε ͨιʔείʔυͳ͍͠தؒදݱΛ ஞ࣍ղऍ͠ͳ͕Β࣮ߦʢӳޠ൛ʣ ͢ΔϓϩάϥϜͷ͜ͱɻ ʢWikipedia ΑΓʣ 8
ΠϯλϓϦλͬͯͳΜͩΖ͏ ͭ͘ΕΘ͔Δ 9
Step
Step 0 C ݴޠͷจࣈྻॲཧ ↓ H e l l o
\0 char *p = "Hello"; • C ݴޠʹ͓͍ͯจࣈྻʮจࣈ͕ϝϞ Ϧ্ʹฒͼɺऴ͕\0 ͷͷʯ • ϙΠϯλͰจࣈྻͷઌ಄ཁૉΛࢦ͢ɻ 10
Step 0 C ݴޠͷจࣈྻॲཧ ↓ H e l l o
\0 char *p = "Hello"; p; // address *p; // ’H’ *(p + 1); // ’e’ p[1]; // ’e’ *p++; // ’H’ *p; // ’e’ 11
Step 1 ಈ͘ίʔυΛॻ͘ #include <stdio.h> int eval(char *p) { return
0; } int main(int argc , char ** argv) { return eval(argv [1]); } eval() ͰϓϩάϥϜͷ࣮ߦΛߦ͏ɻ ./main "program" 12
Step 1 ಈ͘ίʔυΛॻ͘ ςετΛॻ͘ɻ #!/bin/sh # ʢதུʣ runtest "0" 0
runtest ͰϓϩάϥϜͷਖ਼ৗ࣮ߦΛ͔֬ ΊΔɻ 13
Step 2 ࣗવΛಡΉ ΛҰݸಡΈࠐΜͰɺͦΕΛฦ͢ɻ runtest "0" 0 runtest "1" 1
runtest "42" 42 ͜ͷΑ͏ͳग़ྗΛಘΔʹʁ 14
Step 2 ࣗવΛಡΉ ΛҰݸಡΈࠐΜͰɺͦΕΛฦ͢ɻ int eval(char *p) { int ival
= 0; while (isdigit (*p)) { ival = ival * 10 + *p - ’0’; p++; } return ival; } ٙϗϫΠτϘʔυͰղઆɻ 15
Step 3 ͠ࢉΛ͢ ͠ࢉͬͯԿͩΖ͏ɻ runtest "1+42" 43 runtest "23+42" 65
runtest "1+2+4" 7 runtest "1+2+4+10" 17 ͜ͷΑ͏ͳग़ྗΛಘΔʹʁ 16
Step 3 ͠ࢉΛ͢ ʮ͠ࢉʯͱ 1. ॳΊʹ͕དྷΔɻ 2. ͦͷޙʹʮ+ ʯ͕ 0
ճҎ্܁Γ ฦ͢ɻ e.g. 42, 1+2, 1+2+3 17
Step 3 ͠ࢉΛ͢ 1. ॳΊʹ͕དྷΔɻ 2. ͦͷޙʹʮ+ ʯ͕ 0 ճҎ্܁Γ
ฦ͢ɻ ͠ࢉ := ( ‘+’ )* 18
Step 3 ͠ࢉΛ͢ ͠ࢉ := ( ‘+’ )*
int ival = parse_integer (); while (*p++ == ’+’) ival += parse_integer (); return ival; ٙϗϫΠτϘʔυͰղઆɻ 19
Step 4 Ҿ͖ࢉΛ͢ ಉ͡Α͏ʹͯ͠ΈΔɻ runtest "1+2 -3+5" 5 ͜ͷΑ͏ͳग़ྗΛಘΔʹʁ 20
Step 4 Ҿ͖ࢉΛ͢ ͠ࢉ := ( ( ‘+’ |
‘-’ ) )* e.g. 42, 1+3, 12-3, 4+2-5+4-1 ͠ࢉ :thinking face: 21
int ival = parse_integer (); while (*p != ’\0’) {
switch (*p) { case ’+’: p++; ival += parse_integer (); break; case ’-’: p++; ival -= parse_integer (); break; default: goto end; } } end: return ival; 22
Step 5 ֻ͚ࢉɾׂΓࢉΛ͢ ಉ͡Α͏ʹ࣮͢Δʁ runtest "1*2+3" 5 runtest "13/3+4" 8
runtest "1+2*3" 7 runtest "1*2+3*4" 14 runtest "5/2+99/3" 35 ͜ͷΑ͏ͳग़ྗΛಘΔʹʁ 23
Step 5 ֻ͚ࢉɾׂΓࢉΛ͢ ͠ࢉ:= ( ( ‘+’ | ‘-’
| ‘*’ | ‘/’) )* 2*3+4 Αͦ͞͏ɻ 24
Step 5 ֻ͚ࢉɾׂΓࢉΛ͢ ͠ࢉ:= ( ( ‘+’ | ‘-’
| ‘*’ | ‘/’) )* 2*3+4 Αͦ͞͏ɻ 4+2*3 ʁ 24
Step 5 ֻ͚ࢉɾׂΓࢉΛ͢ ԋࢉࢠͷ༏ઌॱҐͱʁ 4 + (2 * 3) -
(6 / 3) ͠ࢉͷཁૉͱֻ͚ͯ͠ࢉΛ͑Δɻ ͱֻ͚ࢉಉ͡ѻ͍ɻ 25
Step 5 ֻ͚ࢉɾׂΓࢉΛ͢ ֻ͚ࢉ:= ( ( ‘*’ | ‘/’
) )* ͠ࢉ:= ֻ͚ࢉ ( ( ‘+’ | ‘-’ ) ֻ͚ࢉ )* શͯͷϓϩάϥϜʮ͠ࢉʯ e.g. 42, 1+2-3, 2*3/2, 2*3+4*5-10/3 26
int parse_add () { int ival = parse_mul (); while
(*p != ’\0’) { switch (*p) { case ’+’: p++; ival += parse_mul (); continue; case ’-’: p++; ival -= parse_mul (); continue; } break; } return ival; } 27
int parse_mul () { int ival = parse_integer (); while
(*p != ’\0’) { switch (*p) { case ’*’: p++; ival *= parse_integer (); continue; case ’/’: p++; ival /= parse_integer (); continue; } break; } return ival; } 28
Step 6 ؔݺͼग़͠Λ࣮ ͷग़ྗΛߦ͏ؔ P() Λͭ͘Δɻ ؔͷΓ 0 ͱ͓ͯ͘͠ɻ runtest
"P(1)" 0 # 1 on screen 29
Step 6 ؔݺͼग़͠Λ࣮ F(2) / 2 + G(3+4*2) * H(0)
- 5 • ؔͷΓͱಉ͡ѻ͍ɻ • ؔͷҾʮ͠ࢉʯ 30
Step 6 ؔݺͼग़͠Λ࣮ ؔݺग़:= ‘P’ ‘(’ ͠ࢉ ‘)’ |
ֻ͚ࢉ:= ؔݺग़ ( ( ‘*’ | ‘/’ ) ؔݺग़ )* ͠ࢉ:= ֻ͚ࢉ ( ( ‘+’ | ‘-’ ) ֻ͚ࢉ )* 31
int parse_mul () { int ival = parse_funccall (); while
(*p != ’\0’) { switch (*p) { case ’*’: p++; ival *= parse_funccall (); continue; case ’/’: p++; ival /= parse_funccall (); continue; } break; } return ival; } 32
int parse_funccall () { if (*p == ’P’) { p++;
expect(’(’); int ival = parse_add (); expect(’)’); printf("%d\n", ival ); return 0; } return parse_integer (); } 33
Step 7 ࣜͷ۠ΓΛՃ ‘;’ ͰࣜΛ۠ΕΔΑ͏ʹ͢Δɻ runtest "P(1);10+2;3" 3 ࠷ऴతͳҰ൪࠷ޙͷࣜͷɻ 34
Step 7 ࣜͷ۠ΓΛՃ ؔݺग़:= ‘P’ ‘(’ ࣜ ‘)’ |
ֻ͚ࢉ:= ؔݺग़ ( ( ‘*’ | ‘/’ ) ؔݺग़ )* ͠ࢉ:= ֻ͚ࢉ ( ( ‘+’ | ‘-’ ) ֻ͚ࢉ )* ࣜ:= ͠ࢉ ( ‘;’ ͠ࢉ )* શͯͷϓϩάϥϜʮࣜʯ 35
int eval() { int ival = parse_add (); while (*p
== ’;’) { p++; ival = parse_add (); } return ival; } 36
Step 8 Ҿͳؔ͠ఆٛΛՃ Ҿͳ͠ͷؔఆ͕ٛͰ͖ΔΑ͏ʹ͢Δɻ runtest "F{1}F()" 1 runtest "F{5/2+99/3 -3*4}F()"
23 runtest "F{5/2+99/3 -3*4;100 -24}F()"\ 76 ໊ؔେจࣈΞϧϑΝϕοτ 1 จࣈɻ ؔఆٛϓϩάϥϜͷઌ಄ͷΈͰՄೳɻ 37
Step 8 Ҿͳؔ͠ఆٛΛՃ F{5/2+99/3-3*4;100-24} • ໊͕ؔ࢝ΊʹདྷΔɻ • {ͱ}ͰؔຊମΛғΉɻ • ؔຊମࣜΛ;
Ͱ۠ͬͨͷɻ • ؔͷΓؔຊମΛධՁ͠ ͨɻ 38
Step 8 Ҿͳؔ͠ఆٛΛՃ F{5/2+99/3-3*4;100-24} ؔఆٛ := [ ‘A’-‘Z’ ] ‘{’
ࣜ ‘}’ ؔݺग़ := ‘P’ ‘(’ ࣜ ‘)’ | [ ‘A’-‘Z’ ] ‘(’ ‘)’ | 39
int eval() { while (1) { if (’A’ <= *p
&& *p <= ’Z’ && *(p + 1) == ’{’) { parse_funcdef (); continue; } return parse_exprs (); } } 40
char *funcbuf [256]; void parse_funcdef () { int n =
*p++; expect(’{’); funcbuf[n] = p; while (*p != ’\0’ && *p++ != ’}’) ; } 41
int parse_funccall () { // ... process of P()... //
then other functions if (’A’ <= *p && *p <= ’Z’) { int name = *p; p++; expect(’(’); expect(’)’); char *old_p = p; p = funcbuf[name ]; int ival = parse_exprs (); p = old_p; return ival; } return parse_integer (); } 42
Step 9 Ҿ͋ΓؔఆٛΛՃ Ҿ͋Γͷؔఆ͕ٛͰ͖ΔΑ͏ʹ͢Δɻ runtest "F{a}F(42)" 42 runtest "F{a+b;a*b}F(1 ,1+1)"
2 ҾখจࣈΞϧϑΝϕοτ 1 จࣈɻ ݺͼग़͠ଆΧϯϚͰ۠ͬͯ͢ɻ 43
Step 9 Ҿ͋ΓؔఆٛΛՃ F{a+b;a*b} • ͱҾΛಉʹѻ͏ɻ • ؔͷதΛධՁ͢Δͱ͖ʹɺҾΛ ରԠ͢Δʹ͢Γସ͑Δɻ ͺͦ͜ΜΘ͔ΒΜʂ͆ͷͰҾΛม
ʢvariableʣͱ͍͏໊લͰ࣮ͨ͠ɻ 44
Step 9 Ҿ͋ΓؔఆٛΛՃ F{a+b;a*b} ม := [ ‘a’-‘z’ ] |
ؔݺग़ := ‘P’ ‘(’ ࣜ ‘)’ | [ ‘A’-‘Z’ ] ‘(’ ‘)’ | ม 45
int *varbuf; int parse_variable () { if (’a’ <= *p
&& *p <= ’z’) return varbuf [(int)*p++]; return parse_integer (); } 46
Step 9 Ҿ͋ΓؔఆٛΛՃ parse funccall() ͷղઆ 1. ໊ؔͱ (ΛಡΉɻ 2.
มςʔϒϧΛ࡞ΔɻҾΛධՁͯ͠ tmpbuf ʹೖΕΔɻ 3. ) ΛಡΉɻ 4. p ͱ funcbuf[name] ΛೖΕସ͑Δɻ 5. tmpbuf ͱ varbuf ΛೖΕସ͑Δɻ 47
Step 9 Ҿ͋ΓؔఆٛΛՃ parse funccall() ͷղઆ 6. parse exprs() ΛݺͿ͜ͱͰؔຊମΛಡ
Ήɻ͜ͷ͕Γɻ 7. ্ͰೖΕସ͑ͨ p ͱ varbuf Λݩʹ͢ɻ 8. ΓΛฦ͢ɻ 47
Step 10 ϑΟϘφονྻΛग़ྗ͢Δ ඞཁͳݴޠػೳશ࣮ͯɻ runtest "1*2+3" 5 runtest "13/3+4" 8
runtest "P(1);10+2;3" 3 runtest "F{a+b;a*b}F(1 ,1+1)" 2 ͜ΕΒΛ༻͍ͯϑΟϘφονྻΛग़ྗ͢ Δʹʁ 48
Step 10 ϑΟϘφονྻΛग़ྗ͢Δ F{P(a);F(b,a+b)}F(1,1) % ./main "F{P(a);F(b,a+b)}F(1,1)" | head -25
2 ͷྦྷͱ͔ܭࢉͰ͖Δɻ 49
·ͱΊ 50
·ͱΊ ݴޠॲཧܥ Δ͚ͩ 50
͝ਗ਼ௌ ͋Γ͕ͱ͏͟͝ ͍·ͨ͠ 51