Warning, /education/labplot/src/backend/gsl/parser.y is written in an unsupported language. File is not indexed.
0001 /***************************************************************************
0002 File : parser.y
0003 Project : LabPlot
0004 Description : Parser for mathematical expressions
0005 --------------------------------------------------------------------
0006 Copyright : (C) 2014 Alexander Semke (alexander.semke@web.de)
0007 Copyright : (C) 2014-2020 Stefan Gerlach (stefan.gerlach@uni.kn)
0008
0009 ***************************************************************************/
0010
0011 /***************************************************************************
0012 * *
0013 * This program is free software; you can redistribute it and/or modify *
0014 * it under the terms of the GNU General Public License as published by *
0015 * the Free Software Foundation; either version 2 of the License, or *
0016 * (at your option) any later version. *
0017 * *
0018 * This program is distributed in the hope that it will be useful, *
0019 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
0020 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
0021 * GNU General Public License for more details. *
0022 * *
0023 * You should have received a copy of the GNU General Public License *
0024 * along with this program; if not, write to the Free Software *
0025 * Foundation, Inc., 51 Franklin Street, Fifth Floor, *
0026 * Boston, MA 02110-1301 USA *
0027 * *
0028 ***************************************************************************/
0029
0030 %{
0031 #include <string.h>
0032 #include <ctype.h>
0033 #include <stdlib.h>
0034 #include <locale.h>
0035 #ifdef HAVE_XLOCALE
0036 #include <xlocale.h>
0037 #endif
0038 #include "parser.h"
0039 #include "constants.h"
0040 #include "functions.h"
0041 #if defined(_WIN32)
0042 #define locale_t _locale_t
0043 #define strtod_l _strtod_l
0044 #define freelocale _free_locale
0045 #endif
0046
0047 #ifdef PDEBUG
0048 #include <stdio.h>
0049 #define pdebug(...) fprintf(stderr, __VA_ARGS__)
0050 #else
0051 #define pdebug(...) {}
0052 #endif
0053
0054 #define YYERROR_VERBOSE 1
0055
0056 /* params passed to yylex (and yyerror) */
0057 typedef struct param {
0058 size_t pos; /* current position in string */
0059 char* string; /* the string to parse */
0060 const char* locale; /* name of locale to convert numbers */
0061 } param;
0062
0063 int yyerror(param *p, const char *err);
0064 int yylex(param *p);
0065
0066 double res;
0067 %}
0068
0069 %lex-param {param *p}
0070 %parse-param {param *p}
0071
0072 %union {
0073 double dval; /* For returning numbers */
0074 symbol *tptr; /* For returning symbol-table pointers */
0075 }
0076
0077 %token <dval> NUM /* Simple double precision number */
0078 %token <tptr> VAR FNCT /* VARiable and FuNCTion */
0079 %type <dval> expr
0080
0081 %right '='
0082 %left '-' '+'
0083 %left '*' '/' '%'
0084 %left NEG /* Negation--unary minus */
0085 %right '^' '!'
0086
0087 %%
0088 input: /* empty */
0089 | input line
0090 ;
0091
0092 line: '\n'
0093 | expr '\n' { res=$1; }
0094 | error '\n' { yyerrok; }
0095 ;
0096
0097 expr: NUM { $$ = $1; }
0098 | VAR { $$ = $1->value.var; }
0099 | VAR '=' expr { $$ = $3; $1->value.var = $3; }
0100 | FNCT '(' ')' { $$ = (*($1->value.fnctptr))(); }
0101 | FNCT '(' expr ')' { $$ = (*((func_t1)($1->value.fnctptr)))($3); }
0102 | FNCT '(' expr ',' expr ')' { $$ = (*((func_t2)($1->value.fnctptr)))($3,$5); }
0103 | FNCT '(' expr ',' expr ','expr ')' { $$ = (*((func_t3)($1->value.fnctptr)))($3,$5,$7); }
0104 | FNCT '(' expr ',' expr ',' expr ','expr ')' { $$ = (*((func_t4)($1->value.fnctptr)))($3,$5,$7,$9); }
0105 | FNCT '(' expr ';' expr ')' { $$ = (*((func_t2)($1->value.fnctptr)))($3,$5); }
0106 | FNCT '(' expr ';' expr ';'expr ')' { $$ = (*((func_t3)($1->value.fnctptr)))($3,$5,$7); }
0107 | FNCT '(' expr ';' expr ';' expr ';'expr ')' { $$ = (*((func_t4)($1->value.fnctptr)))($3,$5,$7,$9); }
0108 | expr '+' expr { $$ = $1 + $3; }
0109 | expr '-' expr { $$ = $1 - $3; }
0110 | expr '*' expr { $$ = $1 * $3; }
0111 | expr '/' expr { $$ = $1 / $3; }
0112 | expr '%' expr { $$ = (int)($1) % (int)($3); }
0113 | '-' expr %prec NEG{ $$ = -$2; }
0114 | expr '^' expr { $$ = pow($1, $3); }
0115 | expr '*' '*' expr { $$ = pow($1, $4); }
0116 | '(' expr ')' { $$ = $2; }
0117 | '|' expr '|' { $$ = fabs($2); }
0118 | expr '!' { $$ = gsl_sf_fact((unsigned int)$1); }
0119 /* logical operators (!,&&,||) are not supported */
0120 ;
0121
0122 %%
0123
0124 /* global symbol table (as linked list) */
0125 symbol *symbol_table = 0;
0126
0127 int parse_errors(void) {
0128 return yynerrs;
0129 }
0130
0131 int yyerror(param *p, const char *s) {
0132 /* remove trailing newline */
0133 p->string[strcspn(p->string, "\n")] = 0;
0134 printf("PARSER ERROR: %s @ position %d of string '%s'\n", s, (int)(p->pos), p->string);
0135
0136 return 0;
0137 }
0138
0139 /* save symbol in symbol table (at start of linked list) */
0140 symbol* put_symbol(const char *symbol_name, int symbol_type) {
0141 /* pdebug("PARSER: put_symbol(): symbol_name = '%s'\n", symbol_name); */
0142
0143 symbol *ptr = (symbol *)malloc(sizeof(symbol));
0144 ptr->name = (char *)malloc(strlen(symbol_name) + 1);
0145 strcpy(ptr->name, symbol_name);
0146 ptr->type = symbol_type;
0147 ptr->value.var = 0; /* set value to 0 even if fctn */
0148 ptr->next = (symbol *)symbol_table;
0149 symbol_table = ptr;
0150
0151 /* pdebug("PARSER: put_symbol() DONE\n"); */
0152 return ptr;
0153 }
0154
0155 /* remove symbol of name symbol_name from symbol table
0156 removes only variables of value 0
0157 returns 0 on success */
0158 int remove_symbol(const char *symbol_name) {
0159 symbol* ptr = symbol_table;
0160
0161 /* check if head contains symbol */
0162 if (ptr && (strcmp(ptr->name, symbol_name) == 0)) {
0163 if (ptr->type == VAR && ptr->value.var == 0) {
0164 pdebug("PARSER: REMOVING symbol '%s'\n", symbol_name);
0165 symbol_table = ptr->next;
0166 free(ptr->name);
0167 free(ptr);
0168 }
0169 return 0;
0170 }
0171
0172 /* search for symbol to be deleted */
0173 symbol* prev;
0174 while (ptr && (strcmp(ptr->name, symbol_name) != 0)) {
0175 prev = ptr;
0176 ptr = ptr->next;
0177 }
0178
0179 /* symbol not found or is not a variable or is not 0 */
0180 if (!ptr || ptr->type != VAR || ptr->value.var != 0)
0181 return 1;
0182
0183 /* remove symbol */
0184 pdebug("PARSER: REMOVING symbol '%s'\n", symbol_name);
0185 prev->next = ptr->next;
0186 free(ptr->name);
0187 free(ptr);
0188
0189 return 0;
0190 }
0191
0192 /* get symbol from symbol table
0193 returns 0 if symbol not found */
0194 symbol* get_symbol(const char *symbol_name) {
0195 pdebug("PARSER: get_symbol(): symbol_name = '%s'\n", symbol_name);
0196
0197 symbol *ptr;
0198 for (ptr = symbol_table; ptr != 0; ptr = (symbol *)ptr->next) {
0199 /* pdebug("%s ", ptr->name); */
0200 if (strcmp(ptr->name, symbol_name) == 0) {
0201 pdebug("PARSER: SYMBOL FOUND\n");
0202 return ptr;
0203 }
0204 }
0205
0206 pdebug("PARSER: SYMBOL NOT FOUND\n");
0207 return 0;
0208 }
0209
0210 /* initialize symbol table with all known functions and constants */
0211 void init_table(void) {
0212 pdebug("PARSER: init_table()\n");
0213
0214 symbol *ptr = 0;
0215 int i;
0216 /* add functions */
0217 for (i = 0; _functions[i].name != 0; i++) {
0218 ptr = put_symbol(_functions[i].name, FNCT);
0219 ptr->value.fnctptr = _functions[i].fnct;
0220 }
0221 /* add constants */
0222 for (i = 0; _constants[i].name != 0; i++) {
0223 ptr = put_symbol(_constants[i].name, VAR);
0224 ptr->value.var = _constants[i].value;
0225 }
0226
0227 pdebug("PARSER: init_table() DONE. sym_table = %p\n", ptr);
0228 }
0229
0230 void delete_table(void) {
0231 pdebug("PARSER: delete_table()\n");
0232 while(symbol_table) {
0233 symbol *tmp = symbol_table;
0234 symbol_table = symbol_table->next;
0235 free(tmp->name);
0236 free(tmp);
0237 }
0238 }
0239
0240 /* add new symbol with value or just set value if symbol is a variable */
0241 symbol* assign_symbol(const char* symbol_name, double value) {
0242 pdebug("PARSER: assign_symbol() : symbol_name = '%s', value = %g\n", symbol_name, value);
0243
0244 /* be sure that the symbol table has been initialized */
0245 if (!symbol_table)
0246 init_table();
0247
0248 symbol* ptr = get_symbol(symbol_name);
0249 if (!ptr) {
0250 pdebug("PARSER: calling putsymbol(): symbol_name = '%s'\n", symbol_name);
0251 ptr = put_symbol(symbol_name, VAR);
0252 } else {
0253 pdebug("PARSER: Symbol already assigned\n");
0254 }
0255
0256 /* do not assign value if symbol already exits as function */
0257 if (ptr->type == VAR)
0258 ptr->value.var = value;
0259
0260 return ptr;
0261 };
0262
0263 static int getcharstr(param *p) {
0264 pdebug(" getcharstr() pos = %d\n", (int)(p->pos));
0265
0266 if (p->string[p->pos] == '\0')
0267 return EOF;
0268 /* pdebug("PARSER: char is %c\n", p->string[p->pos]); */
0269 return p->string[(p->pos)++];
0270 }
0271
0272 static void ungetcstr(size_t *pos) {
0273 /* pdebug("PARSER: ungetcstr()\n"); */
0274 if (*pos > 0)
0275 (*pos)--;
0276 }
0277
0278 double parse(const char* string, const char* locale) {
0279 pdebug("\nPARSER: parse('%s') len = %d\n********************************\n", string, (int)strlen(string));
0280
0281 /* be sure that the symbol table has been initialized */
0282 if (!symbol_table)
0283 init_table();
0284
0285 param p;
0286 p.pos = 0;
0287 p.locale = locale;
0288
0289 /* leave space to terminate string by "\n\0" */
0290 const size_t slen = strlen(string) + 2;
0291 p.string = (char *) malloc(slen * sizeof(char));
0292 if (p.string == NULL) {
0293 printf("PARSER ERROR: Out of memory for parsing string\n");
0294 return 0.;
0295 }
0296
0297 strcpy(p.string, string);
0298 p.string[strlen(string)] = '\n'; // end for parsing
0299 p.string[strlen(string)+1] = '\0'; // end of string
0300 /* pdebug("PARSER: Call yyparse() for \"%s\" (len = %d)\n", p.string, (int)strlen(p.string)); */
0301
0302 /* parameter for yylex */
0303 res = NAN; /* default value */
0304 yynerrs = 0; /* reset error count */
0305 yyparse(&p);
0306
0307 pdebug("PARSER: parse() DONE (result = %g, errors = %d)\n*******************************\n", res, parse_errors());
0308 free(p.string);
0309 p.string = 0;
0310
0311 return res;
0312 }
0313
0314 double parse_with_vars(const char *str, const parser_var *vars, int nvars, const char* locale) {
0315 pdebug("\nPARSER: parse_with_var(\"%s\") len = %d\n", str, (int)strlen(str));
0316
0317 int i;
0318 for(i = 0; i < nvars; i++) { /*assign vars */
0319 pdebug("PARSER: Assign '%s' the value %g\n", vars[i].name, vars[i].value);
0320 assign_symbol(vars[i].name, vars[i].value);
0321 }
0322
0323 return parse(str, locale);
0324 }
0325
0326 int yylex(param *p) {
0327 pdebug("PARSER: YYLEX()");
0328
0329 /* get char and skip white space */
0330 int c;
0331 while ((c = getcharstr(p)) == ' ' || c == '\t');
0332
0333 /* finish if reached EOF */
0334 if (c == EOF) {
0335 pdebug("PARSER: FINISHED\n");
0336 return 0;
0337 }
0338 /* check for non-ASCII chars */
0339 if (!isascii(c)) {
0340 pdebug(" non-ASCII character found. Giving up\n");
0341 yynerrs++;
0342 return 0;
0343 }
0344 if (c == '\n') {
0345 pdebug("PARSER: Reached EOL\n");
0346 return c;
0347 }
0348
0349 pdebug("PARSER: PROCESSING character '%c'\n", c);
0350
0351 /* process numbers */
0352 if (isdigit(c)) {
0353 pdebug("PARSER: Found NUMBER (starts with digit)\n");
0354 ungetcstr(&(p->pos));
0355 char *s = &(p->string[p->pos]);
0356
0357 /* convert to double */
0358 char *remain;
0359 #if defined(_WIN32)
0360 locale_t locale = _create_locale(LC_NUMERIC, p->locale);
0361 if (locale == NULL) {
0362 pdebug("PARSER ERROR in newlocale(%s): %s. Trying system locale.\n", p->locale, strerror(errno));
0363 locale = _create_locale(LC_NUMERIC, "");
0364 }
0365 #else
0366 locale_t locale = newlocale(LC_NUMERIC_MASK, p->locale, (locale_t)0);
0367 if (locale == (locale_t)0) {
0368 pdebug("PARSER ERROR in newlocale(%s): %s. Trying system locale.\n", p->locale, strerror(errno));
0369 locale = newlocale(LC_NUMERIC_MASK, "", (locale_t)0);
0370 pdebug("PARSER: Reading: '%s' with system locale\n", s);
0371 } else {
0372 pdebug("PARSER: Reading: '%s' with locale %s\n", s, p->locale);
0373 }
0374 #endif
0375 double result;
0376 if (locale != NULL) {
0377 result = strtod_l(s, &remain, locale);
0378 freelocale(locale);
0379 } else // use C locale
0380 result = strtod(s, &remain);
0381
0382 pdebug("PARSER: Remain: '%s'\n", remain);
0383
0384 /* check conversion */
0385 if(strlen(s) == strlen(remain))
0386 return 0;
0387
0388 pdebug("PARSER: Result = %g\n", result);
0389 yylval.dval = result;
0390
0391 p->pos += strlen(s) - strlen(remain);
0392
0393 return NUM;
0394 }
0395
0396 /* process symbol */
0397 if (isalpha (c) || c == '.') {
0398 pdebug("PARSER: Found SYMBOL (starts with alpha)\n");
0399 static char *symbol_name = 0;
0400 static int length = 0;
0401 int i = 0;
0402
0403 /* Initially make the buffer long enough for a 10-character symbol name */
0404 if (length == 0) {
0405 length = 10;
0406 symbol_name = (char *) malloc(length + 1);
0407 }
0408
0409 do {
0410 pdebug("PARSER: Reading symbol .. ");
0411 /* If buffer is full, make it bigger */
0412 if (i == length) {
0413 length *= 2;
0414 symbol_name = (char *) realloc(symbol_name, length + 1);
0415 }
0416 symbol_name[i++] = c;
0417 c = getcharstr(p);
0418 pdebug("PARSER: got '%c'\n", c);
0419 }
0420 while (c != EOF && (isalnum(c) || c == '_' || c == '.'));
0421 pdebug("PARSER: Reading SYMBOL DONE\n");
0422
0423 if (c != EOF)
0424 ungetcstr(&(p->pos));
0425 symbol_name[i] = '\0';
0426
0427 symbol *s = get_symbol(symbol_name);
0428 if(s == 0) { /* symbol unknown */
0429 pdebug("PARSER ERROR: Symbol '%s' UNKNOWN\n", symbol_name);
0430 yynerrs++;
0431 return 0;
0432 /* old behavior: add symbol */
0433 /* s = put_symbol(symbol_name, VAR); */
0434 }
0435
0436 yylval.tptr = s;
0437 return s->type;
0438 }
0439
0440 /* else: single operator */
0441 pdebug("PARSER: Found single operator '%c'\n", c);
0442 return c;
0443 }