parser.c

机器人足球AI设计比赛

/** 

SFSEXP: Small, Fast S-Expression Library version 1.0
Written by Matthew Sottile ([e-mail])

Copyright (2004). The Regents of the University of California. This material
was produced under U.S. Government contract W-7405-ENG-36 for Los Alamos
National Laboratory, which is operated by the University of California for
the U.S. Department of Energy. The U.S. Government has rights to use,
reproduce, and distribute this software. NEITHER THE GOVERNMENT NOR THE
UNIVERSITY MAKES ANY WARRANTY, EXPRESS OR IMPLIED, OR ASSUMES ANY LIABILITY
FOR THE USE OF THIS SOFTWARE. If software is modified to produce derivative
works, such modified software should be clearly marked, so as not to confuse
it with the version available from LANL.

Additionally, this program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or (at your
option) any later version. Accordingly, this program is distributed in the
hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
the GNU General Public License for more details.

LA-CC-04-094

**/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "sexp.h"
#include "faststack.h"

/*
 * constants related to atom buffer sizes and growth.
 */
static size_t sexp_val_start_size = 256;
static size_t sexp_val_grow_size  = 64;

/*
 * Function for tuning growth parameters.
 */
void set_parser_buffer_params(size_t ss, size_t gs) {
  if (ss > 0)
    sexp_val_start_size = ss;
  else 
    fprintf(stderr,"%s: Cannot set buffer start size to value<1.\n",__FILE__);

  if (gs > 0)
    sexp_val_grow_size = gs;
  else
    fprintf(stderr,"%s: Cannot set buffer grow size to value<1.\n",__FILE__);
}

/**
 * this structure is pushed onto the stack so we can keep track of the
 * first and last elements in a list.
 * !!!!DON'T USE THESE OUTSIDE THIS FILE!!!!
 */
typedef struct parse_stack_data
{
  sexp_t *fst, *lst;
}
parse_data_t;

/**
 * parse_data_t stack - similar malloc prevention to sexp_t_cache.
 */
faststack_t *pd_cache;

/** 
 * The global <I>sexp_t_cache</I> is a faststack implementing a cache of
 * pre-alloced s-expression element entities.  Odds are a user should never 
 * touch this.  If you do, you're on your own.  This is used internally by 
 * the parser and related code to store unused but allocated sexp_t elements.
 * This should be left alone and manipulated only by the sexp_t_allocate and
 * sexp_t_deallocate functions.  Touching the stack is bad.  
 */ 
faststack_t *sexp_t_cache;

/**
 * sexp_t allocation
 */
#ifdef _NO_MEMORY_MANAGEMENT_
sexp_t *
sexp_t_allocate(void) {
  sexp_t *sx = (sexp_t *) sexp_calloc(1, sizeof(sexp_t));
  assert(sx != NULL);

  return(sx);
}
#else
sexp_t *
sexp_t_allocate(void) {
  sexp_t *sx;
  stack_lvl_t *l;

  if (sexp_t_cache == NULL) {
    sexp_t_cache = make_stack();

    sx = (sexp_t *)sexp_malloc(sizeof(sexp_t));
    assert(sx != NULL);

    sx->next = sx->list = NULL;
  } else {
    if (empty_stack(sexp_t_cache)) {
      sx = (sexp_t *)sexp_malloc(sizeof(sexp_t));
      assert(sx != NULL);

      sx->next = sx->list = NULL;
    } else {
      l = pop(sexp_t_cache);
      sx = (sexp_t *)l->data;
    }
  }

  return sx;
}
#endif

/**
 * sexp_t de-allocation
 */
#ifdef _NO_MEMORY_MANAGEMENT_
void
sexp_t_deallocate(sexp_t *s) {
  if (s->ty == SEXP_VALUE && s->val != NULL) {
    sexp_free(s->val,s->val_allocated);
  }

  sexp_free(s,sizeof(sexp_t));
}
#else
void
sexp_t_deallocate(sexp_t *s) {
  if (sexp_t_cache == NULL) sexp_t_cache = make_stack();

  if (s == NULL) return;

  s->list = s->next = NULL;

  if (s->ty == SEXP_VALUE && s->val != NULL) {
    sexp_free(s->val,s->val_allocated);
  }

  s->val = NULL;

  sexp_t_cache = push(sexp_t_cache, s);
}
#endif

