From f91ac106f900280537c0cf38ce3ab082eb4f9a33 Mon Sep 17 00:00:00 2001 From: Ian C Date: Mon, 21 Aug 2006 22:14:41 +0000 Subject: Added expression handler for EMMA --- Makefile | 16 +- emma.c | 18 +- expr.c | 728 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ expr.h | 59 ++++++ 4 files changed, 807 insertions(+), 14 deletions(-) create mode 100644 expr.c create mode 100644 expr.h diff --git a/Makefile b/Makefile index 12c228f..6031150 100644 --- a/Makefile +++ b/Makefile @@ -18,7 +18,7 @@ # # ------------------------------------------------------------------------- # -# $Id: Makefile,v 1.3 2006-08-21 00:01:01 ianc Exp $ +# $Id: Makefile,v 1.4 2006-08-21 22:14:41 ianc Exp $ # # This CFLAGS assumes that gcc is being used. @@ -37,11 +37,13 @@ TARGET = emma SOURCE = z80.c \ z80_decode.c \ z80_dis.c \ + expr.c \ emma.c OBJECTS = z80.o \ z80_decode.o \ z80_dis.o \ + expr.o \ emma.o all: $(TARGET) emucpm.hex @@ -63,10 +65,20 @@ depend: z80.o: /usr/include/stdlib.h /usr/include/sys/cdefs.h z80.o: /usr/include/sys/_null.h /usr/include/sys/_types.h -z80.o: /usr/include/machine/_types.h z80.h z80_private.h +z80.o: /usr/include/machine/_types.h /usr/include/string.h +z80.o: /usr/include/strings.h z80.h z80_private.h z80_decode.o: /usr/include/stdlib.h /usr/include/sys/cdefs.h z80_decode.o: /usr/include/sys/_null.h /usr/include/sys/_types.h z80_decode.o: /usr/include/machine/_types.h z80.h z80_private.h +z80_dis.o: /usr/include/stdio.h /usr/include/sys/cdefs.h +z80_dis.o: /usr/include/sys/_null.h /usr/include/sys/_types.h +z80_dis.o: /usr/include/machine/_types.h /usr/include/string.h +z80_dis.o: /usr/include/strings.h /usr/include/stdarg.h z80.h z80_private.h +expr.o: /usr/include/stdlib.h /usr/include/sys/cdefs.h +expr.o: /usr/include/sys/_null.h /usr/include/sys/_types.h +expr.o: /usr/include/machine/_types.h /usr/include/stdio.h +expr.o: /usr/include/string.h /usr/include/strings.h /usr/include/ctype.h +expr.o: /usr/include/_ctype.h /usr/include/runetype.h emma.o: /usr/include/stdlib.h /usr/include/sys/cdefs.h emma.o: /usr/include/sys/_null.h /usr/include/sys/_types.h emma.o: /usr/include/machine/_types.h /usr/include/stdio.h diff --git a/emma.c b/emma.c index 41bdb1a..21c640e 100644 --- a/emma.c +++ b/emma.c @@ -31,6 +31,7 @@ static const char id[]="$Id$"; #include #include "z80.h" +#include "expr.h" #define TRUE 1 @@ -202,7 +203,7 @@ static int StrEq(const char *a, const char *b) } -static int Expand(const char *p, long *res) +static int Expand(void *client, const char *p, long *res) { Z80State s; int ok=TRUE; @@ -312,10 +313,8 @@ static Z80Word Address(const char *p) { long e=0; - if (!Expand(p,&e)) - { - e=strtol(p,NULL,0); - } + if (!ExprEval(p,&e,Expand,z80)) + Log("%s\n",ExprError()); return (Z80Word)e; } @@ -331,10 +330,8 @@ static Z80Val Val(const char *p) { long e=0; - if (!Expand(p,&e)) - { - e=strtol(p,NULL,0); - } + if (!ExprEval(p,&e,Expand,z80)) + Log("%s\n",ExprError()); return (Z80Val)e; } @@ -724,8 +721,6 @@ static void DoRun(int no, const char *arg[]) static void DoUntil(int no, const char *arg[]) { - Log("No supported\n"); -#if 0 if (no<2) { Log("Missing arguments\n"); @@ -763,7 +758,6 @@ static void DoUntil(int no, const char *arg[]) } stop=FALSE; -#endif } diff --git a/expr.c b/expr.c new file mode 100644 index 0000000..9369e1d --- /dev/null +++ b/expr.c @@ -0,0 +1,728 @@ +/* + expr - Simple, expression evaluator + + Copyright (C) 2003 Ian Cowburn (ianc@noddybox.demon.co.uk) + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + ------------------------------------------------------------------------- + + Expands an expression. + +*/ +static const char id[]="$Id$"; + +#include +#include +#include +#include + +/* ---------------------------------------- MACROS +*/ +#define TRUE 1 +#define FALSE 0 + +#define TYPE_OPERAND 0 +#define TYPE_VARIABLE 1 +#define TYPE_OPERATOR 2 /* This acts as a base for operator tokens */ +#define TYPE_LPAREN 3 +#define TYPE_RPAREN 4 +#define TYPE_DIVIDE 5 +#define TYPE_MULTIPLY 6 +#define TYPE_ADD 7 +#define TYPE_SUBTRACT 8 +#define TYPE_NOT 9 +#define TYPE_AND 10 +#define TYPE_OR 11 +#define TYPE_XOR 12 +#define TYPE_UNARY_PLUS 13 +#define TYPE_UNARY_NEG 14 +#define TYPE_SHIFTL 15 +#define TYPE_SHIFTR 16 +#define TYPE_EQUALITY 17 +#define TYPE_BOOL_AND 18 +#define TYPE_BOOL_OR 19 +#define TYPE_MODULUS 20 +#define TYPE_LT 21 +#define TYPE_GT 22 +#define TYPE_LTEQ 23 +#define TYPE_GTEQ 24 +#define TYPE_NOTEQUAL 25 + +#define SYM_LPAREN "(" +#define SYM_RPAREN ")" +#define SYM_DIVIDE "/" +#define SYM_MULTIPLY "*" +#define SYM_ADD "+" +#define SYM_SUBTRACT "-" +#define SYM_NOT "~" +#define SYM_AND "&" +#define SYM_OR "|" +#define SYM_XOR "^" +#define SYM_UNARY_PLUS "+" +#define SYM_UNARY_NEG "-" +#define SYM_SHIFTL "<<" +#define SYM_SHIFTR ">>" +#define SYM_EQUALITY "==" +#define SYM_BOOL_AND "&&" +#define SYM_BOOL_OR "||" +#define SYM_MODULUS "%" +#define SYM_LT "<" +#define SYM_GT ">" +#define SYM_LTEQ "<=" +#define SYM_GTEQ ">=" +#define SYM_NOTEQUAL "!=" + +#define OPERATOR_CHARS "()/*+-~&|^<>!=%" + +#define IS_OPERATOR_TYPE(a) ((a)>=TYPE_OPERATOR) + +#define IS_PAREN(c) ((c)==SYM_LPAREN[0] || (c)==SYM_RPAREN[0]) + +#define IS_OPERATOR(c) (strchr(OPERATOR_CHARS,(c))) + +#define IS_OPERAND_END(c) ((c)==' ' || (c)=='\t' || IS_OPERATOR(c)) + +/* ---------------------------------------- TYPES +*/ + +typedef struct stk + { + int token; + int priority; + int is_unary; + char *text; + struct stk *next; + } Stack; + + +typedef enum {OpBinary, OpPretendUnary, OpUnary} OpType; + +typedef struct + { + const char *symbol; + int priority; + int token; + OpType type; + int allow_unary; + } Operator; + + +typedef enum {OpOk, OpSyntaxError, OpUnknown} OpError; + + +/* ---------------------------------------- GLOBALS +*/ +static char error[1024]; + +static int (*expand)(void *client_data, + const char *p, + long *value); + +static void *client=NULL; + +static const Operator op_info[]= + { + /* Unary ops - must be first in list. Note that LPAREN is treated + as a unary as it must be preceeded by another operator, rather + than an operand. + */ + {SYM_NOT, 9, TYPE_NOT, OpUnary, TRUE}, + {SYM_UNARY_PLUS,9, TYPE_UNARY_PLUS,OpUnary, TRUE}, + {SYM_UNARY_NEG, 9, TYPE_UNARY_NEG, OpUnary, TRUE}, + {SYM_LPAREN, 99, TYPE_LPAREN, OpPretendUnary, TRUE}, + + /* Binary ops and don't care ops + */ + {SYM_RPAREN, 99, TYPE_RPAREN, OpBinary, FALSE}, + {SYM_SHIFTL, 6, TYPE_SHIFTL, OpBinary, TRUE}, + {SYM_SHIFTR, 6, TYPE_SHIFTR, OpBinary, TRUE}, + {SYM_MULTIPLY, 5, TYPE_MULTIPLY, OpBinary, TRUE}, + {SYM_DIVIDE, 5, TYPE_DIVIDE, OpBinary, TRUE}, + {SYM_MODULUS, 5, TYPE_MODULUS, OpBinary, TRUE}, + {SYM_ADD, 4, TYPE_ADD, OpBinary, TRUE}, + {SYM_SUBTRACT, 4, TYPE_SUBTRACT, OpBinary, TRUE}, + {SYM_EQUALITY, 1, TYPE_EQUALITY, OpBinary, TRUE}, + {SYM_NOTEQUAL, 1, TYPE_NOTEQUAL, OpBinary, TRUE}, + {SYM_LTEQ, 1, TYPE_LTEQ, OpBinary, TRUE}, + {SYM_GTEQ, 1, TYPE_GTEQ, OpBinary, TRUE}, + {SYM_LT, 1, TYPE_LT, OpBinary, TRUE}, + {SYM_GT, 1, TYPE_GT, OpBinary, TRUE}, + {SYM_BOOL_AND, 0, TYPE_BOOL_AND, OpBinary, TRUE}, + {SYM_AND, 0, TYPE_AND, OpBinary, TRUE}, + {SYM_BOOL_OR, 0, TYPE_BOOL_OR, OpBinary, TRUE}, + {SYM_OR, 0, TYPE_OR, OpBinary, TRUE}, + {SYM_XOR, 0, TYPE_XOR, OpBinary, TRUE}, + + {0,0,0} + }; + + +/* ---------------------------------------- PRIVATE FUNCTIONS +*/ + +/* malloc wrapper +*/ +static void *Malloc(size_t size) +{ + void *p=malloc(size); + + if (!p) + { + fprintf(stderr,"malloc failed\n"); + exit(EXIT_FAILURE); + } + + return p; +} + + +/* Copy a string +*/ +static char *CopyStr(const char *p) +{ + char *new=Malloc(strlen(p)+1); + + return strcpy(new,p); +} + + +/* Empty a stack +*/ +static Stack *ClearStack(Stack *stack) +{ + while(stack) + { + Stack *tmp=stack; + + stack=stack->next; + free(tmp->text); + free(tmp); + } + + return stack; +} + + +/* Push onto the stack +*/ +static Stack *Push(Stack *stack, int token, int priority, + int is_unary, const char *text) +{ + Stack *e=Malloc(sizeof *e); + + e->text=CopyStr(text); + e->priority=priority; + e->token=token; + e->is_unary=is_unary; + e->next=stack; + stack=e; + + return stack; +} + + +/* Destroy the top element on the stack +*/ +static Stack *Pop(Stack *stack) +{ + if (stack) + { + Stack *tmp=stack; + + stack=stack->next; + + free(tmp->text); + free(tmp); + } + + return stack; +} + + +/* Debug to dump a stack non-destructively +static void Dump(const char *name, Stack *stack) +{ + while (stack) + { + printf("%-10s: Type: %-2d is_unary: %d text: %s\n", + name,stack->token,stack->is_unary,stack->text); + + stack=stack->next; + } +} +*/ + + +/* Find the symbol for an operator +*/ +static const char *ToString(int token) +{ + static char buff[32]; + int f; + + strcpy(buff,"UNKNOWN"); + + for(f=0;op_info[f].symbol;f++) + { + if (op_info[f].token==token) + { + strcpy(buff,op_info[f].symbol); + return buff; + } + } + + return "UNKNOWN"; +} + + +/* Search the operator info +*/ +static OpError FindOp(const char *p, int prev_was_op, const Operator **op) +{ + int f; + int found=FALSE; + + *op=NULL; + + for(f=0;op_info[f].symbol;f++) + { + if (strncmp(op_info[f].symbol,p,strlen(op_info[f].symbol))==0) + { + found=TRUE; + + if ((prev_was_op && op_info[f].type!=OpBinary) || + (!prev_was_op && op_info[f].type==OpBinary)) + + { + *op=op_info+f; + return OpOk; + } + } + } + + if (found) + return OpSyntaxError; + else + return OpUnknown; +} + + +static Stack *ToPostfix(const char *expr) +{ + Stack *stack=NULL; + Stack *output=NULL; + char buff[1024]; + char *p; + int prev_was_op=TRUE; + + /* Parse the infix expression into postfix + */ + while(*expr) + { + if (IS_OPERATOR(*expr)) + { + /* Found an operator - parse it + */ + const Operator *op; + OpError op_err; + + op_err=FindOp(expr,prev_was_op,&op); + + /* Unknown operator in expression + */ + if (!op) + { + if (op_err==OpSyntaxError) + sprintf(error,"Syntax error with operator %c",*expr); + else + sprintf(error,"Unknown operator %c",*expr); + + stack=ClearStack(stack); + output=ClearStack(output); + + return NULL; + } + + /* Special handling for closing parenthesis + */ + if (op->token==TYPE_RPAREN) + { + while(stack && stack->token!=TYPE_LPAREN) + { + output=Push(output, + stack->token, + stack->priority, + stack->is_unary, + stack->text); + stack=Pop(stack); + } + + /* Syntax error in expression + */ + if (!stack) + { + sprintf(error,"Missing %s",SYM_LPAREN); + + stack=ClearStack(stack); + output=ClearStack(output); + + return NULL; + } + + /* Remove the opening bracket and continue + */ + stack=Pop(stack); + } + else + { + /* Output the stack until an operator of lower precedence is + found + */ + if (op->type==OpUnary) + { + while(stack && !IS_PAREN(stack->text[0]) && + !stack->is_unary && + (stack->priority >= op->priority)) + { + output=Push(output, + stack->token, + stack->priority, + stack->is_unary, + stack->text); + + stack=Pop(stack); + } + } + else + { + while(stack && !IS_PAREN(stack->text[0]) && + (stack->priority >= op->priority)) + { + output=Push(output, + stack->token, + stack->priority, + stack->is_unary, + stack->text); + + stack=Pop(stack); + } + } + + stack=Push(stack, + op->token, + op->priority, + op->type==OpUnary, + op->symbol); + } + + /* Move past token + */ + expr+=strlen(op->symbol); + + prev_was_op=op->allow_unary; + } + else + { + /* Found an operand - parse and store the operand + */ + p=buff; + + while(*expr && !IS_OPERAND_END(*expr)) + { + *p++=*expr++; + } + + *p=0; + + /* Note that operands are marked as unary just to chose one over + the other branch in EvalPostfix() - no other reason + */ + output=Push(output,TYPE_OPERAND,0,TRUE,buff); + + prev_was_op=FALSE; + } + } + + while(stack) + { + output=Push(output, + stack->token, + stack->priority, + stack->is_unary, + stack->text); + + stack=Pop(stack); + } + + /* Return the stack + */ + return output; +} + + +static int EvalPostfix(Stack **stack, long *result) +{ + Stack *expr; + int token; + + expr=*stack; + + if (!expr) + { + sprintf(error,"Called with empty postfix stack"); + return FALSE; + } + + token=expr->token; + + if (expr->is_unary) + { + if (token==TYPE_OPERAND) + { + char *endp; + + *result=strtol(expr->text,&endp,0); + + if (!(expr->text[0] && *endp==0)) + { + int ok=FALSE; + + if (expand) + ok=expand(client,expr->text,result); + + if (!ok) + { + sprintf(error,"Undefined variable '%s'",expr->text); + return FALSE; + } + } + + expr=Pop(expr); + } + else if (token==TYPE_VARIABLE) + { + int ok=FALSE; + + if (expand) + ok=expand(client,expr->text,result); + + if (!ok) + { + sprintf(error,"Undefined variable '%s'",expr->text); + return FALSE; + } + + expr=Pop(expr); + } + else + { + long val; + + expr=Pop(expr); + + if (!expr || !EvalPostfix(&expr,&val)) + { + sprintf(error,"Operator '%s' expects an argument", + ToString(token)); + *stack=expr; + return FALSE; + } + + switch(token) + { + case TYPE_NOT: + *result=~val; + break; + + case TYPE_UNARY_PLUS: + *result=+val; + break; + + case TYPE_UNARY_NEG: + *result=-val; + break; + + default: + sprintf(error,"Execpected unary token '%s' processed", + ToString(token)); + *stack=expr; + return FALSE; + break; + } + } + } + else + { + long left,right; + + expr=Pop(expr); + + if (!expr || !EvalPostfix(&expr,&right)) + { + sprintf(error,"Operator '%s' expects two arguments", + ToString(token)); + *stack=expr; + return FALSE; + } + + if (!expr || !EvalPostfix(&expr,&left)) + { + sprintf(error,"Operator '%s' expects two arguments", + ToString(token)); + *stack=expr; + return FALSE; + } + + switch(token) + { + case TYPE_DIVIDE: + *result=left/right; + break; + + case TYPE_MULTIPLY: + *result=left*right; + break; + + case TYPE_MODULUS: + *result=left%right; + break; + + case TYPE_ADD: + *result=left+right; + break; + + case TYPE_SUBTRACT: + *result=left-right; + break; + + case TYPE_AND: + *result=left&right; + break; + + case TYPE_OR: + *result=left|right; + break; + + case TYPE_BOOL_AND: + *result=left&&right; + break; + + case TYPE_BOOL_OR: + *result=left||right; + break; + + case TYPE_XOR: + *result=left^right; + break; + + case TYPE_SHIFTL: + if (right<0) + { + sprintf(error,"Cannot shift left by a " + "negative number (%ld)",right); + *stack=expr; + return FALSE; + } + + *result=left<>right; + break; + + case TYPE_EQUALITY: + *result=left==right; + break; + + case TYPE_NOTEQUAL: + *result=left!=right; + break; + + case TYPE_LT: + *result=leftright; + break; + + case TYPE_LTEQ: + *result=left<=right; + break; + + case TYPE_GTEQ: + *result=left>=right; + break; + + default: + sprintf(error,"Unexpected binary token '%s' processed", + ToString(token)); + *stack=expr; + return FALSE; + break; + } + } + + *stack=expr; + + return TRUE; +} + + +/* ---------------------------------------- INTERFACES +*/ + +int ExprEval(const char *expr, long *result, + int (*expand_var)(void *client_data, const char *p, long *value), + void *client_data) +{ + Stack *output; + int ret; + + expand=expand_var; + client=client_data; + + output=ToPostfix(expr); + + if (!output) + return FALSE; + + ret=EvalPostfix(&output,result); + + ClearStack(output); + + return ret; +} + + +/* Gets a readable reason for an error from ExprEval() or ExprParse. +*/ +const char *ExprError(void) +{ + return error; +} + + +/* END OF FILE */ diff --git a/expr.h b/expr.h new file mode 100644 index 0000000..2c77897 --- /dev/null +++ b/expr.h @@ -0,0 +1,59 @@ +/* + expr - Simple, expression evaluator + + Copyright (C) 2003 Ian Cowburn (ianc@noddybox.demon.co.uk) + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + ------------------------------------------------------------------------- + + This is a simple expression evaluator, supporting user supplied variables. + + It works on longs, but a floating point version would be easy enough to + generate from this. + + NB: THIS CODE IS NOT THREAD SAFE +*/ + +#ifndef EXPR_H +#define EXPR_H "$Id$" + +/* ---------------------------------------- INTERFACES +*/ + +/* Returns the result of expr and stores the answer in result. + Returns FALSE on error. + + If expand_var is not NULL then unrecognised strings of characters + (basically anything that gives strtol() problems) are passed to that + to expand the value. The return of this routine should be TRUE if the + value was expanded into value. The client_data pointer is passed to + expand_var(). +*/ +int ExprEval(const char *expr, long *result, + int (*expand_var)(void *client_data, + const char *p, + long *value), + void *client_data); + + +/* Gets a readable reason for an error from ExprEval() or ExprParse. +*/ +const char *ExprError(void); + + +#endif + +/* END OF FILE */ -- cgit v1.2.3