Macro Lambda Calculus' syntax

[codedot]

Using yacc(1) and lex(1), specified by POSIX and available in Debian through packages `bison' and `flex', respectively, a parser was automatically generated for a simple language called Macro Lambda Calculus.

Makefile:

YFLAGS = -dv

test: mlc test.mlc
    ./mlc <test.mlc

mlc: parser.o lexer.o

clean:
    -rm -f mlc y.* *.o

Grammar file:

%token ID

%%

text: line '.' | line ';' text;

line: expr | expr ',' line;

expr: term | ID '=' term;

term: appl | ID ':' term;

appl: atom | appl atom;

atom: ID | '(' term ')';

Lex file:

%{
#include "y.tab.h"
%}

ID [[:alpha:]][[:alnum:]]*

%%

---.*|[ \t\n]+

{ID} return ID;

. return yytext[0];

Main C file:

#include <stdio.h>

extern int yyparse();

int main(int argc, char *argv[])
{
    yyparse();

    return 0;
}

int yywrap(void)
{
    return 1;
}

int yyerror(const char *msg)
{
    fprintf(stderr, "%s\n", msg);
    return 0;
}

Test MLC file:

--- Syntactic sugar

succ = n: f: x: f (n f x),
plus = m: n: f: x: n f (m f x),
mult = m: n: f: m (n f),
pred = n: f: x: n (g: h: h (g f)) (u: x) (u: u),
sub = m: n: n pred m;

zero = f: x: x,
one = f: x: f x,
two = f: x: f (f x),
three = f: x: f (f (f x)),
four = f: x: f (f (f (f x))),
five = f: x: f (f (f (f (f x))));

false = f: s: s,
true = f: s: f,
and = p: q: p q p,
or = p: q: p p q,
not = p: a: b: p b a,
ifthenelse = p: p,
iszero = n: n (x: false) true,
leq = m: n: iszero (sub m n);

pair = x: y: f: f x y,
first = p: p true,
second = p: p false,
nil = x: true,
null = p: p (x: y: false),
phi = x: pair (second x) (succ (second x)),

y = g: (x: g (x x)) (x: g (x x));

fact1 = f: n: ifthenelse (iszero n)
    one
    (mult n (f (pred n))),
fact = y fact1;

fibo1 = f: n: ifthenelse (leq n two)
    one
    (plus (f (pred n)) (f (pred (pred n)))),
fibo = y fibo1.