1 module epsilon.soag.soag; 2 3 import EAG = epsilon.eag; 4 import Predicates = epsilon.predicates; 5 import runtime; 6 import std.bitmanip : BitArray; 7 import std.stdio; 8 9 const firstSym = EAG.firstHNont; 10 const firstRule = 0; 11 const firstSymOcc = 0; 12 const firstAffOcc = 0; 13 const firstPartNum = 0; 14 const firstAffOccNum = 0; 15 const firstVS = 1; 16 const firstDefAffOcc = EAG.firstVar; 17 const firstStorageName = 0; 18 const firstAffixApplCnt = EAG.firstVar; 19 const nil = -1; 20 21 struct SymDesc 22 { 23 int FirstOcc; 24 int MaxPart; 25 EAG.ScopeDesc AffPos; 26 27 public string toString() const pure @safe 28 { 29 import std.format : format; 30 31 string[] items; 32 33 items ~= format!"FirstOcc=%s"(FirstOcc); 34 items ~= format!"MaxPart=%s"(MaxPart); 35 items ~= format!"AffPos=%s"(AffPos); 36 return format!"Sym(%-(%s, %))"(items); 37 } 38 } 39 40 class RuleDesc 41 { 42 EAG.ScopeDesc SymOcc; 43 EAG.ScopeDesc AffOcc; 44 BitArray[] TDP; 45 BitArray[] DP; 46 EAG.ScopeDesc VS; 47 } 48 49 alias RuleBase = RuleDesc; 50 51 class EmptyRule : RuleDesc 52 { 53 EAG.Rule Rule; 54 } 55 56 class OrdRule : RuleDesc 57 { 58 EAG.Alt Alt; 59 } 60 61 struct SymOccDesc 62 { 63 int SymInd; 64 int RuleInd; 65 EAG.Nont Nont; 66 EAG.ScopeDesc AffOcc; 67 int Next; 68 69 public string toString() const @safe 70 { 71 import std.format : format; 72 73 string[] items; 74 75 items ~= EAG.HNontRepr(SymInd); 76 items ~= format!"RuleInd=%s"(RuleInd); 77 items ~= format!"Nont=%s"(Nont); 78 items ~= format!"AffOcc=%s"(AffOcc); 79 items ~= format!"Next=%s"(Next); 80 return format!"SymOcc(%-(%s, %))"(items); 81 } 82 } 83 84 struct AffOccNumRecord 85 { 86 int InRule; 87 int InSym; 88 89 public string toString() const pure @safe 90 { 91 import std.format : format; 92 93 string[] items; 94 95 items ~= format!"InRule=%s"(InRule); 96 items ~= format!"InSym=%s"(InSym); 97 return format!"AffOccNum(%-(%s, %))"(items); 98 } 99 } 100 101 struct AffOccDesc 102 { 103 int ParamBufInd; 104 int SymOccInd; 105 AffOccNumRecord AffOccNum; 106 107 public string toString() const pure @safe 108 { 109 import std.format : format; 110 111 string[] items; 112 113 items ~= format!"ParamBufInd=%s"(ParamBufInd); 114 items ~= format!"SymOccInd=%s"(SymOccInd); 115 items ~= AffOccNum.toString; 116 return format!"AffOcc(%-(%s, %))"(items); 117 } 118 } 119 120 class Instruction 121 { 122 } 123 124 class Visit : Instruction 125 { 126 int SymOcc; 127 int VisitNo; 128 } 129 130 class Leave : Instruction 131 { 132 int VisitNo; 133 } 134 135 class Call : Instruction 136 { 137 int SymOcc; 138 } 139 140 SymDesc[] Sym; 141 int[] PartNum; 142 RuleBase[] Rule; 143 SymOccDesc[] SymOcc; 144 AffOccDesc[] AffOcc; 145 Instruction[] VS; 146 int[] DefAffOcc; 147 int[] StorageName; 148 int[] AffixApplCnt; 149 int NextSym; 150 int NextPartNum; 151 int NextRule; 152 int NextSymOcc; 153 int NextAffOcc; 154 int NextVS; 155 int NextDefAffOcc; 156 int NextStorageName; 157 int NextAffixApplCnt; 158 int MaxAffNumInRule; 159 int MaxAffNumInSym; 160 int MaxPart; 161 const abnormalError = 1; 162 const cyclicTDP = 2; 163 const notLeftDefined = 3; 164 const notEnoughMemory = 99; 165 166 void Error(T)(int ErrorType, T Proc) 167 { 168 stdout.write("ERROR: "); 169 switch (ErrorType) 170 { 171 case abnormalError: 172 stdout.write("abnormal error "); 173 break; 174 case notEnoughMemory: 175 stdout.write("memory allocation failed "); 176 break; 177 case cyclicTDP: 178 stdout.write("TDP is cyclic...aborted\n"); 179 break; 180 case notLeftDefined: 181 stdout.write("Grammar are not left defined\n"); 182 break; 183 default: 184 assert(0); 185 } 186 if (ErrorType == abnormalError || ErrorType == notEnoughMemory) 187 { 188 stdout.write("in procedure "); 189 stdout.writeln(Proc); 190 } 191 throw new Exception("TODO"); 192 } 193 194 void Expand() nothrow @safe 195 { 196 size_t NewLen(size_t ArrayLen) 197 { 198 assert(ArrayLen < DIV(size_t.max, 2)); 199 200 return 2 * ArrayLen + 1; 201 } 202 203 if (NextAffOcc >= AffOcc.length) 204 { 205 auto AffOcc1 = new AffOccDesc[NewLen(AffOcc.length)]; 206 207 for (size_t i = firstAffOcc; i < AffOcc.length; ++i) 208 AffOcc1[i] = AffOcc[i]; 209 AffOcc = AffOcc1; 210 } 211 if (NextSymOcc >= SymOcc.length) 212 { 213 auto SymOcc1 = new SymOccDesc[NewLen(SymOcc.length)]; 214 215 for (size_t i = firstSymOcc; i < SymOcc.length; ++i) 216 SymOcc1[i] = SymOcc[i]; 217 SymOcc = SymOcc1; 218 } 219 if (NextRule >= Rule.length) 220 { 221 auto Rule1 = new RuleBase[NewLen(Rule.length)]; 222 223 for (size_t i = firstRule; i < Rule.length; ++i) 224 Rule1[i] = Rule[i]; 225 Rule = Rule1; 226 } 227 if (NextVS >= VS.length) 228 { 229 auto VS1 = new Instruction[NewLen(VS.length)]; 230 231 for (size_t i = firstVS; i < VS.length; ++i) 232 VS1[i] = VS[i]; 233 VS = VS1; 234 } 235 } 236 237 void AppAffOcc(int Params) nothrow @safe 238 { 239 if (Params != EAG.empty) 240 { 241 while (EAG.ParamBuf[Params].Affixform != EAG.nil) 242 { 243 AffOcc[NextAffOcc].ParamBufInd = Params; 244 AffOcc[NextAffOcc].SymOccInd = NextSymOcc; 245 AffOcc[NextAffOcc].AffOccNum.InRule = NextAffOcc - Rule[NextRule].AffOcc.Beg; 246 AffOcc[NextAffOcc].AffOccNum.InSym = NextAffOcc - SymOcc[NextSymOcc].AffOcc.Beg; 247 ++NextAffOcc; 248 if (NextAffOcc >= AffOcc.length) 249 Expand; 250 ++Params; 251 } 252 } 253 } 254 255 void AppSymOccs(EAG.Factor Factor) nothrow @safe 256 { 257 while (Factor !is null) 258 { 259 if (auto nont = cast(EAG.Nont) Factor) 260 { 261 SymOcc[NextSymOcc].SymInd = nont.Sym; 262 SymOcc[NextSymOcc].RuleInd = NextRule; 263 SymOcc[NextSymOcc].Nont = nont; 264 SymOcc[NextSymOcc].AffOcc.Beg = NextAffOcc; 265 AppAffOcc(nont.Actual.Params); 266 SymOcc[NextSymOcc].AffOcc.End = NextAffOcc - 1; 267 SymOcc[NextSymOcc].Next = Sym[nont.Sym].FirstOcc; 268 Sym[nont.Sym].FirstOcc = NextSymOcc; 269 ++NextSymOcc; 270 if (NextSymOcc >= SymOcc.length) 271 Expand; 272 } 273 Factor = Factor.Next; 274 } 275 } 276 277 void AppLeftSymOcc(size_t leftSym, int Params) @safe 278 { 279 import std.conv : to; 280 281 SymOcc[NextSymOcc].SymInd = leftSym.to!int; 282 SymOcc[NextSymOcc].RuleInd = NextRule; 283 SymOcc[NextSymOcc].Nont = null; 284 SymOcc[NextSymOcc].AffOcc.Beg = NextAffOcc; 285 AppAffOcc(Params); 286 SymOcc[NextSymOcc].AffOcc.End = NextAffOcc - 1; 287 SymOcc[NextSymOcc].Next = Sym[leftSym].FirstOcc; 288 Sym[leftSym].FirstOcc = NextSymOcc; 289 ++NextSymOcc; 290 if (NextSymOcc >= SymOcc.length) 291 Expand; 292 } 293 294 void AppEmptyRule(size_t leftSym, EAG.Rule EAGRule) @safe 295 { 296 EmptyRule A = new EmptyRule; 297 298 Rule[NextRule] = A; 299 A.Rule = EAGRule; 300 A.SymOcc.Beg = NextSymOcc; 301 A.AffOcc.Beg = NextAffOcc; 302 if (auto opt = cast(EAG.Opt) EAGRule) 303 AppLeftSymOcc(leftSym, opt.Formal.Params); 304 else if (auto rep = cast(EAG.Rep) EAGRule) 305 AppLeftSymOcc(leftSym, rep.Formal.Params); 306 A.SymOcc.End = NextSymOcc - 1; 307 A.AffOcc.End = NextAffOcc - 1; 308 ++NextRule; 309 if (NextRule >= Rule.length) 310 Expand; 311 } 312 313 void AppRule(EAG.Alt EAGAlt) @safe 314 { 315 OrdRule A = new OrdRule; 316 317 Rule[NextRule] = A; 318 A.Alt = EAGAlt; 319 A.SymOcc.Beg = NextSymOcc; 320 A.AffOcc.Beg = NextAffOcc; 321 AppLeftSymOcc(EAGAlt.Up, EAGAlt.Formal.Params); 322 AppSymOccs(EAGAlt.Sub); 323 A.SymOcc.End = NextSymOcc - 1; 324 A.AffOcc.End = NextAffOcc - 1; 325 ++NextRule; 326 if (NextRule >= Rule.length) 327 Expand; 328 } 329 330 void AppRepRule(EAG.Alt EAGAlt) @safe 331 { 332 OrdRule A = new OrdRule; 333 334 Rule[NextRule] = A; 335 A.Alt = EAGAlt; 336 A.SymOcc.Beg = NextSymOcc; 337 A.AffOcc.Beg = NextAffOcc; 338 AppLeftSymOcc(EAGAlt.Up, EAGAlt.Formal.Params); 339 AppSymOccs(EAGAlt.Sub); 340 AppLeftSymOcc(EAGAlt.Up, EAGAlt.Actual.Params); 341 A.SymOcc.End = NextSymOcc - 1; 342 A.AffOcc.End = NextAffOcc - 1; 343 ++NextRule; 344 if (NextRule >= Rule.length) 345 Expand; 346 } 347 /** 348 * IN: Instruktion 349 * OUT: - 350 * SEM: fügt eine Instruktion in die Datenstruktur VS ein 351 */ 352 void AppVS(ref Instruction I) nothrow @safe 353 { 354 VS[NextVS] = I; 355 ++NextVS; 356 if (NextVS >= VS.length) 357 Expand; 358 } 359 360 /** 361 * IN: Symbol, Nummer des Affixposition 362 * OUT: boolscher Wert 363 * SEM: Test, ob Affixposition inherited ist 364 */ 365 bool IsInherited(int S, int AffOccNum) @nogc nothrow @safe 366 { 367 return EAG.DomBuf[EAG.HNont[S].Sig + AffOccNum] < 0; 368 } 369 370 /** 371 * IN: Symbol, Nummer des Affixposition 372 * OUT: boolscher Wert 373 * SEM: Test, ob Affixposition synthesized ist 374 */ 375 bool IsSynthesized(size_t S, int AffOccNum) @nogc nothrow @safe 376 { 377 return EAG.DomBuf[EAG.HNont[S].Sig + AffOccNum] > 0; 378 } 379 380 /** 381 * IN: Symbol, Nummern zweier Affixpositionen zum Symbol 382 * OUT: boolscher Wert 383 * SEM: Test, ob die beiden Affixpositionen orientierbar sind 384 */ 385 bool IsOrientable(int S, int AffOccNum1, int AffOccNum2) @nogc nothrow @safe 386 { 387 return IsInherited(S, AffOccNum1) && IsSynthesized(S, AffOccNum2) 388 || IsInherited(S, AffOccNum2) && IsSynthesized(S, AffOccNum1); 389 } 390 391 /** 392 * IN: Regel 393 * OUT: boolscher Wert 394 * SEM: Test, ob eine Evaluatorregel vorliegt 395 * PRECOND: Predicates.Check muss vorher ausgewertet sein 396 */ 397 bool IsEvaluatorRule(size_t R) @nogc nothrow 398 { 399 return !EAG.Pred[SymOcc[Rule[R].SymOcc.Beg].SymInd]; 400 } 401 402 /** 403 * IN: Symbolvorkommen 404 * OUT: boolscher Wert 405 * SEM: Test, ob ein Prädikat vorliegt 406 * PRECOND: Predicates.Check muss vorher ausgewertet sein 407 */ 408 bool IsPredNont(int SO) @nogc nothrow 409 { 410 return EAG.Pred[SymOcc[SO].SymInd]; 411 } 412 413 /** 414 * IN: zwei Instruktionen aus der Visit-Sequenz 415 * OUT: boolscher Wert 416 * SEM: Test, ob zwei Instruktionnen gleich sind; 417 * etwas optimiert für den Fall, dass einer oder beide Parameter nil ist 418 */ 419 bool isEqual(Instruction I1, Instruction I2) @nogc nothrow pure @safe 420 { 421 if (I1 is null && I2 is null) 422 return true; 423 else if (I1 is null || I2 is null) 424 return false; 425 else if (cast(Visit) I1 !is null && cast(Visit) I2 !is null) 426 return (cast(Visit) I1).SymOcc == (cast(Visit) I2).SymOcc 427 && (cast(Visit) I1).VisitNo == (cast(Visit) I2).VisitNo; 428 else if (cast(Leave) I1 !is null && cast(Leave) I2 !is null) 429 return (cast(Leave) I1).VisitNo == (cast(Leave) I2).VisitNo; 430 else if (cast(Call) I1 !is null && cast(Call) I2 !is null) 431 return (cast(Call) I1).SymOcc == (cast(Call) I2).SymOcc; 432 else 433 return false; 434 } 435 436 /** 437 * SEM: Initialisierung der SOAG-Datenstruktur; Transformation der EAG-Datenstruktur 438 */ 439 void Init() 440 { 441 EAG.Alt A; 442 int a; 443 int Max; 444 445 Sym = new SymDesc[EAG.NextHNont]; 446 Rule = new RuleBase[128]; 447 SymOcc = new SymOccDesc[256]; 448 AffOcc = new AffOccDesc[512]; 449 VS = new Instruction[512]; 450 DefAffOcc = new int[EAG.NextVar]; 451 AffixApplCnt = new int[EAG.NextVar]; 452 StorageName = null; 453 NextSym = EAG.NextHNont; 454 NextRule = firstRule; 455 NextSymOcc = firstSymOcc; 456 NextAffOcc = firstAffOcc; 457 NextVS = firstVS; 458 NextDefAffOcc = EAG.NextVar; 459 NextStorageName = nil; 460 NextAffixApplCnt = EAG.NextVar; 461 Predicates.Check; 462 for (size_t i = EAG.firstHNont; i < EAG.NextHNont; ++i) 463 Sym[i].FirstOcc = nil; 464 foreach (i; EAG.All.bitsSet) 465 { 466 if (cast(EAG.Rep) EAG.HNont[i].Def) 467 { 468 A = EAG.HNont[i].Def.Sub; 469 while (A !is null) 470 { 471 AppRepRule(A); 472 A = A.Next; 473 } 474 } 475 else 476 { 477 A = EAG.HNont[i].Def.Sub; 478 while (A !is null) 479 { 480 AppRule(A); 481 A = A.Next; 482 } 483 } 484 if (cast(EAG.Rep) EAG.HNont[i].Def || cast(EAG.Opt) EAG.HNont[i].Def) 485 AppEmptyRule(i, EAG.HNont[i].Def); 486 } 487 MaxAffNumInRule = 0; 488 for (size_t i = firstRule; i < NextRule; ++i) 489 { 490 Max = Rule[i].AffOcc.End - Rule[i].AffOcc.Beg; 491 if (Max > MaxAffNumInRule) 492 MaxAffNumInRule = Max; 493 if (IsEvaluatorRule(i) && Max >= 0) 494 { 495 Rule[i].TDP = new BitArray[Max + 1]; 496 Rule[i].DP = new BitArray[Max + 1]; 497 for (a = firstAffOccNum; a <= Max; ++a) 498 { 499 Rule[i].TDP[a] = BitArray(); 500 Rule[i].TDP[a].length = Max + 1 + 1; 501 Rule[i].DP[a] = BitArray(); 502 Rule[i].DP[a].length = Max + 1 + 1; 503 } 504 } 505 } 506 MaxAffNumInSym = 0; 507 NextPartNum = firstPartNum; 508 foreach (i; EAG.All.bitsSet) 509 { 510 Max = SymOcc[Sym[i].FirstOcc].AffOcc.End - SymOcc[Sym[i].FirstOcc].AffOcc.Beg; 511 Sym[i].AffPos.Beg = NextPartNum; 512 NextPartNum = NextPartNum + Max; 513 Sym[i].AffPos.End = NextPartNum; 514 ++NextPartNum; 515 if (Max > MaxAffNumInSym) 516 MaxAffNumInSym = Max; 517 Sym[i].MaxPart = 0; 518 } 519 PartNum = new int[NextPartNum]; 520 MaxPart = 0; 521 for (size_t i = EAG.firstVar; i < EAG.NextVar; ++i) 522 { 523 DefAffOcc[i] = -1; 524 AffixApplCnt[i] = 0; 525 } 526 } 527 528 static this() @safe 529 { 530 import log : info; 531 532 info!"SOAG-Evaluatorgenerator 1.06 dk 14.03.98"; 533 }