runtime/interpreter.c

   1
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include "interpreter.h"
   6
   7 #define RESIZE_ARRAY_IF_NECESSARY(ptr, size, desired_size) \
   8     if(size < desired_size) \
   9     { \
  10         size *= 2; \
  11         ptr = realloc(ptr, size*sizeof(*ptr)); \
  12     }
  13
  14 struct parse_stack_frame *init_new_stack_frame(struct parse_state *parse_state, struct rtn *rtn)
  15 {
  16     struct parse_stack_frame *frame = &parse_state->parse_stack[parse_state->parse_stack_length++];
  17     frame->rtn = rtn;
  18     frame->rtn_state = &rtn->states[0];
  19     frame->slots.rtn = rtn;
  20     frame->slots.num_slots = rtn->num_slots;
  21
  22     RESIZE_ARRAY_IF_NECESSARY(parse_state->slotbuf, parse_state->slotbuf_size,
  23                               parse_state->slotbuf_len + frame->slots.num_slots);
  24
  25     frame->slots.slots = &parse_state->slotbuf[parse_state->slotbuf_len];
  26     parse_state->slotbuf_len += frame->slots.num_slots;
  27
  28     return frame;
  29 }
  30
  31 struct parse_stack_frame *pop_stack_frame(struct parse_state *parse_state)
  32 {
  33     struct parse_stack_frame *frame = &parse_state->parse_stack[parse_state->parse_stack_length-1];
  34     parse_state->slotbuf_len -= frame->slots.num_slots;
  35     parse_state->parse_stack_length--;
  36     if(parse_state->parse_stack_length == 0)
  37     {
  38         return NULL;  /* the parse is over */
  39     }
  40     else
  41     {
  42         frame--;
  43         frame->rtn_state = frame->rtn_transition->dest_state;
  44         return frame;
  45     }
  46 }
  47
  48 void reset_dfa_match(struct parse_state *parse_state)
  49 {
  50     struct parse_stack_frame *frame = &parse_state->parse_stack[parse_state->parse_stack_length-1];
  51     parse_state->dfa = frame->rtn_state->term_dfa;
  52     parse_state->dfa_state = &parse_state->dfa->states[0];
  53     parse_state->match_begin = parse_state->offset;
  54     parse_state->last_match_state = NULL;
  55 }
  56
  57 void do_rtn_transition(struct parse_state *parse_state, int match_begin, int match_len, char *terminal)
  58 {
  59     struct parse_stack_frame *frame = &parse_state->parse_stack[parse_state->parse_stack_length-1];
  60     struct parse_val val = {PARSE_VAL_TERMINAL, {.terminal = {match_begin, match_len}}};
  61     bool found_transition = false;
  62
  63     /* is this an ignored terminal?  if so, just skip it */
  64     for(int i = 0; i < frame->rtn->num_ignore; i++)
  65     {
  66         if(frame->rtn->ignore_terminals[i] == terminal)
  67         {
  68             reset_dfa_match(parse_state);
  69             return;
  70         }
  71     }
  72
  73     /* find a transition out of this RTN state on this terminal */
  74     for(int i = 0; i < frame->rtn_state->num_transitions; i++)
  75     {
  76         struct rtn_transition *t = &frame->rtn_state->transitions[i];
  77         if(t->transition_type == TERMINAL_TRANSITION && t->edge.terminal_name == terminal)
  78         {
  79             frame->slots.slots[t->slotnum] = val;
  80             frame->rtn_state = t->dest_state;
  81             found_transition = true;
  82             break;
  83         }
  84         else if(t->transition_type == DECISION && t->edge.decision->terminal_name == terminal)
  85         {
  86             struct decision *d = t->edge.decision;
  87
  88             for(int i = 0; i < d->num_actions; i++)
  89             {
  90                 struct rtn_transition *t2 = &frame->rtn_state->transitions[d->actions[i]];
  91
  92                 if(t2->transition_type == NONTERM_TRANSITION)
  93                 {
  94                     if(parse_state->parse_stack_length == parse_state->parse_stack_size)
  95                     {
  96                         printf("Need to reallocate parse stack!!\n");
  97                         exit(1);
  98                     }
  99                     frame->rtn_transition = t2;
 100                     frame = init_new_stack_frame(parse_state, t2->edge.nonterminal);
 101                 }
 102                 else if(t2->transition_type == TERMINAL_TRANSITION)
 103                 {
 104                     frame->slots.slots[t2->slotnum] = val;
 105                     frame->rtn_state = t2->dest_state;
 106                 }
 107             }
 108             found_transition = true;
 109             break;
 110         }
 111     }
 112
 113     if(found_transition)
 114     {
 115         while(parse_state->parse_stack_length > 0 && frame->rtn_state->is_final)
 116         {
 117             frame = pop_stack_frame(parse_state);
 118         }
 119
 120         if(parse_state->parse_stack_length > 0)
 121             reset_dfa_match(parse_state);
 122     }
 123     else
 124     {
 125         printf("Syntax error -- no RTN transition!!\n");
 126     }
 127 }
 128
 129 void refill_buffer(struct parse_state *state)
 130 {
 131     struct buffer *b = state->buffer;
 132     /* if more than 1/4 of the buffer is precious (can't be discarded), double the
 133      * buffer size */
 134     int precious_len = state->offset - state->precious_offset;
 135     if(precious_len > (b->size / 4))
 136     {
 137         b->size *= 2;
 138         b->buf = realloc(b->buf, b->size);
 139     }
 140
 141     memmove(b->buf, b->buf + state->precious_offset - b->base_offset, precious_len);
 142     b->len = precious_len;
 143     b->base_offset = state->precious_offset;
 144
 145     /* now read from the file as much as we can */
 146     int bytes_read = fread(b->buf + b->len, sizeof(char), b->size - b->len, b->file);
 147
 148     if(bytes_read == 0)
 149     {
 150         if(feof(b->file))
 151         {
 152             b->is_eof = true;
 153         }
 154         else
 155         {
 156             printf("Error reading from file!\n");
 157             exit(1);
 158         }
 159     }
 160
 161     b->len += bytes_read;
 162 }
 163
 164 void parse(struct parse_state *parse_state)
 165 {
 166     bool user_cancelled = false;
 167
 168     while(!parse_state->buffer->is_eof && !user_cancelled && parse_state->parse_stack_length > 0)
 169     {
 170         if(parse_state->offset == parse_state->buffer->base_offset + parse_state->buffer->len)
 171             refill_buffer(parse_state);
 172
 173         int ch = parse_state->buffer->buf[parse_state->offset - parse_state->buffer->base_offset];
 174         //printf("Offset: %d, char %c\n", parse_state->offset, ch);
 175         int found_transition = 0;
 176
 177         /* We've read one character, which should cause one transition in the DFA for terminals.
 178          * Find the appropriate transition, and put the DFA in its new state. */
 179         for(int i = 0; i < parse_state->dfa_state->num_transitions; i++)
 180         {
 181             struct intfa_transition *t = &parse_state->dfa_state->transitions[i];
 182
 183             if(ch >= t->ch_low && ch <= t->ch_high)
 184             {
 185                 parse_state->dfa_state = t->dest_state;
 186                 found_transition = 1;
 187                 break;
 188             }
 189         }
 190
 191         if(found_transition)
 192         {
 193             if(parse_state->dfa_state->final)
 194             {
 195                 parse_state->last_match_state = parse_state->dfa_state;
 196                 parse_state->last_match_end = parse_state->offset;
 197             }
 198             parse_state->offset++;
 199         }
 200         else
 201         {
 202             /* if there was a previous match, fall back to that.  otherwise this character represents
 203              * a syntax error. */
 204             if(parse_state->last_match_state)
 205             {
 206                 /* we have a terminal.  do RTN transitions as appropriate */
 207                 //int terminal_len = parse_state->last_match_end-parse_state->match_begin+1;
 208                 //char terminal[terminal_len];
 209                 //memcpy(terminal, parse_state->buffer->buf+parse_state->match_begin, terminal_len);
 210                 //terminal[terminal_len] = '\0';
 211                 //printf("Recognized a terminal (%s) (%s)\n", parse_state->last_match_state->final, terminal);
 212                 parse_state->offset = parse_state->last_match_end + 1;
 213                 do_rtn_transition(parse_state, parse_state->match_begin, parse_state->last_match_end,
 214                                   parse_state->last_match_state->final);
 215             }
 216             else
 217             {
 218                 printf("Syntax error!\n");
 219                 printf("offset(%d), base_offset(%d), len(%d)\n", parse_state->offset, parse_state->buffer->base_offset, parse_state->buffer->len);
 220                 printf("Buffer: %s\n", parse_state->buffer->buf + parse_state->offset - parse_state->buffer->base_offset);
 221             }
 222         }
 223     }
 224 }
 225
 226 void alloc_parse_state(struct parse_state *state)
 227 {
 228     state->buffer = malloc(sizeof(struct buffer));
 229     state->buffer->size = 4096;
 230     state->buffer->buf = malloc((state->buffer->size+1) * sizeof(char));
 231     state->buffer->buf[state->buffer->size] = '\0';
 232
 233     state->parse_stack_size = 50;
 234     state->parse_stack = malloc(sizeof(struct parse_stack_frame) * state->parse_stack_size);
 235
 236     state->slotbuf_size = 200;
 237     state->slotbuf = malloc(sizeof(*state->slotbuf) * state->slotbuf_size);
 238 }
 239
 240 static void init_parse_state_common(struct parse_state *state);
 241
 242 void reinit_parse_state(struct parse_state *state)
 243 {
 244     state->buffer->base_offset -= state->offset;
 245     init_parse_state_common(state);
 246 }
 247
 248 void init_parse_state(struct parse_state *state, struct grammar *g, FILE *file)
 249 {
 250     state->grammar = g;
 251
 252     state->buffer->file = file;
 253     state->buffer->len  = 0;
 254     state->buffer->base_offset = 0;
 255     state->buffer->is_eof = false;
 256
 257     init_parse_state_common(state);
 258 }
 259
 260 static void init_parse_state_common(struct parse_state *state)
 261 {
 262     state->offset = 0;
 263     state->precious_offset = 0;
 264     state->parse_stack_length = 1;
 265     state->match_begin = 0;
 266     state->last_match_end = 0;
 267     state->last_match_state = NULL;
 268
 269     struct parse_stack_frame *frame = &state->parse_stack[0];
 270     frame->rtn = &state->grammar->rtns[0];
 271     frame->rtn_state = &frame->rtn->states[0];
 272     frame->rtn_transition = NULL;
 273     frame->slots.num_slots = frame->rtn->num_slots;
 274     frame->slots.rtn = frame->rtn;
 275     frame->slots.slots = state->slotbuf;
 276     state->slotbuf_len = frame->slots.num_slots;
 277
 278     state->dfa = frame->rtn_state->term_dfa;
 279     state->dfa_state = &state->dfa->states[0];
 280 }
 281
 282 void free_parse_state(struct parse_state *state)
 283 {
 284     free(state->buffer->buf);
 285     free(state->buffer);
 286     free(state->parse_stack);
 287     free(state->slotbuf);
 288 }
 289
 290 /*
 291  * Local Variables:
 292  * c-file-style: "bsd"
 293  * c-basic-offset: 4
 294  * indent-tabs-mode: nil
 295  * End:
 296  * vim:et:sts=4:sw=4
 297  */