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

Groups > comp.programming > #16319 > unrolled thread

Re: Scanning

Back to article view | Back to comp.programming

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Scanning Richard Heathfield <rjh@cpax.org.uk> - 2023-01-19 12:43 +0000
    Re: Scanning Richard Heathfield <rjh@cpax.org.uk> - 2023-01-19 13:56 +0000
    Re: Scanning V V V V V V V V V V V V V V V V V V <vvvvvvvvaaaaaaaaaaaaaaa@mail.ee> - 2023-01-27 01:46 -0800

#16319 — Re: Scanning

On 19/01/2023 12:10 pm, Stefan Ram wrote:
>    Some idle thoughts about scanning (lexical analysis, or
>    rather what comes before it) ...
> 
>    Let's take a very simple task: This scanner for text files
>    has nothing more to do than to return every character,
>    except to strip the spaces at the end of a line.
> 
>    It is a function "get_next_token" that on each call will
>    return the next character from a file to its client (caller),
>    except that spaces at the end of a line will skipped.
> 
>    So we read the line and strip the spaces. (One line in
>    Python.)
> 
>    But how do I know in advance if the line will fit into
>    memory?
> 
>    Perhaps because of such fears, traditional scanners¹ do not
>    read lines or, Heaven forbid, files, but only characters!
> 
>    They do not use random access with respect to the text to be
>    scanned, but sequential access, although things would be
>    easier with random access.
> 
>    So how would you do it with this style of programming (never
>    reading the whole line into memory)?
> 
>    "I read a character. If it's a space, I peek at the next
>    character, if that's a space, I start adding spaces to my
>    look-ahead buffer. If an EOL is encountered, the look-ahead
>    buffer is discarded. Otherwise, I have to start feeding my
>    client from the lookahead buffer until the lookahead buffer
>    is empty."
> 
>    If I am concerned that a line will not fit in memory, how do
>    I know that the sequence of spaces at the end of a line will
>    fit in memory (the look-ahead buffer)? The look-ahead buffer
>    could be replaced by a counter. If you are paranoid, you
>    would use a 64-bit counter and check it for overflow!
> 
>    Is it worth the effort with a look-ahead buffer and
>    sequential access? Should you just read a line, assuming
>    that a line will always fit into memory, and strip the
>    blanks the easy way, i.e., using random access? TIA for any
>    comments!
> 
>    1
> 
>    an example of a traditional scanner:
> 
>    It only ever calls "GetCh", never "GetLine". The code could
>    be easier to write by reading a whole line and then just
>    using functions that can look at that line using random
>    access to get the next symbol (maybe using regular
>    expressions). But a traditional scanner carefully only ever
>    reads a single character and manages a state.
> 
> PROCEDURE GetSym;
> 
> VAR     i          : CARDINAL;
> 
> BEGIN
>    WHILE  ch <= ' '  DO  GetCh  END;
>    IF  ch = '/'  THEN
>      SkipLine;
>      WHILE  ch <= ' '  DO  GetCh  END
>    END;
>    IF  (CAP (ch) <= 'Z') AND (CAP (ch) >= 'A')  THEN
>      i := 0;
>      sym := literal;
>      REPEAT
>        IF  i < IdLength  THEN
>          id [i] := ch;
>          INC (i)
>        END;
>        IF  ch > 'Z' THEN  sym := ident  END;
>        GetCh
>        ...

man 3 realloc

This was a perennial comp.lang.c topic back in the day.

My interface looked (and still looks) like this:

#define FGDATA_BUFSIZ BUFSIZ /* adjust to taste */
#define FGDATA_WRDSIZ sizeof("floccinaucinihilipilification")
#define FGDATA_REDUCE  1

int fgetline(char **line, size_t *size, size_t maxrecsize, FILE 
*fp, unsigned int flags, size_t *plen);

