URL https://opencores.org/ocsvn/socgen/socgen/trunk

Subversion Repositories socgen

[/] [socgen/] [trunk/] [tools/] [math/] [c_arith.c] - Blame information for rev 134

Details | Compare with Previous | View Log


#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
 
unsigned int G_STRING_ITERATOR = 0;
 
/*
 * expr        := term term_tail
 * term_tail   := add_op term term_tail | e
 * term        := factor factor_tail
 * factor_tail := mult_op factor factor_tail | e
 * factor      := ( expr ) | number
 * add_op      := + | -
 * mult_op     := * | /
 */
 
typedef union {
  int terminal;
  struct expression* expr[2];
} Data;
 
typedef struct expression {
  char op;
  Data data;
} Expr;
 
void parse_error(const char* string) {
  unsigned int i;
  fprintf(stderr, "Unexpected symbol '%c' at position %u.\n\n", string[G_STRING_ITERATOR], G_STRING_ITERATOR);
  fprintf(stderr, "String: '%s'\n", string);
  fprintf(stderr, "Problem: ");
  for(i = 0; i < G_STRING_ITERATOR; ++i) {
    fprintf(stderr, " ");
  }
  fprintf(stderr, "^\n");
  exit(1);
}
 
/* Will "consume" a character from the input,
 * (such as +, -, *, etc.) and return it.
 * By consume, I'm really just moving the pointer
 * forward and disregarding the character for
 * future purposes.
 */
char consume_char(const char* string, char c) {
  if(string[G_STRING_ITERATOR] != c) {
    parse_error(string);
  }
  ++G_STRING_ITERATOR;
  return c;
}
 
/* Same as consume_char, except for integers.
 */
int consume_int(const char* string) {
  int i;
 
  if(!isdigit(string[G_STRING_ITERATOR])) {
    parse_error(string);
  }
 
  /* I don't have to pass in the start of the string
   * into atoi, but only where I want it to start
   * scanning for an integer.
   */
  i = atoi(string + G_STRING_ITERATOR);
  while(isdigit(string[G_STRING_ITERATOR])) {
    ++G_STRING_ITERATOR;
  }
  return i;
}
 
Expr* expression(const char* string);
 
Expr* factor(const char* string, Expr* expr) {
  if(string[G_STRING_ITERATOR] == '(') {
    expr->op = consume_char(string, '(');
    expr->data.expr[0] = expression(string);
    consume_char(string, ')');
  } else if(isdigit(string[G_STRING_ITERATOR])) {
    expr->op = 'd';
    expr->data.terminal = consume_int(string);
  }
  return expr;
}
 
Expr* factor_tail(const char* string, Expr* expr) {
  Expr* new_expr;
 
  switch(string[G_STRING_ITERATOR]) {
  case '*':
  case '/':
    if(NULL == (new_expr = (Expr*)malloc(sizeof(Expr)))) {
      exit(1);
    }
    if(NULL == (new_expr->data.expr[1] = (Expr*)malloc(sizeof(Expr)))) {
      exit(1);
    }
    new_expr->op = consume_char(string, string[G_STRING_ITERATOR]);
    new_expr->data.expr[0] = expr;
 
    new_expr->data.expr[1] = factor(string, new_expr->data.expr[1]);
    new_expr = factor_tail(string, new_expr);
    return new_expr;
  case '+':
  case '-':
  case ')':
  case 0:
    return expr;
  default:
    parse_error(string);
  }
}
 
Expr* term(const char* string, Expr* expr) {
  if(string[G_STRING_ITERATOR] == '(' || isdigit(string[G_STRING_ITERATOR])) {
    expr = factor(string, expr);
    expr = factor_tail(string, expr);
    return expr;
  } else {
    parse_error(string);
  }
}
 
Expr* term_tail(const char* string, Expr* expr) {
  Expr* new_expr;
 
  switch(string[G_STRING_ITERATOR]) {
  case '+':
  case '-':
    if(NULL == (new_expr = (Expr*)malloc(sizeof(Expr)))) {
      exit(1);
    }
    if(NULL == (new_expr->data.expr[1] = (Expr*)malloc(sizeof(Expr)))) {
      exit(1);
    }
    new_expr->op = consume_char(string, string[G_STRING_ITERATOR]);
    new_expr->data.expr[0] = expr;
 
    new_expr->data.expr[1] = term(string, new_expr->data.expr[1]);
    new_expr = term_tail(string, new_expr);
    return new_expr;
  case ')':
  case 0:
    return expr;
  default:
    parse_error(string);
  }
}
 
Expr* expression(const char* string) {
  Expr* expr;
 
  if(string[G_STRING_ITERATOR] == '(' || isdigit(string[G_STRING_ITERATOR])) {
    if(NULL == (expr = (Expr*)malloc(sizeof(Expr)))) {
      exit(1);
    }
 
    expr = term(string, expr);
    expr = term_tail(string, expr);
    return expr;
  } else {
    parse_error(string);
  }
}
 
