1 module trie; 2 3 import rules; 4 import std.array : front; 5 6 import std.stdio; 7 8 class Trie { 9 import std.array : appender, Appender; 10 Trie[] follow; 11 RulePart value; 12 SubRule subRule; 13 string[] subRuleNames; 14 string subRuleName; 15 string ruleName; 16 17 this() { 18 } 19 20 this(RulePart value) { 21 this.value = value; 22 } 23 24 override string toString() { 25 auto app = appender!string(); 26 foreach(f; follow) { 27 f.toString(app, 0); 28 } 29 30 return app.data; 31 } 32 33 void toString(Appender!string app, int indent) { 34 import std.format : formattedWrite; 35 import std.array : empty; 36 for(int i = 0; i < indent; ++i) { 37 formattedWrite(app, " "); 38 } 39 formattedWrite(app, "%s", this.value.name); 40 if(this.follow.empty) { 41 formattedWrite(app, " %s\n", this.subRuleName); 42 } else { 43 formattedWrite(app, "\n"); 44 } 45 foreach(f; this.follow) { 46 f.toString(app, indent + 1); 47 } 48 } 49 } 50 51 void printTrie(Trie t, int indent) { 52 import std.stdio; 53 for(int i = 0; i < indent; ++i) { 54 write(" "); 55 } 56 if(t.value !is null) { 57 writefln("%s %s", t.value.name, t.ruleName); 58 } else { 59 writeln(t.ruleName); 60 } 61 62 foreach(it; t.follow) { 63 printTrie(it, indent + 1); 64 } 65 } 66 67 Trie[] ruleToTrie(Rule rule) { 68 import std.array : back; 69 import std.uni : isUpper; 70 auto ret = new Trie; 71 72 foreach(subRule; rule.subRules) { 73 ruleToTrieRecur(ret, subRule, subRule.elements, rule.name); 74 } 75 76 return ret.follow; 77 } 78 79 void ruleToTrieRecur(Trie cur, SubRule sr, RulePart[] rp, string ruleName) { 80 import std.algorithm : sort, uniq; 81 import std.array : array; 82 Trie con; 83 84 // find the con(tinuing) Trie node 85 foreach(elem; cur.follow) { 86 if(elem.value.name == rp.front.name) { 87 con = elem; 88 } 89 } 90 91 if(con is null) { 92 con = new Trie(rp.front); 93 con.subRuleName = sr.name; 94 cur.follow ~= con; 95 } 96 97 con.subRuleNames ~= sr.name; 98 con.subRuleNames = con.subRuleNames.sort.uniq.array; 99 100 if(rp.length > 1) { 101 ruleToTrieRecur(con, sr, rp[1 .. $], ruleName); 102 } else { 103 //writefln("maybe something exists already rule '%s' subrule '%s'" 104 // ~ " overrite with '%s' '%s'", 105 // con.ruleName, con.subRuleName, sr.name, sr 106 // ); 107 con.ruleName = ruleName; 108 con.subRuleName = sr.name; 109 con.subRule = sr; 110 } 111 }