学步园

HOC(High Order Calculator) 是一个解释型的程序语言，最初的版本由Brain Kernighan和Rob Pike在《The UNIX Programming Environment》[UNIX编程环境]一书中作为一个例子给出。本身由lex/yacc构造，结构十分清晰，作为一个教学语言，HOC支持函数，具有类C的语法，有简单的I/O，变量赋值，表达式计算，错误恢复等机制。

后来，Bell实验室又陆续开发出了一些改进的版本，使得HOC可以平坦的移植到各种Linux系统中，我在上学的时候阅读过[UNIX编程环境]这本书，并且对其中的HOC做了一些简单的改进，后来又找到了Bell实验室的一个版本，深入的学了一遍，由于这个发布版本出自Research UNIX系统，我又对源码做了一些修改，并将其移植到了Windows平台。

在第一次学习HOC解释器的时候，是在编译原理课程结束后，当时是想在linux下设计一个通用的数学计算引擎，然后将计算出的数据通过一个前端展示系统(最好平台无关)展示给最终用户。开始，准备用Delphi自己写一个，但是一直没有实现，这个项目就停止了。直到后来发现了一个优秀的绘图工具gnuplot(关于gnuplot的更多细节，请参看我的另一篇文章), 用它来做前端似乎再合适不过了，于是，我决定将原来的改进后的HOC移植到Windows下，然后进行一个简单的整合。

下面是用HOC语言写的一段代码：

代码很简单，先定义一个过程：plotSin(在HOC中有procedure,function之分，前者没有返回值，而后者有)，这个过程定义了三个临时变量begin,end,step,其中PI是一个常量，其值为3.1415926, 然后是一个for循环，begin不断加step(0.1)，直到不小于end，退出循环，同时每次迭代时，先计算sin(begin)的值，并打印此时的begin和sin(begin)值。最后，调用这个过程，执行计算并退出。

这个是程序生成的数据：

将数据交给gnuplot展示，gunplot可以轻易的从数据文件中读出数据，并以第一列为横坐标，第二类为纵坐标画出图形来，根据上边这个数据文件，gnuplot画出的图形结果如下：

如果需要绘制3-D的图形，事实上更为简单一些。如下面的代码所示：

代码很简单，就是两层循环，计算出sin(x)*cos(y)的值，打印出来，一次x迭代结束后，打印一个空行，这样gunplot可以识别次文件，并画出3-D的图形来。

使用gnuplot的3-D绘制命令，splot，可以得到下边的图形：

z = sin(x)*cos(y)

 
 z = x * y

 
 z = x^2 - y^2 (鞍面)

整个思路很清晰，没有什么难懂的地方，而这个HOC的原始版本就是在UNIX下用lex/yacc开发的，只要对正则表达式和BNF形式比较熟悉就可以很快的理解整个解释器的实现(建议直接去看源码)。如果不太熟悉，那么就接着往下看，我会详细解释这些工具的用法和一些形式语言的理论。

• 形式语言

在计算机科学中，形式语言 是用精确的数学定义或者机器可识别的公式定义的语言，形式语言跟自然语言很类似，包含两部分：语法 和语义 。形式语言的定义 为：

• 正则表达式和BNF

1940年代，Warren McCulloch与Walter Pitts将神经系统中的神经元描述成小而简单的自动控制元。在1950年代，数学家斯蒂芬·科尔·克莱尼利用称之为正则集合 的数学符号来描述此模型。正则表达式又称为模式(pattern)，用来描述一系列符合某个句法 规则的串，正则表达式的表达能力十分强大，特别在对串的描述上。通过一系列的数学符号的引入，使得一个很简洁的表达式可以匹配一个很复杂的串，这正是使用正则表达式的目的。正则表达式有很多的现，C,JAVA,JavaScript等语言都支持正则表达式,perl语言对正则表达式的支持更是到达了一个空前的高度。