/**
 * cleanup the sexp library.  Note this is implemented HERE since we need
 * to know about pd_cache, which is local to this file.
 */
#ifdef _NO_MEMORY_MANAGEMENT_
void sexp_cleanup(void) {
}
#else
void sexp_cleanup(void) {
  stack_lvl_t *l;

  if (pd_cache != NULL) {
    l = pd_cache->top;
    while (l != NULL) {
      sexp_free(l->data,sizeof(sexp_t));
      l = l->below;
    }
    destroy_stack(pd_cache);
    pd_cache = NULL;
  }

  if (sexp_t_cache != NULL) {
    l = sexp_t_cache->top;
    while (l != NULL) {
      sexp_free(l->data,sizeof(sexp_t));
      l = l->below;
    }
    destroy_stack(sexp_t_cache);
    sexp_t_cache = NULL;
  }
}
#endif

/**
 * allocation
 */
parse_data_t *
pd_allocate(void) {
  parse_data_t *p;
  stack_lvl_t *l;

  if (pd_cache == NULL) {
    pd_cache = make_stack();
    p = (parse_data_t *)sexp_malloc(sizeof(parse_data_t));
    assert(p!=NULL);
  } else {
    if (empty_stack(pd_cache)) {
      p = (parse_data_t *)sexp_malloc(sizeof(parse_data_t));
      assert(p!=NULL);
    } else {
      l = pop(pd_cache);
      p = (parse_data_t *)l->data;
    }
  }

  return p;
}

/**
 * de-allocation
 */
void
pd_deallocate(parse_data_t *p) {
  if (pd_cache == NULL) pd_cache = make_stack();

  pd_cache = push(pd_cache, p);
}

/**
 * Destroy a continuation by freeing all of its fields that it is responsible
 * for managing, and then free the continuation itself.  This includes internal
 * buffers, stacks, etc..
 */
void
destroy_continuation (pcont_t * pc)
{
  stack_lvl_t *lvl;
  parse_data_t *lvl_data;

  if (pc == NULL) return; /* return if null passed in */

  if (pc->stack != NULL) {
    lvl = pc->stack->top;
    
    /*
     * note that destroy_stack() does not free the data hanging off of the
     * stack.  we have to walk down the stack and do that here. 
     */
    
    while (lvl != NULL) {
      lvl_data = (parse_data_t *)lvl->data;

      /**
       * Seems to have fixed bug with destroying partially parsed
       * expression continuations with the short three lines below.
       */
      if (lvl_data != NULL) {
        lvl_data->lst = NULL;
        destroy_sexp(lvl_data->fst);
        lvl_data->fst = NULL;

        pd_deallocate(lvl_data);
        lvl->data = lvl_data = NULL;
      }

      lvl = lvl->below;
    }
    
    /*
     * stack has no data on it anymore, so we can free it.
     */
    destroy_stack(pc->stack);
    pc->stack = NULL;
  }

  /*
   * free up data used for INLINE_BINARY mode
   */
  if (pc->bindata != NULL) {
    sexp_free(pc->bindata,pc->binexpected);
    pc->bindata = NULL;
  }

  /*
   * free up other allocated data
   */
  sexp_free (pc->val,pc->val_allocated);
  sexp_free (pc,sizeof(pcont_t));
}

/* 
 * wrapper around cparse_sexp.  assumes s contains a single, complete,
 * null terminated s-expression.  partial sexps or strings containing more
 * than one will act up.
 */
sexp_t *
parse_sexp (char *s, size_t len)
{
  pcont_t *pc = NULL;
  sexp_t *sx = NULL;

  if (len < 1 || s == NULL) return NULL; /* empty string - return */  

  pc = cparse_sexp (s, len, pc);
  sx = pc->last_sexp;

  destroy_continuation(pc);

  return sx;
}

