From 7cdcc9ee93757f8406094373d3faddaf62849e52 Mon Sep 17 00:00:00 2001 From: David Walter Seikel Date: Sat, 7 Jan 2012 01:18:11 +1000 Subject: Convert the parser from dealing with just expressions, to dealing with the entire AST. --- LICENCES | 5 + LuaSL/README | 6 +- LuaSL/src/LuaSL_LSL_tree.c | 306 +++++++++++++++++++++++++-------------------- LuaSL/src/LuaSL_LSL_tree.h | 163 ++++++++++-------------- LuaSL/src/LuaSL_yaccer.y | 2 +- 5 files changed, 245 insertions(+), 237 deletions(-) diff --git a/LICENCES b/LICENCES index 02e4c04..794ac5d 100644 --- a/LICENCES +++ b/LICENCES @@ -59,11 +59,16 @@ This is covered by "Creative Commons Attribution-ShareAlike 3.0 Unported License". The attribution portion is covered by the URL above, as per the Wikipedia Terms of Use. +There is no longer any parts of that code left I think. + -------------------------------------------------------------------------------- The flex and bison source files for the LSL parser are from the SL viewer under GPL 2 and copyright at some unknown date (due to missing copyright notice in those specific files) by Linden Research, Inc. +It's likely this will go away, as I'm writing my own, and most of it was +useless to me anyway. + -------------------------------------------------------------------------------- diff --git a/LuaSL/README b/LuaSL/README index b8edefc..c02b180 100644 --- a/LuaSL/README +++ b/LuaSL/README @@ -78,6 +78,6 @@ useful extras. btyacc version 3 (the version coming from my version of Ubuntu) apparently no longer supports C, only C++. It's written in C though. -Let's see if flex and btyacc will do the trick, and output C. - -Might be best to have the LSL to Lua converter as a seperate executable. +Let's see if flex and btyacc will do the trick, and output C. Might be +best to have the LSL to Lua converter as a seperate executable. Think +I'll end up writing my own parser. diff --git a/LuaSL/src/LuaSL_LSL_tree.c b/LuaSL/src/LuaSL_LSL_tree.c index 88768e0..8462112 100644 --- a/LuaSL/src/LuaSL_LSL_tree.c +++ b/LuaSL/src/LuaSL_LSL_tree.c @@ -1,7 +1,3 @@ -/* - * Implementation of functions used to build the abstract syntax tree. - */ - #define LSL_Keywords_define #define LSL_Tokens_define @@ -10,35 +6,38 @@ #include -/** - * @brief Allocates space for an AST leaf - * @return The expression or NULL if not enough memory - */ - -/* -static LSL_AST *newLeaf(LSL_Type type, LSL_AST *left, LSL_AST *right) +static LSL_AST *newAST(LSL_Type type, LSL_AST *left, LSL_AST *right) { - LSL_AST *leaf = malloc(sizeof(LSL_AST)); + LSL_AST *ast = malloc(sizeof(LSL_AST)); + + if (ast == NULL) return NULL; - if (leaf == NULL) return NULL; + ast->type = type; + ast->left = left; + ast->right = right; + ast->line = -1; + ast->character = -1; - leaf->type = type; - leaf->left = left; - leaf->right = right; - leaf->line = -1; - leaf->character = -1; + return ast; +} + +void burnAST(LSL_AST *ast) +{ + if (ast == NULL) return; - return leaf; + burnAST(ast->left); + burnAST(ast->right); + free(ast); } -*/ -void burnLeaf(LSL_AST *leaf) +LSL_AST *addExpression(LSL_Expression *exp) { - if (leaf == NULL) return; + LSL_AST *ast = newAST(LSL_EXPRESSION, NULL, NULL); - burnLeaf(leaf->left); - burnLeaf(leaf->right); - free(leaf); + if (ast) + ast->content.expressionValue = exp; + + return ast; } static LSL_Expression *newLSLExpression(LSL_Type type, LSL_Expression *left, LSL_Expression *right) @@ -50,7 +49,6 @@ static LSL_Expression *newLSLExpression(LSL_Type type, LSL_Expression *left, LSL exp->type = type; exp->left = left; exp->right = right; - exp->expression=0; return exp; } @@ -69,7 +67,7 @@ LSL_Expression *addInteger(int value) LSL_Expression *exp = newLSLExpression(LSL_INTEGER, NULL, NULL); if (exp) - exp->value.integerValue = value; + exp->content.integerValue = value; return exp; } @@ -79,41 +77,96 @@ LSL_Expression *addOperation(LSL_Operation type, LSL_Expression *left, LSL_Expre LSL_Expression *exp = newLSLExpression(LSL_EXPRESSION, left, right); if (exp) - exp->expression = type; + exp->content.operationValue = type; return exp; } -LSL_Expression *newTree(const char *expr) +int evaluateExpression(LSL_Expression *exp, int old) { - LuaSL_yyparseParam param; - YY_BUFFER_STATE state; - + if (NULL == exp) + return old; #ifdef LUASL_DEBUG - yydebug= 5; + #ifdef LUASL_USE_ENUM + printf(" %s ", LSL_Tokens[exp->content.operationValue - LSL_COMMA].token); + #else + printf(" # "); + #endif #endif - param.expression = NULL; - if (yylex_init(&(param.scanner))) - return NULL; - + if (LSL_INTEGER == exp->type) + { #ifdef LUASL_DEBUG - yyset_debug(1, param.scanner); + printf("%d", exp->content.integerValue); #endif + return exp->content.integerValue; + } - state = yy_scan_string(expr, param.scanner); - if (yyparse(¶m)) - return NULL; - - yy_delete_buffer(state, param.scanner); - yylex_destroy(param.scanner); + switch (exp->content.operationValue) + { +#ifdef LUASL_USE_ENUM + case LSL_COMMA : + case LSL_INCREMENT_PRE : + case LSL_INCREMENT_POST : + case LSL_DECREMENT_PRE : + case LSL_DECREMENT_POST : + case LSL_DOT : + case LSL_ASSIGNMENT_PLAIN : + case LSL_ASSIGNMENT_DIVIDE : + case LSL_ASSIGNMENT_MODULO : + case LSL_ASSIGNMENT_MULTIPLY : + case LSL_ASSIGNMENT_SUBTRACT : + case LSL_ASSIGNMENT_ADD : + case LSL_ASSIGNMENT_CONCATENATE : + case LSL_PARENTHESIS_OPEN : + case LSL_PARENTHESIS_CLOSE : + case LSL_BRACKET_OPEN : + case LSL_BRACKET_CLOSE : + case LSL_ANGLE_OPEN : + case LSL_ANGLE_CLOSE : + case LSL_TYPECAST : + break; +#endif + case LSL_BIT_NOT : return ~ evaluateExpression(exp->right, old); + case LSL_BOOL_NOT : return ! evaluateExpression(exp->right, old); + case LSL_NEGATION : return 0 - evaluateExpression(exp->right, old); + case LSL_DIVIDE : return evaluateExpression(exp->left, old) / evaluateExpression(exp->right, old); +#ifdef LUASL_USE_ENUM + case LSL_MODULO : return evaluateExpression(exp->left, old) % evaluateExpression(exp->right, old); +#endif + case LSL_MULTIPLY : return evaluateExpression(exp->left, old) * evaluateExpression(exp->right, old); +#ifdef LUASL_USE_ENUM + case LSL_DOT_PRODUCT : break; + case LSL_CROSS_PRODUCT : break; +#endif + case LSL_SUBTRACT : return evaluateExpression(exp->left, old) - evaluateExpression(exp->right, old); + case LSL_ADD : return evaluateExpression(exp->left, old) + evaluateExpression(exp->right, old); +#ifdef LUASL_USE_ENUM + case LSL_CONCATENATE : break; +#endif + case LSL_LEFT_SHIFT : return evaluateExpression(exp->left, old) << evaluateExpression(exp->right, old); + case LSL_RIGHT_SHIFT : return evaluateExpression(exp->left, old) >> evaluateExpression(exp->right, old); + case LSL_LESS_THAN : return evaluateExpression(exp->left, old) < evaluateExpression(exp->right, old); + case LSL_GREATER_THAN : return evaluateExpression(exp->left, old) > evaluateExpression(exp->right, old); + case LSL_LESS_EQUAL : return evaluateExpression(exp->left, old) <= evaluateExpression(exp->right, old); + case LSL_GREATER_EQUAL : return evaluateExpression(exp->left, old) >= evaluateExpression(exp->right, old); + case LSL_EQUAL : return evaluateExpression(exp->left, old) == evaluateExpression(exp->right, old); + case LSL_NOT_EQUAL : return evaluateExpression(exp->left, old) != evaluateExpression(exp->right, old); + case LSL_BIT_AND : return evaluateExpression(exp->left, old) & evaluateExpression(exp->right, old); + case LSL_BIT_XOR : return evaluateExpression(exp->left, old) ^ evaluateExpression(exp->right, old); + case LSL_BIT_OR : return evaluateExpression(exp->left, old) | evaluateExpression(exp->right, old); + case LSL_BOOL_OR : return evaluateExpression(exp->left, old) || evaluateExpression(exp->right, old); + case LSL_BOOL_AND : return evaluateExpression(exp->left, old) && evaluateExpression(exp->right, old); + } - return param.expression; + return old; } -int evaluateExpression(LSL_Expression *exp, int old) +int evaluateAST(LSL_AST *ast, int old) { - switch(exp->type) + if (NULL == ast) + return old; + switch(ast->type) { #ifdef LUASL_USE_ENUM case LSL_COMMENT : @@ -121,13 +174,13 @@ int evaluateExpression(LSL_Expression *exp, int old) case LSL_NAME : case LSL_IDENTIFIER : break; - case LSL_FLOAT : return (int) exp->value.floatValue; + case LSL_FLOAT : return (int) ast->content.floatValue; #endif case LSL_INTEGER : #ifdef LUASL_DEBUG - printf("%d", exp->value.integerValue); + printf("%d", ast->content.integerValue); #endif - return exp->value.integerValue; + return ast->content.integerValue; #ifdef LUASL_USE_ENUM case LSL_STRING : case LSL_KEY : @@ -137,73 +190,7 @@ int evaluateExpression(LSL_Expression *exp, int old) case LSL_LABEL : break; #endif - case LSL_EXPRESSION : - { -#ifdef LUASL_DEBUG - #ifdef LUASL_USE_ENUM - printf(" %s ", LSL_Tokens[exp->expression - LSL_COMMA].token); - #else - printf(" # "); - #endif -#endif - switch (exp->expression) - { -#ifdef LUASL_USE_ENUM - case LSL_COMMA : - case LSL_INCREMENT_PRE : - case LSL_INCREMENT_POST : - case LSL_DECREMENT_PRE : - case LSL_DECREMENT_POST : - case LSL_DOT : - case LSL_ASSIGNMENT_PLAIN : - case LSL_ASSIGNMENT_DIVIDE : - case LSL_ASSIGNMENT_MODULO : - case LSL_ASSIGNMENT_MULTIPLY : - case LSL_ASSIGNMENT_SUBTRACT : - case LSL_ASSIGNMENT_ADD : - case LSL_ASSIGNMENT_CONCATENATE : - case LSL_PARENTHESIS_OPEN : - case LSL_PARENTHESIS_CLOSE : - case LSL_BRACKET_OPEN : - case LSL_BRACKET_CLOSE : - case LSL_ANGLE_OPEN : - case LSL_ANGLE_CLOSE : - case LSL_TYPECAST : - break; -#endif - case LSL_BIT_NOT : return ~ evaluateExpression(exp->right, old); - case LSL_BOOL_NOT : return ! evaluateExpression(exp->right, old); - case LSL_NEGATION : return 0 - evaluateExpression(exp->right, old); - case LSL_DIVIDE : return evaluateExpression(exp->left, old) / evaluateExpression(exp->right, old); -#ifdef LUASL_USE_ENUM - case LSL_MODULO : return evaluateExpression(exp->left, old) % evaluateExpression(exp->right, old); -#endif - case LSL_MULTIPLY : return evaluateExpression(exp->left, old) * evaluateExpression(exp->right, old); -#ifdef LUASL_USE_ENUM - case LSL_DOT_PRODUCT : break; - case LSL_CROSS_PRODUCT : break; -#endif - case LSL_SUBTRACT : return evaluateExpression(exp->left, old) - evaluateExpression(exp->right, old); - case LSL_ADD : return evaluateExpression(exp->left, old) + evaluateExpression(exp->right, old); -#ifdef LUASL_USE_ENUM - case LSL_CONCATENATE : break; -#endif - case LSL_LEFT_SHIFT : return evaluateExpression(exp->left, old) << evaluateExpression(exp->right, old); - case LSL_RIGHT_SHIFT : return evaluateExpression(exp->left, old) >> evaluateExpression(exp->right, old); - case LSL_LESS_THAN : return evaluateExpression(exp->left, old) < evaluateExpression(exp->right, old); - case LSL_GREATER_THAN : return evaluateExpression(exp->left, old) > evaluateExpression(exp->right, old); - case LSL_LESS_EQUAL : return evaluateExpression(exp->left, old) <= evaluateExpression(exp->right, old); - case LSL_GREATER_EQUAL : return evaluateExpression(exp->left, old) >= evaluateExpression(exp->right, old); - case LSL_EQUAL : return evaluateExpression(exp->left, old) == evaluateExpression(exp->right, old); - case LSL_NOT_EQUAL : return evaluateExpression(exp->left, old) != evaluateExpression(exp->right, old); - case LSL_BIT_AND : return evaluateExpression(exp->left, old) & evaluateExpression(exp->right, old); - case LSL_BIT_XOR : return evaluateExpression(exp->left, old) ^ evaluateExpression(exp->right, old); - case LSL_BIT_OR : return evaluateExpression(exp->left, old) | evaluateExpression(exp->right, old); - case LSL_BOOL_OR : return evaluateExpression(exp->left, old) || evaluateExpression(exp->right, old); - case LSL_BOOL_AND : return evaluateExpression(exp->left, old) && evaluateExpression(exp->right, old); - } - break; - } + case LSL_EXPRESSION : return evaluateExpression(ast->content.expressionValue, old); #ifdef LUASL_USE_ENUM case LSL_DO : case LSL_FOR : @@ -225,22 +212,42 @@ int evaluateExpression(LSL_Expression *exp, int old) } return old; - } void outputExpression(LSL_Expression *exp) { - switch(exp->type) + if (NULL == exp) + return; + + if (LSL_INTEGER == exp->type) + { + printf("%d", exp->content.integerValue); + } + else + { + outputExpression(exp->left); +#ifdef LUASL_USE_ENUM + printf(" %s ", LSL_Tokens[exp->content.operationValue - LSL_COMMA].token); +#else + printf(" # "); +#endif + outputExpression(exp->right); + } +} + +void outputAST(LSL_AST *ast) +{ + if (NULL == ast) + return; + switch(ast->type) { #ifdef LUASL_USE_ENUM case LSL_COMMENT : return; case LSL_TYPE : return; case LSL_NAME : return; case LSL_IDENTIFIER : return; - case LSL_FLOAT : printf("%f", exp->value.floatValue); break; -#endif - case LSL_INTEGER : printf("%d", exp->value.integerValue); break; -#ifdef LUASL_USE_ENUM + case LSL_FLOAT : printf("%f", ast->content.floatValue); break; + case LSL_INTEGER : printf("%d", ast->content.integerValue); break; case LSL_STRING : return; case LSL_KEY : return; case LSL_VECTOR : return; @@ -248,15 +255,7 @@ void outputExpression(LSL_Expression *exp) case LSL_LIST : return; case LSL_LABEL : return; #endif - case LSL_EXPRESSION : - outputExpression(exp->left); -#ifdef LUASL_USE_ENUM - printf(" %s ", LSL_Tokens[exp->expression - LSL_COMMA].token); -#else - printf(" # "); -#endif - outputExpression(exp->right); - break; + case LSL_EXPRESSION : outputExpression(ast->content.expressionValue); break; #ifdef LUASL_USE_ENUM case LSL_DO : return; case LSL_FOR : return; @@ -277,10 +276,12 @@ void outputExpression(LSL_Expression *exp) } } -void convertExpression2Lua(LSL_Expression *exp) +void convertAST2Lua(LSL_AST *ast) { #ifdef LUASL_USE_ENUM - switch(exp->type) + if (NULL == ast) + return; + switch(ast->type) { case LSL_COMMENT : return; case LSL_TYPE : return; @@ -320,22 +321,49 @@ int yyerror(const char *msg) return 0; } +LSL_AST *newTree(const char *expr) +{ + LuaSL_yyparseParam param; + YY_BUFFER_STATE state; + +#ifdef LUASL_DEBUG + yydebug= 5; +#endif + + param.ast = NULL; + if (yylex_init(&(param.scanner))) + return NULL; + +#ifdef LUASL_DEBUG + yyset_debug(1, param.scanner); +#endif + + state = yy_scan_string(expr, param.scanner); + if (yyparse(¶m)) + return NULL; + + yy_delete_buffer(state, param.scanner); + yylex_destroy(param.scanner); + + return param.ast; +} + int main(void) { const char test[] = " 4 + 2 * 10 + 3 * ( 5 + 1 )"; - LSL_Expression *exp; + LSL_AST *ast; - if ((exp = newTree(test))) + if ((ast = newTree(test))) { - int result = evaluateExpression(exp, 0); + int result = evaluateAST(ast, 0); #ifdef LUASL_DEBUG printf("\n"); #endif printf("Result of '%s' is %d\n", test, result); - outputExpression(exp); + outputAST(ast); printf("\n"); - burnLSLExpression(exp); + burnAST(ast); } return 0; diff --git a/LuaSL/src/LuaSL_LSL_tree.h b/LuaSL/src/LuaSL_LSL_tree.h index 271f4a8..a392474 100644 --- a/LuaSL/src/LuaSL_LSL_tree.h +++ b/LuaSL/src/LuaSL_LSL_tree.h @@ -1,6 +1,4 @@ -/* - * Definition of the structure used to build the abstract syntax tree. - */ + #ifndef __EXPRESSION_H__ #define __EXPRESSION_H__ @@ -215,110 +213,84 @@ char *LSL_Keywords[] = }; #endif -typedef union -{ - float floatValue; - int integerValue; - char *stringValue; - char *keyValue; - float vectorValue[3]; - float rotationValue[4]; - union LSL_Leaf *listValue; -} LSL_Value; - -typedef struct -{ - char *name; - LSL_Type type; - LSL_Value value; -} LSL_Identifier; - -typedef struct LSL_Expression -{ - struct LSL_Expression *left; - struct LSL_Expression *right; - LSL_Value value; - LSL_Operation expression; - LSL_Type type; -} LSL_Expression; - typedef struct { - LSL_Type type; - LSL_Expression *expressions; + LSL_Type type; + struct LSL_Expression *expressions; } LSL_Statement; typedef struct { - LSL_Statement *statements; + LSL_Statement *statements; } LSL_Block; typedef struct { - char *name; - LSL_Identifier *parameters; - LSL_Block block; - LSL_Type type; + char *name; + struct LSL_Identifier *parameters; + LSL_Block block; + LSL_Type type; } LSL_Function; typedef struct { - char *name; - LSL_Function *handlers; + char *name; + LSL_Function *handlers; } LSL_State; typedef struct { - char *name; - LSL_Identifier *variables; - LSL_Function *functions; - LSL_State *states; + char *name; + struct LSL_Identifier *variables; + LSL_Function *functions; + LSL_State *states; } LSL_Script; typedef union LSL_Leaf { - char *commentValue; - LSL_Type typeValue; - char *nameValue; - LSL_Identifier *identifierValue; - float floatValue; - int integerValue; - char *stringValue; - char *keyValue; - float vectorValue[3]; - float rotationValue[4]; - union LSL_Leaf *listValue; - char *labelValue; -// LSL_Operation expressionValue; - LSL_Expression *expressionValue; - LSL_Statement *doValue; - LSL_Statement *forValue; - LSL_Statement *ifValue; - LSL_Statement *elseValue; - LSL_Statement *elseIfValue; - char *jumpValue; - char *stateChangeValue; - LSL_Statement *statementValue; - LSL_Identifier *parameterValue; - LSL_Function *functionValue; - LSL_State *stateValue; - LSL_Script *scriptValue; -// class LLScriptType *type; -// class LLScriptConstant *constant; -// class LLScriptIdentifier *identifier; -// class LLScriptSimpleAssignable *assignable; -// class LLScriptGlobalVariable *global; -// class LLScriptEvent *event; -// class LLScriptEventHandler *handler; -// class LLScriptExpression *expression; -// class LLScriptStatement *statement; -// class LLScriptGlobalFunctions *global_funcs; -// class LLScriptFunctionDec *global_decl; -// class LLScriptState *state; -// class LLScritpGlobalStorage *global_store; -// class LLScriptScript *script; + char *commentValue; + LSL_Type typeValue; + char *nameValue; + struct LSL_Identifier *identifierValue; + float floatValue; + int integerValue; + char *stringValue; + char *keyValue; + float vectorValue[3]; + float rotationValue[4]; + union LSL_Leaf *listValue; + char *labelValue; + LSL_Operation operationValue; + struct LSL_Expression *expressionValue; + LSL_Statement *doValue; + LSL_Statement *forValue; + LSL_Statement *ifValue; + LSL_Statement *elseValue; + LSL_Statement *elseIfValue; + char *jumpValue; + char *stateChangeValue; + LSL_Statement *statementValue; + struct LSL_Identifier *parameterValue; + LSL_Function *functionValue; + LSL_State *stateValue; + LSL_Script *scriptValue; } LSL_Leaf; +typedef struct +{ + char *name; + LSL_Type type; + LSL_Leaf content; +} LSL_Identifier; + +typedef struct LSL_Expression +{ + struct LSL_Expression *left; + struct LSL_Expression *right; + LSL_Type type; + LSL_Leaf content; +} LSL_Expression; + typedef struct LSL_AST { struct LSL_AST *left; @@ -342,19 +314,9 @@ typedef struct LSL_AST typedef struct { yyscan_t scanner; - LSL_Expression *expression; + LSL_AST *ast; } LuaSL_yyparseParam; - -void burnLeaf(LSL_AST *leaf); -void burnLSLExpression(LSL_Expression *exp); -LSL_Expression *addInteger(int value); -LSL_Expression *addOperation(LSL_Operation type, LSL_Expression *left, LSL_Expression *right); -LSL_Expression *newTree(const char *expr); -int evaluateExpression(LSL_Expression *exp, int old); -void outputExpression(LSL_Expression *exp); -void convertExpression2Lua(LSL_Expression *exp); - // the parameter name (of the reentrant 'yyparse' function) // data is a pointer to a 'SParserParam' structure #define YYPARSE_PARAM data @@ -362,6 +324,19 @@ void convertExpression2Lua(LSL_Expression *exp); // the argument for the 'yylex' function #define YYLEX_PARAM ((LuaSL_yyparseParam*)data)->scanner + +void burnLSLExpression(LSL_Expression *exp); +void burnAST(LSL_AST *ast); +LSL_AST *addExpression(LSL_Expression *exp); +LSL_Expression *addInteger(int value); +LSL_Expression *addOperation(LSL_Operation type, LSL_Expression *left, LSL_Expression *right); +int evaluateExpression(LSL_Expression *exp, int old); +int evaluateAST(LSL_AST *ast, int old); +void outputExpression(LSL_Expression *exp); +void outputAST(LSL_AST *ast); +void convertAST2Lua(LSL_AST *ast); +LSL_AST *newTree(const char *expr); + int yyerror(const char *msg); int yyparse(void *param); diff --git a/LuaSL/src/LuaSL_yaccer.y b/LuaSL/src/LuaSL_yaccer.y index fd5a461..e208cce 100644 --- a/LuaSL/src/LuaSL_yaccer.y +++ b/LuaSL/src/LuaSL_yaccer.y @@ -28,7 +28,7 @@ %% input : - expr { ((LuaSL_yyparseParam*)data)->expression = $1; } + expr { ((LuaSL_yyparseParam*)data)->ast = addExpression($1); } ; expr : -- cgit v1.1