Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GPDL/HeuristicLab.Problems.GPDL/3.4/GPDefSyn.cs @ 9430

Last change on this file since 9430 was 9430, checked in by gkronber, 11 years ago

initial import of GPDL parser plugin

File size: 18.3 KB
Line 
1// GPDefSyn.cs                                              HDO, 2006-08-28
2// -------------
3// Table-driven top-down syntax analyzer (G-code interpreter).
4// Generated by Coco-2 (PGT).
5//=====================================|========================================
6
7// --- call pragma mehts. and exec. sem. acts. after syntax errors? ---
8#define CONTPRAGMAACTS            // !!!must be defined for SG and PGT!!!
9#undef  CONTSEMACTS               // should not be defined
10
11using System;
12using System.Text;
13
14using Lex = GPDefLex;
15using Sem = GPDefSem;
16
17public class GPDefSyn {
18                   
19  public static String MODULENAME = "GPDefSyn";
20
21  // --- G-code instructions ---
22  public enum Instruction {
23    T, TA, TC, TCA, NT, NTA, ANY, ANYA, EPS, EPSA, JMP, RET
24  } // Instruction
25
26  private const int ROOTPC     =  209;
27  private const int LASTTERM   =   28;
28  private const int LASTPRAGMA =   29;
29
30
31  // --- other constants ---
32  private const int MINERRDIST   =   3;
33  private const int MAXSTACKLEN  = 100;
34  private const int EOFTOK       =   0;
35  private const int FIRSTNONTERM = LASTPRAGMA + 1;
36
37  public class NTData {
38    public int          startPC;
39    public bool         del;
40    public Sets.Set256  firstSet;
41    public NTData(int startPC, bool del, Sets.Set256 firstSet) {
42      this.startPC  = startPC;
43      this.del      = del;
44      this.firstSet = firstSet;
45    } // NTData
46  } // NTData
47 
48  private class GrammarTable {
49    public int[]  header = {
50      214, 28, 29, 40, 6, 0
51    };
52    public byte[] code = {
53         0,   1,   2,  28,   1,  14,   1,  14,  12,   0,  15,   1,  12,  17,
54         0,  16,   0,   5,   5,   1,  28,   0,   5,  18,  10,  19,   0,   0,
55        10,   5,   2,  39,   0,   7,  20,  10,  30,   0,   0,   6,   5,   3,
56        50,   0,   9,  22,  10,  41,   0,   8,   1,  23,   1,   8,  70,   0,
57        24,   8,   2,  26,   0,   2,   2,  28,  15,   0,  20,  28,  11,   0,
58         9,  25,  10,  58,   0,   2,  28,   1,  14,   0,  20,  11,   2,  28,
59         1,  14,   1,  11,  95,   0,   4,   8,   3,  16,   0,  20,  11,   2,
60        28,   1,   0,  18,  14,   1,   4, 109,   0,  15,   4,   4,   4,   0,
61        20,  17,  11,   4,   5,   1,  14,   1,  19, 131,   0,   4,   5,   3,
62        16,  10, 120,   0,   8,   3,  11,   4,   6,   1,  14,   5,   6, 147,
63         0,   3,  16,  10, 138,   0,   8,   4,  11,   3,  28, 157,   0,   1,
64        14,  11,   4,   7,   3,  16,  11,   0,   7,  13,  11,   5,   9, 175,
65         0,   1,  14,  10, 166,   0,   8,   3,  15,  11,   2,  28,   1,  14,
66         0,  15,   4,  10,   3,  16,  11,   1,  16, 199,   0,  13,   8,   6,
67        14,  11,   0,  17,  15,   8,   5,  16,   0,  27,  17,  11,   4,   0,
68         1,   0,   0,  11
69    };
70    public NTData[] nts = {
71      new NTData(   1, false, new Sets.Set256(0x0002)),
72      new NTData(  76, false, new Sets.Set256(0x0000, 0x1000)),
73      new NTData(  83, false, new Sets.Set256(0x0000, 0x1000)),
74      new NTData(  98, false, new Sets.Set256(0x0000, 0x1000)),
75      new NTData( 116, false, new Sets.Set256(0x0080, 0x1000)),
76      new NTData( 134, false, new Sets.Set256(0x0080, 0x1000)),
77      new NTData( 150, false, new Sets.Set256(0x0080, 0x1000)),
78      new NTData( 162, false, new Sets.Set256(0x0080)),
79      new NTData( 166, true , new Sets.Set256(0x0000, 0x1000)),
80      new NTData( 179, false, new Sets.Set256(0x0000, 0x1000)),
81      new NTData( 190, false, new Sets.Set256(0x0000, 0x0003))
82    };
83    public Sets.Set256[] epsSets = {
84      new Sets.Set256(0x0300),
85      new Sets.Set256(0x0004),
86      new Sets.Set256(0x0000, 0x0010),
87      new Sets.Set256(0x0000, 0x0018),
88      new Sets.Set256(0x0000, 0x0800),
89      new Sets.Set256(0x0000, 0x1010)
90    };
91    public Sets.Set256[] anySets = {
92      new Sets.Set256(0x0000)
93    };
94    public String[] names = {
95      "end of file", "PROBLEM", "END", "EPS", "LOCAL", "NONTERMINALS",
96      "RULES", "SEM", "MAXIMIZE", "MINIMIZE", "TERMINALS", "CONSTRAINTS",
97      "INIT", "MUTATE", "CODE", "IN", "SET", "RANGE", "=", "|", ".", "(",
98      ")", "[", "]", "{", "}", "..", "ident", "source", "GPDef",
99      "NonterminalDecl", "TerminalDecl", "RuleDef", "SynExpr", "SynTerm",
100      "SynFact", "SemAction", "ConstraintDef", "ConstraintRule",
101      "SetDefinition"
102    };
103  } // GrammarTable;
104
105  private static GrammarTable gt;
106
107  private static int   pc;             // G-code counter
108  private static int[] stk;            // stack of G-code return adresses
109  private static int   sp;             // stack pointer
110  private static bool  mustRead;       // next Lex.token to read
111  private static int   altRoot;        // root of alternative chain
112  private static bool  leaveOrEnter;   // leaveCnt > 0 OR enterCnt > 0
113  private static int   leaveCnt;       // nr. of sem. proc. to leave
114  private static int   enterCnt;       // nr. of sem. proc. to enter
115  private static int   errDist;        // current error distance
116  private static int[] stkAtErr;       // saved stack at error position
117  private static int[] newSP;          // new stack length
118  private static int[] newPC;          // pc after recovery
119
120
121  public static void GPDefSynMethod(Utils.ModuleAction action, out String moduleName) {
122  //-----------------------------------|----------------------------------------
123    moduleName = MODULENAME;
124    switch (action) {
125      case Utils.ModuleAction.getModuleName:
126        return;
127      case Utils.ModuleAction.initModule:
128        Errors.InstallStopParsingMethod(StopParsing);
129        gt       = new GrammarTable();
130        stk      = new int[MAXSTACKLEN];
131        stkAtErr = new int[MAXSTACKLEN];
132        newSP    = new int[LASTTERM + 1];
133        newPC    = new int[LASTTERM + 1];
134        break;
135      case Utils.ModuleAction.resetModule:
136        break;
137      case Utils.ModuleAction.cleanupModule:
138        gt       = null;
139        stk      = null;
140        stkAtErr = null;
141        newSP    = null;
142        newPC    = null;
143        break;
144    } // switch
145  } // GPDefSynMethod
146
147  private static void Push(int pc) {
148    if (sp < MAXSTACKLEN)
149      stk[sp++] = pc;
150    else
151      Errors.Restriction(MODULENAME, "Push", "parser stack overflow");
152  } // Push
153
154  private static int Pop() {
155    if (sp > 0)
156      return stk[--sp];
157    else {
158      Errors.CompilerError(MODULENAME, "Pop", "parser stack underflow");
159      return 0;
160    } // else
161  } // Pop
162
163  private static void GetNextToken() {
164    for (;;) {
165      Lex.GetToken(); // updates Lex.token
166      if (Lex.token <= LASTTERM)
167        return;
168  #if !CONTPRAGMAACTS
169      if (NumOfSynErrors() == 0)
170  #endif
171        Sem.pragmaMethods[Lex.token - LASTTERM - 1]();
172    } // for
173  } // GetNextToken
174
175  private static int AdrAt(int pc) {
176    return (gt.code[pc - 1] |
177           (gt.code[pc    ] << 8));
178  } // AdrAt
179
180  private static void AdjustPC(ref int pc) {
181    if (pc == 0)
182      return;
183    for (;;)
184      switch ((Instruction)gt.code[pc - 1]) {
185        case Instruction.T:
186        case Instruction.TA:
187        case Instruction.TC:
188        case Instruction.TCA:
189        case Instruction.NT:
190        case Instruction.NTA:
191        case Instruction.ANY:
192        case Instruction.ANYA:
193        case Instruction.EPS:
194        case Instruction.EPSA:
195          return;
196        case Instruction.JMP:
197          pc = AdrAt(pc + 1);
198          break;
199        case Instruction.RET:
200          pc = 0;
201          return;
202        default:
203          pc++; // syn. or sem. action
204          break;
205      } // switch
206  } // AdjustPC
207
208  private static void GetSymInstr(int pc,
209                        out int opcode, out int sy, out int nextPC, out int altPC) {
210    opcode = gt.code[pc - 1];
211    nextPC = 0; // dummy init
212    altPC  = 0; // dummy init
213    switch ((Instruction)opcode) {
214      case Instruction.T:
215      case Instruction.TA:
216      case Instruction.TC:
217      case Instruction.TCA:
218      case Instruction.ANYA:
219      case Instruction.EPS:
220      case Instruction.EPSA:
221        sy = gt.code[pc];
222        break;
223      case Instruction.NT:
224      case Instruction.NTA:
225        sy = gt.code[pc] + FIRSTNONTERM;
226        break;
227      default: // ANY, JMP, RET, SEM, SYN
228        sy = 0;
229        break;
230    } // switch
231    switch ((Instruction)opcode) {
232      case Instruction.T:
233      case Instruction.EPS:
234        nextPC = pc + 2;
235        altPC = 0;
236        break;
237      case Instruction.TC:
238      case Instruction.NT:
239        nextPC = pc + 3;
240        altPC = 0;
241        break;
242      case Instruction.TA:
243      case Instruction.ANYA:
244      case Instruction.EPSA:
245        nextPC = pc + 4;
246        altPC = AdrAt(pc + 2);
247        break;
248      case Instruction.TCA:
249      case Instruction.NTA:
250        nextPC = pc + 5;
251        altPC = AdrAt(pc + 2);
252        break;
253      case Instruction.ANY:
254        nextPC = pc + 1;
255        altPC = 0;
256        break;
257    } // switch
258    AdjustPC(ref nextPC);
259    AdjustPC(ref altPC);
260  } // GetSymInstr
261
262  private static void Fill(int pc, int sp) {
263    int opcode, sy, nextPC, altPC, i;
264    AdjustPC(ref pc);
265    while (pc > 0) {
266      GetSymInstr(pc, out opcode, out sy, out nextPC, out altPC);
267      switch ((Instruction)opcode) {
268        case Instruction.T:
269        case Instruction.TA:
270        case Instruction.TC:
271        case Instruction.TCA:
272          newPC[sy] = pc;
273          newSP[sy] = sp;
274          break;
275        case Instruction.NT:
276        case Instruction.NTA:
277          for (i = 0; i <= LASTTERM; i++)
278            if (Sets.member((ushort)i, gt.nts[sy - FIRSTNONTERM].firstSet)) {
279              newPC[i] = pc;
280              newSP[i] = sp;
281            }
282          if (gt.nts[sy - FIRSTNONTERM].del)
283            Fill(nextPC, sp);
284          break;
285        case Instruction.EPS:
286        case Instruction.EPSA:
287          Fill(nextPC, sp);
288          break;
289      } // switch
290      pc = altPC;
291    } // while
292  } // Fill
293
294  private static void FillSucc(int pc, int sp) {
295    int opcode, sy, nextPC, altPC;
296    AdjustPC(ref pc);
297    while (pc > 0) {
298      GetSymInstr(pc, out opcode, out sy, out nextPC, out altPC);
299      if (nextPC > 0)
300        Fill(nextPC, sp);
301      pc = altPC;
302    } // while
303  } // FillSucc
304
305  private static void Triple(int altRoot) {
306    for (int i = 0; i <= LASTTERM; i++) { // clear triple list
307      newPC[i] = 0;
308      newSP[i] = 0;
309    } // for
310    for (int i = 1; i <= sp; i++) {       // successors of stacked nt's
311      FillSucc(stk[i - 1], i - 1);
312      Fill(stk[i - 1], i - 1);
313    } // for
314    FillSucc(altRoot, sp);                // successors of alt. chain
315    Fill(altRoot, sp);                    // current alt. chain
316  } // Triple
317
318  private static void HandleSynErr(ref int pc, ref int altRoot) {
319    int     opcode, sy, nextPC, altPC, adjPC, nwSP, eq;
320    bool    nameInMsg;
321    String  name;
322    StringBuilder msg = new StringBuilder();
323    leaveOrEnter = false;
324    if (errDist >= MINERRDIST) { // --- primary error
325      nameInMsg = false;
326      adjPC = altRoot;
327      AdjustPC(ref adjPC);
328      while (adjPC > 0) {
329        GetSymInstr(adjPC, out opcode, out sy, out nextPC, out altPC);
330        if ( (Instruction)opcode >= Instruction.T  &&
331             (Instruction)opcode <= Instruction.NTA  ) {
332          if ( gt.names[sy].IndexOf(' ') >= 0 ||
333               !Char.IsLetter(gt.names[sy][0]) )
334            name = "\"" + gt.names[sy] + "\"";
335          else
336            name = gt.names[sy];
337          if (name.IndexOf('{') > -1) // prevent formatting problems in Errors.SynError
338            name = name.Replace("{", "{{");
339          if (name.IndexOf('}') > -1) // prevent formatting problems in Errors.SynError
340            name = name.Replace("}", "}}");
341          if (msg.Length + name.Length + 2 > 80) {
342            msg.Append(" ...");
343            break;
344          } // if
345          if (!nameInMsg) {
346            nameInMsg = true;
347            msg.Append("expected: " + name);
348          } else {
349            msg.Append(", ");
350            msg.Append(name);
351          } // else
352        } // if
353        adjPC = altPC;
354      } // while
355      if (!nameInMsg)
356        msg.Append("syntax error");
357      Errors.SynError(Lex.tokenLine, Lex.tokenCol, msg.ToString(), "");
358      Triple(altRoot);
359      while (newPC[Lex.token] == 0) {
360        GetNextToken();      // may result in a call to StopParsing
361        if (leaveOrEnter)
362          return;
363      } // while
364      nwSP = newSP[Lex.token];
365      leaveCnt = sp - nwSP;
366      enterCnt = 0;
367      Array.Copy(stk, stkAtErr, stk.Length); // save stack
368    } else {                 // --- spurios error
369      if (errDist == 0) {    // no token used since last error
370        GetNextToken();      // may result in a call to StopParsing
371        if (leaveOrEnter)
372          return;
373      } // if
374      while (newPC[Lex.token] == 0) {
375        GetNextToken();      // may result in a call to StopParsing
376        if (leaveOrEnter)
377          return;
378      } // while
379      nwSP = newSP[Lex.token];
380      eq = 2;                // compare stkAtErr and stk
381      while (eq <= sp && eq <= nwSP && stkAtErr[eq - 1] == stk[eq - 1])
382        eq++;
383      eq--;                  // stacks are equal up to index eq
384      leaveCnt = sp - eq;
385      if (nwSP < eq) {
386        leaveCnt = sp - nwSP;
387        enterCnt = 0;
388      } else if (nwSP > eq)
389        enterCnt = nwSP - eq;
390      else // nwSP == eq
391        enterCnt = 0;
392      Array.Copy(stkAtErr, stk, stk.Length); // restore stack
393    } // else
394    leaveOrEnter = (leaveCnt + enterCnt) > 0;
395    sp = nwSP;
396    pc = newPC[Lex.token];
397    altRoot = pc;
398    errDist = 0;
399  } // HandleSynErr
400
401  public static int Interpret() {
402  //-----------------------------------|----------------------------------------
403    int actionNr, opcode, currPC;
404    for (;;) {
405      opcode = gt.code[pc - 1];
406      if ( !leaveOrEnter && mustRead &&
407           (Instruction)opcode <= Instruction.EPSA ) {
408        GetNextToken();
409        mustRead = false;
410        errDist++;
411        altRoot = pc;
412      } // if
413      if (leaveOrEnter) {
414        if (leaveCnt > 0) {
415          leaveCnt--;
416          actionNr = 0;
417        } else { // enterCnt > 0
418          enterCnt--;
419          actionNr = gt.code[stkAtErr[sp - enterCnt - 1] - 2];
420        } // else
421        leaveOrEnter = (leaveCnt + enterCnt) > 0;
422        return actionNr;
423      } // if
424      pc++;
425      switch ((Instruction)opcode) {
426        case Instruction.T:
427          if (Lex.token == gt.code[pc - 1])
428            if (Lex.token != EOFTOK) {
429              pc++;
430              mustRead = true;
431            } else {
432              return 0;
433            } // else
434          else
435            HandleSynErr(ref pc, ref altRoot);
436          break;
437        case Instruction.TA:
438          if (Lex.token == gt.code[pc - 1]) {
439            pc += 3;
440            mustRead = true;
441          } else
442            pc = AdrAt(pc + 1); // try alternative
443          break;
444        case Instruction.TC:
445          if (Lex.token == gt.code[pc - 1]) {
446            pc += 2;
447            mustRead = true;
448            actionNr = gt.code[pc - 2];
449            return actionNr;
450          } else
451            HandleSynErr(ref pc, ref altRoot);
452          break;
453        case Instruction.TCA:
454          if (Lex.token == gt.code[pc - 1]) {
455            pc += 4;
456            mustRead = true;
457            actionNr = gt.code[pc - 2];
458            return actionNr;
459          } else
460            pc = AdrAt(pc + 1); // try alternative
461          break;
462        case Instruction.NT:
463          currPC = gt.code[pc - 1];
464          if ( gt.nts[currPC].del ||
465               Sets.member((ushort)Lex.token, gt.nts[currPC].firstSet) ) {
466            pc++;
467            actionNr = gt.code[pc - 1];
468            Push(pc + 1);
469            pc = gt.nts[currPC].startPC;
470            altRoot = pc;
471            return actionNr;
472          } else
473            HandleSynErr(ref pc, ref altRoot);
474          break;
475        case Instruction.NTA:
476          currPC = gt.code[pc - 1];
477          if (Sets.member((ushort)Lex.token, gt.nts[currPC].firstSet)) {
478            pc += 3;
479            actionNr = gt.code[pc - 1];
480            Push(pc + 1);
481            pc = gt.nts[currPC].startPC;
482            altRoot = pc;
483            return actionNr;
484          } else
485            pc = AdrAt(pc + 1);
486          break;
487        case Instruction.ANY:
488          mustRead = true;
489          break;
490        case Instruction.ANYA:
491          currPC = gt.code[pc - 1];
492          if (Sets.member((ushort)Lex.token, gt.anySets[currPC - 1])) {
493            pc += 3;
494            mustRead = true;
495          } else
496            pc = AdrAt(pc + 1);
497          break;
498        case Instruction.EPS:
499          currPC = gt.code[pc - 1];
500          if (Sets.member((ushort)Lex.token, gt.epsSets[currPC - 1]))
501            pc++;
502          else
503            HandleSynErr(ref pc, ref altRoot);
504          break;
505        case Instruction.EPSA:
506          currPC = gt.code[pc - 1];
507          if (Sets.member((ushort)Lex.token, gt.epsSets[currPC - 1]))
508            pc += 3;
509          else
510            pc = AdrAt(pc + 1);
511          break;
512        case Instruction.JMP:
513          pc = AdrAt(pc);
514          break;
515        case Instruction.RET:
516          pc = Pop();
517          altRoot = pc;
518          return 0;
519        default:
520          if (opcode <= 128) {
521  #if !CONTSEMACTS
522          if (Errors.NumOfSynErrors() == 0)
523  #endif
524            return opcode - 12;
525          } else // opcode > 128
526            return opcode - 128;
527          break;
528      } // switch
529    } // for
530  } // Interpret
531
532
533  public static bool Parse() {
534  //-----------------------------------|----------------------------------------
535    Lex.InitLex();
536    sp           = 0;
537    pc           = ROOTPC;
538    altRoot      = pc;
539    mustRead     = true;
540    errDist      = MINERRDIST + 1;
541    leaveOrEnter = false;
542    leaveCnt     = 0;
543    enterCnt     = 0;
544    Sem.StartSem();
545    return Errors.NumOfSynErrors() == 0;
546  } // Parse
547
548
549  public static void StopParsing() {
550  //-----------------------------------|----------------------------------------
551    leaveCnt     = sp + 1;
552    enterCnt     = 0;
553    leaveOrEnter = true;
554  } // StopParsing
555
556} // GPDefSyn
557 
558// End of GPDefSyn.cs
559//=====================================|========================================
Note: See TracBrowser for help on using the repository browser.