gamma.input.earley.Parser source code

1 module gamma.input.earley.Parser;
2 
3 import gamma.grammar.Alternative;
4 import gamma.grammar.Grammar;
5 import gamma.grammar.GrammarBuilder;
6 import gamma.grammar.Node;
7 import gamma.grammar.Nonterminal;
8 import gamma.grammar.Symbol;
9 import gamma.grammar.SymbolNode;
10 import gamma.grammar.Terminal;
11 import gamma.grammar.affixes.Composite;
12 import gamma.grammar.affixes.Term;
13 import gamma.grammar.affixes.Variable;
14 import gamma.input.earley.AffixForm;
15 import gamma.input.earley.Item;
16 import gamma.input.earley.ItemSet;
17 import std.range;
18 
19 /**
20  * If the item is of the form [ <i>B</i> &rarr; &beta; &bull;, <i>k</i> ] then for each item [ <i>A</i> &rarr;
21  * &alpha; &bull; <i>B</i> &gamma;, <i>j</i> ] in the Earley set denoted by <i>k</i> an item [ <i>A</i> &rarr;
22  * &alpha; <i>B</i> &bull; &gamma;, <i>j</i> ] is added to the current Earley set.
23  *
24  * If the item is of the form [ <i>A</i> &rarr; &alpha; &bull; <i>B</i> &gamma;, <i>j</i> ] then for each alternative
25  * <i>B</i> &rarr; &beta; an item [ <i>B</i> &rarr; &bull; &beta;, <i>k</i> ] is added to the current Earley set,
26  * which is denoted by <i>k</i>.
27  *
28  * If the item is of the form [ <i>A</i> &rarr; &alpha; &bull; <i>X</i> &gamma;, <i>i</i> ] where <i>X</i> equals
29  * the current symbol then an item [ <i>A</i> &rarr; &alpha; <i>X</i> &bull; &gamma;, <i>i</i> ] is added to the next
30  * Earley set.
31  */
32 public class Parser
33 {
34     private Grammar grammar;
35 
36     private Variable[] variablesIterator;
37 
38     // TODO: eliminate attributes 'startSymbol' and 'endSymbol'
39 
40     private Nonterminal startSymbol;
41 
42     private Terminal endSymbol;
43 
44     /**
45      * @param grammar
46      */
47     public this(Grammar grammar)
48     {
49         this.grammar = grammar;
50 
51         GrammarBuilder grammarBuilder;
52 
53         this.startSymbol = grammarBuilder.buildNonterminal("S'");
54         this.endSymbol = grammarBuilder.buildTerminal("$");
55     }
56 
57     /**
58      * @param startSymbol
59      * @param affixForm
60      * @return
61      */
62     public Term parse(Nonterminal startSymbol, AffixForm affixForm)
63     {
64         Node[] rhs;
65 
66         rhs ~= new SymbolNode(startSymbol, null);
67         rhs ~= new SymbolNode(this.endSymbol, null);
68 
69         Alternative alternative = new Alternative(new SymbolNode(this.startSymbol, null), rhs, null);
70         SymbolNode[] symbolNodes = affixForm.symbolNodes;
71 
72         symbolNodes ~= new SymbolNode(this.endSymbol, null);
73 
74         ItemSet itemSet = ItemSet.initialItemSet(alternative, grammar);
75 
76         foreach (symbolNode; symbolNodes)
77         {
78             Symbol symbol = symbolNode.symbol;
79 
80             itemSet = ItemSet.nextItemSet(itemSet, symbol, grammar);
81 
82             // TODO: report syntax errors
83         }
84         if (affixForm.variables !is null)
85             this.variablesIterator = affixForm.variables;
86         if (itemSet.items.empty)
87             return null;
88         else
89             return term(itemSet.items[0].prevItem);
90     }
91 
92     public Term term(Item item)
93     in (cast(Nonterminal) item.prevItem.symbol)
94     {
95         import std.array : array;
96 
97         if (item.subItem is null)
98         {
99             Variable variable = this.variablesIterator.back;
100 
101             assert(cast(Nonterminal) item.prevItem.symbol == variable.nonterminal);
102 
103             return variable;
104         }
105         else
106         {
107             Term[] terms;
108 
109             for (item = item.subItem; item.prevItem !is null; item = item.prevItem)
110                 if (cast(Nonterminal) item.prevItem.symbol)
111                     terms ~= term(item);
112             terms = terms.retro.array;
113             return new Composite(item.alternative, terms);
114         }
115     }
116 }