home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_200 / 228_01 / parser.c < prev    next >
Text File  |  1987-07-31  |  18KB  |  587 lines
  1. /*
  2. HEADER:         CUGXXX;
  3. TITLE:          Generalized, finite-state parser;
  4. DATE:           3-20-86;
  5. DESCRIPTION:    Powerful parser allowing extraction of single tokens from
  6.                 character strings.  User can specify delimiters/escape
  7.                 character.
  8. KEYWORDS:       Generalized finite-state parser, Parser;
  9. FILENAME:       PARSER.C;
  10. WARNINGS:       None;
  11. AUTHORS:        Lloyd Zusman;
  12. COMPILER:       DeSmet C;
  13. REFERENCES:     US-DISK 1308;
  14. ENDREF
  15. */
  16. #ifdef IGNORE_THIS
  17.  
  18. /*
  19.  
  20. NOTE:    lower down in this program description section, i have examples
  21.     of C code with embedded comments.  this "#ifdef" is here because
  22.     without it, the C compiler treats the end-of-comment delimiters
  23.     (asterisk-slash) as significant, and my examples start generating
  24.     code and errors.  the "#ifdef" causes this whole section to be
  25.     ignored, including the end-of-comment delimiters.
  26.  
  27.  
  28.     PARSER.C    Lloyd Zusman, Master Byte Software, Trump User Group
  29.             (408) 395-5693 (voice only)
  30.  
  31.     This program is a generalized, finite state token parser.  It's
  32.     it is the most powerful parser I've seen on any BBS (if I do say
  33.     so myself).  It allows you extract tokens one at a time from a
  34.     string of characters.  The characters used for white space, for
  35.     break characters, and for quotes can be specified.  Also,
  36.     characters in the string can be preceded by a specifiable escape
  37.     character which removes any special meaning the character may have.
  38.  
  39.     There are a lot of formal parameters in this subroutine call, but
  40.     once you get familiar with them, this routine is fairly easy to use.
  41.     "#define" macros can be used to generate simpler looking calls for
  42.     commonly used applications of this routine.
  43.  
  44.     First, some terminology:
  45.  
  46.     token            used here, a single unit of information in
  47.                 the form of a group of characters.
  48.  
  49.     white space        space that gets ignored (except within quotes
  50.                 or when escaped), like blanks and tabs.  in
  51.                 addition, white space terminates a non-quoted
  52.                 token.
  53.  
  54.     break character     a character that separates non-quoted tokens.
  55.                 commas are a common break character.  the
  56.                 usage of break characters to signal the end
  57.                 of a token is the same as that of white space,
  58.                 except multiple break characters with nothing
  59.                 or only white space between generate a null
  60.                 token for each two break characters together.
  61.  
  62.                 for example, if blank is set to be the white
  63.                 space and comma is set to be the break
  64.                 character, the line ...
  65.  
  66.                 A, B, C ,  , DEF
  67.  
  68.                 ... consists of 5 tokens:
  69.  
  70.                 1)    "A"
  71.                 2)    "B"
  72.                 3)    "C"
  73.                 4)    ""      (the null string)
  74.                 5)    "DEF"
  75.  
  76.     quote character     a character that, when surrounding a group
  77.                 of other characters, causes the group of
  78.                 characters to be treated as a single token,
  79.                 no matter how many white spaces or break
  80.                 characters exist in the group.    also, a
  81.                 token always terminates after the closing
  82.                 quote.    for example, if ' is the quote
  83.                 character, blank is white space, and comma
  84.                 is the break character, the following
  85.                 string ...
  86.  
  87.                 A, ' B, CD'EF GHI
  88.  
  89.                 ... consists of 4 tokens:
  90.  
  91.                 1)    "A"
  92.                 2)    " B, CD" (note the blanks & comma)
  93.                 3)    "EF"
  94.                 4)    "GHI"
  95.  
  96.                 the quote characters themselves do
  97.                 not appear in the resultant tokens.  the
  98.                 double quotes are delimiters i use here for
  99.                 documentation purposes only.
  100.  
  101.     escape character    a character which itself is ignored but
  102.                 which causes the next character to be
  103.                 used as is.  ^ and \ are often used as
  104.                 escape characters.  an escape in the last
  105.                 position of the string gets treated as a
  106.                 "normal" (i.e., non-quote, non-white,
  107.                 non-break, and non-escape) character.
  108.                 for example, assume white space, break
  109.                 character, and quote are the same as in the
  110.                 above examples, and further, assume that
  111.                 ^ is the escape character.  then, in the
  112.                 string ...
  113.  
  114.                 ABC, ' DEF ^' GH' I ^ J K^ L ^
  115.  
  116.                 ... there are 7 tokens:
  117.  
  118.                 1)    "ABC"
  119.                 2)    " DEF ' GH"
  120.                 3)    "I"
  121.                 4)    " "     (a lone blank)
  122.                 5)    "J"
  123.                 6)    "K L"
  124.                 7)    "^"     (passed as is at end of line)
  125.  
  126.  
  127.     OK, now that you have this background, here's how to call "parser":
  128.  
  129.     result=parser(flag,token,maxtok,string,white,break,quote,escape,
  130.               brkused,next,quoted)
  131.  
  132.     result:     0 if we haven't reached EOS (end of string), and
  133.             1 if we have (this is an "int").
  134.  
  135.     flag:        right now, only the low order 3 bits are used.
  136.             1 => convert non-quoted tokens to upper case
  137.             2 => convert non-quoted tokens to lower case
  138.             0 => do not convert non-quoted tokens
  139.             (this is a "char").
  140.  
  141.     token:        a character string containing the returned next token
  142.             (this is a "char[]").
  143.  
  144.     maxtok:     the maximum size of "token".  characters beyond
  145.             "maxtok" are truncated (this is an "int").
  146.  
  147.     string:     the string to be parsed (this is a "char[]").
  148.  
  149.     white:        a string of the valid white spaces.  example:
  150.  
  151.             char whitesp[]={" \t"};
  152.  
  153.             blank and tab will be valid white space (this is
  154.             a "char[]").
  155.  
  156.     break:        a string of the valid break characters.  example:
  157.  
  158.             char breakch[]={";,"};
  159.  
  160.             semicolon and comma will be valid break characters
  161.             (this is a "char[]").
  162.  
  163.             IMPORTANT:  do not use the name "break" as a C
  164.             variable, as this is a reserved word in C.
  165.  
  166.     quote:        a string of the valid quote characters.  an example
  167.             would be
  168.  
  169.             char whitesp[]={"'\"");
  170.  
  171.             (this causes single and double quotes to be valid)
  172.             note that a token starting with one of these characters
  173.             needs the same quote character to terminate it.
  174.  
  175.             for example,
  176.  
  177.             "ABC '
  178.  
  179.             is unterminated, but
  180.  
  181.             "DEF" and 'GHI'
  182.  
  183.             are properly terminated.  note that different quote
  184.             characters can appear on the same line; only for
  185.             a given token do the quote characters have to be
  186.             the same (this is a "char[]").
  187.  
  188.     escape:     the escape character (NOT a string ... only one
  189.             allowed).  use zero if none is desired (this is
  190.             a "char").
  191.  
  192.     brkused:    the break character used to terminate the current
  193.             token.    if the token was quoted, this will be the
  194.             quote used.  if the token is the last one on the
  195.             line, this will be zero (this is a pointer to a
  196.             "char").
  197.  
  198.     next:        this variable points to the first character of the
  199.             next token.  it gets reset by "parser" as it steps
  200.             through the string.  set it to 0 upon initialization,
  201.             and leave it alone after that.    you can change it
  202.             if you want to jump around in the string or re-parse
  203.             from the beginning, but be careful (this is a
  204.             pointer to an "int").
  205.  
  206.     quoted:     set to 1 (true) if the token was quoted and 0 (false)
  207.             if not.  you may need this information (for example:
  208.             in C, a string with quotes around it is a character
  209.             string, while one without is an identifier).
  210.  
  211.             (this is a pointer to a "char").
  212.  
  213.     Example 1:
  214.  
  215.     char *whitesp[]={" \t");        /* blank and tab */
  216.     char *breakch[]={",\r");        /* comma and carriage return */
  217.     char *quotech[]={"'\""};        /* single and double quote */
  218.     char escape='^';                /* "uparrow" is escape */
  219.  
  220.     main()
  221.     {
  222.       char *fgets(),line[81],brkused,quoted,token[81];
  223.       int i,next;
  224.  
  225.       while(fgets(line,80,stdin)!=NULL)    /* get line */
  226.       {
  227.  
  228.         printf("Line: %s",line);            /* already has <CR> */
  229.         i=0;
  230.  
  231.         next=0;                /* make sure you do this */
  232.  
  233.         while(parser(2,token,80,line,whitesp,breakch,quotech,escape,
  234.              &brkused,&next,"ed)==0)
  235.         {
  236.           printf(" Token %d = (%s)\n",++i,token);
  237.  
  238.           if(brkchar=='\r') /* <CR> is a break so it won't be included  */
  239.         break;        /* in the token.  treat as end-of-line here */
  240.         }
  241.       }
  242.     }
  243.  
  244.  
  245.  
  246.     In the above example, lines are read from stdin and broken up into
  247.     tokens.  All non-quoted tokens are converted to lower case.  Since
  248.     fgets() returns the final carriage return, we treat it as a break
  249.     character to keep it out of the returned token.  Also, since the only
  250.     way "parser" will return a non-zero error code is at end of line,
  251.     we test "brkchar" to see if we've gotten to the final carriage
  252.     return, and we explicitly break out of the inner loop if we've
  253.     hit it.  Note that since fgets() puts the final <CR> right before
  254.     the end-of-string, if we left out the "if(brkchar='\r')" test,
  255.     we'd get one extra null token (just as if the line ended with a
  256.     single comma).    Run this example to see how it all works.
  257.  
  258.     Example 2:
  259.  
  260.         .
  261.         .
  262.         .
  263.  
  264.     next=0;
  265.     result=parser(1, newstr, 80, str, "", "", "", 0, &brkused, &next,
  266.               "ed);
  267.         .
  268.         .
  269.         .
  270.  
  271.     this call takes whatever is in "str" and converts it to upper case,
  272.     putting the result in "newstr".
  273.  
  274.     *** end of examples ***
  275.  
  276.     in case you're interested, "parser.c" was inspired by a system
  277.     subroutine that comes as part of the PRIMOS operating system for
  278.     the Prime Computer:  "gt$par.plp".  i loosely patterned this routine
  279.     after the Prime routine.
  280.  
  281.     Revisions:
  282.  
  283.     09/30/84    Lloyd Zusman    Initial coding
  284.  
  285.  
  286. NOTE:    This program was developed to run on the "Trump Card" (a Z8000
  287.     CPU on a board specially adapted for plugging into an IBM PC).
  288.     The C compiler I used is fairly standard, and I assume this
  289.     program will compile pretty much "as is" on either the Lattice
  290.     C compiler or the Computer Innovations C compiler.  Any
  291.     incompatibilities between the Trump C compiler and these other
  292.     compilers should be minimal.
  293.  
  294.     Since the C compiler I used generates 32-bit pointers, you may
  295.     feel the urge to use the large model for Lattice or Computer
  296.     Innovations.  However, I don't think I do anything in this
  297.     program that depends on the pointers being any given size, so
  298.     you should be able to compile it using any "size" model you see
  299.     fit.
  300.  
  301.     Incidentally, this "Trump Card" I mentioned is something I'm
  302.     really happy with.  It has a 10 MHz Z8000 and up to 512K of
  303.     memory.  The memory is standard "4164"-type dynamic RAM, and
  304.     therefore the computer doesn't quite run at 10 MHz all the
  305.     time.  The fastest "4164" RAM I've been able to find is 120
  306.     nanosecond memory, but I'm pushing my "Trump Card" up to
  307.     9 MHz and it works just fine with these chips.
  308.  
  309.     There is a simple operating system that comes with this "Trump
  310.     Card", and you can go back and forth between it and your PC.
  311.     As of now (mid October, 1984), the Trump Card's operating system
  312.     doesn't quite support concurrent processes going simultaneously
  313.     on buth CPU's, but that capability should come out fairly soon.
  314.  
  315.     Other nice things that come with this card are:
  316.  
  317.         A Z80 emulator that lets you run CPM programs.
  318.  
  319.         A C compiler (mentioned above).  A 600+ line C program
  320.         that took 6.5 minutes to compile and link on the PC
  321.         (Computer Innovations C compiler, IBM PC standard
  322.         linker) took exactly 22 seconds to compile and link
  323.         on the Trump Card.  You could test and develop a C program
  324.         on the Trump Card, taking advantage of the speed, and then
  325.         move it over to the PC for one last re-compile when
  326.         you're ready to put it into production.  So far, the
  327.         only differences I could find between the Trump's C
  328.         compiler and Computer Innovations are (1) slight
  329.         differences in the format string in "printf" (these
  330.         normally won't even show up); (2) "register" data
  331.         types really get assigned to registers on the Trump
  332.         C compiler; (3) in-line machine language is allowed
  333.         in the Trump C compiler.
  334.  
  335.         A BASIC system that will run IBM's Basic programs
  336.         with very few changes, but quite a bit faster.
  337.  
  338.         A compiler for a language called "Y".  This is
  339.         a "multi-level language", which at it's lowest
  340.         level is just a Z8000 assembler, at the next highest
  341.         level lets you use C-like and Pascal-like constructs
  342.         in your assembly code, and at it's highest level is
  343.         a Meta-Compiler (like YACC, for example) which lets
  344.         you use Backus-Naur grammer constructs to define your
  345.         own high level languages.
  346.  
  347.         Software to make all or part of Trump memory look
  348.         like a ramdisk and/or a print spooler for your PC.
  349.  
  350.         Function calls (analogous to interrupt 021h in MS-DOS)
  351.         which let you do lots of things from applications
  352.         programs on the Trump card, including the ability to
  353.         initiate interrupts on the 8088.
  354.  
  355.         Other various and sundry things like an editor, a linker,
  356.         etc.
  357.  
  358.     Using this Trump Card has really brought home to me how far away
  359.     from "state of the art" these IBM PC's (and XT's and even AT's)
  360.     are.  IBM used slow, substandard technology in it's PC's, XT's,
  361.     and even AT's.  The 6.5-minute C compile and link that took 22
  362.     seconds on the Trump Card illustrates this point.  If you assume
  363.     that the Computer Innovations C compiler I used on the PC is twice
  364.     as slow as it could be (a fairly safe assumption:  Lattice runs
  365.     quite a bit faster), factoring that in still leaves an approximately
  366.     8-to-1 time differential that can only be accounted for by hardware
  367.     inefficiencies in the PC (the badly designed Intel 8088 chip, the
  368.     slow 4.7 MHz clock rate, etc.).  We can't even attribute this slowness
  369.     to the hard disk IBM uses (there are cheap, reliable, commercially
  370.     available internal 10 MB hard disks that are 3 times faster than
  371.     the ones IBM uses) nor to its bus, since the Trump Card uses the
  372.     same disk and the same bus.  Nor can we attribute it to the fact
  373.     that the Trump Card has 512 K of memory, since I have an AST
  374.     "Six Pack Plus" on my PC which has 384 K on it, so my total memory
  375.     on the PC side of things is 640 K.  If you have one of those new
  376.     AT's, you're still only running 3 times faster than the PC (this is
  377.     IBM's claim ... I'll bet you that in most real applications, it's not
  378.     even that fast), so the Trump card is still more than twice as fast
  379.     as the AT can ever hope to be.    What this all boils down to is that
  380.     it's necessary to soup up these PC's in order to make them capable
  381.     of doing anything useful in a reasonable period of time.  The Trump
  382.     Card is one of probably many good ways to turn your IBM PC into
  383.     a real computer.
  384.  
  385.     There was a writeup on the Trump Card in two consecutive recent
  386.     "Byte" issues (May and June, 1984, I believe).  If you're interested
  387.     in more information, you can contact me at the phone number above,
  388.     or you can dial into the official Trump BBS at (408) 923-5565 and
  389.     look around or leave a message for the Sysop.
  390.  
  391.     -Lloyd Zusman, Master Byte Software
  392.  
  393.  
  394. #endif        /* goes with initial "#ifdef" */
  395.  
  396. /* states */
  397.  
  398. #define IN_WHITE 0
  399. #define IN_TOKEN 1
  400. #define IN_QUOTE 2
  401. #define IN_OZONE 3
  402.  
  403. int _p_state;       /* current state     */
  404. unsigned _p_flag;  /* option flag     */
  405. char _p_curquote;  /* current quote char */
  406. int _p_tokpos;       /* current token pos  */
  407.  
  408. /* routine to find character in string ... used only by "parser" */
  409.  
  410. sindex(ch,string)
  411. char ch,*string;
  412.  
  413. {
  414.   char *cp;
  415.   for(cp=string;*cp;++cp)
  416.     if(ch==*cp)
  417.       return (int)(cp-string);    /* return postion of character */
  418.   return -1;            /* eol ... no match found */
  419. }
  420.  
  421. /* routine to store a character in a string ... used only by "parser" */
  422.  
  423. chstore(string,max,ch)
  424. char *string,ch;
  425. int max;
  426.  
  427. {
  428.   char c;
  429.   if(_p_tokpos>=0&&_p_tokpos<max-1)
  430.   {
  431.     if(_p_state==IN_QUOTE)
  432.       c=ch;
  433.     else
  434.       switch(_p_flag&3)
  435.       {
  436.     case 1:         /* convert to upper */
  437.       c=toupper(ch);
  438.       break;
  439.  
  440.     case 2:         /* convert to lower */
  441.       c=tolower(ch);
  442.       break;
  443.  
  444.     default:        /* use as is */
  445.       c=ch;
  446.       break;
  447.       }
  448.     string[_p_tokpos++]=c;
  449.   }
  450.   return;
  451. }
  452.  
  453. /* here it is! */
  454.  
  455. parser(inflag,token,tokmax,line,white,brkchar,quote,eschar,brkused,next,quoted)
  456. unsigned inflag;
  457. char *token,*line,*white,*brkchar,*quote,*brkused,*quoted,eschar;
  458. int tokmax,*next;
  459.  
  460. {
  461.   int qp;
  462.   char c,nc;
  463.  
  464.   *brkused=0;        /* initialize to null */
  465.   *quoted=0;        /* assume not quoted  */
  466.  
  467.   if(!line[*next])    /* if we're at end of line, indicate such */
  468.     return 1;
  469.  
  470.   _p_state=IN_WHITE;       /* initialize state */
  471.   _p_curquote=0;       /* initialize previous quote char */
  472.   _p_flag=inflag;       /* set option flag */
  473.  
  474.   for(_p_tokpos=0;c=line[*next];++(*next))    /* main loop */
  475.   {
  476.     if((qp=sindex(c,brkchar))>=0)  /* break */
  477.     {
  478.       switch(_p_state)
  479.       {
  480.     case IN_WHITE:        /* these are the same here ...    */
  481.     case IN_TOKEN:        /* ... just get out        */
  482.     case IN_OZONE:        /* ditto            */
  483.       ++(*next);
  484.       *brkused=brkchar[qp];
  485.       goto byebye;
  486.  
  487.     case IN_QUOTE:         /* just keep going */
  488.       chstore(token,tokmax,c);
  489.       break;
  490.       }
  491.     }
  492.     else if((qp=sindex(c,quote))>=0)  /* quote */
  493.     {
  494.       switch(_p_state)
  495.       {
  496.     case IN_WHITE:     /* these are identical, */
  497.       _p_state=IN_QUOTE;        /* change states   */
  498.       _p_curquote=quote[qp];     /* save quote char */
  499.       *quoted=1;    /* set to true as long as something is in quotes */
  500.       break;
  501.  
  502.     case IN_QUOTE:
  503.       if(quote[qp]==_p_curquote)    /* same as the beginning quote? */
  504.       {
  505.         _p_state=IN_OZONE;
  506.         _p_curquote=0;
  507.       }
  508.       else
  509.         chstore(token,tokmax,c);    /* treat as regular char */
  510.       break;
  511.  
  512.     case IN_TOKEN:
  513.     case IN_OZONE:
  514.       *brkused=c;            /* uses quote as break char */
  515.       goto byebye;
  516.       }
  517.     }
  518.     else if((qp=sindex(c,white))>=0)       /* white */
  519.     {
  520.       switch(_p_state)
  521.       {
  522.     case IN_WHITE:
  523.     case IN_OZONE:
  524.       break;        /* keep going */
  525.  
  526.     case IN_TOKEN:
  527.       _p_state=IN_OZONE;
  528.       break;
  529.  
  530.     case IN_QUOTE:
  531.       chstore(token,tokmax,c);     /* it's valid here */
  532.       break;
  533.       }
  534.     }
  535.     else if(c==eschar)            /* escape */
  536.     {
  537.       nc=line[(*next)+1];
  538.       if(nc==0)         /* end of line */
  539.       {
  540.     *brkused=0;
  541.     chstore(token,tokmax,c);
  542.     ++(*next);
  543.     goto byebye;
  544.       }
  545.       switch(_p_state)
  546.       {
  547.     case IN_WHITE:
  548.       --(*next);
  549.       _p_state=IN_TOKEN;
  550.       break;
  551.  
  552.     case IN_TOKEN:
  553.     case IN_QUOTE:
  554.       ++(*next);
  555.       chstore(token,tokmax,nc);
  556.       break;
  557.  
  558.     case IN_OZONE:
  559.       goto byebye;
  560.       }
  561.     }
  562.     else    /* anything else is just a real character */
  563.     {
  564.       switch(_p_state)
  565.       {
  566.     case IN_WHITE:
  567.       _p_state=IN_TOKEN;        /* switch states */
  568.  
  569.     case IN_TOKEN:         /* these 2 are     */
  570.     case IN_QUOTE:         /*  identical here */
  571.       chstore(token,tokmax,c);
  572.       break;
  573.  
  574.     case IN_OZONE:
  575.       goto byebye;
  576.       }
  577.     }
  578.   }        /* end of main loop */
  579.  
  580. byebye:
  581.   token[_p_tokpos]=0;    /* make sure token ends with EOS */
  582.  
  583.   return 0;
  584.  
  585. }
  586.  
  587.