1 /* $Id: lr0.c,v 1.19 2016/06/07 00:21:53 tom Exp $ */
5 static core
*new_state(int symbol
);
6 static Value_t
get_state(int symbol
);
7 static void allocate_itemsets(void);
8 static void allocate_storage(void);
9 static void append_states(void);
10 static void free_storage(void);
11 static void generate_states(void);
12 static void initialize_states(void);
13 static void new_itemsets(void);
14 static void save_reductions(void);
15 static void save_shifts(void);
16 static void set_derives(void);
17 static void set_nullable(void);
22 reductions
*first_reduction
;
24 static core
**state_set
;
25 static core
*this_state
;
26 static core
*last_state
;
27 static shifts
*last_shift
;
28 static reductions
*last_reduction
;
31 static Value_t
*shift_symbol
;
33 static Value_t
*rules
;
35 static Value_t
*redset
;
36 static Value_t
*shiftset
;
38 static Value_t
**kernel_base
;
39 static Value_t
**kernel_end
;
40 static Value_t
*kernel_items
;
43 allocate_itemsets(void)
51 Value_t
*symbol_count
;
54 symbol_count
= NEW2(nsyms
, Value_t
);
56 item_end
= ritem
+ nitems
;
57 for (itemp
= ritem
; itemp
< item_end
; itemp
++)
63 symbol_count
[symbol
]++;
67 kernel_base
= NEW2(nsyms
, Value_t
*);
68 kernel_items
= NEW2(count
, Value_t
);
72 for (i
= 0; i
< nsyms
; i
++)
74 kernel_base
[i
] = kernel_items
+ count
;
75 count
+= symbol_count
[i
];
76 if (max
< symbol_count
[i
])
77 max
= symbol_count
[i
];
80 shift_symbol
= symbol_count
;
81 kernel_end
= NEW2(nsyms
, Value_t
*);
85 allocate_storage(void)
88 shiftset
= NEW2(nsyms
, Value_t
);
89 redset
= NEW2(nrules
+ 1, Value_t
);
90 state_set
= NEW2(nitems
, core
*);
101 fprintf(stderr
, "Entering append_states()\n");
103 for (i
= 1; i
< nshifts
; i
++)
105 symbol
= shift_symbol
[i
];
107 while (j
> 0 && shift_symbol
[j
- 1] > symbol
)
109 shift_symbol
[j
] = shift_symbol
[j
- 1];
112 shift_symbol
[j
] = symbol
;
115 for (i
= 0; i
< nshifts
; i
++)
117 symbol
= shift_symbol
[i
];
118 shiftset
[i
] = get_state(symbol
);
135 generate_states(void)
138 itemset
= NEW2(nitems
, Value_t
);
139 ruleset
= NEW2(WORDSIZE(nrules
), unsigned);
145 closure(this_state
->items
, this_state
->nitems
);
153 this_state
= this_state
->next
;
160 get_state(int symbol
)
171 fprintf(stderr
, "Entering get_state(%d)\n", symbol
);
174 isp1
= kernel_base
[symbol
];
175 iend
= kernel_end
[symbol
];
176 n
= (int)(iend
- isp1
);
179 assert(0 <= key
&& key
< nitems
);
189 isp1
= kernel_base
[symbol
];
192 while (found
&& isp1
< iend
)
194 if (*isp1
++ != *isp2
++)
207 sp
= sp
->link
= new_state(symbol
);
215 state_set
[key
] = sp
= new_state(symbol
);
222 initialize_states(void)
225 Value_t
*start_derives
;
228 start_derives
= derives
[start_symbol
];
229 for (i
= 0; start_derives
[i
] >= 0; ++i
)
232 p
= (core
*)MALLOC(sizeof(core
) + i
* sizeof(Value_t
));
238 p
->accessing_symbol
= 0;
239 p
->nitems
= (Value_t
)i
;
241 for (i
= 0; start_derives
[i
] >= 0; ++i
)
242 p
->items
[i
] = rrhs
[start_derives
[i
]];
244 first_state
= last_state
= this_state
= p
;
257 for (i
= 0; i
< nsyms
; i
++)
262 while (isp
< itemsetend
)
268 ksp
= kernel_end
[symbol
];
271 shift_symbol
[shiftcount
++] = symbol
;
272 ksp
= kernel_base
[symbol
];
275 *ksp
++ = (Value_t
)(i
+ 1);
276 kernel_end
[symbol
] = ksp
;
280 nshifts
= shiftcount
;
284 new_state(int symbol
)
293 fprintf(stderr
, "Entering new_state(%d)\n", symbol
);
296 if (nstates
>= MAXYYINT
)
297 fatal("too many states");
299 isp1
= kernel_base
[symbol
];
300 iend
= kernel_end
[symbol
];
301 n
= (unsigned)(iend
- isp1
);
303 p
= (core
*)allocate((sizeof(core
) + (n
- 1) * sizeof(Value_t
)));
304 p
->accessing_symbol
= (Value_t
)symbol
;
305 p
->number
= (Value_t
)nstates
;
306 p
->nitems
= (Value_t
)n
;
312 last_state
->next
= p
;
320 /* show_cores is used for debugging */
330 for (p
= first_state
; p
; ++k
, p
= p
->next
)
334 printf("state %d, number = %d, accessing symbol = %s\n",
335 k
, p
->number
, symbol_name
[p
->accessing_symbol
]);
337 for (i
= 0; i
< n
; ++i
)
339 itemno
= p
->items
[i
];
340 printf("%4d ", itemno
);
342 while (ritem
[j
] >= 0)
344 printf("%s :", symbol_name
[rlhs
[-ritem
[j
]]]);
347 printf(" %s", symbol_name
[ritem
[j
++]]);
349 while (ritem
[j
] >= 0)
350 printf(" %s", symbol_name
[ritem
[j
++]]);
357 /* show_ritems is used for debugging */
364 for (i
= 0; i
< nitems
; ++i
)
365 printf("ritem[%d] = %d\n", i
, ritem
[i
]);
368 /* show_rrhs is used for debugging */
374 for (i
= 0; i
< nrules
; ++i
)
375 printf("rrhs[%d] = %d\n", i
, rrhs
[i
]);
378 /* show_shifts is used for debugging */
387 for (p
= first_shift
; p
; ++k
, p
= p
->next
)
391 printf("shift %d, number = %d, nshifts = %d\n", k
, p
->number
,
394 for (i
= 0; i
< j
; ++i
)
395 printf("\t%d\n", p
->shift
[i
]);
408 p
= (shifts
*)allocate((sizeof(shifts
) +
409 (unsigned)(nshifts
- 1) * sizeof(Value_t
)));
411 p
->number
= this_state
->number
;
412 p
->nshifts
= (Value_t
)nshifts
;
416 send
= shiftset
+ nshifts
;
423 last_shift
->next
= p
;
434 save_reductions(void)
445 for (isp
= itemset
; isp
< itemsetend
; isp
++)
450 redset
[count
++] = (Value_t
)-item
;
456 p
= (reductions
*)allocate((sizeof(reductions
) +
457 (unsigned)(count
- 1) *
460 p
->number
= this_state
->number
;
472 last_reduction
->next
= p
;
489 derives
= NEW2(nsyms
, Value_t
*);
490 rules
= NEW2(nvars
+ nrules
, Value_t
);
493 for (lhs
= start_symbol
; lhs
< nsyms
; lhs
++)
495 derives
[lhs
] = rules
+ k
;
496 for (i
= 0; i
< nrules
; i
++)
520 printf("\nDERIVES\n\n");
522 for (i
= start_symbol
; i
< nsyms
; i
++)
524 printf("%s derives ", symbol_name
[i
]);
525 for (sp
= derives
[i
]; *sp
>= 0; sp
++)
543 nullable
= TMALLOC(char, nsyms
);
546 for (i
= 0; i
< nsyms
; ++i
)
553 for (i
= 1; i
< nitems
; i
++)
556 while ((j
= ritem
[i
]) >= 0)
575 for (i
= 0; i
< nsyms
; i
++)
578 printf("%s is nullable\n", symbol_name
[i
]);
580 printf("%s is not nullable\n", symbol_name
[i
]);
599 if (derives
[start_symbol
] != rules
)
601 DO_FREE(derives
[start_symbol
]);