It's easier to use than it might look:

   char *data = NULL; /* where will the data go? NULL is fine */
   size_t size = 0;   /* how much space do we have right now? */
   size_t len = 0;    /* after call, holds line length */

   while(fgetline(&data, &size, (size_t)-1, stdin, 0, &len) == 0)
   {
     if(len > 0)

If you want fgetline.c and don't have 20 years of clc archives, 
just yell.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [next] | [standalone]

#16323

On 19/01/2023 1:38 pm, Stefan Ram wrote:
> Richard Heathfield <rjh@cpax.org.uk> writes:
>> This was a perennial comp.lang.c topic back in the day.
> 
>    But what about writing a scanner in languages with automatic
>    memory management where reading a whole line is very simple
>    and assuming an input language that limits line length to
>    some reasonable value, say, 1,000,000 characters?
> 
>    In such a language, would there still be reasons not to
>    read the whole line into memory, but to read it char-by-char
>    as traditional scanners do?

There are always reasons, and sometimes they conflict.

For example, memory management, which should be done by the 
language because it's too important to be left to the programmer, 
and which should be done by the programmer because it's too 
important to be left to the language.

What are your priorities? Run speed? Speed of development? Code 
re-use? Scalability? Programmer cost? Robustness? Security?

And what are your constraints?

I'm not asking for your answer to these questions. I'm just 
pointing out that the answer to your question will depend at 
least in part on the answers to mine.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#16352

You are a devil !




On Thursday, January 19, 2023 at 2:43:51 PM UTC+2, Richard Heathfield wrote:
> On 19/01/2023 12:10 pm, Stefan Ram wrote: 
> > Some idle thoughts about scanning (lexical analysis, or 
> > rather what comes before it) ... 
> > 
> > Let's take a very simple task: This scanner for text files 
> > has nothing more to do than to return every character, 
> > except to strip the spaces at the end of a line. 
> > 
> > It is a function "get_next_token" that on each call will 
> > return the next character from a file to its client (caller), 
> > except that spaces at the end of a line will skipped. 
> > 
> > So we read the line and strip the spaces. (One line in 
> > Python.) 
> > 
> > But how do I know in advance if the line will fit into 
> > memory? 
> > 
> > Perhaps because of such fears, traditional scanners¹ do not 
> > read lines or, Heaven forbid, files, but only characters! 
> > 
> > They do not use random access with respect to the text to be 
> > scanned, but sequential access, although things would be 
> > easier with random access. 
> > 
> > So how would you do it with this style of programming (never 
> > reading the whole line into memory)? 
> > 
> > "I read a character. If it's a space, I peek at the next 
> > character, if that's a space, I start adding spaces to my 
> > look-ahead buffer. If an EOL is encountered, the look-ahead 
> > buffer is discarded. Otherwise, I have to start feeding my 
> > client from the lookahead buffer until the lookahead buffer 
> > is empty." 
> > 
> > If I am concerned that a line will not fit in memory, how do 
> > I know that the sequence of spaces at the end of a line will 
> > fit in memory (the look-ahead buffer)? The look-ahead buffer 
> > could be replaced by a counter. If you are paranoid, you 
> > would use a 64-bit counter and check it for overflow! 
> > 
> > Is it worth the effort with a look-ahead buffer and 
> > sequential access? Should you just read a line, assuming 
> > that a line will always fit into memory, and strip the 
> > blanks the easy way, i.e., using random access? TIA for any 
> > comments! 
> > 
> > 1 
> > 
> > an example of a traditional scanner: 
> > 
> > It only ever calls "GetCh", never "GetLine". The code could 
> > be easier to write by reading a whole line and then just 
> > using functions that can look at that line using random 
> > access to get the next symbol (maybe using regular 
> > expressions). But a traditional scanner carefully only ever 
> > reads a single character and manages a state. 
> > 
> > PROCEDURE GetSym; 
> > 
> > VAR i : CARDINAL; 
> > 
> > BEGIN 
> > WHILE ch <= ' ' DO GetCh END; 
> > IF ch = '/' THEN 
> > SkipLine; 
> > WHILE ch <= ' ' DO GetCh END 
> > END; 
> > IF (CAP (ch) <= 'Z') AND (CAP (ch) >= 'A') THEN 
> > i := 0; 
> > sym := literal; 
> > REPEAT 
> > IF i < IdLength THEN 
> > id [i] := ch; 
> > INC (i) 
> > END; 
> > IF ch > 'Z' THEN sym := ident END; 
> > GetCh 
> > ... 
> 
> man 3 realloc 
> 
> This was a perennial comp.lang.c topic back in the day. 
> 
> My interface looked (and still looks) like this: 
> 
> #define FGDATA_BUFSIZ BUFSIZ /* adjust to taste */ 
> #define FGDATA_WRDSIZ sizeof("floccinaucinihilipilification") 
> #define FGDATA_REDUCE 1 
> 
> int fgetline(char **line, size_t *size, size_t maxrecsize, FILE 
> *fp, unsigned int flags, size_t *plen); 
> 
> It's easier to use than it might look: 
> 
> char *data = NULL; /* where will the data go? NULL is fine */ 
> size_t size = 0; /* how much space do we have right now? */ 
> size_t len = 0; /* after call, holds line length */ 
> 
> while(fgetline(&data, &size, (size_t)-1, stdin, 0, &len) == 0) 
> { 
> if(len > 0) 
> 
> If you want fgetline.c and don't have 20 years of clc archives, 
> just yell. 
> 
> -- 
> Richard Heathfield 
> Email: rjh at cpax dot org dot uk 
> "Usenet is a strange place" - dmr 29 July 1999 
> Sig line 4 vacant - apply within

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web