epsilon.earley source code

1 module epsilon.earley;
2 
3 import EAG = epsilon.eag;
4 import io : Position;
5 import runtime;
6 import std.stdio;
7 
8 const end = int.min;
9 const nil = EAG.nil;
10 const firstMSym = 1;
11 const firstItem = 1;
12 
13 struct MSymRecord
14 {
15     int Sym;
16     int Num;
17     Position Pos;
18 }
19 
20 struct ItemRecord
21 {
22     int Dot;
23     int Back;
24     int Left;
25     int Sub;
26 }
27 
28 MSymRecord[] MSymBuf;
29 int NextMSym;
30 ItemRecord[] ItemBuf;
31 int NextItem;
32 int CurList;
33 bool[] Predicted;
34 
35 void Expand() nothrow @safe
36 {
37     size_t NewLen(size_t ArrayLen)
38     {
39         assert(ArrayLen <= DIV(size_t.max, 2));
40 
41         return 2 * ArrayLen;
42     }
43 
44     if (NextMSym >= MSymBuf.length)
45     {
46         auto MSymBuf1 = new MSymRecord[NewLen(MSymBuf.length)];
47 
48         for (size_t i = firstMSym; i < MSymBuf.length; ++i)
49         {
50             MSymBuf1[i] = MSymBuf[i];
51         }
52         MSymBuf = MSymBuf1;
53     }
54     if (NextItem >= ItemBuf.length)
55     {
56         auto ItemBuf1 = new ItemRecord[NewLen(ItemBuf.length)];
57 
58         for (size_t i = firstItem; i < ItemBuf.length; ++i)
59         {
60             ItemBuf1[i] = ItemBuf[i];
61         }
62         ItemBuf = ItemBuf1;
63     }
64 }
65 
66 int StartAffixform() @nogc nothrow @safe
67 {
68     return NextMSym;
69 }
70 
71 void AppMSym(int Sym, int Num, Position Pos) nothrow @safe
72 {
73     if (NextMSym >= MSymBuf.length)
74     {
75         Expand;
76     }
77     MSymBuf[NextMSym].Sym = Sym;
78     MSymBuf[NextMSym].Num = Num;
79     MSymBuf[NextMSym].Pos = Pos;
80     ++NextMSym;
81 }
82 
83 void EndAffixform(Position Pos) nothrow @safe
84 {
85     AppMSym(end, 0, Pos);
86 }
87 
88 void CopyAffixform(int From, ref int To) nothrow @safe
89 {
90     To = NextMSym;
91     while (true)
92     {
93         AppMSym(MSymBuf[From].Sym, MSymBuf[From].Num, MSymBuf[From].Pos);
94         if (MSymBuf[From].Sym == end)
95             break;
96         else
97             ++From;
98     }
99 }
100 
101 void Parse(int Dom, int Affixform, ref int Tree, bool Def) @safe
102 {
103     void SimpleParse(int Dom, int Affixform, ref int Tree, bool Def)
104     {
105         int A;
106         int m;
107         int n;
108         if (MSymBuf[Affixform].Sym == Dom && MSymBuf[Affixform + 1].Sym == end)
109         {
110             Tree = -EAG.FindVar(MSymBuf[Affixform].Sym, MSymBuf[Affixform].Num,
111                     MSymBuf[Affixform].Pos, Def);
112         }
113         else
114         {
115             Tree = nil;
116             A = EAG.MNont[Dom].MRule;
117             do
118             {
119                 m = EAG.MAlt[A].Right;
120                 n = Affixform;
121                 while (EAG.MembBuf[m] == MSymBuf[n].Sym)
122                 {
123                     ++m;
124                     ++n;
125                 }
126                 if (EAG.MembBuf[m] == 0 && MSymBuf[n].Sym == end)
127                 {
128                     Tree = EAG.NextNode;
129                     EAG.NodeBuf[EAG.NextNode] = A;
130                     ++EAG.NextNode;
131                     if (EAG.NextNode >= EAG.NodeBuf.length)
132                     {
133                         EAG.Expand;
134                     }
135                     n = Affixform;
136                     while (MSymBuf[n].Sym != end)
137                     {
138                         if (MSymBuf[n].Sym > 0)
139                         {
140                             EAG.NodeBuf[EAG.NextNode] = -EAG.FindVar(MSymBuf[n].Sym,
141                                     MSymBuf[n].Num, MSymBuf[n].Pos, Def);
142                             ++EAG.NextNode;
143                             if (EAG.NextNode >= EAG.NodeBuf.length)
144                             {
145                                 EAG.Expand;
146                             }
147                         }
148                         ++n;
149                     }
150                     return;
151                 }
152                 A = EAG.MAlt[A].Next;
153             }
154             while (!(A == nil));
155         }
156     }
157 
158     void EarleyParse(int Dom, int Affixform, ref int Tree, bool Def)
159     {
160         int PrevList;
161         int CurSym;
162         int i;
163         void AddItem(int Dot, int Back, int Left, int Sub)
164         {
165             int I;
166             if (EAG.MembBuf[Dot] >= 0 || EAG.MembBuf[Dot] == MSymBuf[CurSym + 1].Sym)
167             {
168                 ItemBuf[NextItem].Dot = Dot;
169                 ItemBuf[NextItem].Back = Back;
170                 I = CurList;
171                 while (ItemBuf[I].Dot != Dot || ItemBuf[I].Back != Back)
172                 {
173                     ++I;
174                 }
175                 if (I == NextItem)
176                 {
177                     ItemBuf[NextItem].Left = Left;
178                     ItemBuf[NextItem].Sub = Sub;
179                     ++NextItem;
180                     if (NextItem >= ItemBuf.length)
181                     {
182                         Expand;
183                     }
184                 }
185                 ItemBuf[NextItem].Dot = nil;
186             }
187         }
188 
189         void Scanner()
190         {
191             int I;
192             int Sub;
193             if (MSymBuf[CurSym].Sym > 0)
194             {
195                 Sub = -EAG.FindVar(MSymBuf[CurSym].Sym, MSymBuf[CurSym].Num,
196                         MSymBuf[CurSym].Pos, Def);
197             }
198             else
199             {
200                 Sub = nil;
201             }
202             I = PrevList;
203             do
204             {
205                 if (EAG.MembBuf[ItemBuf[I].Dot] == MSymBuf[CurSym].Sym)
206                 {
207                     AddItem(ItemBuf[I].Dot + 1, ItemBuf[I].Back, I, Sub);
208                 }
209                 ++I;
210             }
211             while (!(ItemBuf[I].Dot == nil));
212         }
213 
214         void Closure()
215         {
216             int I;
217             int I1;
218             int I2;
219             int N;
220             int A;
221             bool Ready;
222             do
223             {
224                 I = CurList;
225                 Ready = true;
226                 do
227                 {
228                     if (EAG.MembBuf[ItemBuf[I].Dot] > 0)
229                     {
230                         N = EAG.MembBuf[ItemBuf[I].Dot];
231                         if (!Predicted[N])
232                         {
233                             A = EAG.MNont[N].MRule;
234                             do
235                             {
236                                 AddItem(EAG.MAlt[A].Right, CurList, nil, nil);
237                                 A = EAG.MAlt[A].Next;
238                             }
239                             while (!(A == nil));
240                             Predicted[N] = true;
241                         }
242                     }
243                     else if (EAG.MembBuf[ItemBuf[I].Dot] == 0)
244                     {
245                         N = EAG.MAlt[EAG.MembBuf[ItemBuf[I].Dot + 1]].Left;
246                         I1 = ItemBuf[I].Back;
247                         do
248                         {
249                             if (EAG.MembBuf[ItemBuf[I1].Dot] == N)
250                             {
251                                 I2 = NextItem;
252                                 AddItem(ItemBuf[I1].Dot + 1, ItemBuf[I1].Back, I1, I);
253                                 if (I2 < NextItem && ItemBuf[I1].Back == CurList)
254                                 {
255                                     Ready = false;
256                                 }
257                             }
258                             ++I1;
259                         }
260                         while (!(ItemBuf[I1].Dot == nil));
261                     }
262                     ++I;
263                 }
264                 while (!(I == NextItem));
265             }
266             while (!Ready);
267         }
268 
269         void Init(int Start)
270         {
271             int i;
272 
273             if (Predicted is null || Predicted.length < EAG.NextMNont)
274             {
275                 Predicted = new bool[EAG.NextMNont];
276             }
277             if (int.max - 3 >= EAG.NextMemb)
278             {
279                 EAG.NextMemb += 3;
280             }
281             else
282             {
283                 assert(0);
284             }
285             while (EAG.NextMemb >= EAG.MembBuf.length)
286             {
287                 EAG.Expand;
288             }
289             EAG.NextMemb -= 3;
290             EAG.MembBuf[EAG.NextMemb] = Start;
291             EAG.MembBuf[EAG.NextMemb + 1] = end;
292             EAG.MembBuf[EAG.NextMemb + 2] = 0;
293             EAG.MembBuf[EAG.NextMemb + 3] = EAG.NextMAlt;
294             EAG.MAlt[EAG.NextMAlt].Left = EAG.NextMNont;
295             EAG.MAlt[EAG.NextMAlt].Right = EAG.NextMemb;
296             NextItem = firstItem;
297             CurList = NextItem;
298             for (i = EAG.firstMNont; i < EAG.NextMNont; ++i)
299                 Predicted[i] = false;
300             AddItem(EAG.NextMemb, CurList, nil, nil);
301             Closure;
302         }
303 
304         void CreateTree(int I, ref int Tree)
305         {
306             int SubTree;
307             int A;
308             A = EAG.MembBuf[ItemBuf[I].Dot + 1];
309             EAG.NodeBuf[EAG.NextNode] = A;
310             Tree = EAG.NextNode;
311             if (int.max - EAG.MAlt[A].Arity - 1 >= EAG.NextNode)
312                 EAG.NextNode += EAG.MAlt[A].Arity + 1;
313             else
314                 assert(0);
315             while (EAG.NextNode >= EAG.NodeBuf.length)
316                 EAG.Expand;
317             SubTree = EAG.NextNode - 1;
318             do
319             {
320                 if (ItemBuf[I].Sub > 0)
321                 {
322                     CreateTree(ItemBuf[I].Sub, EAG.NodeBuf[SubTree]);
323                     --SubTree;
324                 }
325                 else if (ItemBuf[I].Sub < 0)
326                 {
327                     EAG.NodeBuf[SubTree] = ItemBuf[I].Sub;
328                     --SubTree;
329                 }
330                 I = ItemBuf[I].Left;
331             }
332             while (I != nil);
333         }
334 
335         CurSym = Affixform - 1;
336         Init(Dom);
337         do
338         {
339             PrevList = CurList;
340             ++NextItem;
341             CurList = NextItem;
342             if (NextItem >= ItemBuf.length)
343                 Expand;
344             for (i = EAG.firstMNont; i < EAG.NextMNont; ++i)
345                 Predicted[i] = false;
346             ++CurSym;
347             Scanner;
348             if (CurList == NextItem)
349             {
350                 import log : error;
351 
352                 error!"affixform incorrect\n%s"(MSymBuf[CurSym].Pos);
353                 Tree = nil;
354                 return;
355             }
356             else
357             {
358                 Closure;
359             }
360         }
361         while (!(MSymBuf[CurSym].Sym == end));
362         if (ItemBuf[ItemBuf[CurList].Left].Sub < 0)
363         {
364             Tree = ItemBuf[ItemBuf[CurList].Left].Sub;
365         }
366         else
367         {
368             CreateTree(ItemBuf[ItemBuf[CurList].Left].Sub, Tree);
369         }
370     }
371 
372     SimpleParse(Dom, Affixform, Tree, Def);
373     if (Tree == nil)
374     {
375         EarleyParse(Dom, Affixform, Tree, Def);
376     }
377 }
378 
379 void Init() nothrow @safe
380 {
381     MSymBuf = new MSymRecord[2047];
382     NextMSym = firstMSym;
383     ItemBuf = new ItemRecord[1023];
384     NextItem = firstItem;
385     Predicted = null;
386 }
387 
388 void Finit() @nogc nothrow @safe
389 {
390     MSymBuf = null;
391     ItemBuf = null;
392     Predicted = null;
393 }