rx.c

ac3的解码程序

    {
      n->params.pair.left = a;
      n->params.pair.right = 0;
    }
  return n;
}


#ifdef __STDC__
RX_DECL void
rx_free_rexp (struct rx * rx, struct rexp_node * node)
#else
RX_DECL void
rx_free_rexp (rx, node)
     struct rx * rx;
     struct rexp_node * node;
#endif
{
  if (node)
    {
      switch (node->type)
	{
	case r_cset:
	  if (node->params.cset)
	    rx_free_cset (rx, node->params.cset);

	case r_side_effect:
	  break;
	  
	case r_concat:
	case r_alternate:
	case r_2phase_star:
	case r_opt:
	case r_star:
	  rx_free_rexp (rx, node->params.pair.left);
	  rx_free_rexp (rx, node->params.pair.right);
	  break;

	case r_data:
	  /* This shouldn't occur. */
	  break;
	}
      free ((char *)node);
    }
}


#ifdef __STDC__
RX_DECL struct rexp_node * 
rx_copy_rexp (struct rx *rx,
	   struct rexp_node *node)
#else
RX_DECL struct rexp_node * 
rx_copy_rexp (rx, node)
     struct rx *rx;
     struct rexp_node *node;
#endif
{
  if (!node)
    return 0;
  else
    {
      struct rexp_node *n = rexp_node (rx, node->type);
      if (!n)
	return 0;
      switch (node->type)
	{
	case r_cset:
	  n->params.cset = rx_copy_cset (rx, node->params.cset);
	  if (!n->params.cset)
	    {
	      rx_free_rexp (rx, n);
	      return 0;
	    }
	  break;

	case r_side_effect:
	  n->params.side_effect = node->params.side_effect;
	  break;

	case r_concat:
	case r_alternate:
	case r_opt:
	case r_2phase_star:
	case r_star:
	  n->params.pair.left =
	    rx_copy_rexp (rx, node->params.pair.left);
	  n->params.pair.right =
	    rx_copy_rexp (rx, node->params.pair.right);
	  if (   (node->params.pair.left && !n->params.pair.left)
	      || (node->params.pair.right && !n->params.pair.right))
	    {
	      rx_free_rexp  (rx, n);
	      return 0;
	    }
	  break;
	case r_data:
	  /* shouldn't happen */
	  break;
	}
      return n;
    }
}



/* This page: functions to build and destroy graphs that describe nfa's */

/* Constructs a new nfa node. */
#ifdef __STDC__
RX_DECL struct rx_nfa_state *
rx_nfa_state (struct rx *rx)
#else
RX_DECL struct rx_nfa_state *
rx_nfa_state (rx)
     struct rx *rx;
#endif
{
  struct rx_nfa_state * n = (struct rx_nfa_state *)malloc (sizeof (*n));
  if (!n)
    return 0;
  bzero (n, sizeof (*n));
  n->next = rx->nfa_states;
  rx->nfa_states = n;
  return n;
}


#ifdef __STDC__
RX_DECL void
rx_free_nfa_state (struct rx_nfa_state * n)
#else
RX_DECL void
rx_free_nfa_state (n)
  struct rx_nfa_state * n;
#endif
{
  free ((char *)n);
}


/* This looks up an nfa node, given a numeric id.  Numeric id's are
 * assigned after the nfa has been built.
 */
#ifdef __STDC__
RX_DECL struct rx_nfa_state * 
rx_id_to_nfa_state (struct rx * rx,
		    int id)
#else
RX_DECL struct rx_nfa_state * 
rx_id_to_nfa_state (rx, id)
     struct rx * rx;
     int id;
#endif
{
  struct rx_nfa_state * n;
  for (n = rx->nfa_states; n; n = n->next)
    if (n->id == id)
      return n;
  return 0;
}


/* This adds an edge between two nodes, but doesn't initialize the 
 * edge label.
 */

#ifdef __STDC__
RX_DECL struct rx_nfa_edge * 
rx_nfa_edge (struct rx *rx,
	     enum rx_nfa_etype type,
	     struct rx_nfa_state *start,
	     struct rx_nfa_state *dest)
