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
900
F*でプログラムの正しさを証明する
anqou
1
1.1k
「自作CPUでサイゼリヤ問題」を支える技術
anqou
2
340
ぼくのかんがえたさいきょうのマリオAI
anqou
1
560
seccamp2018でセルフホストCコンパイラをつくった
anqou
8
5.5k
Other Decks in Programming
See All in Programming
Language Server と喋ろう – TSKaigi 2025
pizzacat83
2
670
primeNumberでのRBS導入の現在 && RBS::Traceでinline RBSを拡充してみた
mnmandahalf
0
250
What Spring Developers Should Know About Jakarta EE
ivargrimstad
1
610
ts-morph実践:型を利用するcodemodのテクニック
ypresto
1
540
tsconfigのオプションで変わる型世界
keisukeikeda
1
130
Javaに鉄道指向プログラミング (Railway Oriented Pro gramming) のエッセンスを取り入れる/Bringing the Essence of Railway-Oriented Programming to Java
cocet33000
1
100
がんばりすぎないコーディングルール運用術
tsukakei
1
180
Devinで実践する!AIエージェントと協働する開発組織の作り方
masahiro_nishimi
6
2.6k
Investigating Multithreaded PostgreSQL
macdice
0
150
REST API設計の実践 – ベストプラクティスとその落とし穴
kentaroutakeda
2
320
Agent Rules as Domain Parser
yodakeisuke
1
350
PT AI без купюр
v0lka
0
200
Featured
See All Featured
Learning to Love Humans: Emotional Interface Design
aarron
273
40k
Automating Front-end Workflow
addyosmani
1370
200k
Performance Is Good for Brains [We Love Speed 2024]
tammyeverts
10
840
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
Docker and Python
trallard
44
3.4k
Music & Morning Musume
bryan
47
6.6k
Navigating Team Friction
lara
186
15k
It's Worth the Effort
3n
184
28k
The Illustrated Children's Guide to Kubernetes
chrisshort
48
50k
BBQ
matthewcrist
88
9.7k
Building an army of robots
kneath
306
45k
Become a Pro
speakerdeck
PRO
28
5.4k
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