diff options
Diffstat (limited to 'src/services/quick-answers/math-parser.c')
| -rw-r--r-- | src/services/quick-answers/math-parser.c | 414 |
1 files changed, 0 insertions, 414 deletions
diff --git a/src/services/quick-answers/math-parser.c b/src/services/quick-answers/math-parser.c deleted file mode 100644 index 17d976d..0000000 --- a/src/services/quick-answers/math-parser.c +++ /dev/null @@ -1,414 +0,0 @@ -#include "services/quick-answers/math.h" - -// -// Parser: -// -// The parser context/state which is passed around. -// - -typedef struct _Parser Parser; - -struct _Parser -{ - FoobarMathToken const* tokens; - gsize tokens_count; - gsize position; -}; - -// -// InfixPrecedence: -// -// Value indicating how strongly infix operators should bind. The higher the value, the stronger they should bind. -// - -typedef enum -{ - INFIX_PRECEDENCE_INVALID = -1, - INFIX_PRECEDENCE_NONE = 0, - INFIX_PRECEDENCE_ADDITIVE = 1, - INFIX_PRECEDENCE_MULTIPLICATIVE = 2, - INFIX_PRECEDENCE_EXPONENTS = 3, -} InfixPrecedence; - -static FoobarMathExpression* parser_process ( Parser* ctx, - FoobarMathExpression* lhs, - InfixPrecedence min_precedence ); -static FoobarMathExpression* parser_process_single ( Parser* ctx, - gboolean allow_sign ); -static FoobarMathExpression* parser_process_identifier ( Parser* ctx ); -static FoobarMathExpression* parser_process_number ( Parser* ctx ); -static FoobarMathExpression* parser_process_function ( Parser* ctx, - FoobarMathFunction function ); -static FoobarMathExpression* parser_process_parens ( Parser* ctx ); -static FoobarMathExpression* parser_process_sign ( Parser* ctx ); -static FoobarMathToken const* parser_peek ( Parser const* ctx ); -static FoobarMathToken const* parser_pop ( Parser* ctx ); -static gboolean parser_match_identifier ( FoobarMathToken const* token, - gchar const* identifier ); -static InfixPrecedence parser_operator_precedence( FoobarMathToken const* token ); -static FoobarMathOperation parser_operator ( FoobarMathToken const* token ); - -// --------------------------------------------------------------------------------------------------------------------- -// Parsing -// --------------------------------------------------------------------------------------------------------------------- - -// -// Transform a sequence of tokens into a mathematical expression. -// -// On success, this will return a newly allocated expression which should be freed using foobar_math_expression_free. -// -// On error, this will return NULL. -// -FoobarMathExpression* foobar_math_parse( - FoobarMathToken const* tokens, - gsize tokens_count ) -{ - Parser ctx = { 0 }; - ctx.tokens = tokens; - ctx.tokens_count = tokens_count; - - FoobarMathExpression* lhs = parser_process_single( &ctx, TRUE ); - if ( !lhs ) { return NULL; } - - FoobarMathExpression* expr = parser_process( &ctx, lhs, INFIX_PRECEDENCE_NONE ); - if ( !expr ) { return NULL; } - - if ( parser_peek( &ctx ) ) - { - foobar_math_expression_free( expr ); - return NULL; - } - - return expr; -} - -// -// Process tokens until the end of the current precedence scope (indicated by min_precedence), starting at an operator. -// -FoobarMathExpression* parser_process( - Parser* ctx, - FoobarMathExpression* lhs, - InfixPrecedence min_precedence ) -{ - FoobarMathToken const* op = parser_peek( ctx ); - InfixPrecedence op_precedence = parser_operator_precedence( op ); - while ( op_precedence >= min_precedence ) - { - parser_pop( ctx ); - - FoobarMathExpression* rhs = parser_process_single( ctx, FALSE ); - if ( !rhs ) - { - foobar_math_expression_free( lhs ); - return NULL; - } - - FoobarMathToken const* next_op = parser_peek( ctx ); - while ( parser_operator_precedence( next_op ) > op_precedence ) - { - rhs = parser_process( ctx, rhs, op_precedence + 1 ); - if ( !rhs ) - { - foobar_math_expression_free( lhs ); - return NULL; - } - - next_op = parser_peek( ctx ); - } - - lhs = foobar_math_expression_new_operation( parser_operator( op ), lhs, rhs ); - - op = parser_peek( ctx ); - op_precedence = parser_operator_precedence( op ); - } - - return lhs; -} - -// -// Process a single value which may be either a constant, function, number, expression enclosed in parenthesis or -// negation. -// -// If an unexpected token is encountered (i.e. an operator), this will return FALSE. -// -FoobarMathExpression* parser_process_single( - Parser* ctx, - gboolean allow_sign ) -{ - FoobarMathToken const* token = parser_peek( ctx ); - if ( !token ) { return NULL; } - - switch ( token->type ) - { - case FOOBAR_MATH_TOKEN_IDENTIFIER: - return parser_process_identifier( ctx ); - case FOOBAR_MATH_TOKEN_NUMBER: - return parser_process_number( ctx ); - case FOOBAR_MATH_TOKEN_PAREN_OPEN: - return parser_process_parens( ctx ); - case FOOBAR_MATH_TOKEN_MINUS: - case FOOBAR_MATH_TOKEN_PLUS: - if ( !allow_sign ) { return NULL; } - return parser_process_sign( ctx ); - case FOOBAR_MATH_TOKEN_PAREN_CLOSE: - case FOOBAR_MATH_TOKEN_MUL: - case FOOBAR_MATH_TOKEN_DIV: - case FOOBAR_MATH_TOKEN_POW: - return NULL; - default: - g_warn_if_reached( ); - return NULL; - } -} - -// -// Parse an identifier. -// -// If the identifier is a function, this will expected parenthesis and an expression afterwards. -// -FoobarMathExpression* parser_process_identifier( Parser* ctx ) -{ - FoobarMathToken const* token = parser_pop( ctx ); - if ( parser_match_identifier( token, "pi" ) ) - { - return foobar_math_expression_new_constant( FOOBAR_MATH_CONSTANT_PI ); - } - else if ( parser_match_identifier( token, "e" ) ) - { - return foobar_math_expression_new_constant( FOOBAR_MATH_CONSTANT_E ); - } - else if ( parser_match_identifier( token, "exp" ) ) - { - return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_EXP ); - } - else if ( parser_match_identifier( token, "sqrt" ) ) - { - return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_SQRT ); - } - else if ( parser_match_identifier( token, "sin" ) ) - { - return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_SIN ); - } - else if ( parser_match_identifier( token, "cos" ) ) - { - return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_COS ); - } - else if ( parser_match_identifier( token, "sec" ) ) - { - return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_SEC ); - } - else if ( parser_match_identifier( token, "csc" ) ) - { - return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_CSC ); - } - else if ( parser_match_identifier( token, "tan" ) ) - { - return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_TAN ); - } - else if ( parser_match_identifier( token, "cot" ) ) - { - return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_COT ); - } - else if ( parser_match_identifier( token, "arcsin" ) ) - { - return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_ARCSIN ); - } - else if ( parser_match_identifier( token, "arccos" ) ) - { - return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_ARCCOS ); - } - else if ( parser_match_identifier( token, "arcsec" ) ) - { - return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_ARCSEC ); - } - else if ( parser_match_identifier( token, "arccsc" ) ) - { - return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_ARCCSC ); - } - else if ( parser_match_identifier( token, "arctan" ) ) - { - return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_ARCTAN ); - } - else if ( parser_match_identifier( token, "arccot" ) ) - { - return parser_process_function( ctx, FOOBAR_MATH_FUNCTION_ARCCOT ); - } - else - { - return NULL; - } -} - -// -// Process a numeric value. -// -FoobarMathExpression* parser_process_number( Parser* ctx ) -{ - FoobarMathToken const* token = parser_pop( ctx ); - FoobarMathValue value = { 0 }; - if ( !foobar_math_value_from_string( token->data, token->length, &value ) ) - { - return NULL; - } - - return foobar_math_expression_new_value( value ); -} - -// -// Process a function's parameter which should be enclosed in parenthesis. -// -FoobarMathExpression* parser_process_function( - Parser* ctx, - FoobarMathFunction function ) -{ - FoobarMathToken const* opening_paren = parser_peek( ctx ); - if ( !opening_paren || opening_paren->type != FOOBAR_MATH_TOKEN_PAREN_OPEN ) - { - return NULL; - } - - FoobarMathExpression* arg = parser_process_parens( ctx ); - if ( !arg ) { return NULL; } - - return foobar_math_expression_new_function( function, arg ); -} - -// -// Process an expression enclosed in parenthesis. -// -FoobarMathExpression* parser_process_parens( Parser* ctx ) -{ - parser_pop( ctx ); - FoobarMathExpression* lhs = parser_process_single( ctx, TRUE ); - if ( !lhs ) { return NULL; } - FoobarMathExpression* result = parser_process( ctx, lhs, INFIX_PRECEDENCE_NONE ); - if ( !result ) { return NULL; } - FoobarMathToken const* closing_paren = parser_pop( ctx ); - if ( !closing_paren || closing_paren->type != FOOBAR_MATH_TOKEN_PAREN_CLOSE ) - { - foobar_math_expression_free( result ); - return NULL; - } - return result; -} - -// -// Process a sign (- or +) which may be used for negation of an expression. -// -FoobarMathExpression* parser_process_sign( Parser* ctx ) -{ - FoobarMathToken const* token = parser_pop( ctx ); - FoobarMathExpression* result = parser_process_single( ctx, FALSE ); - if ( !result ) { return NULL; } - - if ( token->type == FOOBAR_MATH_TOKEN_MINUS ) - { - return foobar_math_expression_new_function( FOOBAR_MATH_FUNCTION_NEGATE, result ); - } - else - { - return result; - } -} - -// --------------------------------------------------------------------------------------------------------------------- -// State Helpers -// --------------------------------------------------------------------------------------------------------------------- - -// -// Peek at the current token without consuming it. -// -// If this is the end of the token list, return NULL. -// -FoobarMathToken const* parser_peek( Parser const* ctx ) -{ - if ( ctx->position >= ctx->tokens_count ) { return NULL; } - - return &ctx->tokens[ctx->position]; -} - -// -// Consume the current token. -// -// If this is the end of the token list, return NULL. -// -FoobarMathToken const* parser_pop( Parser* ctx ) -{ - if ( ctx->position >= ctx->tokens_count ) { return NULL; } - - return &ctx->tokens[ctx->position++]; -} - -// --------------------------------------------------------------------------------------------------------------------- -// Helpers -// --------------------------------------------------------------------------------------------------------------------- - -// -// Match a token's string against the given identifier string. -// -// This is necessary because the token's content is not a null-terminated string. -// -gboolean parser_match_identifier( - FoobarMathToken const* token, - gchar const* identifier ) -{ - if ( strlen( identifier ) != token->length ) { return FALSE; } - - return !strncmp( token->data, identifier, token->length ); -} - -// -// Get the precedence of an infix operator token or INVALID. -// -InfixPrecedence parser_operator_precedence( FoobarMathToken const* token ) -{ - if ( token ) - { - switch ( token->type ) - { - case FOOBAR_MATH_TOKEN_PLUS: - case FOOBAR_MATH_TOKEN_MINUS: - return INFIX_PRECEDENCE_ADDITIVE; - case FOOBAR_MATH_TOKEN_MUL: - case FOOBAR_MATH_TOKEN_DIV: - return INFIX_PRECEDENCE_MULTIPLICATIVE; - case FOOBAR_MATH_TOKEN_POW: - return INFIX_PRECEDENCE_EXPONENTS; - case FOOBAR_MATH_TOKEN_IDENTIFIER: - case FOOBAR_MATH_TOKEN_NUMBER: - case FOOBAR_MATH_TOKEN_PAREN_OPEN: - case FOOBAR_MATH_TOKEN_PAREN_CLOSE: - default: - break; - } - } - - return INFIX_PRECEDENCE_INVALID; -} - -// -// Get the operation for an infix operator token. This requires the token to be valid. -// -FoobarMathOperation parser_operator( FoobarMathToken const* token ) -{ - switch ( token->type ) - { - case FOOBAR_MATH_TOKEN_PLUS: - return FOOBAR_MATH_OPERATION_ADD; - case FOOBAR_MATH_TOKEN_MINUS: - return FOOBAR_MATH_OPERATION_SUB; - case FOOBAR_MATH_TOKEN_MUL: - return FOOBAR_MATH_OPERATION_MUL; - case FOOBAR_MATH_TOKEN_DIV: - return FOOBAR_MATH_OPERATION_DIV; - case FOOBAR_MATH_TOKEN_POW: - return FOOBAR_MATH_OPERATION_POW; - case FOOBAR_MATH_TOKEN_IDENTIFIER: - case FOOBAR_MATH_TOKEN_NUMBER: - case FOOBAR_MATH_TOKEN_PAREN_OPEN: - case FOOBAR_MATH_TOKEN_PAREN_CLOSE: - default: - g_warn_if_reached( ); - return 0; - } -} |