5 #include "interpreter.h"
7 #define RESIZE_ARRAY_IF_NECESSARY(ptr, size, desired_size) \
8 if(size < desired_size) \
11 ptr = realloc(ptr, size*sizeof(*ptr)); \
14 struct parse_stack_frame
*init_new_stack_frame(struct parse_state
*parse_state
, struct rtn
*rtn
)
16 struct parse_stack_frame
*frame
= &parse_state
->parse_stack
[parse_state
->parse_stack_length
++];
18 frame
->rtn_state
= &rtn
->states
[0];
19 frame
->slots
.rtn
= rtn
;
20 frame
->slots
.num_slots
= rtn
->num_slots
;
22 RESIZE_ARRAY_IF_NECESSARY(parse_state
->slotbuf
, parse_state
->slotbuf_size
,
23 parse_state
->slotbuf_len
+ frame
->slots
.num_slots
);
25 frame
->slots
.slots
= &parse_state
->slotbuf
[parse_state
->slotbuf_len
];
26 parse_state
->slotbuf_len
+= frame
->slots
.num_slots
;
31 struct parse_stack_frame
*pop_stack_frame(struct parse_state
*parse_state
)
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)
38 return NULL
; /* the parse is over */
43 frame
->rtn_state
= frame
->rtn_transition
->dest_state
;
48 void reset_dfa_match(struct parse_state
*parse_state
)
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
;
57 void do_rtn_transition(struct parse_state
*parse_state
, int match_begin
, int match_len
, char *terminal
)
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;
63 /* is this an ignored terminal? if so, just skip it */
64 for(int i
= 0; i
< frame
->rtn
->num_ignore
; i
++)
66 if(frame
->rtn
->ignore_terminals
[i
] == terminal
)
68 reset_dfa_match(parse_state
);
73 /* find a transition out of this RTN state on this terminal */
74 for(int i
= 0; i
< frame
->rtn_state
->num_transitions
; i
++)
76 struct rtn_transition
*t
= &frame
->rtn_state
->transitions
[i
];
77 if(t
->transition_type
== TERMINAL_TRANSITION
&& t
->edge
.terminal_name
== terminal
)
79 frame
->slots
.slots
[t
->slotnum
] = val
;
80 frame
->rtn_state
= t
->dest_state
;
81 found_transition
= true;
84 else if(t
->transition_type
== DECISION
&& t
->edge
.decision
->terminal_name
== terminal
)
86 struct decision
*d
= t
->edge
.decision
;
88 for(int i
= 0; i
< d
->num_actions
; i
++)
90 struct rtn_transition
*t2
= &frame
->rtn_state
->transitions
[d
->actions
[i
]];
92 if(t2
->transition_type
== NONTERM_TRANSITION
)
94 if(parse_state
->parse_stack_length
== parse_state
->parse_stack_size
)
96 printf("Need to reallocate parse stack!!\n");
99 frame
->rtn_transition
= t2
;
100 frame
= init_new_stack_frame(parse_state
, t2
->edge
.nonterminal
);
102 else if(t2
->transition_type
== TERMINAL_TRANSITION
)
104 frame
->slots
.slots
[t2
->slotnum
] = val
;
105 frame
->rtn_state
= t2
->dest_state
;
108 found_transition
= true;
115 while(parse_state
->parse_stack_length
> 0 && frame
->rtn_state
->is_final
)
117 frame
= pop_stack_frame(parse_state
);
120 if(parse_state
->parse_stack_length
> 0)
121 reset_dfa_match(parse_state
);
125 printf("Syntax error -- no RTN transition!!\n");
129 void refill_buffer(struct parse_state
*state
)
131 struct buffer
*b
= state
->buffer
;
132 /* if more than 1/4 of the buffer is precious (can't be discarded), double the
134 int precious_len
= state
->offset
- state
->precious_offset
;
135 if(precious_len
> (b
->size
/ 4))
138 b
->buf
= realloc(b
->buf
, b
->size
);
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
;
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
);
156 printf("Error reading from file!\n");
161 b
->len
+= bytes_read
;
164 void parse(struct parse_state
*parse_state
)
166 bool user_cancelled
= false;
168 while(!parse_state
->buffer
->is_eof
&& !user_cancelled
&& parse_state
->parse_stack_length
> 0)
170 if(parse_state
->offset
== parse_state
->buffer
->base_offset
+ parse_state
->buffer
->len
)
171 refill_buffer(parse_state
);
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;
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
++)
181 struct intfa_transition
*t
= &parse_state
->dfa_state
->transitions
[i
];
183 if(ch
>= t
->ch_low
&& ch
<= t
->ch_high
)
185 parse_state
->dfa_state
= t
->dest_state
;
186 found_transition
= 1;
193 if(parse_state
->dfa_state
->final
)
195 parse_state
->last_match_state
= parse_state
->dfa_state
;
196 parse_state
->last_match_end
= parse_state
->offset
;
198 parse_state
->offset
++;
202 /* if there was a previous match, fall back to that. otherwise this character represents
204 if(parse_state
->last_match_state
)
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
);
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
);
226 void alloc_parse_state(struct parse_state
*state
)
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';
233 state
->parse_stack_size
= 50;
234 state
->parse_stack
= malloc(sizeof(struct parse_stack_frame
) * state
->parse_stack_size
);
236 state
->slotbuf_size
= 200;
237 state
->slotbuf
= malloc(sizeof(*state
->slotbuf
) * state
->slotbuf_size
);
240 static void init_parse_state_common(struct parse_state
*state
);
242 void reinit_parse_state(struct parse_state
*state
)
244 state
->buffer
->base_offset
-= state
->offset
;
245 init_parse_state_common(state
);
248 void init_parse_state(struct parse_state
*state
, struct grammar
*g
, FILE *file
)
252 state
->buffer
->file
= file
;
253 state
->buffer
->len
= 0;
254 state
->buffer
->base_offset
= 0;
255 state
->buffer
->is_eof
= false;
257 init_parse_state_common(state
);
260 static void init_parse_state_common(struct parse_state
*state
)
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
;
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
;
278 state
->dfa
= frame
->rtn_state
->term_dfa
;
279 state
->dfa_state
= &state
->dfa
->states
[0];
282 void free_parse_state(struct parse_state
*state
)
284 free(state
->buffer
->buf
);
286 free(state
->parse_stack
);
287 free(state
->slotbuf
);
292 * c-file-style: "bsd"
294 * indent-tabs-mode: nil