/* lpard.c: parser for simple lisp, with debug output
 * grammar:  sexpr  --->  alphanum   |   "("    tail
 *           tail   --->  ")"        |   sexpr  tail
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void sexpr(void);
void tail(void);
char gettoken(void);
void err(int);
void nestBlanks(int n);
void enter(char* s);
void leave(char* s);

char tok; /* the next token */
int debug = 1; /* produce debug output */
int nest; /* used for debug output */

void main(void) {
    tok = gettoken();
    sexpr();
}

/* sexpr: recognize a lisp s-expression */
void sexpr(void)
{
                         if (debug) enter("sexpr");
    if (isalnum(tok))
        ; /* nothing for now */
    else if (tok == '(')
        tail();
    else err(0);
                         if (debug) leave("sexpr");
}

/* tail: recognize tail end of a lisp s-expression */
void tail (void)
{
                         if (debug) enter("tail");
    tok = gettoken();
    if (tok == ')')
        ; /* nothing for now */
    else {
        sexpr();
        tail();
    }
                         if (debug) leave("tail");
}

/* err: error message */
void err(int i)
{
    printf("Error number: %ld\n", i);
    exit(1);
}

/* gettoken: fetch next token (here just a char) */
char gettoken(void)
{
    char ch;
    while (isspace(ch = getchar()) && ch != EOF)
        ;
    return ch;
}

/* nestBlanks: initial output for debug output */
void nestBlanks(int n)
{
    int i;
    for (i = 0; i < n-1; i++)
        printf("| ");
}

/* enter: called on function entry (debug output) */
void enter(char* s)
{
    if (debug) {
        nest++; nestBlanks(nest);
        printf("+Enter %s, \t tok: %c\n", s, tok);
    }
}

/* leave: called last when leaving (debug output) */
void leave(char* s)
{
    if (debug) {
        nestBlanks(nest); nest--;
        printf("+Leave %s, \t tok: %c\n", s, tok);
    }
}

ten42% cc -o lparsed lparsed.c

ten42% lparsed
a
+Enter sexpr,    tok: a
+Leave sexpr,    tok: a

ten42% lparsed
()
+Enter sexpr,    tok: (
| +Enter tail,   tok: (
| +Leave tail,   tok: )
+Leave sexpr,    tok: )

ten42% lparsed
(a b c)
+Enter sexpr,    tok: (
| +Enter tail,   tok: (
| | +Enter sexpr,        tok: a
| | +Leave sexpr,        tok: a
| | +Enter tail,         tok: a
| | | +Enter sexpr,      tok: b
| | | +Leave sexpr,      tok: b
| | | +Enter tail,       tok: b
| | | | +Enter sexpr,    tok: c
| | | | +Leave sexpr,    tok: c
| | | | +Enter tail,     tok: c
| | | | +Leave tail,     tok: )
| | | +Leave tail,       tok: )
| | +Leave tail,         tok: )
| +Leave tail,   tok: )
+Leave sexpr,    tok: )

ten42% lparsed
(a (b c (d) e))
+Enter sexpr,    tok: (
| +Enter tail,   tok: (
| | +Enter sexpr,        tok: a
| | +Leave sexpr,        tok: a
| | +Enter tail,         tok: a
| | | +Enter sexpr,      tok: (
| | | | +Enter tail,     tok: (
| | | | | +Enter sexpr,          tok: b
| | | | | +Leave sexpr,          tok: b
| | | | | +Enter tail,   tok: b
| | | | | | +Enter sexpr,        tok: c
| | | | | | +Leave sexpr,        tok: c
| | | | | | +Enter tail,         tok: c
| | | | | | | +Enter sexpr,      tok: (
| | | | | | | | +Enter tail,     tok: (
| | | | | | | | | +Enter sexpr,          tok: d
| | | | | | | | | +Leave sexpr,          tok: d
| | | | | | | | | +Enter tail,   tok: d
| | | | | | | | | +Leave tail,   tok: )
| | | | | | | | +Leave tail,     tok: )
| | | | | | | +Leave sexpr,      tok: )
| | | | | | | +Enter tail,       tok: )
| | | | | | | | +Enter sexpr,    tok: e
| | | | | | | | +Leave sexpr,    tok: e
| | | | | | | | +Enter tail,     tok: e
| | | | | | | | +Leave tail,     tok: )
| | | | | | | +Leave tail,       tok: )
| | | | | | +Leave tail,         tok: )
| | | | | +Leave tail,   tok: )
| | | | +Leave tail,     tok: )
| | | +Leave sexpr,      tok: )
| | | +Enter tail,       tok: )
| | | +Leave tail,       tok: )
| | +Leave tail,         tok: )
| +Leave tail,   tok: )
+Leave sexpr,    tok: )

ten42% lparsed
((((a))))
+Enter sexpr,    tok: (
| +Enter tail,   tok: (
| | +Enter sexpr,        tok: (
| | | +Enter tail,       tok: (
| | | | +Enter sexpr,    tok: (
| | | | | +Enter tail,   tok: (
| | | | | | +Enter sexpr,        tok: (
| | | | | | | +Enter tail,       tok: (
| | | | | | | | +Enter sexpr,    tok: a
| | | | | | | | +Leave sexpr,    tok: a
| | | | | | | | +Enter tail,     tok: a
| | | | | | | | +Leave tail,     tok: )
| | | | | | | +Leave tail,       tok: )
| | | | | | +Leave sexpr,        tok: )
| | | | | | +Enter tail,         tok: )
| | | | | | +Leave tail,         tok: )
| | | | | +Leave tail,   tok: )
| | | | +Leave sexpr,    tok: )
| | | | +Enter tail,     tok: )
| | | | +Leave tail,     tok: )
| | | +Leave tail,       tok: )
| | +Leave sexpr,        tok: )
| | +Enter tail,         tok: )
| | +Leave tail,         tok: )
| +Leave tail,   tok: )
+Leave sexpr,    tok: )