epsilon.predicates source code

1 module epsilon.predicates;
2 
3 import EAG = epsilon.eag;
4 import log;
5 import runtime;
6 import std.bitmanip : BitArray;
7 
8 void Check()
9 in (EAG.Performed(EAG.analysed))
10 {
11     struct EdgeRecord
12     {
13         size_t Dest;
14         int Next;
15     }
16 
17     int[] HNont;
18     EdgeRecord[] Edge;
19     int NextEdge;
20     size_t[] Stack;
21     int Top;
22     BitArray CoPred;
23     BitArray Pred;
24 
25     void NewEdge(int From, size_t To)
26     {
27         Edge[NextEdge].Dest = To;
28         Edge[NextEdge].Next = HNont[From];
29         HNont[From] = NextEdge;
30         ++NextEdge;
31     }
32 
33     void PutCoPred(size_t N)
34     {
35         if (!CoPred[N])
36         {
37             CoPred[N] = true;
38             Stack[Top] = N;
39             ++Top;
40         }
41     }
42 
43     void BuiltEdge()
44     {
45         for (size_t N = EAG.firstHNont; N < EAG.NextHNont; ++N)
46             HNont[N] = -1;
47         foreach (N; EAG.All.bitsSet)
48         {
49             if (!EAG.Null[N])
50                 PutCoPred(N);
51 
52             EAG.Alt A = EAG.HNont[N].Def.Sub;
53 
54             do
55             {
56                 for (EAG.Factor F = A.Sub; F !is null; F = F.Next)
57                     if (cast(EAG.Term) F)
58                         PutCoPred(N);
59                     else if (auto nont = cast(EAG.Nont) F)
60                         NewEdge(nont.Sym, N);
61                 A = A.Next;
62             }
63             while (A !is null);
64         }
65     }
66 
67     void ClearStack()
68     {
69         while (Top > 0)
70         {
71             --Top;
72 
73             int Dep = HNont[Stack[Top]];
74 
75             while (Dep >= 0)
76             {
77                 PutCoPred(Edge[Dep].Dest);
78                 Dep = Edge[Dep].Next;
79             }
80         }
81     }
82 
83     EAG.History &= ~EAG.predicates;
84     HNont = new int[EAG.NextHNont];
85     Edge = new  EdgeRecord[EAG.NONont + 1];
86     NextEdge = 0;
87     Stack = new size_t[EAG.NextHNont];
88     Top = 0;
89     CoPred = BitArray();
90     CoPred.length = EAG.NextHNont + 1;
91     BuiltEdge;
92     ClearStack;
93     Pred = EAG.Prod - CoPred;
94     Pred[EAG.StartSym] = false;
95     EAG.Pred = Pred;
96     EAG.History |= EAG.predicates;
97     List;
98 }
99 
100 private void List()
101 in (EAG.Performed(EAG.analysed | EAG.predicates))
102 {
103     import std.algorithm : map;
104     import std.format : format;
105 
106     info!"predicates in %s: %s"(EAG.BaseName, EAG.Pred.count);
107     if (EAG.Pred.count == 0)
108         return;
109 
110     string[] items;
111 
112     foreach (N; EAG.Pred.bitsSet)
113         if (EAG.HNont[N].anonymous)
114             items ~= format!"EBNF expression in %s\n%s"(EAG.NamedHNontRepr(N), EAG.HNont[N].Def.Sub.Pos);
115         else
116             items ~= format!"%s\n%s"(EAG.HNontRepr(N), EAG.HNont[N].Def.Sub.Pos);
117 
118     trace!"predicate occurrences in %s:%-(\n%s%)"(EAG.BaseName, items);
119 }