真相永远只有一个！

哎最近一直忙于做编译器大作业…好久不来更新blog了OTZ…昨天刚把期中检查的东西上传上去…终于可以喘一口气了，过了五一节之后又要开始奋战了
简单介绍一下这个令所有ACM班人发指的东西吧 - - 以后要是哪位后辈看到了偶这篇BLOG的话好有心理准备…
众所周知编译原理是一门几乎所有计算机系必修的课，但是却很少有人会在本科阶段去尝试做一个编译器…国外大学倒貌似有不少这样的例子，例如Princeton，我们做的Tiger编译器好像就是那边先提出来的。
Tiger本身语言并不难，和Pascal有点像。我们所要做的就是将一个Tiger程序转换成一个.s文件，这个文件是可以在spim软件上面跑的，比如说下面是一个tiger的八皇后程序，搞过分区联赛的人应该都能看懂吧

/* A program to solve the 8-queens problem */

let
    var N := 8

    type intArray = array of int

    var row := intArray [ N ] of 0
    var col := intArray [ N ] of 0
    var diag1 := intArray [N+N-1] of 0
    var diag2 := intArray [N+N-1] of 0

    function printboard() =
       (for i := 0 to N-1
  do (for j := 0 to N-1
       do print(if col[i]=j then " O" else " .");
      print("\n"));
         print("\n"))

    function try(c:int) =
( /*  for i:= 0 to c do print("."); print("\n"); flush();*/
     if c=N
     then printboard()
     else for r := 0 to N-1
    do if row[r]=0 & diag1[r+c]=0 & diag2[r+7-c]=0
            then (row[r]:=1; diag1[r+c]:=1; diag2[r+7-c]:=1;
           col[c]:=r;
       
                  try(c+1);
    row[r]:=0; diag1[r+c]:=0; diag2[r+7-c]:=0)

)
 in try(0)
end
 
做这个编译器需要分为12步，被我们的助教称作是“黄金十二宫”，而他们就是黄金圣斗士（拦路虎么 - -），我们算是青铜圣斗士么囧，那雅典娜是啥 - -
首先前面五步主要分为Flex程序编写，Cup的编写和Type Checking，Flex是词法分析，Cup是语法分析，Type Checking是语义分析。具体说来的话，Flex要为每一个终结符和非终结符指明返回的东西，比如说像下面这样

letter        = [A-Za-z]
digit        = [0-9]
letterdigit       = {letter}|{digit}
other_id_char        = [_]
identifier       = {letter}({letterdigit}|{other_id_char})*
integer        = {digit}*
LineTerminator           = \r|\n|\r\n
WhiteSpace       = {LineTerminator} | [ \t\f]

%state STRING
%state COMMENT

%%
/*keywords*/

<YYINITIAL>"array"       {return newSym(sym.ARRAY);}
<YYINITIAL>"break"       {return newSym(sym.BREAK);}
<YYINITIAL>"do"        {return newSym(sym.DO);}
<YYINITIAL>"else"       {return newSym(sym.ELSE);}
<YYINITIAL>"end"       {return newSym(sym.END);}
<YYINITIAL>"for"       {return newSym(sym.FOR);}
<YYINITIAL>"function"       {return newSym(sym.FUNCTION);}
<YYINITIAL>"in"        {return newSym(sym.IN);}
<YYINITIAL>"if"        {return newSym(sym.IF);}
<YYINITIAL>"let"       {return newSym(sym.LET);}
<YYINITIAL>"nil"       {return newSym(sym.NIL);}
<YYINITIAL>"of"        {return newSym(sym.OF);}
<YYINITIAL>"or"        {return newSym(sym.OR);}
<YYINITIAL>"then"       {return newSym(sym.THEN);}
<YYINITIAL>"to"        {return newSym(sym.TO);}
<YYINITIAL>"type"       {return newSym(sym.TYPE);}
<YYINITIAL>"var"       {return newSym(sym.VAR);}
<YYINITIAL>"while"       {return newSym(sym.WHILE);}

具体的用法请参考Flex的Manual，其实自己找资料然后看懂它，这种能力是相当重要的…
然后是Cup程序，Cup程序所起的作用是写出整个语言的语法结构和产生式，并且要添加相应的动作，比如说像这样

Exp ::= STRING:s     {: RESULT = new StringExp(sleft, s); :}
 | INT:i      {: RESULT = new IntExp(ileft, i.intValue()); :}
 | NIL:nil    {: RESULT = new NilExp(nilleft); :}
 | Lvalue:l    {: RESULT = new VarExp(lleft, (Var)l); :}
 | MINUS:z Exp:e    {: RESULT = new OpExp(zleft,(Exp)(new IntExp(zleft,0)),OpExp.MINUS,e); :}
 %prec UMINUS 

这些东西写的时候要多看Tiger Manual，拼命去看，就像limu大神所说的那样，要放在床头每天看…有些你想不通的问题可能Manual里面就会有…
最后是Type Checking，也称为Semant，意思就是写一个Semant的类，对语句进行类型检查，比如说for循环中不能对循环变量进行赋值，if a then b else c中a必须为int类型，b和c必须返回相同的值，如果c不存在则b必须返回VOID等等…具体的程序我就不贴了，这程序要写600行左右…搞了我好几天啊OTL…像liuchang那样的大神flex写了1个小时，cup写了2个小时，type checking6个小时就搞定了…一个通宵就全部完成了OTL…还设计了好多变态的测试数据，不是为了来测我们的程序，而是想当上下一届的助教然后去虐待下一届的学弟学妹们…（后辈们啊…要是以后是liuchang这个人做你们助教的话，还是小心一点为妙 - -）
这东西难做之处，在于开始的时候根本无从下手，所以推荐大家还是去网上搜一些东西来看看
至于搜索么，要知道光搜“tiger compiler”这样的关键字是不行的~~~=v=~~~，至于怎么搜么，比如说cup里面会经常出现“e1left”这种平时碰不到的关键字，去试试看吧=v=b
最后，如果想要源程序的话我肯定是不会给的…不过我可以提供一些非常有用的参考资料…需要的话请和我联系：
E-Mail: jimmyzzxhlh@gmail.com
QQ: 394926764（注明你是来要编译的东西…否则我一律54掉~~）