Mercury library 1.0 Translation of CFG grammars into an object model (Bachelor's thesis).

- Main Page
- Packages
- Classes
- Files

- File List

All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties
Interpreter.cs
Go to the documentation of this file.
1 using Mercury.Nucleus.Trees;
2 using Mercury.Syntax;
3 using System;
4 using System.Collections.Generic;
5 using System.Linq;
6 using System.Runtime.Caching;
7 using System.Threading.Tasks;
8
9 namespace Mercury.Interpreting
10 {
11 //=============================================================================
12 // IInterpreter
13 //=============================================================================
14
20 public interface IInterpreter<T> where T : class
21 {
23 RewriteRuleCollection<T> RewriteRules { get; }
24
28 InterpreterResult<T> Interpret(Tree<Symbol> tree);
29
30
36 IReadOnlyList<InterpreterResult<T>> Interpret(IReadOnlyList<Tree<Symbol>> trees);
37 }
38
39 //=============================================================================
40 // Interpreter
41 //=============================================================================
42
57 public class Interpreter<T> : IInterpreter<T> where T : class
58 {
59 //--[ Private fields ]-----------------------------------------------
60
61 private IInterpreterContextFactory contextFactory;
62 private bool logging;
63 private int boostlim;
64
65 //--[ Private types ]------------------------------------------------
66
67 #region [ Wildcard Context ]
68
69 private struct WildcardContext
70 {
71 public Wildcard wildcard; // wildcard
72 public int strcix; // index in structure
73 public int treeix; // start subtree index
74 public int treecnt; // subtree count
75 public int instcnt; // instances count
76
77 public WildcardContext(Wildcard w, int six, int tix, int tc, int ic)
78 {
79 wildcard = w;
80 strcix = six; treeix = tix;
81 treecnt = tc; instcnt = ic;
82 }
83 }
84
85 #endregion
86
87 //--[ Private methods ]----------------------------------------------
88
89 #region [ Structure matching ]
90
91 // Instantiate wrapper
92 private bool Instantiate(IElement element, Tree<Symbol> tree, InstanceList instances)
93 {
94 switch(element.Type)
95 {
96 case ElementType.Constant: return Instantiate(element as Constant, tree, instances);
97 case ElementType.Variable: return Instantiate(element as Variable, tree, instances);
98 case ElementType.Structure: return Instantiate(element as Structure, tree, instances);
99 default: return false;
100 }
101 }
102
103 // Instantiates constant
104 private bool Instantiate(Constant constant, Tree<Symbol> tree, InstanceList instances)
105 { return constant.MatchesSymbol(tree.Value); }
106
107 // Instantiates variable
108 private bool Instantiate(Variable variable, Tree<Symbol> tree, InstanceList instances)
109 {
110 if (!variable.MatchesSymbol(tree.Value))
111 return false;
112
113 instances.Add(new Instance(variable, tree));
114 return true;
115 }
116
117 // Instantiates structure and all subelemenets recursively
118 private bool Instantiate(Structure structure, Tree<Symbol> tree, InstanceList instances)
119 {
120 int scc = structure.Children.Count;
121 int tcc = tree.Children.Count;
122
123 if (!structure.HasWildcard && (scc != tcc)) return false;
124
125 int strcix = 0, treeix = 0;
126 Stack<WildcardContext> stack = new Stack<WildcardContext>();
127
128 if ((structure.Value.Type != ElementType.Wildcard) && !Instantiate(structure.Value, tree, instances))
129 return false;
130
131 while(true)
132 {
133 if ((strcix >= scc) && (treeix >= tcc)) break;
134
135 bool status = true;
136
137 Structure strct;
138 if ((strcix >= scc) || ((treeix >= tcc) && (structure[strcix].Value.Type != ElementType.Wildcard)))
139 status = false;
140 else if ((strct = structure[strcix] as Structure) != null)
141 status = Instantiate(strct, tree[treeix], instances);
142 else if (structure[strcix].Value.Type == ElementType.Wildcard)
143 {
144 stack.Push(new WildcardContext(
145 structure[strcix].Value as Wildcard,
146 strcix, treeix, 0, instances.Count));
147 instances.Add(new Instance(stack.Peek().wildcard, new Tree<Symbol>[0]));
148 --treeix;
149 }
150 else
151 status = Instantiate(structure[strcix].Value, tree[treeix], instances);
152
153 if (!status && !Retry(stack, tree, instances, ref strcix, ref treeix))
154 return false;
155
156 ++strcix;
157 ++treeix;
158 }
159
160 return true;
161 }
162
163 // Recovery from wildcard mismatch
164 private bool Retry(Stack<WildcardContext> stack, Tree<Symbol> tree, InstanceList instances, ref int sx, ref int tx)
165 {
166 while(stack.Count != 0)
167 {
168 WildcardContext context = stack.Pop();
169 instances.RemoveLast(instances.Count - context.instcnt);
170
171 sx = context.strcix;
172 tx = context.treeix + (context.treecnt++);
173
174 if ((tx >= tree.Children.Count) || !context.wildcard.MatchesSymbol(tree[tx].Value))
175 continue;
176
177 var data = new Tree<Symbol>[context.treecnt];
178 for (int ix = 0; ix < context.treecnt; ++ix)
179 data[ix] = tree[context.treeix + ix];
180
181 stack.Push(context);
182 instances.Add(new Instance(context.wildcard, data));
183 return true;
184 }
185
186 return false;
187 }
188
189 #endregion
190
191 #region [ Argument processing ]
192
193 private Argument GetArgument(Tree<Symbol> tree, ArgumentType reqtype)
194 {
195 switch (reqtype & ArgumentType.ParserEntity)
196 {
197 case ArgumentType.Tree: return new Argument(ArgumentType.Tree, tree);
198 case ArgumentType.Symbol: return new Argument(ArgumentType.Symbol, tree.Value);
199
200 default:
201 case ArgumentType.ParserEntity: if (!tree.IsLeaf) goto case ArgumentType.Tree;
202 else goto case ArgumentType.Symbol;
203 }
204 }
205
206 private Argument[] ExpandWildcard(Instance instance, ArgumentType required)
207 {
208 if (instance.Var == null || !(instance.Var is Wildcard))
209 throw new InvalidOperationException("This is not a wildcard");
210
211 var data = instance.Value as Tree<Symbol>[];
212 var args = new Argument[data.Length];
213
214 for(int ix = 0; ix < data.Length; ++ix)
215 args[ix] = GetArgument(data[ix] as Tree<Symbol>, required);
216
217 return args;
218 }
219
220 private Argument[] GetArguments(ActionCall<T> call, InstanceList instances, InterpreterContext<T> context)
221 {
222 List<Argument> args = new List<Argument>();
223
224 for(int ix = 0; ix < call.FormalParameters.Count; ++ix)
225 {
226 ArgumentType argtype = ArgumentType.TValue;
227
228 switch (call.FormalParameters[ix].Type)
229 {
230 case ParameterType.IntegralConstant: argtype = ArgumentType.Integer; goto constant;
231 case ParameterType.RealConstant: argtype = ArgumentType.Real; goto constant;
232 case ParameterType.StringConstant: argtype = ArgumentType.String; goto constant;
233 case ParameterType.BooleanConstant: argtype = ArgumentType.Boolean; goto constant;
234
235 constant:
236 args.Add(new Argument(argtype, (call.FormalParameters[ix] as ConstantParameter).Value));
237 break;
238
239 case ParameterType.Variable:
240 VariableParameter varparam = call.FormalParameters[ix] as VariableParameter;
241 Instance instance = instances[varparam.Name];
242 ArgumentType reqtp = call.Action.ArgumentTypes.ElementAtOrLast(ix);
243
244 if (instance.Var.Type == ElementType.Variable)
245 args.Add(GetArgument(instance.Value as Tree<Symbol>, reqtp));
246 else
247 args.AddRange(ExpandWildcard(instance, reqtp));
248
249 break;
250
251 case ParameterType.ActionCall:
252 var xcall = call.FormalParameters[ix] as ActionCall<T>;
253 var xargs = GetArguments(xcall, instances, context);
254 var xctp = call.Action.ArgumentTypes.ElementAtOrLast(ix);
255
256 args.Add(new Evaluator<T>(xcall.Action, xargs, InterpretTree, context));
257 break;
258 }
259 }
260
261 return args.ToArray();
262 }
263
264 #endregion
265
266 private T ExecuteAction(ActionCall<T> actioncall, InstanceList instances,
267 InterpreterContext<T> context)
268 { return new Evaluator<T>(actioncall.Action, GetArguments(actioncall, instances, context),
269 InterpretTree, context).Value as T; }
270
271 private T InterpretTree(Tree<Symbol> tree, InterpreterContext<T> context)
272 {
273 if (tree == null) return null;
274
275 var tentry = new TreeEntry<T>(tree);
276
277 if (context.hroot == null) context.hroot = tentry;
278 else context.cnode.Entries.Add(tentry);
279
280 #region [ Caching ]
281 if (context.cache != null)
282 {
283 var tup = context.cache.Get(tree.CacheKey) as Tuple<T,byte>;
284 if (tup != null)
285 {
286 tentry.Rules.Add(new MemoEntry<T>() { MemoizedValue = tup.Item1 });
287 tentry.Succeeded = tup.Item1 != null;
288 return tup.Item1;
289 }
290 }
291 #endregion
292
293 var reqtp = Defaults.TypeToArgType<T, T>();
294 var instances = new InstanceList();
295
296 InterpreterContext<T> ctxtcpy = null;
297 T result = null;
298
299 foreach (var rule in RewriteRules.RulesFor(tree.Value))
300 {
301 var rentry = new RuleEntry<T>(rule);
302 tentry.Rules.Add(rentry);
303
304 ctxtcpy = context.InternalClone(rentry);
305 ctxtcpy.reqtp = reqtp;
306
307 bool match = Instantiate(rule.LHS, tree, instances);
308 if (match && (result = ExecuteAction(rule.RHS, instances, ctxtcpy)) != null)
309 context.InternalCopy(ctxtcpy);
310
311 rentry.Match = match;
312 rentry.Value = result;
313 rentry.Error = false;
314 rentry.Instances = match ? instances : null;
315
316 instances = new InstanceList();
317
318 if (result != null)
319 break;
320 }
321
322 #region [ Caching ]
323 if (context.cache != null)
324 context.cache.Add(new CacheItem(tree.CacheKey, Tuple.Create(result, (byte)0)),
325 new CacheItemPolicy() { SlidingExpiration = TimeSpan.FromSeconds(20.0) });
326 #endregion
327
328 tentry.Succeeded = result != null;
329 return result;
330 }
331
332 private InterpreterResult<T> Interpret(Tree<Symbol> tree, MemoryCache cache)
333 {
334 var val = default(T);
335 var ex = null as Exception;
336 var context = contextFactory.CreateContext<T>();
337 context.cache = cache;
338
339 try
340 {
341 val = InterpretTree(tree, context);
342 if (!logging)
343 context.hroot = null; // GC will take care of that
344 }
345 catch (Exception e)
346 { ex = e; }
347 finally
348 { context.cache = null; }
349
350 return new InterpreterResult<T>() { Input = tree, Result = val, Exception = ex, Context = context };
351 }
352
353 //--[ Constructors ]-------------------------------------------------
354
367 public Interpreter(RewriteRuleCollection<T> rules, IInterpreterContextFactory factory,
368 bool logging = true, int boostlim = 4)
369 {
370 if (rules == null) throw new ArgumentNullException("rules");
371
372 RewriteRules = rules;
373 contextFactory = factory ?? new EmptyContextFactory();
374
375 this.logging = logging;
376 this.boostlim = boostlim;
377 }
378
379 //--[ Properties ]---------------------------------------------------
380
382 public RewriteRuleCollection<T> RewriteRules { get; private set; }
383
384 //--[ Interface implementation ]-------------------------------------
385
386 #region [ IInterpreter ]
387
391 public InterpreterResult<T> Interpret(Tree<Symbol> tree)
392 { return Interpret(tree, null); }
393
401 public IReadOnlyList<InterpreterResult<T>> Interpret(IReadOnlyList<Tree<Symbol>> trees)
402 {
403 var res = new InterpreterResult<T>[trees.Count];
404
405 if (trees.Count >= boostlim)
406 using(var cache = new MemoryCache(Extensions.RandomString("TreeCache%*")))
407 Parallel.For(0, trees.Count, x => { res[x] = Interpret(trees[x], cache); });
408 else
409 for (int ix = 0; ix < res.Length; ++ix)
410 res[ix] = Interpret(trees[ix], null);
411
412 return res;
413 }
414
415 #endregion
416
417 }
418
419 //=============================================================================
420 // SemanticInterpreter
421 //=============================================================================
422
431 public class SemanticInterpreter<T> : IInterpreter<T>
432 where T : class
433 {
434 //--[ Private fields ]-----------------------------------------------
435
436 private IInterpreter<Tree<Symbol>> semintr;
437 private IInterpreter<T> finintr;
438
439 //--[ Constructors ]-------------------------------------------------
440
445 public SemanticInterpreter(IInterpreter<Tree<Symbol>> semintr,
446 IInterpreter<T> finintr)
447 {
448 if (semintr == null) throw new ArgumentNullException("semintr");
449 if (finintr == null) throw new ArgumentNullException("finintr");
450
451 this.semintr = semintr;
452 this.finintr = finintr;
453 }
454
455 //--[ Properties ]---------------------------------------------------
456
459 public RewriteRuleCollection<Tree<Symbol>> SemanticRules { get { return semintr.RewriteRules; } }
460
463 public RewriteRuleCollection<T> RewriteRules { get { return finintr.RewriteRules; } }
464
465 //--[ Interface implementation ]-------------------------------------
466
467 #region [ IInterpreter ]
468
472 public InterpreterResult<T> Interpret(Tree<Symbol> tree)
473 {
474 try
475 {
476 var tmp = semintr.Interpret(tree);
477 return tmp.Success ? finintr.Interpret(tmp.Result) : null;
478 }
479 catch (Exception ex)
480 {
481 return new InterpreterResult<T>()
482 {
483 Context = null,
484 Exception = ex,
485 Input = tree,
486 Result = null
487 };
488 }
489 }
490
496 public IReadOnlyList<InterpreterResult<T>> Interpret(IReadOnlyList<Tree<Symbol>> trees)
497 {
498 var temp = semintr.Interpret(trees);
499 var fin = finintr.Interpret(temp.Where(x => x.Success).Select(x => x.Result).ToArray());
500
501 var res = new InterpreterResult<T>[trees.Count];
502 int loc = 0;
503 for(int ix = 0; ix < temp.Count; ++ix)
504 {
505 if (temp[ix].Success)
506 res[ix] = fin[loc++];
507 else
508 res[ix] = new InterpreterResult<T>()
509 { Context = null, Exception = null, Input = trees[ix], Result = null };
510 }
511
512 return res;
513 }
514
515 #endregion
516
517 }
518
519 }
Mercury.Interpreting.Instance
Represents a binding between a Mercury.Interpreting.Variable and its value
Definition: Instance.cs:17
Mercury.Interpreting.IInterpreterContextFactory
Factory of context.
Definition: InterpreterContext.cs:89
Mercury.Interpreting.Instance.Value
object Value
Binded value
Definition: Instance.cs:47
Mercury.Interpreting.RuleEntry< T >
Describes a rule that has been used to interpret a tree.
Definition: Entries.cs:92
Mercury.Interpreting.TreeEntry< T >
Represents an entry for tree interpretation.
Definition: Entries.cs:52
Mercury.Interpreting.MemoEntry< T >
Represents memoized value
Definition: Entries.cs:82
Mercury.Interpreting.Interpreter< T >.Interpret
InterpreterResult< T > Interpret(Tree< Symbol > tree)
Interprets the tree using rewrite rules.
Definition: Interpreter.cs:391
Mercury.Interpreting.Interpreter< T >.Interpret
IReadOnlyList< InterpreterResult< T > > Interpret(IReadOnlyList< Tree< Symbol >> trees)
Interprets the specified trees. If the number of trees is at least boostlim specified in the construc...
Definition: Interpreter.cs:401
Mercury.Extensions.RandomString
static string RandomString(int length, string init="")
Creates a random [A-Za-z] string.
Definition: Extensions.cs:115
Mercury.Interpreting.Structure
Represents a tree of Mercury.Interpreting.IElement instances. Must match precisely to the parse tree...
Definition: Element.cs:439
Mercury.Interpreting.VariableParameter
Represents a named parameter that will be replaced by an actual value of a variable captured by inter...
Definition: FormalParameter.cs:160
Mercury.Interpreting.Instance.Var
Variable Var
The variable
Definition: Instance.cs:44
Mercury.Interpreting.ArgumentType
ArgumentType
Defines argument types using in the Mercury library
Definition: Argument.cs:11
Mercury.Interpreting.ConstantParameter
Constant parameter.
Definition: FormalParameter.cs:43
Mercury.Interpreting.Alternative.MatchesSymbol
bool MatchesSymbol(Symbol s)
Indicates whether this alternative matches the given symbol.
Definition: Element.cs:105
Mercury.Interpreting.RewriteRuleCollection< T >
A read-only collection of rewrite rules
Definition: RewriteRuleCollection.cs:14
Mercury.Interpreting.IElement.Type
ElementType Type
Element type
Definition: Element.cs:37
Mercury.Interpreting.Variable
Represents a variable element that captures value and can be used on the RHS of the RewriteRule as an...
Definition: Element.cs:261
Mercury.Interpreting.Structure.Type
ElementType Type
Definition: Element.cs:490
Mercury.Interpreting.Variable.Type
ElementType Type
Definition: Element.cs:336
Mercury.Interpreting.InstanceList.Count
int Count
Number of elements in the list
Definition: Instance.cs:112
Mercury.Interpreting.InterpreterResult< T >
Result of the interpretation.
Definition: InterpreterResult.cs:17
Mercury.Interpreting.ElementType
ElementType
Element Type enumeration
Definition: Element.cs:15
Mercury.Exception
An exception has been thrown
Mercury.Interpreting.Argument
Represents an argument passed to the Mercury.Interpreting.InterpreterAction{T}, the actual parameter ...
Definition: Argument.cs:58
Mercury.Interpreting.Wildcard
An element that matches zero or more values. Can be used as a variable, but the actioncall must be of...
Definition: Element.cs:370
Mercury.Interpreting.SemanticInterpreter< T >.Interpret
InterpreterResult< T > Interpret(Tree< Symbol > tree)
Interprets the tree using rewrite rules.
Definition: Interpreter.cs:472
Mercury.Interpreting.InstanceList
Represents the list of instances
Definition: Instance.cs:94
Mercury.Interpreting.ActionCall< T >
This class represents the application of Mercury.Interpreting.InterpreterAction{T} on the Mercury...
Definition: ActionCall.cs:18
Mercury.Interpreting.InterpreterContext< T >
Interpreter Context class. Some languages may use it to override it and remember data when parse tree...
Definition: InterpreterContext.cs:18
Mercury.Interpreting.IElement
Element interface
Definition: Element.cs:32
Mercury.Interpreting.EmptyContextFactory
Produces contexts with no custom data
Definition: InterpreterContext.cs:117
Mercury.Interpreting.SemanticInterpreter< T >.Interpret
IReadOnlyList< InterpreterResult< T > > Interpret(IReadOnlyList< Tree< Symbol >> trees)
Interprets trees using parallelism (if underlying interprets use it).
Definition: Interpreter.cs:496
Mercury.Interpreting.Interpreter< T >.Interpreter
Interpreter(RewriteRuleCollection< T > rules, IInterpreterContextFactory factory, bool logging=true, int boostlim=4)
Creates a new Interpreter instance.
Definition: Interpreter.cs:367
Mercury.Interpreting.ActionCall< T >.FormalParameters
IReadOnlyList< IFormalParameter > FormalParameters
The list of formal parameters.
Definition: ActionCall.cs:51
Mercury.Success
The analysis was successful and there is at least one result
Mercury.Extensions
Provides extension methods for the Mercury library.
Definition: Extensions.cs:12
Mercury.Interpreting.IInterpreter< T >
Interface for interpreters that create objects from derivation trees according to RewriteRules...
Definition: Interpreter.cs:20
Mercury.Interpreting.SemanticInterpreter< T >.SemanticInterpreter
SemanticInterpreter(IInterpreter< Tree< Symbol >> semintr, IInterpreter< T > finintr)
Initializes a new instance of the SemanticInterpreter{T} class.
Definition: Interpreter.cs:445
Mercury.Interpreting.Constant
Constant element. Basically equivalent of Mercury.Interpreting.Alternative.
Definition: Element.cs:178
Mercury.Interpreting.Structure.HasWildcard
bool HasWildcard
Indicates whether this structure contains wildcard amongst its direct child nodes.
Definition: Element.cs:484