Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GPDL/HeuristicLab.Problems.GPDL/3.4/Parser.cs @ 10067

Last change on this file since 10067 was 10067, checked in by gkronber, 10 years ago

#2026 worked on brute force solver for GPDL problems.

File size: 10.2 KB
Line 
1using System.Text;
2using System.Collections.Generic;
3using System.Linq;
4using IEnumerableConstraintNode = System.Collections.Generic.IEnumerable<ConstraintNode>;
5
6
7
8using System;
9
10namespace HeuristicLab.Problems.GPDL {
11
12
13
14public class Parser {
15  public const int _EOF = 0;
16  public const int _ident = 1;
17  public const int maxT = 23;
18
19  const bool T = true;
20  const bool x = false;
21  const int minErrDist = 2;
22 
23  public Scanner scanner;
24  public Errors  errors;
25
26  public Token t;    // last recognized token
27  public Token la;   // lookahead token
28  int errDist = minErrDist;
29
30public GPDefNode AbstractSyntaxTree { get; private set; }
31
32
33
34  public Parser(Scanner scanner) {
35    this.scanner = scanner;
36    errors = new Errors();
37  }
38
39  void SynErr (int n) {
40    if (errDist >= minErrDist) errors.SynErr(la.line, la.col, n);
41    errDist = 0;
42  }
43
44  public void SemErr (string msg) {
45    if (errDist >= minErrDist) errors.SemErr(t.line, t.col, msg);
46    errDist = 0;
47  }
48 
49  void Get () {
50    for (;;) {
51      t = la;
52      la = scanner.Scan();
53      if (la.kind <= maxT) { ++errDist; break; }
54
55      la = t;
56    }
57  }
58 
59  void Expect (int n) {
60    if (la.kind==n) Get(); else { SynErr(n); }
61  }
62 
63  bool StartOf (int s) {
64    return set[s, la.kind];
65  }
66 
67  void ExpectWeak (int n, int follow) {
68    if (la.kind == n) Get();
69    else {
70      SynErr(n);
71      while (!StartOf(follow)) Get();
72    }
73  }
74
75
76  bool WeakSeparator(int n, int syFol, int repFol) {
77    int kind = la.kind;
78    if (kind == n) {Get(); return true;}
79    else if (StartOf(repFol)) {return false;}
80    else {
81      SynErr(n);
82      while (!(set[syFol, kind] || set[repFol, kind] || set[0, kind])) {
83        Get();
84        kind = la.kind;
85      }
86      return StartOf(syFol);
87    }
88  }
89
90 
91  void SourceCode(out string src) {
92    src = "";
93    Expect(2);
94    int beg = la.pos;
95    while (StartOf(1)) {
96      Get();
97    }
98    int end = la.pos;
99    Expect(3);
100    if(end>beg) src = scanner.buffer.GetString(beg, end);
101  }
102
103  void GPDef() {
104    RuleNode ruleNode = null;
105    GPDefNode gpDef = new GPDefNode();
106    NonTerminalNode ntNode = null;
107    FitnessFunctionNode fitnessFunNode = null;
108    TerminalNode tNode = null;
109    string src = "";
110   
111    Expect(4);
112    Expect(1);
113    gpDef.Name = t.val;
114    if (la.kind == 5) {
115      Get();
116      SourceCode(out src);
117      gpDef.ClassCodeNode = new CodeNode{SrcCode = src};
118    }
119    if (la.kind == 6) {
120      Get();
121      SourceCode(out src);
122      gpDef.InitCodeNode = new CodeNode{SrcCode = src};
123    }
124    Expect(7);
125    while (la.kind == 1) {
126      NonterminalDecl(out ntNode);
127      if(gpDef.IsSymbolDefined(ntNode)) {
128       SemErr("Duplicate non-terminal symbol: " + ntNode.Ident);
129      } else {
130       gpDef.NonTerminals.Add(ntNode);
131      }
132     
133    }
134    if(!gpDef.NonTerminals.Any())
135     SemErr("No non-terminal symbols defined.");
136   
137    Expect(8);
138    while (la.kind == 1) {
139      TerminalDecl(out tNode);
140      if(gpDef.IsSymbolDefined(tNode)) {
141       SemErr("Duplicate terminal symbol: " + tNode.Ident);
142      } else {
143       gpDef.Terminals.Add(tNode);
144      }
145     
146    }
147    if(!gpDef.Terminals.Any())
148     SemErr("No terminal symbols defined.");
149   
150    Expect(9);
151    while (la.kind == 1) {
152      RuleDef(out ruleNode);
153      if(!gpDef.IsNonTerminalDefined(ruleNode.NtSymbol)) {
154       SemErr("Non-terminal symbol " + ruleNode.NtSymbol + " is not defined in the NONTERMINALS section.");
155      } else if(gpDef.IsRuleDefined(ruleNode)) {
156       SemErr("Duplicate rule definition for non-terminal symbol " + ruleNode.NtSymbol);
157      } else {
158       gpDef.Rules.Add(ruleNode);
159      }
160     
161    }
162    var undefinedNT = gpDef.UndefinedNonTerminals();
163    if(!string.IsNullOrEmpty(undefinedNT)) {
164     SemErr("Rules missing in the RULES section for: " + undefinedNT);
165    }
166   
167    fitnessFunNode = new FitnessFunctionNode();
168    gpDef.FitnessFunctionNode = fitnessFunNode;
169   
170    if (la.kind == 10) {
171      Get();
172      fitnessFunNode.Maximization = true;
173    } else if (la.kind == 11) {
174      Get();
175      fitnessFunNode.Maximization = false;
176    } else SynErr(24);
177    SourceCode(out src);
178    fitnessFunNode.SrcCode = src;
179    if(errors.count > 0) throw new FatalError("Syntactic or semantic errors found.");
180    Expect(12);
181    Expect(1);
182    AbstractSyntaxTree = gpDef;
183   
184    Expect(13);
185  }
186
187  void NonterminalDecl(out NonTerminalNode ntNode) {
188    string identStr = ""; ntNode = null; string src = "";
189    Expect(1);
190    identStr = t.val;
191    if (la.kind == 2) {
192      SourceCode(out src);
193    }
194    var myNtNode = new NonTerminalNode();
195    ntNode = myNtNode;
196    myNtNode.Ident = identStr;
197    myNtNode.FormalParameters = src;
198   
199    Expect(13);
200  }
201
202  void TerminalDecl(out TerminalNode tNode) {
203    string identStr = "";
204    tNode = null;
205    TerminalNode myTNode = null;
206    IEnumerableConstraintNode constraints = new List<ConstraintNode>();
207    string src = "";
208   
209    Expect(1);
210    identStr = t.val;
211    if (la.kind == 2) {
212      SourceCode(out src);
213    }
214    myTNode = new TerminalNode();
215    tNode = myTNode;
216    myTNode.Ident = identStr;
217    myTNode.FormalParameters = src;
218    myTNode.FieldDefinitions = Util.ExtractParameters(src);
219   
220    if (la.kind == 15) {
221      Get();
222      ConstraintDef(out constraints);
223    }
224    myTNode.Constraints = constraints;
225    Expect(13);
226  }
227
228  void RuleDef(out RuleNode rule) {
229    AlternativesNode alternatives = null;
230    string identStr = null;
231    RuleNode myRule = null;
232    rule = null;
233    string src = "";
234   
235    Expect(1);
236    identStr = t.val;
237    if (la.kind == 2) {
238      SourceCode(out src);
239    }
240    Expect(20);
241    myRule = new RuleNode();
242    rule = myRule;
243    myRule.NtSymbol = identStr;
244   
245    if (la.kind == 21) {
246      Get();
247      SourceCode(out src);
248      myRule.LocalCode = src;
249     
250    }
251    SynExpr(out alternatives);
252    Expect(13);
253    myRule.Alternatives = alternatives;
254   
255  }
256
257  void SemAction(out RuleActionNode action) {
258    RuleActionNode myAction = null; action = null; string src = "";
259    Expect(14);
260    SourceCode(out src);
261    myAction = new RuleActionNode();
262    myAction.SrcCode = src;
263    action = myAction;
264   
265  }
266
267  void ConstraintDef(out IEnumerableConstraintNode constraints) {
268    List<ConstraintNode> constraintsList = new List<ConstraintNode>();
269    ConstraintNode n = null;
270    constraints = null;
271   
272    while (la.kind == 1) {
273      ConstraintRule(out n);
274      constraintsList.Add(n);
275    }
276    constraints = constraintsList;
277  }
278
279  void ConstraintRule(out ConstraintNode constraint) {
280    constraint = null;
281   
282    Expect(1);
283    constraint = new ConstraintNode(t.val);
284    Expect(16);
285    SetDefinition(constraint);
286  }
287
288  void SetDefinition(ConstraintNode constraint) {
289    string src = "";
290    if (la.kind == 17) {
291      Get();
292      constraint.Type = ConstraintNodeType.Set;
293      SourceCode(out src);
294      constraint.SetExpression = src;
295    } else if (la.kind == 18) {
296      Get();
297      constraint.Type = ConstraintNodeType.Range;
298      SourceCode(out src);
299      constraint.RangeMinExpression = src;
300      Expect(19);
301      SourceCode(out src);
302      constraint.RangeMaxExpression = src;
303    } else SynErr(25);
304  }
305
306  void SynExpr(out AlternativesNode alt ) {
307    alt = new AlternativesNode();
308    SequenceNode seq = null;
309   
310    SynTerm(out seq);
311    alt.Add(seq);
312   
313    while (la.kind == 22) {
314      Get();
315      SynTerm(out seq);
316      alt.Add(seq);
317    }
318  }
319
320  void SynTerm(out SequenceNode seq) {
321    seq = new SequenceNode(); RuleExprNode expr = null;
322    SynFact(out expr);
323    seq.Add(expr);
324   
325    while (la.kind == 1 || la.kind == 14) {
326      SynFact(out expr);
327      seq.Add(expr);
328    }
329  }
330
331  void SynFact(out RuleExprNode expr) {
332    string identStr = "";
333    RuleActionNode action = null;
334    expr = null;
335    string src = "";
336   
337    if (la.kind == 1) {
338      Get();
339      identStr = t.val;
340      if (la.kind == 2) {
341        SourceCode(out src);
342      }
343      var callNode = new CallSymbolNode{Ident = identStr};
344      callNode.ActualParameter = src;
345      expr = callNode;
346     
347    } else if (la.kind == 14) {
348      SemAction(out action);
349      expr = action;
350    } else SynErr(26);
351  }
352
353
354
355  public void Parse() {
356    la = new Token();
357    la.val = "";   
358    Get();
359    GPDef();
360    Expect(0);
361
362  }
363 
364  static readonly bool[,] set = {
365    {T,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x,x,x,x, x},
366    {x,T,T,x, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, T,T,T,T, x}
367
368  };
369} // end Parser
370
371
372public class Errors {
373  public int count = 0;                                    // number of errors detected
374  public System.IO.TextWriter errorStream = Console.Out;   // error messages go to this stream
375  public string errMsgFormat = "-- line {0} col {1}: {2}"; // 0=line, 1=column, 2=text
376
377  public virtual void SynErr (int line, int col, int n) {
378    string s;
379    switch (n) {
380      case 0: s = "EOF expected"; break;
381      case 1: s = "ident expected"; break;
382      case 2: s = "\"<<\" expected"; break;
383      case 3: s = "\">>\" expected"; break;
384      case 4: s = "\"PROBLEM\" expected"; break;
385      case 5: s = "\"CODE\" expected"; break;
386      case 6: s = "\"INIT\" expected"; break;
387      case 7: s = "\"NONTERMINALS\" expected"; break;
388      case 8: s = "\"TERMINALS\" expected"; break;
389      case 9: s = "\"RULES\" expected"; break;
390      case 10: s = "\"MAXIMIZE\" expected"; break;
391      case 11: s = "\"MINIMIZE\" expected"; break;
392      case 12: s = "\"END\" expected"; break;
393      case 13: s = "\".\" expected"; break;
394      case 14: s = "\"SEM\" expected"; break;
395      case 15: s = "\"CONSTRAINTS\" expected"; break;
396      case 16: s = "\"IN\" expected"; break;
397      case 17: s = "\"SET\" expected"; break;
398      case 18: s = "\"RANGE\" expected"; break;
399      case 19: s = "\"..\" expected"; break;
400      case 20: s = "\"=\" expected"; break;
401      case 21: s = "\"LOCAL\" expected"; break;
402      case 22: s = "\"|\" expected"; break;
403      case 23: s = "??? expected"; break;
404      case 24: s = "invalid GPDef"; break;
405      case 25: s = "invalid SetDefinition"; break;
406      case 26: s = "invalid SynFact"; break;
407
408      default: s = "error " + n; break;
409    }
410    errorStream.WriteLine(errMsgFormat, line, col, s);
411    count++;
412  }
413
414  public virtual void SemErr (int line, int col, string s) {
415    errorStream.WriteLine(errMsgFormat, line, col, s);
416    count++;
417  }
418 
419  public virtual void SemErr (string s) {
420    errorStream.WriteLine(s);
421    count++;
422  }
423 
424  public virtual void Warning (int line, int col, string s) {
425    errorStream.WriteLine(errMsgFormat, line, col, s);
426  }
427 
428  public virtual void Warning(string s) {
429    errorStream.WriteLine(s);
430  }
431} // Errors
432
433
434public class FatalError: Exception {
435  public FatalError(string m): base(m) {}
436}
437}
Note: See TracBrowser for help on using the repository browser.