source: branches/HeuristicLab.Problems.GPDL/examples/Fib.txt @ 9573

PROBLEM Fib
CODE<<
  string[] allTerminals = new string[] {"a", "b", "c", "d", "e", "n"} ; 
  SymTab symTab = new SymTab();

  class SymTab {
    private Dictionary<string, int> values = new Dictionary<string,int>();
    public void SetValue(string id, int val) {
      values[id] = val;
    }
    public int GetValue(string id) {
      int val = 0;
      values.TryGetValue(id, out val);      
      return val;
    }
  }
>>

NONTERMINALS
  Program<<int n, out int r>>.                                       /* return value is the result of the last statement. */
  StatSeq<<out int r>>.                                                  
  AssignStat<<out int r>>.                                               /* result of assignment is the assigned value */
  IncStat<<out int r>>.
  DecStat<<out int r>>.
  WhileStat<<out int r>>.                                                /* result of while loop is the result of the last executed statement */
  ReturnStat<<out int r>>.  
  Expr<<out int r>>.
  AdditionExpr<<out int r>>.
  SubtractionExpr<<out int r>>.
  DivisionExpr<<out int r>>.
  MultiplicationExpr<<out int r>>.
  BooleanExpr<<out bool b>>.
  NotExpr<<out bool b>>.
  LessThanExpr<<out bool b>>.
  EqualExpr<<out bool b>>.
  AssignStatAndStatSeq<<out int r>>.
  WhileStatAndStatSeq<<out int r>>.
  ReturnStatAndStatSeq<<out int r>>.

TERMINALS
  ident<<out string id>> 
    CONSTRAINTS
    id IN SET << allTerminals; >>
  .
  Const<<out int val>> 
    CONSTRAINTS
    val IN SET << Enumerable.Range(0, 100); >>
  .
  Nothing<<out int val>>
     CONSTRAINTS
     val IN SET << Enumerable.Repeat(0, 1); >>
  .
  
RULES
  Program<<int n, out int r>> = StatSeq<<out r>>                         SEM << symTab.SetValue("n", n); >>
  .
  StatSeq<<out int r>> =                                                 LOCAL << r = 0; >>
    Nothing<<out r>>                                                              
    | AssignStatAndStatSeq<<out r>>
    | WhileStatAndStatSeq<<out r>>
    | ReturnStatAndStatSeq<<out r>>
  | IncStat<<out r>>
  | DecStat<<out r>>
  .
  
  AssignStatAndStatSeq<<out int r>> = 
    StatSeq<<out r>>  AssignStat<<out r>> 
  .
  WhileStatAndStatSeq<<out int r>> = 
    StatSeq<<out r>> WhileStat<<out r>> 
  .
  ReturnStatAndStatSeq<<out int r>> = 
    StatSeq<<out r>>  ReturnStat<<out r>> 
  .

  AssignStat<<out int r>> =                                               LOCAL << int e; string id;>>
    ident<<out id>> Expr<<out e>>                                         SEM  << symTab.SetValue(id, e); r = e; >>
  .
  IncStat<<out int r>> =                                                  LOCAL << int e; string id;>>
    ident<<out id>>                                                       SEM  << r = symTab.GetValue(id) + 1; symTab.SetValue(id, r); >>
  .
  DecStat<<out int r>> =                                                  LOCAL << int e; string id;>>
    ident<<out id>>                                                       SEM  << r = symTab.GetValue(id) - 1; symTab.SetValue(id, r); >>
  .

  WhileStat<<out int r>> =                                                LOCAL << bool b; int c = 0; >>
                                                                          SEM  << r = 0; >>
                                                                          SEM  << while(true && c++ < 100) { >>
    BooleanExpr<<out b>>                                                  SEM  << if(!b) break; >>
    StatSeq<<out r>>                                                      SEM  << } >>
  .
  ReturnStat<<out int r>> = Expr<<out r>>                                 SEM  << return; >>
  .
  Expr<<out int r>> =                                                     LOCAL << string id; >>
    AdditionExpr<<out r>> 
    | SubtractionExpr<<out r>> 
    | MultiplicationExpr<<out r>> 
    | DivisionExpr<<out r>> 
    | Const<<out r>> 
    | ident<<out id>>                                                      SEM  << r = symTab.GetValue(id); >>
  .
  AdditionExpr<<out int r>> =                                              LOCAL << int e1, e2; >>
     Expr<<out e1>> Expr<<out e2>>                                         SEM  << r = e1 + e2; >>
  .
  SubtractionExpr<<out int r>> =                                           LOCAL << int e1, e2; >>
    Expr<<out e1>> Expr<<out e2>>                                          SEM  << r = e1 - e2; >>
  .
  MultiplicationExpr<<out int r>> =                                        LOCAL << int e1, e2; >>
    Expr<<out e1>> Expr<<out e2>>                                          SEM  << r = e1 * e2; >>
  .
  DivisionExpr<<out int r>> =                                              LOCAL << int e1, e2; >>
    Expr<<out e1>> Expr<<out e2>>                                          SEM  << r = e2 == 0 ? 1 : e1 / e2; >>
  .
  BooleanExpr<<out bool b>> = 
    LessThanExpr<<out b>> 
    | EqualExpr<<out b>> 
    | NotExpr<<out b>> 
  .
  NotExpr<<out bool b>> =                                                  LOCAL << bool notB; >>
    BooleanExpr<<out notB>>                                                SEM  << b = !notB; >>
  .
  LessThanExpr<<out bool b>> =                                             LOCAL << int lhs, rhs; >>
    Expr<<out lhs>> Expr<<out rhs>>                                        SEM  << b = lhs < rhs; >>
  .
  EqualExpr<<out bool b>> =                                                LOCAL << int lhs, rhs; >>
    Expr<<out lhs>> Expr<<out rhs>>                                        SEM  << b = lhs == rhs; >>
  .
  
  
MINIMIZE                                                   /* could also use the keyword MAXIMIZE here */
  <<
    var ns = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    var expected = new int[] { 1,1,2,3,5,8,13,21,34,55, 89};
    
    double sumOfAbsoluteErrors = 0;
    for(int i=0;i<ns.Length;i++) {
      int actualResult;
      Program(ns[i], out actualResult);
      sumOfAbsoluteErrors += Math.Abs(expected[i] - actualResult);
    }
    
    return sumOfAbsoluteErrors;
  >>

  
END Fib.