Annotation of OpenXM/src/ox_math/parse.c, Revision 1.6
1.1 ohara 1: /* -*- mode: C; coding: euc-japan -*- */
1.6 ! ohara 2: /* $OpenXM: OpenXM/src/ox_math/parse.c,v 1.5 1999/11/03 10:56:40 ohara Exp $ */
1.5 ohara 3:
1.1 ohara 4: /* OX expression, CMO expression パーサ */
5:
6: #include <stdio.h>
7: #include <stdlib.h>
8: #include <string.h>
9: #include <sys/param.h>
1.2 ohara 10: #include <setjmp.h>
1.1 ohara 11: #include "oxtag.h"
12: #include "ox.h"
13: #include "parse.h"
14:
15: /* --- 構文解析部 --- */
1.2 ohara 16: /* (重要)セマンティックスについての注意.
17: CMO_LIST, CMO_STRING は、あらかじめ与えられた要素の個数を無視する.
18: CMO_MONOMIAL32 は無視しない. (つまりおかしいときは構文エラーになる)
19: */
20:
1.1 ohara 21: /* parse.c, lex.c では, Lisp 表現された CMO 文字列を読み込み,
1.5 ohara 22: バイト列を出力する. 中間表現として、cmo 構造体を利用する.
23: parse() はトークンの列から cmo 構造体を生成し、そのポインタを返す.
1.1 ohara 24: */
25:
26: /* 重要なことはパーサ(の各サブルーチン)は
27: 常にトークンをひとつ先読みしていると言うことである.
28: */
29:
30: /* 現在読み込み中のトークンを表す. */
31: static int token = 0;
32:
1.2 ohara 33: /* トークンの属性値. yylval は lex() によってセットされる. */
34: static union{
1.5 ohara 35: int d;
36: char *sym;
1.2 ohara 37: } yylval;
38:
39: /* pflag_cmo_addrev がセットされていれば、厳密には CMO expression では
40: ないもの, 例えば (CMO_STRING, "hello") も CMO に変換される. */
1.1 ohara 41:
1.2 ohara 42: static int pflag_cmo_addrev = 1; /* CMO の省略記法を許すか否かのフラグ */
1.1 ohara 43:
44: /* 関数の宣言 */
1.5 ohara 45: static int parse_error(char *s);
46: static int parse_lf();
47: static int parse_right_parenthesis();
48: static int parse_left_parenthesis();
49: static int parse_comma();
50: static int parse_integer();
1.1 ohara 51: static char *parse_string();
1.5 ohara 52: static cmo *parse_cmo_null();
53: static cmo *parse_cmo_int32();
54: static cmo *parse_cmo_string();
55: static cmo *parse_cmo_mathcap();
56: static cmo *parse_cmo_list();
57: static cmo *parse_cmo_monomial32();
58: static cmo *parse_cmo_zz();
59: static cmo *parse_cmo_zero();
60: static cmo *parse_cmo_dms_generic();
61: static cmo *parse_cmo_ring_by_name();
62: static cmo *parse_cmo_distributed_polynomial();
1.6 ! ohara 63: static cmo *parse_cmo_indeterminate();
1.5 ohara 64: static cmo *parse_cmo_error2();
65: static cmo *parse_cmo();
66: static int parse_sm();
67: static ox *parse_ox();
68: static ox *parse_ox_command();
69: static ox *parse_ox_data();
1.1 ohara 70:
1.3 ohara 71: static int is_token_cmo(int token)
1.1 ohara 72: {
1.2 ohara 73: return (token >= MIN_T_CMO && token < MAX_T_CMO) || token == TOKEN(CMO_ERROR2);
1.1 ohara 74: }
75:
1.3 ohara 76: static int is_token_sm(int token)
1.1 ohara 77: {
1.4 ohara 78: return token == TOKEN(SM);
1.1 ohara 79: }
80:
1.3 ohara 81: static int is_token_ox(int token)
1.1 ohara 82: {
83: return token >= MIN_T_OX && token < MAX_T_OX;
84: }
85:
1.2 ohara 86: static jmp_buf env_parse;
87:
88: /* 構文解析に失敗したことを意味する. */
89: static int parse_error(char *s)
90: {
1.3 ohara 91: fprintf(stderr, "syntax error: %s\n", s);
1.2 ohara 92: longjmp(env_parse, 1);
93: }
94:
1.1 ohara 95: /* この部分は書き換え予定. */
96: cmo *parse()
97: {
98: cmo *m;
99:
1.2 ohara 100: if (setjmp(env_parse) != 0) {
101: return NULL; /* 構文解析に失敗したら NULL を返す. */
102: }
103:
1.1 ohara 104: do{
105: token = lex();
106: }while (token == '\n');
107:
108: if (token == '(') {
109: token = lex();
1.3 ohara 110: if (is_token_cmo(token)) {
1.1 ohara 111: m = parse_cmo();
1.3 ohara 112: }else if(is_token_ox(token)) {
1.1 ohara 113: m = parse_ox();
114: }else {
1.3 ohara 115: parse_error("invalid symbol.");
1.1 ohara 116: }
117: parse_lf();
118: return m;
119: }
120: return NULL;
121: }
122:
123: /* トークンを先読みしない(重要). */
124: static int parse_lf()
125: {
126: if (token != '\n') {
1.3 ohara 127: parse_error("no new line.");
1.1 ohara 128: }
129: return 0;
130: }
131:
132:
1.5 ohara 133: static ox *parse_ox()
1.1 ohara 134: {
135: ox *m = NULL;
136:
137: switch(token) {
1.2 ohara 138: case TOKEN(OX_COMMAND):
1.1 ohara 139: token = lex();
140: m = parse_ox_command();
141: break;
1.2 ohara 142: case TOKEN(OX_DATA):
1.1 ohara 143: token = lex();
144: m = parse_ox_data();
145: break;
146: default:
1.3 ohara 147: parse_error("invalid ox.");
1.1 ohara 148: }
149: return m;
150: }
151:
1.5 ohara 152: static ox *parse_ox_data()
1.1 ohara 153: {
1.5 ohara 154: ox *m;
1.1 ohara 155:
156: parse_comma();
157: parse_left_parenthesis();
158: m = (ox *)new_ox_data(parse_cmo());
159: parse_right_parenthesis();
160: return m;
161: }
162:
1.5 ohara 163: static ox *parse_ox_command()
1.1 ohara 164: {
1.5 ohara 165: ox *m;
1.1 ohara 166:
167: parse_comma();
1.4 ohara 168: parse_left_parenthesis();
1.1 ohara 169: m = (ox *)new_ox_command(parse_sm());
170: parse_right_parenthesis();
171: return m;
172: }
173:
1.4 ohara 174: static int parse_sm()
175: {
176: int sm_code;
177: if (token != TOKEN(SM)) {
178: parse_error("no opecode.");
179: }
180: sm_code = yylval.d;
181: token = lex();
182: parse_right_parenthesis();
183: return sm_code;
184: }
185:
186:
1.1 ohara 187: /* 正しい入力ならば, parse_cmo を呼ぶ時点で, token には
1.2 ohara 188: TOKEN(CMO_xxx), TOKEN(OX_xxx) のいずれかがセットされている. */
1.1 ohara 189: static cmo *parse_cmo()
190: {
191: cmo *m = NULL;
192:
193: switch(token) {
1.2 ohara 194: case TOKEN(CMO_NULL):
1.1 ohara 195: token = lex();
196: m = parse_cmo_null();
197: break;
1.2 ohara 198: case TOKEN(CMO_INT32):
1.1 ohara 199: token = lex();
200: m = parse_cmo_int32();
201: break;
1.2 ohara 202: case TOKEN(CMO_STRING):
1.1 ohara 203: token = lex();
204: m = parse_cmo_string();
205: break;
1.2 ohara 206: case TOKEN(CMO_MATHCAP):
207: token = lex();
208: m = parse_cmo_mathcap();
209: break;
210: case TOKEN(CMO_LIST):
211: token = lex();
212: m = parse_cmo_list();
213: break;
214: case TOKEN(CMO_MONOMIAL32):
215: token = lex();
216: m = parse_cmo_monomial32();
217: break;
218: case TOKEN(CMO_ZZ):
1.1 ohara 219: token = lex();
220: m = parse_cmo_zz();
221: break;
1.2 ohara 222: case TOKEN(CMO_ZERO):
223: token = lex();
224: m = parse_cmo_zero();
225: break;
226: case TOKEN(CMO_DMS_GENERIC):
1.1 ohara 227: token = lex();
1.2 ohara 228: m = parse_cmo_dms_generic();
229: break;
230: case TOKEN(CMO_RING_BY_NAME):
231: token = lex();
232: m = parse_cmo_ring_by_name();
233: break;
1.3 ohara 234: case TOKEN(CMO_DISTRIBUTED_POLYNOMIAL):
235: token = lex();
236: m = parse_cmo_distributed_polynomial();
237: break;
1.6 ! ohara 238: case TOKEN(CMO_INDETERMINATE):
! 239: token = lex();
! 240: m = parse_cmo_indeterminate();
! 241: break;
1.2 ohara 242: case TOKEN(CMO_ERROR2):
243: token = lex();
244: m = parse_cmo_error2();
1.1 ohara 245: break;
246: default:
1.3 ohara 247: parse_error("invalid cmo.");
1.1 ohara 248: }
249: return m;
250: }
251:
1.2 ohara 252: static int parse_left_parenthesis()
1.1 ohara 253: {
1.2 ohara 254: if (token != '(') {
1.3 ohara 255: parse_error("no left parenthesis.");
1.1 ohara 256: }
257: token = lex();
258: }
259:
1.2 ohara 260: static int parse_right_parenthesis()
1.1 ohara 261: {
1.2 ohara 262: if (token != ')') {
1.3 ohara 263: parse_error("no right parenthesis.");
1.1 ohara 264: }
265: token = lex();
266: }
267:
268: static int parse_comma()
269: {
270: if (token != ',') {
1.3 ohara 271: parse_error("no comma.");
1.1 ohara 272: }
273: token = lex();
274: }
275:
276: static int parse_integer()
277: {
278: int val;
279: if (token != T_INTEGER) {
1.3 ohara 280: parse_error("no integer.");
1.1 ohara 281: }
282: val = yylval.d;
283: token = lex();
284: return val;
285: }
286:
287: static char *parse_string()
288: {
289: char *s;
290: if (token != T_STRING) {
1.3 ohara 291: parse_error("no string.");
1.1 ohara 292: }
293: s = yylval.sym;
294: token = lex();
295: return s;
296: }
297:
298: static cmo *parse_cmo_null()
299: {
300: parse_right_parenthesis();
1.2 ohara 301: return (cmo *)new_cmo_null();
1.1 ohara 302: }
303:
304: static cmo *parse_cmo_int32()
305: {
306: int i;
307:
308: parse_comma();
309: i = parse_integer();
310: parse_right_parenthesis();
1.2 ohara 311: return (cmo *)new_cmo_int32(i);
1.1 ohara 312: }
313:
314: static cmo *parse_cmo_string()
315: {
316: cmo_string *m;
317: char *s;
318:
319: parse_comma();
320: if (token == T_INTEGER) {
1.2 ohara 321: parse_integer();
1.1 ohara 322: parse_comma();
1.2 ohara 323: }else if (!pflag_cmo_addrev) {
1.3 ohara 324: parse_error("invalid cmo string.");
1.2 ohara 325: }
326: s = parse_string();
327: m = new_cmo_string(s);
328: parse_right_parenthesis();
329: return (cmo *)m;
330: }
331:
332: static cmo *parse_cmo_mathcap()
333: {
334: cmo *ob;
335:
336: parse_comma();
337: parse_left_parenthesis();
338: ob = parse_cmo();
339: parse_right_parenthesis();
340: return (cmo *)new_cmo_mathcap(ob);
341: }
342:
343: static cmo *parse_cmo_list()
344: {
345: int length=0;
346: int i=0;
347: cmo_list *m = new_cmo_list();
348: cmo *newcmo;
349:
350: if (token == ',') {
351: parse_comma();
352:
353: if (token == T_INTEGER) {
354: parse_integer();
355: parse_comma();
356: }else if (!pflag_cmo_addrev) {
1.3 ohara 357: parse_error("invalid cmo_list.");
1.2 ohara 358: }
359:
360: while(token == '(') {
361: parse_left_parenthesis();
362: newcmo = parse_cmo();
363: append_cmo_list(m, newcmo);
364: if (token != ',') {
365: break;
366: }
367: parse_comma();
368: }
369: }else if (!pflag_cmo_addrev) {
1.3 ohara 370: parse_error("invalid cmo_list.");
1.2 ohara 371: }
372: parse_right_parenthesis();
373: return (cmo *)m;
374: }
375:
376: static cmo *parse_cmo_monomial32()
377: {
378: int size;
379: int *exps;
380: int i;
381: cmo_monomial32 *m;
1.3 ohara 382: int tag;
1.2 ohara 383:
384: parse_comma();
385: size = parse_integer();
1.3 ohara 386: if (size < 0) {
387: parse_error("invalid value.");
1.2 ohara 388: }
389: m = new_cmo_monomial32_size(size);
390:
391: for(i=0; i<size; i++) {
392: parse_comma();
393: m->exps[i] = parse_integer();
394: }
395: parse_comma();
396: parse_left_parenthesis();
397: m->coef = parse_cmo();
1.3 ohara 398: tag = m->coef->tag;
399:
400: /* m->coef は CMO_ZZ 型か CMO_INT32 型でなければならない */
401: if (tag != CMO_ZZ && tag != CMO_INT32) {
402: parse_error("invalid cmo.");
403: }
1.2 ohara 404: parse_right_parenthesis();
405: return (cmo *)m;
406: }
407:
408: /* cmo_zz の内部を直接いじる. */
409: static cmo *parse_cmo_zz()
410: {
411: int length;
412: int i=0;
413: cmo_zz *m= NULL;
414:
415: parse_comma();
416: length = parse_integer();
417: if (token == ',') {
418: m = new_cmo_zz_size(length);
419:
420: length = abs(length);
421: for(i=0; i<length; i++) {
422: parse_comma();
423: m->mpz->_mp_d[i] = parse_integer();
1.1 ohara 424: }
1.2 ohara 425: }else if (pflag_cmo_addrev) {
426: m = new_cmo_zz_set_si(length);
1.1 ohara 427: }else {
1.3 ohara 428: parse_error("no comma.");
1.1 ohara 429: }
1.2 ohara 430:
1.1 ohara 431: parse_right_parenthesis();
432: return (cmo *)m;
433: }
434:
1.2 ohara 435: static cmo *parse_cmo_zero()
436: {
437: parse_right_parenthesis();
438: return (cmo *)new_cmo_zero();
439: }
440:
441: static cmo *parse_cmo_dms_generic()
442: {
443: parse_right_parenthesis();
444: return (cmo *)new_cmo_dms_generic();
445: }
446:
447: static cmo *parse_cmo_ring_by_name()
448: {
449: cmo *ob;
450:
451: parse_comma();
452: parse_left_parenthesis();
453: ob = parse_cmo();
1.3 ohara 454:
455: /* ob は CMO_STRING 型でなければならない */
456: if (ob->tag != CMO_STRING) {
457: parse_error("invalid cmo.");
458: }
1.2 ohara 459: parse_right_parenthesis();
460: return (cmo *)new_cmo_ring_by_name(ob);
461: }
462:
1.3 ohara 463: static cmo *parse_cmo_distributed_polynomial()
464: {
465: int length=0;
466: int i=0;
467: cmo_distributed_polynomial *m = new_cmo_distributed_polynomial();
468: cmo *ob;
469: int tag;
470:
471: if (token == ',') {
472: parse_comma();
473:
474: if (token == T_INTEGER) {
475: parse_integer();
476: parse_comma();
477: }else if (!pflag_cmo_addrev) {
478: parse_error("invalid d-polynomial.");
479: }
480:
481: parse_left_parenthesis();
482: m->ringdef = parse_cmo();
483: tag = m->ringdef->tag;
484: /* m->ringdef は DringDefinition でなければならない */
485: if (tag != CMO_RING_BY_NAME && tag != CMO_DMS_GENERIC
486: && tag != CMO_DMS_OF_N_VARIABLES) {
487: parse_error("invalid cmo.");
488: }
489:
490: parse_comma();
491:
492: while(token == '(') {
493: parse_left_parenthesis();
494: ob = parse_cmo();
495: if (ob->tag != CMO_MONOMIAL32 && ob->tag != CMO_ZERO) {
496: parse_error("invalid cmo.");
497: }
1.6 ! ohara 498: append_cmo_list((cmo_list *)m, ob);
1.3 ohara 499: if (token != ',') {
500: break;
501: }
502: parse_comma();
503: }
504: }else if (!pflag_cmo_addrev) {
505: parse_error("invalid d-polynomial.");
506: }
507: parse_right_parenthesis();
508: return (cmo *)m;
509: }
510:
1.6 ! ohara 511: static cmo *parse_cmo_indeterminate()
! 512: {
! 513: cmo *ob;
! 514:
! 515: parse_comma();
! 516: parse_left_parenthesis();
! 517: ob = parse_cmo();
! 518: parse_right_parenthesis();
! 519: return (cmo *)new_cmo_indeterminate(ob);
! 520: }
1.3 ohara 521:
1.2 ohara 522: static cmo *parse_cmo_error2()
523: {
524: cmo *ob;
525:
526: parse_comma();
527: parse_left_parenthesis();
528: ob = parse_cmo();
529: parse_right_parenthesis();
530: return (cmo *)new_cmo_error2(ob);
531: }
532:
1.1 ohara 533: /* --- 字句解析部 --- */
534:
535: /* lexical analyzer で読み飛ばされる文字なら何を初期値にしてもよい */
536: static int c = ' ';
537:
538: /* 一文字読み込む関数 */
539: static int (*GETC)() = getchar;
540:
541: int setgetc(int (*foo)())
542: {
543: GETC = foo;
544: }
545:
546: int resetgetc()
547: {
548: GETC = getchar;
549: }
550:
1.2 ohara 551: #define SIZE_BUFFER 8192
1.1 ohara 552: static char buffer[SIZE_BUFFER];
553:
554: /* 桁溢れの場合の対策はない */
555: static int lex_digit()
556: {
557: int d = 0;
558: do {
559: d = 10*d + (c - '0');
560: c = GETC();
561: } while(isdigit(c));
562: return d;
563: }
564:
565: /* バッファあふれした場合の対策をちゃんと考えるべき */
566: static char *lex_quoted_string()
567: {
568: int i;
569: char c0 = ' ';
570: char *s = NULL;
571: for (i=0; i<SIZE_BUFFER; i++) {
572: c = GETC();
573: if(c == '"') {
574: s = malloc(i+1);
575: buffer[i]='\0';
576: strcpy(s, buffer);
577:
578: c = GETC();
579: return s;
580: }else if (c == '\\') {
581: c0 = c;
582: c = GETC();
583: if (c != '"') {
584: buffer[i++] = c0;
585: }
586: }
587: buffer[i]=c;
588: }
589: fprintf(stderr, "buffer overflow!\n");
590: exit(1);
591: /* return NULL; */
592: }
593:
1.2 ohara 594: typedef struct {
595: char *key;
1.6 ! ohara 596: int tag;
1.2 ohara 597: int token;
598: } symbol;
599:
1.6 ! ohara 600: #define MK_KEY_CMO(x) { #x , x , TOKEN(x) }
! 601: #define MK_KEY_SM(x) { #x , x , TOKEN(SM) }
! 602: #define MK_KEY(x) { #x , x , TOKEN(x) }
1.2 ohara 603:
604: static symbol symbol_list[] = {
1.3 ohara 605: MK_KEY_CMO(CMO_NULL),
606: MK_KEY_CMO(CMO_INT32),
607: MK_KEY_CMO(CMO_DATUM),
608: MK_KEY_CMO(CMO_STRING),
609: MK_KEY_CMO(CMO_MATHCAP),
610: MK_KEY_CMO(CMO_LIST),
611: MK_KEY_CMO(CMO_MONOMIAL32),
612: MK_KEY_CMO(CMO_ZZ),
613: MK_KEY_CMO(CMO_ZERO),
614: MK_KEY_CMO(CMO_DMS_GENERIC),
615: MK_KEY_CMO(CMO_RING_BY_NAME),
616: MK_KEY_CMO(CMO_INDETERMINATE),
617: MK_KEY_CMO(CMO_DISTRIBUTED_POLYNOMIAL),
618: MK_KEY_CMO(CMO_ERROR2),
1.4 ohara 619: MK_KEY_SM(SM_popCMO),
620: MK_KEY_SM(SM_popString),
621: MK_KEY_SM(SM_mathcap),
622: MK_KEY_SM(SM_pops),
623: MK_KEY_SM(SM_executeStringByLocalParser),
624: MK_KEY_SM(SM_executeFunction),
625: MK_KEY_SM(SM_setMathCap),
626: MK_KEY_SM(SM_control_kill),
627: MK_KEY_SM(SM_control_reset_connection),
628: MK_KEY(OX_COMMAND),
629: MK_KEY(OX_DATA),
1.6 ! ohara 630: {NULL, 0, 0} /* a gate keeper */
1.2 ohara 631: };
632:
633: static int token_of_symbol(char *key)
634: {
635: symbol *kp;
636: for(kp = symbol_list; kp->key != NULL; kp++) {
637: if (strcmp(key, kp->key)==0) {
1.6 ! ohara 638: yylval.d = kp->tag;
1.2 ohara 639: return kp->token;
640: }
641: }
642: #if DEBUG
1.1 ohara 643: fprintf(stderr, "lex error\n");
1.2 ohara 644: #endif
1.1 ohara 645: return 0;
646: }
647:
1.2 ohara 648: static int lex_symbol()
1.1 ohara 649: {
650: int i;
651: for (i=0; i<SIZE_BUFFER; i++) {
652: if (!isalnum(c) && c != '_') {
653: buffer[i]='\0';
1.2 ohara 654: return token_of_symbol(buffer);
1.1 ohara 655: }
656: buffer[i]=c;
657: c = GETC();
658: }
659: fprintf(stderr, "buffer overflow!\n");
1.2 ohara 660: return 0;
1.1 ohara 661: }
662:
1.5 ohara 663: /* return する前に一文字先読みしておく. */
1.1 ohara 664: int lex()
665: {
666: int c_dash = 0;
667:
668: /* 空白をスキップする. */
669: while (isspace(c) && c != '\n') {
670: c = GETC();
671: }
672:
673: switch(c) {
674: case '(':
675: case ')':
676: case ',':
677: case '\n':
678: c_dash = c;
679: c = ' ';
680: return c_dash;
681: case EOF:
682: c = GETC();
683: return c_dash;
684: case '"': /* a quoted string! */
685: yylval.sym = lex_quoted_string();
686: return T_STRING;
687: default:
688: }
689:
690: if (isalpha(c)) { /* 識別子 */
1.2 ohara 691: return lex_symbol();
1.1 ohara 692: }
693:
694: /* 32bit 整数値 */
695: if (isdigit(c)){
696: yylval.d = lex_digit();
697: return T_INTEGER;
698: }
699: if (c == '-') {
700: c = GETC();
701: while (isspace(c) && c != '\n') {
702: c = GETC();
703: }
704: if (isdigit(c)){
705: yylval.d = - lex_digit();
706: return T_INTEGER;
707: }
708: return 0;
709: }
710:
711: c = GETC();
712: return 0;
713: }
714:
1.6 ! ohara 715: /* 一文字読み込む関数 */
1.1 ohara 716: static char *mygetc_line;
717: static int mygetc_counter;
718: static int mygetc_counter_max;
1.6 ! ohara 719: static int mygetc_nonlf_flag;
1.1 ohara 720:
721: int mygetc()
722: {
1.6 ! ohara 723: int c = '\0';
! 724:
! 725: if (mygetc_nonlf_flag && mygetc_counter <= mygetc_counter_max) {
! 726: c = mygetc_line[mygetc_counter++];
! 727: if (c == '\0') {
! 728: c = '\n';
! 729: mygetc_nonlf_flag = 0;
! 730: }
1.1 ohara 731: }
1.6 ! ohara 732: return c;
1.1 ohara 733: }
734:
735: int setmode_mygetc(char *s, int len)
736: {
1.6 ! ohara 737: mygetc_nonlf_flag=1;
1.1 ohara 738: mygetc_counter=0;
739: mygetc_counter_max=len;
740: mygetc_line=s;
1.2 ohara 741: }
742:
743: int setflag_parse(int flag)
744: {
745: pflag_cmo_addrev = flag;
1.1 ohara 746: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>