Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GPDL/Examples/Fib.txt @ 17639

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

#2026 fixed a bug in the brute force solver

File size: 5.6 KB
Line 
1PROBLEM Fib
2CODE<<
3  string[] allTerminals = new string[] {"a", "b", "c", "d", "e", "n"} ;
4  SymTab symTab = new SymTab();
5
6  class SymTab {
7    private Dictionary<string, int> values = new Dictionary<string,int>();
8    public void SetValue(string id, int val) {
9      values[id] = val;
10    }
11    public int GetValue(string id) {
12      int val = 0;
13      values.TryGetValue(id, out val);     
14      return val;
15    }
16  }
17>>
18
19NONTERMINALS
20  Program<<int n, out int r>>.                                           /* return value is the result of the last statement. */
21  StatSeq<<out int r>>.
22  AssignStat<<out int r>>.                                               /* result of assignment is the assigned value */
23  IncStat<<out int r>>.
24  DecStat<<out int r>>.
25  WhileStat<<out int r>>.                                                /* result of while loop is the result of the last executed statement */
26  Expr<<out int r>>.
27  AdditionExpr<<out int r>>.
28  SubtractionExpr<<out int r>>.
29  DivisionExpr<<out int r>>.
30  MultiplicationExpr<<out int r>>.
31  BooleanExpr<<out bool b>>.
32  NotExpr<<out bool b>>.
33  LessThanExpr<<out bool b>>.
34  EqualExpr<<out bool b>>.
35  AssignStatAndStatSeq<<out int r>>.
36  WhileStatAndStatSeq<<out int r>>.
37
38TERMINALS
39  ident<<out string id>>
40    CONSTRAINTS
41      id IN SET << allTerminals; >>
42  .
43  Const<<out int val>>
44    CONSTRAINTS
45      val IN SET << Enumerable.Range(0, 100); >>
46  .
47  Nothing<<out int val>>
48     CONSTRAINTS
49       val IN SET << Enumerable.Repeat(0, 1); >>
50  .
51 
52RULES
53  Program<<int n, out int r>> = StatSeq<<out r>>                         SEM << symTab.SetValue("n", n); >>
54  .
55  StatSeq<<out int r>> =                                                 LOCAL << r = 0; >>
56    Nothing<<out r>>
57    | AssignStatAndStatSeq<<out r>>
58    | WhileStatAndStatSeq<<out r>>
59    | IncStat<<out r>>
60    | DecStat<<out r>>
61  .
62 
63  AssignStatAndStatSeq<<out int r>> =
64    StatSeq<<out r>>  AssignStat<<out r>>
65  .
66  WhileStatAndStatSeq<<out int r>> =
67    StatSeq<<out r>> WhileStat<<out r>>
68  .
69
70  AssignStat<<out int r>> =                                               LOCAL << int e; string id;>>
71    ident<<out id>> Expr<<out e>>                                         SEM  << symTab.SetValue(id, e); r = e; >>
72  .
73  IncStat<<out int r>> =                                                  LOCAL << int e; string id;>>
74    ident<<out id>>                                                       SEM  << r = symTab.GetValue(id) + 1; symTab.SetValue(id, r); >>
75  .
76  DecStat<<out int r>> =                                                  LOCAL << int e; string id;>>
77    ident<<out id>>                                                       SEM  << r = symTab.GetValue(id) - 1; symTab.SetValue(id, r); >>
78  .
79
80  WhileStat<<out int r>> =                                                LOCAL << bool b; int c = 0; >>
81                                                                          SEM  << r = 0; >>
82                                                                          SEM  << while(true && c++ < 100) { >>
83    BooleanExpr<<out b>>                                                  SEM  << if(!b) break; >>
84    StatSeq<<out r>>                                                      SEM  << } >>
85  .
86  Expr<<out int r>> =                                                     LOCAL << string id; >>
87    AdditionExpr<<out r>>
88    | SubtractionExpr<<out r>>
89    | MultiplicationExpr<<out r>>
90    | DivisionExpr<<out r>>
91    | Const<<out r>>
92    | ident<<out id>>                                                      SEM  << r = symTab.GetValue(id); >>
93  .
94  AdditionExpr<<out int r>> =                                              LOCAL << int e1, e2; >>
95     Expr<<out e1>> Expr<<out e2>>                                         SEM  << r = e1 + e2; >>
96  .
97  SubtractionExpr<<out int r>> =                                           LOCAL << int e1, e2; >>
98    Expr<<out e1>> Expr<<out e2>>                                          SEM  << r = e1 - e2; >>
99  .
100  MultiplicationExpr<<out int r>> =                                        LOCAL << int e1, e2; >>
101    Expr<<out e1>> Expr<<out e2>>                                          SEM  << r = e1 * e2; >>
102  .
103  DivisionExpr<<out int r>> =                                              LOCAL << int e1, e2; >>
104    Expr<<out e1>> Expr<<out e2>>                                          SEM  << r = e2 == 0 ? 1 : e1 / e2; >>
105  .
106  BooleanExpr<<out bool b>> =
107    LessThanExpr<<out b>>
108    | EqualExpr<<out b>>
109    | NotExpr<<out b>>
110  .
111  NotExpr<<out bool b>> =                                                  LOCAL << bool notB; >>
112    BooleanExpr<<out notB>>                                                SEM  << b = !notB; >>
113  .
114  LessThanExpr<<out bool b>> =                                             LOCAL << int lhs, rhs; >>
115    Expr<<out lhs>> Expr<<out rhs>>                                        SEM  << b = lhs < rhs; >>
116  .
117  EqualExpr<<out bool b>> =                                                LOCAL << int lhs, rhs; >>
118    Expr<<out lhs>> Expr<<out rhs>>                                        SEM  << b = lhs == rhs; >>
119  .
120 
121 
122MINIMIZE
123  <<
124    var ns = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
125    var expected = new int[] { 1,1,2,3,5,8,13,21,34,55, 89};
126   
127    double sumOfAbsoluteErrors = 0;
128    for(int i=0;i<ns.Length;i++) {
129      int actualResult;
130      Program(ns[i], out actualResult);
131      sumOfAbsoluteErrors += Math.Abs(expected[i] - actualResult);
132    }
133   
134    return sumOfAbsoluteErrors;
135  >>
136
137 
138END Fib.
Note: See TracBrowser for help on using the repository browser.