gamma.input.earley.Item source code

1 module gamma.input.earley.Item;
2 
3 import gamma.grammar.Alternative;
4 import gamma.grammar.Node;
5 import gamma.grammar.Nonterminal;
6 import gamma.grammar.Symbol;
7 import gamma.grammar.SymbolNode;
8 import gamma.input.earley.ItemSet;
9 
10 /**
11  * This class represents an Earley item
12  *   [ <i>A</i> &rarr; &alpha; &bull; &beta;, <i>j</i> ],
13  * which means that &alpha; has been recognized since the construction of the Earley set
14  * denoted by <i>j</i>.
15  * <p>
16  * Predecessor links as well as causal links between items are added to be able to reconstruct
17  * a derivation. Each item of the form
18  *   [ <i>A</i> &rarr; &alpha; <i>X</i> &bull; &gamma;, <i>j</i> ]
19  * is linked to a predecessor
20  *   [ <i>A</i> &rarr; &alpha; &bull; <i>X</i> &gamma;, <i>j</i> ].
21  * Furthermore, each item of the form
22  *   [ <i>A</i> &rarr; &alpha; <i>B</i> &bull; &gamma;, <i>j</i> ]
23  * is linked to an item
24  *   [ <i>B</i> &rarr; &beta; &bull;, <i>k</i> ]
25  * by which it has been added in the completer step.
26  */
27 class Item
28 {
29     private Alternative alternative_;
30 
31     private int index;
32 
33     private Symbol symbol_;
34 
35     private ItemSet parent_;
36 
37     private Item prevItem_;
38 
39     private Item subItem_;
40 
41     public static Item initialItem(Alternative alternative, ItemSet parent)
42     {
43         return new Item(alternative, parent, null, null);
44     }
45 
46     public static Item nextItem(Item prevItem, Item subItem)
47     in (!prevItem.isFinal)
48     in (subItem is null || cast(Nonterminal) prevItem.symbol_)
49     {
50         return new Item(prevItem.alternative_, prevItem.parent_, prevItem, subItem);
51     }
52 
53     private this(Alternative alternative, ItemSet parent, Item prevItem, Item subItem)
54     {
55         this.alternative_ = alternative;
56         if (prevItem is null)
57             this.index = 0;
58         else
59             this.index = prevItem.index + 1;
60         if (this.index < alternative.rhs.length)
61             this.symbol_ = (cast(SymbolNode) alternative.rhs[this.index]).symbol;
62         else
63             this.symbol_ = null;
64         this.parent_ = parent;
65         this.prevItem_ = prevItem;
66         this.subItem_ = subItem;
67     }
68 
69     public bool matches(Item item)
70     {
71         return item.alternative_ == this.alternative_ && item.index == this.index && item.parent_ == this.parent_;
72     }
73 
74     public bool isFinal()
75     {
76         return this.symbol is null;
77     }
78 
79     public Alternative alternative()
80     {
81         return this.alternative_;
82     }
83 
84     public Symbol symbol()
85     {
86         return this.symbol_;
87     }
88 
89     public ItemSet parent()
90     {
91         return this.parent_;
92     }
93 
94     public Item prevItem()
95     {
96         return this.prevItem_;
97     }
98 
99     public Item subItem()
100     {
101         return this.subItem_;
102     }
103 
104     public override string toString()
105     {
106         import std.array : appender;
107         import std.conv : to;
108 
109         auto writer = appender!string;
110 
111         with (this.alternative_)
112         {
113             writer.put("[ ");
114             writer.put(lhs.symbol.toString);
115             writer.put(" ->");
116             foreach (i; 0 .. this.index)
117             {
118                 writer.put(" ");
119                 writer.put((cast(SymbolNode) rhs[i]).symbol.toString);
120             }
121             writer.put(" .");
122             foreach (i; this.index .. rhs.length)
123             {
124                 writer.put(" ");
125                 writer.put((cast(SymbolNode) rhs[i]).symbol.toString);
126             }
127             writer.put(", ");
128             writer.put(this.parent_.index.to!string);
129             writer.put(" ]");
130         }
131         return writer[];
132     }
133 }