//=========================================================================
typedef struct varTree{
int Elementkey;
int varValue;
char varName[20];
struct varTree* left;
struct varTree* right;
}varTreeNode_t;
varTreeNode_t * My_varTree = NULL;
varTreeNode_t* Insert(int varValue,char *varName,int X,varTreeNode_t* Tree){
if(Tree == NULL){
//create and return a one node tree
Tree = malloc(sizeof(struct varTree));
if(Tree == NULL){
printf("Out of space!!!!");
}else{
Tree->varValue = varValue;
strcpy(Tree->varName,varName);
Tree->Elementkey = X;
Tree->left = Tree->right = NULL;
}
}else if(X < Tree->Elementkey){
Tree->left = Insert(varValue,varName,X,Tree->left);
}else if(X > Tree->Elementkey){
Tree->right = Insert(varValue,varName,X,Tree->right);
}else{
//else X is in the tree already,we'll do nothing
}
return Tree;
}
varTreeNode_t* Find(char* varName,varTreeNode_t* Tree){
int X = 0,i;
if(Tree == NULL){
return NULL;
}
for(i = 0; i < 20; i++){
X = X + varName[i];
if(varName[i] == '\0'){
break;
}
}
if( X < Tree->Elementkey){
return Find(varName,Tree -> left);
}else if( X > Tree->Elementkey){
return Find(varName,Tree -> right);
}else{
return Tree;
}
}
SimpleASTNode_t* assignmentStatement(Save_Token_t* tokens){//赋值语句a=1+3+b+5;
SimpleASTNode_t* node = NULL;
SimpleASTNode_t* child = NULL;
Save_Token_t* token;
token = tokens_fun.peek();//预读
if((token != NULL) && (token->type == Id)){
token = tokens_fun.read();//消耗掉Id
node = new_SimpleASTNode_2(AssignmentStmt,token->text);
token = tokens_fun.peek();//预读
if((token != NULL) && (token->type == Assignment)){
token = tokens_fun.read();//消耗掉Assignment
child = additive(tokens);
if(child == NULL){//出错，等号右面没有一个合法的表达式
printf("invalide assignment statement, expecting an expression");
}else{
Node_add_child(node,child);
token = tokens_fun.peek();//预读
if((token != NULL) && (token->type == SemiColon)){
token = tokens_fun.read();//消耗掉;
}else{//报错，缺少分号
printf("invalid statement, expecting semicolon");
}
}
}else{
tokens_fun.unread();
node = NULL;
}
}
return node;
}
SimpleASTNode_t* intDeclarationStatement(Save_Token_t* tokens){//变量声明语句 char a = 5+3*6;
SimpleASTNode_t* node = NULL;
SimpleASTNode_t* child = NULL;
Save_Token_t* token;
int pos = tokens_fun.getPosition();//记下初始位置
token = tokens_fun.peek();//预读
if((token != NULL) && ((token->type == CHAR)||(token->type == INT))){
token = tokens_fun.read();//消耗掉int char
child = assignmentStatement(tokens);
if(child == NULL){
tokens_fun.unread();
node = NULL;
}else{
node = new_SimpleASTNode_2(IntDeclaration,token->text);
Node_add_child(node,child);
}
}
return node;
}
SimpleASTNode_t* expressionStatement(Save_Token_t* tokens){//表达式语句 a+b+3;
SimpleASTNode_t* node = NULL;
Save_Token_t* token;
int pos = tokens_fun.getPosition();//记下初始位置
#if DEBUG
printf("----enter fun = expressionStatement()\r\n");
#endif
node = additive(tokens);//匹配加法规则
if(node != NULL){
token = tokens_fun.peek();//预读
if((token != NULL) && (token->type == SemiColon)){
token = tokens_fun.read();//消耗掉;
}else{
node = NULL;
tokens_fun.setPosition(pos);
}
}
return node;
}
//遍历AST，计算值。
int evaluate(SimpleASTNode_t* node,int tab_num){
int X = 0,i;
int result = 0,varValue;
int value1;
int value2;
char *varName;
SimpleASTNode_t* child;
SimpleASTNode_t* child1;
SimpleASTNode_t* child2;
varTreeNode_t* varnode;
switch(node->type){
//case CharDeclaration:
//case IntDeclaration:
//child = node->left;
//result = evaluate(child,tab_num+1);
//break;
case AdditiveExp:
child1 = node->left;
value1 = evaluate(child1,tab_num+1);
child2 = node->right;
value2 = evaluate(child2,tab_num+1);
if(strcmp(node->text,"+") == 0){
result = value1 + value2;
}else{
result = value1 - value2;
}
break;
case MulticativeExp:
child1 = node->left;
value1 = evaluate(child1,tab_num+1);
child2 = node->right;
value2 = evaluate(child2,tab_num+1);
if(strcmp(node->text,"*") == 0){
result = value1 * value2;
}else{
result = value1 / value2;
}
break;
case Ast_IntLiteral:
result = atoi(node->text);
break;
case Ast_Identifier:
varName = node->text;//=====================
varnode = Find(varName,My_varTree);
if(varnode != NULL){
result = varnode->varValue;
}else{
printf("variable %s has not been set any value",varName);
}
break;
case AssignmentStmt:
varName = node->text;
child = node->left;
result = evaluate(child,tab_num+1);
varValue = result;
for(i = 0; i < 20; i++){
X = X + varName[i];
if(varName[i] == '\0'){
break;
}
}
varnode = Find(varName,My_varTree);
if(varnode == NULL){
Insert(varValue,varName,X,My_varTree);
}else{
varnode->varValue = varValue;
}
break;
case CharDeclaration:
case IntDeclaration:
varName = node->text;
child = node->left;
result = evaluate(child,tab_num+1);
varValue = result;
for(i = 0; i < 20; i++){
X = X + varName[i];
if(varName[i] == '\0'){
break;
}
}
varnode = Find(varName,My_varTree);
if(varnode == NULL){
Insert(varValue,varName,X,My_varTree);
}else{
varnode->varValue = varValue;
}
//====================================
break;
default :
break;
}
for(int i = 0; i < tab_num;i++){
//printf(" ");
}
//printf("Result: %d\r\n",result);
return result;
}
int syntactic_parser(Save_Token_t* tokens){
int result = 0;
SimpleASTNode_t* AstTree = NULL;
static enum syntactic_parser_types s_type = CharDeclaration;
switch(s_type){
case CharDeclaration: //char a = 1
AstTree = intDeclarationStatement(tokens);//变量声明语句 char a = 5+3*6;
if(AstTree != NULL){
result = evaluate(AstTree,0);
break;
}
case AssignmentStmt:
AstTree = assignmentStatement(tokens);//赋值语句a=1+3+b+5;
if(AstTree != NULL){
result = evaluate(AstTree,0);
break;
}
case AdditiveExp:
AstTree = expressionStatement(tokens);//表达式语句 a+b+3;
if(AstTree != NULL){
result = evaluate(AstTree,0);
break;
}
default:
result = 0;
break;
}
return result;
}
void tokens_fun_init(){
tokens_fun.peek = token_peek;
tokens_fun.read = token_read;
tokens_fun.unread = token_unread;
tokens_fun.getPosition = token_getPosition;
tokens_fun.setPosition = token_setPosition;
}
//my_tokens[100]
int main(){
int i ,result;
Save_Token_t* tokens;
tokens_fun_init();
My_varTree = Insert(0,"calute",100,NULL);
while(1){
printf("Repl> ",my_tokens);
for(i = 0; i < 100; i++){
my_tokens[i] = 0;
}
gets(my_tokens);
//printf("======%s\r\n",my_tokens);
if((strcmp(my_tokens,"exit();") == 0) || (strcmp(my_tokens,"exit") == 0) || (strcmp(my_tokens,"exit;") == 0)){
printf(">>>>goodbye!!!\r\n");
break;
}
set_Token_Index(0);
Lexical_analyzer();
//printf("============syntactic_parser===============\r\n");
result = syntactic_parser(tokens);
printf(" = %d\r\n",result);
set_save_token_index(0);
token_setPosition(0);
}
}