Debian Codegraph @

ipl/packs/tcll1/gramanal.icn

raw
1 # GRAMANAL.ICN
2 #
3 # LL(1)/LL(k) parser generator in Icon
4 # written by Dr. Thomas W. Christopher
5 #
6 # generally useful grammar analysis routines
7
8 # symbId is a string
9
10 record Symbol(
11 name, # symbId
12 kind, # string in
13 # { "Nonterminal","Terminal","ActionSymbol"}
14 minLeng)# integer, length of shortest terminal string
15 # that can be derived from this nonterminal
16 record Production(
17 lhs, # Symbol, left hand side
18 rhs, # [ Symbol, ... ], right hand side
19 minLeng) # minimum length of terminal string derivable from
20 # lhs using this production
21
22 global symbol #table:symbId->Symbol
23 global first #table:Symbol->set(Symbol)
24 global last #table:Symbol->set(Symbol)
25 global follow #table:Symbol->set(Symbol)
26 global productions #table:Symbol->[Production,...]
27 global selectionSet #table:Production->Set(Symbol)
28 # set of symbols that choose this production
29 # if lhs is atop the stack
30 global nonterminals #set(Symbol)
31 global terminals #set(Symbol)
32 global actions #set(Symbol)
33 global startSymbol #Symbol
34 global eoiSymbol #Symbol, end of input
35 global errorFile #file
36 global errorCount #integer
37 global warningCount #integer
38 global tooLong #integer, too long for a sentence
39 global defaultStartName #string, default name of start symbol
40
41 #######################################################################
42 #
43 # calls to create grammars
44 #
45
46 procedure initGrammar(out)
47 symbol := table()
48 first := table()
49 last := table()
50 follow := table()
51 productions := table()
52 selectionSet := table()
53 nonterminals := set()
54 terminals := set()
55 actions := set()
56 fiducials := set()
57 startSymbol := &null
58 eoiSymbol := Symbol("EOI","Terminal")
59 symbol["EOI"] := eoiSymbol
60 errorFile := \out | &output
61 errorCount := warningCount := 0
62 tooLong := 10000
63 defaultStartName := "start"
64 return
65 end
66
67 procedure error(e[])
68 errorCount +:= 1
69 writes(errorFile,"Error: ")
70 every writes(!e)
71 write()
72 end
73
74 procedure warning(e[])
75 warningCount +:= 1
76 writes(errorFile,"Warning: ")
77 every writes(!e)
78 write()
79 end
80
81 procedure declareProduction(lhs,rhs)
82 # lhs: symbId
83 # rhs: [symbId,...]
84 local n, #Symbol, the left hand side
85 r, #[Symbol,...], the right hand side
86 s #symbId, name of rhs element
87 if /symbol[lhs] then {
88 n := symbol[lhs] := Symbol(lhs,"Nonterminal")
89 insert(nonterminals,n)
90 } else {
91 n := symbol[lhs]
92 /n.kind := "Nonterminal"
93 if n.kind ~==="Nonterminal" then {
94 error(lhs||" is both nonterminal and "||n.kind)
95 fail
96 }
97 }
98 r := []
99 every s := !rhs do {
100 /symbol[s] := Symbol(s)
101 put(r,symbol[s])
102 }
103 /productions[n] := []
104 put(productions[n],Production(n,r))
105 return
106 end
107
108 procedure declareAction(s)
109 local t
110 /symbol[s] := Symbol(s)
111 t := symbol[s]
112 /t.kind := "ActionSymbol"
113 if t.kind ~== "ActionSymbol" then {
114 error(t.kind||" "||s||" being declared an ActionSymbol")
115 fail
116 }
117 insert(actions,t)
118 return
119 end
120
121 procedure declareStartSymbol(s)
122 local n
123 if \startSymbol then {
124 error(
125 "attempt to redeclare start symbol from "||
126 startSymbol.name||
127 " to "||
128 s)
129 fail
130 }
131 if n := \symbol[s] then {
132 /n.kind := "Nonterminal"
133 if n.kind ~== "Nonterminal" then {
134 error( "attempt to declare " ||
135 n.kind || " " ||
136 s || " as start symbol")
137 fail
138 }
139 startSymbol := n
140 return
141 }
142 startSymbol := Symbol(s,"Nonterminal")
143 symbol[s] := startSymbol
144 insert(nonterminals,startSymbol)
145 /productions[startSymbol] := []
146 return
147 end
148
149 procedure declareEOI(s)
150 local eoi
151 if eoiSymbol.name == s then return
152 if \symbol[s] then {
153 error(
154 "attempt to redeclare "||
155 symbol[s].kind||" "||
156 s||" as EOI symbol")
157 fail
158 }
159 remove(symbol,eoiSymbol.name)
160 eoiSymbol.name := s
161 symbol[s] := eoiSymbol
162 return
163 end
164
165 procedure finishDeclarations()
166 local s #Symbol
167
168 insert(terminals,eoiSymbol)
169
170 #what if no start symbol specified? Create one.
171 if /startSymbol then {
172 declareStartSymbol(defaultStartName)
173 }
174
175 every s := !symbol do
176 case s.kind of {
177 &null : {
178 s.kind := "Terminal"
179 insert(terminals,s)
180 s.minLeng := 1
181 }
182 "Terminal": {
183 s.minLeng := 1
184 insert(terminals,s)
185 }
186 "ActionSymbol": {
187 s.minLeng := 0
188 insert(actions,s)
189 }
190 "Nonterminal": {
191 s.minLeng := tooLong
192 insert(nonterminals,s)
193 }
194 }
195 return
196 end
197
198 #######################################################################
199 #
200 # local utility procedures
201 #
202
203 # succeed returning s if s is a null-deriving symbol
204 # (only valid after execution of findMinLeng() )
205 #
206 procedure isNullDeriving(s)
207 if s.minLeng <= 0 then return s else fail
208 end
209
210 # succeed returning symbol s only if s is the specified type of symbol
211 procedure isNonterminal(s)
212 return member(nonterminals,s) #returning s
213 end
214
215 procedure isTerminal(s)
216 return member(terminals,s) #returning s
217 end
218
219 procedure isActionSymbol(s)
220 return member(actions,s) #returning s
221 end
222
223 #######################################################################
224 #
225 #debugging & output routines
226 #
227
228 procedure writeIndented(s,i,l,b)
229 # write string s, indenting by i positions any overflow lines,
230 # breaking after characters in set b (if practical), with overall
231 # line length l
232 #
233 local j,k,r,h
234 /l := 72 #default line length
235 /i := 8 #default indent
236 if /b := ' \t' #default break set--white space
237 then l+:=1
238 r := l - i #remaining length after indent
239 if r <= 1 then fail
240 #cut off initial i chars (or all of string if it's short):
241 s ?:= (h := tab(i+1 | 0) & tab(0))
242 repeat {
243 # find a position j at which to cut the line:
244 j := -1
245 if *s>r then {s ? every k := upto(b) & k <= r & j := k}
246 write(h,s[1:j+1])
247 s := s[j+1:0]
248 if *s = 0 then break
249 h := repl(" ",i)
250 }
251 return
252 end
253
254 procedure symbolToString(s)
255 static nonIdChars
256 initial nonIdChars:=~(&letters++&digits++'_')
257 return if upto(nonIdChars,s) then "\"" || s || "\"" else s
258 end
259
260 procedure productionToString(p)
261 local s
262 s := symbolToString(p.lhs.name) || " ="
263 every s ||:= " " || symbolToString((!p.rhs).name)
264 return s||"."
265 end
266
267 procedure showProductions()
268 local p,S,n,i
269 write()
270 write("Productions:")
271 write("start:",startSymbol.name,", EOI:",eoiSymbol.name)
272 S:=table()
273 every n:=!nonterminals do S[n.name]:=n
274 S:=sort(S,1)
275 every i:=1 to *S do S[i]:=S[i][2]
276 every p := !productions[!S] do {
277 writeIndented(productionToString(p))
278 }
279 return
280 end
281
282 procedure showSymbol(s)
283 write(s.name,": ",\s.kind|"Type undefined",
284 ", minLeng=",\s.minLeng|"Undefined")
285 return
286 end
287
288 procedure showSymbols()
289 local s
290 write()
291 write("Symbols:")
292 every s := !symbol do {
293 showSymbol(s)
294 }
295
296 return
297 end
298
299 procedure showSymbolSet(prefix,s)
300 local t, i, L
301 t:=set()
302 every insert(t,(!s).name)
303 L:=sort(t)
304 prefix ||:= "{"
305 every i := 1 to *L-1 do prefix ||:= symbolToString(L[i]) || ", "
306 prefix ||:= symbolToString(L[-1])
307 prefix ||:= "}"
308 writeIndented(prefix)
309
310 return
311 end
312
313 procedure showSelectionSets()
314 local p,s,L
315 write()
316 write("selection sets:")
317 L := sort(selectionSet,3)
318 while p:=get(L) & s:=get(L) do {
319 showSymbolSet("selection[ "||productionToString(p)||" ] = ",s)
320 }
321 return
322 end
323
324 procedure showSymbolSets(setName,s)
325 local n,st,L
326 L := sort(s,3)
327 write()
328 write(setName," sets:")
329 while n := get(L) & st := get(L) do {
330 showSymbolSet(n.name||"=",st)
331 }
332 return
333 end
334
335 procedure showFirstSets()
336 showSymbolSets("first",first)
337 return
338 end
339
340 procedure showLastSets()
341 showSymbolSets("last",last)
342 return
343 end
344
345 procedure showFollowSets()
346 showSymbolSets("follow",follow)
347 return
348 end
349
350 #######################################################################
351 #
352 # Grammar analysis
353 #
354
355 # compute the min lengths of terminal strings that can be derived
356 # from nonterminals and starting from particular productions.
357 #
358 procedure findMinLeng()
359 local n, ns, p, s, changes, leng
360
361 every ns:=!symbol do case ns.kind of {
362 "Nonterminal": ns.minLeng := tooLong
363 "Terminal": ns.minLeng := 1
364 "ActionSymbol": ns.minLeng := 0
365 }
366 every p := !!productions do p.minLeng := tooLong
367 ### showSymbols() ####
368 changes := 1
369 while \changes do {
370 changes := &null
371 every n := !nonterminals do {
372 every p := !productions[n] do {
373 leng := 0
374 every s := !p.rhs do {
375 leng +:= s.minLeng
376 }
377 p.minLeng := leng
378 ### showSymbol(n) ###
379 if n.minLeng > leng then {
380 changes := 1
381 n.minLeng := leng
382 }
383 }
384 }
385 }
386 return
387 end
388
389 procedure checkMinLeng()
390 local n
391 every n := !nonterminals & n.minLeng >= tooLong do {
392 error(n.name," does not appear to derive a terminal string")
393 }
394 return
395 end
396
397 #
398 # compute transitive closure of a relation
399 #
400 procedure transitiveClosure(s)
401 local n,r,i,k
402
403 every k := key(s) &
404 i := key(s) &
405 member(s[i],k)
406 do {
407 s[i] ++:= s[k]
408 }
409 return
410 end
411
412 #
413 # generate exposed symbols on rhs or in string
414 # "exposed" means preceded (Left) or followed (Right)
415 # by nullable nonterminal or action symbols
416 # includes all symbols, nonterminal, terminal and action
417 #
418 procedure exposedLeft(p)
419 local s
420 case type(p) of {
421 "Symbol": p:=[p]
422 "Production": p:=p.rhs
423 }
424 every s := !p do {
425 suspend s
426 if not isNullDeriving(s) then fail
427 }
428 fail
429 end
430
431 procedure exposedRight(p)
432 local s
433 case type(p) of {
434 "Symbol": p:=[p]
435 "Production": p:=p.rhs
436 }
437 every s := p[*p to 1 by -1] do {
438 suspend s
439 if not isNullDeriving(s) then fail
440 }
441 fail
442 end
443
444 #
445 # Compute Accessible Sets
446 #
447
448 procedure buildInitialAccessibleSets()
449 local p, r, s
450
451 s:=table()
452 every s[!nonterminals] := set()
453 every p := !!productions do {
454 every r := !p.rhs do {
455 insert(s[p.lhs],r)
456 }
457 }
458 return s
459 end
460
461 procedure findAccessibleSets()
462 local s
463 s := buildInitialAccessibleSets()
464 transitiveClosure(s)
465 return s
466 end
467
468 procedure findAccessibleSymbols()
469 local st,a
470 a := findAccessibleSets()
471 st := a[startSymbol]
472 insert(st,startSymbol)
473 insert(st,eoiSymbol)
474 return st
475 end
476
477 procedure checkAccessibility()
478 local s,st
479 st := findAccessibleSymbols()
480 every s := !(nonterminals|terminals|actions) do {
481 if not member(st,s) then
482 error(s.name,
483 " cannot appear in a sentential form")
484 }
485 return
486 end
487
488 #
489 # Compute First Sets
490 #
491
492 procedure initFirstSets()
493 local p, r
494
495 first := table()
496 every first[!nonterminals] := set()
497
498 every p := !!productions do {
499 every r := exposedLeft(p) do {
500 insert(first[p.lhs],r)
501 }
502 }
503 return
504 end
505
506 procedure findFirstSets()
507 initFirstSets()
508 transitiveClosure(first)
509 return
510 end
511
512 #
513 # Compute last sets
514 #
515 procedure initLastSets()
516 local p, r
517
518 last:=table()
519 every last[!nonterminals] := set()
520
521 every p := !!productions do {
522 every r := exposedRight(p) do {
523 insert(last[p.lhs],r)
524 }
525 }
526 return
527 end
528
529 procedure findLastSets()
530 initLastSets()
531 transitiveClosure(last)
532 return
533 end
534
535 procedure checkLnRRecursive()
536 local n
537 every n:= !nonterminals do {
538 if member(first[n],n) & member(last[n],n) then {
539 error(n.name," is both left and right recursive,",
540 " the grammar is ambiguous")
541 }
542 }
543 return
544 end
545
546 procedure findFollowSets()
547 local n, p, rhs, x, y, i, j
548
549 follow := table()
550
551 every n := !nonterminals do follow[n] := set()
552
553 every p := !productions[!nonterminals] &
554 rhs := p.rhs & *rhs>1
555 do {
556 every x := rhs[i:=1 to *rhs-1] & isNonterminal(x) do {
557 every y := rhs[j:=i+1 to *rhs] do {
558 every
559 insert(
560 follow[x|isNonterminal(!last[x])],
561 isTerminal(y|!\first[y])
562 )
563 if not isNullDeriving(y) then break #back to "every x" loop
564 }
565 }
566 }
567 every insert(
568 follow[isNonterminal(startSymbol|!last[startSymbol])],
569 eoiSymbol
570 )
571 return
572 end
573