Now in Baidu WISE team
全部博文（150）
分类： C/C++
2013-01-27 16:12:33
（作者码字辛苦，转载请以超链接形式注明出处）
最近在学习编译原理，于是准备自己动手写一个脚本语言。准备用一些文章记录其中遇到的问题和解决的方法。这些文章需要有一些编译原理，YACC, LEX的储备知识。关于这些知识，使用方面的部分可以简单的通过网络上的文章得到,更详细的原理，需要参考《编译原理》(龙书）。当然，后者不是必须的。推荐以下几个Link，可以获得一些基础的知识。
YACC和LEX快速入门：http://www.ibm.com/developerworks/cn/linux/sdk/lex
Lex和Yacc应用方法(二).再识Lex与Yacc http://blog.csdn.net/liwei_cmg/article/details/1530999
lex与yacc(二)计算器的实现 http://blog.csdn.net/ecbtnrt/article/details/6817937
Lex和Yacc使用教程(五).再识语法树 http://blog.csdn.net/liwei_cmg/article/details/1626129
对于一个简单的赋值语句 i = 1; 目标是i,操作符是'=',操作对象为 '1'。 在(i)和（1）之间执行（赋值）操作，并返回（空）
对于一个直接的调用callFunc()，我们可以认为他没有目标和操作符，只有对象callFunc,也可以认为是 var = callFunc();,但是var并没有用，被丢弃了。
对于一个复杂的复制语句 i = 1 + 2， 我们可以划分成一个3层的树形结构,见下面的示意图。我们执行的时候，就是递归的调用， 对于 1+2，计算出1+2的值，返回给上一层,然后这个临时变量赋给expr,再执行赋值i=expr,完成。
每个节点，每种操作都有相应的返回值和，对于加法，返回的就是表达式的值，对于赋值，语句，无需返回，也可以认为返回为NULL。如何返回，由操作符来定义
题外话，所以Lisp可以用无限的括号表示所有的计算，就是这个道理。这个赋值语句，可以用LISP表达为： （= i （+ 1 2））
返回 : NULL
目标：i
操作符： ‘=’
操作对象： ------------------》 返回： calculate result
目标： 1
操作符： +
操作对象： -----------------》返回：intValue
目标： 2
操作符： NONE
操作对象： NULL
所以有如下的结构定义：
typedef enum {NONE, Assign, Add} opEnum;
typedef struct {
char* varName; //如果是目标是变量，我们用varName表示
int intValue; //如果是目标是值，我们用intValue表示
Node* child; //操作对象
opEnum op; //操作符，假设我们只支持‘=’和+
int ret;
}Node
定义了3种操作：
NONE:直接返回int,
Assign:赋值，返回0xffff
Add:加法，返回计算结果
这里 intValue和varName可以用Union来写. 因为我们赋值语句可能为i = 1+2， 也有可能i = 1+a
假设没有返回值的时候，ret为0xFFFF(仅为方便）
typedef enum {NONE, Assign, Add} opEnum; 我们用一个数组int VARLIST[65536],来存储所有变量（假定都为int,且每个变量名都可以通过getHash计算唯一的在VARLIST中的下标)
这样我们可以定义对于一个结点的值，可以由如下递归方法计算:
int calNode(Node* node){
if( node->op == Assign){
//update the variable
VARLIST[ getHash(node->varName) ] = calNode(node->child);
return 0xFFFF;
}
if( node->op == Add){
if(charName!=NULL) //如果是变量的加法，如 a+2
return VARLIST[getHash(node->varName)] + calNode(node->child);
else //如果是直接可计算出的表达式 如 1+2
return node->intValue+ calNode;
}
if( node->op == None)
return node->intValue;
}
其实，这本质上又回归到了LISP的表达式，通过递归的方式计算出一个语句的值。这是一种通用描述，对于每种语句，其实最终都可以通过以上的形式的方式计算，各种循环和判断无一例外。 也因此，LISP可以用极简的方式表达出现代高级编程语言各种复杂的语法。
2.怎样存储的函数的定义？
我们可以定一个全局的哈希表，key为函数的名字，value为Node*, 这样我们就可以将每一个函数存储在我们表中。
这里，我们简化情况，只定义一个Node*，也就是假设我们只有一个函数。
3.怎样调用函数？
由于我们已经存储了函数的定义，所以调用时，只需要从方法列表中，找出这个函数的item,利用calNode就可以执行这个节点代表的语句序列了
以上我们实际已经处理了要自己实现一个语言中的基础性结构，在这种逻辑的基础上增加完成度和优化，最终应该可以完成一个基本完整的解释器。
Sample Code：
将下面的6个文件放入文件夹中，然后执行shell文件refresh.
这个例子仅为示例，所以只完成了最简单的逻辑。未实现变量哈希表，函数哈希表。仅用一个函数指针记录唯一的一个函数。仅示意了赋值语句的执行。因为并没有记录变量表，也只是输出到屏幕，表示该函数被执行了。
调用函数时使用关键字 run
ryt.l
%{
#include "y.tab.c"
#include
#include
void debugmsg(char* msg);
%}
delim [ \\t\\n]
ws {delim}+
letter [A-Za-z]
digit [0-9]
assign =
id {letter}({letter}|{digit})*
strvalue \\"({letter}|{digit})*\\"
end ;
number {digit}+
fun fun
%%
{ws} {}
"run" { debugmsg("RUN"); return RUN;}
"fun" { debugmsg("FUN"); return FUN;}
{id} { yylval.str = strdup(yytext); debugmsg(yytext); return symbol; }
{assign} { return ASSIGN; }
{end} { return SEMC;}
{number} { yylval.value = atoi(yytext); debugmsg(yytext); return expr;}
"{" { return BLOCKSTART;}
"}" { return BLOCKEND;}
%%
int yywrap()
{
return 1;
}
void debugmsg(char* msg){
if(DEBUG & LEXDEBUG)
printf("[LEX] %s\\n", msg);
}
ryt.y
%{
#include
#include
#include
#include "utility.h"
Node* fun;
Node* installSymbolAssign(char* id, int exp);
Node* installFun(char* id, Node* body);
void execute();
void yyerror(char*s);
void* cur = NULL;
char* curFun;
%}
%union {
char* str;
int value;
Node *node; /* 结点地址 */
}
%token ASSIGN SEMC FUN BLOCKSTART BLOCKEND RUN
%token symbol
%token expr
%type stmtlist stmt
%%
prog : fundefs RUN SEMC { execute();}
;
fundefs : fundefs fundef
| fundef
;
fundef : FUN symbol BLOCKSTART stmtlist BLOCKEND {printf("fundef: %s \\n", $2);
installFun($2, $4);
}
;
stmtlist : stmtlist stmt {printf("!!!!!!!statement\\n");}
| stmt {}
;
stmt : symbol ASSIGN expr SEMC {printf("add stmt: ASSIGN %s \\n", $1);
$$ = installSymbolAssign($1,$3);
}
;
%%
Node* installSymbolAssign(char* id, int exp){
printf("install symbol assign --- %s %d\\n", id, exp);
Node* ret = (Node*)malloc(sizeof(Node));
ret->varName = id;
ret->op = AssignOp;
ret->intValue = exp;
return ret;
}
Node* installFun(char* id, Node* body){
printf("install function %s: %p\\n", id, body);
fun = body;
}
void execute(){
printf("Executing function %p \\n", fun);
ex(fun);
}
int main(){
yyparse();
return 0;
}
void yyerror(char *s) {
fprintf(stdout, "%s\\n", s);
}
utility.h
/*
* =====================================================================================
*
* Filename: utility.h
*
* Description:
*
* Version: 1.0
* Created: 01/26/2013 12:26:49 AM
* Revision: none
* Compiler: gcc
*
* Author: royn.wang.renyuan@gmail.com (),
* Organization:
*
* =====================================================================================
*/
#define LEXDEBUG 1
#define YACCDEBUG 2
typedef enum {NONE, AssignOp, AddOp} opEnum;
typedef struct _exUnit{
char* varName;
int intValue;
opEnum op;
struct _exUnit* next;
int ret;
} Node;
int VarList[256];
int DEBUG;
int ex(Node* node);
utility.c
/* * ===================================================================================== * * Filename: utility.c * * Description: * * Version: 1.0 * Created: 01/26/2013 01:58:35 AM * Revision: none * Compiler: gcc * * Author: royn.wang.renyuan@gmail.com (), * Organization: * * ===================================================================================== */ #include#include #include "utility.h" int DEBUG = 3; int ex(Node* node){ printf("[3] Calculating "); if(node->op == AssignOp){ printf("ASSIGN "); printf("SYMBOL::%s value:: %d\\n",node->varName, node->intValue); return 0xFFFF; } if(node->op == AddOp){ return node->intValue + ex(node); } if(node->next != NULL) ex(node->next); }
refresh