pegged.dynamic.grammar source code

1 /**
2 Dynamic grammars:
3     - no CT parsing (this one will stay)
4     - no memoization (could be added)
5     - slightly less handy parameterized rules (could be better)
6     - no semantic actions (drat, this one is the worse)
7     - no calling from other grammars?
8 
9 Advantages:
10     - fully runtime configurable: change rules, add rules, delete rules.
11 */
12 module pegged.dynamic.grammar;
13 
14 import std.array;
15 import std.stdio;
16 
17 import pegged.peg;
18 import pegged.parser;
19 import pegged.dynamic.peg;
20 
21 struct ParameterizedRule
22 {
23     size_t numArgs;
24     Dynamic delegate(Dynamic[]) code;
25 
26     Dynamic opCall(D...)(D rules)
27     {
28         Dynamic[] args;
29         foreach(i,rule; rules)
30         {
31             static if (is(typeof(rule) == Dynamic))
32                 args ~= rule;
33             else
34                 args ~= rule(); // Dynamic delegate()
35         }
36 
37         if(rules.length == numArgs)
38         {
39             switch(numArgs)
40             {
41                 case 1:
42                     return code([args[0]]);
43                 case 2:
44                     return code([args[0], args[1]]);
45                 case 3:
46                     return code([args[0], args[1], args[2]]);
47                 case 4:
48                     return code([args[0], args[1], args[2], args[3]]);
49                 case 5:
50                     return code([args[0], args[1], args[2], args[3], args[4]]);
51                 case 6:
52                     return code([args[0], args[1], args[2], args[3], args[4], args[5]]);
53                 default:
54                     throw new Exception("Unimplemented parameterized rule with more than 6 arguments.");
55             }
56         }
57         else
58             throw new Exception( "ParameterizedRule called with "
59                                ~ to!string(rules.length)
60                                ~ " args. Waited for "
61                                ~ to!string(numArgs) ~ ".");
62         return code(args);
63     }
64 }
65 
66 ParameterizedRule parameterizedRule(size_t n, Dynamic delegate(Dynamic[] d) code)
67 {
68     ParameterizedRule pr;
69     pr.numArgs = n;
70     pr.code = code;
71     return pr;
72 }
73 
74 struct DynamicGrammar
75 {
76     string grammarName;
77     string startingRule;
78     Dynamic[string] rules;
79     ParameterizedRule[string] paramRules;
80 
81     ParseTree decimateTree(ParseTree p)
82     {
83         if(p.children.length == 0) return p;
84 
85         ParseTree[] filterChildren(ParseTree pt)
86         {
87             ParseTree[] result;
88             foreach(child; pt.children)
89             {
90                 if (  (child.name.startsWith(grammarName) && child.matches.length != 0)
91                    || !child.successful && child.children.length == 0)
92                 {
93                     child.children = filterChildren(child);
94                     result ~= child;
95                 }
96                 else if (child.name.startsWith("keep!(")) // 'keep' node are never discarded.
97                                                // They have only one child, the node to keep
98                 {
99                     result ~= child.children[0];
100                 }
101                 else // discard this node, but see if its children contain nodes to keep
102                 {
103                     result ~= filterChildren(child);
104                 }
105             }
106             return result;
107         }
108         p.children = filterChildren(p);
109         return p;
110     }
111 
112     ParseTree opCall(ParseTree p)
113     {
114         return decimateTree(rules[startingRule](p));
115         /+
116         result.children = [result];
117         result.name = grammarName;
118         return result;
119         +/
120     }
121 
122     ParseTree opCall(string input)
123     {
124         return decimateTree(rules[startingRule](ParseTree(``, false, [], input, 0, 0)));
125         /+
126         result.children = [result];
127         result.name = grammarName;
128         return result;
129         +/
130     }
131 
132     void opIndexAssign(D)(D code, string s)
133     {
134         rules[s]= named(code, grammarName ~ "." ~ s);
135     }
136 
137     Dynamic opIndex(string s)
138     {
139         return rules[s];
140     }
141 }
142 
143 // Helper to insert 'Spacing' before and after Primaries
144 ParseTree spaceArrow(ParseTree input)
145 {
146     ParseTree wrapInSpaces(ParseTree p)
147     {
148         ParseTree spacer =
149         ParseTree("Pegged.Prefix", true, null, null, 0,0, [
150             ParseTree("Pegged.Suffix", true, null, null, 0, 0, [
151                 ParseTree("Pegged.Primary", true, null, null, 0, 0, [
152                     ParseTree("Pegged.RhsName", true, null, null, 0,0, [
153                         ParseTree("Pegged.Identifier", true, ["Spacing"])
154                     ])
155                 ])
156             ])
157         ]);
158         ParseTree result = ParseTree("Pegged.WrapAround", true, p.matches, p.input, p.begin, p.end, p.children);
159         result.children = spacer ~ result.children ~ spacer;
160         return result;
161     }
162     return modify!( p => p.name == "Pegged.Primary",
163                     wrapInSpaces)(input);
164 }
165 
166 Dynamic makeRule(string def, Dynamic[string] context)
167 {
168     ParseTree p = Pegged.decimateTree(Pegged.Definition(def));
169     return makeRule(p, context);
170 }
171 
172 Dynamic makeRule(ParseTree def, Dynamic[string] context)
173 {
174     Dynamic code;
175 
176     Dynamic getDyn(string name)
177     {
178         if (name in context)
179             return context[name];
180         else
181             throw new Exception("Unknown name: " ~ name);
182     }
183 
184     Dynamic ruleFromTree(ParseTree p)
185     {
186         //writeln("rfT: ", p.name, " ", p.matches);
187         //Dynamic result;
188         switch(p.name)
189         {
190             case "Pegged.Expression":
191                 //if (p.children.length > 1) // OR expression
192                 //{
193                     Dynamic[] children;
194                     foreach(seq; p.children)
195                         children ~= ruleFromTree(seq);
196                     return distribute!(or)(children);
197                 //}
198                 //else // One child -> just a sequence, no need for a or!( , )
199                 //{
200                 //    return ruleFromTree(p.children[0]);
201                 //}
202                 //break;
203             case "Pegged.Sequence":
204                 //if (p.children.length > 1) // real sequence
205                 //{
206                     Dynamic[] children;
207                     foreach(seq; p.children)
208                         children ~= ruleFromTree(seq);
209                     return distribute!(pegged.dynamic.peg.and)(children);
210                 /+}
211                 else // One child -> just a Suffix, no need for a and!( , )
212                 {
213                     return ruleFromTree(p.children[0]);
214                 }
215                 +/
216             case "Pegged.Prefix":
217                 ParseTree temp;
218                 foreach_reverse(i,child; p.children[0..$-1]) // transforming a list into a linear tree
219                 {
220                     temp  = p.children[$-1];
221                     p.children[$-1] = child;
222                     p.children[$-1].children = [temp];
223                 }
224                 return ruleFromTree(p.children[$-1]);
225             case "Pegged.Suffix":
226                 foreach(child; p.children[1..$])
227                 {
228                     ParseTree temp = p.children[0];
229                     p.children[0] = child;
230                     p.children[0].children = [temp];
231                 }
232                 return ruleFromTree(p.children[0]);
233             case "Pegged.Primary":
234                 return ruleFromTree(p.children[0]);
235             case "Pegged.RhsName":
236                 return ruleFromTree(p.children[0]);
237             case "Pegged.Identifier":
238                 //writeln("Identifier: ", p.matches[0], " ");//, getDyn(p.matches[0])()(ParseTree()).name);
239                 return getDyn(p.matches[0]);
240             case "Pegged.Literal":
241                 //writeln("Literal: ", p.matches);
242                 if(p.matches.length == 3) // standard case
243                     return literal(p.matches[1]);
244                 else // only two children -> empty literal
245                     return eps();
246             case "Pegged.CharClass":
247                 if (p.children.length > 1)
248                 {
249                     Dynamic[] children;
250                     foreach(seq; p.children)
251                         children ~= ruleFromTree(seq);
252                     return distribute!(pegged.dynamic.peg.or)(children);
253                 }
254                 else // One child -> just a sequence, no need for a or!( , )
255                 {
256                     return ruleFromTree(p.children[0]);
257                 }
258                 //break;
259             case "Pegged.CharRange":
260                 /// Make the generation at the Char level: directly what is needed, be it `` or "" or whatever
261                 if (p.children.length > 1) // a-b range
262                 {
263                     return charRange(p.matches[0].front, p.matches[2].front);
264                 }
265                 else // lone char
266                 {
267                     //result = "pegged.peg.literal!(";
268                     string ch = p.matches[0];
269                     switch (ch)
270                     {
271                         case "\\[":
272                         case "\\]":
273                         case "\\-":
274                             return literal(ch[0..1]);
275                         case "\\\'":
276                             return literal("\'");
277                         case "\\`":
278                             return literal("`");
279                         case "\\":
280                         case "\\\\":
281                             return literal("\\");
282                         case "\"":
283                         case "\\\"":
284                             return literal("\"");
285                         case "\n":
286                         case "\r":
287                         case "\t":
288                             return literal(ch);
289                         default:
290                             return literal(ch);
291                     }
292                 }
293             case "Pegged.Char":
294                 string ch = p.matches[0];
295                 switch (ch)
296                 {
297                     case "\\[":
298                     case "\\]":
299                     case "\\-":
300 
301                     case "\\\'":
302                     case "\\\"":
303                     case "\\`":
304                     case "\\\\":
305                         return literal(ch[1..$]);
306                     case "\n":
307                     case "\r":
308                     case "\t":
309                         return literal(ch);
310                     default:
311                         return literal(ch);
312                 }
313                 //break;
314             case "Pegged.POS":
315                 return posLookahead(ruleFromTree(p.children[0]));
316             case "Pegged.NEG":
317                 return negLookahead(ruleFromTree(p.children[0]));
318             case "Pegged.FUSE":
319                 return fuse(ruleFromTree(p.children[0]));
320             case "Pegged.DISCARD":
321                 return discard(ruleFromTree(p.children[0]));
322             case "Pegged.KEEP":
323                 return keep(ruleFromTree(p.children[0]));
324             case "Pegged.DROP":
325                 return drop(ruleFromTree(p.children[0]));
326             case "Pegged.PROPAGATE":
327                 return propagate(ruleFromTree(p.children[0]));
328             case "Pegged.OPTION":
329                 return option(ruleFromTree(p.children[0]));
330             case "Pegged.ZEROORMORE":
331                 return zeroOrMore(ruleFromTree(p.children[0]));
332             case "Pegged.ONEORMORE":
333                 return oneOrMore(ruleFromTree(p.children[0]));
334             case "Pegged.Action":
335                 Dynamic result = ruleFromTree(p.children[0]);
336                 foreach(act; p.matches[1..$])
337                     result = action(result, getDyn(act));
338                 return result;
339             case "Pegged.ANY":
340                 return any();
341             case "Pegged.WrapAround":
342                 return wrapAround( ruleFromTree(p.children[0])
343                                         , ruleFromTree(p.children[1])
344                                         , ruleFromTree(p.children[2]));
345             default:
346                 throw new Exception("Bad tree: " ~ p.toString());
347         }
348     }
349 
350     switch(def.children[1].children[0].name)
351     {
352         case "Pegged.LEFTARROW":
353             code = ruleFromTree(def.children[2]);
354             break;
355         case "Pegged.FUSEARROW":
356             code = fuse(ruleFromTree(def.children[2]));
357             break;
358         case "Pegged.DISCARDARROW":
359             code = discard(ruleFromTree(def.children[2]));
360             break;
361         case "Pegged.KEEPARROW":
362             code = keep(ruleFromTree(def.children[2]));
363             break;
364         case "Pegged.DROPARROW":
365             code = drop(ruleFromTree(def.children[2]));
366             break;
367         case "Pegged.PROPAGATEARROW":
368             code = propagate(ruleFromTree(def.children[2]));
369             break;
370         case "Pegged.SPACEARROW":
371             ParseTree modified = spaceArrow(def.children[2]);
372             code = ruleFromTree(modified);
373             break;
374         case "Pegged.ACTIONARROW":
375             Dynamic actionResult = ruleFromTree(def.children[2]);
376             foreach(act; def.children[1].matches[1..$])
377                 actionResult = action(actionResult, getDyn(act));
378             code = actionResult;
379             break;
380         default:
381             throw new Exception("Unknow arrow: " ~ def.children[1].children[0].name);
382             //break;
383     }
384 
385     return named(code, def.matches[0]);
386 }
387 
388 DynamicGrammar grammar(string definition, Dynamic[string] context = null)
389 {
390     //writeln("Entering dyn gram");
391     ParseTree defAsParseTree = Pegged(definition);
392     //writeln(defAsParseTree);
393     if (!defAsParseTree.successful)
394     {
395         // To work around a strange bug with ParseTree printing at compile time
396         throw new Exception("Bad grammar input: " ~ defAsParseTree.toString(""));
397     }
398 
399     DynamicGrammar gram;
400     foreach(name, rule; context)
401     {
402         gram.rules[name] = rule;
403     }
404 
405     ParseTree p = defAsParseTree.children[0];
406 
407     string grammarName = p.children[0].matches[0];
408     string shortGrammarName = p.children[0].matches[0];
409     gram.grammarName = shortGrammarName;
410 
411     // Predefined spacing
412     gram.rules["Spacing"] = discard(zeroOrMore(or(literal(" "), literal("\t"), literal("\n"), literal("\r"))));
413 
414     ParseTree[] definitions = p.children[1 .. $];
415 
416     foreach(i,def; definitions)
417     {
418         gram[def.matches[0]] = fail();
419     }
420 
421     foreach(i,def; definitions)
422     {
423         string shortName = def.matches[0];
424 
425         if (i == 0)
426             gram.startingRule = shortName;
427         // prepending the global grammar name, to get a qualified-name rule 'Gram.Rule'
428         def.matches[0] = shortGrammarName ~ "." ~ def.matches[0];
429         gram.rules[shortName] = makeRule(def, gram.rules);
430     }
431 
432     return gram;
433 }
434 
435 Dynamic distribute(alias fun)(Dynamic[] args)
436 {
437     //mixin(makeSwitch(40));
438     switch(args.length)
439     {
440         case 1:
441             return fun(args[0]);
442         case 2:
443             return fun(args[0], args[1]);
444         case 3:
445             return fun(args[0], args[1], args[2]);
446         case 4:
447             return fun(args[0], args[1], args[2], args[3]);
448         case 5:
449             return fun(args[0], args[1], args[2], args[3], args[4]);
450         case 6:
451             return fun(args[0], args[1], args[2], args[3], args[4], args[5]);
452         default:
453             return fun(fun(args[0], args[1], args[2], args[3], args[4], args[5]), distribute!fun(args[6..$]));
454     }
455 }