Debian Codegraph @

ipl/packs/tcll1/ll1.icn

raw
1
2 link gramanal
3 link xcode
4
5 global outFile
6
7 global fiducials #set(Symbol)
8 global selectionSet #table:Production->Set(Symbol)
9 # set of symbols that choose this production
10 # if lhs is atop the stack
11
12 #
13 #
14 #
15 procedure analyzeGrammar()
16
17 findMinLeng()
18 checkMinLeng()
19 checkAccessibility()
20 findFirstSets()
21 findLastSets()
22 checkLnRRecursive()
23 findFollowSets()
24
25 end
26
27 procedure declareFiducial(s)
28 local t
29 /symbol[s] := Symbol(s)
30 t := symbol[s]
31 /t.kind := "Terminal"
32 if t.kind ~== "Terminal" then {
33 error(t.kind," ",s," being declared a fiducial")
34 fail
35 }
36 insert(fiducials,t)
37 return
38 end
39
40 procedure findSelectionSets()
41 local p,r,s,t
42 every p:=!!productions do {
43 s:= set()
44 every r := exposedLeft(p) do {
45 if isNonterminal(r) then {
46 s ++:= first[r]
47 } else if isTerminal(r) then {
48 insert(s,r)
49 }
50 }
51 if p.minLeng=0 then s ++:= follow[p.lhs]
52 every t := !s & not isTerminal(t) do delete(s,t)
53 selectionSet[p] := s
54 }
55 return
56 end
57
58 procedure ll1(outFileName)
59 local t,g
60
61 analyzeGrammar()
62 findSelectionSets()
63
64 testLL1()
65
66 if errorCount>0 then fail
67
68 outFile := open(outFileName,"w") |
69 {error( "unable to open output file ",outFileName)
70 return}
71
72 t:=genLL1()
73 #g:=encode(t)
74 #write(outFile,g)
75 xencode(t,outFile)
76 #
77 close(outFile)
78 return
79
80 end
81
82 procedure testLL1()
83
84 local n, plist, p1, p2, px, py, m, i, s
85
86 #check for left recursion
87
88 every n := !nonterminals do
89 if member(first[n],n) then
90 error(n.name," is left recursive, the grammar is not LL(1)")
91
92 #check for overlapping selection sets
93
94 every n := !nonterminals do {
95 plist := productions[n]
96 m := *plist
97 every p1 := plist[i:=1 to m-1] &
98 p2 := plist[i+1 to m] do {
99 if p1.minLeng = p2.minLeng = 0 then {
100 error("productions\n1.\t",
101 productionToString(p1),"\n2.\t",
102 productionToString(p2),
103 "\nboth derive the empty string" )
104 } else if *(s:=selectionSet[p1]**selectionSet[p2]) > 0 then {
105 if (p1.minLeng = 0) | (p2.minLeng = 0) then {
106 px:=p1; py:=p2; if px.minLeng=0 then px:=:py
107 warning("overlapping selection sets for\n\t",
108 productionToString(px),
109 "\nand empty-deriving production\n\t",
110 productionToString(py) )
111 } else {
112 error("overlapping selection sets for\n1.\t",
113 productionToString(p1),"\n2.\t",
114 productionToString(p2) )
115 }
116 showSymbolSet(" overlap: ",s)
117 }
118 }
119 }
120 return
121 end
122
123 procedure genLL1()
124 local mapSymbol,
125 rhsList,
126 mapRHS,
127 emptyRHS,
128 sel,
129 deflt,
130 firstFiduc,
131 fiducList,
132 actionList,
133 termList,
134 minLengRHS
135 local s,p,r,L,n,m,mr,ml,ms,nullrhs,t,i
136 # build encapsulated symbols, [ name ], so that all references
137 # to the symbol can share the same string
138 mapSymbol := table()
139 every s := !symbol do {
140 mapSymbol[s] := [s.name]
141 }
142 # map productions into right hand side lists with encapsulated symbols
143 emptyRHS:=list()
144 mapRHS := table()
145 every p := !!productions do {
146 L:=list()
147 every s:= !p.rhs do put(L,mapSymbol[s])
148 mapRHS[p] := if *L = 0 then emptyRHS else L
149 }
150 #make a list of all right hand sides
151 # the list will be used after input to remove the symbols
152 # from their encapsulating lists
153 rhsList:=[]
154 every L:=!mapRHS do put(rhsList,L)
155
156 #create selection and default tables
157 sel:=table()
158 deflt:=table()
159 every n:=!nonterminals do {
160
161 # Build a list of productions for the nonterminal sorted by
162 # cardinality of selection set. Reserve a production with an
163 # empty-string-deriving RHS for special treatment. Put the
164 # productions into the sel table, but reserve the empty-deriving
165 # RHS or, if none, then the RHS with the largest selection set to
166 # be the default. If there is an overlap in selection sets between
167 # a non-empty-deriving and the empty-deriving RHS, then this will
168 # give precedence to the non-empty-deriving RHS, as is required to
169 # solve the "dangling else problem."
170
171 nullrhs:=&null
172 t:=table() #map productions into cardinality of selection set
173 every p:=!productions[n] do
174 if p.minLeng=0
175 then nullrhs:=p
176 else t[p] := *selectionSet[p]
177 L:=sort(t,2)
178 put(L,[\nullrhs,*selectionSet[nullrhs]])
179 if *L = 1 then {
180 deflt[mapSymbol[n]] := mapRHS[L[1][1]]
181 } else {
182 /sel[mapSymbol[n]] := table()
183 # if there is an empty-deriving RHS then put all other
184 # RHS's into sel table--the empty-deriving one will be
185 # the default. Or, if the largest selection set
186 # for any RHS is small enough, then put all RHS's into
187 # selection table. Otherwise, reserve the RHS with the
188 # largest selection set to be the default.
189 m := if /nullrhs & L[*L][2] < 5 then *L else *L-1
190 every i := 1 to m &
191 p := L[i][1] &
192 mr := mapRHS[p] &
193 ml := mapSymbol[p.lhs] &
194 ms := mapSymbol[!selectionSet[p]] do {
195 sel[ml][ms] := mr
196 }
197 # If not included already, handle the last.
198 if m~=*L then deflt[mapSymbol[n]]:=mapRHS[L[*L][1]]
199 }
200 }
201
202 termList := list()
203 every s:=!terminals do put(termList,mapSymbol[s])
204
205 actionList := list()
206 every put(actionList,mapSymbol[!actions])
207
208 fiducList := list()
209 insert(fiducials,eoiSymbol)
210 every put(fiducList,mapSymbol[!fiducials])
211
212 firstFiduc := table()
213 every n:=!nonterminals & *(s:=first[n]**fiducials)>0 do {
214 firstFiduc[mapSymbol[n]] := list()
215 every put(firstFiduc[mapSymbol[n]],
216 mapSymbol[!s])
217 }
218
219 minLengRHS := table()
220 every n := !nonterminals do {
221 p := productions[n][1]
222 every r := !productions[n] &
223 p.minLeng > r.minLeng do p:=r
224 minLengRHS[mapSymbol[n]] := mapRHS[p]
225 }
226
227 return [
228 rhsList,
229 sel,
230 deflt,
231 termList,
232 actionList,
233 fiducList,
234 firstFiduc,
235 minLengRHS,
236 mapSymbol[startSymbol],
237 mapSymbol[eoiSymbol]
238 ]
239 end
240
241
242 #######################################################################
243 #
244 # printing the grammar
245 #
246 procedure printGrammar()
247 local n,p,st,s
248 write("start symbol:\t",startSymbol.name)
249 write("EOI symbol:\t",eoiSymbol.name)
250 write()
251 showSymbolSet("terminal symbols: ",terminals)
252
253 write()
254 showSymbolSet("fiducial symbols: ",fiducials)
255
256 write()
257 showSymbolSet("action symbols: ",actions)
258
259 write()
260 write("nonterminal symbols:")
261 st := set()
262 every insert(st,(!nonterminals).name)
263 st := sort(st)
264 every n := !st do {
265 s := symbol[n]
266 write(" ",n,":")
267 showSymbolSet(" first set: ",first[s])
268 showSymbolSet(" follow set: ",follow[s])
269 write()
270 }
271
272 write("productions:")
273 every p := !productions[symbol[!st]] do {
274 writeIndented(productionToString(p))
275 showSymbolSet(" : ",selectionSet[p])
276 }
277 return
278 end
279