Debian Codegraph @

ipl/packs/ibpag2/ibreader.icn

raw
1 ############################################################################
2 #
3 # Name: ibreader.icn
4 #
5 # Title: reader for Ibpag2 source files
6 #
7 # Author: Richard L. Goerwitz
8 #
9 # Version: 1.29
10 #
11 ############################################################################
12 #
13 # This file contains a collection of procedures that 1) read in an
14 # Ibpag2 source file, 2) output token defines, 3) emit action code,
15 # and finally 4) pass a start symbol, list of productions, and token
16 # table back to the calling procedure. Described formally:
17 #
18 # ibreader: file x file x string -> ib_grammar record
19 # (in, out, module) -> grammar
20 #
21 # In is the input stream; out is the output stream; module is an
22 # optional string that distinguishes this grammar from others that
23 # might also be running simultaneously. Grammar is an ib_grammar
24 # record containing the start symbol in its first field and the
25 # production list in its second. Its third field contains a table
26 # used to map integers to actual token names or character literals,
27 # i.e. its keys are things like -1, 0, etc. and its values are things
28 # like "error," "EOF," etc.
29 #
30 # Note that if a module argument is supplied to ibreader(), one must
31 # also be supplied to ibwriter(). See ibwriter.icn.
32 #
33 # The format of the input file is highly reminiscent of YACC. It
34 # consists of three basic sections, the first two of which are
35 # followed by %%. See the main documentation to Ibpag2 for
36 # specifics. Major differences between Ibpag2 and YACC input format
37 # include:
38 #
39 # 1) "$$ = x" constructs are replaced by "return x" (e.g. "$$ =
40 # $1 + $3" -> "return $1 + $3")
41 #
42 # 2) all variables within a given action are, by default, local
43 # to that action; i.e. they cannot be accessed by other
44 # actions unless you declare them global elsewhere (e.g. in
45 # the pass-through part of the declarations section %{ ... %})
46 #
47 # 3) the %union declaration is not needed by Ibpag
48 #
49 # 4) tokens and symbols are separated from each other by a comma
50 # (e.g. %token '+', '-' and S : NP, VP)
51 #
52 # 5) epsilon is indicated by the keyword "epsilon" (e.g. REL :
53 # epsilon)
54 #
55 # 6) both epsilon and error *may* be declared as %tokens for
56 # reasons of precedence, although they retain hard-coded
57 # internal values (-2 and -1, respectively)
58 #
59 # 7) all actions must follow the last RHS symbol of the rule they
60 # apply to (preceded by an optional %prec directive); to
61 # achieve S : NP { action1 }, VP { action2 }, insert a dummy
62 # rule: S : NP, dummy, VP { action2 }; dummy : epsilon {
63 # action1 } ;
64 #
65 # 8) YYERROR, YYACCEPT, yyclearin, and yyerrok are the same,
66 # except they are written IIERROR, IIACCEPT, iiclearin, and
67 # iierrok (i.e. "ii" replaces "yy")
68 #
69 # 9) Ibpag2's input files are tokenized like modified Icon files,
70 # and, as a consequence, Icon's reserved words must not be
71 # used as symbols (e.g. "if : if, then" is no go)
72 #
73 ############################################################################
74 #
75 # Links: itokens, escape
76 #
77 # See also: ibwriter
78 #
79 ############################################################################
80
81 #link itokens, escape
82 link escape
83
84 record ib_grammar(start, rules, tbl)
85 record tokstats(str, no, prec, assoc)
86
87 # Declared in itokens.icn:
88 # global line_number
89
90 #
91 # ibreader: file x file x string x string -> ib_grammar record
92 # (in, out, module, source_fname) -> grammar
93 #
94 # Where in is an input stream, out is an output stream, module is
95 # some string uniquely identifying this module (optional), and
96 # where grammar is an ib_grammar record containing the start
97 # symbol in its first field and a list of production records in
98 # its second. Source_fname is the string name of Ibpag2's input
99 # grammar file. Defaults to "source file."
100 #
101 procedure ibreader(in, out, module, source_fname)
102
103 local tmp, grammar, toktbl, next_token, next_token_no_nl,
104 token, LHS, t
105
106 /source_fname := "source file"
107 grammar := ib_grammar(&null, list(), table())
108 toktbl := table()
109 next_token := create itokens(in, 1)
110 next_token_no_nl := create 1(tmp := |@next_token, \tmp.sym)
111 token := @next_token_no_nl | iohno(4)
112
113 # Do the %{ $} and %token stuff, i.e. everything up to %%
114 # (NEWSECT).
115 #
116 until token.sym == "NEWSECT" do {
117 case token.sym of {
118 default : {
119 iohno(48, "token "||image(token.str) ||"; line "|| line_number)
120 }
121 "SEMICOL" : {
122 # Skip semicolon. Get another token while we're at it.
123 token := @next_token_no_nl | iohno(47, "line "||line_number)
124 }
125 "BEGGLOB" : {
126 write(out, "\n$line ", line_number, " ", image(source_fname))
127 # Copy token values to out until we reach "%}" (ENDGLOB).
128 (token := copy_icon_stuff(next_token, out)).sym == "ENDGLOB"
129 token := @next_token_no_nl
130 }
131 "MOD" : {
132 (token := @next_token_no_nl).sym == "IDENT" |
133 iohno(30, "line " || line_number)
134 #
135 # Read in token declarations, set associativity and
136 # precedences, and enter the tokens into toktbl.
137 #
138 token := {
139 case token.str of {
140 default : iohno(30, "line " || line_number)
141 "token" : read_decl(next_token_no_nl, toktbl, &null)
142 "right" : read_decl(next_token_no_nl, toktbl, "r")
143 "left" : read_decl(next_token_no_nl, toktbl, "l")
144 "nonassoc": read_decl(next_token_no_nl, toktbl, "n")
145 "union" : iohno(45, "line "|| line_number)
146 "start" : {
147 (token := @next_token_no_nl).sym == "IDENT" |
148 iohno(31, "line " || line_number)
149 /grammar.start := token.str |
150 iohno(32, "line " || line_number)
151 @next_token_no_nl | iohno(4)
152 }
153 }
154 }
155 }
156 }
157 }
158 # Skip past %% (NEWSECT) and semicolon (if present).
159 token := @next_token_no_nl | iohno(47, "line "|| line_number)
160 (token := token | @next_token_no_nl | iohno(4)).sym ~== "SEMICOL"
161 token.sym == "NEWSECT" & iohno(47, "line "|| line_number)
162
163 #
164 # Fetch start symbol if it wasn't defined above via %start; by
165 # default the start symbol is the LHS of rule 1.
166 #
167 /grammar.start := token.str
168
169 # Having reached the end of the declarations section, we can now
170 # copy out a define for each token number, not counting character
171 # literals (which are stored as integers). While we're at it,
172 # create a table that maps token numbers back to character
173 # literals and strings (for use in later verbose and debugging
174 # displays).
175 #
176 write(out, "\n")
177 every t := !toktbl do {
178 if type(t.str) == "integer" then
179 insert(grammar.tbl, t.no, image(char(t.str)))
180 else {
181 insert(grammar.tbl, t.no, t.str)
182 write(out, "$define ", t.str, "\t", t.no)
183 }
184 }
185
186 # Now, finally, read in rules up until we reach EOF or %% (i.e.
187 # NEWSECT). EOF is signaled below by failure of read_RHS().
188 #
189 until token.sym == "NEWSECT" do {
190 token.sym == "IDENT" | iohno(33, token.str ||" line "|| line_number)
191 LHS := token.str
192 token := @next_token_no_nl | iohno(4)
193 token.sym == "COLON" | iohno(34, token.str ||" line "|| line_number)
194 #
195 # Read in RHS, then the action (if any) then the prec (if
196 # any). If we see a BAR, then repeat, re-using the same
197 # left-hand side symbol.
198 #
199 while token :=
200 read_RHS(next_token, next_token_no_nl, out, toktbl, LHS,
201 grammar, module, source_fname) |
202 # if read_RHS fails, we're at EOF
203 break break
204 do token.sym == "BAR" | break
205 }
206
207 # Copy the remainder of the file to out as Icon code.
208 write(out, "\n$line ", line_number, " ", image(source_fname))
209 every copy_icon_stuff(next_token, out, "EOFX")
210
211 # Do final setup on the reverse token table. This table will be
212 # used later to map integers to their original names in verbose or
213 # debugging displays.
214 #
215 insert(grammar.tbl, 0, "$")
216
217 return grammar
218
219 end
220
221
222 #
223 # copy_icon_stuff: coexpression x file x string -> ib_TOK records
224 # (next_token, out, except) -> token records
225 #
226 # Copy Icon code to output stream, also suspending as we go.
227 # Insert separators between tokens where needed. Do not output
228 # any token whose sym field matches except. The point in
229 # suspending tokens as we go is to enable the calling procedure to
230 # look for signal tokens that indicate insertion or termination
231 # points.
232 #
233 procedure copy_icon_stuff(next_token, out, except)
234
235 local separator, T
236
237 separator := ""
238 while T := @next_token do {
239 if \T.sym then suspend T
240 if \T.sym == \except then next
241 if any(&digits ++ &letters ++ '_.', \T.str, 1, 2) & \T.sym ~== "DOT"
242 then writes(out, separator)
243 writes(out, T.str)
244 if any(&digits ++ &letters ++ '_.', \T.str, -1, 0) & \T.sym ~== "DOT"
245 then separator := " " else separator := ""
246 }
247
248 # unexpected EOF error
249 (except === "EOFX") | iohno(4)
250
251 end
252
253
254 #
255 # read_decl: coexpression x table x string -> ib_TOK
256 # (next_token_no_nl, toktbl, assoc) -> token
257 #
258 # Read in token declarations, assigning them the correct
259 # precedence and associativity. Number the tokens for later
260 # $define preprocessor directives. When done, return the last
261 # token processed. Toktbl is the table that holds the stats for
262 # each declared token.
263 #
264 procedure read_decl(next_token_no_nl, toktbl, assoc)
265
266 local token, c
267 static token_no, prec
268 initial {
269 token_no := 256
270 prec := 0
271 }
272
273 # All tokens in this list have the same prec and assoc.
274 # Precedence is determined by order. Associativity is determined
275 # by keyword in the calling procedure, and is passed as arg 3.
276 #
277 prec +:= 1
278 assoc === ("n"|"r"|"l"|&null) | iohno(5, image(assoc))
279
280 # As long as we find commas and token names, keep on adding tokens
281 # to the token table. Return the unused token when done. If we
282 # reach EOF, there's been an error.
283 #
284 repeat {
285 token := @next_token_no_nl | iohno(4)
286 case token.sym of {
287 default : iohno(31, token.str ||" line "|| line_number)
288 "CSETLIT" | "STRING": {
289 # Enter character literals as integers.
290 *escape(token.str[2:-1]) = 1 | iohno(49, token.str)
291 c := ord(escape(token.str[2:-1]))
292 toktbl[c] := tokstats(c, c, prec, assoc)
293 }
294 "IDENT" : {
295 case token.str of {
296 "error" :
297 toktbl[token.str] := tokstats("error", -1, prec, assoc)
298 "epsilon":
299 toktbl[token.str] := tokstats("epsilon",-2,prec, assoc)
300 default : {
301 # Enter TOKENs as string-keyed records in toktbl.
302 token_no +:= 1
303 toktbl[token.str] :=
304 tokstats(token.str, token_no, prec, assoc)
305 }
306 }
307 }
308 }
309 # As long as we're seeing commas, go back for more tokens.
310 token := @next_token_no_nl | iohno(4)
311 token.sym == "COMMA" | break
312 }
313
314 # Skip past semicolon, if present (as set up now, it shouldn't be).
315 (token := token | @next_token_no_nl | iohno(4)).sym ~== "SEMICOL"
316 return token
317
318 end
319
320
321 #
322 # read_RHS: coexpression x coexpression x file x table x
323 # string x ib_grammar record x string x string -> token
324 #
325 # Read_RHS goes through the RHS of rule definitions, inserting the
326 # resulting productions into a master rule list. At the same
327 # time, it outputs the actions corresponding to those productions
328 # as procedures that are given names corresponding to the numbers
329 # of the productions. I.e. production 1, if endowed with an {
330 # action }, will correspond to procedure _1_. Prec and assoc are
331 # automatically set to that of the last RHS nonterminal, but this
332 # may be changed explicitly by the %prec keyword, as in YACC.
333 # Source_fname is the name of the source grammar file we're pro-
334 # cessing (caller will give us some reasonable default if we're
335 # reading &input).
336 #
337 # Fails on EOF.
338 #
339 procedure read_RHS(next_token, next_token_no_nl, out, toktbl, LHS,
340 grammar, module, source_fname)
341
342 local token, rule, c
343 static rule_no
344 initial rule_no := 0
345
346 rule_no +:= 1
347 # LHS RHS POS LOOK no prec assoc
348 rule := production(LHS, list(), &null, &null, rule_no, &null, &null)
349 put(grammar.rules, rule)
350
351 # Read in RHS symbols.
352 #
353 repeat {
354 token := @next_token_no_nl | iohno(4)
355 case token.sym of {
356 default :
357 iohno(35, "token "|| image(token.str)||"; line "|| line_number)
358 "CSETLIT" | "STRING": {
359 *escape(token.str[2:-1]) = 1 | iohno(49, token.str)
360 c := ord(escape(token.str[2:-1]))
361 if \toktbl[c] then {
362 rule.prec := toktbl[c].prec
363 rule.assoc := toktbl[c].assoc
364 }
365 # literals not declared earlier will get caught here
366 else insert(grammar.tbl, c, image(char(c)))
367 put(rule.RHS, c)
368 }
369 "IDENT" : {
370 # If it's a terminal (i.e. a declared token), assign
371 # this rule its precedence and associativity. If it's
372 # not in toktbl, then it's not a declared token....
373 if \toktbl[token.str] then {
374 rule.prec := toktbl[token.str].prec
375 rule.assoc := toktbl[token.str].assoc
376 put(rule.RHS, toktbl[token.str].no)
377 if toktbl[token.str].no = -2 then {
378 *rule.RHS > 1 & iohno(44, "line ", line_number)
379 rule.POS := 2
380 }
381 }
382 # ...undeclared stuff. Could be a nonterminal. If
383 # error and/or epsilon weren't declared as tokens,
384 # they will get caught here, too.
385 else {
386 case token.str of {
387 &null : stop("What is going on here?")
388 default : put(rule.RHS, token.str)
389 "error" : {
390 put(rule.RHS, -1)
391 insert(grammar.tbl, -1, "error")
392 }
393 "epsilon" : {
394 if *put(rule.RHS, -2) > 1
395 then iohno(44, "line ", line_number)
396 else rule.POS := 2
397 insert(grammar.tbl, -2, "epsilon")
398 }
399 }
400 }
401 }
402 }
403 # Comma means: Go back for another RHS symbol.
404 token := @next_token_no_nl | fail
405 token.sym == "COMMA" | break
406 }
407
408 # Skip semicolon token, if present.
409 (token := token | @next_token_no_nl | fail).sym ~== "SEMICOL"
410
411 # Read and set (optional) precedence.
412 #
413 if token.sym == "MOD" then {
414 token := @next_token_no_nl | iohno(4)
415 (token.sym == "IDENT" & token.str == "prec") |
416 iohno(43, token.str || " line " || line_number)
417 token := @next_token_no_nl | iohno(4)
418 case token.sym of {
419 "CSETLIT" | "STRING" : {
420 *escape(token.str[2:-1]) = 1 | iohno(49, token.str)
421 c := ord(escape(token.str[2:-1])) &
422 rule.prec := toktbl[c].prec &
423 rule.assoc := toktbl[c].assoc
424 }
425 "IDENT" : {
426 \toktbl[token.str] |
427 iohno(43, token.str || " line " || line_number)
428 rule.prec := toktbl[token.str].prec &
429 rule.assoc := toktbl[token.str].assoc
430 }
431 default : 1 = 4 # deliberate failure
432 } | iohno(43, "line ", line_number)
433 token := @next_token_no_nl | fail
434 }
435
436 # Skip semicolon token, if present.
437 (token := token | @next_token_no_nl | fail).sym ~== "SEMICOL"
438
439 # Read in (optional) action.
440 #
441 if token.sym == "LBRACE" then {
442 write_action_as_procedure(next_token, out, rule,
443 module, source_fname)
444 token := @next_token_no_nl | fail
445 }
446
447 # Skip semicolon token, if present.
448 (token := token | @next_token_no_nl | fail).sym ~== "SEMICOL"
449 return token
450
451 end
452
453
454 #
455 # write_action_as_procedure
456 #
457 procedure write_action_as_procedure(next_token, out, rule,
458 module, source_fname)
459
460 local argstr, bracelevel, token, i, neg
461
462 /module := ""
463 argstr := ""
464 #
465 # Decide the number of arguments based on the length of the RHS of
466 # rule. Exception: Epsilon productions are empty, and pop nothing
467 # off the stack, so take zero args.
468 #
469 if rule.RHS[1] ~=== -2 then {
470 every argstr ||:= "arg" || (1 to *rule.RHS) || ","
471 argstr := trim(argstr, ',')
472 }
473 write(out, "procedure _", rule.no, "_", module, "(", argstr, ")")
474 write(out, "\n$line ", line_number, " ", image(source_fname))
475
476 bracelevel := 1
477 until bracelevel = 0 do {
478 every token := copy_icon_stuff(next_token, out, "RHSARG") do {
479 case token.sym of {
480 default : next
481 "LBRACE" : bracelevel +:= 1
482 "RBRACE" : bracelevel -:= 1
483 "RHSARG" : {
484 until \ (token := @next_token).sym do
485 writes(out, token.str)
486 if neg := (token.sym == "MINUS") then
487 until \ (token := @next_token).sym do
488 writes(out, token.str)
489 else neg := &null
490 token.sym == "INTLIT" | iohno(37, "$"||token.str)
491 if /neg & token.str ~== "0" then {
492 token.str <= *rule.RHS | iohno(38, "$"||token.str)
493 writes(out, " arg", token.str, " ")
494 } else {
495 # Code for $0, $-1, etc.
496 #
497 # Warning! If the name of the stack is changed
498 # in iiparse.lib, it has to be changed here, too.
499 #
500 i := abs(token.str)+1
501 writes(out, " value_stack", module, "[", i, "] ")
502 }
503 }
504 }
505 if bracelevel = 0 then {
506 write(out, "\nend\n")
507 return token
508 }
509 }
510 }
511
512 iohno(39, "line "|| line_number)
513
514 end
515