/* Runs through the AST, evaluating and freeing
 * the tree as it goes.
 */
int evaluate(Expr* expr) {
  int ret;
 
  switch(expr->op) {
  case '(':
    ret = evaluate(expr->data.expr[0]);
    free(expr->data.expr[0]);
    break;
  case '*':
    ret =
      evaluate(expr->data.expr[0])
      *
      evaluate(expr->data.expr[1])
      ;
    free(expr->data.expr[0]);
    free(expr->data.expr[1]);
    break;
  case '/':
    ret =
      evaluate(expr->data.expr[0])
      /
      evaluate(expr->data.expr[1])
      ;
    free(expr->data.expr[0]);
    free(expr->data.expr[1]);
    break;
  case '+':
    ret =
      evaluate(expr->data.expr[0])
      +
      evaluate(expr->data.expr[1])
      ;
    free(expr->data.expr[0]);
    free(expr->data.expr[1]);
    break;
  case '-':
    ret =
      evaluate(expr->data.expr[0])
      -
      evaluate(expr->data.expr[1])
      ;
    free(expr->data.expr[0]);
    free(expr->data.expr[1]);
    break;
  case 'd':
    ret = expr->data.terminal;
    break;
  default:
    exit(1);
  }
  return ret;
}
 
int main(int argc, char** argv) {
  Expr* expr = NULL;
 
  if(argc > 1) {
    expr = expression(argv[1]);
    printf("%d\n", evaluate(expr));
    free(expr);
  }
  return 0;
}

Browse

Tools

Subversion Repositories socgen

[/] [socgen/] [trunk/] [tools/] [math/] [c_arith.c] - Blame information for rev 134