在对一些有某些特征的串进行描述的时候，通常会觉得特别难，在使用状态机的理论后，可以得到一定的简化，在数学上可以证明，状态机的表达能力跟正则表达式的表达能力是相等的，也就是说，一切能用状态机表示出来的语言用正则语言也是可以描述的。

下面说两个简单的例子，我们在表达“浮点数”这个概念时，用自然语言可以做如下描述：“由若干个数字开头，然后是一个点号(.)，然后又是若干个数字”。将这种不确定的语言如何翻译成机器能识别的语言呢？幸好，科学家发明了正则表达式，比如这个例子中，我们可以使用:[0-9]+\.[0-9]{1,} 来表示(当然，这个版本可能有bug，暂时不考虑)。又比如，在很多计算机程序设计语言中，变量命的规则为“以下划线或者字母开头，由数字，下划线，字母组成，长度不超过某个限制(比如64个字符)”，用正则表达式可以做出下面的描述：[_a-zA-Z][_a-zA-Z0-9]{,63}.

BNF，说起BNF就更牛了，BNF是一种上下文无关文法 (context-free)，基本上所有的计算机语言都是使用上下文无关文法描述的，在表达能力上，上下文无关文法要比有限自动机 和正则文法 强大，先看看一个上下文无关文法的简单例子：

语言G1，有以下规则：

