| 1 | PROBLEM Fib
|
|---|
| 2 | CODE<<
|
|---|
| 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 |
|
|---|
| 19 | NONTERMINALS
|
|---|
| 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 | ReturnStat<<out int r>>.
|
|---|
| 27 | Expr<<out int r>>.
|
|---|
| 28 | AdditionExpr<<out int r>>.
|
|---|
| 29 | SubtractionExpr<<out int r>>.
|
|---|
| 30 | DivisionExpr<<out int r>>.
|
|---|
| 31 | MultiplicationExpr<<out int r>>.
|
|---|
| 32 | BooleanExpr<<out bool b>>.
|
|---|
| 33 | NotExpr<<out bool b>>.
|
|---|
| 34 | LessThanExpr<<out bool b>>.
|
|---|
| 35 | EqualExpr<<out bool b>>.
|
|---|
| 36 | AssignStatAndStatSeq<<out int r>>.
|
|---|
| 37 | WhileStatAndStatSeq<<out int r>>.
|
|---|
| 38 | ReturnStatAndStatSeq<<out int r>>.
|
|---|
| 39 |
|
|---|
| 40 | TERMINALS
|
|---|
| 41 | ident<<out string id>>
|
|---|
| 42 | CONSTRAINTS
|
|---|
| 43 | id IN SET << allTerminals; >>
|
|---|
| 44 | .
|
|---|
| 45 | Const<<out int val>>
|
|---|
| 46 | CONSTRAINTS
|
|---|
| 47 | val IN SET << Enumerable.Range(0, 100); >>
|
|---|
| 48 | .
|
|---|
| 49 | Nothing<<out int val>>
|
|---|
| 50 | CONSTRAINTS
|
|---|
| 51 | val IN SET << Enumerable.Repeat(0, 1); >>
|
|---|
| 52 | .
|
|---|
| 53 |
|
|---|
| 54 | RULES
|
|---|
| 55 | Program<<int n, out int r>> = StatSeq<<out r>> SEM << symTab.SetValue("n", n); >>
|
|---|
| 56 | .
|
|---|
| 57 | StatSeq<<out int r>> = LOCAL << r = 0; >>
|
|---|
| 58 | Nothing<<out r>>
|
|---|
| 59 | | AssignStatAndStatSeq<<out r>>
|
|---|
| 60 | | WhileStatAndStatSeq<<out r>>
|
|---|
| 61 | | ReturnStatAndStatSeq<<out r>>
|
|---|
| 62 | | IncStat<<out r>>
|
|---|
| 63 | | DecStat<<out r>>
|
|---|
| 64 | .
|
|---|
| 65 |
|
|---|
| 66 | AssignStatAndStatSeq<<out int r>> =
|
|---|
| 67 | StatSeq<<out r>> AssignStat<<out r>>
|
|---|
| 68 | .
|
|---|
| 69 | WhileStatAndStatSeq<<out int r>> =
|
|---|
| 70 | StatSeq<<out r>> WhileStat<<out r>>
|
|---|
| 71 | .
|
|---|
| 72 | ReturnStatAndStatSeq<<out int r>> =
|
|---|
| 73 | StatSeq<<out r>> ReturnStat<<out r>>
|
|---|
| 74 | .
|
|---|
| 75 |
|
|---|
| 76 | AssignStat<<out int r>> = LOCAL << int e; string id;>>
|
|---|
| 77 | ident<<out id>> Expr<<out e>> SEM << symTab.SetValue(id, e); r = e; >>
|
|---|
| 78 | .
|
|---|
| 79 | IncStat<<out int r>> = LOCAL << int e; string id;>>
|
|---|
| 80 | ident<<out id>> SEM << r = symTab.GetValue(id) + 1; symTab.SetValue(id, r); >>
|
|---|
| 81 | .
|
|---|
| 82 | DecStat<<out int r>> = LOCAL << int e; string id;>>
|
|---|
| 83 | ident<<out id>> SEM << r = symTab.GetValue(id) - 1; symTab.SetValue(id, r); >>
|
|---|
| 84 | .
|
|---|
| 85 |
|
|---|
| 86 | WhileStat<<out int r>> = LOCAL << bool b; int c = 0; >>
|
|---|
| 87 | SEM << r = 0; >>
|
|---|
| 88 | SEM << while(true && c++ < 100) { >>
|
|---|
| 89 | BooleanExpr<<out b>> SEM << if(!b) break; >>
|
|---|
| 90 | StatSeq<<out r>> SEM << } >>
|
|---|
| 91 | .
|
|---|
| 92 | ReturnStat<<out int r>> = Expr<<out r>> SEM << return; >>
|
|---|
| 93 | .
|
|---|
| 94 | Expr<<out int r>> = LOCAL << string id; >>
|
|---|
| 95 | AdditionExpr<<out r>>
|
|---|
| 96 | | SubtractionExpr<<out r>>
|
|---|
| 97 | | MultiplicationExpr<<out r>>
|
|---|
| 98 | | DivisionExpr<<out r>>
|
|---|
| 99 | | Const<<out r>>
|
|---|
| 100 | | ident<<out id>> SEM << r = symTab.GetValue(id); >>
|
|---|
| 101 | .
|
|---|
| 102 | AdditionExpr<<out int r>> = LOCAL << int e1, e2; >>
|
|---|
| 103 | Expr<<out e1>> Expr<<out e2>> SEM << r = e1 + e2; >>
|
|---|
| 104 | .
|
|---|
| 105 | SubtractionExpr<<out int r>> = LOCAL << int e1, e2; >>
|
|---|
| 106 | Expr<<out e1>> Expr<<out e2>> SEM << r = e1 - e2; >>
|
|---|
| 107 | .
|
|---|
| 108 | MultiplicationExpr<<out int r>> = LOCAL << int e1, e2; >>
|
|---|
| 109 | Expr<<out e1>> Expr<<out e2>> SEM << r = e1 * e2; >>
|
|---|
| 110 | .
|
|---|
| 111 | DivisionExpr<<out int r>> = LOCAL << int e1, e2; >>
|
|---|
| 112 | Expr<<out e1>> Expr<<out e2>> SEM << r = e2 == 0 ? 1 : e1 / e2; >>
|
|---|
| 113 | .
|
|---|
| 114 | BooleanExpr<<out bool b>> =
|
|---|
| 115 | LessThanExpr<<out b>>
|
|---|
| 116 | | EqualExpr<<out b>>
|
|---|
| 117 | | NotExpr<<out b>>
|
|---|
| 118 | .
|
|---|
| 119 | NotExpr<<out bool b>> = LOCAL << bool notB; >>
|
|---|
| 120 | BooleanExpr<<out notB>> SEM << b = !notB; >>
|
|---|
| 121 | .
|
|---|
| 122 | LessThanExpr<<out bool b>> = LOCAL << int lhs, rhs; >>
|
|---|
| 123 | Expr<<out lhs>> Expr<<out rhs>> SEM << b = lhs < rhs; >>
|
|---|
| 124 | .
|
|---|
| 125 | EqualExpr<<out bool b>> = LOCAL << int lhs, rhs; >>
|
|---|
| 126 | Expr<<out lhs>> Expr<<out rhs>> SEM << b = lhs == rhs; >>
|
|---|
| 127 | .
|
|---|
| 128 |
|
|---|
| 129 |
|
|---|
| 130 | MINIMIZE /* could also use the keyword MAXIMIZE here */
|
|---|
| 131 | <<
|
|---|
| 132 | var ns = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
|
|---|
| 133 | var expected = new int[] { 1,1,2,3,5,8,13,21,34,55, 89};
|
|---|
| 134 |
|
|---|
| 135 | double sumOfAbsoluteErrors = 0;
|
|---|
| 136 | for(int i=0;i<ns.Length;i++) {
|
|---|
| 137 | int actualResult;
|
|---|
| 138 | Program(ns[i], out actualResult);
|
|---|
| 139 | sumOfAbsoluteErrors += Math.Abs(expected[i] - actualResult);
|
|---|
| 140 | }
|
|---|
| 141 |
|
|---|
| 142 | return sumOfAbsoluteErrors;
|
|---|
| 143 | >>
|
|---|
| 144 |
|
|---|
| 145 |
|
|---|
| 146 | END Fib.
|
|---|