Line No.	Rev	Author	Line
1	134	jt_eaton	`#include <stdlib.h>`
2			`#include <stdio.h>`
3			`#include <ctype.h>`
4
5			`unsigned int G_STRING_ITERATOR = 0;`
6
7			`/*`
8			`* expr := term term_tail`
9			`* term_tail := add_op term term_tail \| e`
10			`* term := factor factor_tail`
11			`* factor_tail := mult_op factor factor_tail \| e`
12			`* factor := ( expr ) \| number`
13			`* add_op := + \| -`
14			`* mult_op := * \| /`
15			`*/`
16
17			`typedef union {`
18			`int terminal;`
19			`struct expression* expr[2];`
20			`} Data;`
21
22			`typedef struct expression {`
23			`char op;`
24			`Data data;`
25			`} Expr;`
26
27			`void parse_error(const char* string) {`
28			`unsigned int i;`
29			`fprintf(stderr, "Unexpected symbol '%c' at position %u.\n\n", string[G_STRING_ITERATOR], G_STRING_ITERATOR);`
30			`fprintf(stderr, "String: '%s'\n", string);`
31			`fprintf(stderr, "Problem: ");`
32			`for(i = 0; i < G_STRING_ITERATOR; ++i) {`
33			`fprintf(stderr, " ");`
34			`}`
35			`fprintf(stderr, "^\n");`
36			`exit(1);`
37			`}`
38
39			`/* Will "consume" a character from the input,`
40			`* (such as +, -, *, etc.) and return it.`
41			`* By consume, I'm really just moving the pointer`
42			`* forward and disregarding the character for`
43			`* future purposes.`
44			`*/`
45			`char consume_char(const char* string, char c) {`
46			`if(string[G_STRING_ITERATOR] != c) {`
47			`parse_error(string);`
48			`}`
49			`++G_STRING_ITERATOR;`
50			`return c;`
51			`}`
52
53			`/* Same as consume_char, except for integers.`
54			`*/`
55			`int consume_int(const char* string) {`
56			`int i;`
57
58			`if(!isdigit(string[G_STRING_ITERATOR])) {`
59			`parse_error(string);`
60			`}`
61
62			`/* I don't have to pass in the start of the string`
63			`* into atoi, but only where I want it to start`
64			`* scanning for an integer.`
65			`*/`
66			`i = atoi(string + G_STRING_ITERATOR);`
67			`while(isdigit(string[G_STRING_ITERATOR])) {`
68			`++G_STRING_ITERATOR;`
69			`}`
70			`return i;`
71			`}`
72
73			`Expr* expression(const char* string);`
74
75			`Expr* factor(const char* string, Expr* expr) {`
76			`if(string[G_STRING_ITERATOR] == '(') {`
77			`expr->op = consume_char(string, '(');`
78			`expr->data.expr[0] = expression(string);`
79			`consume_char(string, ')');`
80			`} else if(isdigit(string[G_STRING_ITERATOR])) {`
81			`expr->op = 'd';`
82			`expr->data.terminal = consume_int(string);`
83			`}`
84			`return expr;`
85			`}`
86
87			`Expr* factor_tail(const char* string, Expr* expr) {`
88			`Expr* new_expr;`
89
90			`switch(string[G_STRING_ITERATOR]) {`
91			`case '*':`
92			`case '/':`
93			`if(NULL == (new_expr = (Expr*)malloc(sizeof(Expr)))) {`
94			`exit(1);`
95			`}`
96			`if(NULL == (new_expr->data.expr[1] = (Expr*)malloc(sizeof(Expr)))) {`
97			`exit(1);`
98			`}`
99			`new_expr->op = consume_char(string, string[G_STRING_ITERATOR]);`
100			`new_expr->data.expr[0] = expr;`
101
102			`new_expr->data.expr[1] = factor(string, new_expr->data.expr[1]);`
103			`new_expr = factor_tail(string, new_expr);`
104			`return new_expr;`
105			`case '+':`
106			`case '-':`
107			`case ')':`
108			`case 0:`
109			`return expr;`
110			`default:`
111			`parse_error(string);`
112			`}`
113			`}`
114
115			`Expr* term(const char* string, Expr* expr) {`
116			`if(string[G_STRING_ITERATOR] == '(' \|\| isdigit(string[G_STRING_ITERATOR])) {`
117			`expr = factor(string, expr);`
118			`expr = factor_tail(string, expr);`
119			`return expr;`
120			`} else {`
121			`parse_error(string);`
122			`}`
123			`}`
124
125			`Expr* term_tail(const char* string, Expr* expr) {`
126			`Expr* new_expr;`
127
128			`switch(string[G_STRING_ITERATOR]) {`
129			`case '+':`
130			`case '-':`
131			`if(NULL == (new_expr = (Expr*)malloc(sizeof(Expr)))) {`
132			`exit(1);`
133			`}`
134			`if(NULL == (new_expr->data.expr[1] = (Expr*)malloc(sizeof(Expr)))) {`
135			`exit(1);`
136			`}`
137			`new_expr->op = consume_char(string, string[G_STRING_ITERATOR]);`
138			`new_expr->data.expr[0] = expr;`
139
140			`new_expr->data.expr[1] = term(string, new_expr->data.expr[1]);`
141			`new_expr = term_tail(string, new_expr);`
142			`return new_expr;`
143			`case ')':`
144			`case 0:`
145			`return expr;`
146			`default:`
147			`parse_error(string);`
148			`}`
149			`}`
150
151			`Expr* expression(const char* string) {`
152			`Expr* expr;`
153
154			`if(string[G_STRING_ITERATOR] == '(' \|\| isdigit(string[G_STRING_ITERATOR])) {`
155			`if(NULL == (expr = (Expr*)malloc(sizeof(Expr)))) {`
156			`exit(1);`
157			`}`
158
159			`expr = term(string, expr);`
160			`expr = term_tail(string, expr);`
161			`return expr;`
162			`} else {`
163			`parse_error(string);`
164			`}`
165			`}`
166
167			`/* Runs through the AST, evaluating and freeing`
168			`* the tree as it goes.`
169			`*/`
170			`int evaluate(Expr* expr) {`
171			`int ret;`
172
173			`switch(expr->op) {`
174			`case '(':`
175			`ret = evaluate(expr->data.expr[0]);`
176			`free(expr->data.expr[0]);`
177			`break;`
178			`case '*':`
179			`ret =`
180			`evaluate(expr->data.expr[0])`
181			`*`
182			`evaluate(expr->data.expr[1])`
183			`;`
184			`free(expr->data.expr[0]);`
185			`free(expr->data.expr[1]);`
186			`break;`
187			`case '/':`
188			`ret =`
189			`evaluate(expr->data.expr[0])`
190			`/`
191			`evaluate(expr->data.expr[1])`
192			`;`
193			`free(expr->data.expr[0]);`
194			`free(expr->data.expr[1]);`
195			`break;`
196			`case '+':`
197			`ret =`
198			`evaluate(expr->data.expr[0])`
199			`+`
200			`evaluate(expr->data.expr[1])`
201			`;`
202			`free(expr->data.expr[0]);`
203			`free(expr->data.expr[1]);`
204			`break;`
205			`case '-':`
206			`ret =`
207			`evaluate(expr->data.expr[0])`
208			`-`
209			`evaluate(expr->data.expr[1])`
210			`;`
211			`free(expr->data.expr[0]);`
212			`free(expr->data.expr[1]);`
213			`break;`
214			`case 'd':`
215			`ret = expr->data.terminal;`
216			`break;`
217			`default:`
218			`exit(1);`
219			`}`
220			`return ret;`
221			`}`
222
223			`int main(int argc, char** argv) {`
224			`Expr* expr = NULL;`
225
226			`if(argc > 1) {`
227			`expr = expression(argv[1]);`
228			`printf("%d\n", evaluate(expr));`
229			`free(expr);`
230			`}`
231			`return 0;`
232			`}`