From 4acb11b9692e01d40bee2d3c31d582d5de485b31 Mon Sep 17 00:00:00 2001 From: PioneerAxon Date: Fri, 3 Aug 2012 18:26:28 +0530 Subject: [PATCH] Replace lex/bison parser with hand-written parser Fixed .gitignore file entry. Removed dependency of lex/bison. Add back test case in test-mp-equation.c. Added new parser code. -prelexer.[ch] deals with unichar manipulation. -lexer.[ch] generates tokens from input. -parser.[ch] deals with grammar, and generates parse-tree. -parserfunc.[ch] binds mp code and parser to evaluate parse-tree. This patch is result of 33 commits. The repository with complete commit history is hosted at https://bitbucket.org/PioneerAxon/math-parser --- .gitignore | 2 +- configure.ac | 19 - src/Makefile.am | 59 ++- src/lexer.c | 587 ++++++++++++++++++++++ src/lexer.h | 40 ++ src/mp-equation-lexer.l | 111 ---- src/mp-equation-parser.y | 261 ---------- src/mp-equation-private.h | 56 --- src/mp-equation.c | 85 ++-- src/parser.c | 1228 +++++++++++++++++++++++++++++++++++++++++++++ src/parser.h | 79 +++ src/parserfunc.c | 967 +++++++++++++++++++++++++++++++++++ src/parserfunc.h | 80 +++ src/prelexer.c | 214 ++++++++ src/prelexer.h | 93 ++++ src/test-mp-equation.c | 2 +- 16 files changed, 3353 insertions(+), 530 deletions(-) create mode 100644 src/lexer.c create mode 100644 src/lexer.h delete mode 100644 src/mp-equation-lexer.l delete mode 100644 src/mp-equation-parser.y delete mode 100644 src/mp-equation-private.h create mode 100644 src/parser.c create mode 100644 src/parser.h create mode 100644 src/parserfunc.c create mode 100644 src/parserfunc.h create mode 100644 src/prelexer.c create mode 100644 src/prelexer.h diff --git a/.gitignore b/.gitignore index e1d78404..3cc5d513 100644 --- a/.gitignore +++ b/.gitignore @@ -40,4 +40,4 @@ src/mp-equation-parser.h src/gcalccmd src/gcalctool src/test-mp -src/test-mp-serializer +src/test-mp-equation diff --git a/configure.ac b/configure.ac index c2ff44d4..011073d3 100644 --- a/configure.ac +++ b/configure.ac @@ -43,25 +43,6 @@ AC_SUBST(GLIB_MKENUMS) AC_CHECK_LIB(m, log) dnl ########################################################################### -dnl Determine if a usable lex is available on this system -dnl ########################################################################### - -AM_PROG_LEX -if [[ "$LEX" != "flex" ]]; then - AC_MSG_ERROR(flex is required to create the gcalctool scanners) -fi - -dnl ########################################################################### -dnl Determine if a usable yacc is available on this system -dnl ########################################################################### - -AC_PROG_YACC -AC_CHECK_PROG(HAVE_YACC, $YACC, yes, no) -if [[ "$HAVE_YACC" = "no" ]]; then - AC_MSG_ERROR($YACC is not usable as yacc - consider using bison) -fi - -dnl ########################################################################### dnl Internationalization dnl ########################################################################### diff --git a/src/Makefile.am b/src/Makefile.am index 3a23f658..b67c11d0 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -42,10 +42,6 @@ gcalctool_SOURCES = \ mp-equation.c \ mp-equation.h \ mp-equation-private.h \ - mp-equation-lexer.c \ - mp-equation-lexer.h \ - mp-equation-parser.c \ - mp-equation-parser.h \ mp-private.h \ mp-serializer.c \ mp-serializer.h \ @@ -57,7 +53,15 @@ gcalctool_SOURCES = \ unit-category.c \ unit-category.h \ unit-manager.c \ - unit-manager.h + unit-manager.h \ + prelexer.c \ + prelexer.h \ + lexer.c \ + lexer.h \ + parserfunc.c \ + parserfunc.h \ + parser.c \ + parser.h gcalctool_LDADD = \ $(GCALCTOOL_LIBS) @@ -74,8 +78,6 @@ gcalccmd_SOURCES = \ mp-enums.c \ mp-enums.h \ mp-equation.c \ - mp-equation-parser.c \ - mp-equation-lexer.c \ mp-serializer.c \ mp-serializer.h\ mp-trigonometric.c \ @@ -84,7 +86,15 @@ gcalccmd_SOURCES = \ unit-category.c \ unit-category.h \ unit-manager.c \ - unit-manager.h + unit-manager.h \ + prelexer.c \ + prelexer.h \ + lexer.c \ + lexer.h \ + parserfunc.c \ + parserfunc.h \ + parser.c \ + parser.h gcalccmd_LDADD = \ $(GCALCCMD_LIBS) \ @@ -117,8 +127,6 @@ test_mp_equation_SOURCES = \ mp-enums.c \ mp-enums.h \ mp-equation.c \ - mp-equation-parser.c \ - mp-equation-lexer.c \ mp-serializer.c \ mp-serializer.h \ mp-trigonometric.c \ @@ -127,7 +135,15 @@ test_mp_equation_SOURCES = \ unit-category.c \ unit-category.h \ unit-manager.c \ - unit-manager.h + unit-manager.h \ + prelexer.c \ + prelexer.h \ + lexer.c \ + lexer.h \ + parserfunc.c \ + parserfunc.h \ + parser.c \ + parser.h test_mp_equation_LDADD = \ $(GCALCCMD_LIBS) \ @@ -135,24 +151,7 @@ test_mp_equation_LDADD = \ CLEANFILES = \ mp-enums.c \ - mp-enums.h \ - mp-equation-parser.h \ - mp-equation-parser.c \ - mp-equation-lexer.c \ - mp-equation-lexer.h - -# Generate parser files -mp-equation-parser.c mp-equation-parser.h: mp-equation-parser.y mp-equation-lexer.h - $(AM_V_GEN)$(YACC) -d -o mp-equation-parser.c $(srcdir)/mp-equation-parser.y - -# Generate lexer files -mp-equation-lexer.c mp-equation-lexer.h: mp-equation-lexer.l - $(AM_V_GEN)$(LEX) $(srcdir)/mp-equation-lexer.l - -# Rebuild parser when source files change -mp-equation-parser.o: mp-equation-lexer.h -mp-equation-lexer.o: mp-equation-parser.h -mp-equation.c: mp-equation-lexer.h mp-equation-parser.h + mp-enums.h # Generate enum types mp-enums.h: mp-enums.h.template mp-serializer.h @@ -176,8 +175,6 @@ uninstall-local: && rm -f "$(DESTDIR)$(bindir)/gnome-calculator" EXTRA_DIST = \ - mp-equation-parser.y \ - mp-equation-lexer.l \ mp-enums.c.template \ mp-enums.h.template diff --git a/src/lexer.c b/src/lexer.c new file mode 100644 index 00000000..9f6f9abf --- /dev/null +++ b/src/lexer.c @@ -0,0 +1,587 @@ +#include +#include +#include + +#include "lexer.h" +#include "parserfunc.h" +#include "mp-equation.h" + +static gboolean +l_check_if_function(LexerState* state) +{ + gchar* name = pl_get_marked_substring(state->prelexer); + if(!state->parent->function_is_defined) + { + free(name); + return FALSE; + } + if ((*(state->parent->function_is_defined))(state->parent, name)) + { + free(name); + return TRUE; + } + else + { + free(name); + return FALSE; + } +} + +static gboolean +l_check_if_number(LexerState* state) +{ + MPNumber tmp; + int count = 0; + gchar* text = pl_get_marked_substring(state->prelexer); + if(mp_set_from_string(text, state->parent->options->base, &tmp) == 0) + { + free(text); + return TRUE; + } + else + { + /* Try to rollback several characters to see, if that yeilds any number. */ + while(strlen (text) > 0) + { + if(mp_set_from_string(text, state->parent->options->base, &tmp) == 0) + { + free(text); + return TRUE; + } + free(text); + count++; + pl_roll_back(state->prelexer); + text = pl_get_marked_substring(state->prelexer); + } + /* Undo all rollbacks. */ + while(count--) + pl_get_next_token (state->prelexer); + free(text); + return FALSE; + } +} + +/* Insert generated token to the LexerState structure. */ +static LexerToken* +l_insert_token(LexerState* state, const LexerTokenType type) +{ + state->tokens = (LexerToken *) realloc(state->tokens, (state->token_count + 1) * sizeof(LexerToken)); + assert(state->tokens != NULL); + state->tokens[state->token_count].string = pl_get_marked_substring(state->prelexer); + state->tokens[state->token_count].start_index = state->prelexer->mark_index; + state->tokens[state->token_count].end_index = state->prelexer->next_index; + state->tokens[state->token_count].token_type = type; + state->token_count++; + return &state->tokens[state->token_count - 1]; +} + +/* Generates next token from pre-lexer stream and call l_insert_token() to insert it at the end. */ +static LexerToken* +l_insert_next_token(LexerState* lstate) +{ + PreLexerState* state = lstate->prelexer; + LexerTokenType type; + gchar* tmp; + pl_set_marker(state); + /* Ignore all blank spaces. :) */ + while((type = pl_get_next_token(state)) == PL_SKIP) + /* Set marker. Beginning of new token. */ + pl_set_marker(state); + if(type == T_AND + ||type == T_OR + ||type == T_XOR + ||type == T_NOT + ||type == T_ADD + ||type == T_SUBTRACT + ||type == T_MULTIPLY + ||type == T_DIVIDE + ||type == T_L_FLOOR + ||type == T_R_FLOOR + ||type == T_L_CEILING + ||type == T_R_CEILING + ||type == T_ROOT + ||type == T_ROOT_3 + ||type == T_ROOT_4 + ||type == T_ASSIGN + ||type == T_L_R_BRACKET + ||type == T_R_R_BRACKET + ||type == T_L_S_BRACKET + ||type == T_R_S_BRACKET + ||type == T_L_C_BRACKET + ||type == T_R_C_BRACKET + ||type == T_ABS + ||type == T_POWER + ||type == T_FACTORIAL + ||type == T_PERCENTAGE) + { + return l_insert_token(lstate, type); + } + /* [PL_SUPER_MINUS][PL_SUPER_DIGIT]+ */ + if(type == PL_SUPER_MINUS) + { + if((type = pl_get_next_token(state)) != PL_SUPER_DIGIT) + { + /* ERROR: expected PL_SUP_DIGIT */ + set_error(lstate->parent, PARSER_ERR_MP, tmp = pl_get_marked_substring (state)); + free(tmp); + return l_insert_token(lstate, T_UNKNOWN); + } + /* Get all PL_SUPER_DIGITs. */ + while (pl_get_next_token(state) == PL_SUPER_DIGIT); + pl_roll_back(state); + return l_insert_token(lstate, T_NSUP_NUMBER); + } + /* [PL_SUPER_DIGIT]+ */ + if(type == PL_SUPER_DIGIT) + { + while(pl_get_next_token(state) == PL_SUPER_DIGIT); + pl_roll_back(state); + return l_insert_token(lstate, T_SUP_NUMBER); + } + /* [PL_SUB_DIGIT]+ */ + if(type == PL_SUB_DIGIT) + { + while(pl_get_next_token(state) == PL_SUB_DIGIT); + pl_roll_back(state); + return l_insert_token(lstate, T_SUB_NUMBER); + } + /* [PL_FRACTION] */ + if(type == PL_FRACTION) + { + return l_insert_token(lstate, T_NUMBER); + } + if(type == PL_DIGIT) + { + while((type = pl_get_next_token(state)) == PL_DIGIT); + if(type == PL_FRACTION) + { + return l_insert_token(lstate, T_NUMBER); + } + else if(type == PL_SUB_DIGIT) + { + while(pl_get_next_token(state) == PL_SUB_DIGIT); + pl_roll_back(state); + return l_insert_token(lstate, T_NUMBER); + } + else if(type == PL_DEGREE) + { + type = pl_get_next_token(state); + if(type == PL_DIGIT) + { + while((type = pl_get_next_token(state)) == PL_DIGIT); + if(type == PL_DECIMAL) + { + goto ANGLE_NUM_DM_STATE; + } + else if(type == PL_MINUTE) + { + type = pl_get_next_token(state); + if(type == PL_DIGIT) + { + while((type = pl_get_next_token(state)) == PL_DIGIT); + if(type == PL_DECIMAL) + { + goto ANGLE_NUM_DMS_STATE; + } + else if(type == PL_SECOND) + { + return l_insert_token(lstate, T_NUMBER); + } + else + { + /* ERROR: expected PL_SECOND */ + set_error(lstate->parent, PARSER_ERR_MP, tmp = pl_get_marked_substring (state)); + free(tmp); + return l_insert_token(lstate, T_UNKNOWN); + } + } + else if(type == PL_DECIMAL) + { +ANGLE_NUM_DMS_STATE: + if((type = pl_get_next_token (state)) != PL_DIGIT) + { + /* ERROR: expected PL_DIGIT */ + set_error(lstate->parent, PARSER_ERR_MP, tmp = pl_get_marked_substring(state)); + free(tmp); + return l_insert_token(lstate, T_UNKNOWN); + } + while((type = pl_get_next_token(state)) == PL_DIGIT); + if(type == PL_SECOND) + { + return l_insert_token(lstate, T_NUMBER); + } + else + { + /* ERROR: expected PL_SECOND */ + set_error(lstate->parent, PARSER_ERR_MP, tmp = pl_get_marked_substring(state)); + free(tmp); + return l_insert_token(lstate, T_UNKNOWN); + } + } + else + { + pl_roll_back(state); + return l_insert_token(lstate, T_NUMBER); + } + } + else + { + /* ERROR: expected PL_MINUTE | PL_DIGIT */ + set_error(lstate->parent, PARSER_ERR_MP, tmp = pl_get_marked_substring(state)); + free(tmp); + return l_insert_token(lstate, T_UNKNOWN); + } + } + else if(type == PL_DECIMAL) + { +ANGLE_NUM_DM_STATE: + if((type = pl_get_next_token(state)) != PL_DIGIT) + { + /* ERROR: expected PL_DIGIT */ + set_error(lstate->parent, PARSER_ERR_MP, tmp = pl_get_marked_substring(state)); + free(tmp); + return l_insert_token(lstate, T_UNKNOWN); + } + while((type = pl_get_next_token(state)) == PL_DIGIT); + if(type == PL_MINUTE) + { + return l_insert_token(lstate, T_NUMBER); + } + else + { + /* ERROR: expected PL_MINUTE */ + set_error(lstate->parent, PARSER_ERR_MP, tmp = pl_get_marked_substring(state)); + free(tmp); + return l_insert_token(lstate, T_UNKNOWN); + } + } + else + { + return l_insert_token(lstate, T_NUMBER); + } + } + else if(type == PL_DECIMAL) + { + goto DECIMAL_STATE; + } + else if(type == PL_HEX) + { + goto HEX_DEC_STATE; + } + else + { + pl_roll_back(state); + return l_insert_token(lstate, T_NUMBER); + } + } + if(type == PL_DECIMAL) + { +DECIMAL_STATE: + type = pl_get_next_token(state); + if(type == PL_DIGIT) + { + while((type = pl_get_next_token(state)) == PL_DIGIT); + if(type == PL_DEGREE) + { + return l_insert_token(lstate, T_NUMBER); + } + else if(type == PL_HEX) + { + goto DECIMAL_HEX_STATE; + } + else if(type == PL_SUB_DIGIT) + { + while(pl_get_next_token(state) == PL_SUB_DIGIT); + pl_roll_back(state); + return l_insert_token(lstate, T_NUMBER); + } + else + { + pl_roll_back(state); + return l_insert_token(lstate, T_NUMBER); + } + } + else if(type == PL_HEX) + { + goto DECIMAL_HEX_STATE; + } + else + { + /* ERROR: expected PL_DIGIT | PL_HEX */ + set_error(lstate->parent, PARSER_ERR_MP, tmp = pl_get_marked_substring(state)); + free(tmp); + return l_insert_token(lstate, T_UNKNOWN); + } + } + if(type == PL_HEX) + { + while((type = pl_get_next_token(state)) == PL_HEX); + if(type == PL_DIGIT) + { +HEX_DEC_STATE: + while(1) + { + type = pl_get_next_token(state); + if(type == PL_DIGIT || type == PL_HEX) + { + continue; + } + else if(type == PL_DECIMAL) + { + goto DECIMAL_HEX_STATE; + } + else if(type == PL_SUB_DIGIT) + { + while(pl_get_next_token(state) == PL_SUB_DIGIT); + pl_roll_back(state); + return l_insert_token(lstate, T_NUMBER); + } + else + { + if(l_check_if_number(lstate)) + return l_insert_token(lstate, T_NUMBER); + /* ERROR: expected PL_DECIMAL | PL_DIGIT | PL_HEX */ + set_error(lstate->parent, PARSER_ERR_MP, tmp = pl_get_marked_substring(state)); + free(tmp); + return l_insert_token(lstate, T_UNKNOWN); + } + } + } + else if(type == PL_DECIMAL) + { +DECIMAL_HEX_STATE: + type = pl_get_next_token(state); + if(!(type == PL_DIGIT || type == PL_HEX)) + { + /* ERROR: expected PL_DIGIT | PL_HEX */ + set_error(lstate->parent, PARSER_ERR_MP, tmp = pl_get_marked_substring(state)); + free(tmp); + return l_insert_token(lstate, T_UNKNOWN); + } + while(1) + { + type = pl_get_next_token(state); + if(type == PL_DIGIT || type == PL_HEX) + { + continue; + } + else if(type == PL_SUB_DIGIT) + { + while(pl_get_next_token(state) == PL_SUB_DIGIT); + pl_roll_back(state); + return l_insert_token(lstate, T_NUMBER); + } + else + { + pl_roll_back(state); + return l_insert_token(lstate, T_NUMBER); + } + } + } + else if(type == PL_SUB_DIGIT) + { + while(pl_get_next_token(state) == PL_SUB_DIGIT); + pl_roll_back(state); + if(l_check_if_number(lstate)) + { + /* NUMBER */ + return l_insert_token(lstate, T_NUMBER); + } + else + { + /* VARIABLE */ + if(l_check_if_function(lstate)) + { + return l_insert_token(lstate, T_FUNCTION); + } + else + { + return l_insert_token(lstate, T_VARIABLE); + } + } + } + else if(type == PL_LETTER) + { + goto LETTER_STATE; + } + else + { + pl_roll_back(state); + if(l_check_if_number(lstate)) + { + /* NUMBER */ + return l_insert_token(lstate, T_NUMBER); + } + else + { + /* VARIABLE */ + if(l_check_if_function(lstate)) + { + return l_insert_token(lstate, T_FUNCTION); + } + else + { + return l_insert_token(lstate, T_VARIABLE); + } + } + } + } + if(type == PL_LETTER) + { +LETTER_STATE: + while(1) + { + type = pl_get_next_token(state); + if(type == PL_LETTER || type == PL_HEX) + { + continue; + } + else if(type == PL_SUB_DIGIT) + { + while(pl_get_next_token(state) == PL_SUB_DIGIT); + pl_roll_back(state); + tmp = g_ascii_strdown(pl_get_marked_substring(state), -1); + if(g_strcmp0(tmp, "mod") == 0) + { + return l_insert_token(lstate, T_MOD); + } + if(g_strcmp0(tmp, "and") == 0) + { + return l_insert_token(lstate, T_AND); + } + if(g_strcmp0(tmp, "or") == 0) + { + return l_insert_token(lstate, T_OR); + } + if(g_strcmp0(tmp, "xor") == 0) + { + return l_insert_token(lstate, T_XOR); + } + if(g_strcmp0(tmp, "not") == 0) + { + return l_insert_token(lstate, T_NOT); + } + if(g_strcmp0(tmp, "in") == 0) + { + return l_insert_token(lstate, T_IN); + } + if(l_check_if_function(lstate)) + { + return l_insert_token(lstate, T_FUNCTION); + } + else + { + return l_insert_token(lstate, T_VARIABLE); + } + } + else + { + pl_roll_back(state); + tmp = g_ascii_strdown(pl_get_marked_substring(state), -1); + if(g_strcmp0(tmp, "mod") == 0) + { + return l_insert_token(lstate, T_MOD); + } + if(g_strcmp0(tmp, "and") == 0) + { + return l_insert_token(lstate, T_AND); + } + if(g_strcmp0(tmp, "or") == 0) + { + return l_insert_token(lstate, T_OR); + } + if(g_strcmp0(tmp, "xor") == 0) + { + return l_insert_token(lstate, T_XOR); + } + if(g_strcmp0(tmp, "not") == 0) + { + return l_insert_token(lstate, T_NOT); + } + if(g_strcmp0(tmp, "in") == 0) + { + return l_insert_token(lstate, T_IN); + } + if(l_check_if_function(lstate)) + { + return l_insert_token(lstate, T_FUNCTION); + } + else + { + return l_insert_token(lstate, T_VARIABLE); + } + } + } + } + if(type == PL_EOS) + { + return l_insert_token(lstate, PL_EOS); + } + /* ERROR: Unexpected token.. X( */ + set_error(lstate->parent, PARSER_ERR_INVALID, tmp = pl_get_marked_substring(state)); + free(tmp); + return l_insert_token(lstate, T_UNKNOWN); +} + +/* Call l_insert_next_token() as many times as needed to completely tokenize the string. */ +void +l_insert_all_tokens(LexerState* state) +{ + LexerToken* token; + while(1) + { + token = l_insert_next_token(state); + assert(token != NULL); + if(token->token_type == PL_EOS) + { + break; + } + } +} + +/* Create a lexer state from given input string. This will take care of pre-lexer state. */ +LexerState* +l_create_lexer(const gchar* input, struct parser_state* parent) +{ + LexerState* ret; + ret = (LexerState *) malloc(sizeof(LexerState)); + assert(ret != NULL); + ret->prelexer = pl_create_scanner(input); + ret->tokens = NULL; + ret->token_count = 0; + ret->next_token = 0; + ret->parent = parent; + return ret; +} + +/* Destroy lexer state and free memory. */ +void +l_destroy_lexer(LexerState* state) +{ + int l; + pl_destroy_scanner(state->prelexer); + for(l = 0; l < state->token_count; l++) + { + free(state->tokens[l].string); + } + free(state->tokens); + free(state); +} + +/* Get next token interface. Will be called by parser to get pointer to next token in token stream. */ +LexerToken* +l_get_next_token(LexerState* state) +{ + /* Return PL_EOS token after token stream reaches to its end. */ + if(state->next_token >= state->token_count) + return &state->tokens[state->token_count - 1]; + return &state->tokens[state->next_token++]; +} + +/* Roll back one lexer token. */ +void +l_roll_back(LexerState* state) +{ + if(state->next_token > 0) + state->next_token--; +} diff --git a/src/lexer.h b/src/lexer.h new file mode 100644 index 00000000..2fd7fa77 --- /dev/null +++ b/src/lexer.h @@ -0,0 +1,40 @@ +#ifndef LEXER_H +#define LEXER_H + +#include "prelexer.h" + +/* Structure to hold single token. */ +typedef struct +{ + gchar* string; /* Poniter to local copy of token string. */ + guint start_index; /* Start index in original stream. */ + guint end_index; /* End index in original stream. */ + LexerTokenType token_type; /* Type of token. */ +} LexerToken; + +/* Structure to hold lexer state and all the tokens. */ +typedef struct +{ + PreLexerState *prelexer; /* Pre-lexer state. Pre-lexer is part of lexer. */ + LexerToken *tokens; /* Pointer to the dynamic array of LexerTokens. */ + guint token_count; /* Count of tokens in array. */ + guint next_token; /* Index of next, to be sent, token. */ + struct parser_state *parent; /* Pointer to the parent parser. */ +} LexerState; + +/* Create a new LexerState object and fill the dynamic array with tokens. */ +LexerState* l_create_lexer(const gchar*, struct parser_state*); + +/* Destroy LexerState object and free up space. */ +void l_destroy_lexer(LexerState*); + +/* Tokanize complete string. */ +void l_insert_all_tokens(LexerState*); + +/* Return next, to be sent, token. */ +LexerToken* l_get_next_token(LexerState*); + +/* Roll back one token. */ +void l_roll_back(LexerState*); + +#endif /* LEXER_H */ diff --git a/src/mp-equation-lexer.l b/src/mp-equation-lexer.l deleted file mode 100644 index 1a8919e7..00000000 --- a/src/mp-equation-lexer.l +++ /dev/null @@ -1,111 +0,0 @@ -%option 8bit reentrant bison-locations -%option never-interactive -%option noyywrap noinput nounput -%option prefix="_mp_equation_" -%option extra-type="MPEquationParserState *" -%option outfile="mp-equation-lexer.c" header-file="mp-equation-lexer.h" - -%{ -/* - * Copyright (C) 2004-2008 Sami Pietila - * Copyright (C) 2008-2011 Robert Ancell - * - * 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. See http://www.gnu.org/copyleft/gpl.html the full text of the - * license. - */ - -#include -#include -#include - -#include "mp-equation-private.h" -#include "mp-equation-parser.h" -#include "mp-equation.h" -%} - - -ZERO "0"|"〇"|"٠"|"۰"|"߀"|"०"|"০"|"੦"|"૦"|"୦"|"௦"|"౦"|"೦"|"൦"|"๐"|"໐"|"༠"|"၀"|"႐"|"០"|"᠐"|"᥆"|"᧐"|"᭐"|"᮰"|"᱀"|"᱐"|"꘠"|"꣐"|"꤀"|"꩐"|"𐒠" -ONE "1"|"〡"|"١"|"۱"|"߁"|"१"|"১"|"੧"|"૧"|"୧"|"௧"|"౧"|"೧"|"൧"|"๑"|"໑"|"༡"|"၁"|"႑"|"១"|"᠑"|"᥇"|"᧑"|"᭑"|"᮱"|"᱁"|"᱑"|"꘡"|"꣑"|"꤁"|"꩑"|"𐒡" -TWO "2"|"〢"|"٢"|"۲"|"߂"|"२"|"২"|"੨"|"૨"|"୨"|"௨"|"౨"|"೨"|"൨"|"๒"|"໒"|"༢"|"၂"|"႒"|"២"|"᠒"|"᥈"|"᧒"|"᭒"|"᮲"|"᱂"|"᱒"|"꘢"|"꣒"|"꤂"|"꩒"|"𐒢" -THREE "3"|"〣"|"٣"|"۳"|"߃"|"३"|"৩"|"੩"|"૩"|"୩"|"௩"|"౩"|"೩"|"൩"|"๓"|"໓"|"༣"|"၃"|"႓"|"៣"|"᠓"|"᥉"|"᧓"|"᭓"|"᮳"|"᱃"|"᱓"|"꘣"|"꣓"|"꤃"|"꩓"|"𐒣" -FOUR "4"|"〤"|"٤"|"۴"|"߄"|"४"|"৪"|"੪"|"૪"|"୪"|"௪"|"౪"|"೪"|"൪"|"๔"|"໔"|"༤"|"၄"|"႔"|"៤"|"᠔"|"᥊"|"᧔"|"᭔"|"᮴"|"᱄"|"᱔"|"꘤"|"꣔"|"꤄"|"꩔"|"𐒤" -FIVE "5"|"〥"|"٥"|"۵"|"߅"|"५"|"৫"|"੫"|"૫"|"୫"|"௫"|"౫"|"೫"|"൫"|"๕"|"໕"|"༥"|"၅"|"႕"|"៥"|"᠕"|"᥋"|"᧕"|"᭕"|"᮵"|"᱅"|"᱕"|"꘥"|"꣕"|"꤅"|"꩕"|"𐒥" -SIX "6"|"〦"|"٦"|"۶"|"߆"|"६"|"৬"|"੬"|"૬"|"୬"|"௬"|"౬"|"೬"|"൬"|"๖"|"໖"|"༦"|"၆"|"႖"|"៦"|"᠖"|"᥌"|"᧖"|"᭖"|"᮶"|"᱆"|"᱖"|"꘦"|"꣖"|"꤆"|"꩖"|"𐒦" -SEVEN "7"|"〧"|"٧"|"۷"|"߇"|"७"|"৭"|"੭"|"૭"|"୭"|"௭"|"౭"|"೭"|"൭"|"๗"|"໗"|"༧"|"၇"|"႗"|"៧"|"᠗"|"᥍"|"᧗"|"᭗"|"᮷"|"᱇"|"᱗"|"꘧"|"꣗"|"꤇"|"꩗"|"𐒧" -EIGHT "8"|"〨"|"٨"|"۸"|"߈"|"८"|"৮"|"੮"|"૮"|"୮"|"௮"|"౮"|"೮"|"൮"|"๘"|"໘"|"༨"|"၈"|"႘"|"៨"|"᠘"|"᥎"|"᧘"|"᭘"|"᮸"|"᱈"|"᱘"|"꘨"|"꣘"|"꤈"|"꩘"|"𐒨" -NINE "9"|"〩"|"٩"|"۹"|"߉"|"९"|"৯"|"੯"|"૯"|"୯"|"௯"|"౯"|"೯"|"൯"|"๙"|"໙"|"༩"|"၉"|"႙"|"៩"|"᠙"|"᥏"|"᧙"|"᭙"|"᮹"|"᱉"|"᱙"|"꘩"|"꣙"|"꤉"|"꩙"|"𐒩" -DECIMAL "."|"," -DEC {ZERO}|{ONE}|{TWO}|{THREE}|{FOUR}|{FIVE}|{SIX}|{SEVEN}|{EIGHT}|{NINE} -HEX {DEC}|[A-Fa-f] -SUPER_DIGITS "⁰"|"¹"|"²"|"³"|"⁴"|"⁵"|"⁶"|"⁷"|"⁸"|"⁹" -SUPER_MINUS "⁻" -SUB_DIGITS "₀"|"₁"|"₂"|"₃"|"₄"|"₅"|"₆"|"₇"|"₈"|"₉" -FRACTION "½"|"⅓"|"⅔"|"¼"|"¾"|"⅕"|"⅖"|"⅗"|"⅘"|"⅙"|"⅚"|"⅛"|"⅜"|"⅝"|"⅞" -GREEKS "α"|"β"|"γ"|"δ"|"ε"|"ζ"|"η"|"θ"|"ι"|"κ"|"λ"|"μ"|"ν"|"ξ"|"ο"|"π"|"ρ"|"ς"|"σ"|"τ"|"υ"|"φ"|"χ"|"ψ"|"ω" -DEGREES "°" -MINUTES "'" -SECONDS "\"" -LETTERS [a-zA-Z]|{GREEKS} - -SUP_NUM {SUPER_DIGITS}+ -NSUP_NUM {SUPER_MINUS}{SUPER_DIGITS}+ -SUB_NUM {SUB_DIGITS}+ -WORD {LETTERS}+ -DEC_NUM {DEC}+|{DEC}*{DECIMAL}{DEC}+ -DEF_NUM {HEX}+|{HEX}*{DECIMAL}{HEX}+ -BASE_NUM {HEX}+{SUB_NUM}|{HEX}*{DECIMAL}{HEX}+{SUB_NUM} -ANGLE_NUM {DEC_NUM}{DEGREES}|{DEC}+{DEGREES}{DEC_NUM}{MINUTES}|{DEC}+{DEGREES}{DEC}+{MINUTES}{DEC_NUM}{SECONDS} - -NUMBER {DEF_NUM}|{BASE_NUM}|{FRACTION}|{DEC}+{FRACTION}|{ANGLE_NUM} -VARIABLE {WORD}|{WORD}{SUB_NUM}|{GREEKS} - -MOD [mM][oO][dD] -AND "∧"|[aA][nN][dD] -OR "∨"|[oO][rR] -XOR "⊻"|"⊕"|[xX][oO][rR] -NOT "¬"|"~"|[nN][oO][tT] -RE "⃰ℜ" -IM "ℑ" -IN [iI][nN] - -%% - -"+" {return tADD;} -"-"|"−" {return tSUBTRACT;} -"*"|"×" {return tMULTIPLY;} -"/"|"∕"|"÷" {return tDIVIDE;} -{MOD} {return tMOD;} -"⌊" {return tLFLOOR;} -"⌋" {return tRFLOOR;} -"⌈" {return tLCEILING;} -"⌉" {return tRCEILING;} -"√" {return tROOT;} -"∛" {return tROOT3;} -"∜" {return tROOT4;} -{NOT} {return tNOT;} -{AND} {return tAND;} -{OR} {return tOR;} -{XOR} {return tXOR;} -{IN} {return tIN;} -{NUMBER} {if (mp_set_from_string(yytext, _mp_equation_get_extra(yyscanner)->options->base, &yylval->int_t) != 0) REJECT; return tNUMBER;} -{SUP_NUM} {yylval->integer = super_atoi(yytext); return tSUPNUM;} -{NSUP_NUM} {yylval->integer = super_atoi(yytext); return tNSUPNUM;} -{SUB_NUM} {yylval->integer = sub_atoi(yytext); return tSUBNUM;} -{VARIABLE} {\ - MPEquationParserState *state = _mp_equation_get_extra(yyscanner);\ - if (state->function_is_defined(state, yytext)) {\ - yylval->name = strdup(yytext);\ - return tFUNCTION;\ - }\ - else {\ - yylval->name = strdup(yytext);\ - return tVARIABLE;\ - }\ -} -[ \r\t\n] -. {return *yytext;} - -%% diff --git a/src/mp-equation-parser.y b/src/mp-equation-parser.y deleted file mode 100644 index cb9e49e1..00000000 --- a/src/mp-equation-parser.y +++ /dev/null @@ -1,261 +0,0 @@ -%{ -/* - * Copyright (C) 2004-2008 Sami Pietila - * Copyright (C) 2008-2011 Robert Ancell - * - * 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. See http://www.gnu.org/copyleft/gpl.html the full text of the - * license. - */ - -#include -#include -#include -#include -#include - -#include "mp-equation-private.h" -#include "mp-equation-parser.h" -#include "mp-equation-lexer.h" - -// fixme support x log x -// treat exp NAME exp as a function always and pass both arguments, i.e. -// can do mod using both and all others use $1 * NAME($3) - -static void set_error(yyscan_t yyscanner, int error, const char *token) -{ - _mp_equation_get_extra(yyscanner)->error = error; - if (token) - _mp_equation_get_extra(yyscanner)->error_token = strdup(token); -} - -static void set_result(yyscan_t yyscanner, const MPNumber *x) -{ - mp_set_from_mp(x, &(_mp_equation_get_extra(yyscanner))->ret); -} - -static char * -utf8_next_char (const char *c) -{ - c++; - while ((*c & 0xC0) == 0x80) - c++; - return (char *)c; -} - -static int get_variable(yyscan_t yyscanner, const char *name, int power, MPNumber *z) -{ - int result = 0; - - /* If defined, then get the variable */ - if (_mp_equation_get_extra(yyscanner)->get_variable(_mp_equation_get_extra(yyscanner), name, z)) { - mp_xpowy_integer(z, power, z); - return 1; - } - - /* If has more than one character then assume a multiplication of variables */ - if (utf8_next_char(name)[0] != '\0') { - const char *c, *next; - char *buffer = malloc(sizeof(char) * strlen(name)); - MPNumber value; - - result = 1; - mp_set_from_integer(1, &value); - for (c = name; *c != '\0'; c = next) { - MPNumber t; - - next = utf8_next_char(c); - snprintf(buffer, next - c + 1, "%s", c); - - if (!_mp_equation_get_extra(yyscanner)->get_variable(_mp_equation_get_extra(yyscanner), buffer, &t)) { - result = 0; - break; - } - - /* If last term do power */ - if (*next == '\0') - mp_xpowy_integer(&t, power, &t); - - mp_multiply(&value, &t, &value); - } - - free(buffer); - if (result) - mp_set_from_mp(&value, z); - } - - if (!result) - set_error(yyscanner, PARSER_ERR_UNKNOWN_VARIABLE, name); - - return result; -} - -static void set_variable(yyscan_t yyscanner, const char *name, MPNumber *x) -{ - _mp_equation_get_extra(yyscanner)->set_variable(_mp_equation_get_extra(yyscanner), name, x); -} - -static int get_function(yyscan_t yyscanner, const char *name, const MPNumber *x, MPNumber *z) -{ - if (!_mp_equation_get_extra(yyscanner)->get_function(_mp_equation_get_extra(yyscanner), name, x, z)) { - set_error(yyscanner, PARSER_ERR_UNKNOWN_FUNCTION, name); - return 0; - } - return 1; -} - -static int get_inverse_function(yyscan_t yyscanner, const char *name, const MPNumber *x, MPNumber *z) -{ - char *inv_name; - int result; - - inv_name = malloc(sizeof(char) * (strlen(name) + strlen("⁻¹") + 1)); - strcpy(inv_name, name); - strcat(inv_name, "⁻¹"); - result = get_function(yyscanner, inv_name, x, z); - free(inv_name); - - return result; -} - -static void do_not(yyscan_t yyscanner, const MPNumber *x, MPNumber *z) -{ - if (!mp_is_overflow(x, _mp_equation_get_extra(yyscanner)->options->wordlen)) { - set_error(yyscanner, PARSER_ERR_OVERFLOW, NULL); - } - mp_not(x, _mp_equation_get_extra(yyscanner)->options->wordlen, z); -} - -static char *make_unit(const char *name, int power) -{ - char *name2; - - // FIXME: Hacky - if (power == 2) { - name2 = malloc(sizeof(char) * (strlen(name) + strlen("²") + 1)); - sprintf(name2, "%s²", name); - } - else if (power == 3) { - name2 = malloc(sizeof(char) * (strlen(name) + strlen("³") + 1)); - sprintf(name2, "%s³", name); - } - else { - name2 = malloc(sizeof(char) * (strlen(name) + strlen("?") + 1)); - sprintf(name2, "%s?", name); - } - - return name2; -} - -static void do_conversion(yyscan_t yyscanner, const MPNumber *x, const char *x_units, const char *z_units, MPNumber *z) -{ - if (!_mp_equation_get_extra(yyscanner)->convert(_mp_equation_get_extra(yyscanner), x, x_units, z_units, z)) - set_error(yyscanner, PARSER_ERR_UNKNOWN_CONVERSION, NULL); -} - -%} - -%pure-parser -%name-prefix="_mp_equation_" -%locations -%parse-param {yyscan_t yyscanner} -%lex-param {yyscan_t yyscanner} - -%union { - MPNumber int_t; - int integer; - char *name; -} - -%left tNUMBER -%left tLFLOOR tRFLOOR tLCEILING tRCEILING -%left UNARY_PLUS -%left tADD tSUBTRACT -%left tAND tOR tXOR tXNOR -%left tMULTIPLY MULTIPLICATION -%left tDIVIDE tMOD -%left tNOT -%left tROOT tROOT3 tROOT4 -%left tVARIABLE tFUNCTION -%right tSUBNUM tSUPNUM tNSUPNUM -%left BOOLEAN_OPERATOR -%left PERCENTAGE -%left UNARY_MINUS -%right '^' '!' '|' -%left tIN - -%type exp variable term -%type unit -%start statement - -%% - -statement: - exp { set_result(yyscanner, &$1); } -| exp '=' { set_result(yyscanner, &$1); } -| tVARIABLE '=' exp {set_variable(yyscanner, $1, &$3); set_result(yyscanner, &$3); } -| tNUMBER unit tIN unit { MPNumber t; do_conversion(yyscanner, &$1, $2, $4, &t); set_result(yyscanner, &t); free($2); free($4); } -| unit tIN unit { MPNumber x, t; mp_set_from_integer(1, &x); do_conversion(yyscanner, &x, $1, $3, &t); set_result(yyscanner, &t); free($1); free($3); } -; - -unit: - tVARIABLE {$$ = $1;} -| tVARIABLE tSUPNUM {$$ = make_unit($1, $2); free($1);} - -/* |x| gets confused and thinks = |x|(...||) */ - -exp: - '(' exp ')' {mp_set_from_mp(&$2, &$$);} -| exp tDIVIDE exp '(' exp ')' {mp_divide(&$1, &$3, &$$); mp_multiply(&$5, &$$, &$$);} -| exp tMOD exp '(' exp ')' {mp_modulus_divide(&$1, &$3, &$$); mp_multiply(&$5, &$$, &$$);} -| exp '(' exp ')' {mp_multiply(&$1, &$3, &$$);} -| tLFLOOR exp tRFLOOR {mp_floor(&$2, &$$);} -| tLCEILING exp tRCEILING {mp_ceiling(&$2, &$$);} -| '[' exp ']' {mp_round(&$2, &$$);} -| '{' exp '}' {mp_fractional_part(&$2, &$$);} -| '|' exp '|' {mp_abs(&$2, &$$);} -| exp '^' exp {mp_xpowy(&$1, &$3, &$$);} -| exp tSUPNUM {mp_xpowy_integer(&$1, $2, &$$);} -| exp tNSUPNUM {mp_xpowy_integer(&$1, $2, &$$);} -| exp '!' {mp_factorial(&$1, &$$);} -| variable {mp_set_from_mp(&$1, &$$);} -| tNUMBER variable %prec MULTIPLICATION {mp_multiply(&$1, &$2, &$$);} -| tSUBTRACT exp %prec UNARY_MINUS {mp_invert_sign(&$2, &$$);} -| tADD tNUMBER %prec UNARY_PLUS {mp_set_from_mp(&$2, &$$);} -| exp tDIVIDE exp {mp_divide(&$1, &$3, &$$);} -| exp tMOD exp {mp_modulus_divide(&$1, &$3, &$$);} -| exp tMULTIPLY exp {mp_multiply(&$1, &$3, &$$);} -| exp tADD exp '%' %prec PERCENTAGE {mp_add_integer(&$3, 100, &$3); mp_divide_integer(&$3, 100, &$3); mp_multiply(&$1, &$3, &$$);} -| exp tSUBTRACT exp '%' %prec PERCENTAGE {mp_add_integer(&$3, -100, &$3); mp_divide_integer(&$3, -100, &$3); mp_multiply(&$1, &$3, &$$);} -| exp tADD exp {mp_add(&$1, &$3, &$$);} -| exp tSUBTRACT exp {mp_subtract(&$1, &$3, &$$);} -| exp '%' {mp_divide_integer(&$1, 100, &$$);} -| tNOT exp {do_not(yyscanner, &$2, &$$);} -| exp tAND exp %prec BOOLEAN_OPERATOR {mp_and(&$1, &$3, &$$);} -| exp tOR exp %prec BOOLEAN_OPERATOR {mp_or(&$1, &$3, &$$);} -| exp tXOR exp %prec BOOLEAN_OPERATOR {mp_xor(&$1, &$3, &$$);} -| tNUMBER {mp_set_from_mp(&$1, &$$);} -; - - -variable: - term {mp_set_from_mp(&$1, &$$);} -| tFUNCTION exp {if (!get_function(yyscanner, $1, &$2, &$$)) YYABORT; free($1);} -| tFUNCTION tSUPNUM exp {if (!get_function(yyscanner, $1, &$3, &$$)) YYABORT; mp_xpowy_integer(&$$, $2, &$$); free($1);} -| tFUNCTION tNSUPNUM exp {if (!get_inverse_function(yyscanner, $1, &$3, &$$)) YYABORT; mp_xpowy_integer(&$$, -$2, &$$); free($1);} -| tVARIABLE tSUPNUM exp {set_error(yyscanner, PARSER_ERR_UNKNOWN_FUNCTION, $1); free($1); YYABORT;} -| tSUBNUM tROOT exp {mp_root(&$3, $1, &$$);} -| tROOT exp {mp_sqrt(&$2, &$$);} -| tROOT3 exp {mp_root(&$2, 3, &$$);} -| tROOT4 exp {mp_root(&$2, 4, &$$);} -; - -term: - tVARIABLE {if (!get_variable(yyscanner, $1, 1, &$$)) YYABORT; free($1);} -| tVARIABLE tSUPNUM {if (!get_variable(yyscanner, $1, $2, &$$)) YYABORT; free($1);} -| term term {mp_multiply(&$1, &$2, &$$);} -; - -%% diff --git a/src/mp-equation-private.h b/src/mp-equation-private.h deleted file mode 100644 index 681fef51..00000000 --- a/src/mp-equation-private.h +++ /dev/null @@ -1,56 +0,0 @@ -/* - * Copyright (C) 2004-2008 Sami Pietila - * Copyright (C) 2008-2009 Robert Ancell - * - * 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. See http://www.gnu.org/copyleft/gpl.html the full text of the - * license. - */ - -#ifndef MP_EQUATION_PRIVATE_H -#define MP_EQUATION_PRIVATE_H - -#include "mp-equation.h" - -typedef struct MPEquationParserState MPEquationParserState; - -/* State for parser */ -struct MPEquationParserState { - /* User provided options */ - MPEquationOptions *options; - - /* Function to check if a variable is defined */ - int (*variable_is_defined)(MPEquationParserState *state, const char *name); - - /* Function to get variable values */ - int (*get_variable)(MPEquationParserState *state, const char *name, MPNumber *z); - - /* Function to set variable values */ - void (*set_variable)(MPEquationParserState *state, const char *name, const MPNumber *x); - - /* Function to check if a function is defined */ - int (*function_is_defined)(MPEquationParserState *state, const char *name); - - /* Function to solve functions */ - int (*get_function)(MPEquationParserState *state, const char *name, const MPNumber *x, MPNumber *z); - - /* Function to convert units */ - int (*convert)(MPEquationParserState *state, const MPNumber *x, const char *x_units, const char *z_units, MPNumber *z); - - // FIXME: get_operator?? - - /* Error returned from parser */ - int error; - - /* Name of token where error occured */ - char *error_token; - - /* Value returned from parser */ - MPNumber ret; -}; - -int _mp_equation_error(void *yylloc, MPEquationParserState *state, char *text); - -#endif diff --git a/src/mp-equation.c b/src/mp-equation.c index addff8ef..9b6a1954 100644 --- a/src/mp-equation.c +++ b/src/mp-equation.c @@ -10,16 +10,12 @@ */ #include - -#include "mp-equation-private.h" -#include "mp-equation-parser.h" -#include "mp-equation-lexer.h" - -extern int _mp_equation_parse(yyscan_t yyscanner); - +#include +#include +#include "parser.h" static int -variable_is_defined(MPEquationParserState *state, const char *name) +variable_is_defined(ParserState *state, const char *name) { /* FIXME: Make more generic */ if (strcmp(name, "e") == 0 || strcmp(name, "i") == 0 || strcmp(name, "π") == 0) @@ -31,7 +27,7 @@ variable_is_defined(MPEquationParserState *state, const char *name) static int -get_variable(MPEquationParserState *state, const char *name, MPNumber *z) +get_variable(ParserState *state, const char *name, MPNumber *z) { int result = 1; @@ -50,7 +46,7 @@ get_variable(MPEquationParserState *state, const char *name, MPNumber *z) } static void -set_variable(MPEquationParserState *state, const char *name, const MPNumber *x) +set_variable(ParserState *state, const char *name, const MPNumber *x) { // Reserved words, e, π, mod, and, or, xor, not, abs, log, ln, sqrt, int, frac, sin, cos, ... if (strcmp(name, "e") == 0 || strcmp(name, "i") == 0 || strcmp(name, "π") == 0) @@ -107,7 +103,7 @@ super_atoi(const char *data) static int -function_is_defined(MPEquationParserState *state, const char *name) +function_is_defined(ParserState *state, const char *name) { char *c, *lower_name; @@ -151,7 +147,7 @@ function_is_defined(MPEquationParserState *state, const char *name) static int -get_function(MPEquationParserState *state, const char *name, const MPNumber *x, MPNumber *z) +get_function(ParserState *state, const char *name, const MPNumber *x, MPNumber *z) { char *c, *lower_name; int result = 1; @@ -239,7 +235,7 @@ get_function(MPEquationParserState *state, const char *name, const MPNumber *x, static int -convert(MPEquationParserState *state, const MPNumber *x, const char *x_units, const char *z_units, MPNumber *z) +convert(ParserState *state, const MPNumber *x, const char *x_units, const char *z_units, MPNumber *z) { if (state->options->convert) return state->options->convert(x, x_units, z_units, z, state->options->callback_data); @@ -252,49 +248,44 @@ MPErrorCode mp_equation_parse(const char *expression, MPEquationOptions *options, MPNumber *result, char **error_token) { int ret; - MPEquationParserState state; - yyscan_t yyscanner; - YY_BUFFER_STATE buffer; + int err; + ParserState* state; + state = p_create_parser (expression, options); if (!(expression && result) || strlen(expression) == 0) return PARSER_ERR_INVALID; - memset(&state, 0, sizeof(MPEquationParserState)); - state.options = options; - state.variable_is_defined = variable_is_defined; - state.get_variable = get_variable; - state.set_variable = set_variable; - state.function_is_defined = function_is_defined; - state.get_function = get_function; - state.convert = convert; - state.error = 0; - + state->variable_is_defined = variable_is_defined; + state->get_variable = get_variable; + state->set_variable = set_variable; + state->function_is_defined = function_is_defined; + state->get_function = get_function; + state->convert = convert; + state->error = 0; mp_clear_error(); - - _mp_equation_lex_init_extra(&state, &yyscanner); - buffer = _mp_equation__scan_string(expression, yyscanner); - - ret = _mp_equation_parse(yyscanner); - if (state.error_token != NULL && error_token != NULL) { - *error_token = state.error_token; + ret = p_parse (state); + if (state->error_token != NULL && error_token != NULL) { + *error_token = state->error_token; } - - _mp_equation__delete_buffer(buffer, yyscanner); - _mp_equation_lex_destroy(yyscanner); - /* Error during parsing */ - if (state.error) - return state.error; + if (state->error) { + err = state->error; + p_destroy_parser (state); + return err; + } - if (mp_get_error()) + if (mp_get_error()) { + p_destroy_parser (state); return PARSER_ERR_MP; + } /* Failed to parse */ - if (ret) + if (ret) { + p_destroy_parser (state); return PARSER_ERR_INVALID; - - mp_set_from_mp(&state.ret, result); - + } + mp_set_from_mp(&state->ret, result); + p_destroy_parser (state); return PARSER_ERR_NONE; } @@ -322,9 +313,3 @@ mp_error_code_to_string(MPErrorCode error_code) return "Unknown parser error"; } } - - -int _mp_equation_error(void *yylloc, MPEquationParserState *state, char *text) -{ - return 0; -} diff --git a/src/parser.c b/src/parser.c new file mode 100644 index 00000000..497f148d --- /dev/null +++ b/src/parser.c @@ -0,0 +1,1228 @@ +#include +#include +#include +#include + +#include "parser.h" +#include "parserfunc.h" +#include "mp-equation.h" + +/* Converts LexerTokenType to Precedence value. */ +static guint +p_get_precedence(LexerTokenType type) +{ + /* WARNING: This function doesn't work for Unary Plus and Unary Minus. Use their precedence directly while inserting them in tree. */ + if(type == T_ADD + ||type == T_SUBTRACT) + return P_AddSubtract; + if(type == T_MULTIPLY) + return P_Multiply; + if(type == T_MOD) + return P_Mod; + if(type == T_DIVIDE) + return P_Divide; + if(type == T_NOT) + return P_Not; + if(type == T_ROOT + ||type == T_ROOT_3 + ||type == T_ROOT_4) + return P_Root; + if(type == T_FUNCTION) + return P_Function; + if(type == T_AND + ||type == T_OR + ||type == T_XOR) + return P_Boolean; + if(type == T_PERCENTAGE) + return P_Percentage; + if(type == T_POWER) + return P_Power; + if(type == T_FACTORIAL) + return P_Factorial; + if(type == T_NUMBER + ||type == T_VARIABLE) + return P_NumberVariable; + return P_Unknown; +} + +/* Return associativity of specific token type from precedence. */ +static Associativity +p_get_associativity_p(Precedence type) +{ + if(type == P_Boolean + ||type == P_Divide + ||type == P_Mod + ||type == P_Multiply + ||type == P_AddSubtract) + return LEFT_ASSOCIATIVE; + if(type == P_Power) + return RIGHT_ASSOCIATIVE; + /* For all remaining / non-associative operators, return Left Associativity. */ + return LEFT_ASSOCIATIVE; +} + +/* Return associativity of specific token by converting it to precedence first. */ +static Associativity +p_get_associativity(LexerToken* token) +{ + return p_get_associativity_p(p_get_precedence(token->token_type)); +} + +/* Generate precedence for a node from precedence value. Includes depth_level. */ +static guint +p_make_precedence_p(ParserState* state, Precedence p) +{ + return (p + (state->depth_level * P_Depth)); +} + +/* Generate precedence for a node from lexer token type. Includes depth_level. */ +static guint +p_make_precedence_t(ParserState* state, LexerTokenType type) +{ + return (p_get_precedence(type) + (state->depth_level * P_Depth)); +} + +/* Allocate and create a new node. */ +static ParseNode* +p_create_node(ParserState* state, LexerToken* token, guint precedence, Associativity associativity, void* value, void* (*function)(ParseNode*)) +{ + ParseNode* new; + new = (ParseNode*) malloc(sizeof(ParseNode)); + assert(new != NULL); + new->parent = NULL; + new->left = NULL; + new->right = NULL; + new->token = token; + new->precedence = precedence; + new->associativity = associativity; + new->value = value; + new->state = state; + new->evaluate = function; + return new; +} + +/* Compares two nodes to decide, which will be parent and which willbe child. */ +static gint +p_cmp_nodes(ParseNode* left, ParseNode* right) +{ + /* Return values. + 1 = right goes up (near root) in parse tree. + 0 = left goes up (near root) in parse tree. + */ + if(left == NULL) + return 0; + if(left->precedence > right->precedence) + { + return 1; + } + else if(left->precedence < right->precedence) + { + return 0; + } + else + { + if(right->associativity == RIGHT_ASSOCIATIVE) + { + return 0; + } + else + { + return 1; + } + } +} + +/* Unified interface (unary and binary nodes) to insert node into parse tree. */ +static void +p_insert_into_tree_all(ParserState* state, ParseNode* node, guint unary_function) +{ + if(state->root == NULL) + { + state->root = node; + state->right_most = state->root; + return; + } + ParseNode* tmp = state->right_most; + while(p_cmp_nodes(tmp, node)) + tmp = tmp->parent; + if(unary_function) + { + /* If tmp is null, that means, we have to insert new node at root. */ + if(tmp == NULL) + { + node->right = state->root; + node->right->parent = node; + + state->root = node; + } + else + { + node->right = tmp->right; + if(node->right) + node->right->parent = node; + + tmp->right = node; + if(tmp->right) + tmp->right->parent = tmp; + + } + state->right_most = node; + while(state->right_most->right != NULL) + state->right_most = state->right_most->right; + } + else + { + /* If tmp is null, that means, we have to insert new node at root. */ + if(tmp == NULL) + { + node->left = state->root; + node->left->parent = node; + + state->root = node; + } + else + { + node->left = tmp->right; + if(node->left) + node->left->parent = node; + + tmp->right = node; + if(tmp->right) + tmp->right->parent = tmp; + + } + state->right_most = node; + } +} + +/* Insert binary node into the parse tree. */ +static void +p_insert_into_tree(ParserState* state, ParseNode* node) +{ + p_insert_into_tree_all(state, node, 0); +} + +/* Insert unary node into the parse tree. */ +static void +p_insert_into_tree_unary(ParserState* state, ParseNode* node) +{ + p_insert_into_tree_all(state, node, 1); +} + +/* Recursive call to free every node of parse-tree. */ +static void +p_destroy_all_nodes(ParseNode* node) +{ + if(node == NULL) + return; + p_destroy_all_nodes(node->left); + p_destroy_all_nodes(node->right); + /* Don't call free for tokens, as they are allocated and freed in lexer. */ + /* WARNING: If node->value is freed elsewhere, please assign it NULL before calling p_destroy_all_nodes(). */ + if(node->value) + free(node->value); + free(node); +} + +/* Create parser state. */ +ParserState* +p_create_parser(const gchar* input, MPEquationOptions* options) +{ + ParserState* state; + state = (ParserState*) malloc(sizeof(ParserState)); + assert(state != NULL); + state->lexer = l_create_lexer(input, state); + state->root = NULL; + state->depth_level = 0; + state->right_most = NULL; + state->options = options; + state->error = 0; + state->error_token = NULL; + return state; +} + +static guint statement (ParserState*); +/* Start parsing input string. And call evaluate on success. */ +guint +p_parse(ParserState* state) +{ + guint ret; + LexerToken* token; + MPNumber* ans; + l_insert_all_tokens(state->lexer); + ret = statement(state); + token = l_get_next_token(state->lexer); + if(token->token_type == T_ASSIGN) + { + token = l_get_next_token(state->lexer); + if(token->token_type != PL_EOS) + { + /* Full string is not parsed. */ + if(!state->error) + set_error(state, PARSER_ERR_INVALID, token->string); + return PARSER_ERR_INVALID; + } + } + if(token->token_type != PL_EOS) + { + /* Full string is not parsed. */ + if(!state->error) + set_error(state, PARSER_ERR_INVALID, token->string); + return PARSER_ERR_INVALID; + } + if(ret == 0) + /* Input can't be parsed with grammar. */ + return PARSER_ERR_INVALID; + ans = (MPNumber *) (*(state->root->evaluate))(state->root); + if(ans) + { + mp_set_from_mp(ans, &state->ret); + free(ans); + return PARSER_ERR_NONE; + } + return PARSER_ERR_INVALID; +} + +/* Destroy parser state. */ +void +p_destroy_parser(ParserState* state) +{ + /* If state has a parse tree, destroy it first. */ + if(state->root) + { + p_destroy_all_nodes(state->root); + } + l_destroy_lexer(state->lexer); + free(state); +} + +/* LL (*) parser. Lookahead count depends on tokens. Handle with care. :P */ + +static guint expression(ParserState* state); +static guint expression_1(ParserState* state); +static guint expression_2(ParserState* state); +static guint unit(ParserState* state); +static guint variable(ParserState* state); +static guint term(ParserState* state); +static guint term_2(ParserState* state); + +/* Helping function to p_check_variable. */ +static gchar* +utf8_next_char(const gchar* c) +{ + c++; + while((*c & 0xC0) == 0x80) + c++; + return (gchar *)c; +} + +/* Check if string "name" is a valid variable for given ParserState. It is the same code, used to get the value of variable in parserfunc.c. */ +static gboolean +p_check_variable(ParserState* state, gchar* name) +{ + gint result = 0; + + const gchar *c, *next; + gchar *buffer; + MPNumber temp; + + if(!(state->get_variable)) + { + return FALSE; + } + + /* If defined, then get the variable */ + if((*(state->get_variable))(state, name, &temp)) + { + return TRUE; + } + + /* If has more than one character then assume a multiplication of variables */ + if(utf8_next_char(name)[0] != '\0') + { + result = 1; + buffer = (gchar*) malloc(sizeof(gchar) * strlen(name)); + for(c = name; *c != '\0'; c = next) + { + next = utf8_next_char(c); + snprintf(buffer, next - c + 1, "%s", c); + if(!(*(state->get_variable))(state, buffer, &temp)) + { + result = 0; + break; + } + } + free(buffer); + } + if(!result) + { + return FALSE; + } + return TRUE; +} + +static guint +statement(ParserState* state) +{ + LexerToken* token; + LexerToken* token_old; + ParseNode* node; + token = l_get_next_token(state->lexer); + if(token->token_type == T_VARIABLE) + { + token_old = token; + token = l_get_next_token(state->lexer); + if(token->token_type == T_ASSIGN) + { + /* VARIABLE = expression. */ + + node = p_create_node(state, token_old, p_make_precedence_p(state, P_NumberVariable), p_get_associativity(token_old), NULL, pf_none); + p_insert_into_tree(state, node); + + node = p_create_node(state, token, 0, p_get_associativity(token), NULL, pf_set_var); + p_insert_into_tree(state, node); + + if(!expression(state)) + return 0; + return 1; + } + else if(token->token_type == T_IN) + { + /* UNIT in UNIT. */ + l_roll_back(state->lexer); + l_roll_back(state->lexer); + if(!unit(state)) + return 0; + l_get_next_token(state->lexer); + + node = p_create_node(state, token, 0, p_get_associativity(token), NULL, pf_convert_1); + p_insert_into_tree(state, node); + + if(!unit(state)) + return 0; + return 1; + } + else if(token->token_type == T_SUP_NUMBER) + { + token = l_get_next_token(state->lexer); + if(token->token_type == T_IN) + { + /* UNIT in UNIT */ + l_roll_back(state->lexer); + l_roll_back(state->lexer); + l_roll_back(state->lexer); + if(!unit(state)) + return 0; + l_get_next_token(state->lexer); + + node = p_create_node(state, token, 0, p_get_associativity(token), NULL, pf_convert_1); + p_insert_into_tree(state, node); + + if(!unit(state)) + return 0; + return 1; + } + else + { + l_roll_back(state->lexer); + l_roll_back(state->lexer); + l_roll_back(state->lexer); + if(!expression(state)) + return 0; + return 1; + } + } + else + { + l_roll_back(state->lexer); + l_roll_back(state->lexer); + if(!expression(state)) + return 0; + return 1; + } + } + else if(token->token_type == T_NUMBER) + { + token_old = token; + token = l_get_next_token(state->lexer); + if(token->token_type == T_VARIABLE) + { + token = l_get_next_token(state->lexer); + if(token->token_type == T_IN) + { + /* NUMBER UNIT in UNIT */ + l_roll_back(state->lexer); + l_roll_back(state->lexer); + + node = p_create_node(state, token_old, p_make_precedence_t(state, token_old->token_type), p_get_associativity(token), NULL, pf_constant); + p_insert_into_tree(state, node); + + if(!unit(state)) + return 0; + token = l_get_next_token(state->lexer); + + node = p_create_node(state, token, 0, p_get_associativity(token), NULL, pf_convert_number); + p_insert_into_tree(state, node); + + if(!unit(state)) + return 0; + return 1; + } + else if(token->token_type == T_SUP_NUMBER) + { + token = l_get_next_token(state->lexer); + if(token->token_type == T_IN) + { + /* NUMBER UNIT in UNIT */ + l_roll_back(state->lexer); + l_roll_back(state->lexer); + l_roll_back(state->lexer); + + node = p_create_node(state, token_old, p_make_precedence_t(state, token_old->token_type), p_get_associativity(token), NULL, pf_constant); + p_insert_into_tree(state, node); + + if(!unit(state)) + return 0; + token = l_get_next_token(state->lexer); + + node = p_create_node(state, token, 0, p_get_associativity(token), NULL, pf_convert_number); + p_insert_into_tree(state, node); + + if(!unit(state)) + return 0; + return 1; + } + else + { + l_roll_back(state->lexer); + l_roll_back(state->lexer); + l_roll_back(state->lexer); + l_roll_back(state->lexer); + if(!expression(state)) + return 0; + return 1; + } + } + else + { + l_roll_back(state->lexer); + l_roll_back(state->lexer); + l_roll_back(state->lexer); + if(!expression(state)) + return 0; + return 1; + } + } + else + { + l_roll_back(state->lexer); + l_roll_back(state->lexer); + if(!expression(state)) + return 0; + return 1; + } + } + else + { + l_roll_back(state->lexer); + if(!expression(state)) + return 0; + return 1; + } +} + +static guint +unit(ParserState* state) +{ + LexerToken* token; + LexerToken* token_old; + ParseNode* node; + token = l_get_next_token(state->lexer); + if(token->token_type == T_VARIABLE) + { + token_old = token; + token = l_get_next_token(state->lexer); + if(token->token_type == T_SUP_NUMBER) + { + /* VARIABLE POWER */ + + node = p_create_node(state, token_old, p_make_precedence_t(state, token_old->token_type), p_get_associativity(token_old), pf_make_unit(token_old->string, token->string), pf_none); + p_insert_into_tree(state, node); + + return 1; + } + else + { + l_roll_back(state->lexer); + /* VARIABLE */ + + node = p_create_node(state, token_old, p_make_precedence_t(state, token_old->token_type), p_get_associativity(token_old), NULL, pf_none); + p_insert_into_tree(state, node); + + return 1; + } + } + else + { + l_roll_back(state->lexer); + return 0; + } +} + +static guint +expression(ParserState* state) +{ + if(!expression_1(state)) + return 0; + if(!expression_2(state)) + return 0; + return 1; +} + +static guint +expression_1(ParserState* state) +{ + LexerToken* token; + ParseNode* node; + token = l_get_next_token(state->lexer); + if(token->token_type == PL_EOS + ||token->token_type == T_ASSIGN) + { + l_roll_back(state->lexer); + return 0; + } + if(token->token_type == T_L_R_BRACKET) + { + state->depth_level++; + if(!expression(state)) + return 0; + token = l_get_next_token(state->lexer); + if(token->token_type == T_R_R_BRACKET) + { + state->depth_level--; + return 1; + } + else + //Expected ")" here... + return 0; + } + else if(token->token_type == T_L_S_BRACKET) + { + state->depth_level++; + + /* Give round, preference of P_Unknown aka 0, to keep it on the top of expression. */ + + node = p_create_node(state, token, p_make_precedence_p(state, P_Unknown), p_get_associativity(token), NULL, pf_do_round); + p_insert_into_tree_unary(state, node); + + if(!expression(state)) + return 0; + token = l_get_next_token(state->lexer); + if(token->token_type == T_R_S_BRACKET) + { + state->depth_level--; + return 1; + } + else + //Expected "]" here... + return 0; + } + else if(token->token_type == T_L_C_BRACKET) + { + state->depth_level++; + + /* Give fraction, preference of P_Unknown aka 0, to keep it on the top of expression. */ + + node = p_create_node(state, token, p_make_precedence_p(state, P_Unknown), p_get_associativity(token), NULL, pf_do_fraction); + p_insert_into_tree_unary(state, node); + + if(!expression(state)) + return 0; + token = l_get_next_token(state->lexer); + if(token->token_type == T_R_C_BRACKET) + { + state->depth_level--; + return 1; + } + else + //Expected "}" here... + return 0; + } + else if(token->token_type == T_ABS) + { + state->depth_level++; + + /* Give abs, preference of P_Unknown aka 0, to keep it on the top of expression. */ + + node = p_create_node(state, token, p_make_precedence_p(state, P_Unknown), p_get_associativity(token), NULL, pf_do_abs); + p_insert_into_tree_unary(state, node); + + if(!expression(state)) + return 0; + token = l_get_next_token(state->lexer); + if(token->token_type == T_ABS) + { + state->depth_level--; + return 1; + } + else + //Expected "|" here... + return 0; + } + else if(token->token_type == T_NOT) + { + /* NOT expression */ + + node = p_create_node(state, token, p_make_precedence_p(state, P_Not), p_get_associativity(token), NULL, pf_do_not); + p_insert_into_tree_unary(state, node); + + if(!expression(state)) + return 0; + return 1; + } + else if(token->token_type == T_NUMBER) + { + /* NUMBER */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_constant); + p_insert_into_tree(state, node); + + token = l_get_next_token(state->lexer); + l_roll_back(state->lexer); + + if(token->token_type == T_FUNCTION + ||token->token_type == T_VARIABLE + ||token->token_type == T_SUB_NUMBER + ||token->token_type == T_ROOT + ||token->token_type == T_ROOT_3 + ||token->token_type == T_ROOT_4) + { + /* NUMBER variable. */ + + node = p_create_node(state, NULL, p_make_precedence_p(state, P_Multiply), p_get_associativity_p(P_Multiply), NULL, pf_do_multiply); + p_insert_into_tree(state, node); + + if(!variable(state)) + return 0; + else + return 1; + } + else + { + return 1; + } + } + else if(token->token_type == T_L_FLOOR) + { + state->depth_level++; + /* Give floor, preference of P_Unknown aka 0, to keep it on the top of expression. */ + + node = p_create_node(state, NULL, p_make_precedence_p(state, P_Unknown), p_get_associativity_p(P_Unknown), NULL, pf_do_floor); + p_insert_into_tree_unary(state, node); + + if(!expression(state)) + return 0; + token = l_get_next_token(state->lexer); + if(token->token_type == T_R_FLOOR) + { + state->depth_level--; + return 1; + } + else + //Expected ⌋ here... + return 0; + } + else if(token->token_type == T_L_CEILING) + { + state->depth_level++; + /* Give ceiling, preference of P_Unknown aka 0, to keep it on the top of expression. */ + + node = p_create_node(state, NULL, p_make_precedence_p(state, P_Unknown), p_get_associativity_p(P_Unknown), NULL, pf_do_ceiling); + p_insert_into_tree_unary(state, node); + + if(!expression(state)) + return 0; + token = l_get_next_token(state->lexer); + if(token->token_type == T_R_CEILING) + { + state->depth_level--; + return 1; + } + else + //Expected ⌉ here... + return 0; + } + else if(token->token_type == T_SUBTRACT) + { + /* UnaryMinus expression */ + + node = p_create_node(state, token, p_make_precedence_p(state, P_UnaryMinus), p_get_associativity_p(P_UnaryMinus), NULL, pf_unary_minus); + p_insert_into_tree_unary(state, node); + + if(!expression_1(state)) + return 0; + return 1; + } + else if(token->token_type == T_ADD) + { + token = l_get_next_token(state->lexer); + if(token->token_type == T_NUMBER) + { + /* UnaryPlus expression */ + /* Ignore T_ADD. It is not required. */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_constant); + p_insert_into_tree(state, node); + return 1; + } + else + { + return 0; + } + } + else + { + l_roll_back(state->lexer); + if(!variable(state)) + return 0; + else + return 1; + } +} + +static guint +expression_2(ParserState* state) +{ + LexerToken* token; + ParseNode* node; + token = l_get_next_token(state->lexer); + if(token->token_type == T_L_R_BRACKET) + { + /* expression "(" expression ")" */ + + node = p_create_node(state, NULL, p_make_precedence_p(state, P_Multiply), p_get_associativity_p(P_Multiply), NULL, pf_do_multiply); + p_insert_into_tree(state, node); + + state->depth_level++; + if(!expression(state)) + return 0; + token = l_get_next_token(state->lexer); + if(token->token_type == T_R_R_BRACKET) + { + state->depth_level--; + if(!expression_2(state)) + return 0; + return 1; + } + else + { + return 0; + } + } + else if(token->token_type == T_POWER) + { + /* expression "^" expression */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_do_x_pow_y); + p_insert_into_tree(state, node); + + if(!expression_1(state)) + return 0; + if(!expression_2(state)) + return 0; + return 1; + } + else if(token->token_type == T_SUP_NUMBER) + { + /* expression T_SUP_NUMBER */ + + node = p_create_node(state, NULL, p_make_precedence_p(state, P_Power), p_get_associativity_p(P_Power), NULL, pf_do_x_pow_y_int); + p_insert_into_tree(state, node); + + node = p_create_node(state, token, p_make_precedence_p(state, P_NumberVariable), p_get_associativity_p(P_NumberVariable), NULL, pf_none); + p_insert_into_tree(state, node); + + if(!expression_2(state)) + return 0; + return 1; + } + else if(token->token_type == T_NSUP_NUMBER) + { + /* expression T_NSUP_NUMBER */ + + node = p_create_node(state, NULL, p_make_precedence_p(state, P_Power), p_get_associativity_p(P_Power), NULL, pf_do_x_pow_y_int); + p_insert_into_tree(state, node); + + node = p_create_node(state, token, p_make_precedence_p(state, P_NumberVariable), p_get_associativity_p(P_NumberVariable), NULL, pf_none); + p_insert_into_tree(state, node); + + if(!expression_2(state)) + return 0; + return 1; + } + else if(token->token_type == T_FACTORIAL) + { + /* expression T_FACTORIAL */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_do_factorial); + p_insert_into_tree_unary(state, node); + + if(!expression_2(state)) + return 0; + return 1; + } + else if(token->token_type == T_MULTIPLY) + { + /* expression T_MULTIPLY expression */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_do_multiply); + p_insert_into_tree(state, node); + + if(!expression_1(state)) + return 0; + if(!expression_2(state)) + return 0; + return 1; + } + else if(token->token_type == T_PERCENTAGE) + { + /* expression % */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_do_percent); + p_insert_into_tree_unary(state, node); + + if(!expression_2(state)) + return 0; + return 1; + } + else if(token->token_type == T_AND) + { + /* expression T_AND expression */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_do_and); + p_insert_into_tree(state, node); + + if(!expression_1(state)) + return 0; + if(!expression_2(state)) + return 0; + return 1; + } + else if(token->token_type == T_OR) + { + /* expression T_OR expression */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_do_or); + p_insert_into_tree(state, node); + + if(!expression_1(state)) + return 0; + if(!expression_2(state)) + return 0; + return 1; + } + else if(token->token_type == T_XOR) + { + /* expression T_XOR expression */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_do_xor); + p_insert_into_tree(state, node); + + if(!expression_1(state)) + return 0; + if(!expression_2(state)) + return 0; + return 1; + } + else if(token->token_type == T_DIVIDE) + { + /* expression T_DIVIDE expression */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_do_divide); + p_insert_into_tree(state, node); + + if(!expression_1(state)) + return 0; + if(!expression_2(state)) + return 0; + return 1; + } + else if(token->token_type == T_MOD) + { + /* expression T_MOD expression */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_do_mod); + p_insert_into_tree(state, node); + + if(!expression_1(state)) + return 0; + if(!expression_2(state)) + return 0; + return 1; + } + else if(token->token_type == T_ADD) + { + /* expression T_ADD expression */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_do_add); + p_insert_into_tree(state, node); + + if(!expression_1(state)) + return 0; + token = l_get_next_token(state->lexer); + if(token->token_type == T_PERCENTAGE) + { + //FIXME: This condition needs to be verified for all cases.. :( + if(node->right->precedence > P_Percentage) + { + node->precedence = P_Percentage; + node->evaluate = pf_do_add_percent; + return 1; + } + else + { + /* Assume '%' to be part of 'expression T_PERCENTAGE' statement. */ + l_roll_back(state->lexer); + if(!expression_2(state)) + return 1; + } + } + else + { + l_roll_back(state->lexer); + } + if(!expression_2(state)) + return 0; + return 1; + } + else if(token->token_type == T_SUBTRACT) + { + /* expression T_SUBTRACT expression */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_do_subtract); + p_insert_into_tree(state, node); + + if(!expression_1(state)) + return 0; + token = l_get_next_token(state->lexer); + if(token->token_type == T_PERCENTAGE) + { + //FIXME: This condition needs to be verified for all cases.. :( + if(node->right->precedence > P_Percentage) + { + node->precedence = P_Percentage; + node->evaluate = pf_do_subtract_percent; + return 1; + } + else + { + /* Assume '%' to be part of 'expression T_PERCENTAGE' statement. */ + l_roll_back(state->lexer); + if(!expression_2 (state)) + return 1; + } + } + else + { + l_roll_back(state->lexer); + } + if(!expression_2(state)) + return 0; + return 1; + } + else + { + l_roll_back(state->lexer); + return 1; + } +} + +static guint +variable(ParserState* state) +{ + LexerToken* token; + LexerToken* token_old; + ParseNode* node; + token = l_get_next_token(state->lexer); + if(token->token_type == T_FUNCTION) + { + token_old = token; + token = l_get_next_token(state->lexer); + if(token->token_type == T_SUP_NUMBER) + { + /* FUNCTION SUP_NUMBER expression */ + /* Pass power as void * value. That will be taken care in pf_apply_func_with_powre. */ + + node = p_create_node(state, token_old, p_make_precedence_t(state, token_old->token_type), p_get_associativity(token_old), token, pf_apply_func_with_power); + p_insert_into_tree_unary(state, node); + + if(!expression(state)) + return 0; + return 1; + } + else if(token->token_type == T_NSUP_NUMBER) + { + /* FUNCTION NSUP_NUMBER expression */ + /* Pass power as void * value. That will be taken care in pf_apply_func_with_npowre. */ + + node = p_create_node(state, token_old, p_make_precedence_t(state, token_old->token_type), p_get_associativity(token_old), token, pf_apply_func_with_npower); + p_insert_into_tree_unary(state, node); + + if(!expression(state)) + return 0; + return 1; + } + else + { + l_roll_back(state->lexer); + /* FUNCTION expression */ + + node = p_create_node(state, token_old, p_make_precedence_t(state, token_old->token_type), p_get_associativity(token_old), NULL, pf_apply_func); + p_insert_into_tree_unary(state, node); + + if(!expression(state)) + return 0; + return 1; + } + } + else if(token->token_type == T_SUB_NUMBER) + { + token_old = token; + token = l_get_next_token(state->lexer); + if(token->token_type == T_ROOT) + { + /* SUB_NUM ROOT expression */ + /* Pass SUB_NUM as void* value in node. pf_do_nth_root will take care of it. */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), token_old, pf_do_nth_root); + p_insert_into_tree_unary(state, node); + + if(!expression (state)) + return 0; + return 1; + } + else + { + return 0; + } + } + else if(token->token_type == T_ROOT) + { + /* ROOT expression */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_do_sqrt); + p_insert_into_tree_unary(state, node); + + if(!expression(state)) + return 0; + return 1; + } + else if(token->token_type == T_ROOT_3) + { + /* ROOT_3 expression */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_do_root_3); + p_insert_into_tree_unary(state, node); + + if(!expression(state)) + return 0; + return 1; + } + else if(token->token_type == T_ROOT_4) + { + /* ROOT_4 expression */ + + node = p_create_node(state, token, p_make_precedence_t(state, token->token_type), p_get_associativity(token), NULL, pf_do_root_4); + p_insert_into_tree_unary(state, node); + + if(!expression(state)) + return 0; + return 1; + } + else if(token->token_type == T_VARIABLE) + { + l_roll_back(state->lexer); + //TODO: unknown function ERROR for (T_VARIABLE T_SUP_NUMBER expression). + if(!term(state)) + return 0; + return 1; + } + else + { + return 0; + } +} + +static guint +term(ParserState* state) +{ + LexerToken* token; + LexerToken* token_old; + ParseNode* node; + token = l_get_next_token(state->lexer); + if(token->token_type == T_VARIABLE) + { + token_old = token; + /* Check if the token is a valid variable or not. */ + if(!p_check_variable(state, token->string)) + { + set_error(state, PARSER_ERR_UNKNOWN_VARIABLE, token->string); + return 0; + } + token = l_get_next_token(state->lexer); + if(token->token_type == T_SUP_NUMBER) + { + /* VARIABLE SUP_NUMBER */ + /* Pass power as void* value. pf_get_variable_with_power will take care of it. */ + + node = p_create_node(state, token_old, p_make_precedence_t(state, token_old->token_type), p_get_associativity(token_old), token, pf_get_variable_with_power); + p_insert_into_tree(state, node); + + } + else + { + l_roll_back(state->lexer); + /* VARIABLE */ + + node = p_create_node(state, token_old, p_make_precedence_t(state, token_old->token_type), p_get_associativity(token_old), NULL, pf_get_variable); + p_insert_into_tree(state, node); + + } + if(!term_2(state)) + return 0; + return 1; + } + else + { + return 0; + } +} + +static guint +term_2(ParserState* state) +{ + LexerToken* token; + ParseNode* node; + token = l_get_next_token(state->lexer); + l_roll_back(state->lexer); + if(token->token_type == PL_EOS + ||token->token_type == T_ASSIGN) + { + return 1; + } + if(token->token_type == T_VARIABLE) + { + /* Insert multiply in between two distinct (variable). */ + + node = p_create_node(state, NULL, p_make_precedence_p(state, P_Multiply), p_get_associativity_p(P_Multiply), NULL, pf_do_multiply); + p_insert_into_tree(state, node); + + if(!term(state)) + return 0; + return 1; + } + else + { + return 1; + } +} diff --git a/src/parser.h b/src/parser.h new file mode 100644 index 00000000..3efaa033 --- /dev/null +++ b/src/parser.h @@ -0,0 +1,79 @@ +#ifndef PARSER_H +#define PARSER_H + +#include + +#include "mp-equation.h" +#include "mp.h" + +/* Operator Associativity. */ +typedef enum +{ + LEFT_ASSOCIATIVE, + RIGHT_ASSOCIATIVE +} Associativity; + +/* Operator Precedence. */ +typedef enum +{ + P_Unknown = 0, + P_AddSubtract=1, + P_Multiply=2, + P_Mod=3, + P_Divide=4, + P_Not=5, + P_Root=6, + P_Function=7, + P_Boolean=8, + P_Percentage=9, + /* UnaryMinus and Power must have same precedence. */ + P_UnaryMinus=10, + P_Power=10, + P_Factorial=11, + P_NumberVariable=12, + /* P_Depth should be always at the bottom. It stops node jumping off the current depth level. */ + P_Depth +} Precedence; + +/* ParseNode structure for parse tree. */ +typedef struct parse_node +{ + struct parse_node *parent; + struct parse_node *left, *right; + LexerToken *token; + guint precedence; + Associativity associativity; + void* value; + struct parser_state* state; + void* (*evaluate) (struct parse_node* self); +} ParseNode; + +/* ParserState structure. Stores parser state. */ +typedef struct parser_state +{ + ParseNode *root; + ParseNode *right_most; + LexerState *lexer; + guint depth_level; + MPEquationOptions *options; + int error; + char *error_token; + MPNumber ret; + int (*variable_is_defined)(struct parser_state *state, const char *name); + int (*get_variable)(struct parser_state *state, const char *name, MPNumber *z); + void (*set_variable)(struct parser_state *state, const char *name, const MPNumber *x); + int (*function_is_defined)(struct parser_state *state, const char *name); + int (*get_function)(struct parser_state *state, const char *name, const MPNumber *x, MPNumber *z); + int (*convert)(struct parser_state *state, const MPNumber *x, const char *x_units, const char *z_units, MPNumber *z); +} ParserState; + +/* Create ParserState object. */ +ParserState* p_create_parser(const gchar*, MPEquationOptions*); + +/* Destroy ParserState object. */ +void p_destroy_parser(ParserState*); + +/* Parse string from ParserState. */ +guint p_parse(ParserState*); + +#endif /* PARSER_H */ diff --git a/src/parserfunc.c b/src/parserfunc.c new file mode 100644 index 00000000..edd34f68 --- /dev/null +++ b/src/parserfunc.c @@ -0,0 +1,967 @@ +#include +#include +#include +#include + +#include "parser.h" +#include "parserfunc.h" + +/* Register error variables in ParserState structure. */ +void +set_error(ParserState* state, gint errorno, const gchar *token) +{ + state->error = errorno; + if(token) + state->error_token = strdup(token); +} + +/* Unused function pointer. This won't be called anytime. */ +void* +pf_none(ParseNode* self) +{ + return NULL; +} + +/* Set variable. */ +void* +pf_set_var(ParseNode* self) +{ + MPNumber* val; + val = (MPNumber *) (*(self->right->evaluate))(self->right); + if(!val || !(self->state->set_variable)) + { + if(val) + free(val); + return NULL; + } + (*(self->state->set_variable))(self->state, self->left->token->string, val); + return val; +} + +/* Converts Number from one unit to other. */ +void* +pf_convert_number(ParseNode* self) +{ + gchar* from; + gchar* to; + gint free_from = 0; + gint free_to = 0; + MPNumber tmp; + MPNumber* ans; + ans = (MPNumber *) malloc(sizeof(MPNumber)); + if(self->left->value) + { + from = (gchar*) self->left->value; + free_from = 1; + } + else + from = self->left->token->string; + if(self->right->value) + { + to = (gchar*) self->right->value; + free_to = 1; + } + else + to = self->right->token->string; + + if(mp_set_from_string(self->left->left->token->string, self->state->options->base, &tmp) != 0) + { + free(ans); + ans = NULL; + goto END_PF_CONVERT_NUMBER; + } + if(!(self->state->convert)) + { + free(ans); + ans = NULL; + goto END_PF_CONVERT_NUMBER; + } + if(!(*(self->state->convert))(self->state, &tmp, from, to, ans)) + { + set_error(self->state, PARSER_ERR_UNKNOWN_CONVERSION, NULL); + free(ans); + ans = NULL; + } +END_PF_CONVERT_NUMBER: + if(free_from) + { + g_free(self->left->value); + self->left->value = NULL; + } + if(free_to) + { + g_free(self->right->value); + self->right->value = NULL; + } + return ans; +} + +/* Conversion rate. */ +void* +pf_convert_1(ParseNode* self ) +{ + gchar* from; + gchar* to; + gint free_from = 0; + gint free_to = 0; + MPNumber tmp; + MPNumber* ans; + ans = (MPNumber *) malloc(sizeof(MPNumber)); + if(self->left->value) + { + from = (gchar*) self->left->value; + free_from = 1; + } + else + from = self->left->token->string; + if(self->right->value) + { + to = (gchar*) self->right->value; + free_to = 1; + } + else + to = self->right->token->string; + mp_set_from_integer(1, &tmp); + if(!(self->state->convert)) + { + free(ans); + return NULL; + } + if(!(*(self->state->convert))(self->state, &tmp, from, to, ans)) + { + set_error(self->state, PARSER_ERR_UNKNOWN_CONVERSION, NULL); + free(ans); + ans = NULL; + } + if(free_from) + { + g_free(self->left->value); + self->left->value = NULL; + } + if(free_to) + { + g_free(self->right->value); + self->right->value = NULL; + } + return ans; +} + +/* Join source unit and power. */ +gchar* +pf_make_unit(gchar* source, gchar* power) +{ + return g_strjoin(NULL, source, power, NULL); +} + +static gchar * +utf8_next_char(const gchar *c) +{ + c++; + while((*c & 0xC0) == 0x80) + c++; + return(gchar *) c; +} + +/* Get value of variable. */ +void* +pf_get_variable(ParseNode* self) +{ + gint result = 0; + + const gchar *c, *next; + gchar *buffer; + MPNumber value; + + MPNumber t; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + + if(!(self->state->get_variable)) + { + free(ans); + return NULL; + } + + /* If defined, then get the variable */ + if((*(self->state->get_variable))(self->state, self->token->string, ans)) + { + return ans; + } + + /* If has more than one character then assume a multiplication of variables */ + if(utf8_next_char(self->token->string)[0] != '\0') + { + result = 1; + buffer = (gchar*) malloc(sizeof(gchar) * strlen(self->token->string)); + mp_set_from_integer(1, &value); + for(c = self->token->string; *c != '\0'; c = next) + { + next = utf8_next_char(c); + snprintf(buffer, next - c + 1, "%s", c); + if(!(*(self->state->get_variable))(self->state, buffer, &t)) + { + result = 0; + break; + } + mp_multiply(&value, &t, &value); + } + free(buffer); + if(result) + mp_set_from_mp(&value, ans); + } + if(!result) + { + free (ans); + ans = NULL; + set_error(self->state, PARSER_ERR_UNKNOWN_VARIABLE, self->token->string); + } + return ans; +} + +/* Get value of variable with power. */ +void* +pf_get_variable_with_power(ParseNode* self) +{ + gint result = 0; + gint pow; + + const gchar *c, *next; + gchar *buffer; + MPNumber value; + + MPNumber t; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + pow = super_atoi(((LexerToken*) self->value)->string); + + /* No need to free the memory. It is allocated and freed somewhere else. */ + self->value = NULL; + + if(!(self->state->get_variable)) + { + free(ans); + return NULL; + } + + /* If defined, then get the variable */ + if((*(self->state->get_variable))(self->state, self->token->string, ans)) + { + mp_xpowy_integer(ans, pow, ans); + return ans; + } + + /* If has more than one character then assume a multiplication of variables */ + if(utf8_next_char(self->token->string)[0] != '\0') + { + result = 1; + buffer = (gchar*) malloc(sizeof(gchar) * strlen(self->token->string)); + mp_set_from_integer(1, &value); + for(c = self->token->string; *c != '\0'; c = next) + { + next = utf8_next_char(c); + snprintf(buffer, next - c + 1, "%s", c); + if(!(*(self->state->get_variable))(self->state, buffer, &t)) + { + result = 0; + break; + } + + /* If last term do power */ + if(*next == '\0') + mp_xpowy_integer(&t, pow, &t); + mp_multiply(&value, &t, &value); + } + free(buffer); + if(result) + mp_set_from_mp(&value, ans); + } + if(!result) + { + free(ans); + ans = NULL; + set_error(self->state, PARSER_ERR_UNKNOWN_VARIABLE, self->token->string); + } + return ans; +} + +/* Apply function on child. */ +void* +pf_apply_func(ParseNode* self) +{ + MPNumber* val; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!(self->state->get_function)) + { + free(val); + free(ans); + return NULL; + } + if(!val) + { + free(ans); + return NULL; + } + if(!(*(self->state->get_function))(self->state, self->token->string, val, ans)) + { + free(val); + free(ans); + set_error(self->state, PARSER_ERR_UNKNOWN_FUNCTION, self->token->string); + return NULL; + } + free(val); + return ans; +} + +/* Apply function with +ve power. */ +void* +pf_apply_func_with_power(ParseNode* self) +{ + MPNumber* val; + MPNumber* tmp; + MPNumber* ans; + gint pow; + tmp = (MPNumber*) malloc(sizeof(MPNumber)); + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!(self->state->get_function)) + { + free(tmp); + free(ans); + free(val); + self->value = NULL; + return NULL; + } + if(!val) + { + free(tmp); + free(ans); + self->value = NULL; + return NULL; + } + if(!(*(self->state->get_function))(self->state, self->token->string, val, tmp)) + { + free(tmp); + free(ans); + free(val); + self->value = NULL; + set_error(self->state, PARSER_ERR_UNKNOWN_FUNCTION, self->token->string); + return NULL; + } + pow = super_atoi(((LexerToken*) self->value)->string); + mp_xpowy_integer(tmp, pow, ans); + free(val); + free(tmp); + self->value = NULL; + return ans; +} + +/* Apply function with -ve power. */ +void* +pf_apply_func_with_npower(ParseNode* self) +{ + MPNumber* val; + MPNumber* tmp; + MPNumber* ans; + gint pow; + gchar* inv_name; + inv_name = (gchar*) malloc(sizeof(gchar) * strlen(self->token->string) + strlen("⁻¹") + 1); + strcpy(inv_name, self->token->string); + strcat(inv_name, "⁻¹"); + tmp = (MPNumber*) malloc(sizeof(MPNumber)); + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val) + { + free(tmp); + free(inv_name); + free(ans); + self->value = NULL; + return NULL; + } + if(!(self->state->get_function)) + { + free(tmp); + free(ans); + free(inv_name); + self->value = NULL; + return NULL; + } + if(!(*(self->state->get_function))(self->state, inv_name, val, tmp)) + { + free(tmp); + free(ans); + free(val); + free(inv_name); + self->value = NULL; + set_error(self->state, PARSER_ERR_UNKNOWN_FUNCTION, self->token->string); + return NULL; + } + pow = super_atoi(((LexerToken*) self->value)->string); + mp_xpowy_integer(tmp, -pow, ans); + free(val); + free(tmp); + free(inv_name); + self->value = NULL; + return ans; +} + +/* Find nth root of child. */ +void* +pf_do_nth_root(ParseNode* self) +{ + MPNumber* val; + gint pow; + MPNumber* ans; + pow = sub_atoi(((LexerToken*) self->value)->string); + self->value = NULL; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val) + { + free(ans); + return NULL; + } + mp_root(val, pow, ans); + free(val); + return ans; +} + +/* Find sqrt of child. */ +void* +pf_do_sqrt(ParseNode* self) +{ + MPNumber* val; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val) + { + free(ans); + return NULL; + } + mp_sqrt(val, ans); + free(val); + return ans; +} + +/* Find 3rd root of child. */ +void* +pf_do_root_3(ParseNode* self) +{ + MPNumber* val; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val) + { + free(ans); + return NULL; + } + mp_root(val, 3, ans); + free(val); + return ans; +} + +/* Find 4th root of child. */ +void* +pf_do_root_4(ParseNode* self) +{ + MPNumber* val; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val) + { + free(ans); + return NULL; + } + mp_root(val, 4, ans); + free(val); + return ans; +} + +/* Apply floor function. */ +void* +pf_do_floor(ParseNode* self) +{ + MPNumber* val; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val) + { + free(ans); + return NULL; + } + mp_floor(val, ans); + free(val); + return ans; +} + +/* Apply ceiling function. */ +void* pf_do_ceiling (ParseNode* self) +{ + MPNumber* val; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val) + { + free(ans); + return NULL; + } + mp_ceiling(val, ans); + free(val); + return ans; +} + +/* Round off. */ +void* +pf_do_round(ParseNode* self) +{ + MPNumber* val; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val) + { + free(ans); + return NULL; + } + mp_round(val, ans); + free(val); + return ans; +} + +/* Fraction. */ +void* +pf_do_fraction(ParseNode* self) +{ + MPNumber* val; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val) + { + free(ans); + return NULL; + } + mp_fractional_part(val, ans); + free(val); + return ans; +} + +/* Absolute value. */ +void* +pf_do_abs(ParseNode* self) +{ + MPNumber* val; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val) + { + free(ans); + return NULL; + } + mp_abs(val, ans); + free(val); + return ans; +} + +/* Find x^y for x and y being MPNumber. */ +void* +pf_do_x_pow_y(ParseNode* self) +{ + MPNumber* val; + MPNumber* pow; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->left->evaluate))(self->left); + pow = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val || !pow) + { + if(val) + free(val); + if(pow) + free(pow); + free(ans); + return NULL; + } + mp_xpowy(val, pow, ans); + free(val); + free(pow); + return ans; +} + +/* Find x^y for MPNumber x and integer y. */ +void* +pf_do_x_pow_y_int(ParseNode* self) +{ + MPNumber* val; + gint pow; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->left->evaluate))(self->left); + pow = super_atoi(self->right->token->string); + if(!val) + { + free(ans); + return NULL; + } + mp_xpowy_integer(val, pow, ans); + free(val); + return ans; +} + +/* Find factorial. */ +void* +pf_do_factorial(ParseNode* self) +{ + MPNumber* val; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val) + { + free(ans); + return NULL; + } + mp_factorial(val, ans); + free(val); + return ans; +} + +/* Apply unary minus. */ +void* +pf_unary_minus(ParseNode* self) +{ + MPNumber* val; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val) + { + free(ans); + return NULL; + } + mp_invert_sign(val, ans); + free(val); + return ans; +} + +/* Divide. */ +void* +pf_do_divide(ParseNode* self) +{ + MPNumber* left; + MPNumber* right; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + left = (MPNumber*) (*(self->left->evaluate))(self->left); + right = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!left || !right) + { + if(left) + free(left); + if(right) + free(right); + free(ans); + return NULL; + } + mp_divide(left, right, ans); + free(left); + free(right); + return ans; +} + +/* Modulus. */ +void* +pf_do_mod(ParseNode* self) +{ + MPNumber* left; + MPNumber* right; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + left = (MPNumber*) (*(self->left->evaluate))(self->left); + right = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!left || !right) + { + if(left) + free(left); + if(right) + free(right); + free(ans); + return NULL; + } + mp_modulus_divide(left, right, ans); + free(left); + free(right); + return ans; +} + +/* Multiply two numbers. */ +void* +pf_do_multiply(ParseNode* self) +{ + MPNumber* left; + MPNumber* right; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + left = (MPNumber*) (*(self->left->evaluate))(self->left); + right = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!left || !right) + { + if(left) + free(left); + if(right) + free(right); + free(ans); + return NULL; + } + mp_multiply(left, right, ans); + free(left); + free(right); + return ans; +} + +/* Subtract two numbers. */ +void* +pf_do_subtract(ParseNode* self) +{ + MPNumber* left; + MPNumber* right; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + left = (MPNumber*) (*(self->left->evaluate))(self->left); + right = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!left || !right) + { + if(left) + free(left); + if(right) + free (right); + free(ans); + return NULL; + } + mp_subtract(left, right, ans); + free(left); + free(right); + return ans; +} + +/* Add two numbers. */ +void* +pf_do_add(ParseNode* self) +{ + MPNumber* left; + MPNumber* right; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + left = (MPNumber*) (*(self->left->evaluate))(self->left); + right = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!left || !right) + { + if(left) + free(left); + if(right) + free(right); + free(ans); + return NULL; + } + mp_add(left, right, ans); + free(left); + free(right); + return ans; +} + +/*Add (x) Percentage to value. */ +void* +pf_do_add_percent(ParseNode* self) +{ + MPNumber* ans; + MPNumber* val; + MPNumber* per; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->left->evaluate))(self->left); + per = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val || !per) + { + if(val) + free(val); + if(per) + free(per); + free(ans); + return NULL; + } + mp_add_integer(per, 100, per); + mp_divide_integer(per, 100, per); + mp_multiply(val, per, ans); + free(val); + free(per); + return ans; +} + +/* Subtract (x) Percentage to value. */ +void* +pf_do_subtract_percent(ParseNode* self) +{ + MPNumber* ans; + MPNumber* val; + MPNumber* per; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->left->evaluate))(self->left); + per = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val || !per) + { + if(val) + free(val); + if(per) + free(per); + free(ans); + return NULL; + } + mp_add_integer(per, -100, per); + mp_divide_integer(per, -100, per); + mp_multiply(val, per, ans); + free(val); + free(per); + return ans; +} + +/* Converts a constant into percentage. */ +void* +pf_do_percent(ParseNode* self) +{ + MPNumber* val; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val) + { + free(ans); + return NULL; + } + mp_divide_integer(val, 100, ans); + free(val); + return ans; +} + +/* NOT. */ +void* +pf_do_not(ParseNode* self) +{ + MPNumber* val; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + val = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!val) + { + free(ans); + return NULL; + } + if(!mp_is_overflow(val, self->state->options->wordlen)) + { + set_error(self->state, PARSER_ERR_OVERFLOW, NULL); + free(ans); + ans = NULL; + } + mp_not(val, self->state->options->wordlen, ans); + free(val); + return ans; +} + +/* AND. */ +void* +pf_do_and(ParseNode* self) +{ + MPNumber* left; + MPNumber* right; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + left = (MPNumber*) (*(self->left->evaluate))(self->left); + right = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!left || !right) + { + if(left) + free(left); + if(right) + free(right); + free(ans); + return NULL; + } + mp_and(left, right, ans); + free(left); + free(right); + return ans; +} + +/* OR. */ +void* +pf_do_or(ParseNode* self) +{ + MPNumber* left; + MPNumber* right; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + left = (MPNumber*) (*(self->left->evaluate))(self->left); + right = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!left || !right) + { + if(left) + free(left); + if(right) + free(right); + free(ans); + return NULL; + } + mp_or(left, right, ans); + free(left); + free(right); + return ans; +} + +/* XOR. */ +void* +pf_do_xor(ParseNode* self) +{ + MPNumber* left; + MPNumber* right; + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + left = (MPNumber*) (*(self->left->evaluate))(self->left); + right = (MPNumber*) (*(self->right->evaluate))(self->right); + if(!left || !right) + { + if(left) + free(left); + if(right) + free(right); + free(ans); + return NULL; + } + mp_xor(left, right, ans); + free(left); + free(right); + return ans; +} + +/* Constant value. Convert into MPNumber and return. */ +void* +pf_constant(ParseNode* self) +{ + MPNumber* ans; + ans = (MPNumber*) malloc(sizeof(MPNumber)); + if(mp_set_from_string(self->token->string, self->state->options->base, ans) != 0) + { + /* This should never happen, as l_check_if_number() has already passed the string once. */ + /* If the code reaches this point, something is really wrong. X( */ + free(ans); + set_error(self->state, PARSER_ERR_INVALID, self->token->string); + return NULL; + } + return ans; +} + diff --git a/src/parserfunc.h b/src/parserfunc.h new file mode 100644 index 00000000..cf049b06 --- /dev/null +++ b/src/parserfunc.h @@ -0,0 +1,80 @@ +#ifndef PAESERFUNC_H +#define PARSERFUNC_H + +#include "parser.h" + +void set_error(ParserState*, gint, const gchar*); + +void* pf_none(ParseNode*); + +void* pf_set_var(ParseNode*); + +void* pf_convert_number(ParseNode*); + +void* pf_convert_1(ParseNode*); + +gchar* pf_make_unit(gchar* source, gchar* power); + +void* pf_get_variable(ParseNode*); + +void* pf_get_variable_with_power(ParseNode*); + +void* pf_apply_func(ParseNode*); + +void* pf_apply_func_with_power(ParseNode*); + +void* pf_apply_func_with_npower(ParseNode*); + +void* pf_do_nth_root(ParseNode*); + +void* pf_do_sqrt(ParseNode*); + +void* pf_do_root_3(ParseNode*); + +void* pf_do_root_4(ParseNode*); + +void* pf_do_floor(ParseNode*); + +void* pf_do_ceiling(ParseNode*); + +void* pf_do_round(ParseNode*); + +void* pf_do_fraction(ParseNode*); + +void* pf_do_abs(ParseNode*); + +void* pf_do_x_pow_y(ParseNode*); + +void* pf_do_x_pow_y_int(ParseNode*); + +void* pf_do_factorial(ParseNode*); + +void* pf_unary_minus(ParseNode*); + +void* pf_do_divide(ParseNode*); + +void* pf_do_mod(ParseNode*); + +void* pf_do_multiply(ParseNode*); + +void* pf_do_subtract(ParseNode*); + +void* pf_do_add(ParseNode*); + +void* pf_do_add_percent(ParseNode*); + +void* pf_do_subtract_percent(ParseNode*); + +void* pf_do_percent(ParseNode*); + +void* pf_do_not(ParseNode*); + +void* pf_do_and(ParseNode*); + +void* pf_do_or(ParseNode*); + +void* pf_do_xor(ParseNode*); + +void* pf_constant(ParseNode*); + +#endif /* PARSERFUNC_H */ diff --git a/src/prelexer.c b/src/prelexer.c new file mode 100644 index 00000000..a22dd0da --- /dev/null +++ b/src/prelexer.c @@ -0,0 +1,214 @@ +#include +#include +#include +#include + +#include "prelexer.h" + +/* Creates a scanner state which will be useful for accessing the lexer later. */ +PreLexerState* +pl_create_scanner(const gchar* input) +{ + PreLexerState* state; + assert(input != NULL); + assert(g_utf8_validate(input, -1, NULL)); + state = (PreLexerState *) malloc(sizeof(PreLexerState)); + assert(state != NULL); + state->stream = g_strdup(input); + state->length = strlen(state->stream); /* Can't find a GLib replacement of strlen. The mailing list discussion says, it is not implemented because strlen is perfectly capable. :) */ + state->next_index = 0; + state->mark_index = 0; + return state; +} + +/* Destroy and free memory used by LexerState object. */ +void +pl_destroy_scanner(PreLexerState* state) +{ + free(state->stream); + free(state); +} + +/* Roll back last scanned unichar. */ +void +pl_roll_back(PreLexerState* state) +{ + gchar* tmp; + tmp = g_utf8_find_prev_char(state->stream, state->stream + state->next_index); + if(tmp == NULL) + /* Already at the beginning of the stram. Reset index. */ + state->next_index = 0; + else + state->next_index = tmp - state->stream; +} + +/* Get validated gunichar from input stream. */ +gunichar +pl_get_next_gunichar(PreLexerState* state) +{ + gunichar ret; + if(state->next_index >= state->length) + { + /* To prevent scanning last letter multiple times, when a single unconditional rollback is used. */ + if(state->next_index == state->length) + state->next_index++; + return 0; + } + ret = g_utf8_get_char_validated(state->stream + state->next_index, -1); + state->next_index = g_utf8_next_char(state->stream + state->next_index) - state->stream; + return ret; +} + +/* Set marker index. To be used for highlighting and error reporting. */ +void +pl_set_marker(PreLexerState* state) +{ + state->mark_index = state->next_index; +} + +/* Get marked substring. To be used for error reporting. */ +gchar* +pl_get_marked_substring(const PreLexerState* state) +{ + return g_strndup(state->stream + state->mark_index, state->next_index - state->mark_index); +} + +/* Compares a list of strings with given unichar. To be used by pl_get_next_token() only. */ +static gboolean +pl_compare_all(const gunichar ch, const gint count, gchar *arr[]) +{ + gint l; + for(l = 0; l < count; l++) + { + if(ch == g_utf8_get_char_validated(arr[l], -1)) + return TRUE; + } + return FALSE; +} + +/* Pre-Lexer tokanizer. To be called only by Lexer. */ +LexerTokenType +pl_get_next_token(PreLexerState* state) +{ + gunichar ch = pl_get_next_gunichar(state); + if(pl_compare_all(ch, 2, (gchar*[]){",","."})) + return PL_DECIMAL; + + if(g_unichar_isdigit(ch) || pl_compare_all(ch, 10, (gchar*[]){"〇","〡","〢","〣","〤","〥","〦","〧","〨","〩"})) + return PL_DIGIT; /* 0-9 */ + + if(g_unichar_isxdigit(ch)) + return PL_HEX; /* This is supposed to report just the A-F. */ + + if(pl_compare_all(ch, 10, (gchar*[]){"⁰","¹","²","³","⁴","⁵","⁶","⁷","⁸","⁹"})) + return PL_SUPER_DIGIT; + + if(pl_compare_all(ch, 1, (gchar*[]){"⁻"})) + return PL_SUPER_MINUS; + + if(pl_compare_all(ch, 10, (gchar*[]){"₀","₁","₂","₃","₄","₅","₆","₇","₈","₉"})) + return PL_SUB_DIGIT; + + if(pl_compare_all(ch, 15, (gchar*[]){"½","⅓","⅔","¼","¾","⅕","⅖","⅗","⅘","⅙","⅚","⅛","⅜","⅝","⅞"})) + return PL_FRACTION; + + if(pl_compare_all(ch, 1, (gchar*[]){"°"})) + return PL_DEGREE; + + if(pl_compare_all(ch, 1, (gchar*[]){"'"})) + return PL_MINUTE; + + if(pl_compare_all(ch, 1, (gchar*[]){"\""})) + return PL_SECOND; + + if(g_unichar_isalpha(ch)) + return PL_LETTER; /* All alphabets excluding A-F. [a-fA-F] are reported as PL_HEX. */ + + if(pl_compare_all(ch, 1, (gchar*[]){"∧"})) + return T_AND; + + if(pl_compare_all(ch, 1, (gchar*[]){"∨"})) + return T_OR; + + if(pl_compare_all(ch, 2, (gchar*[]){"⊻","⊕"})) + return T_XOR; + + if(pl_compare_all(ch, 2, (gchar*[]){"¬","~"})) + return T_NOT; + + if(pl_compare_all(ch, 1, (gchar*[]){"+"})) + return T_ADD; + + if(pl_compare_all(ch, 2, (gchar*[]){"-","−"})) + return T_SUBTRACT; + + if(pl_compare_all(ch, 2, (gchar*[]){"*","×"})) + return T_MULTIPLY; + + if(pl_compare_all(ch, 3, (gchar*[]){"/","∕","÷"})) + return T_DIVIDE; + + if(pl_compare_all(ch, 1, (gchar*[]){"⌊"})) + return T_L_FLOOR; + + if(pl_compare_all(ch, 1, (gchar*[]){"⌋"})) + return T_R_FLOOR; + + if(pl_compare_all(ch, 1, (gchar*[]){"⌈"})) + return T_L_CEILING; + + if(pl_compare_all(ch, 1, (gchar*[]){"⌉"})) + return T_R_CEILING; + + if(pl_compare_all(ch, 1, (gchar*[]){"√"})) + return T_ROOT; + + if(pl_compare_all(ch, 1, (gchar*[]){"∛"})) + return T_ROOT_3; + + if(pl_compare_all(ch, 1, (gchar*[]){"∜"})) + return T_ROOT_4; + + if(pl_compare_all(ch, 1, (gchar*[]){"="})) + return T_ASSIGN; + + if(pl_compare_all(ch, 1, (gchar*[]){"("})) + return T_L_R_BRACKET; + + if(pl_compare_all(ch, 1, (gchar*[]){")"})) + return T_R_R_BRACKET; + + if(pl_compare_all(ch, 1, (gchar*[]){"["})) + return T_L_S_BRACKET; + + if(pl_compare_all(ch, 1, (gchar*[]){"]"})) + return T_R_S_BRACKET; + + if(pl_compare_all(ch, 1, (gchar*[]){"{"})) + return T_L_C_BRACKET; + + if(pl_compare_all(ch, 1, (gchar*[]){"}"})) + return T_R_C_BRACKET; + + if(pl_compare_all(ch, 1, (gchar*[]){"|"})) + return T_ABS; + + if(pl_compare_all(ch, 1, (gchar*[]){"^"})) + return T_POWER; + + if(pl_compare_all(ch, 1, (gchar*[]){"!"})) + return T_FACTORIAL; + + if(pl_compare_all(ch, 1, (gchar*[]){"%"})) + return T_PERCENTAGE; + + if(pl_compare_all(ch, 4, (gchar*[]){" ","\r","\t","\n"})) + /* Gotta ignore'Em all!!! ;) */ + return PL_SKIP; + + if(ch == 0) + return PL_EOS; + + /* There is no spoon. */ + return T_UNKNOWN; +} diff --git a/src/prelexer.h b/src/prelexer.h new file mode 100644 index 00000000..b27998fa --- /dev/null +++ b/src/prelexer.h @@ -0,0 +1,93 @@ +#ifndef PRE_LEXER_H +#define PRE_LEXER_H + +#include + +/* Structure to store lexer state. */ +typedef struct +{ + gchar* stream; /* Pointer to the local copy of input string. */ + guint length; /* Length of input string; stored to reduce calls to strlen(). */ + guint next_index; /* Index of next (to be read) character from input. */ + guint mark_index; /* Location, last marked. Useful for getting substrings as part of highlighting */ +} PreLexerState; + +/* Enum for tokens generated by pre-lexer and lexer. */ +typedef enum +{ + T_UNKNOWN=0, //Unknown + + /* These are all Pre-Lexer tokens, returned by pre-lexer */ + PL_DECIMAL, //Decimal saperator + PL_DIGIT, //Decimal digit + PL_HEX, //A-F of Hex digits + PL_SUPER_DIGIT, //Super digits + PL_SUPER_MINUS, //Super minus + PL_SUB_DIGIT, //Sub digits + PL_FRACTION, //Fractions + PL_DEGREE, //Degree + PL_MINUTE, //Minutes + PL_SECOND, //10 //Seconds + PL_LETTER, //Alphabets + PL_EOS, //End of stream. Yay!! + PL_SKIP, //Skip this symbol (whitespace or newline). + + /* These are all tokens, returned by Lexer. */ + T_ADD, //Plus + T_SUBTRACT, //Minus + T_MULTIPLY, //Multiply + T_DIVIDE, //Divide + T_MOD, //Modulus + T_L_FLOOR, //Floor ( Left ) + T_R_FLOOR, //20 //Floor ( Right ) + T_L_CEILING, //Ceiling ( Left ) + T_R_CEILING, //Ceiling ( Right ) + T_ROOT, //Square root + T_ROOT_3, //Cube root + T_ROOT_4, //Fourth root + T_NOT, //Bitwise NOT + T_AND, //Bitwise AND + T_OR, //Bitwise OR + T_XOR, //Bitwise XOR + T_IN, //30 //IN ( for converter ) + T_NUMBER, //Number + T_SUP_NUMBER, //Super Number + T_NSUP_NUMBER, //Negative Super Number + T_SUB_NUMBER, //Sub Number + T_FUNCTION, //Function + T_VARIABLE, //Variable name + T_ASSIGN, //= + T_L_R_BRACKET, //40 //( + T_R_R_BRACKET, //) + T_L_S_BRACKET, //[ + T_R_S_BRACKET, //] + T_L_C_BRACKET, //{ + T_R_C_BRACKET, //} + T_ABS, //| + T_POWER, //^ + T_FACTORIAL, //! + T_PERCENTAGE //49 //% +} LexerTokenType; + +/* Creates a scanner state. Useful when multiple scanners are in action. */ +PreLexerState* pl_create_scanner(const gchar*); + +/* Destroy and free memory used by LexerState object. */ +void pl_destroy_scanner(PreLexerState*); + +/* Roll back last scanned unichar. */ +void pl_roll_back(PreLexerState*); + +/* Get validated gunichar from input stream. */ +gunichar pl_get_next_gunichar(PreLexerState*); + +/* Set marker index. To be used for highlighting and error reporting. */ +void pl_set_marker(PreLexerState*); + +/* Get marked substring. To be used for error reporting. */ +gchar* pl_get_marked_substring(const PreLexerState*); + +/* Get next Pre-Lexer token from stream. */ +LexerTokenType pl_get_next_token(PreLexerState*); + +#endif /* PRE_LEXER_H */ diff --git a/src/test-mp-equation.c b/src/test-mp-equation.c index 3a60acb2..95bb4a86 100644 --- a/src/test-mp-equation.c +++ b/src/test-mp-equation.c @@ -398,7 +398,7 @@ test_equations() test("2^1", "2", 0); test("2^2", "4", 0); test("2⁻¹", "0.5", 0); - //test("2⁻", "", PARSER_ERR_MP); // FIXME: Maybe an error in bison? + test("2⁻", "", PARSER_ERR_MP); test("2^−1", "0.5", 0); test("2^(−1)", "0.5", 0); test("x⁻¹", "0.5", 0); -- 2.11.4.GIT