1 {
2 LR(0) set construction. For an explanation of this algorithm, see
3 Aho/Sethi/Ullman, "Compilers : Principles, Techniques and Tools,"
4 1986, Section 4.7.
5
6
7 Copyright (c) 1990-92 Albert Graef <ag@muwiinfa.geschichte.uni-mainz.de>
8 Copyright (C) 1996 Berend de Boer <berend@pobox.com>
9
10 This program is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 2 of the License, or
13 (at your option) any later version.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
23
24
25 $Revision: 1.2 $
26 $Modtime: 96-07-31 14:09 $
27
28 $History: YACCLR0.PAS $
29 *
30 * ***************** Version 2 *****************
31 * User: Berend Date: 96-10-10 Time: 21:16
32 * Updated in $/Lex and Yacc/tply
33 * Updated for protected mode, windows and Delphi 1.X and 2.X.
34
35 }
36
37
38 unit YaccLR0;
39
40 interface
41
42
43 procedure LR0Set;
44 (* constructs the LR(0) state set, shift and goto transitions and
45 corresponding kernel items *)
46
47 implementation
48
49 uses YaccBase, YaccTabl;
50
51 (* This implementation is based on the algorithm given in Aho/Sethi/Ullman,
52 1986, Section 4.7. *)
53
54 procedure get_syms ( var item_set : ItemSet; var sym_set : IntSet );
55 (* get the symbols for which there are transitions in item_set *)
56 var i : Integer;
57 begin
58 with item_set do
59 begin
60 empty(sym_set);
61 for i := 1 to n_items do
62 with item[i], rule_table^[rule_no]^ do
63 if pos_no<=rhs_len then
64 include(sym_set, rhs_sym[pos_no]);
65 end;
66 end(*get_syms*);
67
make_statenull68 function make_state ( var item_set : ItemSet; sym : Integer ) : Integer;
69 (* construct a new state for the transitions in item_set on symbol sym;
70 returns: the new state number *)
71 var i : Integer;
72 begin
73 with item_set do
74 begin
75 (* add the new state: *)
76 new_state;
77 for i := 1 to n_items do
78 with item[i], rule_table^[rule_no]^ do
79 if (pos_no<=rhs_len) and (rhs_sym[pos_no]=sym) then
80 add_item(rule_no, pos_no+1);
81 make_state := add_state;
82 end;
83 end(*make_state*);
84
85 procedure add_next_links;
86 (* add links to successor items for kernel items in the active state *)
87 var k, i : Integer;
88 begin
89 with state_table^[act_state] do
90 for k := trans_lo to trans_hi do
91 with trans_table^[k] do
92 for i := item_lo to item_hi do
93 with item_table^[i], rule_table^[rule_no]^ do
94 if (pos_no<=rhs_len) and (rhs_sym[pos_no]=sym) then
95 next := find_item(next_state, rule_no, pos_no+1 );
96 end(*add_next_links*);
97
98 procedure LR0Set;
99 var act_items : ItemSet;
100 act_syms : IntSet;
101 i : Integer;
102 begin
103 (* initialize state 0: *)
104 new_state;
105 add_item(1, 1); (* augmented start production *)
106 act_state := add_state;
107 (* build the state table: *)
108 repeat
109 (* compute the closure of the current state: *)
110 get_item_set(act_state, act_items);
111 closure(act_items);
112 (* sort items: *)
113 sort_item_set(act_items);
114 (* determine symbols used in shift and goto transitions: *)
115 get_syms(act_items, act_syms);
116 (* add transitions: *)
117 start_trans;
118 for i := 1 to size(act_syms) do
119 if act_syms[i]=0 then
120 (* accept action *)
121 add_trans(0, 0)
122 else
123 (* shift/goto action *)
124 add_trans(act_syms[i], make_state(act_items, act_syms[i]));
125 end_trans;
126 (* add next links to kernel items: *)
127 add_next_links;
128 (* switch to next state: *)
129 inc(act_state);
130 until act_state=n_states;
131 end(*LR0Set*);
132
133 end(*YaccLR0*).
134