#else
RX_DECL struct rx_nfa_edge * 
rx_nfa_edge (rx, type, start, dest)
     struct rx *rx;
     enum rx_nfa_etype type;
     struct rx_nfa_state *start;
     struct rx_nfa_state *dest;
#endif
{
  struct rx_nfa_edge *e;
  e = (struct rx_nfa_edge *)malloc (sizeof (*e));
  if (!e)
    return 0;
  e->next = start->edges;
  start->edges = e;
  e->type = type;
  e->dest = dest;
  return e;
}


#ifdef __STDC__
RX_DECL void
rx_free_nfa_edge (struct rx_nfa_edge * e)
#else
RX_DECL void
rx_free_nfa_edge (e)
     struct rx_nfa_edge * e;
#endif
{
  free ((char *)e);
}


/* This constructs a POSSIBLE_FUTURE, which is a kind epsilon-closure
 * of an NFA.  These are added to an nfa automaticly by eclose_nfa.
 */  

#ifdef __STDC__
static struct rx_possible_future * 
rx_possible_future (struct rx * rx,
		 struct rx_se_list * effects)
#else
static struct rx_possible_future * 
rx_possible_future (rx, effects)
     struct rx * rx;
     struct rx_se_list * effects;
#endif
{
  struct rx_possible_future *ec;
  ec = (struct rx_possible_future *) malloc (sizeof (*ec));
  if (!ec)
    return 0;
  ec->destset = 0;
  ec->next = 0;
  ec->effects = effects;
  return ec;
}


#ifdef __STDC__
static void
rx_free_possible_future (struct rx_possible_future * pf)
#else
static void
rx_free_possible_future (pf)
     struct rx_possible_future * pf;
#endif
{
  free ((char *)pf);
}


#ifdef __STDC__
RX_DECL void
rx_free_nfa (struct rx *rx)
#else
RX_DECL void
rx_free_nfa (rx)
     struct rx *rx;
#endif
{
  while (rx->nfa_states)
    {
      while (rx->nfa_states->edges)
	{
	  switch (rx->nfa_states->edges->type)
	    {
	    case ne_cset:
	      rx_free_cset (rx, rx->nfa_states->edges->params.cset);
	      break;
	    default:
	      break;
	    }
	  {
	    struct rx_nfa_edge * e;
	    e = rx->nfa_states->edges;
	    rx->nfa_states->edges = rx->nfa_states->edges->next;
	    rx_free_nfa_edge (e);
	  }
	} /* while (rx->nfa_states->edges) */
      {
	/* Iterate over the partial epsilon closures of rx->nfa_states */
	struct rx_possible_future * pf = rx->nfa_states->futures;
	while (pf)
	  {
	    struct rx_possible_future * pft = pf;
	    pf = pf->next;
	    rx_free_possible_future (pft);
	  }
      }
      {
	struct rx_nfa_state *n;
	n = rx->nfa_states;
	rx->nfa_states = rx->nfa_states->next;
	rx_free_nfa_state (n);
      }
    }
}



/* This page: translating a pattern expression into an nfa and doing the 
 * static part of the nfa->super-nfa translation.
 */

/* This is the thompson regexp->nfa algorithm. 
 * It is modified to allow for `side-effect epsilons.'  Those are
 * edges that are taken whenever a similar epsilon edge would be,
 * but which imply that some side effect occurs when the edge 
 * is taken.
 *
 * Side effects are used to model parts of the pattern langauge 
 * that are not regular (in the formal sense).
 */

#ifdef __STDC__
RX_DECL int
rx_build_nfa (struct rx *rx,
	      struct rexp_node *rexp,
	      struct rx_nfa_state **start,
	      struct rx_nfa_state **end)
#else
RX_DECL int
rx_build_nfa (rx, rexp, start, end)
     struct rx *rx;
     struct rexp_node *rexp;
     struct rx_nfa_state **start;
     struct rx_nfa_state **end;
