| 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 |
|