Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | (* ML-Yacc Parser Generator (c) 1989 Andrew W. Appel, David R. Tarditi *) |
2 | ||
3 | (* base.sig: Base signature file for SML-Yacc. This file contains signatures | |
4 | that must be loaded before any of the files produced by ML-Yacc are loaded | |
5 | *) | |
6 | ||
7 | (* STREAM: signature for a lazy stream.*) | |
8 | ||
9 | signature STREAM = | |
10 | sig type 'xa stream | |
11 | val streamify : (unit -> '_a) -> '_a stream | |
12 | val cons : '_a * '_a stream -> '_a stream | |
13 | val get : '_a stream -> '_a * '_a stream | |
14 | end | |
15 | ||
16 | (* LR_TABLE: signature for an LR Table. | |
17 | ||
18 | The list of actions and gotos passed to mkLrTable must be ordered by state | |
19 | number. The values for state 0 are the first in the list, the values for | |
20 | state 1 are next, etc. | |
21 | *) | |
22 | ||
23 | signature LR_TABLE = | |
24 | sig | |
25 | datatype ('a,'b) pairlist = EMPTY | PAIR of 'a * 'b * ('a,'b) pairlist | |
26 | datatype state = STATE of int | |
27 | datatype term = T of int | |
28 | datatype nonterm = NT of int | |
29 | datatype action = SHIFT of state | |
30 | | REDUCE of int | |
31 | | ACCEPT | |
32 | | ERROR | |
33 | type table | |
34 | ||
35 | val numStates : table -> int | |
36 | val numRules : table -> int | |
37 | val describeActions : table -> state -> | |
38 | (term,action) pairlist * action | |
39 | val describeGoto : table -> state -> (nonterm,state) pairlist | |
40 | val action : table -> state * term -> action | |
41 | val goto : table -> state * nonterm -> state | |
42 | val initialState : table -> state | |
43 | exception Goto of state * nonterm | |
44 | ||
45 | val mkLrTable : {actions : ((term,action) pairlist * action) array, | |
46 | gotos : (nonterm,state) pairlist array, | |
47 | numStates : int, numRules : int, | |
48 | initialState : state} -> table | |
49 | end | |
50 | ||
51 | (* TOKEN: signature revealing the internal structure of a token. This signature | |
52 | TOKEN distinct from the signature {parser name}_TOKENS produced by ML-Yacc. | |
53 | The {parser name}_TOKENS structures contain some types and functions to | |
54 | construct tokens from values and positions. | |
55 | ||
56 | The representation of token was very carefully chosen here to allow the | |
57 | polymorphic parser to work without knowing the types of semantic values | |
58 | or line numbers. | |
59 | ||
60 | This has had an impact on the TOKENS structure produced by SML-Yacc, which | |
61 | is a structure parameter to lexer functors. We would like to have some | |
62 | type 'a token which functions to construct tokens would create. A | |
63 | constructor function for a integer token might be | |
64 | ||
65 | INT: int * 'a * 'a -> 'a token. | |
66 | ||
67 | This is not possible because we need to have tokens with the representation | |
68 | given below for the polymorphic parser. | |
69 | ||
70 | Thus our constructur functions for tokens have the form: | |
71 | ||
72 | INT: int * 'a * 'a -> (svalue,'a) token | |
73 | ||
74 | This in turn has had an impact on the signature that lexers for SML-Yacc | |
75 | must match and the types that a user must declare in the user declarations | |
76 | section of lexers. | |
77 | *) | |
78 | ||
79 | signature TOKEN = | |
80 | sig | |
81 | structure LrTable : LR_TABLE | |
82 | datatype ('a,'b) token = TOKEN of LrTable.term * ('a * 'b * 'b) | |
83 | val sameToken : ('a,'b) token * ('a,'b) token -> bool | |
84 | end | |
85 | ||
86 | (* LR_PARSER: signature for a polymorphic LR parser *) | |
87 | ||
88 | signature LR_PARSER = | |
89 | sig | |
90 | structure Stream: STREAM | |
91 | structure LrTable : LR_TABLE | |
92 | structure Token : TOKEN | |
93 | ||
94 | sharing LrTable = Token.LrTable | |
95 | ||
96 | exception ParseError | |
97 | ||
98 | val parse : {table : LrTable.table, | |
99 | lexer : ('_b,'_c) Token.token Stream.stream, | |
100 | arg: 'arg, | |
101 | saction : int * | |
102 | '_c * | |
103 | (LrTable.state * ('_b * '_c * '_c)) list * | |
104 | 'arg -> | |
105 | LrTable.nonterm * | |
106 | ('_b * '_c * '_c) * | |
107 | ((LrTable.state *('_b * '_c * '_c)) list), | |
108 | void : '_b, | |
109 | ec : { is_keyword : LrTable.term -> bool, | |
110 | noShift : LrTable.term -> bool, | |
111 | preferred_change : (LrTable.term list * LrTable.term list) list, | |
112 | errtermvalue : LrTable.term -> '_b, | |
113 | showTerminal : LrTable.term -> string, | |
114 | terms: LrTable.term list, | |
115 | error : string * '_c * '_c -> unit | |
116 | }, | |
117 | lookahead : int (* max amount of lookahead used in *) | |
118 | (* error correction *) | |
119 | } -> '_b * | |
120 | (('_b,'_c) Token.token Stream.stream) | |
121 | end | |
122 | ||
123 | (* LEXER: a signature that most lexers produced for use with SML-Yacc's | |
124 | output will match. The user is responsible for declaring type token, | |
125 | type pos, and type svalue in the UserDeclarations section of a lexer. | |
126 | ||
127 | Note that type token is abstract in the lexer. This allows SML-Yacc to | |
128 | create a TOKENS signature for use with lexers produced by ML-Lex that | |
129 | treats the type token abstractly. Lexers that are functors parametrized by | |
130 | a Tokens structure matching a TOKENS signature cannot examine the structure | |
131 | of tokens. | |
132 | *) | |
133 | ||
134 | signature LEXER = | |
135 | sig | |
136 | structure UserDeclarations : | |
137 | sig | |
138 | type ('a,'b) token | |
139 | type pos | |
140 | type svalue | |
141 | end | |
142 | val makeLexer : (int -> string) -> unit -> | |
143 | (UserDeclarations.svalue,UserDeclarations.pos) UserDeclarations.token | |
144 | end | |
145 | ||
146 | (* ARG_LEXER: the %arg option of ML-Lex allows users to produce lexers which | |
147 | also take an argument before yielding a function from unit to a token | |
148 | *) | |
149 | ||
150 | signature ARG_LEXER = | |
151 | sig | |
152 | structure UserDeclarations : | |
153 | sig | |
154 | type ('a,'b) token | |
155 | type pos | |
156 | type svalue | |
157 | type arg | |
158 | end | |
159 | val makeLexer : (int -> string) -> UserDeclarations.arg -> unit -> | |
160 | (UserDeclarations.svalue,UserDeclarations.pos) UserDeclarations.token | |
161 | end | |
162 | ||
163 | (* PARSER_DATA: the signature of ParserData structures in {parser name}LrValsFun | |
164 | produced by SML-Yacc. All such structures match this signature. | |
165 | ||
166 | The {parser name}LrValsFun produces a structure which contains all the values | |
167 | except for the lexer needed to call the polymorphic parser mentioned | |
168 | before. | |
169 | ||
170 | *) | |
171 | ||
172 | signature PARSER_DATA = | |
173 | sig | |
174 | (* the type of line numbers *) | |
175 | ||
176 | type pos | |
177 | ||
178 | (* the type of semantic values *) | |
179 | ||
180 | type svalue | |
181 | ||
182 | (* the type of the user-supplied argument to the parser *) | |
183 | type arg | |
184 | ||
185 | (* the intended type of the result of the parser. This value is | |
186 | produced by applying extract from the structure Actions to the | |
187 | final semantic value resultiing from a parse. | |
188 | *) | |
189 | ||
190 | type result | |
191 | ||
192 | structure LrTable : LR_TABLE | |
193 | structure Token : TOKEN | |
194 | sharing Token.LrTable = LrTable | |
195 | ||
196 | (* structure Actions contains the functions which mantain the | |
197 | semantic values stack in the parser. Void is used to provide | |
198 | a default value for the semantic stack. | |
199 | *) | |
200 | ||
201 | structure Actions : | |
202 | sig | |
203 | val actions : int * pos * | |
204 | (LrTable.state * (svalue * pos * pos)) list * arg-> | |
205 | LrTable.nonterm * (svalue * pos * pos) * | |
206 | ((LrTable.state *(svalue * pos * pos)) list) | |
207 | val void : svalue | |
208 | val extract : svalue -> result | |
209 | end | |
210 | ||
211 | (* structure EC contains information used to improve error | |
212 | recovery in an error-correcting parser *) | |
213 | ||
214 | structure EC : | |
215 | sig | |
216 | val is_keyword : LrTable.term -> bool | |
217 | val noShift : LrTable.term -> bool | |
218 | val preferred_change : (LrTable.term list * LrTable.term list) list | |
219 | val errtermvalue : LrTable.term -> svalue | |
220 | val showTerminal : LrTable.term -> string | |
221 | val terms: LrTable.term list | |
222 | end | |
223 | ||
224 | (* table is the LR table for the parser *) | |
225 | ||
226 | val table : LrTable.table | |
227 | end | |
228 | ||
229 | (* signature PARSER is the signature that most user parsers created by | |
230 | SML-Yacc will match. | |
231 | *) | |
232 | ||
233 | signature PARSER = | |
234 | sig | |
235 | structure Token : TOKEN | |
236 | structure Stream : STREAM | |
237 | exception ParseError | |
238 | ||
239 | (* type pos is the type of line numbers *) | |
240 | ||
241 | type pos | |
242 | ||
243 | (* type result is the type of the result from the parser *) | |
244 | ||
245 | type result | |
246 | ||
247 | (* the type of the user-supplied argument to the parser *) | |
248 | type arg | |
249 | ||
250 | (* type svalue is the type of semantic values for the semantic value | |
251 | stack | |
252 | *) | |
253 | ||
254 | type svalue | |
255 | ||
256 | (* val makeLexer is used to create a stream of tokens for the parser *) | |
257 | ||
258 | val makeLexer : (int -> string) -> | |
259 | (svalue,pos) Token.token Stream.stream | |
260 | ||
261 | (* val parse takes a stream of tokens and a function to print | |
262 | errors and returns a value of type result and a stream containing | |
263 | the unused tokens | |
264 | *) | |
265 | ||
266 | val parse : int * ((svalue,pos) Token.token Stream.stream) * | |
267 | (string * pos * pos -> unit) * arg -> | |
268 | result * (svalue,pos) Token.token Stream.stream | |
269 | ||
270 | val sameToken : (svalue,pos) Token.token * (svalue,pos) Token.token -> | |
271 | bool | |
272 | end | |
273 | ||
274 | (* signature ARG_PARSER is the signature that will be matched by parsers whose | |
275 | lexer takes an additional argument. | |
276 | *) | |
277 | ||
278 | signature ARG_PARSER = | |
279 | sig | |
280 | structure Token : TOKEN | |
281 | structure Stream : STREAM | |
282 | exception ParseError | |
283 | ||
284 | type arg | |
285 | type lexarg | |
286 | type pos | |
287 | type result | |
288 | type svalue | |
289 | ||
290 | val makeLexer : (int -> string) -> lexarg -> | |
291 | (svalue,pos) Token.token Stream.stream | |
292 | val parse : int * ((svalue,pos) Token.token Stream.stream) * | |
293 | (string * pos * pos -> unit) * arg -> | |
294 | result * (svalue,pos) Token.token Stream.stream | |
295 | ||
296 | val sameToken : (svalue,pos) Token.token * (svalue,pos) Token.token -> | |
297 | bool | |
298 | end |