diff options
Diffstat (limited to 'src/symbolic_parser.c')
| -rw-r--r-- | src/symbolic_parser.c | 330 |
1 files changed, 330 insertions, 0 deletions
diff --git a/src/symbolic_parser.c b/src/symbolic_parser.c new file mode 100644 index 0000000..08cae88 --- /dev/null +++ b/src/symbolic_parser.c @@ -0,0 +1,330 @@ +/* +Copyright 2015-2022 Ian Jauslin + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. +*/ + +#include "symbolic_parser.h" +#include <stdlib.h> +#include <stdio.h> +#include "tree.h" +#include "definitions.cpp" +#include "array.h" +#include "istring.h" +#include "fields.h" +#include "polynomial.h" + +#define SP_NULL_MODE 0 +#define SP_FUNCTION_MODE 1 + +// parse a symbolic expression from a char_array +int parse_symbolic_expression(Char_Array str, Fields_Table fields, Variables variables, Polynomial* polynomial){ + Tree symbol_tree; + char_array_to_symbol_tree(str, &symbol_tree); + resolve_symbol_tree(symbol_tree, fields, variables, polynomial); + free_Tree(symbol_tree); + return(0); +} +// from char* +int parse_symbolic_expression_str(char* str, Fields_Table fields, Variables variables, Polynomial* polynomial){ + Char_Array char_array; + str_to_char_array(str,&char_array); + parse_symbolic_expression(char_array, fields, variables, polynomial); + free_Char_Array(char_array); + return(0); +} + +// compute the symbol tree from a string +int char_array_to_symbol_tree(Char_Array str, Tree* symbol_tree){ + // buffer + char* buffer=calloc(str.length+1,sizeof(char)); + char* buffer_ptr=buffer; + Tree child; + int match; + Char_Array nodestr; + Char_Array label; + Char_Array str_clean; + int mode; + int comment=0; + int j; + int gotanode=0; + + // allocate memory + init_Tree(symbol_tree,SYMBOL_TREE_SIZE, SYMBOL_TREE_LABEL_SIZE); + + // remove comments, ' ' and '\n' + init_Char_Array(&str_clean,str.length); + for(j=0;j<str.length;j++){ + if(comment==1){ + if(str.str[j]=='\n'){ + comment=0; + } + } + else{ + switch(str.str[j]){ + case ' ':break; + case '\n':break; + // comments + case '#': + comment=1; + break; + default: + char_array_append(str.str[j],&str_clean); + break; + } + } + } + + // if the string contains no '<', then trivial tree + for(j=0;j<str_clean.length;j++){ + if(str_clean.str[j]=='<'){ + break; + } + } + // no '<': trivial tree + if(j==str_clean.length){ + tree_set_label(str_clean, symbol_tree); + free(buffer); + free_Char_Array(str_clean); + return(0); + } + + *buffer_ptr='\0'; + // loop over the input string + // start in null mode + mode=SP_NULL_MODE; + for(j=0;j<str_clean.length;j++){ + switch(str_clean.str[j]){ + // new node + case '<': + // find matching bracket + match=matching_bracket(str_clean,j); + // check whether it exists + if(match<0){ + fprintf(stderr,"syntax error: unmatched brackets in %s\n",char_array_to_str_noinit(&str)); + exit(-1); + } + // extract substring until bracket + char_array_substring(str_clean,j+1,match-1,&nodestr); + + // check whether node is trivial + if(j==0 && match==str_clean.length-1){ + free_Tree(*symbol_tree); + char_array_to_symbol_tree(nodestr, symbol_tree); + free_Char_Array(nodestr); + j=match; + break; + } + + // parse subexpression + char_array_to_symbol_tree(nodestr, &child); + free_Char_Array(nodestr); + // add child to tree + tree_append_child_noinit(child, symbol_tree); + // boolean indicating a node has been found + gotanode=1; + // set next position after the node + j=match; + + // if function mode, then check that the match is at the end of the node + if(mode==SP_FUNCTION_MODE){ + if(match<str_clean.length-1){ + fprintf(stderr,"syntax error: functions must occupy an entire node (e.g. <%%exp<...>>), got %s\n",char_array_to_str_noinit(&str)); + exit(-1); + } + else{ + // set label + str_to_char_array(buffer,&label); + tree_set_label(label,symbol_tree); + free_Char_Array(label); + } + } + break; + + // function + case '%': + if(j>0){ + fprintf(stderr,"syntax error: functions must occupy an entire node (e.g. <%%exp<...>>), got %s\n",char_array_to_str_noinit(&str)); + exit(-1); + } + mode=SP_FUNCTION_MODE; + break; + + // product + case '*': + if(gotanode==0){ + fprintf(stderr,"syntax error: '*' is not preceded by a node in %s\n",char_array_to_str_noinit(&str)); + exit(-1); + } + if(j>=str_clean.length-1){ + fprintf(stderr,"syntax error: '*' cannot be at the end of an expression, got %s\n",char_array_to_str_noinit(&str)); + exit(-1); + } + // set label + init_Char_Array(&label,1); + char_array_append('*',&label); + tree_set_label(label,symbol_tree); + free_Char_Array(label); + // next child + char_array_substring(str_clean,j+1,str_clean.length-1,&nodestr); + // parse subexpression + char_array_to_symbol_tree(nodestr, &child); + free_Char_Array(nodestr); + // append next child + tree_append_child_noinit(child, symbol_tree); + + // make it stop + j=str_clean.length-1; + break; + + // sum + case '+': + if(gotanode==0){ + fprintf(stderr,"syntax error: '+' is not preceded by a node in %s\n",char_array_to_str_noinit(&str)); + exit(-1); + } + if(j>=str_clean.length-1){ + fprintf(stderr,"syntax error: '+' cannot be at the end of an expression, got %s\n",char_array_to_str_noinit(&str)); + exit(-1); + } + // set label + init_Char_Array(&label,1); + char_array_append('+',&label); + tree_set_label(label,symbol_tree); + free_Char_Array(label); + // next child + char_array_substring(str_clean,j+1,str_clean.length-1,&nodestr); + // parse subexpression + char_array_to_symbol_tree(nodestr, &child); + free_Char_Array(nodestr); + // append next child + tree_append_child_noinit(child, symbol_tree); + + // make it stop + j=str_clean.length-1; + break; + + default: + if(mode!=SP_NULL_MODE){ + // write to buffer + buffer_ptr=str_addchar(buffer_ptr,str_clean.str[j]); + } + break; + } + } + + free_Char_Array(str_clean); + free(buffer); + return(0); +} +// from char* +int str_to_symbol_tree(char* str, Tree* symbol_tree){ + Char_Array char_array; + str_to_char_array(str,&char_array); + char_array_to_symbol_tree(char_array,symbol_tree); + free_Char_Array(char_array); + return(0); +} + + +// find matching '<' and '>' +int matching_bracket(Char_Array str, int start){ + int bracket_count=0; + int i; + for(i=start;i<str.length;i++){ + if(str.str[i]=='<'){ + bracket_count++; + } + else if(str.str[i]=='>'){ + bracket_count--; + if(bracket_count==0){ + return(i); + } + } + } + // if the function has not returned, then no matching bracket + return(-1); +} + + +// resolve a symbol tree to its corresponding polynomial +int resolve_symbol_tree(Tree symbol_tree, Fields_Table fields, Variables variables, Polynomial* output){ + Polynomial poly; + Tree variable_tree; + + // trivial tree + if(symbol_tree.length==0){ + // variable + if(symbol_tree.root_label.length>0 && symbol_tree.root_label.str[0]=='$'){ + variables_find_var(symbol_tree.root_label, variables, &variable_tree); + resolve_symbol_tree(variable_tree, fields, variables, output); + free_Tree(variable_tree); + } + //polynomial + else{ + Char_Array_to_Polynomial(symbol_tree.root_label, output); + } + } + + // exp + else if (char_array_cmp_str(symbol_tree.root_label,"exp")==1){ + if(symbol_tree.length!=1){ + fprintf(stderr,"syntax error: exp must have 1 argument\n"); + exit(-1); + } + resolve_symbol_tree(symbol_tree.children[0], fields, variables, &poly); + polynomial_exponential(poly, output, fields); + free_Polynomial(poly); + } + + // log + else if (char_array_cmp_str(symbol_tree.root_label,"log_1")==1){ + if(symbol_tree.length!=1){ + fprintf(stderr,"syntax error: log_1 must have 1 argument\n"); + exit(-1); + } + resolve_symbol_tree(symbol_tree.children[0], fields, variables, &poly); + polynomial_logarithm(poly, output, fields); + free_Polynomial(poly); + } + + // product + else if (char_array_cmp_str(symbol_tree.root_label,"*")==1){ + if(symbol_tree.length!=2){ + fprintf(stderr,"syntax error: '*' must have 2 arguments\n"); + exit(-1); + } + resolve_symbol_tree(symbol_tree.children[0], fields, variables, output); + resolve_symbol_tree(symbol_tree.children[1], fields, variables, &poly); + polynomial_prod_chain(poly, output, fields); + free_Polynomial(poly); + } + + // sum + else if (char_array_cmp_str(symbol_tree.root_label,"+")==1){ + if(symbol_tree.length!=2){ + fprintf(stderr,"syntax error: '+' must have 2 arguments\n"); + exit(-1); + } + resolve_symbol_tree(symbol_tree.children[0], fields, variables, output); + resolve_symbol_tree(symbol_tree.children[1], fields, variables, &poly); + polynomial_add_chain_noinit(poly, output, fields); + } + + else{ + fprintf(stderr,"syntax error: unrecognized operation '%s'\n",char_array_to_str_noinit(&(symbol_tree.root_label))); + exit(-1); + } + + return(0); +} |