lambda.y

   1 %define parse.error verbose
   2 %{
   3 #include "lambda.h"
   4 #include "lambda.tab.h"
   5 #include "lambda.yy.h"
   6 #include "mem.h"
   7 #include "print.h"
   8 #include "reduce.h"
   9
  10 struct decllist *decls = NULL;
  11 extern int yylex();
  12
  13 int yydebug=1;
  14 void yyerror(const char *str)
  15 {
  16         fprintf(stderr, "parse error: %s\n", str);
  17 }
  18
  19 int yywrap()
  20 {
  21         struct decllist *t;
  22         while(decls != NULL){
  23                 free(decls->ident);
  24                 lambda_free(decls->value);
  25                 t = decls->next;
  26                 free(decls);
  27                 decls = t;
  28         }
  29         return 1;
  30 }
  31
  32 struct lambda *make_lambda()
  33 {
  34         return malloc(sizeof (struct lambda));
  35 }
  36
  37 struct lambda *make_ident(char *i)
  38 {
  39         struct lambda *r = make_lambda();
  40         r->which = lambda_ident;
  41         r->data.identifier.ident = strdup(i);
  42         r->data.identifier.revision = 0;
  43         return r;
  44 }
  45
  46 struct lambda *make_abstraction(char *i, bool strict, struct lambda *t)
  47 {
  48         struct lambda *r = make_lambda();
  49         r->which = lambda_abs;
  50         r->data.abstraction.ident = strdup(i);
  51         r->data.abstraction.revision = 0;
  52         r->data.abstraction.strict = strict;
  53         r->data.abstraction.expr = t;
  54         return r;
  55 }
  56
  57 struct lambda *make_application(struct lambda *t1, struct lambda *t2)
  58 {
  59         struct lambda *r = make_lambda();
  60         r->which = lambda_app;
  61         r->data.application.expr1 = t1;
  62         r->data.application.expr2 = t2;
  63         return r;
  64 }
  65
  66 struct lambda *make_numeral(unsigned int i)
  67 {
  68         struct lambda *body = make_ident("x");
  69         while(i-- > 0)
  70                 body = make_application(make_ident("f"), body);
  71         return make_abstraction("f", false, make_abstraction("x", false, body));
  72 }
  73
  74 struct lambda *make_bool(bool b)
  75 {
  76         return b
  77                 ? make_abstraction("a", false, make_abstraction("b", false, make_ident("a")))
  78                 : make_abstraction("a", false, make_abstraction("b", false, make_ident("b")));
  79 }
  80
  81 void decls_prepend(char *ident, struct lambda *value)
  82 {
  83         struct decllist *head = malloc(sizeof (struct decllist));
  84         head->next = decls;
  85         head->ident = strdup(ident);
  86         head->value = value;
  87         decls = head;
  88 }
  89
  90 struct lambda *decls_lookup(char *ident)
  91 {
  92         struct decllist *c = decls;
  93         while(c != NULL){
  94                 if(strcmp(c->ident, ident) == 0)
  95                         return copy(c->value);
  96                 c = c->next;
  97         }
  98         return make_ident(ident);
  99 }
 100
 101 int main()
 102 {
 103         int r = yyparse();
 104         yylex_destroy();
 105         return r;
 106 }
 107
 108 %}
 109
 110 %token LAMBDA DOT OBRACE CBRACE IDENT FUNC SEMICOLON ASSIGN LITERAL BANG
 111
 112 %%
 113
 114 program
 115         :
 116         | lambda SEMICOLON program
 117 lambda
 118         : term
 119                 {
 120                         int maxdepth = 1000;
 121                         printf("     ");
 122                         lambda_reduce($1, $1, &maxdepth);
 123                         lambda_print($1, NULL);
 124                         lambda_free($1);
 125                 }
 126         | FUNC func
 127                 {
 128                         decls_prepend($1->data.identifier.ident, $2);
 129                         printf("%s = ", $1->data.identifier.ident);
 130                         lambda_print($2, NULL);
 131                         lambda_free($1);
 132                 }
 133 func
 134         : ASSIGN term
 135                 { $$ = $2; }
 136         | BANG IDENT func
 137                 {
 138                         $$ = make_abstraction($2->data.identifier.ident, true, $3);
 139                         lambda_free($2);
 140                 }
 141         | IDENT func
 142                 {
 143                         $$ = make_abstraction($1->data.identifier.ident, false, $2);
 144                         lambda_free($1);
 145                 }
 146 term
 147         : term appterm
 148                 { $$ = make_application($1, $2); }
 149         | appterm
 150                 { $$ = $1; }
 151 appterm
 152         : LITERAL
 153                 { $$ = $1; }
 154         | FUNC
 155                 {
 156                         $$ = decls_lookup($1->data.identifier.ident);
 157                         lambda_free($1);
 158                 }
 159         | IDENT
 160                 { $$ = $1; }
 161         | LAMBDA abstraction
 162                 { $$ = $2; }
 163         | OBRACE term CBRACE
 164                 { $$ = $2; }
 165 abstraction
 166         : BANG IDENT abstraction
 167                 {
 168                         $$ = make_abstraction($2->data.identifier.ident, true, $3);
 169                         lambda_free($2);
 170                 }
 171         | IDENT abstraction
 172                 {
 173                         $$ = make_abstraction($1->data.identifier.ident, false, $2);
 174                         lambda_free($1);
 175                 }
 176         | DOT term
 177                 { $$ = $2; }