Unofficial Dub Package Documentation 
1 module epsilon.analyzer;
2 
3 import EAG = epsilon.eag;
4 import Earley = epsilon.earley;
5 import epsilon.lexer : Lexer, Token;
6 import io : Input, Position;
7 import log;
8 import runtime;
9 import std.bitmanip : BitArray;
10 import std.conv : to;
11 
12 const nil = EAG.nil;
13 int ErrorCounter;
14 bool NameNotified;
15 
16 Lexer lexer;
17 
18 void Error(Position Pos, string ErrMsg) @safe
19 {
20     import std.exception : enforce;
21 
22     ++ErrorCounter;
23 
24     enforce(ErrorCounter <= 25,
25             "Too many errors!");
26 
27     error!"%s\n%s"(ErrMsg, Pos);
28 }
29 
30 /**
31  * Specification:
32  *   (MetaRule | HyperRule) {MetaRule | HyperRule} .
33  */
34 void Specification()
35 {
36     /**
37      * MetaRule:
38      *   ident "=" MetaExpr ".".
39      */
40     void MetaRule(int Id, bool IsToken)
41     {
42         const MNont = EAG.FindMNont(Id);
43 
44         /**
45          * MetaExpr:
46          *   MetaTerm {"|" MetaTerm}.
47          */
48         void MetaExpr()
49         {
50             /**
51              * MetaTerm:
52              *   {ident | string}.
53              */
54             void MetaTerm()
55             {
56                 while (true)
57                 {
58                     if (lexer.front == Token.name)
59                     {
60                         EAG.AppMemb(EAG.FindMNont(lexer.value.to!int));
61                         lexer.popFront;
62                         if (lexer.front == Token.number)
63                         {
64                             Error(lexer.position, "number is not allowed here");
65                             lexer.popFront;
66                         }
67                     }
68                     else if (lexer.front == Token.string_)
69                     {
70                         EAG.AppMemb(-EAG.FindMTerm(lexer.value.to!int));
71                         lexer.popFront;
72                     }
73                     else
74                     {
75                         EAG.AppMemb(EAG.nil);
76                         break;
77                     }
78                 }
79             }
80 
81             while (true)
82             {
83                 const Rhs = EAG.NextMemb;
84 
85                 MetaTerm;
86                 EAG.AppMemb(EAG.NewMAlt(MNont, Rhs));
87                 if (lexer.front == '|')
88                     lexer.popFront;
89                 else
90                     break;
91             }
92         }
93 
94         EAG.MNont[MNont].IsToken = EAG.MNont[MNont].IsToken || IsToken;
95         if (lexer.front == '=')
96             lexer.popFront;
97         else
98             Error(lexer.position, "'=' expected");
99         MetaExpr;
100         if (lexer.front == '.')
101             lexer.popFront;
102         else
103             Error(lexer.position, "'.' expected");
104     }
105 
106     void SetBaseName()
107     {
108         EAG.StartSym = EAG.firstHNont;
109         EAG.BaseName = EAG.symbolTable.symbol(EAG.HNont[EAG.StartSym].Id);
110     }
111 
112     /**
113      * HyperRule:
114      *   ident [FormalParams] ":" HyperExpr ".".
115      */
116     void HyperRule(int Id, bool IsToken)
117     {
118         void Distribute(int Sym, EAG.Alt A, int Sig, EAG.ParamsDesc Formal)
119         {
120             void CopyParams(ref int s, ref int d)
121             {
122                 int Affixform;
123                 int P = s;
124 
125                 d = EAG.NextParam;
126                 while (EAG.ParamBuf[P].Affixform != nil)
127                 {
128                     Earley.CopyAffixform(EAG.ParamBuf[P].Affixform, Affixform);
129                     EAG.AppParam(Affixform, EAG.ParamBuf[P].Pos);
130                     ++P;
131                 }
132                 EAG.AppParam(nil, EAG.ParamBuf[P].Pos);
133             }
134 
135             EAG.HNont[Sym].Sig = Sig;
136             A.Formal.Pos = Formal.Pos;
137             A.Formal.Params = Formal.Params;
138             A = A.Next;
139             while (A !is null)
140             {
141                 A.Formal.Pos = Formal.Pos;
142                 CopyParams(Formal.Params, A.Formal.Params);
143                 A = A.Next;
144             }
145         }
146 
147         /**
148          * FormalParams:
149          *   "<" ("+" | "-") Affixform ":" ident {"," ("+" | "-") Affixform ":" ident} ">".
150          * ActualParams:
151          *   "<" Affixform {"," Affixform} ">".
152          */
153         void Params(ref EAG.ParamsDesc Actual, ref EAG.ParamsDesc Formal)
154         {
155             /**
156              * Affixform:
157              *   {string | ["!"] ident [number]}.
158              */
159             void Affixform(ref int Sym)
160             {
161                 int Cnt = 0;
162 
163                 while (true)
164                 {
165                     short Uneq;
166                     int Num;
167                     Position Pos = lexer.position;
168 
169                     if (lexer.front == Token.string_)
170                     {
171                         Sym = -EAG.FindMTerm(lexer.value.to!int);
172                         Num = 0;
173                         lexer.popFront;
174                         ++Cnt;
175                     }
176                     else if (lexer.front == '!' || lexer.front == Token.name)
177                     {
178                         if (lexer.front == '!')
179                         {
180                             Uneq = -1;
181                             lexer.popFront;
182                         }
183                         else
184                         {
185                             Uneq = 1;
186                         }
187                         if (lexer.front == Token.name)
188                         {
189                             Sym = EAG.FindMNont(lexer.value.to!int);
190                             lexer.popFront;
191                             if (lexer.front == Token.number)
192                             {
193                                 Num = Uneq * (lexer.value.to!int + 2);
194                                 lexer.popFront;
195                             }
196                             else
197                             {
198                                 Num = Uneq;
199                             }
200                             ++Cnt;
201                         }
202                         else
203                         {
204                             Error(lexer.position, "Metanonterminal expected");
205                         }
206                     }
207                     else
208                     {
209                         Earley.EndAffixform(Pos);
210                         break;
211                     }
212                     Earley.AppMSym(Sym, Num, Pos);
213                 }
214                 if (Cnt != 1)
215                     Sym = -1;
216             }
217 
218             EAG.ParamsDesc P;
219 
220             P.Params = EAG.empty;
221             P.Pos = lexer.position;
222             Actual = P;
223             Formal = P;
224             if (lexer.front == '<')
225             {
226                 lexer.popFront;
227 
228                 bool isFormal = lexer.front == '+' || lexer.front == '-';
229 
230                 P.Params = EAG.NextParam;
231                 while (true)
232                 {
233                     char Dir;
234                     int Sym;
235 
236                     if (lexer.front == '+' || lexer.front == '-')
237                     {
238                         if (!isFormal)
239                             Error(lexer.position, "'+' or '-' not allowed in actual params");
240                         Dir = lexer.front.to!char;
241                         lexer.popFront;
242                     }
243                     else
244                     {
245                         if (isFormal)
246                             Error(lexer.position, "'+' or '-' expected");
247                     }
248                     EAG.AppParam(Earley.StartAffixform(), lexer.position);
249                     Affixform(Sym);
250                     if (isFormal)
251                     {
252                         if (Sym < 0 || lexer.front == ':')
253                         {
254                             if (lexer.front == ':')
255                                 lexer.popFront;
256                             else
257                                 Error(lexer.position, "':' expected");
258                             if (lexer.front == Token.name)
259                             {
260                                 EAG.AppDom(Dir, EAG.FindMNont(lexer.value.to!int));
261                                 lexer.popFront;
262                             }
263                             else
264                             {
265                                 Error(lexer.position, "Metanonterminal expected");
266                             }
267                             if (lexer.front == Token.number)
268                             {
269                                 Error(lexer.position, "number is not allowed here");
270                                 lexer.popFront;
271                             }
272                         }
273                         else
274                         {
275                             EAG.AppDom(Dir, Sym);
276                         }
277                     }
278                     while (lexer.front != ',' && lexer.front != '>' && lexer.front != Token.end)
279                     {
280                         Error(lexer.position, "symbol not allowed");
281                         lexer.popFront;
282                     }
283                     if (lexer.front == ',')
284                         lexer.popFront;
285                     else
286                         break;
287                 }
288                 EAG.AppParam(EAG.nil, lexer.position);
289                 if (lexer.front == '>')
290                     lexer.popFront;
291                 else
292                     Error(lexer.position, "'>' expected");
293                 if (isFormal)
294                     Formal.Params = P.Params;
295                 else
296                     Actual.Params = P.Params;
297             }
298         }
299 
300         /**
301          * HyperExpr:
302          *   [FormalParams] HyperTerm [ActualParams] {"|" [FormalParams] HyperTerm [ActualParams]}.
303          */
304         void HyperExpr(int HNont, int Id, char Left, ref EAG.Alt HExpr, Position AltPos)
305         {
306             /**
307              * HyperTerm:
308              *   { ident [ActualParams]
309              *   | string
310              *   | [ActualParams] ( "(" HyperExpr ")"
311              *                    | "[" HyperExpr "]" [FormalParams]
312              *                    | "{" HyperExpr "}" [FormalParams]  )
313              *   } .
314              */
315             void HyperTerm(ref EAG.ParamsDesc Actual, ref EAG.Factor First, ref EAG.Factor Last)
316             {
317                 int HNont;
318                 EAG.Alt HExpr;
319                 EAG.ParamsDesc Formal;
320                 char Left;
321                 Position Pos;
322 
323                 First = null;
324                 Last = null;
325                 while (true)
326                 {
327                     if (lexer.front == Token.name)
328                     {
329                         if (Actual.Params != EAG.empty)
330                         {
331                             Error(Actual.Pos, "actual params not allowed here");
332                             Actual.Params = EAG.empty;
333                         }
334                         HNont = EAG.FindHNont(lexer.value.to!int);
335                         Pos = lexer.position;
336                         lexer.popFront;
337                         if (lexer.front == Token.number)
338                         {
339                             Error(lexer.position, "number is not allowed here!");
340                             lexer.popFront;
341                         }
342                         Params(Actual, Formal);
343                         if (Formal.Params != EAG.empty)
344                             Error(Formal.Pos, "formal params not allowed here");
345                         EAG.NewNont(Last, HNont, Actual, Pos);
346                         Actual.Params = EAG.empty;
347                     }
348                     else if (lexer.front == Token.string_)
349                     {
350                         if (Actual.Params != EAG.empty)
351                         {
352                             Error(Actual.Pos, "actual params not allowed here");
353                             Actual.Params = EAG.empty;
354                         }
355                         EAG.NewTerm(Last, EAG.FindHTerm(lexer.value.to!int), lexer.position);
356                         lexer.popFront;
357                     }
358                     else
359                     {
360                         if (Actual.Params == EAG.empty)
361                         {
362                             Params(Actual, Formal);
363                             if (Formal.Params != EAG.empty)
364                                 Error(Formal.Pos, "formal params not allowed here");
365                         }
366                         if (lexer.front == '(' || lexer.front == '[' || lexer.front == '{')
367                         {
368                             Pos = lexer.position;
369                             HNont = EAG.NewAnonymNont(Id);
370                             EAG.NewNont(Last, HNont, Actual, Pos);
371                             Actual.Params = EAG.empty;
372                             if (lexer.front == '(')
373                             {
374                                 lexer.popFront;
375                                 HyperExpr(HNont, Id, '(', HExpr, Pos);
376                                 if (lexer.front == ')')
377                                     lexer.popFront;
378                                 else
379                                     Error(lexer.position, "')' expected");
380                                 EAG.NewGrp(HNont, HExpr);
381                             }
382                             else
383                             {
384                                 Left = lexer.front.to!char;
385                                 lexer.popFront;
386                                 HyperExpr(HNont, Id, Left, HExpr, Pos);
387                                 Pos = lexer.position;
388                                 if (Left == '{')
389                                 {
390                                     if (lexer.front == '}')
391                                         lexer.popFront;
392                                     else
393                                         Error(lexer.position, "'}' expected");
394                                 }
395                                 else
396                                 {
397                                     if (lexer.front == ']')
398                                         lexer.popFront;
399                                     else
400                                         Error(lexer.position, "']' expected");
401                                 }
402                                 Params(Actual, Formal);
403                                 if (!EAG.SigOK(HNont))
404                                     Error(Formal.Pos, "formal params differ");
405                                 if (Left == '{')
406                                     EAG.NewRep(HNont, HExpr, Formal, Pos);
407                                 else
408                                     EAG.NewOpt(HNont, HExpr, Formal, Pos);
409                             }
410                         }
411                         else
412                         {
413                             return;
414                         }
415                     }
416                     if (First is null)
417                         First = Last;
418                 }
419             }
420 
421             EAG.Alt Last = null;
422 
423             HExpr = null;
424             while (true)
425             {
426                 EAG.ParamsDesc Actual;
427                 EAG.ParamsDesc Formal;
428                 EAG.ParamsDesc Formal1;
429                 EAG.Factor FirstF;
430                 EAG.Factor LastF;
431 
432                 Params(Actual, Formal);
433                 if (!EAG.SigOK(HNont))
434                     Error(Formal.Pos, "formal params differ");
435                 HyperTerm(Actual, FirstF, LastF);
436                 if (Left == '{' && Actual.Params == EAG.empty)
437                 {
438                     Params(Actual, Formal1);
439                     if (Formal1.Params != EAG.empty)
440                         Error(Formal1.Pos, "formal params not allowed here");
441                 }
442                 else if (Left != '{' && Actual.Params != EAG.empty)
443                 {
444                     Error(Actual.Pos, "actual params not allowed here");
445                     Actual.Params = EAG.empty;
446                 }
447                 EAG.NewAlt(Last, HNont, Formal, Actual, FirstF, LastF, AltPos);
448                 if (HExpr is null)
449                     HExpr = Last;
450                 if (lexer.front == '|')
451                 {
452                     AltPos = lexer.position;
453                     lexer.popFront;
454                 }
455                 else
456                 {
457                     break;
458                 }
459             }
460         }
461 
462         int HNont = EAG.FindHNont(Id);
463         int Sig;
464         EAG.Alt HExpr;
465 
466         if (!NameNotified && HNont == EAG.firstHNont && ErrorCounter == 0 && lexer.ok)
467         {
468             NameNotified = true;
469             SetBaseName;
470             info!"Analysing %s"(EAG.BaseName);
471         }
472         EAG.HNont[HNont].IsToken = EAG.HNont[HNont].IsToken || IsToken;
473 
474         EAG.ParamsDesc Actual;
475         EAG.ParamsDesc Formal;
476 
477         Params(Actual, Formal);
478         if (Actual.Params != EAG.empty)
479             Error(Actual.Pos, "actual params not allowed here");
480         if (Formal.Params != EAG.empty && EAG.SigOK(HNont))
481         {
482             Sig = EAG.HNont[HNont].Sig;
483             EAG.HNont[HNont].Sig = EAG.empty;
484         }
485 
486         Position AltPos;
487 
488         if (lexer.front == ':')
489         {
490             AltPos = lexer.position;
491             lexer.popFront;
492         }
493         else
494         {
495             Error(lexer.position, "':' expected");
496         }
497         HyperExpr(HNont, Id, '(', HExpr, AltPos);
498         if (Formal.Params != EAG.empty)
499             Distribute(HNont, HExpr, Sig, Formal);
500         EAG.NewGrp(HNont, HExpr);
501         if (lexer.front == '.')
502             lexer.popFront;
503         else
504             Error(lexer.position, "'.' expected");
505     }
506 
507     do
508     {
509         int Id;
510         bool IsToken = false;
511 
512         if (lexer.front == Token.name)
513         {
514             Id = lexer.value.to!int;
515             lexer.popFront;
516         }
517         else
518         {
519             Error(lexer.position, "identifier of rule expected");
520         }
521         if (lexer.front == Token.number)
522         {
523             Error(lexer.position, "number is not allowed here");
524             lexer.popFront;
525         }
526         if (lexer.front == '*')
527         {
528             IsToken = true;
529             lexer.popFront;
530         }
531         if (lexer.front == '=')
532             MetaRule(Id, IsToken);
533         else
534             HyperRule(Id, IsToken);
535         if (lexer.front != Token.name && lexer.front != Token.end)
536         {
537             Error(lexer.position, "not allowed symbol");
538             do
539                 lexer.popFront;
540             while (lexer.front != '.' && lexer.front != Token.end);
541             if (lexer.front != Token.end)
542                 lexer.popFront;
543             Error(lexer.position, "    restart point");
544         }
545     }
546     while (lexer.front != Token.end);
547     ErrorCounter += lexer.ok ? 0 : 1;
548 }
549 
550 void CheckSemantics()
551 {
552     void Shrink(int Sym)
553     {
554         if (EAG.HNont[Sym].Id >= 0 && cast(EAG.Grp) EAG.HNont[Sym].Def)
555         {
556             EAG.Alt A = (cast(EAG.Grp) EAG.HNont[Sym].Def).Sub;
557 
558             if (A.Formal.Params == EAG.empty && A.Next is null && A.Sub !is null && cast(EAG.Nont) A.Sub)
559             {
560                 EAG.Nont F = cast(EAG.Nont) A.Sub;
561 
562                 if (EAG.HNont[F.Sym].anonymous && F.Actual.Params == EAG.empty && F.Next is null)
563                 {
564                     EAG.HNont[Sym].Def = EAG.HNont[F.Sym].Def;
565                     EAG.HNont[F.Sym].Def = null;
566                     EAG.HNont[Sym].Sig = EAG.HNont[F.Sym].Sig;
567                     A = EAG.HNont[Sym].Def.Sub;
568                     do
569                     {
570                         A.Up = Sym;
571                         A = A.Next;
572                     }
573                     while (A !is null);
574                 }
575             }
576         }
577     }
578 
579     void Traverse(int Sym)
580     {
581         void CheckParamList(int Dom, EAG.ParamsDesc Par, bool Lhs)
582         {
583             import std.math : abs;
584 
585             int P = Par.Params;
586 
587             while (EAG.DomBuf[Dom] != nil && EAG.ParamBuf[P].Affixform != nil)
588             {
589                 EAG.ParamBuf[P].isDef = Lhs && EAG.DomBuf[Dom] < 0 || !Lhs && EAG.DomBuf[Dom] > 0;
590                 Earley.Parse(abs(EAG.DomBuf[Dom]), EAG.ParamBuf[P].Affixform,
591                         EAG.ParamBuf[P].Affixform, EAG.ParamBuf[P].isDef);
592                 if (EAG.ParamBuf[P].Affixform == EAG.nil)
593                     ++ErrorCounter;
594                 ++Dom;
595                 ++P;
596             }
597             if (EAG.DomBuf[Dom] != EAG.ParamBuf[P].Affixform)
598             {
599                 Error(Par.Pos, "number of affixforms differs from signature");
600             }
601         }
602 
603         void CheckActual(EAG.Nont F)
604         {
605             if (EAG.WellMatched(EAG.HNont[F.Sym].Sig, EAG.empty)
606                     && F.Actual.Params != EAG.empty
607                     && F.Next !is null
608                     && cast(EAG.Nont) F.Next
609                     && (cast(EAG.Nont) F.Next).Actual.Params == EAG.empty
610                     && EAG.HNont[(cast(EAG.Nont) F.Next).Sym].anonymous)
611             {
612                 (cast(EAG.Nont)F.Next).Actual = F.Actual;
613                 F.Actual.Params = EAG.empty;
614             }
615         }
616 
617         void CheckRep(EAG.Alt A)
618         {
619             if (A.Last !is null)
620                 if (auto F = cast(EAG.Nont) A.Last)
621                 {
622                     if (EAG.WellMatched(EAG.HNont[F.Sym].Sig, EAG.empty)
623                             && F.Actual.Params != EAG.empty
624                             && A.Actual.Params == EAG.empty)
625                     {
626                         A.Actual = F.Actual;
627                         F.Actual.Params = EAG.empty;
628                     }
629                 }
630         }
631 
632         EAG.Rule Node = EAG.HNont[Sym].Def;
633         const Sig = EAG.HNont[Sym].Sig;
634 
635         if (Node !is null)
636         {
637             if (auto rep = cast(EAG.Rep) Node)
638             {
639                 EAG.Scope = EAG.NextVar;
640                 rep.Scope.Beg = EAG.NextVar;
641                 CheckParamList(Sig, rep.Formal, true);
642                 rep.Scope.End = EAG.NextVar;
643             }
644             else if (auto opt = cast(EAG.Opt) Node)
645             {
646                 EAG.Scope = EAG.NextVar;
647                 opt.Scope.Beg = EAG.NextVar;
648                 CheckParamList(Sig, opt.Formal, true);
649                 opt.Scope.End = EAG.NextVar;
650             }
651 
652             EAG.Alt A = Node.Sub;
653 
654             do
655             {
656                 EAG.Scope = EAG.NextVar;
657                 A.Scope.Beg = EAG.NextVar;
658                 CheckParamList(Sig, A.Formal, true);
659                 if (cast(EAG.Rep) Node)
660                 {
661                     CheckRep(A);
662                     CheckParamList(Sig, A.Actual, false);
663                 }
664 
665                 EAG.Factor F = A.Sub;
666 
667                 while (F !is null)
668                 {
669                     if (auto nont = cast(EAG.Nont) F)
670                     {
671                         CheckActual(nont);
672                         CheckParamList(EAG.HNont[nont.Sym].Sig, nont.Actual, false);
673                     }
674                     F = F.Next;
675                 }
676                 A.Scope.End = EAG.NextVar;
677                 A = A.Next;
678             }
679             while (A !is null);
680         }
681     }
682 
683     EAG.All = BitArray();
684     EAG.All.length = EAG.NextHNont + 1;
685     if (EAG.firstHNont == EAG.NextHNont)
686     {
687         ++ErrorCounter;
688         error!"EAG needs at least one hyper-rule";
689     }
690     for (int Sym = EAG.firstHNont; Sym < EAG.NextHNont; ++Sym)
691     {
692         if (EAG.HNont[Sym].Def is null)
693         {
694             if (EAG.HNont[Sym].Id >= 0)
695             {
696                 ++ErrorCounter;
697                 error!"hyper-nonterminal %s undefined"(EAG.symbolTable.symbol(EAG.HNont[Sym].Id));
698             }
699         }
700         else
701         {
702             EAG.All[Sym] = true;
703             Shrink(Sym);
704         }
705     }
706     for (int Sym = EAG.firstMNont; Sym < EAG.NextMNont; ++Sym)
707     {
708         if (EAG.MNont[Sym].MRule == nil)
709         {
710             ++ErrorCounter;
711             error!"meta-nonterminal %s undefined"(EAG.symbolTable.symbol(EAG.MNont[Sym].Id));
712         }
713     }
714     if (ErrorCounter == 0)
715     {
716         for (int Sym = EAG.firstHNont; Sym < EAG.NextHNont; ++Sym)
717             Traverse(Sym);
718         for (int n = EAG.firstVar; n < EAG.NextVar; ++n)
719         {
720             if (EAG.Var[n].Num < 0 && EAG.Var[n].Neg == EAG.nil)
721                 Error(EAG.Var[n].Pos, "! operator not allowed");
722             if (!EAG.Var[n].Def)
723             {
724                 import std.format : format;
725 
726                 Error(EAG.Var[n].Pos, format!"variable %s never on defining position"(EAG.VarRepr(n)));
727             }
728         }
729         if (EAG.DomBuf[EAG.HNont[EAG.StartSym].Sig] == EAG.nil
730                 || EAG.DomBuf[EAG.HNont[EAG.StartSym].Sig] < 0
731                 || EAG.DomBuf[EAG.HNont[EAG.StartSym].Sig + 1] != EAG.nil)
732         {
733             ++ErrorCounter;
734             error!"start symbol %s must have exactly one synthesized attribute"(
735                     EAG.symbolTable.symbol(EAG.HNont[EAG.StartSym].Id));
736         }
737         if (EAG.firstMNont == EAG.NextMNont)
738         {
739             ++ErrorCounter;
740             error!"EAG needs at least one meta-rule";
741         }
742     }
743 }
744 
745 void ComputeEAGSets()
746 {
747     struct EdgeRecord
748     {
749         EAG.Alt Dest;
750         int Next;
751     }
752 
753     EdgeRecord[] Edge;
754     int NextEdge;
755     int[] Deg;
756     int[] Stack;
757     int Top;
758     BitArray Prod;
759 
760     void ComputeReach(int Sym)
761     {
762         EAG.Alt A = EAG.HNont[Sym].Def.Sub;
763 
764         EAG.Reach[Sym] = true;
765         do
766         {
767             for (EAG.Factor F = A.Sub; F !is null; F = F.Next)
768                 if (auto nont = cast(EAG.Nont) F)
769                     if (!EAG.Reach[nont.Sym])
770                         ComputeReach(nont.Sym);
771             A = A.Next;
772         }
773         while (A !is null);
774     }
775 
776     void NewEdge(int From, EAG.Alt To)
777     {
778         Edge[NextEdge].Dest = To;
779         Edge[NextEdge].Next = Edge[From].Next;
780         Edge[From].Next = NextEdge;
781         ++NextEdge;
782     }
783 
784     void TestDeg(EAG.Alt A)
785     {
786         if (Deg[A.Ind] == 0)
787         {
788             if (!Prod[A.Up])
789             {
790                 Prod[A.Up] = true;
791                 Stack[Top] = A.Up;
792                 ++Top;
793             }
794         }
795     }
796 
797     void Prune()
798     {
799         int E;
800         EAG.Alt A;
801         while (Top > 0)
802         {
803             --Top;
804             E = Edge[Stack[Top]].Next;
805             while (E != nil)
806             {
807                 A = Edge[E].Dest;
808                 --Deg[A.Ind];
809                 TestDeg(A);
810                 E = Edge[E].Next;
811             }
812         }
813     }
814 
815     long Warnings = 0;
816 
817     EAG.Reach = BitArray();
818     EAG.Reach.length = EAG.NextHNont + 1;
819 
820     ComputeReach(EAG.StartSym);
821     for (int Sym = EAG.firstHNont; Sym < EAG.NextHNont; ++Sym)
822         if (EAG.HNont[Sym].Def !is null && !EAG.Reach[Sym] && EAG.HNont[Sym].Id >= 0)
823             ++Warnings;
824     Deg = new int[EAG.NextHAlt];
825     Stack = new int[EAG.NextHNont];
826     Top = 0;
827     Edge = new EdgeRecord[EAG.NextHNont + EAG.NONont + 1];
828     NextEdge = EAG.NextHNont;
829     for (int Sym = EAG.firstHNont; Sym < EAG.NextHNont; ++Sym)
830         Edge[Sym].Next = nil;
831     EAG.Null = BitArray();
832     EAG.Null.length = EAG.NextHNont + 1;
833     Prod = BitArray();
834     Prod.length = EAG.NextHNont + 1;
835     for (int Sym = EAG.firstHNont; Sym < EAG.NextHNont; ++Sym)
836     {
837         if (EAG.HNont[Sym].Def !is null)
838         {
839             if (cast(EAG.Opt) EAG.HNont[Sym].Def || cast(EAG.Rep) EAG.HNont[Sym].Def)
840             {
841                 Prod[Sym] = true;
842                 Stack[Top] = Sym;
843                 ++Top;
844             }
845 
846             EAG.Alt A = EAG.HNont[Sym].Def.Sub;
847 
848             do
849             {
850                 bool TermFound = false;
851 
852                 Deg[A.Ind] = 0;
853                 for (EAG.Factor F = A.Sub; F !is null; F = F.Next)
854                 {
855                     if (cast(EAG.Term) F)
856                     {
857                         TermFound = true;
858                     }
859                     else if (auto nont = cast(EAG.Nont) F)
860                     {
861                         ++Deg[A.Ind];
862                         NewEdge(nont.Sym, A);
863                     }
864                 }
865                 if (TermFound)
866                     Deg[A.Ind] += int.min;
867                 else
868                     TestDeg(A);
869                 A = A.Next;
870             }
871             while (A !is null);
872         }
873     }
874     Prune;
875     EAG.Null = Prod.dup;
876     for (int Sym = EAG.firstHNont; Sym < EAG.NextHNont; ++Sym)
877     {
878         if (EAG.HNont[Sym].Def !is null)
879         {
880             EAG.Alt A = EAG.HNont[Sym].Def.Sub;
881 
882             do
883             {
884                 if (Deg[A.Ind] < 0)
885                 {
886                     Deg[A.Ind] -= int.min;
887                     TestDeg(A);
888                 }
889                 A = A.Next;
890             }
891             while (A !is null);
892         }
893     }
894     Prune;
895     EAG.Prod = Prod;
896     Warnings += (EAG.All & ~EAG.Prod).count;
897     if (Warnings > 0)
898         warn!"%s warnings"(Warnings);
899 }
900 
901 void Analyse(Input input)
902 {
903     EAG.Init;
904     lexer = Lexer(input, EAG.symbolTable);
905     Earley.Init;
906     ErrorCounter = 0;
907     NameNotified = false;
908     Specification;
909     if (ErrorCounter == 0)
910     {
911         CheckSemantics;
912         Earley.Finit;
913     }
914     if (ErrorCounter == 0)
915     {
916         ComputeEAGSets;
917     }
918     if (ErrorCounter == 0)
919     {
920         EAG.History |= EAG.analysed;
921         info!"%s grammar is valid"(EAG.BaseName);
922     }
923     else
924     {
925         EAG.History &= ~EAG.analysed;
926         if (NameNotified)
927             info!"errors in %s"(EAG.BaseName);
928         else
929             info!"errors";
930     }
931 }
932 
933 void Warnings()
934 in (EAG.Performed(EAG.analysed))
935 {
936     const Unreach = EAG.All - EAG.Reach;
937     const Unprod = EAG.All - EAG.Prod;
938     const NoWarnings = Unreach.bitsSet.empty && Unprod.bitsSet.empty;
939 
940     if (NoWarnings)
941     {
942         info!"Analyser: no warnings on %s's hyper-nonterminals"(EAG.BaseName);
943         return;
944     }
945     warn!"Analyser warnings on %s's hyper-nonterminals:"(EAG.BaseName);
946     for (int Sym = EAG.firstHNont; Sym < EAG.NextHNont; ++Sym)
947     {
948         if (Unreach[Sym] && EAG.HNont[Sym].Id >= 0)
949             warn!"%s unreachable"(EAG.HNontRepr(Sym));
950         if (Unprod[Sym])
951         {
952             if (EAG.HNont[Sym].anonymous)
953                 warn!"anonymous nonterminal in %s unproductive"(EAG.NamedHNontRepr(Sym));
954             else
955                 warn!"%s unproductive"(EAG.HNontRepr(Sym));
956         }
957     }
958 }

Page generated by adrdox