- 浏览: 452981 次
- 性别:
- 来自: 西安
文章分类
最新评论
-
进退取舍:
谢谢,这个用上了!!
Java 一个线程池的示例 -
pb_water:
感谢楼主,打算买楼主的书,支持一下,楼主功德无量
JavaScript内核系列第0版整理稿下载 -
lancezhcj:
有图会直观的多呢,再摸索摸索
有限自动机与建模 -
hsmsyy:
这里应该是原创了吧,楼主我觉得闭包的作用:实现面向对象。有待商 ...
JavaScript内核系列 第7章 闭包 -
wll52:
在应用退出之前,需要释放连接 con.disconnect() ...
使用smack与GTalk通信
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,有以下规则:
A -> B
B -> #
语言L(G1)可以描述这样一个语言:L(G1) = {0n
# 1n
| n >=
0}。
上下文无关文法的形式定义是这样:
1) V是一个有穷集合,称为变元集
2) Σ是一个与V不相交的有穷集合,称为终结符集
3) R是一个有穷规则集,每条规则由一个变元(非终结符)和一个由变元和终结符组成的串组成
4) S ∈ V是起始变元
如在文法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
static struct { /* Built-ins */ char *name; double (*func)(double); } builtins[] = { "sin", sin, "cos", cos, "tan", tan, "atan", atan, "asin", Asin, /* checks range */ "acos", Acos, /* checks range */ "sinh", Sinh, /* checks range */ "cosh", Cosh, /* checks range */ "tanh", tanh, "log", Log, /* checks range */ "log10", Log10, /* checks range */ "exp", Exp, /* checks range */ "sqrt", Sqrt, /* checks range */ "gamma", Gamma, /* checks range */ "int", integer, "abs", fabs, "erf", erf, "erfc", erfc, 0, 0 };
再比如,HOC的符号表 (编译器内部的一个常用的数据结构,用于存储编译过程中的二元组)Symbol结构:
hoc.h line4
typedef struct Symbol { /* symbol table entry */ char *name; long type; union { double val; /* VAR */ double (*ptr)(double); /* BLTIN */ Inst *defn; /* FUNCTION, PROCEDURE */ char *str; /* STRING */ } u; struct Symbol *next; /* to link to another */ } Symbol;
其中内部的匿名union中,有一个字段double (*ptr)(double)就是一个函数指针,名字为ptr,用于表示内建的函数表,也就是刚才提到的builtins数组。
好了,理论就先说到这里,下面开始从头开始构造HOC语言,我会先设计一个简单的框架,我们逐步扩展这个框架,并在最后实现这个语言解释器。好了,可以开始了……
- 一个简单的计算器
hoc.l
%{ #include "y.tab.h" extern YYSTYPE yylval; extern int lineno; %} %% [ \t]+ {;}//空白字符,如空格,table等 [0-9]+|[0-9]*\.[0-9]+ {//浮点数 sscanf(yytext,"%lf",&yylval.val); return NUMBER; } \n {//换行 lineno++; return '\n'; } . {//其他任意字符 return yytext[0]; } %%
hoc.l很简单,读到空白字符,如空格,table等键则忽略不计,接着读下一个字符,读到换行,就将lineno变量加一,读到浮点数,则将内容读入yylval,并返回NUMBER标记。
hoc.y
%{ #include <stdio.h> #include <stdlib.h> char *progname;//记录程序名,为了显示错误 int lineno = 1;//行号,用于显示错误 %} %union{ double val; } %token <val> NUMBER %type <val> expr %left '+' '-' %left '*' '/' %left UNARYMINUS//left 意思为这些操作符的结合方式是从左到右,而有些操作符如平方,与此相反 %% list : | list '\n' | list expr '\n' {printf("\t%.8g\n",$2);}//打印结果 ; expr : NUMBER {$$ = $1;} | '-' expr %prec UNARYMINUS {$$ = -$2;}//负数 | expr '+' expr {$$ = $1 + $3;} | expr '-' expr {$$ = $1 - $3;} | expr '*' expr {$$ = $1 * $3;} | expr '/' expr {$$ = $1 / $3;} | '(' expr ')' {$$ = $2;} ; %% //上边的$$表示根规则(变元)的值,$1,$2,$i 等表示,第i个子表达式(终结符或者变元) int main(int argc,char **argv) { progname = argv[0];//记录程序的名字 yyparse(); } yywrap() { return 1; } yyerror(char *s) { warning(s,(char *)0); } warning(char *s,char *t) { fprintf(stderr,"%s : %s",progname,s); if(t) fprintf(stderr," %s",t); fprintf(stderr," near line %d\n",lineno); }
hoc.y中间的%%与%%之间的一段就是计算器的BNF的描述,这样一个简洁的描述和一些简单的语义规则($$ = $1 + $3等)即可完成一个桌面计算器的形式描述。其他的几个函数,是yacc要求实现的,做一些错误处理等操作。
如果你工作在*nix系统,可以使用下面的makefile来自动编译整个程序,需要注意的是,你需要一个lex和一个yacc,当然,C的编译器和目标文件的连接器也是必须的。
makefile
hoc: y.tab.o lex.yy.o gcc y.tab.o lex.yy.o -o hoc y.tab.o:y.tab.c gcc -c y.tab.c y.tab.c:hoc.y yacc -d hoc.y lex.yy.o:lex.yy.c gcc -c lex.yy.c lex.yy.c:hoc.l lex hoc.l clean: rm -f y.tab.[cho] rm -f lex.yy.[cho]
编译通过后,你即可使用在shell中测试一些简单的表达式求值:
$./hoc
这个版本的hoc可以处理一些比较简单的表达式,如(1+3)*(5-2),(-12)*6/2等,可以计算出结果,并打印出来。如果有不认识的文法如a++,3^2
= ?或者除0错误4/0等,你会得到一个错误信息,并且hoc会退出(这正是YACC默认的行为)。
- 支持变量
下一个版本,我们给hoc加入变量声明的机制,变量可以是a-z中的任意个字母,如可以定义:a = 2,b = -4等形式的量,变量可以跟数字一样做+/-/*/等操作。我们可以简单的加入一个数组来维护这些变量,对于第一个版本来说,改动并不大:
hoc.l
[a-z]{ yylval.index = yytext[0] - 'a'; return VAR; }
对hoc.l来说,我们可以添加这样一个简单的规则,将读到的变量的ASCII值放入一个全局变量(在lex和yacc中共享)中,并返回记号VAR,yac会对这个记号做处理。
hoc.y
double mem[26]; ... ... %union{ double val; int index; } expr: ... ... | VAR {$$ = mem[$1];} | VAR '=' expr {$$ = mem[$1] = $3;} ... ...
对于hoc.y改动也不是很大,增加了一个用于存储变量的值的数组mem,这个数组的大小跟英文中的字母数目一样,从规则expr的改动可以看出,当你在给一个变量赋值后,可以通过变量名来引用这个变量的值,比如,你先设置一个变量x = 5,在接下来的某个地方使用x,你会得到一个输出5,当然,这两个语句之间要确保x没有被修改过。
- 错误恢复
当你的程序在执行过程中,你可能不太希望一出错马上就退出,可能想要让系统从错误中恢复过来,继续下边的语句,这虽然不一定是必须的,但是,在这里可能是有用的。
#include <setjmp.h> jmp_buf begin; int main(int argc,char **argv) { int fpecatch(); progname = argv[0]; setjmp(begin); signal(SIGFPE,fpecatch);//注册回调函数,当发生FPE时,调用fpecatch() yyparse();//调用分析程序 } fpecatch()//Floating point exception { warning("floating point exception",(char *)0); } yyerror(char *s) { warning(s,(char *)0); longjmp(begin,0);//跳转回begin初始化的地方 }
现在main中初始化一个jmp_buf型的变量begin,然后设置信号setjmp(begin),然后调用yyparse(),当错误发生 时,如除零错误,yacc会调用yyerror()来处理,这时,在yyerror内部,可以调用一个系统调用longjmp(begin, 0),即可恢复到begin被初始化的地方,即main函数中,yyparse()之前的位置。
关于C语言中,这个jmp_buf, setjmp(jmp_buf b)和longjmp(jmp_buf buf, int code)的具体使用,可以参考别的C语言手册。
- 与C整合,调用外部的C函数
lex/yacc真正强大之处在于他们和C语言的结合能力上。它们可以自由的使用外部的C语言定义好的函数。事实上,由于lex/yacc只是一种 中间结果,它们最终还是要生成C代码的,所以使用外部的C语言是没有任何问题的。我们现在可以给hoc添加幂函数的处理,对幂函数的实现我们可以使用外部 的C语言的math库。
hoc.y
... ... extern double POW(double ,double); ... ... %right '^'//幂函数的操作符是自右到左结合的 ... ... expr : ... ... | expr '^' expr {$$ = POW($1,$3);}//调用外部的POW函数 ... ...
math.c
#include <stdio.h> #include <math.h> double POW(double x,double y)//当然,也可以在内部调用math.pow,但是这里要说明的是使用外部的C代码 { return pow(x,y); }
我们可以进行一些简单的测试,现在我们可以把第二个版本的hoc的完整代码给出来:
lex.l
%{ #include "y.tab.h" extern YYSTYPE yylval; extern int lineno; %} %% [ \t]+ {;} [0-9]+|[0-9]*\.[0-9]+ { sscanf(yytext,"%lf",&yylval.val); return NUMBER; } [a-z] { yylval.index = yytext[0] - 'a'; return VAR; } \n {lineno++;return '\n';} . {return yytext[0];} %%
lex.y
%{ #include <stdio.h> #include <stdlib.h> char *progname; int lineno = 1; double mem[26]; extern double POW(double ,double); %} %union{ double val; int index; } %token <val> NUMBER %token <index> VAR %type <val> expr %right '=' %left '+' '-' %left '*' '/' %left UNARYMINUS %right '^' %% list : | list '\n' | list expr '\n' {printf("\t%.8g\n",$2);} | list error '\n' {yyerrok;} ; expr : NUMBER | VAR {$$ = mem[$1];} | VAR '=' expr {$$ = mem[$1] = $3;} | '-' expr %prec UNARYMINUS {$$ = -$2;} | expr '+' expr {$$ = $1 + $3;} | expr '-' expr {$$ = $1 - $3;} | expr '*' expr {$$ = $1 * $3;} | expr '/' expr {if($3 == 0.0) yyerror("devide zero error\n"); $$ = $1 / $3;} | expr '^' expr {$$ = POW($1,$3);} | '(' expr ')' {$$ = $2;} ; %% #include <signal.h> #include <setjmp.h> jmp_buf begin; int main(int argc,char **argv) { int fpecatch(); progname = argv[0]; setjmp(begin); signal(SIGFPE,fpecatch); yyparse(); } fpecatch()//Floating point exception { warning("floating point exception",(char *)0); } yyerror(char *s) { warning(s,(char *)0); longjmp(begin,0); } yywrap() { return 1; } warning(char *s,char *t) { fprintf(stderr,"%s : %s",progname,s); if(t) fprintf(stderr," %s",t); fprintf(stderr," near line %d\n",lineno); }
math.c
#include <stdio.h> #include <math.h> double POW(double x,double y) { return pow(x,y); }
makefile
hoc: y.tab.o lex.yy.o maths.o gcc y.tab.o lex.yy.o maths.o -o hoc -lm y.tab.o:y.tab.c gcc -c y.tab.c y.tab.c:hoc.y yacc -d hoc.y lex.yy.o:lex.yy.c gcc -c lex.yy.c lex.yy.c:hoc.l lex hoc.l maths.o:maths.c gcc -c maths.c clean: rm -f y.tab.[cho] rm -f lex.yy.[cho] rm -f maths.o
make成功以后,就可以测试一下,对变量的支持,和错误的恢复,以及对幂函数的支持。现在离我们的目标还有多远呢?我觉得已经比较接近了,但是, 我们现在还需要支持更多的外部函数,如计算正弦余弦函数,计算对数函数,开方,幂函数等等。还有,像很多个数学引擎一样,我们应该考虑内建一些常量,如 PI,E等。当然,除了我们第二个版本的半成品,再没有一个语言的变量会规定为一个字母,因此,我们需要对这些方面进行一些改造。
这一次就先写这些,我对高版本的HOC再做一些注释,然后再写一些解释很分析出来。
- hoc4.zip (15.4 KB)
- 下载次数: 123
相关推荐
NS2是一个面向对象的Tcl(OTcl)语言脚本解释器,它有一个事件调度器、一个网络组件库。事件调度器跟踪仿真的时间并且根据预定时间安排队列中的事件,激活当前时间对应的处理该事件的网络对象。事件调度器维护一个排序...
然后,通过OTcl解释器运行脚本,启动模拟器。在模拟过程中,NS2会根据脚本中的设置执行相应的网络行为,并记录下关键事件和数据。最后,可以用NAM来查看模拟过程的可视化结果,或者分析模拟生成的日志文件,获取更...
#### 四、仿真结果与分析 在添加了ABR协议之后,研究人员进行了节点间数据传输率的测试,以评估ABR协议在NS2中的性能表现。实验结果表明,使用拓展后的NS2进行ABR协议的网络仿真能够有效地反映该协议的实际效果,并...
此文档详细介绍了如何在SecureCRT中使用VBScript进行自动化任务处理,覆盖了从创建到执行脚本的全过程,并深入探讨了与远程机器连接、读取和发送数据、获取终端用户信息以及日志记录和文件操作等方面的知识点。...
4. **tcl8.5.9**:TCL解释器,用于运行otcl脚本。 5. **xgraph**:图形化数据展示工具,用于可视化模拟结果。 6. **ns nam**:Network Animation and Movie Tool,用于将模拟过程转换为动画或静态图像,便于分析和...
- ZK 支持多作用域解释器,这意味着可以在不同的作用域中执行 zscript 代码。 - 这有助于更好地管理代码和资源。 - **单一作用域解释器:** - 单一作用域解释器是指所有 zscript 代码都在同一个作用域中执行。 ...
可能包含的文件有网络配置文件、路由协议实现、事件调度器、以及用于数据分析和结果可视化的脚本。 通过分析这些源码,研究者和开发者可以了解如何在NS2中集成GPSR协议以支持VANETs中的V2V通信,评估其性能,如...
- **包状态与Java会话状态**: 讨论了与包和Java会话相关的状态管理。 - **查看结果集**: 展示了如何观察查询的结果。 - **DBMS_OUTPUT查看**: 如何查看DBMS_OUTPUT缓冲区中的信息。 - **HTP输出查看**: 查看HTTP...
传感器节点负责收集环境数据,执行器则根据指令执行操作,而网关则将6LoWPAN网络与更广阔的IPv6互联网连接起来。网络中的节点可以自组织形成Ad Hoc网络,使用路由协议如RPL(Routing Protocol for Low-Power and ...
4. **NS2命令与对象**:列出并解释常用的NS2命令和对象,如`$ns`、`$node`、`$tcp`等,以及如何使用它们来控制网络行为。 5. **协议仿真**:可能包括TCP/IP协议栈的各个层次,如物理层、数据链路层、网络层、传输层...
- **作业定义编辑器**:解释如何使用作业定义编辑器来创建和修改作业。 - **队列定义编辑器**:介绍如何创建和修改队列对象。 - **队列表定义编辑器**:教授如何管理队列表对象。 - **用户定义编辑器**:介绍如何...
Click 是一个用于构建可编程路由器的平台,NS-3 可以与之集成以实现更灵活的网络仿真。 ##### 模型描述 (Model Description) 模型描述详细介绍了如何在 NS-3 中集成 Click 模块路由器,包括安装步骤、配置方法以及...
#### 详细解释与示例: ##### 1. 使用 OPENROWSET 方法将 SQL Server 数据导出至 Excel **背景介绍:** 当需要将 SQL Server 数据库中的数据导出至已存在的 Excel 文件时,并且该文件已经按照所需的格式创建好了...
它支持多层协议仿真,包括物理层、数据链路层、网络层以及应用层,这使得GloMoSim能够处理各种复杂的网络场景,如蜂窝网络、Ad Hoc网络、传感器网络等。 在GloMoSim中,网络实体(如节点、基站、通信信道)的交互...
- **任务调度与控制**:介绍了任务调度的概念以及如何在 TRUETIME 中实现任务的调度和控制。 - **分布式控制系统**:演示了如何使用 TRUETIME 构建一个简单的分布式控制系统。 - **截止期超时处理**:解释了如何处理...
聚合器部分则详细说明了如何将来自多个收集器的数据进行合并和处理,以支持更高级的数据分析需求。 ##### 11.6 适配器 Adaptors 适配器部分则介绍了如何使用适配器来调整数据格式,以便于不同的数据分析工具能够...
3. **应用层-流量产生器.txt**:这部分可能讨论了如何在ns-2中创建和配置不同的应用层流量源,如CBR(Continuous Bit Rate)、TCP、UDP等,这些都是网络模拟中的重要元素。 4. **gnuplot使用.txt**:Gnuplot是一款...
- **高效的仿真架构**:为了提高仿真效率,事件调度器和数据通道的基本网络组件对象使用C++编写,这些对象通过TclCL映射对OTcl解释器可见。这种方式既保证了高效的数据处理,又提供了灵活的仿真配置接口。 #### ...