Ruby 1.9.2p136(2010-12-25revision30365)

- Main Page
- Modules
- Data Structures
- Files

- File List
- Globals

# ext/racc/cparse/cparse.c

Go to the documentation of this file.

    00001 /*
    00002
    00003     cparse.c -- Racc Runtime Core
    00004
    00005     Copyright (c) 1999-2006 Minero Aoki
    00006
    00007     This library is free software.
    00008     You can distribute/modify this program under the same terms of ruby.
    00009
    00010     $originalId: cparse.c,v 1.8 2006/07/06 11:39:46 aamine Exp $
    00011
    00012 */
    00013
    00014 #include "ruby/ruby.h"
    00015
    00016 #ifndef FALSE
    00017 #define FALSE 0
    00018 #endif
    00019 #ifndef TRUE
    00020 #define TRUE 1
    00021 #endif
    00022
    00023 /* -----------------------------------------------------------------------
    00024                         Important Constants
    00025 ----------------------------------------------------------------------- */
    00026
    00027 #define RACC_VERSION "1.4.5"
    00028
    00029 #define DEFAULT_TOKEN -1
    00030 #define ERROR_TOKEN    1
    00031 #define FINAL_TOKEN    0
    00032
    00033 #define vDEFAULT_TOKEN  INT2FIX(DEFAULT_TOKEN)
    00034 #define vERROR_TOKEN    INT2FIX(ERROR_TOKEN)
    00035 #define vFINAL_TOKEN    INT2FIX(FINAL_TOKEN)
    00036
    00037 /* -----------------------------------------------------------------------
    00038                           File Local Variables
    00039 ----------------------------------------------------------------------- */
    00040
    00041 static VALUE RaccBug;
    00042 static VALUE CparseParams;
    00043
    00044 static ID id_yydebug;
    00045 static ID id_nexttoken;
    00046 static ID id_onerror;
    00047 static ID id_noreduce;
    00048 static ID id_errstatus;
    00049
    00050 static ID id_d_shift;
    00051 static ID id_d_reduce;
    00052 static ID id_d_accept;
    00053 static ID id_d_read_token;
    00054 static ID id_d_next_state;
    00055 static ID id_d_e_pop;
    00056
    00057 /* -----------------------------------------------------------------------
    00058                               Utils
    00059 ----------------------------------------------------------------------- */
    00060
    00061 /* For backward compatibility */
    00062 #ifndef ID2SYM
    00063 # define ID2SYM(i) ULONG2NUM(i)
    00064 #endif
    00065 #ifndef SYM2ID
    00066 #  define SYM2ID(v) ((ID)NUM2ULONG(v))
    00067 #endif
    00068 #ifndef SYMBOL_P
    00069 #  define SYMBOL_P(v) FIXNUM_P(v)
    00070 #endif
    00071 #ifndef LONG2NUM
    00072 #  define LONG2NUM(i) INT2NUM(i)
    00073 #endif
    00074
    00075 static ID value_to_id _((VALUE v));
    00076 static inline long num_to_long _((VALUE n));
    00077
    00078 static ID
    00079 value_to_id(VALUE v)
    00080 {
    00081     if (! SYMBOL_P(v)) {
    00082         rb_raise(rb_eTypeError, "not symbol");
    00083     }
    00084     return SYM2ID(v);
    00085 }
    00086
    00087 static inline long
    00088 num_to_long(VALUE n)
    00089 {
    00090     return NUM2LONG(n);
    00091 }
    00092
    00093 #define AREF(s, idx) \
    00094     ((0 <= idx && idx < RARRAY_LEN(s)) ? RARRAY_PTR(s)[idx] : Qnil)
    00095
    00096 /* -----------------------------------------------------------------------
    00097                         Parser Stack Interfaces
    00098 ----------------------------------------------------------------------- */
    00099
    00100 static VALUE get_stack_tail _((VALUE stack, long len));
    00101 static void cut_stack_tail _((VALUE stack, long len));
    00102
    00103 static VALUE
    00104 get_stack_tail(VALUE stack, long len)
    00105 {
    00106     if (len < 0) return Qnil;  /* system error */
    00107     if (len > RARRAY_LEN(stack)) len = RARRAY_LEN(stack);
    00108     return rb_ary_new4(len, RARRAY_PTR(stack) + RARRAY_LEN(stack) - len);
    00109 }
    00110
    00111 static void
    00112 cut_stack_tail(VALUE stack, long len)
    00113 {
    00114     while (len > 0) {
    00115         rb_ary_pop(stack);
    00116         len--;
    00117     }
    00118 }
    00119
    00120 #define STACK_INIT_LEN 64
    00121 #define NEW_STACK() rb_ary_new2(STACK_INIT_LEN)
    00122 #define PUSH(s, i) rb_ary_store(s, RARRAY_LEN(s), i)
    00123 #define POP(s) rb_ary_pop(s)
    00124 #define LAST_I(s) \
    00125     ((RARRAY_LEN(s) > 0) ? RARRAY_PTR(s)[RARRAY_LEN(s) - 1] : Qnil)
    00126 #define GET_TAIL(s, len) get_stack_tail(s, len)
    00127 #define CUT_TAIL(s, len) cut_stack_tail(s, len)
    00128
    00129 /* -----------------------------------------------------------------------
    00130                        struct cparse_params
    00131 ----------------------------------------------------------------------- */
    00132
    00133 struct cparse_params {
    00134     VALUE value_v;         /* VALUE version of this struct */
    00135
    00136     VALUE parser;          /* parser object */
    00137
    00138     int   lex_is_iterator;
    00139     VALUE lexer;           /* scanner object */
    00140     ID    lexmid;          /* name of scanner method (must be an iterator) */
    00141
    00142     /* State transition tables (immutable)
    00143        Data structure is from Dragon Book 4.9 */
    00144     /* action table */
    00145     VALUE action_table;
    00146     VALUE action_check;
    00147     VALUE action_default;
    00148     VALUE action_pointer;
    00149     /* goto table */
    00150     VALUE goto_table;
    00151     VALUE goto_check;
    00152     VALUE goto_default;
    00153     VALUE goto_pointer;
    00154
    00155     long  nt_base;         /* NonTerminal BASE index */
    00156     VALUE reduce_table;    /* reduce data table */
    00157     VALUE token_table;     /* token conversion table */
    00158
    00159     /* parser stacks and parameters */
    00160     VALUE state;
    00161     long curstate;
    00162     VALUE vstack;
    00163     VALUE tstack;
    00164     VALUE t;
    00165     long shift_n;
    00166     long reduce_n;
    00167     long ruleno;
    00168
    00169     long errstatus;         /* nonzero in error recovering mode */
    00170     long nerr;              /* number of error */
    00171
    00172     int use_result_var;
    00173
    00174     VALUE retval;           /* return value of parser routine */
    00175     long fin;               /* parse result status */
    00176 #define CP_FIN_ACCEPT  1
    00177 #define CP_FIN_EOT     2
    00178 #define CP_FIN_CANTPOP 3
    00179
    00180     int debug;              /* user level debug */
    00181     int sys_debug;          /* system level debug */
    00182
    00183     long i;                 /* table index */
    00184 };
    00185
    00186 /* -----------------------------------------------------------------------
    00187                         Parser Main Routines
    00188 ----------------------------------------------------------------------- */
    00189
    00190 static VALUE racc_cparse _((VALUE parser, VALUE arg, VALUE sysdebug));
    00191 static VALUE racc_yyparse _((VALUE parser, VALUE lexer, VALUE lexmid,
    00192                              VALUE arg, VALUE sysdebug));
    00193
    00194 static void call_lexer _((struct cparse_params *v));
    00195 static VALUE lexer_i _((VALUE block_args, VALUE data, VALUE self));
    00196
    00197 static VALUE assert_array _((VALUE a));
    00198 static long assert_integer _((VALUE n));
    00199 static VALUE assert_hash _((VALUE h));
    00200 static VALUE initialize_params _((VALUE vparams, VALUE parser, VALUE arg,
    00201                                  VALUE lexer, VALUE lexmid));
    00202 static void cparse_params_mark _((void *ptr));
    00203
    00204 static void parse_main _((struct cparse_params *v,
    00205                          VALUE tok, VALUE val, int resume));
    00206 static void extract_user_token _((struct cparse_params *v,
    00207                                   VALUE block_args, VALUE *tok, VALUE *val));
    00208 static void shift _((struct cparse_params* v, long act, VALUE tok, VALUE val));
    00209 static int reduce _((struct cparse_params* v, long act));
    00210 static VALUE reduce0 _((VALUE block_args, VALUE data, VALUE self));
    00211
    00212 #ifdef DEBUG
    00213 # define D_puts(msg)        if (v->sys_debug) puts(msg)
    00214 # define D_printf(fmt,arg)  if (v->sys_debug) printf(fmt,arg)
    00215 #else
    00216 # define D_puts(msg)
    00217 # define D_printf(fmt,arg)
    00218 #endif
    00219
    00220 static VALUE
    00221 racc_cparse(VALUE parser, VALUE arg, VALUE sysdebug)
    00222 {
    00223     volatile VALUE vparams;
    00224     struct cparse_params *v;
    00225
    00226     vparams = Data_Make_Struct(CparseParams, struct cparse_params,
    00227                                cparse_params_mark, -1, v);
    00228     D_puts("starting cparse");
    00229     v->sys_debug = RTEST(sysdebug);
    00230     vparams = initialize_params(vparams, parser, arg, Qnil, Qnil);
    00231     v->lex_is_iterator = FALSE;
    00232     parse_main(v, Qnil, Qnil, 0);
    00233
    00234     return v->retval;
    00235 }
    00236
    00237 static VALUE
    00238 racc_yyparse(VALUE parser, VALUE lexer, VALUE lexmid, VALUE arg, VALUE sysdebug)
    00239 {
    00240     volatile VALUE vparams;
    00241     struct cparse_params *v;
    00242
    00243     vparams = Data_Make_Struct(CparseParams, struct cparse_params,
    00244                                cparse_params_mark, -1, v);
    00245     v->sys_debug = RTEST(sysdebug);
    00246     D_puts("start C yyparse");
    00247     vparams = initialize_params(vparams, parser, arg, lexer, lexmid);
    00248     v->lex_is_iterator = TRUE;
    00249     D_puts("params initialized");
    00250     parse_main(v, Qnil, Qnil, 0);
    00251     call_lexer(v);
    00252     if (!v->fin) {
    00253         rb_raise(rb_eArgError, "%s() is finished before EndOfToken",
    00254                  rb_id2name(v->lexmid));
    00255     }
    00256
    00257     return v->retval;
    00258 }
    00259
    00260 #ifdef HAVE_RB_BLOCK_CALL
    00261 static void
    00262 call_lexer(struct cparse_params *v)
    00263 {
    00264     rb_block_call(v->lexer, v->lexmid, 0, NULL, lexer_i, v->value_v);
    00265 }
    00266 #else
    00267 static VALUE
    00268 lexer_iter(VALUE data)
    00269 {
    00270     struct cparse_params *v;
    00271
    00272     Data_Get_Struct(data, struct cparse_params, v);
    00273     rb_funcall(v->lexer, v->lexmid, 0);
    00274     return Qnil;
    00275 }
    00276
    00277 static void
    00278 call_lexer(struct cparse_params *v)
    00279 {
    00280     rb_iterate(lexer_iter, v->value_v, lexer_i, v->value_v);
    00281 }
    00282 #endif
    00283
    00284 static VALUE
    00285 lexer_i(VALUE block_args, VALUE data, VALUE self)
    00286 {
    00287     struct cparse_params *v;
    00288     VALUE tok, val;
    00289
    00290     Data_Get_Struct(data, struct cparse_params, v);
    00291     if (v->fin)
    00292         rb_raise(rb_eArgError, "extra token after EndOfToken");
    00293     extract_user_token(v, block_args, &tok, &val);
    00294     parse_main(v, tok, val, 1);
    00295     if (v->fin && v->fin != CP_FIN_ACCEPT)
    00296        rb_iter_break();
    00297     return Qnil;
    00298 }
    00299
    00300 static VALUE
    00301 assert_array(VALUE a)
    00302 {
    00303     Check_Type(a, T_ARRAY);
    00304     return a;
    00305 }
    00306
    00307 static VALUE
    00308 assert_hash(VALUE h)
    00309 {
    00310     Check_Type(h, T_HASH);
    00311     return h;
    00312 }
    00313
    00314 static long
    00315 assert_integer(VALUE n)
    00316 {
    00317     return NUM2LONG(n);
    00318 }
    00319
    00320 static VALUE
    00321 initialize_params(VALUE vparams, VALUE parser, VALUE arg, VALUE lexer, VALUE lexmid)
    00322 {
    00323     struct cparse_params *v;
    00324
    00325     Data_Get_Struct(vparams, struct cparse_params, v);
    00326     v->value_v = vparams;
    00327     v->parser = parser;
    00328     v->lexer = lexer;
    00329     if (! NIL_P(lexmid))
    00330         v->lexmid = value_to_id(lexmid);
    00331
    00332     v->debug = RTEST(rb_ivar_get(parser, id_yydebug));
    00333
    00334     Check_Type(arg, T_ARRAY);
    00335     if (!(13 <= RARRAY_LEN(arg) && RARRAY_LEN(arg) <= 14))
    00336         rb_raise(RaccBug, "[Racc Bug] wrong arg.size %ld", RARRAY_LEN(arg));
    00337     v->action_table   = assert_array  (RARRAY_PTR(arg)[ 0]);
    00338     v->action_check   = assert_array  (RARRAY_PTR(arg)[ 1]);
    00339     v->action_default = assert_array  (RARRAY_PTR(arg)[ 2]);
    00340     v->action_pointer = assert_array  (RARRAY_PTR(arg)[ 3]);
    00341     v->goto_table     = assert_array  (RARRAY_PTR(arg)[ 4]);
    00342     v->goto_check     = assert_array  (RARRAY_PTR(arg)[ 5]);
    00343     v->goto_default   = assert_array  (RARRAY_PTR(arg)[ 6]);
    00344     v->goto_pointer   = assert_array  (RARRAY_PTR(arg)[ 7]);
    00345     v->nt_base        = assert_integer(RARRAY_PTR(arg)[ 8]);
    00346     v->reduce_table   = assert_array  (RARRAY_PTR(arg)[ 9]);
    00347     v->token_table    = assert_hash   (RARRAY_PTR(arg)[10]);
    00348     v->shift_n        = assert_integer(RARRAY_PTR(arg)[11]);
    00349     v->reduce_n       = assert_integer(RARRAY_PTR(arg)[12]);
    00350     if (RARRAY_LEN(arg) > 13) {
    00351         v->use_result_var = RTEST(RARRAY_PTR(arg)[13]);
    00352     }
    00353     else {
    00354         v->use_result_var = TRUE;
    00355     }
    00356
    00357     v->tstack = v->debug ? NEW_STACK() : Qnil;
    00358     v->vstack = NEW_STACK();
    00359     v->state = NEW_STACK();
    00360     v->curstate = 0;
    00361     PUSH(v->state, INT2FIX(0));
    00362     v->t = INT2FIX(FINAL_TOKEN + 1);   /* must not init to FINAL_TOKEN */
    00363     v->nerr = 0;
    00364     v->errstatus = 0;
    00365     rb_ivar_set(parser, id_errstatus, LONG2NUM(v->errstatus));
    00366
    00367     v->retval = Qnil;
    00368     v->fin = 0;
    00369
    00370     v->lex_is_iterator = FALSE;
    00371
    00372     rb_iv_set(parser, "@vstack", v->vstack);
    00373     if (v->debug) {
    00374         rb_iv_set(parser, "@tstack", v->tstack);
    00375     }
    00376     else {
    00377         rb_iv_set(parser, "@tstack", Qnil);
    00378     }
    00379
    00380     return vparams;
    00381 }
    00382
    00383 static void
    00384 cparse_params_mark(void *ptr)
    00385 {
    00386     struct cparse_params *v = (struct cparse_params*)ptr;
    00387
    00388     rb_gc_mark(v->value_v);
    00389     rb_gc_mark(v->parser);
    00390     rb_gc_mark(v->lexer);
    00391     rb_gc_mark(v->action_table);
    00392     rb_gc_mark(v->action_check);
    00393     rb_gc_mark(v->action_default);
    00394     rb_gc_mark(v->action_pointer);
    00395     rb_gc_mark(v->goto_table);
    00396     rb_gc_mark(v->goto_check);
    00397     rb_gc_mark(v->goto_default);
    00398     rb_gc_mark(v->goto_pointer);
    00399     rb_gc_mark(v->reduce_table);
    00400     rb_gc_mark(v->token_table);
    00401     rb_gc_mark(v->state);
    00402     rb_gc_mark(v->vstack);
    00403     rb_gc_mark(v->tstack);
    00404     rb_gc_mark(v->t);
    00405     rb_gc_mark(v->retval);
    00406 }
    00407
    00408 static void
    00409 extract_user_token(struct cparse_params *v, VALUE block_args,
    00410                    VALUE *tok, VALUE *val)
    00411 {
    00412     if (NIL_P(block_args)) {
    00413         /* EOF */
    00414         *tok = Qfalse;
    00415         *val = rb_str_new("$", 1);
    00416         return;
    00417     }
    00418
    00419     if (TYPE(block_args) != T_ARRAY) {
    00420         rb_raise(rb_eTypeError,
    00421                  "%s() %s %s (must be Array[2])",
    00422                  v->lex_is_iterator ? rb_id2name(v->lexmid) : "next_token",
    00423                  v->lex_is_iterator ? "yielded" : "returned",
    00424                  rb_class2name(CLASS_OF(block_args)));
    00425     }
    00426     if (RARRAY_LEN(block_args) != 2) {
    00427         rb_raise(rb_eArgError,
    00428                  "%s() %s wrong size of array (%ld for 2)",
    00429                  v->lex_is_iterator ? rb_id2name(v->lexmid) : "next_token",
    00430                  v->lex_is_iterator ? "yielded" : "returned",
    00431                  RARRAY_LEN(block_args));
    00432     }
    00433     *tok = AREF(block_args, 0);
    00434     *val = AREF(block_args, 1);
    00435 }
    00436
    00437 #define SHIFT(v,act,tok,val) shift(v,act,tok,val)
    00438 #define REDUCE(v,act) do {\
    00439     switch (reduce(v,act)) {  \
    00440       case 0: /* normal */    \
    00441         break;                \
    00442       case 1: /* yyerror */   \
    00443         goto user_yyerror;    \
    00444       case 2: /* yyaccept */  \
    00445         D_puts("u accept");   \
    00446         goto accept;          \
    00447       default:                \
    00448         break;                \
    00449     }                         \
    00450 } while (0)
    00451
    00452 static void
    00453 parse_main(struct cparse_params *v, VALUE tok, VALUE val, int resume)
    00454 {
    00455     long i;              /* table index */
    00456     long act;            /* action type */
    00457     VALUE act_value;     /* action type, VALUE version */
    00458     int read_next = 1;   /* true if we need to read next token */
    00459     VALUE tmp;
    00460
    00461     if (resume)
    00462         goto resume;
    00463
    00464     while (1) {
    00465         D_puts("");
    00466         D_puts("---- enter new loop ----");
    00467         D_puts("");
    00468
    00469         D_printf("(act) k1=%ld\n", v->curstate);
    00470         tmp = AREF(v->action_pointer, v->curstate);
    00471         if (NIL_P(tmp)) goto notfound;
    00472         D_puts("(act) pointer[k1] ok");
    00473         i = NUM2LONG(tmp);
    00474
    00475         D_printf("read_next=%d\n", read_next);
    00476         if (read_next && (v->t != vFINAL_TOKEN)) {
    00477             if (v->lex_is_iterator) {
    00478                 D_puts("resuming...");
    00479                 if (v->fin) rb_raise(rb_eArgError, "token given after EOF");
    00480                 v->i = i;  /* save i */
    00481                 return;
    00482               resume:
    00483                 D_puts("resumed");
    00484                 i = v->i;  /* load i */
    00485             }
    00486             else {
    00487                 D_puts("next_token");
    00488                 tmp = rb_funcall(v->parser, id_nexttoken, 0);
    00489                 extract_user_token(v, tmp, &tok, &val);
    00490             }
    00491             /* convert token */
    00492             v->t = rb_hash_aref(v->token_table, tok);
    00493             if (NIL_P(v->t)) {
    00494                 v->t = vERROR_TOKEN;
    00495             }
    00496             D_printf("(act) t(k2)=%ld\n", NUM2LONG(v->t));
    00497             if (v->debug) {
    00498                 rb_funcall(v->parser, id_d_read_token,
    00499                            3, v->t, tok, val);
    00500             }
    00501         }
    00502         read_next = 0;
    00503
    00504         i += NUM2LONG(v->t);
    00505         D_printf("(act) i=%ld\n", i);
    00506         if (i < 0) goto notfound;
    00507
    00508         act_value = AREF(v->action_table, i);
    00509         if (NIL_P(act_value)) goto notfound;
    00510         act = NUM2LONG(act_value);
    00511         D_printf("(act) table[i]=%ld\n", act);
    00512
    00513         tmp = AREF(v->action_check, i);
    00514         if (NIL_P(tmp)) goto notfound;
    00515         if (NUM2LONG(tmp) != v->curstate) goto notfound;
    00516         D_printf("(act) check[i]=%ld\n", NUM2LONG(tmp));
    00517
    00518         D_puts("(act) found");
    00519       act_fixed:
    00520         D_printf("act=%ld\n", act);
    00521         goto handle_act;
    00522
    00523       notfound:
    00524         D_puts("(act) not found: use default");
    00525         act_value = AREF(v->action_default, v->curstate);
    00526         act = NUM2LONG(act_value);
    00527         goto act_fixed;
    00528
    00529
    00530       handle_act:
    00531         if (act > 0 && act < v->shift_n) {
    00532             D_puts("shift");
    00533             if (v->errstatus > 0) {
    00534                 v->errstatus--;
    00535                 rb_ivar_set(v->parser, id_errstatus, LONG2NUM(v->errstatus));
    00536             }
    00537             SHIFT(v, act, v->t, val);
    00538             read_next = 1;
    00539         }
    00540         else if (act < 0 && act > -(v->reduce_n)) {
    00541             D_puts("reduce");
    00542             REDUCE(v, act);
    00543         }
    00544         else if (act == -(v->reduce_n)) {
    00545             goto error;
    00546           error_recovered:
    00547             ;   /* goto label requires stmt */
    00548         }
    00549         else if (act == v->shift_n) {
    00550             D_puts("accept");
    00551             goto accept;
    00552         }
    00553         else {
    00554             rb_raise(RaccBug, "[Racc Bug] unknown act value %ld", act);
    00555         }
    00556
    00557         if (v->debug) {
    00558             rb_funcall(v->parser, id_d_next_state,
    00559                        2, LONG2NUM(v->curstate), v->state);
    00560         }
    00561     }
    00562     /* not reach */
    00563
    00564
    00565   accept:
    00566     if (v->debug) rb_funcall(v->parser, id_d_accept, 0);
    00567     v->retval = RARRAY_PTR(v->vstack)[0];
    00568     v->fin = CP_FIN_ACCEPT;
    00569     return;
    00570
    00571
    00572   error:
    00573     D_printf("error detected, status=%ld\n", v->errstatus);
    00574     if (v->errstatus == 0) {
    00575         v->nerr++;
    00576         rb_funcall(v->parser, id_onerror,
    00577                    3, v->t, val, v->vstack);
    00578     }
    00579   user_yyerror:
    00580     if (v->errstatus == 3) {
    00581         if (v->t == vFINAL_TOKEN) {
    00582             v->retval = Qfalse;
    00583             v->fin = CP_FIN_EOT;
    00584             return;
    00585         }
    00586         read_next = 1;
    00587     }
    00588     v->errstatus = 3;
    00589     rb_ivar_set(v->parser, id_errstatus, LONG2NUM(v->errstatus));
    00590
    00591     /* check if we can shift/reduce error token */
    00592     D_printf("(err) k1=%ld\n", v->curstate);
    00593     D_printf("(err) k2=%d (error)\n", ERROR_TOKEN);
    00594     while (1) {
    00595         tmp = AREF(v->action_pointer, v->curstate);
    00596         if (NIL_P(tmp)) goto error_pop;
    00597         D_puts("(err) pointer[k1] ok");
    00598
    00599         i = NUM2LONG(tmp) + ERROR_TOKEN;
    00600         D_printf("(err) i=%ld\n", i);
    00601         if (i < 0) goto error_pop;
    00602
    00603         act_value = AREF(v->action_table, i);
    00604         if (NIL_P(act_value)) {
    00605             D_puts("(err) table[i] == nil");
    00606             goto error_pop;
    00607         }
    00608         act = NUM2LONG(act_value);
    00609         D_printf("(err) table[i]=%ld\n", act);
    00610
    00611         tmp = AREF(v->action_check, i);
    00612         if (NIL_P(tmp)) {
    00613             D_puts("(err) check[i] == nil");
    00614             goto error_pop;
    00615         }
    00616         if (NUM2LONG(tmp) != v->curstate) {
    00617             D_puts("(err) check[i] != k1");
    00618             goto error_pop;
    00619         }
    00620
    00621         D_puts("(err) found: can handle error token");
    00622         break;
    00623
    00624       error_pop:
    00625         D_puts("(err) act not found: can't handle error token; pop");
    00626
    00627         if (RARRAY_LEN(v->state) <= 1) {
    00628             v->retval = Qnil;
    00629             v->fin = CP_FIN_CANTPOP;
    00630             return;
    00631         }
    00632         POP(v->state);
    00633         POP(v->vstack);
    00634         v->curstate = num_to_long(LAST_I(v->state));
    00635         if (v->debug) {
    00636             POP(v->tstack);
    00637             rb_funcall(v->parser, id_d_e_pop,
    00638                        3, v->state, v->tstack, v->vstack);
    00639         }
    00640     }
    00641
    00642     /* shift/reduce error token */
    00643     if (act > 0 && act < v->shift_n) {
    00644         D_puts("e shift");
    00645         SHIFT(v, act, ERROR_TOKEN, val);
    00646     }
    00647     else if (act < 0 && act > -(v->reduce_n)) {
    00648         D_puts("e reduce");
    00649         REDUCE(v, act);
    00650     }
    00651     else if (act == v->shift_n) {
    00652         D_puts("e accept");
    00653         goto accept;
    00654     }
    00655     else {
    00656         rb_raise(RaccBug, "[Racc Bug] unknown act value %ld", act);
    00657     }
    00658     goto error_recovered;
    00659 }
    00660
    00661 static void
    00662 shift(struct cparse_params *v, long act, VALUE tok, VALUE val)
    00663 {
    00664     PUSH(v->vstack, val);
    00665     if (v->debug) {
    00666         PUSH(v->tstack, tok);
    00667         rb_funcall(v->parser, id_d_shift,
    00668                    3, tok, v->tstack, v->vstack);
    00669     }
    00670     v->curstate = act;
    00671     PUSH(v->state, LONG2NUM(v->curstate));
    00672 }
    00673
    00674 static int
    00675 reduce(struct cparse_params *v, long act)
    00676 {
    00677     VALUE code;
    00678     v->ruleno = -act * 3;
    00679     code = rb_catch("racc_jump", reduce0, v->value_v);
    00680     v->errstatus = num_to_long(rb_ivar_get(v->parser, id_errstatus));
    00681     return NUM2INT(code);
    00682 }
    00683
    00684 static VALUE
    00685 reduce0(VALUE val, VALUE data, VALUE self)
    00686 {
    00687     struct cparse_params *v;
    00688     VALUE reduce_to, reduce_len, method_id;
    00689     long len;
    00690     ID mid;
    00691     VALUE tmp, tmp_t = Qundef, tmp_v = Qundef;
    00692     long i, k1, k2;
    00693     VALUE goto_state;
    00694
    00695     Data_Get_Struct(data, struct cparse_params, v);
    00696     reduce_len = RARRAY_PTR(v->reduce_table)[v->ruleno];
    00697     reduce_to  = RARRAY_PTR(v->reduce_table)[v->ruleno+1];
    00698     method_id  = RARRAY_PTR(v->reduce_table)[v->ruleno+2];
    00699     len = NUM2LONG(reduce_len);
    00700     mid = value_to_id(method_id);
    00701
    00702     /* call action */
    00703     if (len == 0) {
    00704         tmp = Qnil;
    00705         if (mid != id_noreduce)
    00706             tmp_v = rb_ary_new();
    00707         if (v->debug)
    00708             tmp_t = rb_ary_new();
    00709     }
    00710     else {
    00711         if (mid != id_noreduce) {
    00712             tmp_v = GET_TAIL(v->vstack, len);
    00713             tmp = RARRAY_PTR(tmp_v)[0];
    00714         }
    00715         else {
    00716             tmp = RARRAY_PTR(v->vstack)[ RARRAY_LEN(v->vstack) - len ];
    00717         }
    00718         CUT_TAIL(v->vstack, len);
    00719         if (v->debug) {
    00720             tmp_t = GET_TAIL(v->tstack, len);
    00721             CUT_TAIL(v->tstack, len);
    00722         }
    00723         CUT_TAIL(v->state, len);
    00724     }
    00725     if (mid != id_noreduce) {
    00726         if (v->use_result_var) {
    00727             tmp = rb_funcall(v->parser, mid,
    00728                              3, tmp_v, v->vstack, tmp);
    00729         }
    00730         else {
    00731             tmp = rb_funcall(v->parser, mid,
    00732                              2, tmp_v, v->vstack);
    00733         }
    00734     }
    00735
    00736     /* then push result */
    00737     PUSH(v->vstack, tmp);
    00738     if (v->debug) {
    00739         PUSH(v->tstack, reduce_to);
    00740         rb_funcall(v->parser, id_d_reduce,
    00741                    4, tmp_t, reduce_to, v->tstack, v->vstack);
    00742     }
    00743
    00744     /* calculate transition state */
    00745     if (RARRAY_LEN(v->state) == 0)
    00746         rb_raise(RaccBug, "state stack unexpectedly empty");
    00747     k2 = num_to_long(LAST_I(v->state));
    00748     k1 = num_to_long(reduce_to) - v->nt_base;
    00749     D_printf("(goto) k1=%ld\n", k1);
    00750     D_printf("(goto) k2=%ld\n", k2);
    00751
    00752     tmp = AREF(v->goto_pointer, k1);
    00753     if (NIL_P(tmp)) goto notfound;
    00754
    00755     i = NUM2LONG(tmp) + k2;
    00756     D_printf("(goto) i=%ld\n", i);
    00757     if (i < 0) goto notfound;
    00758
    00759     goto_state = AREF(v->goto_table, i);
    00760     if (NIL_P(goto_state)) {
    00761         D_puts("(goto) table[i] == nil");
    00762         goto notfound;
    00763     }
    00764     D_printf("(goto) table[i]=%ld (goto_state)\n", NUM2LONG(goto_state));
    00765
    00766     tmp = AREF(v->goto_check, i);
    00767     if (NIL_P(tmp)) {
    00768         D_puts("(goto) check[i] == nil");
    00769         goto notfound;
    00770     }
    00771     if (tmp != LONG2NUM(k1)) {
    00772         D_puts("(goto) check[i] != table[i]");
    00773         goto notfound;
    00774     }
    00775     D_printf("(goto) check[i]=%ld\n", NUM2LONG(tmp));
    00776
    00777     D_puts("(goto) found");
    00778   transit:
    00779     PUSH(v->state, goto_state);
    00780     v->curstate = NUM2LONG(goto_state);
    00781     return INT2FIX(0);
    00782
    00783   notfound:
    00784     D_puts("(goto) not found: use default");
    00785     /* overwrite `goto-state' by default value */
    00786     goto_state = AREF(v->goto_default, k1);
    00787     goto transit;
    00788 }
    00789
    00790 /* -----------------------------------------------------------------------
    00791                           Ruby Interface
    00792 ----------------------------------------------------------------------- */
    00793
    00794 void
    00795 Init_cparse(void)
    00796 {
    00797     VALUE Racc, Parser;
    00798     ID id_racc = rb_intern("Racc");
    00799
    00800     if (rb_const_defined(rb_cObject, id_racc)) {
    00801         Racc = rb_const_get(rb_cObject, id_racc);
    00802         Parser = rb_const_get_at(Racc, rb_intern("Parser"));
    00803     }
    00804     else {
    00805         Racc = rb_define_module("Racc");
    00806         Parser = rb_define_class_under(Racc, "Parser", rb_cObject);
    00807     }
    00808     rb_define_private_method(Parser, "_racc_do_parse_c", racc_cparse, 2);
    00809     rb_define_private_method(Parser, "_racc_yyparse_c", racc_yyparse, 4);
    00810     rb_define_const(Parser, "Racc_Runtime_Core_Version_C",
    00811                     rb_str_new2(RACC_VERSION));
    00812     rb_define_const(Parser, "Racc_Runtime_Core_Id_C",
    00813         rb_str_new2("$originalId: cparse.c,v 1.8 2006/07/06 11:39:46 aamine Exp $"));
    00814
    00815     CparseParams = rb_define_class_under(Racc, "CparseParams", rb_cObject);
    00816
    00817     RaccBug = rb_eRuntimeError;
    00818
    00819     id_yydebug      = rb_intern("@yydebug");
    00820     id_nexttoken    = rb_intern("next_token");
    00821     id_onerror      = rb_intern("on_error");
    00822     id_noreduce     = rb_intern("_reduce_none");
    00823     id_errstatus    = rb_intern("@racc_error_status");
    00824
    00825     id_d_shift       = rb_intern("racc_shift");
    00826     id_d_reduce      = rb_intern("racc_reduce");
    00827     id_d_accept      = rb_intern("racc_accept");
    00828     id_d_read_token  = rb_intern("racc_read_token");
    00829     id_d_next_state  = rb_intern("racc_next_state");
    00830     id_d_e_pop       = rb_intern("racc_e_pop");
    00831 }
    00832