eric@snark.thyrsus.COM (Eric S. Raymond) (10/25/90)
I had so much fun writing this that I decided to share it...
/*
* stdemo.c -- demonstrate application of stack-threaded recursion
*
* This is excerpted from some enhancements I'm hacking into Xlife.
*
* An implementation problem with the state-quintuple format used for the
* transition-table compiler is that we need to apply the `code-generator'
* function to all glob patterns implied by an RE of the form
*
* <ss><ss><ss><ss><ss>
*
* where <ss> can be a digit or a digit set bracketed by [, ]; but there
* could be up to MAXSTATES to the 5th power of these, which is too many to
* generate into a scratch array or file and then crunch through.
*
* We cope with this using stack-threaded recursion, an idea cheerfully
* stolen from some obscure EMACS internals. We crunch through the RE, using
* recursion to build a pointer tree with attached values that's actually
* stored on the auto-variables stack! Maximum stack storage used is O(5);
*
* Whenever a call to the recursive parser terminates, the function to be
* applied gets fed the current `branch' of the in-stack tree.
*
* To demonstrate this, simply compile and run it, typing in REs on each line:
*
* $ stdemo
* 12345
* 1, 2, 3, 4, 5
*
* [012]78[34]2
* 0, 7, 8, 3, 2
* 0, 7, 8, 4, 2
* 1, 7, 8, 3, 2
* 1, 7, 8, 4, 2
* 2, 7, 8, 3, 2
* 2, 7, 8, 4, 2
*
* 12
* Wrong number of states.
* $
*
* Read on, and be enlightened...
* Eric S. Raymond
* (eric@snark.thyrsus.com)
*/
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define is_state(c) isdigit(c) /* is char a valid state indicator? */
#define stoi(c) ((c) - '0') /* state character to int */
#define RULESIZE 5 /* size of the tuples */
struct stackthread
{
int value;
struct stackthread *parent;
};
#define SUCCEED 0 /* parse OK */
#define E_NOCLOSE -1 /* missing close */
#define E_BADCHAR -2 /* invalid character */
#define E_WRONGNUM -3 /* wrong number of elements */
static int parse_recurse(parent, buf, ecount)
char *buf;
struct stackthread *parent;
int ecount;
{
struct stackthread st;
if (is_state(buf[0]))
{
/*
* Sequential cons of next state onto the tip of the branch
* passed on.
*/
st.parent = parent;
st.value = stoi(*buf);
return(parse_recurse(&st, buf + 1, ecount + 1));
}
else if (buf[0] == '[')
{
char *ep = strchr(buf, ']');
if (ep == (char *)NULL)
return(E_NOCLOSE);
/*
* Wild-carding time. We iterate through the set; for each member,
* we start a recurse from just past the *end* of the set.
*/
st.parent = parent;
while (is_state(*++buf))
{
int err;
st.value = stoi(*buf);
if ((err = parse_recurse(&st, ep + 1, ecount + 1)) < 0)
return(err);
}
return(SUCCEED);
}
else if (buf[0] == ']')
return(SUCCEED);
else if (buf[0] != '\n')
return(E_BADCHAR);
else if (ecount != RULESIZE)
return(E_WRONGNUM);
else
{
/* plug your function in here */
printf("%d, %d, %d, %d, %d\n",
parent->parent->parent->parent->parent->value,
parent->parent->parent->parent->value,
parent->parent->parent->value,
parent->parent->value,
parent->value);
return(SUCCEED);
}
}
int read_rules(fp)
FILE *fp;
{
char buf[80];
struct stackthread top;
/*
* Note: for applications where you don't know the length of the branch
* in advance, you can initialize the parent field of top to NULL and
* use that to detect end-of-list.
*/
while (fgets(buf, sizeof(buf), fp) != (char *)NULL)
{
int status;
if (buf[0] == '\n' || buf[0] == '\0')
continue;
else if ((status = parse_recurse(&top, buf, 0)) != SUCCEED)
return(status);
else
putchar('\n');
}
return(SUCCEED);
}
main()
{
switch(read_rules(stdin))
{
case SUCCEED:
(void) printf("OK.\n");
break;
case E_NOCLOSE:
(void) printf("Missing ] character.\n");
break;
case E_BADCHAR:
(void) printf("Invalid character.\n");
break;
case E_WRONGNUM:
(void) printf("Wrong number of states.\n");
break;
default:
(void) printf("Unknown error.\n");
break;
}
}
/* stdemo.c ends here */
--
Eric S. Raymond = ...!uunet!snark!eric (mad mastermind of TMN-Netnews)