/* Decompression code */ while (1) { c = getchar(); if (c == EOF) break; if (c == 0xFF) { len = getchar(); c = getchar(); while (len--) emit(c); } else emit(c); } emit(EOF);
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
/* Parser code */ while (1) { c = getchar(); break; if (isalpha(c)) { do { add_to_token(c); c = getchar(); } while (isalpha(c)); got_token(WORD); } add_to_token(c); got_token(PUNCT); }
voidparser(int c) { staticenum { START, IN_WORD } state; switch (state) { case IN_WORD: if (isalpha(c)) { add_to_token(c); return; } got_token(WORD); state = START; /* fall through */ case START: add_to_token(c); if (isalpha(c)) state = IN_WORD; else got_token(PUNCT); break; } }
在 The Art of Computer Programming 中,Donald Knuth 提出了解决此类问题的方法。他的回答是完全抛弃栈的概念。不要再将一个进程视为调用者,将另一个进程视为被调用者,而是开始将它们视为平等合作。
实际操作上:用略有不同的原语(primitive: In programming, a fundamental element in a language that can be used to create larger procedures that do the work a programmer wants to do.)替换传统的“调用(call)”原语。 新的“调用”会将返回值保存在堆栈以外的其他位置,然后跳转到另一个保存的返回值中指定的位置。 因此,每次解压缩器发出另一个字符时,它都会保存其程序计数器并跳转到解析器中最后已知的位置 - 每次解析器需要另一个字符时,它都会保存自己的程序计数器并跳转到解压缩器保存的位置。 控制在两个例程(routines)之间来回穿梭(back and forth)。
intfunction() { staticint i, state = 0; switch (state) { case0: goto LABEL0; case1: goto LABEL1; } LABEL0: /* start of function */ for (i = 0; i < 10; i++) { state = 1; /* so we will come back to LABEL1 */ return i; LABEL1: ; /* resume control straight after the return */ } }
intfunction(void) { staticint i, state = 0; switch (state) { case0: /* start of function */ for (i = 0; i < 10; i++) { state = 1; /* so we will come back to "case 1" */ return i; case1: ; /* resume control straight after the return */ } } }
现在这看起来很有希望。 我们现在要做的就是构建一些精心挑选的宏,我们可以将血淋淋的细节隐藏在看似合理的东西中:(使用do ... while(0)来确保crReturn直接出现在 if 和 else 之间时不需要大括号)
1 2 3 4 5 6 7 8 9 10
#define crBegin static int state=0; switch(state) { case 0: #define crReturn(i,x) do { state=i; return x; case i:; } while (0) #define crFinish } intfunction(void) { staticint i; crBegin; for (i = 0; i < 10; i++) crReturn(1, i); crFinish; }
intdecompressor(void) { staticint c, len; crBegin; while (1) { c = getchar(); if (c == EOF) break; if (c == 0xFF) { len = getchar(); c = getchar(); while (len--) crReturn(c); } else crReturn(c); } crReturn(EOF); crFinish; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
voidparser(int c) { crBegin; while (1) { /* first char already in c */ if (c == EOF) break; if (isalpha(c)) { do { add_to_token(c); crReturn( ); } while (isalpha(c)); got_token(WORD); } add_to_token(c); got_token(PUNCT); crReturn( ); } crFinish; }