using System.Text; using System.Collections.Generic; using IEnumerableConstraintNode = System.Collections.Generic.IEnumerable; using System; namespace HeuristicLab.Problems.GPDL { public class Parser { public const int _EOF = 0; public const int _ident = 1; public const int maxT = 23; const bool T = true; const bool x = false; const int minErrDist = 2; public Scanner scanner; public Errors errors; public Token t; // last recognized token public Token la; // lookahead token int errDist = minErrDist; public static HeuristicLab.Optimization.IProblem problem; public Parser(Scanner scanner) { this.scanner = scanner; errors = new Errors(); } void SynErr (int n) { if (errDist >= minErrDist) errors.SynErr(la.line, la.col, n); errDist = 0; } public void SemErr (string msg) { if (errDist >= minErrDist) errors.SemErr(t.line, t.col, msg); errDist = 0; } void Get () { for (;;) { t = la; la = scanner.Scan(); if (la.kind <= maxT) { ++errDist; break; } la = t; } } void Expect (int n) { if (la.kind==n) Get(); else { SynErr(n); } } bool StartOf (int s) { return set[s, la.kind]; } void ExpectWeak (int n, int follow) { if (la.kind == n) Get(); else { SynErr(n); while (!StartOf(follow)) Get(); } } bool WeakSeparator(int n, int syFol, int repFol) { int kind = la.kind; if (kind == n) {Get(); return true;} else if (StartOf(repFol)) {return false;} else { SynErr(n); while (!(set[syFol, kind] || set[repFol, kind] || set[0, kind])) { Get(); kind = la.kind; } return StartOf(syFol); } } void SourceCode(out string src) { src = ""; Expect(2); int beg = la.pos; while (StartOf(1)) { Get(); } int end = la.pos; Expect(3); if(end>beg) src = scanner.buffer.GetString(beg, end); } void GPDef() { RuleNode ruleNode = null; GPDefNode gpDef = new GPDefNode(); NonTerminalNode ntNode = null; FitnessFunctionNode fitnessFunNode = null; TerminalNode tNode = null; problem = null; string src = ""; Expect(4); Expect(1); gpDef.Name = t.val; if (la.kind == 5) { Get(); SourceCode(out src); gpDef.ClassCodeNode = new CodeNode{SrcCode = src}; } if (la.kind == 6) { Get(); SourceCode(out src); gpDef.InitCodeNode = new CodeNode{SrcCode = src}; } Expect(7); while (la.kind == 1) { NonterminalDecl(out ntNode); gpDef.NonTerminals.Add(ntNode); } Expect(8); while (la.kind == 1) { TerminalDecl(out tNode); gpDef.Terminals.Add(tNode); } Expect(9); while (la.kind == 1) { RuleDef(out ruleNode); gpDef.Rules.Add(ruleNode); } fitnessFunNode = new FitnessFunctionNode(); gpDef.FitnessFunctionNode = fitnessFunNode; if (la.kind == 10) { Get(); fitnessFunNode.Maximization = true; } else if (la.kind == 11) { Get(); fitnessFunNode.Maximization = false; } else SynErr(24); SourceCode(out src); fitnessFunNode.SrcCode = src; Expect(12); Expect(1); var gen = new ProblemGenerator(); problem = gen.GenerateFromAst(gpDef); Expect(13); } void NonterminalDecl(out NonTerminalNode ntNode) { string identStr = ""; ntNode = null; string src = ""; Expect(1); identStr = t.val; if (la.kind == 2) { SourceCode(out src); } var myNtNode = new NonTerminalNode(); ntNode = myNtNode; myNtNode.Ident = identStr; myNtNode.FormalParameters = src; Expect(13); } void TerminalDecl(out TerminalNode tNode) { string identStr = ""; tNode = null; TerminalNode myTNode = null; IEnumerableConstraintNode constraints = null; string src = ""; Expect(1); identStr = t.val; if (la.kind == 2) { SourceCode(out src); } myTNode = new TerminalNode(); tNode = myTNode; myTNode.Ident = identStr; myTNode.FormalParameters = src; myTNode.FieldDefinitions = SourceReader.ExtractFormalParameters(src); if (la.kind == 15) { Get(); ConstraintDef(out constraints); myTNode.Constraints = constraints; } Expect(13); } void RuleDef(out RuleNode rule) { RuleExprNode expr = null; string identStr = null; RuleNode myRule = null; rule = null; string src = ""; Expect(1); identStr = t.val; if (la.kind == 2) { SourceCode(out src); } Expect(20); myRule = new RuleNode(); rule = myRule; myRule.NtSymbol = identStr; if (la.kind == 21) { Get(); SourceCode(out src); myRule.LocalCode = src; } SynExpr(out expr); Expect(13); myRule.RuleExpr = expr; } void SemAction(out RuleActionNode action) { RuleActionNode myAction = null; action = null; string src = ""; Expect(14); SourceCode(out src); myAction = new RuleActionNode(); myAction.SrcCode = src; action = myAction; } void ConstraintDef(out IEnumerableConstraintNode constraints) { List constraintsList = new List(); ConstraintNode n = null; constraints = null; while (la.kind == 1) { ConstraintRule(out n); constraintsList.Add(n); } constraints = constraintsList; } void ConstraintRule(out ConstraintNode constraint) { constraint = null; Expect(1); constraint = new ConstraintNode(t.val); Expect(16); SetDefinition(constraint); } void SetDefinition(ConstraintNode constraint) { string src = ""; if (la.kind == 17) { Get(); constraint.Type = ConstraintNodeType.Set; SourceCode(out src); constraint.SetExpression = src; } else if (la.kind == 18) { Get(); constraint.Type = ConstraintNodeType.Range; SourceCode(out src); constraint.RangeMinExpression = src; Expect(19); SourceCode(out src); constraint.RangeMaxExpression = src; } else SynErr(25); } void SynExpr(out RuleExprNode expr ) { expr = null; AlternativesNode alt = null; SynTerm(out expr); alt = new AlternativesNode(); alt.Add(expr); while (la.kind == 22) { Get(); SynTerm(out expr); alt.Add(expr); expr = alt; } } void SynTerm(out RuleExprNode expr) { SequenceNode seq = null; expr = null; SynFact(out expr); seq = new SequenceNode(); seq.Add(expr); while (la.kind == 1 || la.kind == 14) { SynFact(out expr); seq.Add(expr); expr = seq; } } void SynFact(out RuleExprNode expr) { string identStr = ""; RuleActionNode action = null; expr = null; string src = ""; if (la.kind == 1) { Get(); identStr = t.val; if (la.kind == 2) { SourceCode(out src); } var callNode = new CallSymbolNode{Ident = identStr}; callNode.ActualParameter = src; expr = callNode; } else if (la.kind == 14) { SemAction(out action); expr = action; } else SynErr(26); } public void Parse() { la = new Token(); la.val = ""; Get(); GPDef(); Expect(0); } static readonly bool[,] set = { {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}, {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} }; } // end Parser public class Errors { public int count = 0; // number of errors detected public System.IO.TextWriter errorStream = Console.Out; // error messages go to this stream public string errMsgFormat = "-- line {0} col {1}: {2}"; // 0=line, 1=column, 2=text public virtual void SynErr (int line, int col, int n) { string s; switch (n) { case 0: s = "EOF expected"; break; case 1: s = "ident expected"; break; case 2: s = "\"<<\" expected"; break; case 3: s = "\">>\" expected"; break; case 4: s = "\"PROBLEM\" expected"; break; case 5: s = "\"CODE\" expected"; break; case 6: s = "\"INIT\" expected"; break; case 7: s = "\"NONTERMINALS\" expected"; break; case 8: s = "\"TERMINALS\" expected"; break; case 9: s = "\"RULES\" expected"; break; case 10: s = "\"MAXIMIZE\" expected"; break; case 11: s = "\"MINIMIZE\" expected"; break; case 12: s = "\"END\" expected"; break; case 13: s = "\".\" expected"; break; case 14: s = "\"SEM\" expected"; break; case 15: s = "\"CONSTRAINTS\" expected"; break; case 16: s = "\"IN\" expected"; break; case 17: s = "\"SET\" expected"; break; case 18: s = "\"RANGE\" expected"; break; case 19: s = "\"..\" expected"; break; case 20: s = "\"=\" expected"; break; case 21: s = "\"LOCAL\" expected"; break; case 22: s = "\"|\" expected"; break; case 23: s = "??? expected"; break; case 24: s = "invalid GPDef"; break; case 25: s = "invalid SetDefinition"; break; case 26: s = "invalid SynFact"; break; default: s = "error " + n; break; } errorStream.WriteLine(errMsgFormat, line, col, s); count++; } public virtual void SemErr (int line, int col, string s) { errorStream.WriteLine(errMsgFormat, line, col, s); count++; } public virtual void SemErr (string s) { errorStream.WriteLine(s); count++; } public virtual void Warning (int line, int col, string s) { errorStream.WriteLine(errMsgFormat, line, col, s); } public virtual void Warning(string s) { errorStream.WriteLine(s); } } // Errors public class FatalError: Exception { public FatalError(string m): base(m) {} } }