Commits

PioneerAxon committed fdb7ba8

Parser frame

ParserState, ParserNode and Associativity.
LL (*) parser structure

  • Participants
  • Parent commits 8365ed1

Comments (0)

Files changed (3)

 CC=gcc
 CFLAGS=-c -Wall `pkg-config --cflags glib-2.0` -I.
 
-math-parser: prelexer.o lexer.o main.o
-	$(CC) -o math-parser prelexer.o lexer.o main.o `pkg-config --libs glib-2.0`
+math-parser: prelexer.o lexer.o parser.o main.o
+	$(CC) -o math-parser prelexer.o lexer.o parser.o main.o `pkg-config --libs glib-2.0`
 
 prelexer.o: prelexer.c prelexer.h
 	$(CC) $(CFLAGS) prelexer.c
 lexer.o: lexer.c lexer.h
 	$(CC) $(CFLAGS) lexer.c
 
+parser.o: parser.c parser.h
+	$(CC) $(CFLAGS) parser.c
+
 main.o: main.c prelexer.h
 	$(CC) $(CFLAGS) main.c
 
+#include<stdlib.h>
+
+#include<parser.h>
+
+Associativity
+p_get_associativity (LexerToken* token) {
+	LexerTokenType type = token->token_type;
+	if (type == T_NUMBER
+	 || type == T_L_FLOOR
+	 || type == T_R_FLOOR
+	 || type == T_L_CEILING
+	 || type == T_R_CEILING
+	 || type == T_ADD
+	 || type == T_SUBTRACT
+	 || type == T_NOT
+	 || type == T_AND
+	 || type == T_OR
+	 || type == T_XOR
+	 || type == T_MULTIPLY
+	 || type == T_DIVIDE
+	 || type == T_MOD
+	 || type == T_ROOT
+	 || type == T_ROOT_3
+	 || type == T_ROOT_4
+	 || type == T_VARIABLE
+	 || type == T_FUNCTION
+	 || type == T_PERCENTAGE
+	 || type == T_IN)
+		return LEFT_ASSOCIATIVE;
+	if (type == T_SUB_NUMBER
+	 || type == T_SUP_NUMBER
+	 || type == T_NSUP_NUMBER)
+		return RIGHT_ASSOCIATIVE;
+//	printf("NO ASSOCIATIVITY FOUND..\n");
+	return LEFT_ASSOCIATIVE;
+}
+
+/* Always returns highest value of precedence from p_get_precedence () + 1. */
+guint
+p_get_highest_precedence () {
+	return 15;
+}
+
+guint
+p_get_precedence (LexerToken* token) {
+	LexerTokenType type = token->token_type;
+	if (type == T_NUMBER)
+		return 1;
+	if (type == T_L_FLOOR
+	 || type == T_R_FLOOR
+	 || type == T_L_CEILING
+	 || type == T_R_CEILING)
+		return 2;
+	if (type == T_ADD
+	 || type == T_SUBTRACT)
+		return 3;
+	if (type == T_MULTIPLY)
+		return 4;
+	if (type == T_DIVIDE)
+		return 5;
+	if (type == T_NOT)
+		return 6;
+	if (type == T_ROOT
+	 || type == T_ROOT_3
+	 || type == T_ROOT_4)
+		return 7;
+	if (type == T_VARIABLE
+	 || type == T_FUNCTION)
+		return 8;
+	if (type == T_SUB_NUMBER
+	 || type == T_SUP_NUMBER
+	 || type == T_NSUP_NUMBER)
+		return 9;
+	if (type == T_AND
+	 || type == T_OR
+	 || type == T_XOR)
+		return 10;
+	if (type == T_PERCENTAGE)
+		return 11;
+//UNARY MINUS	if (type == T_SUBTRACT) return 12;
+	if (type == T_POWER
+	 || type == T_FACTORIAL
+	 || type == T_ABS)
+		return 13;
+	if (type == T_IN)
+		return 14;
+
+	return 0;
+}
+
+ParseNode*
+p_create_node (ParserState* state, LexerToken* token) {
+	ParseNode* new;
+	new = (ParseNode*) malloc (sizeof (ParseNode));
+	new->parent = NULL;
+	new->left = NULL;
+	new->right = NULL;
+	new->token = token;
+	new->precedence = p_get_precedence (token) + (state->depth_level * p_get_highest_precedence ());
+	return new;
+}
+
+void
+p_insert_into_tree (ParserState* state, ParseNode* node) {
+	if (state->root == NULL) {
+		state->root = node;
+	}
+}
+
+
+/* LL (*) parser. Lookahead count depends on tokens. Handle with care. :P */
+
+guint expression (ParserState* state);
+guint expression_1 (ParserState* state);
+guint expression_2 (ParserState* state);
+guint term (ParserState* state);
+guint unit (ParserState* state);
+guint variable (ParserState* state);
+guint term (ParserState* state);
+guint term_2 (ParserState* state);
+
+guint
+statement (ParserState* state) {
+	LexerToken* 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_ASSIGN) {
+			//TODO: assignment statement.
+			if (!expression (state))
+				return 0;
+			return 1;
+		}
+		else if (token->token_type == T_IN) {
+			//TODO: conversion rate statement.
+			return 1;
+		}
+		else if (token->token_type == T_SUP_NUMBER) {
+			token = l_get_next_token (state->lexer);
+			if (token->token_type == T_IN) {
+				//TODO: conversion rate with sup_num statement.
+				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 = 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) {
+				//TODO: conversion statement.
+				return 1;
+			}
+			else if (token->token_type == T_SUP_NUMBER) {
+				token = l_get_next_token (state->lexer);
+				if (token->token_type == T_IN) {
+					//TODO: conversion with sup_num statement.
+					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 {
+		if (!expression (state))
+			return 0;
+		return 1;
+	}
+}
+
+guint
+unit (ParserState* state) {
+	LexerToken* 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_SUP_NUMBER) {
+			//TODO: make unit with sup_num.
+			return 1;
+		}
+		else {
+			l_roll_back (state->lexer);
+			//TODO: unit.
+			return 1;
+		}
+	}
+	else {
+		l_roll_back (state->lexer);
+		//TODO: ERROR
+		return 0;
+	}
+}
+
+guint
+expression (ParserState* state) {
+	if (!expression_1 (state))
+		return 0;
+	if (!expression_2 (state))
+		return 0;
+	return 1;
+}
+
+guint
+expression_1 (ParserState* state) {
+	LexerToken* token;
+	token = l_get_next_token (state->lexer);
+	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++;
+		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++;
+		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++;
+		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) {
+		state->depth_level++;
+		if (!expression (state))
+			return 0;
+		state->depth_level--;
+		return 1;
+	}
+	else if (token->token_type == T_NUMBER) {
+		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) {
+			if (!variable (state))
+				return 0;
+			else
+				return 1;
+		}
+		else {
+			return 1;
+		}
+	}
+	else if (token->token_type == T_L_FLOOR) {
+		state->depth_level++;
+		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++;
+		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) {
+		token = l_get_next_token (state->lexer);
+		if (token->token_type == T_NUMBER) {
+			//TODO: negate Number here..
+			return 1;
+		}
+		else
+		//Expected Number here...
+			return 0;
+	}
+	else if (token->token_type == T_ADD) {
+		token = l_get_next_token (state->lexer);
+		if (token->token_type == T_NUMBER) {
+			//TODO: positive Number here..
+			return 1;
+		}
+		else
+		//Expected Number here...
+			return 0;
+	}
+	else {
+		l_roll_back (state->lexer);
+		if (!variable (state))
+			return 0;
+		else
+			return 1;
+	}
+}
+
+guint
+expression_2 (ParserState* state) {
+	LexerToken* token;
+	token = l_get_next_token (state->lexer);
+	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--;
+			if (!expression_2 (state))
+				return 0;
+			return 1;
+		}
+		else {
+			return 0;
+		}
+	}
+	else if (token->token_type == T_POWER) {
+		if (!expression (state))
+			return 0;
+		if (!expression_2 (state))
+			return 0;
+		return 1;
+		
+	}
+	else if (token->token_type == T_SUP_NUMBER) {
+		if (!expression_2 (state))
+			return 0;
+		return 1;	
+	}
+	else if (token->token_type == T_NSUP_NUMBER) {
+		if (!expression_2 (state))
+			return 0;
+		return 1;
+	}
+	else if (token->token_type == T_FACTORIAL) {
+		if (!expression_2 (state))
+			return 0;
+		return 1;	
+	}
+	else if (token->token_type == T_MULTIPLY) {
+		if (!expression (state))
+			return 0;
+		if (!expression_2 (state))
+			return 0;
+		return 1;
+	}
+	else if (token->token_type == T_PERCENTAGE) {
+		if (!expression_2 (state))
+			return 0;
+		return 1;
+	}
+	else if (token->token_type == T_AND) {
+		if (!expression (state))
+			return 0;
+		if (!expression_2 (state))
+			return 0;
+		return 1;
+	}
+	else if (token->token_type == T_OR) {
+		if (!expression (state))
+			return 0;
+		if (!expression_2 (state))
+			return 0;
+		return 1;
+	}
+	else if (token->token_type == T_XOR) {
+		if (!expression (state))
+			return 0;
+		if (!expression_2 (state))
+			return 0;
+		return 1;
+	}
+	else if (token->token_type == T_DIVIDE) {
+		if (!expression (state))
+			return 0;
+		token = l_get_next_token (state->lexer);
+		//Special case...
+		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--;
+				if (!expression_2 (state))
+					return 0;
+				return 1;
+			}
+			else
+				return 0;
+		}
+		else {
+			l_roll_back (state->lexer);
+			if (!expression_2 (state))
+				return 0;
+			return 1;
+		}
+	}
+	else if (token->token_type == T_MOD) {
+		if (!expression (state))
+			return 0;
+		token = l_get_next_token (state->lexer);
+		//Special case...
+		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--;
+				if (!expression_2 (state))
+					return 0;
+				return 1;
+			}
+			else
+				return 0;
+		}
+		else {
+			l_roll_back (state->lexer);
+			if (!expression_2 (state))
+				return 0;
+			return 1;
+		}
+	}
+	else if (token->token_type == T_ADD) {
+		if (!expression (state))
+			return 0;
+		token = l_get_next_token (state->lexer);
+		if (token->token_type == T_PERCENTAGE) {
+		}
+		else {
+			l_roll_back (state->lexer);
+		}
+		if (!expression_2 (state))
+			return 0;
+		return 1;
+	}
+	else if (token->token_type == T_SUBTRACT) {
+		if (!expression (state))
+			return 0;
+		token = l_get_next_token (state->lexer);
+		if (token->token_type == T_PERCENTAGE) {
+		}
+		else {
+			l_roll_back (state->lexer);
+		}
+		if (!expression_2 (state))
+			return 0;
+		return 1;
+	}
+	else {
+		return 0;
+	}
+}
+
+guint
+variable (ParserState* state) {
+	LexerToken* token;
+	token = l_get_next_token (state->lexer);
+	if (token->token_type == T_FUNCTION) {
+		token = l_get_next_token (state->lexer);
+		if (token->token_type == T_SUP_NUMBER) {
+			//TODO: function with sup_num power.
+			return 1;
+		}
+		else if (token->token_type == T_NSUP_NUMBER) {
+			//TODO: function with nsup_num power.
+			return 1;
+		}
+		else {
+			l_roll_back (state->lexer);
+			if (!expression (state))
+				return 0;
+			return 1;
+		}
+	}
+	else if (token->token_type == T_SUB_NUMBER) {
+		token = l_get_next_token (state->lexer);
+		if (token->token_type == T_ROOT) {
+			//TODO: nth root of exp.
+			if (!expression (state))
+				return 0;
+			return 1;
+		}
+		else {
+			//TODO: ERROR.
+			return 0;
+		}
+	}
+	else if (token->token_type == T_ROOT) {
+		//TODO: sqrt of exp.
+		if (!expression (state))
+			return 0;
+		return 1;
+	}
+	else if (token->token_type == T_ROOT_3) {
+		//TODO: cuberoot of exp.
+		if (!expression (state))
+			return 0;
+		return 1;
+	}
+	else if (token->token_type == T_ROOT_4) {
+		//TODO: 4th root of exp.
+		if (!expression (state))
+			return 0;
+		return 1;
+	}
+	else if (token->token_type == T_VARIABLE) {
+		l_roll_back (state->lexer);
+		//TODO: term and unknown function ERROR.
+		if (!term (state))
+			return 0;
+		return 1;
+	}
+	else {
+		//TODO: ERROR.
+		return 0;
+	}
+}
+
+guint
+term (ParserState* state) {
+	LexerToken* 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_SUP_NUMBER) {
+			l_roll_back (state->lexer);
+		}
+		if(!term_2 (state))
+			return 0;
+		return 1;
+	}
+	else {
+		//TODO: ERROR.
+		return 0;
+	}
+}
+
+guint
+term_2 (ParserState* state) {
+	LexerToken* token;
+	token = l_get_next_token (state->lexer);
+	l_roll_back (state->lexer);
+	if (token->token_type == T_VARIABLE) {
+		if (!term (state))
+			return 0;
+		return 1;
+	}
+	else {
+		return 1;
+	}
+}
+#include <lexer.h>
+
+typedef enum {
+	LEFT_ASSOCIATIVE,
+	RIGHT_ASSOCIATIVE
+} Associativity;
+
+typedef struct {
+	struct ParseNode *parent;
+	struct ParseNode *left, *right;
+	LexerToken *token;
+	guint precedence;
+	void* value;
+	void (*function) (struct ParseNode* self);
+} ParseNode;
+
+typedef struct {
+	ParseNode *root;
+	ParseNode *next_parent;
+	LexerState *lexer;
+	guint depth_level;
+} ParserState;