| 1 | PROBLEM Factorial
|
|---|
| 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 | 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 |
|
|---|
| 38 | TERMINALS
|
|---|
| 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 |
|
|---|
| 52 | RULES
|
|---|
| 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 |
|
|---|
| 87 | Expr<<out int r>> = LOCAL << string id; >>
|
|---|
| 88 | AdditionExpr<<out r>>
|
|---|
| 89 | | SubtractionExpr<<out r>>
|
|---|
| 90 | | MultiplicationExpr<<out r>>
|
|---|
| 91 | | DivisionExpr<<out r>>
|
|---|
| 92 | | Const<<out r>>
|
|---|
| 93 | | ident<<out id>> SEM << r = symTab.GetValue(id); >>
|
|---|
| 94 | .
|
|---|
| 95 | AdditionExpr<<out int r>> = LOCAL << int e1, e2; >>
|
|---|
| 96 | Expr<<out e1>> Expr<<out e2>> SEM << r = e1 + e2; >>
|
|---|
| 97 | .
|
|---|
| 98 | SubtractionExpr<<out int r>> = LOCAL << int e1, e2; >>
|
|---|
| 99 | Expr<<out e1>> Expr<<out e2>> SEM << r = e1 - e2; >>
|
|---|
| 100 | .
|
|---|
| 101 | MultiplicationExpr<<out int r>> = LOCAL << int e1, e2; >>
|
|---|
| 102 | Expr<<out e1>> Expr<<out e2>> SEM << r = e1 * e2; >>
|
|---|
| 103 | .
|
|---|
| 104 | DivisionExpr<<out int r>> = LOCAL << int e1, e2; >>
|
|---|
| 105 | Expr<<out e1>> Expr<<out e2>> SEM << r = e2 == 0 ? 1 : e1 / e2; >>
|
|---|
| 106 | .
|
|---|
| 107 | BooleanExpr<<out bool b>> =
|
|---|
| 108 | LessThanExpr<<out b>>
|
|---|
| 109 | | EqualExpr<<out b>>
|
|---|
| 110 | | NotExpr<<out b>>
|
|---|
| 111 | .
|
|---|
| 112 | NotExpr<<out bool b>> = LOCAL << bool notB; >>
|
|---|
| 113 | BooleanExpr<<out notB>> SEM << b = !notB; >>
|
|---|
| 114 | .
|
|---|
| 115 | LessThanExpr<<out bool b>> = LOCAL << int lhs, rhs; >>
|
|---|
| 116 | Expr<<out lhs>> Expr<<out rhs>> SEM << b = lhs < rhs; >>
|
|---|
| 117 | .
|
|---|
| 118 | EqualExpr<<out bool b>> = LOCAL << int lhs, rhs; >>
|
|---|
| 119 | Expr<<out lhs>> Expr<<out rhs>> SEM << b = lhs == rhs; >>
|
|---|
| 120 | .
|
|---|
| 121 |
|
|---|
| 122 |
|
|---|
| 123 | MINIMIZE
|
|---|
| 124 | <<
|
|---|
| 125 | var ns = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
|
|---|
| 126 | var expected = new int[] { 1,1,2,6,24,120,720,5040,40320,362880,3628800 };
|
|---|
| 127 |
|
|---|
| 128 | double sumOfLogAbsoluteErrors = 0;
|
|---|
| 129 | for(int i=0;i<ns.Length;i++) {
|
|---|
| 130 | int actualResult;
|
|---|
| 131 | Program(ns[i], out actualResult);
|
|---|
| 132 | sumOfLogAbsoluteErrors += Math.Log(Math.Abs(expected[i] - actualResult) + 1);
|
|---|
| 133 | }
|
|---|
| 134 |
|
|---|
| 135 | return sumOfLogAbsoluteErrors;
|
|---|
| 136 | >>
|
|---|
| 137 |
|
|---|
| 138 |
|
|---|
| 139 | END Factorial.
|
|---|
