lambda.y

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