Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #1156

Re: parser tokens

Show all headers | View raw

Bill Cunningham wrote:

>     I know in writing a parser there are tokens involved. Would strtok be
> used? I am wanting to do this in C also.

The strtok() function isn't suited for this purpose.  In fact, I suspect 
that the strtok() function doesn't have any useful purpose at all.  Let me 
explain.

To start off, a token is not a sub-string.  A token is, instead, a symbol 
which is used to represent a set which is comprised of specific sequences of 
characters.  For example, the token for a non-negative integer may be 
defined by the set (0 | [1-9][0-9]*), which means that the strings "123", 
"0", "12312312314145236347546845" represent the same token.

With this in mind, the strtok() function only returns a set of sub-strings 
from a base string, according to a given set of delimiter bytes.  This means 
that, in this context, the function actually doesn't extract tokens, which 
happens to be the whole point of performing a lexical analysis.  As a 
consequence, every sub-string which is returned by strtok() still needs to 
be analyzed in order to be able to do anything at all with the data.

If this wasn't enough, there is a long list of problems and inconveniences 
caused by strtok().  For example, the delimiter bytes required by strtok() 
are also tokens, and yet they are ignored. So, in the end the strtok() 
function only ends up needlesslly complicating things instead of helping.

A better solution is to write a routine that actually extracts tokens from 
any given string.  This type of routine, which tends to be referred to as a 
lexer or scanner, analyzes each given string character by character so that 
it identifies any character sequence as a specific token.  

Depending on the language definition, this may take some work.  Due to this, 
some tools have already been developed to help programmers with this task, 
such as flex[1] and re2c[2].  Nevertheless, if a language is simple enough 
then a lexer is also simple to develop.  For an example, check the lexer 
routine in the following example code:

http://en.wikipedia.org/wiki/LL_parser#Parser_implementation_in_C.2B.2B

So, in short, you are better off forgetting about strtok() and instead 
develop your own lexer routine.


Hope this helps,
Rui Maciel

[1] http://flex.sourceforge.net/
[2] http://re2c.org/

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

parser tokens "Bill Cunningham" <nospam@nspam.invalid> - 2011-12-29 22:46 -0500
  Re: parser tokens "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2011-12-30 10:50 +0100
    Re: parser tokens Rui Maciel <rui.maciel@gmail.com> - 2011-12-30 14:54 +0000
      Re: parser tokens "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2011-12-30 16:26 +0100
        Re: parser tokens Rui Maciel <rui.maciel@gmail.com> - 2011-12-30 16:09 +0000
          Re: parser tokens "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2011-12-30 18:22 +0100
            Re: parser tokens Rui Maciel <rui.maciel@gmail.com> - 2011-12-30 19:33 +0000
              Re: parser tokens "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2011-12-30 23:08 +0100
  Re: parser tokens "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2011-12-30 12:09 +0000
    Re: parser tokens Rui Maciel <rui.maciel@gmail.com> - 2011-12-30 14:43 +0000
      Re: parser tokens "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2011-12-31 08:48 +0000
  Re: parser tokens Rui Maciel <rui.maciel@gmail.com> - 2011-12-30 14:23 +0000
  Re: parser tokens Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-30 23:41 +0000
    Re: parser tokens "Bill Cunningham" <nospam@nspam.invalid> - 2011-12-31 18:26 -0500
      Re: parser tokens Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-01 01:51 +0000
        Re: parser tokens "Bill Cunningham" <nospam@nspam.invalid> - 2012-01-01 12:17 -0500
          Re: parser tokens Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-01 22:17 +0000
            Re: parser tokens "BartC" <bc@freeuk.com> - 2012-01-01 22:54 +0000

csiph-web