用OurCoder监督自己的学习
由 尼克徐 发布于 2014年03月25日 ｜ 更新于 2014年07月17日tinyfool sycx multilinguist 等7人欣赏。
为了克服自己的懒惰和思路发散，从今天开始，在ourcoder网站的监督下学习（已征得@tinyfool 的同意，感谢！）。
具体办法是：
1,首先向@tinyfool 打款50元，作为付给网站方的服务费。学习计划完成后，再向网站方打款100元，以示感谢。
2，本次学习目标：compilers (网址：https://class.coursera.org/compilers-004）
3，学习周期：3个月，到6月26日截止。
4， 具体量化目标： 每周完成compilers里布置的作业，并参与最后的考核，成绩达标。 每周要把完成作业的贴图贴到本帖下，以供大家监督。
5，惩罚措施： 如果某一周没有完成该周任务，则罚款50元。
此次学习计划从今天开始。
看完导论，开始学Compilers的第一周第一次课。
这次课开始学一门语言，叫做"Cool"语言，以后的课程就是要编一个Cool语言的编译器。
Cool语言是一门教学语言( Classroom Object Oriented Language)，它很简单，专门用于编译原理的教学，所以它的编译器非常多，据说几百个，都是学生写的...
1，虚拟机下载和运行，见链接： link text
2，写了个程序：hello_world.cl
class Main inherits IO {
main(): SELF_TYPE {
out_string("Hello, World.\n")
};
};
编译： coolc hello_world.cl
编译成 hello_world.s
执行： spim hello_world.s
输出：Hello, World.
上周末，继续学习Cool语言，几个小程序： 求阶乘的：
class Main inherits A2I {
main() : Object {
(new IO).out_string(i2a(fact(a2i((new IO).in_string()))).concat("n"))
};
fact(i: Int) : Int {
if (i = 0) then 1 else i * fact(i-1) fi
};
};
以及另一写法：
class Main inherits IO {
main(): Object {{
out_string("Enter an integer greater-than or equal-to 0:");
let input: Int <- in_int() in
if input < 0 then
out_string("ERROR: Number must be greater-than or equal-to 0n")
else {
out_string("The factorial of ").out_int(input);
out_string(" is ").out_int(factorial(input));
}
fi;
}};
factorial(num: Int):Int {
if num = 0 then 1 else num * factorial(num - 1) fi
};
};
还有几个，关于Cool的数据结构的，不贴上了。
后来又学了正则表达式及其实现原理，确定状态自动机DFA（Deterministic finite automaton），不确定状态自动机(Nondeterministic finite automaton),及其实现(总共是两周的课程量)。
作业留的很多，其中一个是以Flex为辅助工具写词法分析器代码(C++)，并能作为词法分析模块嵌入到以前的Compiler项目中去运行而不出错。
另一些是对某些字符串，根据状态机原理做推理和变换等。
为了做完这些作业，老师列了一堆的参考资料，近百页英文。
4月9日是作业提交截止日期。时间紧张啊...
这两天继续学习Flex/Bison,不学好这个,没法完成作业了。
Flex/Bison很好玩,几十行代码,规定了TOKEN的正则表达式和语法推理的规则,就能做一个简单的语言解释器,的例如我做了个计算器解释器的练习,源代码:
fb1-4.l
/* rocognize tokens for the calculator */
%{
#include "fb1-5.tab.h"
%}
%%
"+" {return ADD; }
"-" {return SUB; }
"*" {return MUL; }
"/" {return DIV; }
"|" {return ABS; }
"(" {return OP; }
")" {return CP; }
"//".* /* ignore comments */
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
n {return EOL; }
[ t] { /* ignore whitespace */ }
. { printf("Mystery character %c\n", *yytext); }
%%
fb1-5.y:
/* simplest version of calculator */
%{
#include <stdio.h>
%}
/* declare tokens */
%token NUMBER
%token OP CP
%token ADD SUB MUL DIV ABS
%token EOL
%%
calclist: /* nothing */
| calclist exp EOL {printf(" = %d\n",$2);}
;
exp: factor /* default $$=$1 */
| exp ADD factor { $$ = $1 + $3; }
| exp SUB factor { $$ = $1 - $3; }
;
factor: term /*default $$ = $1 */
| factor MUL term { $$ = $1 * $3; }
| factor DIV term { $$ = $1 / $3; }
;
term: NUMBER /* default $$ = $1 */
| ABS term { $$ = $2 >= 0 ? $2 : -$2;}
| OP exp CP { $$ = $2; } //New rule
;
%%
int main(int argc, char **argv)
{
yyparse();
return 0;
}
int yyerror(char *s)
{
fprintf(stderr, "error: %s\n", s);
return 0;
}
int yywrap(void)
{
return 1;
}
生成解释器源代码用的命令行:
flex fb1-4.l
bison -d fb1-5.y
此时会生成lex.yy.c, fb1-5.h, fb1-5.c几个源代码,然后编译(我用的是WINXP的32位环境,所以编译时加参数-m32)
gcc -m32 fb1-5.tab.c lex.yy.c -o calc.exe
此处生成的calc.exe就是个计算器了。运行后结果:
C:flexbison>calc
4+3*(5-2)
= 13
5+3*4
= 17
起了个大早儿，连滚带爬在Deadline前完成了这期的Compilers作业。
选择题太难了，12分只得了6.5分。推理证明题挺容易，都做出来了。
后天要交源代码的作业了,还没动手做呢，参考资料还没啃完...然后老板吼着这周要加班！
哭啊，熬夜做完的词法分析器编译成功了但有一大堆错误，来不及检查了又到Deadline了。一会还得上班去。真不想工作了！
含泪继续被罚款50元...
早上得多吃点。宁可发胖也要安慰受伤的心。
这一两百块钱，真没有杀伤力。应该立志，如果一天不学习，就自己砍自己一个脚指。
看看过两个月还有没有脚指了，如果没有的话，就不用学习了。
以我学习的经验来看，养成一个习惯大概两个月就了，不用那么费心。
最近在学Parser和Top Down Parser.
理解了语法定义时的一些问题。
例如，运算符的优先级的实现，不是表面那么简单，是通过多余的语法项的定义来实现的。
以及左递归的问题。
终于在Deadline之前完成了这一期的作业，成绩险险的及格了，不用被罚款了，汗一个。
作业依旧很难，尤其是选择题，有些是连蒙带猜。
没想到编译器原理里，有那么多的类似数学的东西，很难懂。
就这个状态，我不知道怎么通过期中考试...
下次这门课开课我会继续在这里，用同样的方式跟。:-)
总结一下学这门课，到目前为止的收获：
1， 对确定有限状态机和非确定有限状态机的原理和转换有了更深入的理解，知道了为什么和怎么做以及怎么优化。这对以后我学Automata提供了很好的基础。
2， 搞明白了正则表达式的实现，正在用c写一个轻量级正则表达式解析器（用于tokenizer），正好可以把上一条的收获全用上。
3， 对从语法的定义，到生成语法树的算法理解更深入了，计划写一两个可插拔的语法树解析算法，来验证所学到的东西。
4， 初步学会了flex/bison的使用。