pcont_t *
init_continuation(char *str) 
{
  pcont_t *cc;
  /* new continuation... */
  cc = (pcont_t *)sexp_malloc(sizeof(pcont_t));
  assert(cc != NULL);
  
  /* allocate atom buffer */
  cc->val = (char *)sexp_malloc(sizeof(char)*sexp_val_start_size);
  assert(cc->val != NULL);
  
  /* by default we assume a normal parser */
  cc->mode = PARSER_NORMAL;

  cc->val_allocated = sexp_val_start_size;
  cc->val_used = 0;

  cc->bindata = NULL;
  cc->binread = cc->binexpected = 0;

  /* allocate stack */
  cc->esc = 0;
  cc->stack = make_stack();
  cc->sbuffer = str;
  cc->lastPos = NULL;
  cc->state = 1;
  cc->vcur = cc->val;
  cc->depth = 0;
  cc->qdepth = 0;
  cc->squoted = 0;

  return cc;
}

/**
 * Iterative parser.  Wrapper around parse_sexp that is slightly more
 * intelligent and allows users to iteratively "pop" the expressions
 * out of a string that contains a bunch of expressions.
 * Useful if you have a string like "(foo bar)(goo har)(moo mar)" and
 * want to get "(foo bar)", "(goo har)", and "(moo mar)" individually on
 * repeated calls.
 */
sexp_t *
iparse_sexp (char *s, size_t len, pcont_t *cc) {
  pcont_t *pc;
  sexp_t *sx = NULL;
  
  /* 
   * sanity check.
   */
  if (cc == NULL) {
    fprintf(stderr,"iparse_sexp called with null continuation!\n");
    return NULL;
  }
  
  /* call the parser */
  pc = cparse_sexp(s,len,cc);
  
  if (cc->last_sexp != NULL) {
    sx = cc->last_sexp;
    cc->last_sexp = NULL;
  }
  
  return sx;
}

/*************************************************************************/
/*************************************************************************/
/*************************************************************************/
/*************************************************************************/
/*************************************************************************/

/**
 * Continuation based parser - the guts of the package.
 */
pcont_t *
cparse_sexp (char *str, size_t len, pcont_t *lc)
{
  char *t, *s;
  register size_t       binexpected = 0;
  register size_t       binread = 0; 
  register unsigned int mode = PARSER_NORMAL;
  register size_t       val_allocated = 0;
  register unsigned int squoted = 0;
  register size_t       val_used = 0;
  register unsigned int state = 1;
  register unsigned int depth = 0;
  register unsigned int qdepth = 0;
  register unsigned int elts = 0;
  register unsigned int esc = 0;
  pcont_t *cc;
  char *val, *vcur, *bindata = NULL;
  sexp_t *sx = NULL;
  faststack_t *stack;
  parse_data_t *data;
  stack_lvl_t *lvl;
#ifdef _DEBUG_
  unsigned long fsm_iterations = 0;
  unsigned long maxdepth = 0;
#endif /* _DEBUG_ */
  char *bufEnd;
  int keepgoing = 1;

  /* make sure non-null string */
  if (str == NULL) {
    fprintf(stderr,"cparse_sexp: called with null string.\n");
    return lc;
  }
  
  /* first, if we have a non null continuation passed in, restore state. */
  if (lc != NULL) {
    cc = lc;
    binexpected = cc->binexpected;
    binread = cc->binread;
    bindata = cc->bindata;
    val_used = cc->val_used;
    val_allocated = cc->val_allocated;
    squoted = cc->squoted;
    val = cc->val;
    vcur = cc->vcur;
    state = cc->state;
    depth = cc->depth;
    qdepth = cc->qdepth;
    stack = cc->stack;
    esc = cc->esc;
    mode = cc->mode;
    s = str;
    if (cc->lastPos != NULL)
      t = cc->lastPos;
    else {