Hi Edwardedbarx wrote:Hi Tomazzi,
Analising the expression grammar, I found these syntax rules to be checked by the parser.
OK, so what do You expect from me?
Hi Edwardedbarx wrote:Hi Tomazzi,
Analising the expression grammar, I found these syntax rules to be checked by the parser.
I cannot expect anything by right, however, if you feel you want to, I would appreciate some comments whenever you feel a comment is appropriate.tomazzi wrote:Hi Edwardedbarx wrote:Hi Tomazzi,
Analising the expression grammar, I found these syntax rules to be checked by the parser.
OK, so what do You expect from me?
Code: Select all
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#define INVALID 0
#define VALID 1
typedef char* pchar;
pchar* tokens; /* global variable to hold token list */
int token_count = 0; /* global variable to keep track of token count */
int error_pos = 0; /* global variable to hold error position */
#define token_delta 50
typedef struct {
int start_bracket;
int stop_bracket;
int consecutive_brackets;
} t_bracket_values;
void tokenise(char* expression) {
char ch; /* character at iterator's position */
char* atoken; /* token to be added to token list */
char* start = NULL; /* holds a char* to point to start of multicharacter token */
char* string_token; /* holds multicharacter token */
int char_count = 0; /* keeps track of number of characters in multicharacter token */
int while_counter = 0;
/* expr_len_and_null holds the total length of input string including null terminator */
int expr_len_and_null = strlen(expression) + 1;
while (while_counter++ <= expr_len_and_null) {
ch = *expression++;
switch (ch) {
case '(':
case ')':
case '.':
case '+':
case '!':
case '\0':
if (start && char_count > 0) {
string_token = malloc((char_count + 1)*sizeof(char));
strncpy(string_token, start, char_count);
tokens[token_count++] = string_token;
start = NULL;
char_count = 0;
}
if (ch == '\0') return;
atoken = malloc(2*sizeof(char));
atoken[0] = ch;
atoken[1] = '\0';
tokens[token_count++] = atoken;
break;
case '\n':
break;
default:
if (start == NULL)
start = expression - 1;
char_count++;
}
}
}
void free_memory() {
int k = token_count;
while (--k >= 0) free(tokens[k]);
free(tokens);
}
/****************PARSER*****************/
static char* getToken(pchar* tokens, int i) {
if (i < token_count)
return tokens[i];
else return NULL;
}
#define alpha "abcdefghijklmnopqrstuvwxyz"
/* succeeds ". + )" end */
#define alpha_cl_br ")"alpha
/* succeeds "! alpha " */
#define oper_op_br "!+.("
/* at the beginning of expression */
#define alpha_excl_op_br "!("alpha
static int isOperand(pchar* tokens, int i) {
char* atoken = getToken(tokens, i);
if (atoken == NULL)
return 0;
else {
if (strlen(atoken) > 1)
return 1;
else return (strchr(alpha, atoken[0]) != NULL);
}
}
int getErrorPosn(pchar* tokens) {
int i = -1;
char prev_ch = '\0', ch;
int error_pos1 = -1, error_pos2 = -1;
char* atoken;
if (token_count == 1) {
if (!isOperand(tokens, 0))
i = 0;
error_pos = i;
return error_pos;
}
while (++i < token_count) {
atoken = getToken(tokens, i);
ch = atoken[0];
if (i > 0 && i < token_count - 1) {
if ( (ch == '+' || ch == '.' || ch == ')') &&
(prev_ch == ')' || isOperand(tokens, i - 1)) )
{
prev_ch = ch;
continue;
}
if ( (ch == '!' || ch == '(' || isOperand(tokens, i)) &&
strchr(oper_op_br, prev_ch) )
{
prev_ch = ch;
continue;
}
}
prev_ch = ch;
/* at the end of token list */
if ( (i == token_count - 1) && (ch == ')' || isOperand(tokens, i)) )
continue;
/* at the beginning of token list */
if ( (i == 0) && (ch == '!' || ch == '(' || isOperand(tokens, i)) )
continue;
error_pos1 = i;
break;
}
int brackets = 0;
for (i = 0; i < token_count; i++) {
atoken = getToken(tokens, i);
ch = atoken[0];
if (ch == '(') brackets++;
else if (ch == ')')
brackets--;
if (brackets < 0) {
error_pos2 = i;
break;
}
}
if (brackets > 0)
error_pos2 = i;
/* choose the earlier error for output */
if (error_pos1 > error_pos2)
error_pos = error_pos1;
else error_pos = error_pos2;
return error_pos;
}
/***************************************/
int main() {
extern int error_pos;
char input[101];
tokens = malloc(token_delta*sizeof(char*));
fgets(input, 100, stdin);
tokenise(input);
int k = -1;
/* print the tokens one per line */
printf("token count is %d\n", token_count);
while(++k < token_count)
printf("%s\n", tokens[k]);
getErrorPosn(tokens);
if (error_pos > -1)
printf("Error found at position %d\n", error_pos + 1);
else printf("No error found.\n");
free_memory();
return 0;
}
Code: Select all
tokens = malloc(token_delta*sizeof(char*));
Code: Select all
int32_t *pint = 100; pint++ /* gives 104, not 101 */
Code: Select all
atoken = malloc(2*sizeof(char));
Code: Select all
void tokenise(char* expression) ...
static char* getToken(pchar* tokens, int i) ...
Code: Select all
int expr_len_and_null = strlen(expression) + 1;
while (while_counter++ <= expr_len_and_null) {
...
if (ch == '\0') return;
...
}
While I have never seen an example of the contrary, the standard (C99 at least) explicitly allows different sizes for pointers to different types. Casting to (void *) should not lose information, but not the other way around.tomazzi wrote: Size of pointer of any type is always the same as the size of void*
Actually, the standard says about representation and alignment of pointers, not the size (except that sizeof(void*) is platform-dependand)reinob wrote:While I have never seen an example of the contrary, the standard (C99 at least) explicitly allows different sizes for pointers to different types. Casting to (void *) should not lose information, but not the other way around.tomazzi wrote: Size of pointer of any type is always the same as the size of void*
Code: Select all
int32_t var;
void *vptr;
int32_t *ptr32 = 32;
vptr = ptr32;
var = *(++ptr32); /* read from address 36: OK */
var = *((int32_t*) (++vptr)); /* read from address 33: unaligned: crash/warning */
Hmmm... Isn't that the other way around? That is, first dereference the pointer, then increment it (which is known as "post-increment"). Incrementing first, then dereferencing is what wouldn't work, if I understand your code correctly.edbarx wrote:Code: Select all
*t++ means first increment the pointer, then dereference it, otherwise this wouldn't work.
Code: Select all
if(*pString != '\n'){
do_this();
}
else {
HowAboutThis();
AndThisOne();
}
Code: Select all
if(*pString != '\n'){
do_this();
}
else
HowAboutThis();
AndThisOne();
This is a bit tricky, but of course You are right.luvr wrote:Hmmm... Isn't that the other way around? That is, first dereference the pointer, then increment it (which is known as "post-increment"). Incrementing first, then dereferencing is what wouldn't work, if I understand your code correctly.edbarx wrote:Code: Select all
*t++ means first increment the pointer, then dereference it, otherwise this wouldn't work.
Good point, but code blocks (scopes) are in fact far more important:srq2625 wrote:3. Use "{" and "}" (I call these braces) to define code blocks - even blocks of only one line.
Code: Select all
typedef struct {
int err_code;
char err_desc[64];
} err_t;
int func1(void) {
err_t err1, err2;
err1.err_code = some_glibc_fn();
if (0 != err1.err_code) {
strerror_r(err1.err_code, err1.err_desc, 64);
return err1.err_code;
}
err2.err_code = some_glibc_fn();
if (0 != err2.err_code) {
strerror_r(err2.err_code, err2.err_desc, 64);
return err2.err_code;
}
}
int func2(void) {
{
err_t err1;
err1.err_code = some_glibc_fn();
if (0 != err1.err_code) {
strerror_r(err1.err_code, err1.err_desc, 64);
return err1.err_code;
}
}
{
err_t err2;
err2.err_code = some_glibc_fn();
if (0 != err2.err_code) {
strerror_r(err2.err_code, err2.err_desc, 64);
return err2.err_code;
}
}
}
Code: Select all
#ifndef _EXPR_CALC_H_
#define _EXPR_CALC_H_
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define NUMBER_TYPE double
#define token_delta 50
#define CHAR_SIZE sizeof(char)
#define _DEBUG
typedef enum {
id_undef = -1,
id_op, /* operator */
id_sign,
id_br, /* bracket */
id_num
} t_idy;
typedef struct {
t_idy idy;
union {
char cmd;
NUMBER_TYPE num;
};
} t_expr_token;
typedef t_expr_token* p_expr_token;
typedef struct {
t_expr_token* tokens;
int token_count;
int malloc_token_count;
char* fatal_error_ptr;
int error_pos;
int memory_error; /* */
double result;
} t_calc_struct;
t_calc_struct* create_calc(char* expr, int* error);
void init_calc(t_calc_struct* calc);
void free_calc(t_calc_struct* calc);
t_calc_struct* copy_calc(t_calc_struct* source);
int valid_calc_stack(t_calc_struct* calc);
NUMBER_TYPE calc_eval(t_calc_struct* calc);
#endif
Code: Select all
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "expr_calc.h"
void init_calc(t_calc_struct* calc) {
calc->tokens = NULL;
calc->token_count = 0;
calc->malloc_token_count = 0;
calc->fatal_error_ptr = NULL;
calc->error_pos = -1;
calc->result = 0.0;
calc->memory_error = 0;
}
/* returns 1 on success, 0 on failure */
static int malloc_tokens(t_calc_struct* calc) {
void* realloc_res;
int success = 0;
if (calc->malloc_token_count == 0) {
calc->malloc_token_count = token_delta;
calc->tokens = malloc(calc->malloc_token_count*sizeof(t_expr_token));
if (calc->tokens != NULL)
success = 1;
else success = -1;
} else {
calc->malloc_token_count += token_delta;
realloc_res = realloc(calc->tokens, calc->malloc_token_count*sizeof(t_expr_token));
if (realloc_res != NULL)
success = 2;
else success = -2;
}
if (success == 1 || success == 2) {
return 1;
} else if (success < 0) {
calc->malloc_token_count -= token_delta;
return 0;
}
return 0; /* never reached */
}
t_calc_struct* copy_calc(t_calc_struct* source) {
t_calc_struct* dest = malloc(sizeof(t_calc_struct));
if (dest == NULL) return NULL;
*dest = *source;
int j;
dest->tokens = malloc(source->malloc_token_count*sizeof(t_expr_token));
if (dest->tokens == NULL) {
free(dest);
return NULL;
}
for (j = 0; j < source->token_count; j++)
dest->tokens[j] = source->tokens[j];
return dest;
}
void free_calc(t_calc_struct* calc) {
free(calc->tokens);
free(calc);
}
static void do_syntax_check(t_calc_struct* calc);
static char* save_number_to_tokens(t_calc_struct* calc, char* start) {
char* end;
if (start != NULL) {
NUMBER_TYPE x = strtod(start, &end);
calc->tokens[calc->token_count].idy = id_num;
calc->tokens[calc->token_count].num = x;
calc->token_count++;
start = NULL;
}
return end;
}
static void save_single_char_token(t_calc_struct* calc, char ch, t_idy id) {
calc->tokens[calc->token_count].idy = id;
calc->tokens[calc->token_count].cmd = ch;
calc->token_count++;
}
static void tokenise(t_calc_struct* calc, char* expression) {
char ch; /* character at iterator's position */
char* end;
calc->token_count = 0;
calc->error_pos = -1;
calc->fatal_error_ptr = NULL;
if (calc->malloc_token_count == 0 && malloc_tokens(calc) < 0)
return;
t_idy prev_id = id_undef, id;
while (expression) {
if (calc->malloc_token_count == calc->token_count) {
if (malloc_tokens(calc) < 0)
calc->memory_error = 1;
return;
}
ch = *expression;
if (ch == '\0' || ch == '\n') break;
switch (ch) {
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
case '.':
end = save_number_to_tokens(calc, expression);
expression = end;
prev_id = id_num;
continue;
/* these char tokens are fully defined by themselves */
case '(':
case ')':
save_single_char_token(calc, ch, id_br);
prev_id = id_br;
break;
/* these char tokens are fully defined by themselves */
case '*':
case '/':
case '^':
save_single_char_token(calc, ch, id_op);
prev_id = id_op;
break;
case '+':
case '-':
if (
prev_id == '*' ||
prev_id == '/' ||
*(expression - 1) == '(' ||
prev_id == id_undef ||
prev_id == id_sign ||
prev_id == id_op
) id = id_sign;
else id = id_op;
save_single_char_token(calc, ch, id);
prev_id = id;
break;
case ' ':
expression++;
continue;
default:
calc->fatal_error_ptr = expression;
}
expression++;
if (calc->fatal_error_ptr) return;
}
do_syntax_check(calc);
}
static void remove_tokens(t_calc_struct* calc, int from, int count) {
int index = from, insert_pos = from;
for (index = from + count; index < calc->token_count; index++) {
calc->tokens[insert_pos] = calc->tokens[index];
insert_pos++;
}
}
static void simplify_signs(t_calc_struct* calc, int from, int *to) {
int index = from;
int positive = 1, sign_found = 0;
while (index <= *to) {
while (calc->tokens[index].idy == id_sign) {
sign_found++;
if (calc->tokens[index].cmd == '-')
positive = !positive;
index++;
}
if (sign_found) {
remove_tokens(calc, index - sign_found, sign_found);
*to -= sign_found;
calc->token_count -= sign_found;
index -= sign_found;
if (!positive) {
calc->tokens[index].num = -(calc->tokens[index].num);
}
sign_found = 0;
positive = 1;
continue;
}
index++;
}
}
static void do_syntax_check(t_calc_struct* calc) {
int index = -1;
t_idy token_type;
t_expr_token pred;
calc->error_pos = -1;
int brackets = 0;
while (++index < calc->token_count) {
token_type = calc->tokens[index].idy;
switch (token_type) {
case id_op:
/* operator must be between first and last token excluding both ends */
/* operator must succeed a number or a ')' */
if (index > 0 && index < calc->token_count - 1) {
pred = calc->tokens[index - 1];
if (pred.idy == id_num ||(pred.idy == id_br && pred.cmd == ')'))
continue;
}
calc->error_pos = index;
return;
case id_sign:
/* sign must lie between token 0 and last token excluding the last */
/* sign must succeed a '(', a sign and operator*/
if (index == 0) continue;
if (index >= 0 && index < calc->token_count - 1) {
pred = calc->tokens[index - 1];
if (
pred.idy == id_sign || pred.idy == id_op ||
(pred.idy == id_br && pred.cmd == '(')
) continue;
}
calc->error_pos = index;
return;
case id_br:
/* '(' can succeed op, sign, '(' */
/* '(' must lie between token 0 and last one excluding the last token */
/* ')' can succeed ')' and number */
/* ')' must lie from token 2 onwards */
if (calc->tokens[index].cmd == '(') {
brackets++;
if (index == calc->token_count - 1) {
calc->error_pos = index;
return;
}
if (index == 0) continue;
pred = calc->tokens[index - 1];
if (
pred.idy == id_op || pred.idy == id_sign ||
(pred.idy == id_br && pred.cmd == '(')
) continue;
} else {
brackets--;
if (index < 2) {
calc->error_pos = index;
return;
}
if (brackets < 0) {
calc->error_pos = index;
return;
}
pred = calc->tokens[index - 1];
if (pred.idy == id_num || (pred.idy == id_br && pred.cmd == ')'))
continue;
}
calc->error_pos = index;
return;
case id_num:
/* number can succeed operator, sign and '(' */
/* number can be first and last token */
if (index == 0 || index == calc->token_count - 1)
continue;
pred = calc->tokens[index - 1];
if (
pred.idy == id_op || pred.idy == id_sign ||
(pred.idy == id_br && pred.cmd == '(')
) continue;
calc->error_pos = index;
return;
case id_undef:
calc->error_pos = index;
return;
}
}
if (brackets > 0) {
calc->error_pos = index + 1;
}
}
static void do_binary_op(t_calc_struct* calc, char op, int from, int *to) {
NUMBER_TYPE tmp_res;
int index = from + 1;
while (index < *to) {
if (calc->tokens[index].idy == id_op && calc->tokens[index].cmd == op) {
switch (op) {
case '^':
tmp_res = pow(calc->tokens[index - 1].num, calc->tokens[index + 1].num);
break;
case '*':
tmp_res = calc->tokens[index - 1].num * calc->tokens[index + 1].num;
break;
case '/':
tmp_res = calc->tokens[index - 1].num / calc->tokens[index + 1].num;
break;
case '+':
tmp_res = calc->tokens[index - 1].num + calc->tokens[index + 1].num;
break;
case '-':
tmp_res = calc->tokens[index - 1].num - calc->tokens[index + 1].num;
break;
}
/* save tokens at */
remove_tokens(calc, index, 2);
calc->token_count -= 2;
calc->tokens[index - 1].idy = id_num;
calc->tokens[index - 1].num = tmp_res;
*to -= 2;
} else index += 2;
}
}
static NUMBER_TYPE evaluate_fn(t_calc_struct* calc) {
if (calc->fatal_error_ptr || calc->error_pos > -1 || calc->token_count == 0) return 0.0;
int open_br = -1, close_br = -1, index = 0;
/* search tokens for ')' starting from token 0 */
while (index < calc->token_count) {
if (calc->tokens[index].idy == id_br && calc->tokens[index].cmd == ')') {
close_br = index;
break;
}
index++;
}
/* search tokens for '(' searching backwards from close_br */
index--;
while (index > -1) {
if (calc->tokens[index].idy == id_br && calc->tokens[index].cmd == '(') {
open_br = index;
break;
}
index--;
}
int to = -1;
/* do the actual computation */
if (close_br > -1 && open_br > -1) {
to = close_br - 1;
simplify_signs(calc, open_br + 1, &to);
do_binary_op(calc, '^', open_br + 1, &to);
do_binary_op(calc, '/', open_br + 1, &to);
do_binary_op(calc, '*', open_br + 1, &to);
do_binary_op(calc, '+', open_br + 1, &to);
do_binary_op(calc, '-', open_br + 1, &to);
remove_tokens(calc, to + 1, 1);
remove_tokens(calc, open_br, 1);
calc->token_count -= 2;
} else {
to = calc->token_count - 1;
simplify_signs(calc, 0, &to);
do_binary_op(calc, '^', 0, &to);
do_binary_op(calc, '/', 0, &to);
do_binary_op(calc, '*', 0, &to);
do_binary_op(calc, '+', 0, &to);
do_binary_op(calc, '-', 0, &to);
}
if (calc->token_count > 1)
evaluate_fn(calc);
if (calc->tokens[0].idy == id_num)
return calc->tokens[0].num;
else return 0.0;
}
int valid_calc_stack(t_calc_struct* calc) {
return (calc->error_pos == -1 && calc->fatal_error_ptr == NULL);
}
t_calc_struct* create_calc(char* expr, int* error) {
t_calc_struct* calc = malloc(sizeof(t_calc_struct));
if (calc == NULL) return NULL;
init_calc(calc);
tokenise(calc, expr);
if (error != NULL) *error = calc->error_pos;
return calc;
}
NUMBER_TYPE calc_eval(t_calc_struct* calc) {
t_calc_struct* tmp_calc =copy_calc(calc);
if (tmp_calc == NULL) {
/* TODO: must set a variable indicating memory failure */
return 0.0;
}
NUMBER_TYPE x = evaluate_fn(tmp_calc);
free_calc(tmp_calc);
return x;
}
Code: Select all
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "expr_calc.h"
int main() {
char input[1024];
fgets(input, 1023, stdin);
t_calc_struct* calc = create_calc(input, NULL);
#ifdef DEBUG
int i = 0;
for (i = 0; i < calc->token_count; i++) {
switch (calc->tokens[i]->idy) {
case id_sign:
printf("sign: %c\n", calc->tokens[i]->cmd);
break;
case id_op:
printf("operat: %c\n", calc->tokens[i]->cmd);
break;
case id_br:
printf("bracket: %c\n", calc->tokens[i]->cmd);
break;
case id_num:
printf("number: %f\n", calc->tokens[i]->num);
break;
case id_undef:
printf("something strange happened at index %d\n", i);
break;
}
}
#endif
NUMBER_TYPE x;
if (valid_calc_stack(calc)) {
x = calc_eval(calc);
printf("result = %f\n", x);
} else printf("error_pos = %d\n", calc->error_pos);
free_calc(calc);
return 0;
}
The devil is in the details, Ed.edbarx wrote:...
For those interested to give me feedback about its quality, I tell them there is NO need for them to examine every detail of the code.