gamma.input.earley.ItemSet source code

1 module gamma.input.earley.ItemSet;
2 
3 import gamma.grammar.Alternative;
4 import gamma.grammar.Grammar;
5 import gamma.grammar.Nonterminal;
6 import gamma.grammar.Symbol;
7 import gamma.util.Indexed;
8 import gamma.input.earley.Item;
9 
10 class ItemSet : Indexed
11 {
12     private Item[] items_;
13 
14     private size_t index_;
15 
16     public static ItemSet initialItemSet(Alternative alternative, Grammar grammar)
17     {
18         ItemSet itemSet = new ItemSet(0);
19         Item item = Item.initialItem(alternative, itemSet);
20 
21         itemSet.items_ ~= item;
22         itemSet.closure(grammar);
23         return itemSet;
24     }
25 
26     public static ItemSet nextItemSet(ItemSet prevItemSet, Symbol symbol, Grammar grammar)
27     {
28         ItemSet itemSet = new ItemSet(prevItemSet.index_ + 1);
29 
30         foreach (item; prevItemSet.items_)
31             if (item.symbol == symbol)
32                 itemSet.items_ ~= Item.nextItem(item, null);
33         itemSet.closure(grammar);
34         return itemSet;
35     }
36 
37     private this(size_t index)
38     {
39         this.index_ = index;
40     }
41 
42     public Item[] items()
43     {
44         return this.items_;
45     }
46 
47     public override size_t index() const @nogc nothrow pure @safe
48     {
49         return this.index_;
50     }
51 
52     private void closure(Grammar grammar)
53     {
54         size_t length;
55 
56         // TODO: repetition only for self referential final items
57 
58         do
59         {
60             length = this.items_.length;
61             for (int i = 0; i < this.items_.length; ++i)
62             {
63                 Item item = this.items_[i];
64 
65                 if (item.isFinal)
66                 {
67                     Symbol lhsSymbol = item.alternative.lhs.symbol;
68                     ItemSet parent = item.parent;
69 
70                     for (int j = 0; j < parent.items_.length; ++j)
71                     {
72                         Item parentItem = parent.items_[j];
73 
74                         if (parentItem.symbol == lhsSymbol)
75                             add(Item.nextItem(parentItem, item));
76                     }
77                 } else if (cast(Nonterminal) item.symbol)
78                 {
79                     Nonterminal nonterminal = cast(Nonterminal) item.symbol;
80                     Alternative[] alternatives = grammar.ruleOf(nonterminal).alternatives;
81 
82                     foreach (alternative; alternatives)
83                         add(Item.initialItem(alternative, this));
84                 }
85             }
86         }
87         while (this.items_.length > length);
88     }
89 
90     private void add(Item item)
91     {
92         // TODO: report ambiguities
93 
94         foreach (otherItem; this.items_)
95             if (item.matches(otherItem))
96                 return;
97         this.items_ ~= item;
98     }
99 
100     public override string toString() const
101     {
102         import std.format : format;
103 
104         return format!"{%-(\n\t%s,%)\n}"(this.items_);
105     }
106 }