symbolic4
parser.c
Go to the documentation of this file.
1 
2 /*
3 
4  Copyright (c) 2019 Hannes Eberhard
5 
6  Permission is hereby granted, free of charge, to any person obtaining a copy
7  of this software and associated documentation files (the "Software"), to deal
8  in the Software without restriction, including without limitation the rights
9  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10  copies of the Software, and to permit persons to whom the Software is
11  furnished to do so, subject to the following conditions:
12 
13  The above copyright notice and this permission notice shall be included in all
14  copies or substantial portions of the Software.
15 
16  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22  SOFTWARE.
23 
24  */
25 
26 #include "symbolic4.h"
27 
28 /**
29 
30  @brief Determines the expression type of a character
31 
32  @details
33  It can't distinguish between @c EXPT_VALUE and @c EXPT_FUNCTION.
34 
35  @param[in] source The character to analyze.
36 
37  @return
38  - The expression type or @c EXPT_NULL when an unexpected character
39  was encountered.
40 
41  */
42 expression_type get_expression_type(char source) {
43  if (isalpha(source) || isdigit(source) || source == '.') {
44  return EXPT_VALUE;
45  } else if (strchr("=+-/*^", source)) {
46  return EXPT_OPERATION;
47  } else if (strchr(",()", source)) {
48  return EXPT_CONTROL;
49  } else {
50  return EXPT_NULL;
51  }
52 }
53 
54 /**
55 
56  @brief Determines the expression identifier of a character of the
57  type EXPT_VALUE
58 
59  @param[in] source The character to analyze.
60 
61  @return
62  - The expression type or @c EXPT_NULL when an unexpected character
63  was encountered.
64 
65  */
66 expression_identifier get_value_identifier(char source) {
67  if (isalpha(source)) {
68  return EXPI_SYMBOL;
69  } else if (isdigit(source) || source == '.') {
70  return EXPI_LITERAL;
71  } else {
72  return EXPI_NULL;
73  }
74 }
75 
76 /**
77 
78  @brief Determines the expression identifier of a character of the
79  type EXPT_OPERATION
80 
81  @param[in] source The character to analyze.
82 
83  @return
84  - The expression type or @c EXPT_NULL when an unexpected character
85  was encountered.
86 
87  */
88 expression_identifier get_operator_identifier(char source) {
89  if (source == '=') {
90  return EXPI_EQUATION;
91  } else if (source == '+') {
92  return EXPI_ADDITION;
93  } else if (source == '-') {
94  return EXPI_SUBTRACTION;
95  } else if (source == '*') {
96  return EXPI_MULTIPLICATION;
97  } else if (source == '/') {
98  return EXPI_DIVISION;
99  } else if (source == '^') {
100  return EXPI_EXPONENTATION;
101  } else {
102  return EXPI_NULL;
103  }
104 }
105 
106 /**
107 
108  @brief Determines the expression identifier of a character of the
109  type EXPT_CONTROL
110 
111  @param[in] source The character to analyze.
112 
113  @return
114  - The expression type or @c EXPT_NULL when an unexpected character
115  was encountered.
116 
117  */
118 expression_identifier get_control_identifier(char source) {
119  if (source == ',') {
120  return EXPI_COMMA;
121  } else if (source == '(') {
122  return EXPI_LEFT_PARENTHESIS;
123  } else if (source == ')') {
124  return EXPI_RIGHT_PARENTHESIS;
125  } else {
126  return EXPI_NULL;
127  }
128 }
129 
130 /**
131 
132  @brief Appends a multiplication expression if necessary
133 
134  @details
135  This function appends a multiplication if
136 
137  - the token array is not empty
138 
139  - and the last expression in the token array is either a value or
140  a close parenthesis.
141 
142  @param[in,out] tokens The token array the multiplication should be
143  appended to.
144 
145  */
146 void append_multiplication_if_necessary(expression* tokens) {
147  if (tokens->child_count > 0 && (tokens->children[tokens->child_count - 1]->type == EXPT_VALUE || tokens->children[tokens->child_count - 1]->identifier == EXPI_RIGHT_PARENTHESIS)) {
148  append_child(tokens, new_expression(EXPT_OPERATION, EXPI_MULTIPLICATION, 0));
149  }
150 }
151 
152 uint8_t tokenize_buffer(expression* tokens, char* buffer) {
153 
154  uint8_t i, j;
155  char* lowercase_buffer = string_to_lower(buffer);
156  char* lowercase_keyword = NULL;
157  char* keyword_occurrence = NULL;
158  uint8_t keyword_occurrence_position;
159 
160  /* search for pi */
161  while ((keyword_occurrence = strstr(lowercase_buffer, "pi")) != NULL) {
162  keyword_occurrence_position = keyword_occurrence - lowercase_buffer;
163  append_multiplication_if_necessary(tokens);
164  lowercase_buffer[keyword_occurrence_position] = '~';
165  lowercase_buffer[keyword_occurrence_position + 1] = '~';
166  append_child(tokens, new_symbol(EXPI_SYMBOL, "pi"));
167  }
168 
169  /* search for functions */
170  for (i = 0; keyword_strings[i] != NULL; i++) {
171  lowercase_keyword = string_to_lower(keyword_strings[i]);
172  if ((keyword_occurrence = strstr(lowercase_buffer, lowercase_keyword)) != NULL) {
173  if (strlen(keyword_occurrence) != strlen(keyword_strings[i])) continue;
174  smart_free(lowercase_keyword);
175  break;
176  }
177  smart_free(lowercase_keyword);
178  }
179 
180  keyword_occurrence_position = (keyword_identifiers[i] != EXPI_NULL) ? keyword_occurrence - lowercase_buffer : strlen(lowercase_buffer);
181 
182  for (j = 0; j < keyword_occurrence_position; j++) {
183  if (lowercase_buffer[j] != '~') {
184  append_multiplication_if_necessary(tokens);
185  append_child(tokens, new_symbol(EXPI_SYMBOL, &buffer[j]));
186  tokens->children[tokens->child_count - 1]->value.symbolic[1] = '\0';
187  }
188  }
189 
190  if (keyword_identifiers[i] != EXPI_NULL) {
191  append_multiplication_if_necessary(tokens);
192  append_child(tokens, new_expression(EXPT_FUNCTION, keyword_identifiers[i], 0));
193  }
194 
195  smart_free(lowercase_buffer);
196 
197  return RETS_SUCCESS;
198 
199 }
200 
201 uint8_t string_to_literal(expression** result, const char* source) {
202 
203  uint8_t i = 0;
204  int8_t sign = 1;
205  uintmax_t a = 0;
206  uintmax_t b = 0;
207  uintmax_t c = 1;
208  expression* literal;
209 
210  if (source[0] == '-') {
211  sign = -1;
212  i++;
213  }
214 
215  for ( ; isdigit(source[i]); i++) {
216  a = 10 * a + (source[i] - '0');
217 // if (a > pow(2, sizeof(uintmax_t) * 8) / 10) return set_error(ERRD_SYSTEM, ERRI_MAX_INT_VALUE_EXCEEDED, "");
218  }
219 
220  if (source[i] == '.') {
221 
222  for (i = i + 1; isdigit(source[i]); i++) {
223  b = 10 * b + (source[i] - '0');
224  c *= 10;
225  }
226 
227  if (source[i] == '.') return set_error(ERRD_PARSER, ERRI_SYNTAX, "");
228 
229  }
230 
231  literal = new_literal(1, b, c);
232  simplify(literal, false);
233  literal->value.numeric.numerator += a * literal->value.numeric.denominator;
234 
235  *result = literal;
236 
237  return RETS_SUCCESS;
238 
239 }
240 
241 uint8_t tokenize_value_expression(expression* tokens, uint8_t* index, const char* source) {
242 
243  expression_identifier identifier = get_value_identifier(source[*index]);
244  expression* literal;
245  char buffer[100];
246  uint8_t buffer_position = 0;
247 
248  while (get_value_identifier(source[*index]) == identifier) {
249  buffer[buffer_position++] = source[(*index)++];
250  }
251 
252  buffer[buffer_position] = '\0';
253 
254  if (identifier == EXPI_SYMBOL) {
255  ERROR_CHECK(tokenize_buffer(tokens, buffer));
256  } else {
257  ERROR_CHECK(string_to_literal(&literal, buffer));
258  append_multiplication_if_necessary(tokens);
259  append_child(tokens, literal);
260  }
261 
262  (*index)--;
263 
264  return RETS_SUCCESS;
265 
266 }
267 
268 void tokenize_operator_expression(expression* tokens, char source) {
269 
270  expression_identifier identifier = get_operator_identifier(source);
271 
272  if (identifier == EXPI_SUBTRACTION && (tokens->child_count == 0 || tokens->children[tokens->child_count - 1]->type == EXPT_OPERATION || (tokens->children[tokens->child_count - 1]->type == EXPT_CONTROL && tokens->children[tokens->child_count - 1]->identifier != EXPI_RIGHT_PARENTHESIS))) {
273  append_child(tokens, new_literal(-1, 1, 1));
274  append_child(tokens, new_expression(EXPT_OPERATION, EXPI_MULTIPLICATION, 0));
275  } else {
276  append_child(tokens, new_expression(EXPT_OPERATION, identifier, 0));
277  }
278 
279 }
280 
281 void tokenize_control_expression(expression* tokens, char source) {
282 
283  expression_identifier identifier = get_control_identifier(source);
284 
285  if (identifier == EXPI_LEFT_PARENTHESIS) {
286  append_multiplication_if_necessary(tokens);
287  }
288 
289  append_child(tokens, new_expression(EXPT_CONTROL, identifier, 0));
290 
291 }
292 
293 uint8_t tokenize(expression* tokens, const char* query) {
294 
295  uint8_t i;
296 
297  for (i = 0; query[i] != '\0'; i++) {
298 
299  if (query[i] == ' ') continue;
300 
301  switch (get_expression_type(query[i])) {
302  case EXPT_VALUE:
303  ERROR_CHECK(tokenize_value_expression(tokens, &i, query));
304  break;
305  case EXPT_OPERATION:
306  tokenize_operator_expression(tokens, query[i]);
307  break;
308  case EXPT_CONTROL:
309  tokenize_control_expression(tokens, query[i]);
310  break;
311  default:
312  return set_error(ERRD_PARSER, ERRI_UNEXPECTED_CHARACTER, "");
313  }
314 
315  }
316 
317  return RETS_SUCCESS;
318 
319 }
320 
321 uint8_t validate(expression* tokens) {
322 
323  uint8_t i;
324  int8_t open_parentheses = 0;
325  expression* tuple[2];
326 
327  tuple[1] = tokens->children[0];
328 
329  for (i = 0; i < tokens->child_count; i++) {
330 
331  tuple[0] = tuple[1];
332  tuple[1] = tokens->children[i];
333 
334  if (tokens->children[i]->identifier == EXPI_LEFT_PARENTHESIS) open_parentheses++;
335  if (tokens->children[i]->identifier == EXPI_RIGHT_PARENTHESIS) open_parentheses--;
336 
337  if (tuple[0]->type == EXPT_VALUE) {
338 
339  if (tuple[0] == tuple[1]) continue;
340 
341  if (tuple[1]->type == EXPT_VALUE) {
342  return set_error(ERRD_PARSER, ERRI_SYNTAX, "");
343  } else if (tuple[1]->type == EXPT_FUNCTION) {
344  return set_error(ERRD_PARSER, ERRI_SYNTAX, "");
345  } else if (tuple[1]->identifier == EXPI_LEFT_PARENTHESIS) {
346  return set_error(ERRD_PARSER, ERRI_SYNTAX, "");
347  }
348 
349  } else if (tuple[0]->type == EXPT_OPERATION) {
350 
351  if (tuple[1]->type == EXPT_OPERATION) {
352  return set_error(ERRD_PARSER, ERRI_SYNTAX, "");
353  } else if (tuple[1]->type == EXPT_CONTROL && tuple[1]->identifier != EXPI_LEFT_PARENTHESIS) {
354  return set_error(ERRD_PARSER, ERRI_SYNTAX, "");
355  }
356 
357  } else if (tuple[0]->type == EXPT_FUNCTION) {
358 
359  if (tuple[0] == tuple[1] && i == 0) continue;
360 
361  if (tuple[1]->identifier != EXPI_LEFT_PARENTHESIS) {
362  return set_error(ERRD_PARSER, ERRI_SYNTAX, "");
363  }
364 
365  }
366 
367  }
368 
369  if (open_parentheses < 0) return set_error(ERRD_PARSER, ERRI_PARENTHESIS_MISMATCH, "");
370 
371  return RETS_SUCCESS;
372 
373 }
374 
375 void merge_expressions_with_operator(expression* output_stack, expression* operator_stack) {
376 
377  uint8_t i;
378  uint8_t child_count = 0;
379 
380  switch (operator_stack->children[operator_stack->child_count - 1]->type) {
381  case EXPT_OPERATION:
382  child_count = 2;
383  break;
384  case EXPT_FUNCTION:
385  while (output_stack->children[output_stack->child_count - child_count - 1]->identifier != EXPI_LEFT_PARENTHESIS) {
386  child_count++;
387  }
388  break;
389  case EXPT_CONTROL:
390  free_expression(operator_stack->children[operator_stack->child_count - 1], false);
391  operator_stack->child_count--;
392  return;
393  default:
394  break;
395  }
396 
397  for (i = 0; i < child_count; i++) {
398  append_child(operator_stack->children[operator_stack->child_count - 1], output_stack->children[output_stack->child_count - child_count + i]);
399  }
400 
401  if (operator_stack->children[operator_stack->child_count - 1]->type == EXPT_FUNCTION) {
402  output_stack->child_count--;
403  }
404 
405  output_stack->child_count -= child_count;
406  append_child(output_stack, operator_stack->children[operator_stack->child_count - 1]);
407  operator_stack->child_count--;
408 
409 }
410 
411 void parse_control_expression(expression* tokens, uint8_t* index, expression* output_stack, expression* operator_stack) {
412 
413  switch (tokens->children[*index]->identifier) {
414 
415  case EXPI_COMMA:
416 
417  while (operator_stack->children[operator_stack->child_count - 1]->identifier != EXPI_LEFT_PARENTHESIS) {
418  merge_expressions_with_operator(output_stack, operator_stack);
419  }
420 
421  break;
422 
423  case EXPI_LEFT_PARENTHESIS:
424  append_child(operator_stack, tokens->children[*index]);
425  break;
426 
427  case EXPI_RIGHT_PARENTHESIS:
428 
429  while (operator_stack->children[operator_stack->child_count - 1]->identifier != EXPI_LEFT_PARENTHESIS) {
430  merge_expressions_with_operator(output_stack, operator_stack);
431  }
432 
433  free_expression(operator_stack->children[operator_stack->child_count - 1], false);
434  operator_stack->child_count--;
435 
436  if (operator_stack->child_count > 0) {
437  if (operator_stack->children[operator_stack->child_count - 1]->type == EXPT_FUNCTION) {
438  merge_expressions_with_operator(output_stack, operator_stack);
439  }
440  }
441 
442  break;
443 
444  default:
445  break;
446 
447  }
448 
449 }
450 
451 void parse(expression* tokens) {
452 
453  uint8_t i;
454  expression* output_stack = new_expression(EXPT_STRUCTURE, EXPI_LIST, 0);
455  expression* operator_stack = new_expression(EXPT_STRUCTURE, EXPI_LIST, 0);
456 
457  for (i = 0; i < tokens->child_count; i++) {
458 
459  switch (tokens->children[i]->type) {
460 
461  case EXPT_VALUE:
462  append_child(output_stack, tokens->children[i]);
463  break;
464 
465  case EXPT_OPERATION:
466  while (operator_stack->child_count > 0 &&
467  tokens->children[i]->identifier <= operator_stack->children[operator_stack->child_count - 1]->identifier &&
468  tokens->children[i]->identifier != EXPI_EXPONENTATION &&
469  operator_stack->children[operator_stack->child_count - 1]->identifier != EXPI_LEFT_PARENTHESIS) {
470  merge_expressions_with_operator(output_stack, operator_stack);
471  }
472  append_child(operator_stack, tokens->children[i]);
473  break;
474 
475  case EXPT_FUNCTION:
476  append_child(output_stack, new_expression(EXPT_CONTROL, EXPI_LEFT_PARENTHESIS, 0));
477  append_child(operator_stack, tokens->children[i]);
478  break;
479 
480  case EXPT_CONTROL:
481  parse_control_expression(tokens, &i, output_stack, operator_stack);
482  break;
483 
484  default:
485  break;
486 
487  }
488 
489  }
490 
491  while (operator_stack->child_count > 0) {
492  merge_expressions_with_operator(output_stack, operator_stack);
493  }
494 
495  *tokens = *copy_expression(output_stack->children[0]);
496 
497  free_expression(output_stack, false);
498  free_expression(operator_stack, false);
499 
500 }
EXPI_LIST
Definition: expression.h:90
EXPI_NULL
Definition: expression.h:42
EXPT_FUNCTION
Definition: expression.h:35
numeric_value::denominator
uintmax_t denominator
Definition: expression.h:109
symbolic4.h
parse_control_expression
void parse_control_expression(expression *tokens, uint8_t *index, expression *output_stack, expression *operator_stack)
Definition: parser.c:411
validate
uint8_t validate(expression *tokens)
Definition: parser.c:321
EXPI_LEFT_PARENTHESIS
Definition: expression.h:95
EXPI_EXPONENTATION
Definition: expression.h:53
expression::symbolic
char symbolic[10]
Definition: expression.h:128
expression::type
expression_type type
Definition: expression.h:114
EXPI_SYMBOL
Definition: expression.h:45
tokenize_control_expression
void tokenize_control_expression(expression *tokens, char source)
Definition: parser.c:281
expression_identifier
expression_identifier
Definition: expression.h:40
EXPI_COMMA
Definition: expression.h:94
expression
Definition: expression.h:112
expression::identifier
expression_identifier identifier
Definition: expression.h:115
ERRI_UNEXPECTED_CHARACTER
Definition: foundation.h:52
EXPT_CONTROL
Definition: expression.h:37
EXPT_STRUCTURE
Definition: expression.h:36
EXPI_RIGHT_PARENTHESIS
Definition: expression.h:96
ERRD_PARSER
Definition: foundation.h:39
ERRI_SYNTAX
Definition: foundation.h:55
smart_free
void smart_free(void *pointer)
Frees a pointer.
Definition: foundation.c:112
get_operator_identifier
expression_identifier get_operator_identifier(char source)
Determines the expression identifier of a character of the type EXPT_OPERATION.
Definition: parser.c:88
ERROR_CHECK
#define ERROR_CHECK(F)
Check if the return status of a function is RETS_ERROR. If so, return RETS_ERROR.
Definition: foundation.h:31
EXPT_VALUE
Definition: expression.h:33
new_symbol
expression * new_symbol(expression_identifier identifier, const char *value)
Allocates and initializes a new symbol/variable expression.
Definition: expression.c:252
expression::value
union expression::@0 value
merge_expressions_with_operator
void merge_expressions_with_operator(expression *output_stack, expression *operator_stack)
Definition: parser.c:375
RETS_SUCCESS
Definition: foundation.h:67
string_to_lower
char * string_to_lower(const char *string)
Converts a string to lowercase.
Definition: foundation.c:206
free_expression
void free_expression(expression *source, bool persistent)
Definition: expression.c:315
string_to_literal
uint8_t string_to_literal(expression **result, const char *source)
Definition: parser.c:201
EXPI_MULTIPLICATION
Definition: expression.h:51
set_error
uint8_t set_error(error_domain domain, error_identifier identifier, const char *body)
Sets current_error to the arguments provided.
Definition: foundation.c:152
tokenize_value_expression
uint8_t tokenize_value_expression(expression *tokens, uint8_t *index, const char *source)
Definition: parser.c:241
tokenize
uint8_t tokenize(expression *tokens, const char *query)
Definition: parser.c:293
EXPT_OPERATION
Definition: expression.h:34
expression_type
expression_type
Definition: expression.h:31
expression::numeric
numeric_value numeric
Definition: expression.h:129
append_multiplication_if_necessary
void append_multiplication_if_necessary(expression *tokens)
Appends a multiplication expression if necessary.
Definition: parser.c:146
get_control_identifier
expression_identifier get_control_identifier(char source)
Determines the expression identifier of a character of the type EXPT_CONTROL.
Definition: parser.c:118
copy_expression
expression * copy_expression(const expression *source)
Returns a deep copy of an expression.
Definition: expression.c:286
EXPI_SUBTRACTION
Definition: expression.h:50
get_value_identifier
expression_identifier get_value_identifier(char source)
Determines the expression identifier of a character of the type EXPT_VALUE.
Definition: parser.c:66
simplify
uint8_t simplify(expression *source, bool recursive)
Definition: simplify.c:1117
append_child
void append_child(expression *parent, expression *child)
Appends a child to an expression.
Definition: expression.c:383
keyword_strings
char * keyword_strings[]
Definition: expression.c:28
new_expression
expression * new_expression(expression_type type, expression_identifier identifier, uint8_t child_count,...)
Allocates and initializes a new expression with the arguments provided.
Definition: expression.c:183
EXPI_EQUATION
Definition: expression.h:48
tokenize_buffer
uint8_t tokenize_buffer(expression *tokens, char *buffer)
Definition: parser.c:152
get_expression_type
expression_type get_expression_type(char source)
Determines the expression type of a character.
Definition: parser.c:42
keyword_identifiers
expression_identifier keyword_identifiers[]
Definition: expression.c:91
new_literal
expression * new_literal(int8_t sign, uintmax_t numerator, uintmax_t denominator)
Allocates and initializes a new literal expression.
Definition: expression.c:225
EXPI_ADDITION
Definition: expression.h:49
EXPT_NULL
Definition: expression.h:32
expression::child_count
uint8_t child_count
Definition: expression.h:119
ERRI_PARENTHESIS_MISMATCH
Definition: foundation.h:56
tokenize_operator_expression
void tokenize_operator_expression(expression *tokens, char source)
Definition: parser.c:268
expression::children
struct expression ** children
Definition: expression.h:124
numeric_value::numerator
uintmax_t numerator
Definition: expression.h:108
EXPI_DIVISION
Definition: expression.h:52
parse
void parse(expression *tokens)
Definition: parser.c:451
EXPI_LITERAL
Definition: expression.h:44