#endif
{
  struct rx_nfa_edge *edge;

  /* Start & end nodes may have been allocated by the caller. */
  *start = *start ? *start : rx_nfa_state (rx);

  if (!*start)
    return 0;

  if (!rexp)
    {
      *end = *start;
      return 1;
    }

  *end = *end ? *end : rx_nfa_state (rx);

  if (!*end)
    {
      rx_free_nfa_state (*start);
      return 0;
    }

  switch (rexp->type)
    {
    case r_data:
      return 0;

    case r_cset:
      edge = rx_nfa_edge (rx, ne_cset, *start, *end);
      if (!edge)
	return 0;
      edge->params.cset = rx_copy_cset (rx, rexp->params.cset);
      if (!edge->params.cset)
	{
	  rx_free_nfa_edge (edge);
	  return 0;
	}
      return 1;
 
    case r_opt:
      return (rx_build_nfa (rx, rexp->params.pair.left, start, end)
	      && rx_nfa_edge (rx, ne_epsilon, *start, *end));

    case r_star:
      {
	struct rx_nfa_state * star_start = 0;
	struct rx_nfa_state * star_end = 0;
	return (rx_build_nfa (rx, rexp->params.pair.left,
			      &star_start, &star_end)
		&& star_start
		&& star_end
		&& rx_nfa_edge (rx, ne_epsilon, star_start, star_end)
		&& rx_nfa_edge (rx, ne_epsilon, *start, star_start)
		&& rx_nfa_edge (rx, ne_epsilon, star_end, *end)

		&& rx_nfa_edge (rx, ne_epsilon, star_end, star_start));
      }

    case r_2phase_star:
      {
	struct rx_nfa_state * star_start = 0;
	struct rx_nfa_state * star_end = 0;
	struct rx_nfa_state * loop_exp_start = 0;
	struct rx_nfa_state * loop_exp_end = 0;

	return (rx_build_nfa (rx, rexp->params.pair.left,
			      &star_start, &star_end)
		&& rx_build_nfa (rx, rexp->params.pair.right,
				 &loop_exp_start, &loop_exp_end)
		&& star_start
		&& star_end
		&& loop_exp_end
		&& loop_exp_start
		&& rx_nfa_edge (rx, ne_epsilon, star_start, *end)
		&& rx_nfa_edge (rx, ne_epsilon, *start, star_start)
		&& rx_nfa_edge (rx, ne_epsilon, star_end, *end)

		&& rx_nfa_edge (rx, ne_epsilon, star_end, loop_exp_start)
		&& rx_nfa_edge (rx, ne_epsilon, loop_exp_end, star_start));
      }


    case r_concat:
      {
	struct rx_nfa_state *shared = 0;
	return
	  (rx_build_nfa (rx, rexp->params.pair.left, start, &shared)
	   && rx_build_nfa (rx, rexp->params.pair.right, &shared, end));
      }

    case r_alternate:
      {
	struct rx_nfa_state *ls = 0;
	struct rx_nfa_state *le = 0;
	struct rx_nfa_state *rs = 0;
	struct rx_nfa_state *re = 0;
	return (rx_build_nfa (rx, rexp->params.pair.left, &ls, &le)
		&& rx_build_nfa (rx, rexp->params.pair.right, &rs, &re)
		&& rx_nfa_edge (rx, ne_epsilon, *start, ls)
		&& rx_nfa_edge (rx, ne_epsilon, *start, rs)
		&& rx_nfa_edge (rx, ne_epsilon, le, *end)
		&& rx_nfa_edge (rx, ne_epsilon, re, *end));
      }

    case r_side_effect:
      edge = rx_nfa_edge (rx, ne_side_effect, *start, *end);
      if (!edge)
	return 0;
      edge->params.side_effect = rexp->params.side_effect;
      return 1;
    }

  /* this should never happen */
  return 0;
}


