lambda.y

   1 %{
   2 #include "lambda.h"
   3 #include "lambda.tab.h"
   4 #include "mem.h"
   5
   6 struct lambda *result;
   7 extern int yylex();
   8
   9 int yydebug=1;
  10 void yyerror(const char *str)
  11 {
  12         fprintf(stderr, "parse error: %s\n", str);
  13 }
  14
  15 int yywrap()
  16 {
  17         return 1;
  18 }
  19
  20 struct lambda *make_lambda()
  21 {
  22         return malloc(sizeof (struct lambda));
  23 }
  24
  25 struct lambda *make_ident(char *i)
  26 {
  27         struct lambda *r = make_lambda();
  28         r->which = lambda_ident;
  29         r->data.identifier = strdup(i);
  30         return r;
  31 }
  32
  33 struct lambda *make_abstraction(char *i, struct lambda *t)
  34 {
  35         struct lambda *r = make_lambda();
  36         r->which = lambda_abs;
  37         r->data.abstraction.ident = strdup(i);
  38         r->data.abstraction.expr = t;
  39         return r;
  40 }
  41
  42 struct lambda *make_application(struct lambda *t1, struct lambda *t2)
  43 {
  44         struct lambda *r = make_lambda();
  45         r->which = lambda_app;
  46         r->data.application.expr1 = t1;
  47         r->data.application.expr2 = t2;
  48         return r;
  49 }
  50
  51 %}
  52
  53 %token LAMBDA DOT OBRACE CBRACE IDENT I K S T F
  54
  55 %%
  56
  57 lambda
  58         : term
  59                 { result = $$; }
  60 term
  61         : term appterm
  62                 {
  63                         $$ = make_application($1, $2);
  64                 }
  65         | appterm
  66                 { $$ = $1; }
  67 appterm
  68         : IDENT
  69                 {
  70                         $$ = make_ident($1->data.identifier);
  71                         lambda_free($1);
  72                 }
  73         | LAMBDA IDENT DOT term
  74                 {
  75                         $$ = make_abstraction($2->data.identifier, $4);
  76                         lambda_free($2);
  77                 }
  78         | OBRACE term CBRACE
  79                 { $$ = $2; }
  80         | I
  81                 { $$ = make_abstraction("x", make_ident("x")); }
  82         | K
  83                 { $$ = make_abstraction("x", make_abstraction("y", make_ident("x"))); }
  84         | S
  85                 { $$ = make_abstraction("x", make_abstraction("y", make_abstraction("z",
  86                         make_application(make_application(make_ident("x"), make_ident("y")),
  87                                 make_application(make_ident("y"), make_ident("z"))))));
  88                 }
  89         | T
  90                 { $$ = make_abstraction("x", make_abstraction("y", make_ident("x"))); }
  91         | F
  92                 { $$ = make_abstraction("x", make_abstraction("y", make_ident("y"))); }