home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / modelers / geomview / source.lha / Geomview / src / lib / oogl / util / fsa.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-25  |  8.9 KB  |  309 lines
  1. /* Copyright (c) 1992 The Geometry Center; University of Minnesota
  2.    1300 South Second Street;  Minneapolis, MN  55454, USA;
  3.    
  4. This file is part of geomview/OOGL. geomview/OOGL is free software;
  5. you can redistribute it and/or modify it only under the terms given in
  6. the file COPYING, which you should have received along with this file.
  7. This and other related software may be obtained via anonymous ftp from
  8. geom.umn.edu; email: software@geom.umn.edu. */
  9.  
  10. /* Authors: Charlie Gunn, Stuart Levy, Tamara Munzner, Mark Phillips */
  11.  
  12. /* $Id: fsa.c,v 1.11 1992/08/25 20:18:10 mbp Exp $
  13.  *
  14.  * fsa.c: finite state automaton for matching a finite set of strings
  15.  *
  16.  * The procedures in this file are documented in the manual page fsa.1,
  17.  * a formatted copy of which is in ../../../doc/fsa.man.
  18.  *
  19.  * Mark Phillips
  20.  * April 17, 1989: originally written
  21.  * Nov 18 1991: modified to allow > 1 fsa
  22.  */
  23.  
  24. #include <stdio.h>
  25. #include "ooglutil.h"
  26.  
  27. /* size of blocks in which to allocate state nodes */
  28. #define BLKSIZ 5
  29.  
  30. /* Special states and flags */
  31. #define ACCEPT -1
  32. #define REJECT -2
  33. #define ERROR  -3
  34.  
  35. /* Operation flags */
  36. #define PROGRAM 1
  37. #define PARSE   2
  38.  
  39. typedef struct Trule_s {
  40.   char            c;    /* char for this rule */
  41.   int              ns;    /* state to switch to */
  42.   struct Trule_s     *next;    /* ptr to next rule for this state */
  43. } Trule;
  44.  
  45. typedef struct State_s {
  46.   Trule *tlist;        /* list of transition rules for this state */
  47.   void *return_value;    /* value to return if we end in this state */
  48. } State;
  49.  
  50. typedef struct Fsa_s {
  51.   State **state;
  52.   int state_count;
  53.   void *reject_value;
  54.   int initial_state;
  55.   void *return_value;
  56. };
  57.  
  58. /* This must be included *after* the typedef struct Fsa_s above: */
  59. #include "fsa.h"
  60.  
  61. static Trule *new_trule_node(Fsa, int);
  62. static void *fsa_execute(Fsa, char *, void *, int);
  63. static int next_state(Fsa, int, char, void *, int);
  64. static int new_state(Fsa);
  65. static void delete_trule_list(Trule *);
  66.  
  67. /*-----------------------------------------------------------------------
  68.  * Function:    fsa_initialize
  69.  * Description:    Initialize an FSA
  70.  * Args  IN:    fsa: the fsa to initialize; if NULL, a new one is created
  71.  *        reject: value to return when parsing unacceptable
  72.  *          string
  73.  */
  74. Fsa fsa_initialize(Fsa fsa,void *reject)
  75. {
  76.   if (fsa == NULL)
  77.     fsa = OOGLNewE(struct Fsa_s, "struct Fsa");
  78.   else {
  79.     /* Clear out current program: */
  80.     while (fsa->state_count--) {
  81.       delete_trule_list( (fsa->state[fsa->state_count])->tlist );
  82.       OOGLFree((char*)(fsa->state[fsa->state_count]));
  83.     }
  84.     OOGLFree((char*)(fsa->state));
  85.   }
  86.   fsa->state_count = 0;
  87.   fsa->reject_value = reject;
  88.   fsa->initial_state = new_state(fsa);
  89.  
  90.   return fsa;
  91. }
  92.  
  93. /*-----------------------------------------------------------------------
  94.  * Function:    fsa_install
  95.  * Description:    Install a string in an FSA
  96.  * Args  IN:    fsa: the fsa to install into
  97.  *        s: the string to install
  98.  *        v: the value to return when s is parsed
  99.  * Returns:    v, unless there is not enough room in the FSA, in
  100.  *        which case the fsa's reject value is returned
  101.  */
  102. void *
  103. fsa_install(Fsa fsa,char *s,void *v)
  104. {
  105.   return(fsa_execute(fsa, s, v, PROGRAM));
  106. }
  107.  
  108. /*-----------------------------------------------------------------------
  109.  * Function:    fsa_parse
  110.  * Description:    Parse a string
  111.  * Args  IN:    fsa: the fsa to use
  112.  *        s: the string to parse
  113.  * Returns:    If s is acceptable, returns the value v that was
  114.  *        specified when s was installed with fsa_install().  If
  115.  *        v is not acceptable, returns the value of reject given
  116.  *        in the most recent call to fsa_initialize().
  117.  * Notes:    
  118.  */
  119. void *
  120. fsa_parse(Fsa fsa, char *s)
  121. {
  122.   return(fsa_execute(fsa, s, 0, PARSE));
  123. }
  124.  
  125. /*-----------------------------------------------------------------------
  126.  * Function:    fsa_execute
  127.  * Description:    parse or program (install) a string
  128.  * Args  IN:    fsa: the fsa to use
  129.  *        s: the string
  130.  *        v: value to correspond to string
  131.  *        op: PROGRAM or PARSE
  132.  * Returns:    Result of parsing or installing.  If op==PROGRAM, this
  133.  *        is always v, unless there is no more room in the FSA,
  134.  *        in which case it is the fsa' reject value.  If op==PARSE,
  135.  *        it is either v, or the reject value.
  136.  *
  137.  *        The philosophy of this procedure and procedure
  138.  *        next_state() is that programming the FSA and parsing a
  139.  *        string using the FSA are very similar processes; the
  140.  *        only difference is in what is done when there is no
  141.  *        rule for the current state corresponding to the
  142.  *        current input char.  When parsing, we return a
  143.  *        rejection.  When programming, we add a rule, and
  144.  *        possibly a new state.
  145.  *
  146.  *        If op==PROGRAM, s is added to list of acceptable
  147.  *        strings, and the FSA is programmed to return v for s.
  148.  *        If op==PARSE, the FSA is executed and returns value
  149.  *        corresponding to s, or reject value if s is not
  150.  *        acceptable.
  151.  */
  152. static void *
  153. fsa_execute(Fsa fsa,char *s, void *v, int op)
  154. {
  155.   int cs;            /* current state */
  156.  
  157.   if (s==NULL) return fsa->reject_value;
  158.   cs = fsa->initial_state;
  159.   fsa->return_value = fsa->reject_value;
  160.   while ( (cs != ACCEPT) && (cs != REJECT) && (cs != ERROR) ) {
  161.     cs = next_state(fsa, cs, *s, v, op);
  162.     ++s;
  163.   }
  164.   return( (cs == ERROR) ? fsa->reject_value : fsa->return_value );
  165. }
  166.  
  167. /*-----------------------------------------------------------------------
  168.  * Function:    next_state
  169.  * Description:    Get the next state based on current state and char
  170.  * Args  IN:    fsa: the fsa to use
  171.  *        cs: current state
  172.  *        c: current char
  173.  *        v: return value when programing
  174.  *        op: PROGRAM or PARSE
  175.  * Returns:    index of next state, or ERROR
  176.  * Notes:    If op==PROGRAM and no transition rule for c exists for
  177.  *        the current state, a new state is created and a
  178.  *        transition rule to that state is added to the current
  179.  *        state.
  180.  *
  181.  *        See also comments for fsa_execute().
  182.  */
  183. static int
  184. next_state(Fsa fsa, int cs, char c, void *v, int op)
  185. {
  186.   Trule *t;
  187.  
  188.   /* Check tlist of current state for rule for c */
  189.   t = (fsa->state[cs])->tlist;
  190.   while (t != NULL) {
  191.     if (t->c == c) {
  192.       /* We found rule for c; if next state is ACCEPT, set return value. */
  193.       /* Then return next state. */
  194.       if (t->ns == ACCEPT) {
  195.     if (op==PROGRAM)
  196.       fsa->return_value = (fsa->state[cs])->return_value = v;
  197.     else
  198.       fsa->return_value = (fsa->state[cs])->return_value;
  199.       }
  200.       return(t->ns);
  201.     }
  202.     t = t->next;
  203.   }
  204.   /* No rule for c present; if just parsing, return rejection */
  205.   if (op == PARSE) return(REJECT);
  206.  
  207.   /* Otherwise, add a rule for c to current state */
  208.  
  209.   /* Install a rule node for c in current state's tlist */
  210.   t = new_trule_node(fsa, cs);
  211.   if (t == NULL) return(ERROR);
  212.   t->c = c;
  213.  
  214.   /* Now specify the next state for this rule */
  215.   if (c == '\0') {
  216.     /* '\0' means end of a word, so set return value for this state */
  217.     /* to v and set the next state for this rule to ACCEPT */
  218.     fsa->return_value = (fsa->state[cs])->return_value = v;
  219.     t->ns = ACCEPT;
  220.   }
  221.   else {
  222.     /* Not '\0' means another char in word, so create a new state */
  223.     t->ns = new_state(fsa);
  224.     if (t->ns == ERROR) return(ERROR);
  225.   }
  226.  
  227.   return(t->ns);
  228. }
  229.  
  230. /*-----------------------------------------------------------------------
  231.  * Function:    new_trule_node
  232.  * Description:    return a ptr to a new trule node in the tlist of a state
  233.  * Args  IN:    fsa: the fsa to use
  234.  *        n: index of state to add node to
  235.  * Returns:    ptr to newly allowcated rule node
  236.  */
  237. static Trule *
  238. new_trule_node(Fsa fsa, int n)
  239. {
  240.   Trule *t, *tnew;
  241.  
  242.   /* Allocate and initialize the node */
  243.   tnew = OOGLNewE(Trule, "Trule *");
  244.   if (tnew == NULL) return(NULL);
  245.   tnew->c = '\1';
  246.   tnew->ns = REJECT;
  247.   tnew->next = NULL;
  248.  
  249.   /* Install it in tlist of state n */
  250.   if (fsa->state[n]->tlist == NULL) {
  251.     /* List is empty: */
  252.     fsa->state[n]->tlist = tnew;
  253.   }
  254.   else {
  255.     /* List is not empty; set t = last node in list, then add tnew to end */
  256.     t = fsa->state[n]->tlist;
  257.     while (t->next != NULL)  t = t->next;
  258.     t->next = tnew;
  259.   }
  260.  
  261.   /* Return ptr to the new trule node */
  262.   return(tnew);
  263. }
  264.  
  265. /*-----------------------------------------------------------------------
  266.  * Function:    new_state
  267.  * Description:    get a new state for an fsa
  268.  * Args:    fsa: the fsa to use
  269.  * Returns:    index (an int) of new state
  270.  */
  271. static int
  272. new_state(Fsa fsa)
  273. {
  274.   if (fsa->state_count == 0) {
  275.     fsa->state = OOGLNewNE(State *, BLKSIZ, "State *");
  276.   }
  277.   else if ((fsa->state_count % BLKSIZ == 0)) {
  278.     fsa->state =
  279.       OOGLRenewNE(State *,
  280.           fsa->state,
  281.           (fsa->state_count/BLKSIZ+1)*BLKSIZ,
  282.           "reallocating for State *");
  283.   }
  284.  
  285.   fsa->state[fsa->state_count] = OOGLNewE(State, "State");
  286.   if (fsa->state[fsa->state_count] == NULL) return(ERROR);
  287.   fsa->state[fsa->state_count]->return_value = fsa->reject_value;
  288.   fsa->state[fsa->state_count]->tlist = NULL;
  289.   ++fsa->state_count;
  290.   return(fsa->state_count-1);
  291. }
  292.  
  293. /*-----------------------------------------------------------------------
  294.  * Function:    delete_trule_list
  295.  * Description:    Delete a trule list, freeing up its nodes
  296.  * Args  IN:    tlist: ptr to first node in list
  297.  */
  298. static void
  299. delete_trule_list(Trule *tlist)
  300. {
  301.   Trule *t;
  302.  
  303.   while (tlist != NULL) {
  304.     t = tlist;
  305.     tlist = tlist->next;
  306.     OOGLFree((char*)t);
  307.   }
  308. }
  309.