diff options
| -rw-r--r-- | ChangeLog | 10 | ||||
| -rw-r--r-- | ext/Setup | 1 | ||||
| -rw-r--r-- | ext/Setup.dj | 1 | ||||
| -rw-r--r-- | ext/Setup.emx | 1 | ||||
| -rw-r--r-- | ext/Setup.nt | 1 | ||||
| -rw-r--r-- | ext/Setup.x68 | 1 | ||||
| -rw-r--r-- | ext/racc/cparse/MANIFEST | 3 | ||||
| -rw-r--r-- | ext/racc/cparse/cparse.c | 764 | ||||
| -rw-r--r-- | ext/racc/cparse/depend | 1 | ||||
| -rw-r--r-- | ext/racc/cparse/extconf.rb | 4 | ||||
| -rw-r--r-- | lib/README | 1 | ||||
| -rw-r--r-- | lib/racc/parser.rb | 480 |
12 files changed, 1268 insertions, 0 deletions
@@ -1,3 +1,13 @@ +Fri Mar 22 16:27:24 2002 Minero Aoki <aamine@loveruby.net> + + * lib/racc/parser.rb: new file. + + * ext/racc/MANIFEST, cparse.c, depend, extconf.rb: new files. + + * lib/README: add racc/parser.rb. + + * ext/Setup*: add racc/cparse. + Fri Mar 22 15:44:38 2002 Minero Aoki <aamine@loveruby.net> * ext/strscan/MANIFEST, strscan.c, depend, extconf.rb: new files. @@ -15,6 +15,7 @@ #iconv #nkf #pty +#racc/cparse #readline #sdbm #socket diff --git a/ext/Setup.dj b/ext/Setup.dj index 15f3ec39ec..cf537499e4 100644 --- a/ext/Setup.dj +++ b/ext/Setup.dj @@ -15,6 +15,7 @@ gdbm #iconv nkf #pty +racc/cparse readline sdbm #socket diff --git a/ext/Setup.emx b/ext/Setup.emx index 6e0e91b394..b4534ce8bb 100644 --- a/ext/Setup.emx +++ b/ext/Setup.emx @@ -15,6 +15,7 @@ fcntl #iconv nkf #pty +racc/cparse #readline #sdbm socket diff --git a/ext/Setup.nt b/ext/Setup.nt index 8b5f9d2ee1..c61111a1e7 100644 --- a/ext/Setup.nt +++ b/ext/Setup.nt @@ -15,6 +15,7 @@ fcntl #iconv nkf #pty +racc/cparse #readline sdbm socket diff --git a/ext/Setup.x68 b/ext/Setup.x68 index 6fe330ad60..dac83a82f3 100644 --- a/ext/Setup.x68 +++ b/ext/Setup.x68 @@ -15,6 +15,7 @@ fcntl #iconv nkf #pty +racc/cparse #readline #sdbm #socket diff --git a/ext/racc/cparse/MANIFEST b/ext/racc/cparse/MANIFEST new file mode 100644 index 0000000000..daf1f846b9 --- /dev/null +++ b/ext/racc/cparse/MANIFEST @@ -0,0 +1,3 @@ +MANIFEST +cparse.c +extconf.rb diff --git a/ext/racc/cparse/cparse.c b/ext/racc/cparse/cparse.c new file mode 100644 index 0000000000..7607364890 --- /dev/null +++ b/ext/racc/cparse/cparse.c @@ -0,0 +1,764 @@ +/* vi:set sw=4: + + cparse.c + + Copyright (c) 1999-2002 Minero Aoki <aamine@loveruby.net> + + This library is free software. + You can distribute/modify this program under the same terms of ruby. + + $Id$ + +*/ + +#include <stdio.h> +#include "ruby.h" + +#define RACC_VERSION "1.4.2" + +#define DFLT_TOK -1 +#define ERR_TOK 1 +#define FINAL_TOK 0 + +#define vDFLT_TOK INT2FIX(DFLT_TOK) +#define vERR_TOK INT2FIX(ERR_TOK) +#define vFINAL_TOK INT2FIX(FINAL_TOK) + +static VALUE RaccBug; +static VALUE CparseParams; + +static ID id_yydebug; +static ID id_nexttoken; +static ID id_onerror; +static ID id_noreduce; +static ID id_catch; +static VALUE sym_raccjump; +static ID id_errstatus; + +static ID id_d_shift; +static ID id_d_reduce; +static ID id_d_accept; +static ID id_d_read_token; +static ID id_d_next_state; +static ID id_d_e_pop; + + +#ifdef ID2SYM +# define id_to_value(i) ID2SYM(i) +#else +# define id_to_value(i) ULONG2NUM(i) +#endif + +static ID +value_to_id(v) + VALUE v; +{ +#ifndef SYMBOL_P +# define SYMBOL_P(v) FIXNUM_P(v) +#endif + if (! SYMBOL_P(v)) { + rb_raise(rb_eTypeError, "not symbol"); + } +#ifdef SYM2ID + return SYM2ID(v); +#else + return (ID)NUM2ULONG(v); +#endif +} + +#ifndef LONG2NUM +# define LONG2NUM(i) INT2NUM(i) +#endif + +static VALUE +slice_tail(stack, len) + VALUE stack; + long len; +{ + if (len < 0) return Qnil; /* system error */ + if (len > RARRAY(stack)->len) len = RARRAY(stack)->len; + return rb_ary_new4(len, RARRAY(stack)->ptr + RARRAY(stack)->len - len); +} + +static void +cut_off_tail(stack, len) + VALUE stack; + long len; +{ + while (len > 0) { + rb_ary_pop(stack); + len--; + } +} + +#define STACK_INIT_LEN 64 +#define INIT_STACK(s) \ + s = rb_ary_new2(STACK_INIT_LEN) + +#define AREF(s, idx) \ + ((0 <= idx && idx < RARRAY(s)->len) ? RARRAY(s)->ptr[idx] : Qnil) + +#define PUSH(s, i) \ + rb_ary_store(s, RARRAY(s)->len, i) + +#define POP(s) \ + rb_ary_pop(s) + +#define LAST_I(s) \ + ((RARRAY(s)->len > 0) ? RARRAY(s)->ptr[RARRAY(s)->len - 1] : Qnil) + +#define GET_TAIL(s, len) \ + slice_tail(s, len) + +#define CUT_TAIL(s, len) \ + cut_off_tail(s, len) + + +struct cparse_params { + VALUE vv; + + VALUE parser; + VALUE recv; + ID mid; + + VALUE action_table; + VALUE action_check; + VALUE action_default; + VALUE action_pointer; + VALUE goto_table; + VALUE goto_check; + VALUE goto_default; + VALUE goto_pointer; + long nt_base; + VALUE reduce_table; + VALUE token_table; + + VALUE state; + long curstate; + VALUE vstack; + VALUE tstack; + VALUE t; + long shift_n; + long reduce_n; + long ruleno; + + long errstatus; + long nerr; + + VALUE use_result_var; + VALUE iterator_p; + + VALUE retval; + long fin; +#define CP_FIN_ACCEPT 1 +#define CP_FIN_EOT 2 +#define CP_FIN_CANTPOP 3 + + VALUE debug; + VALUE in_debug; + + long i; +}; + + +static void initvars _((VALUE, struct cparse_params*, VALUE, VALUE, VALUE)); +static void wrap_yyparse _((struct cparse_params*)); +static void parser_core _((struct cparse_params*, VALUE, VALUE, int)); +static void extract_utok _((struct cparse_params*, VALUE, VALUE*, VALUE*)); +static VALUE catch_iter _((VALUE)); +static VALUE do_reduce _((VALUE, VALUE, VALUE)); + + +#define REDUCE(v, act) \ + v->ruleno = -act * 3; \ + tmp = rb_iterate(catch_iter, v->parser, \ + do_reduce, v->vv); \ + code = NUM2LONG(tmp); \ + tmp = rb_ivar_get(v->parser, id_errstatus); \ + v->errstatus = NUM2LONG(tmp); \ + switch (code) { \ + case 0: /* normal */ \ + break; \ + case 1: /* yyerror */ \ + goto user_yyerror; \ + case 2: /* yyaccept */ \ + goto accept; \ + default: \ + break; \ + } + +#define SHIFT(v, act, tok, val) \ + PUSH(v->vstack, val); \ + if (v->debug) { \ + PUSH(v->tstack, tok); \ + rb_funcall(v->parser, id_d_shift, \ + 3, tok, v->tstack, v->vstack); \ + } \ + v->curstate = act; \ + PUSH(v->state, LONG2NUM(v->curstate)); + +#define ACCEPT(v) \ + if (v->debug) rb_funcall(v->parser, id_d_accept, 0); \ + v->retval = RARRAY(v->vstack)->ptr[0]; \ + v->fin = CP_FIN_ACCEPT; \ + return; + + +#ifdef DEBUG +# define D(code) if (v->in_debug) code +#else +# define D(code) +#endif + + +static VALUE +racc_cparse(parser, arg, indebug) + VALUE parser, arg, indebug; +{ + struct cparse_params vv; + struct cparse_params *v; + + v = &vv; + v->in_debug = RTEST(indebug); + D(puts("start C doparse")); + initvars(parser, v, arg, Qnil, Qnil); + v->iterator_p = Qfalse; + D(puts("params initialized")); + parser_core(v, Qnil, Qnil, 0); + + return v->retval; +} + +static VALUE +racc_yyparse(parser, recv, mid, arg, indebug) + VALUE parser, recv, mid, arg, indebug; +{ + struct cparse_params vv; + struct cparse_params *v; + + v = &vv; + v->in_debug = RTEST(indebug); + D(puts("start C yyparse")); + initvars(parser, v, arg, recv, mid); + v->iterator_p = Qtrue; + D(puts("params initialized")); + parser_core(v, Qnil, Qnil, 0); + wrap_yyparse(v); + if (! v->fin) { + rb_raise(rb_eArgError, "%s() is finished before EndOfToken", + rb_id2name(v->mid)); + } + + return v->retval; +} + +static VALUE +call_scaniter(data) + VALUE data; +{ + struct cparse_params *v; + + Data_Get_Struct(data, struct cparse_params, v); + rb_funcall(v->recv, v->mid, 0); + + return Qnil; +} + +static VALUE +catch_scaniter(arr, data, self) + VALUE arr, data, self; +{ + struct cparse_params *v; + VALUE tok, val; + + Data_Get_Struct(data, struct cparse_params, v); + if (v->fin) + rb_raise(rb_eArgError, "extra token after EndOfToken"); + extract_utok(v, arr, &tok, &val); + parser_core(v, tok, val, 1); + if (v->fin && v->fin != CP_FIN_ACCEPT) + rb_iter_break(); + + return Qnil; +} + +static void +wrap_yyparse(v) + struct cparse_params *v; +{ + rb_iterate(call_scaniter, v->vv, + catch_scaniter, v->vv); +} + +static void +initvars(parser, v, arg, recv, mid) + VALUE parser, arg, recv, mid; + struct cparse_params *v; +{ + VALUE act_tbl, act_chk, act_def, act_ptr, + goto_tbl, goto_chk, goto_def, goto_ptr, + ntbas, red_tbl, tok_tbl, shi_n, red_n; + VALUE debugp; + + + v->vv = Data_Wrap_Struct(CparseParams, 0, 0, v); + + v->parser = parser; + v->recv = recv; + if (! NIL_P(mid)) + v->mid = value_to_id(mid); + + debugp = rb_ivar_get(parser, id_yydebug); + v->debug = RTEST(debugp); + + Check_Type(arg, T_ARRAY); + if (!(RARRAY(arg)->len == 13 || + RARRAY(arg)->len == 14)) + rb_raise(RaccBug, "[Racc Bug] wrong arg.size %ld", RARRAY(arg)->len); + act_tbl = RARRAY(arg)->ptr[0]; + act_chk = RARRAY(arg)->ptr[1]; + act_def = RARRAY(arg)->ptr[2]; + act_ptr = RARRAY(arg)->ptr[3]; + goto_tbl = RARRAY(arg)->ptr[4]; + goto_chk = RARRAY(arg)->ptr[5]; + goto_def = RARRAY(arg)->ptr[6]; + goto_ptr = RARRAY(arg)->ptr[7]; + ntbas = RARRAY(arg)->ptr[8]; + red_tbl = RARRAY(arg)->ptr[9]; + tok_tbl = RARRAY(arg)->ptr[10]; + shi_n = RARRAY(arg)->ptr[11]; + red_n = RARRAY(arg)->ptr[12]; + if (RARRAY(arg)->len > 13) { + VALUE useres; + useres = RARRAY(arg)->ptr[13]; + v->use_result_var = RTEST(useres); + } + else { + v->use_result_var = Qtrue; + } + Check_Type(act_tbl, T_ARRAY); + Check_Type(act_chk, T_ARRAY); + Check_Type(act_def, T_ARRAY); + Check_Type(act_ptr, T_ARRAY); + Check_Type(goto_tbl, T_ARRAY); + Check_Type(goto_chk, T_ARRAY); + Check_Type(goto_def, T_ARRAY); + Check_Type(goto_ptr, T_ARRAY); + Check_Type(ntbas, T_FIXNUM); + Check_Type(red_tbl, T_ARRAY); + Check_Type(tok_tbl, T_HASH); + Check_Type(shi_n, T_FIXNUM); + Check_Type(red_n, T_FIXNUM); + v->action_table = act_tbl; + v->action_check = act_chk; + v->action_default = act_def; + v->action_pointer = act_ptr; + v->goto_table = goto_tbl; + v->goto_check = goto_chk; + v->goto_default = goto_def; + v->goto_pointer = goto_ptr; + v->nt_base = NUM2LONG(ntbas); + v->reduce_table = red_tbl; + v->token_table = tok_tbl; + v->shift_n = NUM2LONG(shi_n); + v->reduce_n = NUM2LONG(red_n); + + if (v->debug) INIT_STACK(v->tstack); + INIT_STACK(v->vstack); + INIT_STACK(v->state); + v->curstate = 0; + PUSH(v->state, INT2FIX(0)); + v->t = LONG2NUM(FINAL_TOK + 1); /* must not init to FINAL_TOK */ + v->nerr = 0; + v->errstatus = 0; + rb_ivar_set(parser, id_errstatus, LONG2NUM(v->errstatus)); + + v->retval = Qnil; + v->fin = 0; + + v->iterator_p = Qfalse; +} + +static void +extract_utok(v, arr, t_var, v_var) + struct cparse_params *v; + VALUE arr; + VALUE *t_var, *v_var; +{ + if (NIL_P(arr)) { + /* EOF */ + *t_var = Qfalse; + *v_var = rb_str_new("$", 1); + return; + } + if (TYPE(arr) != T_ARRAY) { + rb_raise(rb_eTypeError, + "%s() %s %s (must be Array[2])", + v->iterator_p ? rb_id2name(v->mid) : "next_token", + v->iterator_p ? "yielded" : "returned", + rb_class2name(CLASS_OF(arr))); + } + if (RARRAY(arr)->len != 2) + rb_raise(rb_eArgError, + "%s() %s wrong size of array (%ld for 2)", + v->iterator_p ? rb_id2name(v->mid) : "next_token", + v->iterator_p ? "yielded" : "returned", + RARRAY(arr)->len); + *t_var = AREF(arr, 0); + *v_var = AREF(arr, 1); +} + +static void +parser_core(v, tok, val, resume) + struct cparse_params *v; + VALUE tok, val; + int resume; +{ + long act; + int read_next = 1; + + if (resume) + goto resume; + + while (1) { + long i; + VALUE tmp; + VALUE vact = 1; + + D(puts("enter new loop")); + + /* decide action */ + + D(printf("(act) k1=%ld\n", v->curstate)); + tmp = AREF(v->action_pointer, v->curstate); + if (! NIL_P(tmp)) { + i = NUM2LONG(tmp); + + D(puts("(act) pointer[k1] true")); + D(printf("read_next=%d\n", read_next)); + if (read_next) { + if (v->t != vFINAL_TOK) { + if (v->iterator_p) { + /***** BUG? ******/ + D(puts("resuming...")); + if (v->fin) { + rb_raise(rb_eArgError, + "token given after EndOfToken seen"); + } + v->i = i; + return; + } + tmp = rb_funcall(v->parser, id_nexttoken, 0); + extract_utok(v, tmp, &tok, &val); + resume: + if (v->iterator_p) { + D(puts("resume")); + i = v->i; + } + tmp = rb_hash_aref(v->token_table, tok); + v->t = NIL_P(tmp) ? vERR_TOK : tmp; + D(printf("(act) t(k2)=%ld\n", NUM2LONG(v->t))); + if (v->debug) { + rb_funcall(v->parser, id_d_read_token, + 3, v->t, tok, val); + } + } + read_next = 0; + } + + i += NUM2LONG(v->t); + D(printf("(act) i=%ld\n", i)); + if (i >= 0) { + vact = AREF(v->action_table, i); + D(printf("(act) table[i]=%ld\n", NUM2LONG(vact))); + if (! NIL_P(vact)) { + tmp = AREF(v->action_check, i); + D(printf("(act) check[i]=%ld\n", NUM2LONG(tmp))); + if (! NIL_P(tmp) && NUM2LONG(tmp) == v->curstate) { + D(puts("(act) found")); + goto act_found; + } + } + } + } + D(puts("(act) not found: use default")); + vact = AREF(v->action_default, v->curstate); + + act_found: + act = NUM2LONG(vact); + D(printf("act=%ld\n", act)); + + + if (act > 0 && act < v->shift_n) { + D(puts("shift")); + + if (v->errstatus > 0) { + v->errstatus--; + rb_ivar_set(v->parser, id_errstatus, LONG2NUM(v->errstatus)); + } + SHIFT(v, act, v->t, val); + read_next = 1; + } + else if (act < 0 && act > -(v->reduce_n)) { + int code; + D(puts("reduce")); + + REDUCE(v, act); + } + else if (act == -(v->reduce_n)) { + D(printf("error detected, status=%ld\n", v->errstatus)); + + if (v->errstatus == 0) { + v->nerr++; + rb_funcall(v->parser, id_onerror, + 3, v->t, val, v->vstack); + } + + user_yyerror: + + if (v->errstatus == 3) { + if (v->t == vFINAL_TOK) { + v->retval = Qfalse; + v->fin = CP_FIN_EOT; + return; + } + read_next = 1; + } + v->errstatus = 3; + rb_ivar_set(v->parser, id_errstatus, LONG2NUM(v->errstatus)); + + /* check if We can shift/reduce error token */ + D(printf("(err) k1=%ld\n", v->curstate)); + D(printf("(err) k2=%d (error)\n", ERR_TOK)); + while (1) { + tmp = AREF(v->action_pointer, v->curstate); + if (! NIL_P(tmp)) { + D(puts("(err) pointer[k1] true")); + i = NUM2LONG(tmp) + ERR_TOK; + D(printf("(err) i=%ld\n", i)); + if (i >= 0) { + vact = AREF(v->action_table, i); + if (! NIL_P(vact)) { + D(printf("(err) table[i]=%ld\n", NUM2LONG(vact))); + tmp = AREF(v->action_check, i); + if (! NIL_P(tmp) && NUM2LONG(tmp) == v->curstate) { + D(puts("(err) found: can handle error tok")); + break; + } + else { + D(puts("(err) check[i]!=k1 or nil")); + } + } + else { + D(puts("(err) table[i] == nil")); + } + } + } + D(puts("(err) not found: can't handle error tok: pop")); + + if (RARRAY(v->state)->len == 0) { + v->retval = Qnil; + v->fin = CP_FIN_CANTPOP; + return; + } + POP(v->state); + POP(v->vstack); + tmp = LAST_I(v->state); + v->curstate = NUM2LONG(tmp); + if (v->debug) { + POP(v->tstack); + rb_funcall(v->parser, id_d_e_pop, + 3, v->state, v->tstack, v->vstack); + } + } + act = NUM2LONG(vact); + + /* shift|reduce error token */ + + if (act > 0 && act < v->shift_n) { + D(puts("e shift")); + SHIFT(v, act, ERR_TOK, val); + } + else if (act < 0 && act > -(v->reduce_n)) { + int code; + + D(puts("e reduce")); + REDUCE(v, act); + } + else if (act == v->shift_n) { + D(puts("e accept")); + ACCEPT(v); + } + else { + rb_raise(RaccBug, "[Racc Bug] unknown act value %ld", act); + } + } + else if (act == v->shift_n) { + accept: + D(puts("accept")); + ACCEPT(v); + } + else { + rb_raise(RaccBug, "[Racc Bug] unknown act value %ld", act); + } + + if (v->debug) { + rb_funcall(v->parser, id_d_next_state, + 2, LONG2NUM(v->curstate), v->state); + } + } +} + + +static VALUE +catch_iter(parser) + VALUE parser; +{ + return rb_funcall(parser, id_catch, 1, sym_raccjump); +} + + +static VALUE +do_reduce(val, data, self) + VALUE val, data, self; +{ + struct cparse_params *v; + VALUE reduce_to, reduce_len, method_id; + long len; + ID mid; + VALUE tmp, tmp_t, tmp_v; + long i, k1, k2; + VALUE ret; + + Data_Get_Struct(data, struct cparse_params, v); + reduce_len = RARRAY(v->reduce_table)->ptr[v->ruleno]; + reduce_to = RARRAY(v->reduce_table)->ptr[v->ruleno+1]; + method_id = RARRAY(v->reduce_table)->ptr[v->ruleno+2]; + len = NUM2LONG(reduce_len); + mid = value_to_id(method_id); + + if (len == 0) { + tmp = Qnil; + if (mid != id_noreduce) + tmp_v = rb_ary_new(); + if (v->debug) + tmp_t = rb_ary_new(); + } + else { + if (mid != id_noreduce) { + tmp_v = GET_TAIL(v->vstack, len); + tmp = RARRAY(tmp_v)->ptr[0]; + } + else { + tmp = RARRAY(v->vstack)->ptr[ RARRAY(v->vstack)->len - len ]; + } + CUT_TAIL(v->vstack, len); + if (v->debug) { + tmp_t = GET_TAIL(v->tstack, len); + CUT_TAIL(v->tstack, len); + } + CUT_TAIL(v->state, len); + } + + /* method call must be done before tstack.push */ + if (mid != id_noreduce) { + if (v->use_result_var) { + tmp = rb_funcall(v->parser, mid, + 3, tmp_v, v->vstack, tmp); + } + else { + tmp = rb_funcall(v->parser, mid, + 2, tmp_v, v->vstack); + } + } + PUSH(v->vstack, tmp); + if (v->debug) { + PUSH(v->tstack, reduce_to); + rb_funcall(v->parser, id_d_reduce, + 4, tmp_t, reduce_to, v->tstack, v->vstack); + } + + if (RARRAY(v->state)->len == 0) { + rb_raise(RaccBug, "state stack unexpected empty"); + } + tmp = LAST_I(v->state); + k2 = NUM2LONG(tmp); + k1 = NUM2LONG(reduce_to) - v->nt_base; + D(printf("(goto) k1=%ld\n", k1)); + D(printf("(goto) k2=%ld\n", k2)); + + tmp = AREF(v->goto_pointer, k1); + if (! NIL_P(tmp)) { + i = NUM2LONG(tmp) + k2; + D(printf("(goto) i=%ld\n", i)); + if (i >= 0) { + ret = AREF(v->goto_table, i); + if (! NIL_P(ret)) { + D(printf("(goto) table[i]=%ld (ret)\n", NUM2LONG(ret))); + tmp = AREF(v->goto_check, i); + if (!NIL_P(tmp) && tmp == LONG2NUM(k1)) { + D(printf("(goto) check[i]=%ld\n", NUM2LONG(tmp))); + D(puts("(goto) found")); + goto doret; + } + else { + D(puts("(goto) check[i]!=table[i] or nil")); + } + } + else { + D(puts("(goto) table[i] == nil")); + } + } + } + D(puts("(goto) not found: use default")); + ret = AREF(v->goto_default, k1); + +doret: + PUSH(v->state, ret); + v->curstate = NUM2LONG(ret); + + return INT2FIX(0); +} + + +void +Init_cparse() +{ + VALUE Racc; + VALUE Parser; + ID id_racc = rb_intern("Racc"); + + if (rb_const_defined(rb_cObject, id_racc)) { + Racc = rb_const_get(rb_cObject, id_racc); + Parser = rb_const_get_at(Racc, rb_intern("Parser")); + } + else { + Racc = rb_define_module("Racc"); + Parser = rb_define_class_under(Racc, "Parser", rb_cObject); + } + rb_define_private_method(Parser, "_racc_do_parse_c", racc_cparse, 2); + rb_define_private_method(Parser, "_racc_yyparse_c", racc_yyparse, 4); + rb_define_const(Parser, "Racc_Runtime_Core_Version_C", + rb_str_new2(RACC_VERSION)); + rb_define_const(Parser, "Racc_Runtime_Core_Id_C", + rb_str_new2("$Id$")); + + CparseParams = rb_define_class_under(Racc, "CparseParams", rb_cObject); + + RaccBug = rb_eRuntimeError; + + id_yydebug = rb_intern("@yydebug"); + id_nexttoken = rb_intern("next_token"); + id_onerror = rb_intern("on_error"); + id_noreduce = rb_intern("_reduce_none"); + id_catch = rb_intern("catch"); + id_errstatus = rb_intern("@racc_error_status"); + sym_raccjump = id_to_value(rb_intern("racc_jump")); + + id_d_shift = rb_intern("racc_shift"); + id_d_reduce = rb_intern("racc_reduce"); + id_d_accept = rb_intern("racc_accept"); + id_d_read_token = rb_intern("racc_read_token"); + id_d_next_state = rb_intern("racc_next_state"); + id_d_e_pop = rb_intern("racc_e_pop"); +} diff --git a/ext/racc/cparse/depend b/ext/racc/cparse/depend new file mode 100644 index 0000000000..7b06a880f5 --- /dev/null +++ b/ext/racc/cparse/depend @@ -0,0 +1 @@ +cparse.o: cparse.c $(hdrdir)/ruby.h $(topdir)/config.h $(hdrdir)/defines.h diff --git a/ext/racc/cparse/extconf.rb b/ext/racc/cparse/extconf.rb new file mode 100644 index 0000000000..dd953a7e15 --- /dev/null +++ b/ext/racc/cparse/extconf.rb @@ -0,0 +1,4 @@ +# $Id$ + +require 'mkmf' +create_makefile 'racc/cparse' diff --git a/lib/README b/lib/README index d05964fa67..48aabfb1d8 100644 --- a/lib/README +++ b/lib/README @@ -47,6 +47,7 @@ pp.rb pretty print objects prettyprint.rb pretty printing algorithm profile.rb ruby profiler pstore.rb persistent object strage using marshal +racc/parser.rb racc (Ruby yACC) runtime rational.rb rational number support readbytes.rb define IO#readbytes resolv.rb DNS resolver in Ruby diff --git a/lib/racc/parser.rb b/lib/racc/parser.rb new file mode 100644 index 0000000000..ca581006d0 --- /dev/null +++ b/lib/racc/parser.rb @@ -0,0 +1,480 @@ +# +# parser.rb +# +# Copyright (c) 1999-2002 Minero Aoki <aamine@loveruby.net> +# +# This program is free software. +# You can distribute/modify this program under the same terms of ruby. +# +# As a special exception, when this code is copied by Racc +# into a Racc output file, you may use that output file +# without restriction. +# +# $Id$ +# + +unless defined? NotImplementedError then + NotImplementedError = NotImplementError +end + + +module Racc + class ParseError < StandardError; end +end +unless defined? ::ParseError then + ParseError = Racc::ParseError +end + + +module Racc + + unless defined? Racc_No_Extentions then + Racc_No_Extentions = false + end + + class Parser + + Racc_Runtime_Version = '1.4.2' + Racc_Runtime_Revision = '$Revision$'.split(/\s+/)[1] + + Racc_Runtime_Core_Version_R = '1.4.2' + Racc_Runtime_Core_Revision_R = '$Revision$'.split(/\s+/)[1] + begin + require 'racc/cparse' + # Racc_Runtime_Core_Version_C = (defined in extention) + Racc_Runtime_Core_Revision_C = Racc_Runtime_Core_Id_C.split(/\s+/)[2] + unless new.respond_to? :_racc_do_parse_c, true then + raise LoadError, 'old cparse.so' + end + if Racc_No_Extentions then + raise LoadError, 'selecting ruby version of racc runtime core' + end + + Racc_Main_Parsing_Routine = :_racc_do_parse_c + Racc_YY_Parse_Method = :_racc_yyparse_c + Racc_Runtime_Core_Version = Racc_Runtime_Core_Version_C + Racc_Runtime_Core_Revision = Racc_Runtime_Core_Revision_C + Racc_Runtime_Type = 'c' + rescue LoadError + Racc_Main_Parsing_Routine = :_racc_do_parse_rb + Racc_YY_Parse_Method = :_racc_yyparse_rb + Racc_Runtime_Core_Version = Racc_Runtime_Core_Version_R + Racc_Runtime_Core_Revision = Racc_Runtime_Core_Revision_R + Racc_Runtime_Type = 'ruby' + end + + def self.racc_runtime_type + Racc_Runtime_Type + end + + + private + + + def _racc_setup + t = self.type + + unless t::Racc_debug_parser then + @yydebug = false + end + @yydebug = false unless defined? @yydebug + + if @yydebug then + @racc_debug_out = $stderr unless defined? @racc_debug_out + @racc_debug_out ||= $stderr + end + + arg = t::Racc_arg + if arg.size < 14 then + arg[13] = true + end + arg + end + + def _racc_init_sysvars + @racc_state = [ 0 ] + @racc_tstack = [] + @racc_vstack = [] + + @racc_t = nil + @racc_val = nil + + @racc_read_next = true + + @racc_user_yyerror = false + @racc_error_status = 0 + end + + + ### + ### do_parse + ### + + def do_parse + __send__ Racc_Main_Parsing_Routine, _racc_setup(), false + end + + def next_token + raise NotImplementedError, "#{self.type}\#next_token is not defined" + end + + def _racc_do_parse_rb( arg, in_debug ) + action_table, action_check, action_default, action_pointer, + goto_table, goto_check, goto_default, goto_pointer, + nt_base, reduce_table, token_table, shift_n, + reduce_n, use_result, * = arg + + _racc_init_sysvars + tok = act = i = nil + nerr = 0 + + + catch( :racc_end_parse ) { + while true do + + if i = action_pointer[ @racc_state[-1] ] then + if @racc_read_next then + if @racc_t != 0 then # not EOF + tok, @racc_val = next_token() + unless tok then # EOF + @racc_t = 0 + else + @racc_t = (token_table[tok] or 1) # error token + end + racc_read_token( @racc_t, tok, @racc_val ) if @yydebug + + @racc_read_next = false + end + end + i += @racc_t + if i >= 0 and act = action_table[i] and + action_check[i] == @racc_state[-1] then + ; + else + act = action_default[ @racc_state[-1] ] + end + else + act = action_default[ @racc_state[-1] ] + end + + while act = _racc_evalact( act, arg ) do end + + end + } + end + + + ### + ### yyparse + ### + + def yyparse( recv, mid ) + __send__ Racc_YY_Parse_Method, recv, mid, _racc_setup(), true + end + + def _racc_yyparse_rb( recv, mid, arg, c_debug ) + action_table, action_check, action_default, action_pointer, + goto_table, goto_check, goto_default, goto_pointer, + nt_base, reduce_table, token_table, shift_n, + reduce_n, use_result, * = arg + + _racc_init_sysvars + tok = nil + act = nil + i = nil + nerr = 0 + + + catch( :racc_end_parse ) { + until i = action_pointer[ @racc_state[-1] ] do + while act = _racc_evalact( + action_default[ @racc_state[-1] ], arg ) do end + end + + recv.__send__( mid ) do |tok, val| +# $stderr.puts "rd: tok=#{tok}, val=#{val}" + unless tok then + @racc_t = 0 + else + @racc_t = (token_table[tok] or 1) # error token + end + @racc_val = val + @racc_read_next = false + + i += @racc_t + if i >= 0 and act = action_table[i] and + action_check[i] == @racc_state[-1] then +# $stderr.puts "01: act=#{act}" + else + act = action_default[ @racc_state[-1] ] +# $stderr.puts "02: act=#{act}" +# $stderr.puts "curstate=#{@racc_state[-1]}" + end + + while act = _racc_evalact( act, arg ) do end + + while not (i = action_pointer[ @racc_state[-1] ]) or + not @racc_read_next or + @racc_t == 0 do # $ + if i and i += @racc_t and + i >= 0 and + act = action_table[i] and + action_check[i] == @racc_state[-1] then +# $stderr.puts "03: act=#{act}" + ; + else +# $stderr.puts "04: act=#{act}" + act = action_default[ @racc_state[-1] ] + end + + while act = _racc_evalact( act, arg ) do end + end + end + } + end + + + ### + ### common + ### + + def _racc_evalact( act, arg ) +# $stderr.puts "ea: act=#{act}" + action_table, action_check, action_default, action_pointer, + goto_table, goto_check, goto_default, goto_pointer, + nt_base, reduce_table, token_table, shift_n, + reduce_n, use_result, * = arg +nerr = 0 # tmp + + if act > 0 and act < shift_n then + # + # shift + # + + if @racc_error_status > 0 then + @racc_error_status -= 1 unless @racc_t == 1 # error token + end + + @racc_vstack.push @racc_val + @racc_state.push act + @racc_read_next = true + + if @yydebug then + @racc_tstack.push @racc_t + racc_shift( @racc_t, @racc_tstack, @racc_vstack ) + end + + elsif act < 0 and act > -reduce_n then + # + # reduce + # + + code = catch( :racc_jump ) { + @racc_state.push _racc_do_reduce( arg, act ) + false + } + if code then + case code + when 1 # yyerror + @racc_user_yyerror = true # user_yyerror + return -reduce_n + when 2 # yyaccept + return shift_n + else + raise RuntimeError, '[Racc Bug] unknown jump code' + end + end + + elsif act == shift_n then + # + # accept + # + + racc_accept if @yydebug + throw :racc_end_parse, @racc_vstack[0] + + elsif act == -reduce_n then + # + # error + # + + case @racc_error_status + when 0 + unless arg[21] then # user_yyerror + nerr += 1 + on_error @racc_t, @racc_val, @racc_vstack + end + when 3 + if @racc_t == 0 then # is $ + throw :racc_end_parse, nil + end + @racc_read_next = true + end + @racc_user_yyerror = false + @racc_error_status = 3 + + while true do + if i = action_pointer[ @racc_state[-1] ] then + i += 1 # error token + if i >= 0 and + (act = action_table[i]) and + action_check[i] == @racc_state[-1] then + break + end + end + + throw :racc_end_parse, nil if @racc_state.size < 2 + @racc_state.pop + @racc_vstack.pop + if @yydebug then + @racc_tstack.pop + racc_e_pop( @racc_state, @racc_tstack, @racc_vstack ) + end + end + + return act + + else + raise RuntimeError, "[Racc Bug] unknown action #{act.inspect}" + end + + racc_next_state( @racc_state[-1], @racc_state ) if @yydebug + + nil + end + + def _racc_do_reduce( arg, act ) + action_table, action_check, action_default, action_pointer, + goto_table, goto_check, goto_default, goto_pointer, + nt_base, reduce_table, token_table, shift_n, + reduce_n, use_result, * = arg + state = @racc_state + vstack = @racc_vstack + tstack = @racc_tstack + + i = act * -3 + len = reduce_table[i] + reduce_to = reduce_table[i+1] + method_id = reduce_table[i+2] + void_array = [] + + tmp_t = tstack[ -len, len ] if @yydebug + tmp_v = vstack[ -len, len ] + tstack[ -len, len ] = void_array if @yydebug + vstack[ -len, len ] = void_array + state[ -len, len ] = void_array + + # tstack must be updated AFTER method call + if use_result then + vstack.push __send__(method_id, tmp_v, vstack, tmp_v[0]) + else + vstack.push __send__(method_id, tmp_v, vstack) + end + tstack.push reduce_to + + racc_reduce( tmp_t, reduce_to, tstack, vstack ) if @yydebug + + k1 = reduce_to - nt_base + if i = goto_pointer[ k1 ] then + i += state[-1] + if i >= 0 and (curstate = goto_table[i]) and goto_check[i] == k1 then + return curstate + end + end + goto_default[ k1 ] + end + + def on_error( t, val, vstack ) + raise ParseError, sprintf("\nparse error on value %s (%s)", + val.inspect, + token_to_str(t) || '?') + end + + def yyerror + throw :racc_jump, 1 + end + + def yyaccept + throw :racc_jump, 2 + end + + def yyerrok + @racc_error_status = 0 + end + + + # for debugging output + + def racc_read_token( t, tok, val ) + @racc_debug_out.print 'read ' + @racc_debug_out.print tok.inspect, '(', racc_token2str(t), ') ' + @racc_debug_out.puts val.inspect + @racc_debug_out.puts + end + + def racc_shift( tok, tstack, vstack ) + @racc_debug_out.puts "shift #{racc_token2str tok}" + racc_print_stacks tstack, vstack + @racc_debug_out.puts + end + + def racc_reduce( toks, sim, tstack, vstack ) + out = @racc_debug_out + out.print 'reduce ' + if toks.empty? then + out.print ' <none>' + else + toks.each {|t| out.print ' ', racc_token2str(t) } + end + out.puts " --> #{racc_token2str(sim)}" + + racc_print_stacks tstack, vstack + @racc_debug_out.puts + end + + def racc_accept + @racc_debug_out.puts 'accept' + @racc_debug_out.puts + end + + def racc_e_pop( state, tstack, vstack ) + @racc_debug_out.puts 'error recovering mode: pop token' + racc_print_states state + racc_print_stacks tstack, vstack + @racc_debug_out.puts + end + + def racc_next_state( curstate, state ) + @racc_debug_out.puts "goto #{curstate}" + racc_print_states state + @racc_debug_out.puts + end + + def racc_print_stacks( t, v ) + out = @racc_debug_out + out.print ' [' + t.each_index do |i| + out.print ' (', racc_token2str(t[i]), ' ', v[i].inspect, ')' + end + out.puts ' ]' + end + + def racc_print_states( s ) + out = @racc_debug_out + out.print ' [' + s.each {|st| out.print ' ', st } + out.puts ' ]' + end + + def racc_token2str( tok ) + type::Racc_token_to_s_table[tok] or + raise RuntimeError, "[Racc Bug] can't convert token #{tok} to string" + end + + def token_to_str( t ) + type::Racc_token_to_s_table[t] + end + + end + +end |