语言L(G1)可以描述这样一个语言：L(G1) = {0ⁿ # 1ⁿ | n >= 0}。
上下文无关文法的形式定义是这样：

如在文法G1中，V={A, B}, Σ = {0, 1, #}, S = A, R为:
A -> 0A1
A -> B
B -> #

这部分基本上是纯理论，看懂了下边的很好理解，看不懂的也没有关系，在下边的实践中慢慢的理解，最终会理解的。

• lex/yacc

这两个工具太有名了，而且功能非常之强大，在UNIX下已经牛了几十年了，很多工具和语言的解释器都是用它们来做的。一般来说，lex生成关于记号的规则，生成yacc需要用到的tokens，yacc定义文法以及语义，而语义的解释一般由外部的C来完成，UNIX下，C是原生的，而且这些工具可以无缝连接，所以在*nix下做一个语言的解释器是很容易的。当然，如果你在windows平台，照样可以完成这些动作，只是稍微有点麻烦。lex/yacc已经被已经到了windows平台，而且有很多个版本,GNU Bison已经很好的工作在win32平台了。还有一个集成开发环境，叫Parser
Generator，不过这个是面向学生和教育工作者的，其他的人需要购买一个License.

lex中，用正则表达式定义一些记号，如数字，字符串，关键字等的定义可以放在这个里，主要是做词法分析。lex将输入的文件按字符读入，然后匹配定义好的规则，如果发现是数字则返回数字，等等。返回的结果交给yacc(语法分析)做进一步处理。

yacc，使用BNF描述一些语法规则，它将lex返回来的记号与自己的规则相匹配，发现匹配后，执行一定的语义解释，翻译！

• C语言的函数指针

C语言中，函数是可以作为一个指针，这个指针指向函数的内存空间，如果这些指针放在一个数组中，你甚至可以通过指针的移动如*pc++来调用下一个函数(当然，这种方式本身是不推荐的)。

定义一个函数指针 ：

double (*func)(double);

表示，当以了一个函数指针*func,这个函数接受一个double类型的参数，并返回一个double型的数。比如，在HOC中，有一个函数名与具体函数之间的映射表，代码如下

init.c line42

C代码  

1. static struct {        /* Built-ins */  
2.     char *name;  
3.     double    (*func)(double);  
4. } builtins[] = {  
5.     "sin",    sin,  
6.     "cos",    cos,  
7.     "tan",    tan,  
8.     "atan",    atan,  
9.     "asin",    Asin,    /* checks range */  
10.     "acos", Acos,    /* checks range */  
11.     "sinh",    Sinh,    /* checks range */  
12.     "cosh",    Cosh,    /* checks range */  
13.     "tanh",    tanh,  
14.     "log",    Log,    /* checks range */  
15.     "log10", Log10,    /* checks range */  
16.     "exp",    Exp,    /* checks range */  
17.     "sqrt",    Sqrt,    /* checks range */  
18.     "gamma", Gamma,    /* checks range */  
19.     "int",    integer,  
20.     "abs",    fabs,  
21.     "erf",    erf,  
22.     "erfc",    erfc,  
23.     0,    0  
24. };  

再比如，HOC的符号表 (编译器内部的一个常用的数据结构，用于存储编译过程中的二元组)Symbol结构：

hoc.h line4

C代码  

1. typedef struct Symbol { /* symbol table entry */  
2.     char *name;  
3.     long type;  
4.     union {  
5.         double val; /* VAR */  
6.         double (*ptr)(double); /* BLTIN */  
7.         Inst *defn; /* FUNCTION, PROCEDURE */  
8.         char *str; /* STRING */  
9.     } u;  
10.     struct Symbol *next; /* to link to another */  
11. } Symbol;  

其中内部的匿名union中，有一个字段double (*ptr)(double)就是一个函数指针，名字为ptr,用于表示内建的函数表，也就是刚才提到的builtins数组。

好了，理论就先说到这里，下面开始从头开始构造HOC语言，我会先设计一个简单的框架，我们逐步扩展这个框架，并在最后实现这个语言解释器。好了，可以开始了……

• 一个简单的计算器

hoc.l

C代码  

1. %{  
2. #include "y.tab.h"  
3. extern YYSTYPE yylval;  
4. extern int lineno;  
5. %}  
6. %%  
7. [ \t]+        {;}//空白字符，如空格，table等  
8. [0-9]+|[0-9]*\.[0-9]+     
9.             {//浮点数  
10.                 sscanf(yytext,"%lf",&yylval.val);  
11.                 return NUMBER;  
12.             }  
13. \n          {//换行  
14.                 lineno++;  
15.                 return '\n';  
16.             }  
17. .           {//其他任意字符  
18.                 return yytext[0];  
19.             }  
20. %%  

hoc.l很简单，读到空白字符，如空格，table等键则忽略不计，接着读下一个字符，读到换行，就将lineno变量加一，读到浮点数，则将内容读入yylval，并返回NUMBER标记。

hoc.y

C代码  

1. %{  
2. #include <stdio.h>  
3. #include <stdlib.h>  
4. char *progname;//记录程序名，为了显示错误  
5. int    lineno = 1;//行号，用于显示错误  
6. %}  
7. %union{  
8.     double val;  
9. }  
10. %token <val> NUMBER  
11. %type <val> expr  
12. %left '+' '-'  
13. %left '*' '/'  
14. %left UNARYMINUS//left 意思为这些操作符的结合方式是从左到右，而有些操作符如平方，与此相反  
15. %%  
16. list    :     
17.         |    list '\n'  
18.         |    list expr '\n'    {printf("\t%.8g\n",$2);}//打印结果  
19.         ;  
20. expr    :    NUMBER            {$$ = $1;}  
21.         |    '-' expr %prec UNARYMINUS {$$ = -$2;}//负数  
22.         |    expr '+' expr    {$$ = $1 + $3;}  
23.         |    expr '-' expr    {$$ = $1 - $3;}  
24.         |    expr '*' expr    {$$ = $1 * $3;}  
25.         |    expr '/' expr    {$$ = $1 / $3;}  
26.         |    '(' expr ')'     {$$ = $2;}  
27.         ;  
28. %%  
29. //上边的$$表示根规则(变元)的值，$1,$2,$i 等表示，第i个子表达式(终结符或者变元)  
30. int main(int argc,char **argv)  
31. {  
32.     progname = argv[0];//记录程序的名字  
33.     yyparse();  
34. }  
35. yywrap()  
36. {  
37.     return 1;  
38. }  
39. yyerror(char *s)  
40. {  
41.     warning(s,(char *)0);  
42. }  
43. warning(char *s,char *t)  
44. {