1-- Copyright (c) 1990 Regents of the University of California.
2-- All rights reserved.
3--
4--    The primary authors of ayacc were David Taback and Deepak Tolani.
5--    Enhancements were made by Ronald J. Schmalz.
6--
7--    Send requests for ayacc information to ayacc-info@ics.uci.edu
8--    Send bug reports for ayacc to ayacc-bugs@ics.uci.edu
9--
10-- Redistribution and use in source and binary forms are permitted
11-- provided that the above copyright notice and this paragraph are
12-- duplicated in all such forms and that any documentation,
13-- advertising materials, and other materials related to such
14-- distribution and use acknowledge that the software was developed
15-- by the University of California, Irvine.  The name of the
16-- University may not be used to endorse or promote products derived
17-- from this software without specific prior written permission.
18-- THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
19-- IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
20-- WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
21
22-- Module       : lr0_machine.ada
23-- Component of : ayacc
24-- Version      : 1.2
25-- Date         : 11/21/86  12:30:58
26-- SCCS File    : disk21~/rschm/hasee/sccs/ayacc/sccs/sxlr0_machine.ada
27
28-- $Header: lr0_machine.a,v 0.1 86/04/01 15:06:19 ada Exp $
29-- $Log:	lr0_machine.a,v $
30-- Revision 0.1  86/04/01  15:06:19  ada
31--  This version fixes some minor bugs with empty grammars
32--  and $$ expansion. It also uses vads5.1b enhancements
33--  such as pragma inline.
34--
35--
36-- Revision 0.0  86/02/19  18:37:14  ada
37--
38-- These files comprise the initial version of Ayacc
39-- designed and implemented by David Taback and Deepak Tolani.
40-- Ayacc has been compiled and tested under the Verdix Ada compiler
41-- version 4.06 on a vax 11/750 running Unix 4.2BSD.
42--
43
44with Rule_Table, Symbol_Table, Set_Pack;
45use  Rule_Table, Symbol_Table;
46package LR0_Machine is
47
48    type Parse_State   is   range -1..5_000;
49    Null_Parse_State   :    constant Parse_State := -1;
50
51    type Item is
52	record
53	    Rule_ID      : Rule;
54	    Dot_Position : Natural;
55	end record;
56
57    type Transition is
58	record
59	    Symbol   : Grammar_Symbol;
60	    State_ID : Parse_State;
61	end record;
62
63    function "<" (Item_1,  Item_2  : Item)        return Boolean;
64    function "<" (Trans_1, Trans_2 : Transition)  return Boolean;
65
66
67    package Parse_State_Set_Pack     is new Set_Pack(Parse_State,    "<");
68    package Item_Set_Pack            is new Set_Pack(Item,           "<");
69    package Transition_Set_Pack      is new Set_Pack(Transition,     "<");
70    package Grammar_Symbol_Set_Pack  is new Set_Pack(Grammar_Symbol, "<");
71
72    subtype Parse_State_Set          is Parse_State_Set_Pack.Set;
73    subtype Item_Set                 is Item_Set_Pack.Set;
74    subtype Transition_Set           is Transition_Set_Pack.Set;
75    subtype Grammar_Symbol_Set       is Grammar_Symbol_Set_Pack.Set;
76
77    subtype Parse_State_Iterator     is Parse_State_Set_Pack.Set_Iterator;
78    subtype Item_Iterator            is Item_Set_Pack.Set_Iterator;
79    subtype Transition_Iterator      is Transition_Set_Pack.Set_Iterator;
80    subtype Grammar_Symbol_Iterator  is Grammar_Symbol_Set_Pack.Set_Iterator;
81
82
83    procedure LR0_Initialize;    -- must be called first.
84
85    function First_Parse_State  return  Parse_State;
86    function Last_Parse_State   return  Parse_State;
87
88
89    function Get_Goto
90	(State_ID : Parse_State;
91	 Sym      : Grammar_Symbol) return Parse_State;
92
93
94    -- Returns the predecessor states of STATE_ID and the item I.
95    -- Must be called with PRED_SET empty!
96    procedure Get_Pred_Set
97	(State_ID : in Parse_State;
98	 I        : in Item;
99	 Pred_Set : in out Parse_State_Set);
100
101
102
103
104    type Transition_Type is (Terminals, Nonterminals, Grammar_Symbols);
105
106    procedure Get_Transitions
107	(State_ID : in     Parse_State;
108	 Kind     : in     Transition_Type;
109	 Set_1    : in out Transition_Set);
110
111    procedure Get_Transition_Symbols
112	(State_ID : in     Parse_State;
113	 Kind     : in     Transition_Type;
114	 Set_1    : in out Grammar_Symbol_Set);
115
116    procedure Get_Kernel
117	(State_ID : in     Parse_State;
118	 Set_1    : in out Item_Set);
119
120    procedure Closure (Set_1 : in out Item_Set);
121
122
123
124    --
125    --  The following routines allow the user to iterate over the
126    --  items in the kernel of a particular state.
127    --
128
129    type Kernel_Iterator is limited private;
130    procedure Initialize
131            (Iterator : in out Kernel_Iterator;
132	     State_ID : in Parse_State);
133
134    function  More(Iterator : Kernel_Iterator) return Boolean;
135    procedure Next(Iterator : in out Kernel_Iterator; I : out Item);
136
137
138    --
139    --  The following routines allow the user to iterate over the
140    --  nonterminal transitions of a particular state
141    --
142    type Nt_Transition_Iterator is limited private;
143    procedure Initialize
144	(Iterator : in out Nt_Transition_Iterator;
145	 State_ID : in Parse_State);
146
147    function  More (Iterator : Nt_Transition_Iterator) return Boolean;
148    procedure Next
149	(Iterator : in out Nt_Transition_Iterator;
150	 Trans : out Transition);
151
152
153    -- The following routines allow iteration over the Terminal transitions
154    -- of a particular state.
155
156    type T_Transition_Iterator is limited private;  -- For Terminals
157    procedure Initialize
158	(Iterator : in out T_Transition_Iterator;
159	 State_ID : in Parse_State);
160
161    function  More (Iterator : T_Transition_Iterator) return Boolean;
162    procedure Next
163	(Iterator : in out T_Transition_Iterator;
164	 Trans : out Transition);
165
166
167
168    To_Many_States      : exception;
169    No_More_Iterations  : exception;
170    State_Out_of_Bounds : exception;
171
172--RJS    pragma inline(more); --DEC Ada Bug: , next);
173
174private
175
176    type Item_Array_Index is range 0..5_000; -- An arbitrarily big number
177    type Item_Array;
178    type Item_Array_Pointer is access Item_Array;
179    type Kernel_Iterator is
180	record
181	    Kernel  : Item_Array_Pointer;
182	    Curser  : Item_Array_Index;
183	end record;
184
185
186    type Transition_Array;
187    type Transition_Array_Pointer is access Transition_Array;
188    type Nt_Transition_Iterator is
189	record
190	    Nonterm_Trans : Transition_Array_Pointer;
191	    Curser        : Integer;  -- Use a derived type instead ???
192	end record;
193
194    type T_Transition_Iterator is
195	record
196	    Term_Trans  : Transition_Array_Pointer;
197	    Curser      : Integer;
198	end record;
199
200end LR0_Machine;
201