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, 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.expr = t;
  53         return r;
  54 }
  55
  56 struct lambda *make_application(struct lambda *t1, struct lambda *t2)
  57 {
  58         struct lambda *r = make_lambda();
  59         r->which = lambda_app;
  60         r->data.application.expr1 = t1;
  61         r->data.application.expr2 = t2;
  62         return r;
  63 }
  64
  65 struct lambda *make_numeral(unsigned int i)
  66 {
  67         struct lambda *body = make_ident("x");
  68         while(i-- > 0)
  69                 body = make_application(make_ident("f"), body);
  70         return make_abstraction("f", make_abstraction("x", body));
  71 }
  72
  73 struct lambda *make_bool(bool b)
  74 {
  75         return b
  76                 ? make_abstraction("a", make_abstraction("b", make_ident("a")))
  77                 : make_abstraction("a", make_abstraction("b", make_ident("b")));
  78 }
  79
  80 void decls_prepend(char *ident, struct lambda *value)
  81 {
  82         struct decllist *head = malloc(sizeof (struct decllist));
  83         head->next = decls;
  84         head->ident = strdup(ident);
  85         head->value = value;
  86         decls = head;
  87 }
  88
  89 struct lambda *decls_lookup(char *ident)
  90 {
  91         struct decllist *c = decls;
  92         while(c != NULL){
  93                 if(strcmp(c->ident, ident) == 0)
  94                         return copy(c->value);
  95                 c = c->next;
  96         }
  97         return make_ident(ident);
  98 }
  99
 100 int main()
 101 {
 102         int r = yyparse();
 103         yylex_destroy();
 104         return r;
 105 }
 106
 107 %}
 108
 109 %token LAMBDA DOT OBRACE CBRACE IDENT FUNC SEMICOLON ASSIGN LITERAL
 110
 111 %%
 112
 113 program
 114         :
 115         | lambda SEMICOLON program
 116 lambda
 117         : term
 118                 {
 119                         int maxdepth = 1000;
 120                         printf("     ");
 121                         lambda_reduce($1, $1, &maxdepth);
 122                         lambda_print($1, NULL);
 123                         lambda_free($1);
 124                 }
 125         | FUNC ASSIGN term
 126                 {
 127                         decls_prepend($1->data.identifier.ident, $3);
 128                         printf("%s = ", $1->data.identifier.ident);
 129                         lambda_print($3, NULL);
 130                         lambda_free($1);
 131                 }
 132 term
 133         : term appterm
 134                 { $$ = make_application($1, $2); }
 135         | appterm
 136                 { $$ = $1; }
 137 appterm
 138         : LITERAL
 139                 { $$ = $1; }
 140         | FUNC
 141                 {
 142                         $$ = decls_lookup($1->data.identifier.ident);
 143                         lambda_free($1);
 144                 }
 145         | IDENT
 146                 {
 147                         $$ = make_ident($1->data.identifier.ident);
 148                         lambda_free($1);
 149                 }
 150         | LAMBDA abstraction
 151                 { $$ = $2; }
 152         | OBRACE term CBRACE
 153                 { $$ = $2; }
 154 abstraction
 155         : IDENT abstraction
 156                 {
 157                         $$ = make_abstraction($1->data.identifier.ident, $2);
 158                         lambda_free($1);
 159                 }
 160         | DOT term
 161                 { $$ = $2; }