/* RX_NAME_NFA_STATES identifies all nodes with outgoing non-epsilon
 * transitions.  Only these nodes can occur in super-states.  
 * All nodes are given an integer id. 
 * The id is non-negative if the node has non-epsilon out-transitions, negative
 * otherwise (this is because we want the non-negative ids to be used as 
 * array indexes in a few places).
 */

#ifdef __STDC__
RX_DECL void
rx_name_nfa_states (struct rx *rx)
#else
RX_DECL void
rx_name_nfa_states (rx)
     struct rx *rx;
#endif
{
  struct rx_nfa_state *n = rx->nfa_states;

  rx->nodec = 0;
  rx->epsnodec = -1;

  while (n)
    {
      struct rx_nfa_edge *e = n->edges;

      if (n->is_start)
	n->eclosure_needed = 1;

      while (e)
	{
	  switch (e->type)
	    {
	    case ne_epsilon:
	    case ne_side_effect:
	      break;

	    case ne_cset:
	      n->id = rx->nodec++;
	      {
		struct rx_nfa_edge *from_n = n->edges;
		while (from_n)
		  {
		    from_n->dest->eclosure_needed = 1;
		    from_n = from_n->next;
		  }
	      }
	      goto cont;
	    }
	  e = e->next;
	}
      n->id = rx->epsnodec--;
    cont:
      n = n->next;
    }
  rx->epsnodec = -rx->epsnodec;
}


/* This page: data structures for the static part of the nfa->supernfa
 * translation.
 *
 * There are side effect lists -- lists of side effects occuring
 * along an uninterrupted, acyclic path of side-effect epsilon edges.
 * Such paths are collapsed to single edges in the course of computing
 * epsilon closures.  Such single edges are labled with a list of all
 * the side effects entailed in crossing them.  Like lists of side
 * effects are made == by the constructors below.
 *
 * There are also nfa state sets.  These are used to hold a list of all
 * states reachable from a starting state for a given type of transition
 * and side effect list.   These are also hash-consed.
 */

/* The next several functions compare, construct, etc. lists of side
 * effects.  See ECLOSE_NFA (below) for details.
 */

/* Ordering of rx_se_list
 * (-1, 0, 1 return value convention).
 */

#ifdef __STDC__
static int 
se_list_cmp (void * va, void * vb)
#else
static int 
se_list_cmp (va, vb)
     void * va;
     void * vb;
#endif
{
  struct rx_se_list * a = (struct rx_se_list *)va;
  struct rx_se_list * b = (struct rx_se_list *)vb;

  return ((va == vb)
	  ? 0
	  : (!va
	     ? -1
	     : (!vb
		? 1
		: ((long)a->car < (long)b->car
		   ? 1
		   : ((long)a->car > (long)b->car
		      ? -1
		      : se_list_cmp ((void *)a->cdr, (void *)b->cdr))))));
}


#ifdef __STDC__
static int 
se_list_equal (void * va, void * vb)
#else
static int 
se_list_equal (va, vb)
     void * va;
     void * vb;
#endif
{
  return !(se_list_cmp (va, vb));
}

static struct rx_hash_rules se_list_hash_rules =
{
  se_list_equal,
  compiler_hash_alloc,
  compiler_free_hash,
  compiler_hash_item_alloc,
  compiler_free_hash_item
};


#ifdef __STDC__
static struct rx_se_list * 
side_effect_cons (struct rx * rx,
		  void * se, struct rx_se_list * list)
#else
static struct rx_se_list * 
side_effect_cons (rx, se, list)
     struct rx * rx;
     void * se;
     struct rx_se_list * list;
#endif
{
  struct rx_se_list * l;
  l = ((struct rx_se_list *) malloc (sizeof (*l)));
  if (!l)
    return 0;
  l->car = se;
  l->cdr = list;
  return l;
}


#ifdef __STDC__
static struct rx_se_list *
hash_cons_se_prog (struct rx * rx,
		   struct rx_hash * memo,
		   void * car, struct rx_se_list * cdr)
#else
static struct rx_se_list *
hash_cons_se_prog (rx, memo, car, cdr)
     struct rx * rx;