C and C++

Moderators: None (Apply to moderate this forum)
Number of threads: 28629
Number of posts: 94611

This Forum Only
Post New Thread
Single Post View       Linear View       Threaded View      f

Report
Segmentation fault... Posted by IDK on 5 Jun 2006 at 11:30 AM
I have a segmentation fault again...
It's a little wierd...
This is some piece of code I'm working on:

#include <stdlib.h>
#include <stdio.h>

char look;             // { Lookahead Character }
FILE *ifile;           // input stream
FILE *ofile;           // output stream
char **KWlist;

//{--------------------------------------------------------------}
//{ Read New Character From Input Stream }

void GetChar(){
   look = fgetc(ifile);
}

//{--------------------------------------------------------------}
//{ Report Error}

void Abort(char* s){
   printf("\nError %s.", s);
   abort();
}

void Expected(char* s){
   printf("Error: %s Expected\n", s);
   abort();
}

//{--------------------------------------------------------------}
//{ Match a Specific Input Character }

void match(char x){
   if(look == x)
       GetChar();
   else{
       char* c = " \n";
       c[0] = x;
       Expected(c);
   }
}

//{--------------------------------------------------------------}
//{ Recognicion funcs }
char upcase(char c){
     if((c >= 'a') & (c <= 'z'))
         c += 'A' - 'a';
     return c;
}

int IsAlpha(char c){
   c = upcase(c);
   return ((c >= 'A') & (c <= 'Z'));
}

int IsDigit(char c){
    return ((c >= '0') & (c <= '9'));
}

int IsOp(char c){
    return (c == '+') | (c == '-') | (c == '*') | (c == '/') | (c == '<') | (c == '>') | (c == ':') | (c == '=') | (c == '!');
}

int IsAlNum(char c){
    return IsAlpha(c) | IsDigit(c);
}

int IsWhite(char c){
    return (c == ' ') | (c == '\t') | (c == '\n');
}


//{--------------------------------------------------------------}
//{ Get an Identifier }

void skipWhite(){
    while(IsWhite(look))
        GetChar();
}

void Fin(){
    if(look == '\n') GetChar();
    if(look == '\r') GetChar();
}

int Lookup(char ** list, char* s, int n){
    //++n;
    while(n--)
        if(list[n][0] == s[0])
            if(strcmp(list[n], s) == 0)
                return 1;
    return 0;
}


char* getName(){
    char *c, *p;
    if ((c=(char *) malloc(9))==NULL) return NULL;
    p = c;
    if(!IsAlpha(upcase(look))) Expected("Name");

    while(IsAlNum(look)){
        *p = upcase(look);
        ++p;
        GetChar();
    }
    *p = 0;
    skipWhite();
    return c;
}

char* getNum(){
    char *c, *p;
    if ((c=(char *) malloc(17))==NULL) return NULL;
    p = c;
    if(!IsDigit(look)) Expected("Integer");
    while(IsDigit(look)){
        *p = upcase(look);
        ++p;
        GetChar();
    }
    *p = 0;
    skipWhite();
    return c;
}

char* getOp(){
    char *c, *p;
    if ((c=(char *) malloc(4))==NULL) return NULL;
    p = c;
    if(!IsOp(look)) Expected("Integer");
    while(IsOp(look)){
        *p = upcase(look);
        ++p;
        GetChar();
    }
    *p = 0;
    skipWhite();
    return c;
}

char* scan(){ //remember to free!!
    skipWhite();
    char *c;
    while(look == '\n')
        Fin();

    if(IsAlpha(look))
        c = getName();
    else if(IsDigit(look))
        c = getNum();
    else if(IsOp(look))
        c = getOp();
    else {
        if ((c=(char *) malloc(2))==NULL) return NULL;
        *c = look;
        ++c;
        *c = 0;
        --c;
        GetChar();
    }
    return c;
}


//{--------------------------------------------------------------}
//{ Initialize }

void init(){
    ifile = stdin;  //fopen("test.q", "r");
    ofile = stdout;
    GetChar();

    if ((KWlist=(char **) malloc(6))==NULL) Abort("malloc error");
    KWlist[0] = "IF";
    KWlist[1] = "ELSE";
    KWlist[2] = "END";
    KWlist[3] = "ENDIF";
    KWlist[4] = "1234";
}


//{--------------------------------------------------------------}
//{ Main Program }

int main(){
    init();

    char* c;
    //scanf("%s",c); //this line works
    c = scan();      //but this doesn't
    printf("%s\n", c);
    printf("%d\n", Lookup(KWlist, c, 4)); //if I put a three here it works but not if it's a four and scan() is used.

    free(c);
    free(KWlist);

    return 0;
}


Read the comments in main to understand the prob...
The problem should be with scan() but I can't see why.

It only occures when the third parameter in Lookup is 4 and scan() is used. When the parameters is lower, or scanf() is used it works.

Happy coding wishes
the one and only
Niklas Ulvinge aka IDK
Report
Re: Segmentation fault... Posted by gustavosserra on 5 Jun 2006 at 11:54 AM
You are not using pointers correctly. You declared char*, so you must allocate memory to it before use. Or not declare it as a pointer at all.
char* c = new char; //c++
char* c = (char*)malloc(sizeof(char) * 1); //c
char c; //another option


Hope that helps,
Mortissus

: I have a segmentation fault again...
: It's a little wierd...
: This is some piece of code I'm working on:
:
:
: #include <stdlib.h>
: #include <stdio.h>
: 
: char look;             // { Lookahead Character }
: FILE *ifile;           // input stream
: FILE *ofile;           // output stream
: char **KWlist;
: 
: //{--------------------------------------------------------------}
: //{ Read New Character From Input Stream }
: 
: void GetChar(){
:    look = fgetc(ifile);
: }
: 
: //{--------------------------------------------------------------}
: //{ Report Error}
: 
: void Abort(char* s){
:    printf("\nError %s.", s);
:    abort();
: }
: 
: void Expected(char* s){
:    printf("Error: %s Expected\n", s);
:    abort();
: }
: 
: //{--------------------------------------------------------------}
: //{ Match a Specific Input Character }
: 
: void match(char x){
:    if(look == x)
:        GetChar();
:    else{
:        char* c = " \n";
:        c[0] = x;
:        Expected(c);
:    }
: }
: 
: //{--------------------------------------------------------------}
: //{ Recognicion funcs }
: char upcase(char c){
:      if((c >= 'a') & (c <= 'z'))
:          c += 'A' - 'a';
:      return c;
: }
: 
: int IsAlpha(char c){
:    c = upcase(c);
:    return ((c >= 'A') & (c <= 'Z'));
: }
: 
: int IsDigit(char c){
:     return ((c >= '0') & (c <= '9'));
: }
: 
: int IsOp(char c){
:     return (c == '+') | (c == '-') | (c == '*') | (c == '/') | (c == '<') | (c == '>') | (c == ':') | (c == '=') | (c == '!');
: }
: 
: int IsAlNum(char c){
:     return IsAlpha(c) | IsDigit(c);
: }
: 
: int IsWhite(char c){
:     return (c == ' ') | (c == '\t') | (c == '\n');
: }
: 
: 
: //{--------------------------------------------------------------}
: //{ Get an Identifier }
: 
: void skipWhite(){
:     while(IsWhite(look))
:         GetChar();
: }
: 
: void Fin(){
:     if(look == '\n') GetChar();
:     if(look == '\r') GetChar();
: }
: 
: int Lookup(char ** list, char* s, int n){
:     //++n;
:     while(n--)
:         if(list[n][0] == s[0])
:             if(strcmp(list[n], s) == 0)
:                 return 1;
:     return 0;
: }
: 
: 
: char* getName(){
:     char *c, *p;
:     if ((c=(char *) malloc(9))==NULL) return NULL;
:     p = c;
:     if(!IsAlpha(upcase(look))) Expected("Name");
: 
:     while(IsAlNum(look)){
:         *p = upcase(look);
:         ++p;
:         GetChar();
:     }
:     *p = 0;
:     skipWhite();
:     return c;
: }
: 
: char* getNum(){
:     char *c, *p;
:     if ((c=(char *) malloc(17))==NULL) return NULL;
:     p = c;
:     if(!IsDigit(look)) Expected("Integer");
:     while(IsDigit(look)){
:         *p = upcase(look);
:         ++p;
:         GetChar();
:     }
:     *p = 0;
:     skipWhite();
:     return c;
: }
: 
: char* getOp(){
:     char *c, *p;
:     if ((c=(char *) malloc(4))==NULL) return NULL;
:     p = c;
:     if(!IsOp(look)) Expected("Integer");
:     while(IsOp(look)){
:         *p = upcase(look);
:         ++p;
:         GetChar();
:     }
:     *p = 0;
:     skipWhite();
:     return c;
: }
: 
: char* scan(){ //remember to free!!
:     skipWhite();
:     char *c;
:     while(look == '\n')
:         Fin();
: 
:     if(IsAlpha(look))
:         c = getName();
:     else if(IsDigit(look))
:         c = getNum();
:     else if(IsOp(look))
:         c = getOp();
:     else {
:         if ((c=(char *) malloc(2))==NULL) return NULL;
:         *c = look;
:         ++c;
:         *c = 0;
:         --c;
:         GetChar();
:     }
:     return c;
: }
: 
: 
: //{--------------------------------------------------------------}
: //{ Initialize }
: 
: void init(){
:     ifile = stdin;  //fopen("test.q", "r");
:     ofile = stdout;
:     GetChar();
: 
:     if ((KWlist=(char **) malloc(6))==NULL) Abort("malloc error");
:     KWlist[0] = "IF";
:     KWlist[1] = "ELSE";
:     KWlist[2] = "END";
:     KWlist[3] = "ENDIF";
:     KWlist[4] = "1234";
: }
: 
: 
: //{--------------------------------------------------------------}
: //{ Main Program }
: 
: int main(){
:     init();
: 
:     char* c;
:     //scanf("%s",c); //this line works
:     c = scan();      //but this doesn't
:     printf("%s\n", c);
:     printf("%d\n", Lookup(KWlist, c, 4)); //if I put a three here it works but not if it's a four and scan() is used.
: 
:     free(c);
:     free(KWlist);
: 
:     return 0;
: }
: 

:
: Read the comments in main to understand the prob...
: The problem should be with scan() but I can't see why.
:
: It only occures when the third parameter in Lookup is 4 and scan() is used. When the parameters is lower, or scanf() is used it works.
:
: Happy coding wishes
: the one and only
: Niklas Ulvinge aka IDK
:

Report
Re: Segmentation fault... Posted by IDK on 5 Jun 2006 at 12:16 PM
: You are not using pointers correctly. You declared char*, so you must allocate memory to it before use. Or not declare it as a pointer at all.
:
: char* c = new char; //c++
: char* c = (char*)malloc(sizeof(char) * 1); //c
: char c; //another option
: 

:
: Hope that helps,
: Mortissus
:

This is C, it doesn't have new
Report
Re: Segmentation fault... Posted by IDK on 7 Jun 2006 at 6:39 AM
: : You are not using pointers correctly. You declared char*, so you must allocate memory to it before use. Or not declare it as a pointer at all.
: :
: : char* c = new char; //c++
: : char* c = (char*)malloc(sizeof(char) * 1); //c
: : char c; //another option
: : 

: :
: : Hope that helps,
: : Mortissus
: :
:
: This is C, it doesn't have new
:
Opps, I didn't read your post correctly. Disregard the previus post. Sorry.

But I am using the pointers correctly. If I'm not, wich func is wrong?
Report
Re: Segmentation fault... Posted by stephl on 7 Jun 2006 at 6:49 AM
: : : You are not using pointers correctly. You declared char*, so you must allocate memory to it before use. Or not declare it as a pointer at all.
: : :
: : : char* c = new char; //c++
: : : char* c = (char*)malloc(sizeof(char) * 1); //c
: : : char c; //another option
: : : 

: : :
: : : Hope that helps,
: : : Mortissus
: : :
: :
: : This is C, it doesn't have new
: :
: Opps, I didn't read your post correctly. Disregard the previus post. Sorry.
:
: But I am using the pointers correctly. If I'm not, wich func is wrong?
:
What is wrong in the way you use pointers is the fact that you do not always allocate memory before writing to the location pointed to by the pointer. For example, you need to allocate memory before calling scanf().
By the way, I tested the corrected code and it appears to work.

Steph
Report
Re: Segmentation fault Posted by IDK on 7 Jun 2006 at 7:29 AM

: What is wrong in the way you use pointers is the fact that you do not always allocate memory before writing to the location pointed to by the pointer. For example, you need to allocate memory before calling scanf().
: By the way, I tested the corrected code and it appears to work.
:
: Steph
:
What was wrong using scan()?

It worked with scanf(). If I should have allocated memmory for c and didn't it should give a segmentation fault, but it did not.

Report
Re: Segmentation fault Posted by stephl on 7 Jun 2006 at 7:38 AM
:
: : What is wrong in the way you use pointers is the fact that you do not always allocate memory before writing to the location pointed to by the pointer. For example, you need to allocate memory before calling scanf().
: : By the way, I tested the corrected code and it appears to work.
: :
: : Steph
: :
: What was wrong using scan()?
:
: It worked with scanf(). If I should have allocated memmory for c and didn't it should give a segmentation fault, but it did not.
:
:
Your call to scan() was OK since scan() calls functions which allocate memory (except the fact that there were other errors in these functions; they are corrected in the version I posted). What concerns scanf(), I am sure you need to allocate memory before calling scanf(). Check out the doc of this function. Such programming errors often lead to segmentation faults but not always. If you are "lucky", it will just overwrite other variables in your program. Segmentation faults occur when your program attempts to write to a block of memory which does not belong to your program.

Steph
Report
Re: Segmentation fault Posted by IDK on 7 Jun 2006 at 9:36 AM
: :
: : : What is wrong in the way you use pointers is the fact that you do not always allocate memory before writing to the location pointed to by the pointer. For example, you need to allocate memory before calling scanf().
: : : By the way, I tested the corrected code and it appears to work.
: : :
: : : Steph
: : :
: : What was wrong using scan()?
: :
: : It worked with scanf(). If I should have allocated memmory for c and didn't it should give a segmentation fault, but it did not.
: :
: :
: Your call to scan() was OK since scan() calls functions which allocate memory (except the fact that there were other errors in these functions; they are corrected in the version I posted). What concerns scanf(), I am sure you need to allocate memory before calling scanf(). Check out the doc of this function. Such programming errors often lead to segmentation faults but not always. If you are "lucky", it will just overwrite other variables in your program. Segmentation faults occur when your program attempts to write to a block of memory which does not belong to your program.
:
: Steph
:
To help this I think I always should init all pointers to null.
Your code was good, thanks.
I didn't like the intends and the funcs shouldn't return a pointer to char so I rewrote them:
void getOp(char *c){
    char *p;
    p = c;
    if(!IsOp(look)) Expected("Integer");
    while(IsOp(look)){
        *p = upcase(look);
        ++p;
        GetChar();
    }
    *p = 0;
    skipWhite();
}
//and similar with the others, getNum and getName

void scan(char* c){
    skipWhite();
    while(look == '\n')
        Fin();

    if(IsAlpha(look))
        getName(c);
    else if(IsDigit(look))
        getNum(c);
    else if(IsOp(look))
        getOp(c);
    else {
        *c = look;
        ++c;
        *c = 0;
        --c;
        GetChar();
    }
}




I'm still not sure what the problem was...


: (except the fact that there were other errors in these functions; they are corrected in the version I posted)

What errors?
Report
Re: Segmentation fault Posted by stephl on 9 Jun 2006 at 3:04 AM
: : :
: : : : What is wrong in the way you use pointers is the fact that you do not always allocate memory before writing to the location pointed to by the pointer. For example, you need to allocate memory before calling scanf().
: : : : By the way, I tested the corrected code and it appears to work.
: : : :
: : : : Steph
: : : :
: : : What was wrong using scan()?
: : :
: : : It worked with scanf(). If I should have allocated memmory for c and didn't it should give a segmentation fault, but it did not.
: : :
: : :
: : Your call to scan() was OK since scan() calls functions which allocate memory (except the fact that there were other errors in these functions; they are corrected in the version I posted). What concerns scanf(), I am sure you need to allocate memory before calling scanf(). Check out the doc of this function. Such programming errors often lead to segmentation faults but not always. If you are "lucky", it will just overwrite other variables in your program. Segmentation faults occur when your program attempts to write to a block of memory which does not belong to your program.
: :
: : Steph
: :
: To help this I think I always should init all pointers to null.
: Your code was good, thanks.
: I didn't like the intends and the funcs shouldn't return a pointer to char so I rewrote them:
:
: void getOp(char *c){
:     char *p;
:     p = c;
:     if(!IsOp(look)) Expected("Integer");
:     while(IsOp(look)){
:         *p = upcase(look);
:         ++p;
:         GetChar();
:     }
:     *p = 0;
:     skipWhite();
: }
: //and similar with the others, getNum and getName
: 
: void scan(char* c){
:     skipWhite();
:     while(look == '\n')
:         Fin();
: 
:     if(IsAlpha(look))
:         getName(c);
:     else if(IsDigit(look))
:         getNum(c);
:     else if(IsOp(look))
:         getOp(c);
:     else {
:         *c = look;
:         ++c;
:         *c = 0;
:         --c;
:         GetChar();
:     }
: }
: 
: 
: 

:
: I'm still not sure what the problem was...
:
:
: : (except the fact that there were other errors in these functions; they are corrected in the version I posted)
:
: What errors?
:
In fact, there were no errors in these functions (except in match() but it is not called). Sorry, I wrote this without reading your code again . However, there were a few useless statements:

In Lookup()
There is no need to compare just the first character of list[n] and s and if they are the same then compare the whole strings. Why don't you only compare the entire strings?

In getNum()
It is useless to call upcase() in the while loop since look is a digit here.

In getOp()
Same thing than in getNum().

But as you can see it is of less importance.
What concerns the cause of the problem, I am not sure at present but I'll think about it and tell you if I find something.

Steph
Report
Re: Segmentation fault Posted by IDK on 9 Jun 2006 at 3:19 AM
: In fact, there were no errors in these functions (except in match() but it is not called). Sorry, I wrote this without reading your code again . However, there were a few useless statements:
:
: In Lookup()
: There is no need to compare just the first character of list[n] and s and if they are the same then compare the whole strings. Why don't you only compare the entire strings?
:

It a lot faster. Even if strcmp is rather fast, it's still slow in compared to just comparing two bytes.


: In getNum()
: It is useless to call upcase() in the while loop since look is a digit here.
:
: In getOp()
: Same thing than in getNum().
:

Thanks for that, I didn't think of it...
I'll change it right away.


Report
Re: Segmentation fault Posted by stephl on 9 Jun 2006 at 4:15 AM
: : In fact, there were no errors in these functions (except in match() but it is not called). Sorry, I wrote this without reading your code again . However, there were a few useless statements:
: :
: : In Lookup()
: : There is no need to compare just the first character of list[n] and s and if they are the same then compare the whole strings. Why don't you only compare the entire strings?
: :
:
: It a lot faster. Even if strcmp is rather fast, it's still slow in compared to just comparing two bytes.
:

:
: : In getNum()
: : It is useless to call upcase() in the while loop since look is a digit here.
: :
: : In getOp()
: : Same thing than in getNum().
: :
:
: Thanks for that, I didn't think of it...
: I'll change it right away.
:

:
:
I am not sure that what you mentionned about the speed of a program comparing strings is true. How would you implement strcmp()? This way for example:
int strcmp(char *s1,char *s2)
{
while (*s1 && *s1==*s2)
{
++s1;
++s2;
}
if (*s1<*s2) return -1;
else if (*s1>*s2) return 1;
else return 0;
}


As you can see, not the whole strings are compared. The algorithm stops as soon as a difference is detected. That's why I do not think it would cost more time to call strcmp() directly (except the cost of a call to a function ).

Steph
Report
strcmp Posted by Lundin on 9 Jun 2006 at 4:38 AM
Just wanted to point out that you are still following
the strcmp spec if do like this:

int strcmp(const char *s1, const char *s2)
{
  while (*s1 && *s1==*s2)
  {
    ++s1;
    ++s2;
  }
  return *s1 - *s2;
}



Ok, hum... so I optimized it with one CPU tick or so...?
What's important to know is that the version of this function provided by the compiler is probably heavily optimized and most likely inlined as well.
Report
Re: Segmentation fault Posted by stephl on 9 Jun 2006 at 3:44 AM
: : :
: : : : What is wrong in the way you use pointers is the fact that you do not always allocate memory before writing to the location pointed to by the pointer. For example, you need to allocate memory before calling scanf().
: : : : By the way, I tested the corrected code and it appears to work.
: : : :
: : : : Steph
: : : :
: : : What was wrong using scan()?
: : :
: : : It worked with scanf(). If I should have allocated memmory for c and didn't it should give a segmentation fault, but it did not.
: : :
: : :
: : Your call to scan() was OK since scan() calls functions which allocate memory (except the fact that there were other errors in these functions; they are corrected in the version I posted). What concerns scanf(), I am sure you need to allocate memory before calling scanf(). Check out the doc of this function. Such programming errors often lead to segmentation faults but not always. If you are "lucky", it will just overwrite other variables in your program. Segmentation faults occur when your program attempts to write to a block of memory which does not belong to your program.
: :
: : Steph
: :
: To help this I think I always should init all pointers to null.
: Your code was good, thanks.
: I didn't like the intends and the funcs shouldn't return a pointer to char so I rewrote them:
:
: void getOp(char *c){
:     char *p;
:     p = c;
:     if(!IsOp(look)) Expected("Integer");
:     while(IsOp(look)){
:         *p = upcase(look);
:         ++p;
:         GetChar();
:     }
:     *p = 0;
:     skipWhite();
: }
: //and similar with the others, getNum and getName
: 
: void scan(char* c){
:     skipWhite();
:     while(look == '\n')
:         Fin();
: 
:     if(IsAlpha(look))
:         getName(c);
:     else if(IsDigit(look))
:         getNum(c);
:     else if(IsOp(look))
:         getOp(c);
:     else {
:         *c = look;
:         ++c;
:         *c = 0;
:         --c;
:         GetChar();
:     }
: }
: 
: 
: 

:
: I'm still not sure what the problem was...
:
:
: : (except the fact that there were other errors in these functions; they are corrected in the version I posted)
:
: What errors?
:
Well, I am not sure but I think I found something.
One of the causes may be the fact that a name should not be longer than 8 chars since getName() only allocates 9 bytes. Same thing with getNum() where numbers in the input stream should not be longer than 16 chars. Finally in getOp() an operator should not be longer than 3 chars. However, I think you have thought about that and allocated enough memory in each case.
Anyway, there is a problem in init(). Sorry, I had not noticed that before. You allocate only 6 bytes for KWlist whereas you should allocate 5*sizeof (char *) which often equals 5*4=20 bytes for 32-bit pointers or 5*2=10 bytes for 16-bit pointers. What I do not understand is the fact that the segmentation fault did not occur every time the program was running; this allocation error should have caused a runtime error in init() when you initialize the KWlist array. It leads to another problem in Lookup() when you compare s with the different elements of KWlist which is not in fact as long as you suppose since you did not allocate enough memory.
Something that is also strange to me is the fact that it worked when Lookup() received 3 or less as its second parameter. It could be explained this way. If your compiler is set to generate code for 16-bit pointers (possible with the old Turbo C), then you allocate in fact an array of 6/2=3 pointers to char instead of 5. So if Lookup() receives more than 3, when you compare the strings, you attempt to read memory which has not been allocated, and this may lead to segmentation faults. However, this explanation supposes that no error occurred in init(), which I think very strange.
I do not have any other explanation so far. Did you test your program many times? I mean 10 times or more when passing 3 or less to Lookup().
Well, segmentation faults do not always occur and a program may generate a fault at one time and run without any problem at another time. However, this problem appears really strange to me and I am sorry to say that I do not have any other explanation, since I did not find any other error . Perhaps somebody else on the messageboard could explain that phenomenon; I personnaly cannot.

Steph
Report
Re: Segmentation fault Posted by IDK on 9 Jun 2006 at 5:27 AM
: Well, I am not sure but I think I found something.
: One of the causes may be the fact that a name should not be longer than 8 chars since getName() only allocates 9 bytes. Same thing with getNum() where numbers in the input stream should not be longer than 16 chars. Finally in getOp() an operator should not be longer than 3 chars. However, I think you have thought about that and allocated enough memory in each case.
: Anyway, there is a problem in init(). Sorry, I had not noticed that before. You allocate only 6 bytes for KWlist whereas you should allocate 5*sizeof (char *) which often equals 5*4=20 bytes for 32-bit pointers or 5*2=10 bytes for 16-bit pointers. What I do not understand is the fact that the segmentation fault did not occur every time the program was running; this allocation error should have caused a runtime error in init() when you initialize the KWlist array. It leads to another problem in Lookup() when you compare s with the different elements of KWlist which is not in fact as long as you suppose since you did not allocate enough memory.
: Something that is also strange to me is the fact that it worked when Lookup() received 3 or less as its second parameter. It could be explained this way. If your compiler is set to generate code for 16-bit pointers (possible with the old Turbo C), then you allocate in fact an array of 6/2=3 pointers to char instead of 5. So if Lookup() receives more than 3, when you compare the strings, you attempt to read memory which has not been allocated, and this may lead to segmentation faults. However, this explanation supposes that no error occurred in init(), which I think very strange.
: I do not have any other explanation so far. Did you test your program many times? I mean 10 times or more when passing 3 or less to Lookup().
: Well, segmentation faults do not always occur and a program may generate a fault at one time and run without any problem at another time. However, this problem appears really strange to me and I am sorry to say that I do not have any other explanation, since I did not find any other error . Perhaps somebody else on the messageboard could explain that phenomenon; I personnaly cannot.
:
: Steph
:
It sounds good. I allocated 6 bytes, wich is enough for 3 pointers, and no more. Maybe the compiler or OS optimised away the assignment in init, or something. Thanks.
Report
Re: Segmentation fault Posted by stephl on 9 Jun 2006 at 5:29 AM
: : Well, I am not sure but I think I found something.
: : One of the causes may be the fact that a name should not be longer than 8 chars since getName() only allocates 9 bytes. Same thing with getNum() where numbers in the input stream should not be longer than 16 chars. Finally in getOp() an operator should not be longer than 3 chars. However, I think you have thought about that and allocated enough memory in each case.
: : Anyway, there is a problem in init(). Sorry, I had not noticed that before. You allocate only 6 bytes for KWlist whereas you should allocate 5*sizeof (char *) which often equals 5*4=20 bytes for 32-bit pointers or 5*2=10 bytes for 16-bit pointers. What I do not understand is the fact that the segmentation fault did not occur every time the program was running; this allocation error should have caused a runtime error in init() when you initialize the KWlist array. It leads to another problem in Lookup() when you compare s with the different elements of KWlist which is not in fact as long as you suppose since you did not allocate enough memory.
: : Something that is also strange to me is the fact that it worked when Lookup() received 3 or less as its second parameter. It could be explained this way. If your compiler is set to generate code for 16-bit pointers (possible with the old Turbo C), then you allocate in fact an array of 6/2=3 pointers to char instead of 5. So if Lookup() receives more than 3, when you compare the strings, you attempt to read memory which has not been allocated, and this may lead to segmentation faults. However, this explanation supposes that no error occurred in init(), which I think very strange.
: : I do not have any other explanation so far. Did you test your program many times? I mean 10 times or more when passing 3 or less to Lookup().
: : Well, segmentation faults do not always occur and a program may generate a fault at one time and run without any problem at another time. However, this problem appears really strange to me and I am sorry to say that I do not have any other explanation, since I did not find any other error . Perhaps somebody else on the messageboard could explain that phenomenon; I personnaly cannot.
: :
: : Steph
: :
: It sounds good. I allocated 6 bytes, wich is enough for 3 pointers, and no more. Maybe the compiler or OS optimised away the assignment in init, or something. Thanks.
:
May you tell me what compiler you use so that I know whether it is most likely to use 32- or 16-bit pointers?

Steph
Report
Re: Segmentation fault... Posted by stephl on 5 Jun 2006 at 12:14 PM
Some mistakes I have noticed.

#include <stdlib.h>
#include <stdio.h>

char look;             // { Lookahead Character }
FILE *ifile;           // input stream
FILE *ofile;           // output stream
char **KWlist;

//{--------------------------------------------------------------}
//{ Read New Character From Input Stream }

void GetChar(){
   look = fgetc(ifile);
}

//{--------------------------------------------------------------}
//{ Report Error}

void Abort(char* s){
   printf("\nError %s.", s);
   abort();
}

void Expected(char* s){
   printf("Error: %s Expected\n", s);
   abort();
}

//{--------------------------------------------------------------}
//{ Match a Specific Input Character }

void match(char x){
   if(look == x)
       GetChar();
   else{
       char* c = " \n";
/*
You should not declare c this way, because the string " \n" is then considered
as a string constant and should not be modified. Because you want to modify it
on the next line, declare c this way instead:

char c[3]=" \n";

This line initializes the array whose elements can be modified later.
*/
       c[0] = x;
       Expected(c);
   }
}

//{--------------------------------------------------------------}
//{ Recognicion funcs }
char upcase(char c){
     if((c >= 'a') & (c <= 'z'))
/*
Here it works but you should use && instead because what you want to perform
is a logical AND (boolean), not a bitwise AND
*/
         c += 'A' - 'a';
     return c;
}

int IsAlpha(char c){
   c = upcase(c);
   return ((c >= 'A') & (c <= 'Z'));
/*Same thing than above*/
}

int IsDigit(char c){
    return ((c >= '0') & (c <= '9'));
/*Same thing than above*/
}

int IsOp(char c){
    return (c == '+') | (c == '-') | (c == '*') | (c == '/') | (c == '<') | (c == '>') | (c == ':') | (c == '=') | (c == '!');
/*It works, but I think that it is preferable to use || to be clearer*/
}

int IsAlNum(char c){
    return IsAlpha(c) | IsDigit(c);
/* || */
}

int IsWhite(char c){
    return (c == ' ') | (c == '\t') | (c == '\n');
/* || */
}


//{--------------------------------------------------------------}
//{ Get an Identifier }

void skipWhite(){
    while(IsWhite(look))
        GetChar();
}

void Fin(){
    if(look == '\n') GetChar();
    if(look == '\r') GetChar();
}

int Lookup(char ** list, char* s, int n){
    //++n;
    while(n--)
        if(list[n][0] == s[0])
            if(strcmp(list[n], s) == 0)
                return 1;
    return 0;
}


char* getName(){
    char *c, *p;
    if ((c=(char *) malloc(9))==NULL) return NULL;
    p = c;
    if(!IsAlpha(upcase(look))) Expected("Name");

    while(IsAlNum(look)){
        *p = upcase(look);
        ++p;
        GetChar();
    }
    *p = 0;
    skipWhite();
    return c;
}

char* getNum(){
    char *c, *p;
    if ((c=(char *) malloc(17))==NULL) return NULL;
    p = c;
    if(!IsDigit(look)) Expected("Integer");
    while(IsDigit(look)){
        *p = upcase(look);
        ++p;
        GetChar();
    }
    *p = 0;
    skipWhite();
    return c;
}

char* getOp(){
    char *c, *p;
    if ((c=(char *) malloc(4))==NULL) return NULL;
    p = c;
    if(!IsOp(look)) Expected("Integer");
    while(IsOp(look)){
        *p = upcase(look);
        ++p;
        GetChar();
    }
    *p = 0;
    skipWhite();
    return c;
}

char* scan(){ //remember to free!!
    skipWhite();
    char *c;
    while(look == '\n')
        Fin();

    if(IsAlpha(look))
        c = getName();
    else if(IsDigit(look))
        c = getNum();
    else if(IsOp(look))
        c = getOp();
    else {
        if ((c=(char *) malloc(2))==NULL) return NULL;
        *c = look;
        ++c;
        *c = 0;
        --c;
        GetChar();
    }
    return c;
}


//{--------------------------------------------------------------}
//{ Initialize }

void init(){
    ifile = stdin;  //fopen("test.q", "r");
    ofile = stdout;
    GetChar();

    if ((KWlist=(char **) malloc(6))==NULL) Abort("malloc error");
/*
Here you only allocate space for 6 characters, which is not enough to store the 5
following strings
*/
    KWlist[0] = "IF";
    KWlist[1] = "ELSE";
    KWlist[2] = "END";
    KWlist[3] = "ENDIF";
    KWlist[4] = "1234";
}


//{--------------------------------------------------------------}
//{ Main Program }

int main(){
    init();

    char* c;
    //scanf("%s",c); //this line works
/*
It's amazing the line with scanf works. Normally, you should allocate space to store
the chars before calling scanf
*/
    c = scan();      //but this doesn't
    printf("%s\n", c);
    printf("%d\n", Lookup(KWlist, c, 4)); //if I put a three here it works but not if it's a four and scan() is used.

    free(c);
    free(KWlist);

    return 0;
}


Steph
Report
Re: Segmentation fault... Posted by IDK on 5 Jun 2006 at 12:33 PM
: //{--------------------------------------------------------------}
: //{ Initialize }
: 
: void init(){
:     ifile = stdin;  //fopen("test.q", "r");
:     ofile = stdout;
:     GetChar();
: 
:     if ((KWlist=(char **) malloc(6))==NULL) Abort("malloc error");
: /*
: Here you only allocate space for 6 characters, which is not enough to store the 5
: following strings
: */
:     KWlist[0] = "IF";
:     KWlist[1] = "ELSE";
:     KWlist[2] = "END";
:     KWlist[3] = "ENDIF";
:     KWlist[4] = "1234";
: }
: 

I thought I was declaring a an array of pointers to strings.
Doesn't "Hello" a 'return' a pointer to char.
Then I move that pointer to an array of 6 bytes.
The "Hello" is declared on the heap.
: 
: //{--------------------------------------------------------------}
: //{ Main Program }
: 
: int main(){
:     init();
: 
:     char* c;
:     //scanf("%s",c); //this line works
: /*
: It's amazing the line with scanf works. Normally, you should allocate space to store
: the chars before calling scanf
: */
:     c = scan();      //but this doesn't
:     printf("%s\n", c);
:     printf("%d\n", Lookup(KWlist, c, 4)); //if I put a three here it works but not if it's a four and scan() is used.
: 
:     free(c);
:     free(KWlist);
: 
:     return 0;
: }
: 

Report
Re: Segmentation fault... Posted by stephl on 5 Jun 2006 at 12:42 PM
:
: : //{--------------------------------------------------------------}
: : //{ Initialize }
: : 
: : void init(){
: :     ifile = stdin;  //fopen("test.q", "r");
: :     ofile = stdout;
: :     GetChar();
: : 
: :     if ((KWlist=(char **) malloc(6))==NULL) Abort("malloc error");
: : /*
: : Here you only allocate space for 6 characters, which is not enough to store the 5
: : following strings
: : */
: :     KWlist[0] = "IF";
: :     KWlist[1] = "ELSE";
: :     KWlist[2] = "END";
: :     KWlist[3] = "ENDIF";
: :     KWlist[4] = "1234";
: : }
: : 
: 

: I thought I was declaring a an array of pointers to strings.
: Doesn't "Hello" a 'return' a pointer to char.
: Then I move that pointer to an array of 6 bytes.
: The "Hello" is declared on the heap.
:
: : 
: : //{--------------------------------------------------------------}
: : //{ Main Program }
: : 
: : int main(){
: :     init();
: : 
: :     char* c;
: :     //scanf("%s",c); //this line works
: : /*
: : It's amazing the line with scanf works. Normally, you should allocate space to store
: : the chars before calling scanf
: : */
: :     c = scan();      //but this doesn't
: :     printf("%s\n", c);
: :     printf("%d\n", Lookup(KWlist, c, 4)); //if I put a three here it works but not if it's a four and scan() is used.
: : 
: :     free(c);
: :     free(KWlist);
: : 
: :     return 0;
: : }
: : 

:
Yes, sorry, you're right. But remember that if you assign these string constants to the pointers in KWlist, you should not modify these strings later.
I am working on your code now and I'll try to post something later if I have time.

Steph
Report
Re: Segmentation fault... Posted by IDK on 5 Jun 2006 at 1:04 PM
: :
: : : //{--------------------------------------------------------------}
: : : //{ Initialize }
: : : 
: : : void init(){
: : :     ifile = stdin;  //fopen("test.q", "r");
: : :     ofile = stdout;
: : :     GetChar();
: : : 
: : :     if ((KWlist=(char **) malloc(6))==NULL) Abort("malloc error");
: : : /*
: : : Here you only allocate space for 6 characters, which is not enough to store the 5
: : : following strings
: : : */
: : :     KWlist[0] = "IF";
: : :     KWlist[1] = "ELSE";
: : :     KWlist[2] = "END";
: : :     KWlist[3] = "ENDIF";
: : :     KWlist[4] = "1234";
: : : }
: : : 
: : 

: : I thought I was declaring a an array of pointers to strings.
: : Doesn't "Hello" a 'return' a pointer to char.
: : Then I move that pointer to an array of 6 bytes.
: : The "Hello" is declared on the heap.
: :
: : : 
: : : //{--------------------------------------------------------------}
: : : //{ Main Program }
: : : 
: : : int main(){
: : :     init();
: : : 
: : :     char* c;
: : :     //scanf("%s",c); //this line works
: : : /*
: : : It's amazing the line with scanf works. Normally, you should allocate space to store
: : : the chars before calling scanf
: : : */
: : :     c = scan();      //but this doesn't
: : :     printf("%s\n", c);
: : :     printf("%d\n", Lookup(KWlist, c, 4)); //if I put a three here it works but not if it's a four and scan() is used.
: : : 
: : :     free(c);
: : :     free(KWlist);
: : : 
: : :     return 0;
: : : }
: : : 

: :
: Yes, sorry, you're right. But remember that if you assign these string constants to the pointers in KWlist, you should not modify these strings later.
: I am working on your code now and I'll try to post something later if I have time.
:
: Steph
:
Why can't I modify them?
int i = 0;
i = 2;

Here i is also declared on the heap, and I can modify it too.
Report
Re: Segmentation fault... Posted by stephl on 5 Jun 2006 at 1:23 PM
: : :
: : : : //{--------------------------------------------------------------}
: : : : //{ Initialize }
: : : : 
: : : : void init(){
: : : :     ifile = stdin;  //fopen("test.q", "r");
: : : :     ofile = stdout;
: : : :     GetChar();
: : : : 
: : : :     if ((KWlist=(char **) malloc(6))==NULL) Abort("malloc error");
: : : : /*
: : : : Here you only allocate space for 6 characters, which is not enough to store the 5
: : : : following strings
: : : : */
: : : :     KWlist[0] = "IF";
: : : :     KWlist[1] = "ELSE";
: : : :     KWlist[2] = "END";
: : : :     KWlist[3] = "ENDIF";
: : : :     KWlist[4] = "1234";
: : : : }
: : : : 
: : : 

: : : I thought I was declaring a an array of pointers to strings.
: : : Doesn't "Hello" a 'return' a pointer to char.
: : : Then I move that pointer to an array of 6 bytes.
: : : The "Hello" is declared on the heap.
: : :
: : : : 
: : : : //{--------------------------------------------------------------}
: : : : //{ Main Program }
: : : : 
: : : : int main(){
: : : :     init();
: : : : 
: : : :     char* c;
: : : :     //scanf("%s",c); //this line works
: : : : /*
: : : : It's amazing the line with scanf works. Normally, you should allocate space to store
: : : : the chars before calling scanf
: : : : */
: : : :     c = scan();      //but this doesn't
: : : :     printf("%s\n", c);
: : : :     printf("%d\n", Lookup(KWlist, c, 4)); //if I put a three here it works but not if it's a four and scan() is used.
: : : : 
: : : :     free(c);
: : : :     free(KWlist);
: : : : 
: : : :     return 0;
: : : : }
: : : : 

: : :
: : Yes, sorry, you're right. But remember that if you assign these string constants to the pointers in KWlist, you should not modify these strings later.
: : I am working on your code now and I'll try to post something later if I have time.
: :
: : Steph
: :
: Why can't I modify them?
:
: int i = 0;
: i = 2;
: 

: Here i is also declared on the heap, and I can modify it too.
:
I'll give an example to make things clearer. There's a difference between these two pieces of code:
/*EXAMPLE 1*/
char *p="Hello";

/*EXAMPLE 2*/
char p[]="Hello";

/*EXAMPLE 3*/
char p[6]="Hello";


EX2 and EX3 are the same except the fact that in EX2 the compiler computes the size itself.
In EX1, what is allocated on the stack is one pointer to char; the string "Hello" is not stored on the stack but in a special segment of memory where constants are stored. This address in the constant memory segment is assigned to the variable p. But the memory block pointed to by p should not be modified because it belongs to the constant segment.

In EX2 or EX3, 6 bytes are allocated on the stack, one for each character in the string, and these bytes are assigned the corresponding chars in the string. Then p represents the address of this 6-byte-wide block of memory. Of course, these bytes can be freely modified.

I hope I am clear in my explanations.

Steph
Report
Re: Segmentation fault... Posted by IDK on 5 Jun 2006 at 1:42 PM
: I'll give an example to make things clearer. There's a difference between these two pieces of code:
:
: /*EXAMPLE 1*/
: char *p="Hello";
: 
: /*EXAMPLE 2*/
: char p[]="Hello";
: 
: /*EXAMPLE 3*/
: char p[6]="Hello";
: 

:
: EX2 and EX3 are the same except the fact that in EX2 the compiler computes the size itself.
: In EX1, what is allocated on the stack is one pointer to char; the string "Hello" is not stored on the stack but in a special segment of memory where constants are stored. This address in the constant memory segment is assigned to the variable p. But the memory block pointed to by p should not be modified because it belongs to the constant segment.
:
: In EX2 or EX3, 6 bytes are allocated on the stack, one for each character in the string, and these bytes are assigned the corresponding chars in the string. Then p represents the address of this 6-byte-wide block of memory. Of course, these bytes can be freely modified.
:
: I hope I am clear in my explanations.
:
: Steph
:
Thanks for clearing that up.
I don't want to change those bytes, I only whant to compare them in the Lookup func.

Is stack and heap the same thing? I'm confusing them...

...OK, now I've read a little, and here's a good description:

Constants are declared in the constant segment, wich is located 'in the code'.
Variables are declared on the stack, wich is located on the high end of the memmory in a stack way.
Malloc declares data on the heap, wich is located on the low end of the memmory in a data way.
Report
Re: Segmentation fault... Posted by stephl on 5 Jun 2006 at 1:57 PM
: : I'll give an example to make things clearer. There's a difference between these two pieces of code:
: :
: : /*EXAMPLE 1*/
: : char *p="Hello";
: : 
: : /*EXAMPLE 2*/
: : char p[]="Hello";
: : 
: : /*EXAMPLE 3*/
: : char p[6]="Hello";
: : 

: :
: : EX2 and EX3 are the same except the fact that in EX2 the compiler computes the size itself.
: : In EX1, what is allocated on the stack is one pointer to char; the string "Hello" is not stored on the stack but in a special segment of memory where constants are stored. This address in the constant memory segment is assigned to the variable p. But the memory block pointed to by p should not be modified because it belongs to the constant segment.
: :
: : In EX2 or EX3, 6 bytes are allocated on the stack, one for each character in the string, and these bytes are assigned the corresponding chars in the string. Then p represents the address of this 6-byte-wide block of memory. Of course, these bytes can be freely modified.
: :
: : I hope I am clear in my explanations.
: :
: : Steph
: :
: Thanks for clearing that up.
: I don't want to change those bytes, I only whant to compare them in the Lookup func.
:
: Is stack and heap the same thing? I'm confusing them...
:
: ...OK, now I've read a little, and here's a good description:
:
: Constants are declared in the constant segment, wich is located 'in the code'.
: Variables are declared on the stack, wich is located on the high end of the memmory in a stack way.
: Malloc declares data on the heap, wich is located on the low end of the memmory in a data way.
:

The stack is used for all the variables declared in the different functions and for parameters. The heap is used to allocate memory dynamically with malloc(), calloc()...
I've something that compiles, but it has to be tested now.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>


char look,*KWlist[5];
FILE *ifile,*ofile;


void GetChar(void)
{
look=fgetc(ifile);
}


void Expected(char *s)
{
printf("Error: %s Expected\n",s);
abort();
}


void match(char x)
{
char c[3]=" \n";

if (look==x) GetChar();
else
{
c[0]=x;
Expected(c);
}
}


char upcase(char c)
{
if (c>='a' && c<='z') c+='A'-'a';
return c;
}


int IsAlpha(char c)
{
c=upcase(c);
return c>='A' && c<='Z';
}


int IsDigit(char c)
{
return c>='0' && c<='9';
}


int IsOp(char c)
{
return c=='+' || c=='-' || c=='*' || c=='/' || c=='<' || c=='>' || c==':' ||
 c=='=' || c=='!';
}


int IsAlNum(char c)
{
return IsAlpha(c) || IsDigit(c);
}


int IsWhite(char c)
{
return c==' ' || c=='\t' || c=='\n';
}


void skipWhite(void)
{
while (IsWhite(look)) GetChar();
}


void Fin(void)
{
if (look=='\n') GetChar();
if (look=='\r') GetChar();
}


int Lookup(char **list,char *s,int n)
{
while (n--)
if (!strcmp(list[n],s)) return 1;
return 0;
}


char *getName(char *buf)
{
char *p;

p=buf;
if (!IsAlpha(look)) Expected("Name");
while (IsAlNum(look))
{
*p=upcase(look);
++p;
GetChar();
}
*p=0;
skipWhite();
return buf;
}


char *getNum(char *buf)
{
char *p;

p=buf;
if (!IsDigit(look)) Expected("Integer");
while (IsDigit(look))
{
*p++=look;
GetChar();
}
*p=0;
skipWhite();
return buf;
}


char *getOp(char *buf)
{
char *p;

p=buf;
if (!IsOp(look)) Expected("Operator");
while (IsOp(look))
{
*p++=look;
GetChar();
}
*p=0;
skipWhite();
return buf;
}


char *scan(char *buf)
{
skipWhite();
/*while (look=='\n') Fin();*/
if (IsAlpha(look)) return getName(buf);
else if (IsDigit(look)) return getNum(buf);
else if (IsOp(look)) return getOp(buf);
else
{
*buf=look;
buf[1]=0;
GetChar();
return buf;
}
}


void init(void)
{
ifile=fopen("test.txt","r");
ofile=stdout;
GetChar();
KWlist[0]="IF";
KWlist[1]="ELSE";
KWlist[2]="END";
KWlist[3]="ENDIF";
KWlist[4]="1234";
}


int main(void)
{
char c[512];

init();
scan(c);
fclose(ifile);
printf("%s\n",c);
printf("%d\n",Lookup(KWlist,c,5));
return 0;
}


Steph
Report
strcmp Posted by IDK on 9 Jun 2006 at 5:52 AM
Maximum thread limit...

That's how strcmp worked. I had no idea.

My way is compiled to just one instruction CMPS, wich is just 5 cycles on a Pentium.
The strcmp func could, as I can see it, only be optimised to a loop, (since there is two comparisons to be made).

I don't know how to say this but something like this:
The case for it to match is small, one in 26 or similar.
Since strcmp is slower than my way, and the probability for a match is low, the extra comparison for a match will not differ much.

My way: 25 times cmps and one strcmp
only strcmp: 26 times strcmp
Report
Re: strcmp Posted by Lundin on 9 Jun 2006 at 6:11 AM
: Maximum thread limit...
:
: That's how strcmp worked. I had no idea.
:
: My way is compiled to just one instruction CMPS, wich is just 5 cycles on a Pentium.
: The strcmp func could, as I can see it, only be optimised to a loop, (since there is two comparisons to be made).
:
: I don't know how to say this but something like this:
: The case for it to match is small, one in 26 or similar.
: Since strcmp is slower than my way, and the probability for a match is low, the extra comparison for a match will not differ much.
:
: My way: 25 times cmps and one strcmp
: only strcmp: 26 times strcmp
:


Well, you are using a PC... If you get a context switch in the middle of the whole thing you are probably gone for thousands of strcmp. Might be worth it to make the code more readable and sacrifice some performance.

Report
Re: strcmp Posted by IDK on 9 Jun 2006 at 6:36 AM
: : Maximum thread limit...
: :
: : That's how strcmp worked. I had no idea.
: :
: : My way is compiled to just one instruction CMPS, wich is just 5 cycles on a Pentium.
: : The strcmp func could, as I can see it, only be optimised to a loop, (since there is two comparisons to be made).
: :
: : I don't know how to say this but something like this:
: : The case for it to match is small, one in 26 or similar.
: : Since strcmp is slower than my way, and the probability for a match is low, the extra comparison for a match will not differ much.
: :
: : My way: 25 times cmps and one strcmp
: : only strcmp: 26 times strcmp
: :
:
:
: Well, you are using a PC...

Who doesn't?

: If you get a context switch in the middle of the whole thing you are probably gone for thousands of strcmp.

?? Maybe my english is bad but I can't figure out what it says.

: Might be worth it to make the code more readable and sacrifice some performance.
:

I don't agree that it makes it more readable to remove them.
Report
Re: strcmp Posted by stephl on 9 Jun 2006 at 6:25 AM
: Maximum thread limit...
:
: That's how strcmp worked. I had no idea.
:
: My way is compiled to just one instruction CMPS, wich is just 5 cycles on a Pentium.
: The strcmp func could, as I can see it, only be optimised to a loop, (since there is two comparisons to be made).
:
: I don't know how to say this but something like this:
: The case for it to match is small, one in 26 or similar.
: Since strcmp is slower than my way, and the probability for a match is low, the extra comparison for a match will not differ much.
:
: My way: 25 times cmps and one strcmp
: only strcmp: 26 times strcmp

I agree with the fact that a call to strcmp() plus the extra comparison require a little more time to execute than your single comparison. However, unless you compare thousands of strings, do you think you'll notice the difference between the two methods?

Steph

Report
Re: strcmp Posted by IDK on 9 Jun 2006 at 6:39 AM
: : Maximum thread limit...
: :
: : That's how strcmp worked. I had no idea.
: :
: : My way is compiled to just one instruction CMPS, wich is just 5 cycles on a Pentium.
: : The strcmp func could, as I can see it, only be optimised to a loop, (since there is two comparisons to be made).
: :
: : I don't know how to say this but something like this:
: : The case for it to match is small, one in 26 or similar.
: : Since strcmp is slower than my way, and the probability for a match is low, the extra comparison for a match will not differ much.
: :
: : My way: 25 times cmps and one strcmp
: : only strcmp: 26 times strcmp
:
: I agree with the fact that a call to strcmp() plus the extra comparison require a little more time to execute than your single comparison. However, unless you compare thousands of strings, do you think you'll notice the difference between the two methods?
:
: Steph
:
That's what I'm planning to do, compare thousands of strings.
I'm making a compiler.
Report
Re: strcmp Posted by stephl on 9 Jun 2006 at 6:49 AM
: : : Maximum thread limit...
: : :
: : : That's how strcmp worked. I had no idea.
: : :
: : : My way is compiled to just one instruction CMPS, wich is just 5 cycles on a Pentium.
: : : The strcmp func could, as I can see it, only be optimised to a loop, (since there is two comparisons to be made).
: : :
: : : I don't know how to say this but something like this:
: : : The case for it to match is small, one in 26 or similar.
: : : Since strcmp is slower than my way, and the probability for a match is low, the extra comparison for a match will not differ much.
: : :
: : : My way: 25 times cmps and one strcmp
: : : only strcmp: 26 times strcmp
: :
: : I agree with the fact that a call to strcmp() plus the extra comparison require a little more time to execute than your single comparison. However, unless you compare thousands of strings, do you think you'll notice the difference between the two methods?
: :
: : Steph
: :
: That's what I'm planning to do, compare thousands of strings.
: I'm making a compiler.
:
On what platform is your compiler intended to run? If it is for Windows, I am not sure it is worth trying to avoid one comparison or a call to strcmp(). Windows does so many things behind your back that I do not think you'll save much time with a single byte comparison instead of two. For example: context switching (ie the process that allows Windows to switch from one task to another) requires to save many parameters (eg processor registers). To my mind, all this takes much more time than the single comparison you're trying to avoid.

Steph
Report
Re: strcmp Posted by stephl on 9 Jun 2006 at 7:17 AM
: : : Maximum thread limit...
: : :
: : : That's how strcmp worked. I had no idea.
: : :
: : : My way is compiled to just one instruction CMPS, wich is just 5 cycles on a Pentium.
: : : The strcmp func could, as I can see it, only be optimised to a loop, (since there is two comparisons to be made).
: : :
: : : I don't know how to say this but something like this:
: : : The case for it to match is small, one in 26 or similar.
: : : Since strcmp is slower than my way, and the probability for a match is low, the extra comparison for a match will not differ much.
: : :
: : : My way: 25 times cmps and one strcmp
: : : only strcmp: 26 times strcmp
: :
: : I agree with the fact that a call to strcmp() plus the extra comparison require a little more time to execute than your single comparison. However, unless you compare thousands of strings, do you think you'll notice the difference between the two methods?
: :
: : Steph
: :
: That's what I'm planning to do, compare thousands of strings.
: I'm making a compiler.
:
I have performed some tests in order to show the differences between strcmp() and your method.
The program is:
#include <windows.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>


int main(int argc,char **argv)
{
char s[]="a";
char t[sizeof s];
DWORD ticks,ticks0;
int i,max,temp;

if (argc!=2) return 1;
max=atoi(argv[1]);
strcpy(t,"b");
ticks0=GetTickCount();
for (i=0;i<max;++i)
if (!strcmp(s,t)) temp=1;
ticks=GetTickCount()-ticks0;
printf("Time elapsed with strcmp() for %d tests: %u ms\n",max,ticks);
ticks0=GetTickCount();
for (i=0;i<max;++i)
if (*s==*t) temp=1;
ticks=GetTickCount()-ticks0;
printf("Time elapsed without strcmp() for %d tests: %u ms\n",max,ticks);
printf("%d\n",temp);
return 0;
}


The first character is different in each string, so strcmp() will only compare the first two characters and stops.
Here are the results with a Pentium4 at 2.8GHz:

Z:\Data\C\Test>test 1000000
Time elapsed with strcmp() for 1000000 tests: 16 ms
Time elapsed without strcmp() for 1000000 tests: 0 ms
0

Z:\Data\C\Test>test 10000000
Time elapsed with strcmp() for 10000000 tests: 78 ms
Time elapsed without strcmp() for 10000000 tests: 16 ms
0

Z:\Data\C\Test>test 1000000000
Time elapsed with strcmp() for 1000000000 tests: 7078 ms
Time elapsed without strcmp() for 1000000000 tests: 1454 ms
0


As you can see, even with one billion comparisons between the two strings, the difference is not so huge: 7s instead of 1.4s.

Steph
Report
Re: strcmp Posted by IDK on 9 Jun 2006 at 8:24 AM
: : : : Maximum thread limit...
: : : :
: : : : That's how strcmp worked. I had no idea.
: : : :
: : : : My way is compiled to just one instruction CMPS, wich is just 5 cycles on a Pentium.
: : : : The strcmp func could, as I can see it, only be optimised to a loop, (since there is two comparisons to be made).
: : : :
: : : : I don't know how to say this but something like this:
: : : : The case for it to match is small, one in 26 or similar.
: : : : Since strcmp is slower than my way, and the probability for a match is low, the extra comparison for a match will not differ much.
: : : :
: : : : My way: 25 times cmps and one strcmp
: : : : only strcmp: 26 times strcmp
: : :
: : : I agree with the fact that a call to strcmp() plus the extra comparison require a little more time to execute than your single comparison. However, unless you compare thousands of strings, do you think you'll notice the difference between the two methods?
: : :
: : : Steph
: : :
: : That's what I'm planning to do, compare thousands of strings.
: : I'm making a compiler.
: :
: I have performed some tests in order to show the differences between strcmp() and your method.
: The program is:
:
: #include <windows.h>
: #include <stdio.h>
: #include <string.h>
: #include <stdlib.h>
: 
: 
: int main(int argc,char **argv)
: {
: char s[]="a";
: char t[sizeof s];
: DWORD ticks,ticks0;
: int i,max,temp;
: 
: if (argc!=2) return 1;
: max=atoi(argv[1]);
: strcpy(t,"b");
: ticks0=GetTickCount();
: for (i=0;i<max;++i)
: if (!strcmp(s,t)) temp=1;
: ticks=GetTickCount()-ticks0;
: printf("Time elapsed with strcmp() for %d tests: %u ms\n",max,ticks);
: ticks0=GetTickCount();
: for (i=0;i<max;++i)
: if (*s==*t) temp=1;
: ticks=GetTickCount()-ticks0;
: printf("Time elapsed without strcmp() for %d tests: %u ms\n",max,ticks);
: printf("%d\n",temp);
: return 0;
: }
: 

:
: The first character is different in each string, so strcmp() will only compare the first two characters and stops.
: Here are the results with a Pentium4 at 2.8GHz:
:
:
: Z:\Data\C\Test>test 1000000
: Time elapsed with strcmp() for 1000000 tests: 16 ms
: Time elapsed without strcmp() for 1000000 tests: 0 ms
: 0
: 
: Z:\Data\C\Test>test 10000000
: Time elapsed with strcmp() for 10000000 tests: 78 ms
: Time elapsed without strcmp() for 10000000 tests: 16 ms
: 0
: 
: Z:\Data\C\Test>test 1000000000
: Time elapsed with strcmp() for 1000000000 tests: 7078 ms
: Time elapsed without strcmp() for 1000000000 tests: 1454 ms
: 0
: 

:
: As you can see, even with one billion comparisons between the two strings, the difference is not so huge: 7s instead of 1.4s.
:
: Steph
:
5 times faster! Thats enough for me.
Think if booting was five times faster.

Thanks for the comparison.

For the post:
I'm using linux now, but this could easily be ported to windows, or anything I think. I hope my code is ansi, and if it is, it could in fact be ported to all computers.
Report
Re: strcmp Posted by stephl on 9 Jun 2006 at 8:37 AM
: : : : : Maximum thread limit...
: : : : :
: : : : : That's how strcmp worked. I had no idea.
: : : : :
: : : : : My way is compiled to just one instruction CMPS, wich is just 5 cycles on a Pentium.
: : : : : The strcmp func could, as I can see it, only be optimised to a loop, (since there is two comparisons to be made).
: : : : :
: : : : : I don't know how to say this but something like this:
: : : : : The case for it to match is small, one in 26 or similar.
: : : : : Since strcmp is slower than my way, and the probability for a match is low, the extra comparison for a match will not differ much.
: : : : :
: : : : : My way: 25 times cmps and one strcmp
: : : : : only strcmp: 26 times strcmp
: : : :
: : : : I agree with the fact that a call to strcmp() plus the extra comparison require a little more time to execute than your single comparison. However, unless you compare thousands of strings, do you think you'll notice the difference between the two methods?
: : : :
: : : : Steph
: : : :
: : : That's what I'm planning to do, compare thousands of strings.
: : : I'm making a compiler.
: : :
: : I have performed some tests in order to show the differences between strcmp() and your method.
: : The program is:
: :
: : #include <windows.h>
: : #include <stdio.h>
: : #include <string.h>
: : #include <stdlib.h>
: : 
: : 
: : int main(int argc,char **argv)
: : {
: : char s[]="a";
: : char t[sizeof s];
: : DWORD ticks,ticks0;
: : int i,max,temp;
: : 
: : if (argc!=2) return 1;
: : max=atoi(argv[1]);
: : strcpy(t,"b");
: : ticks0=GetTickCount();
: : for (i=0;i<max;++i)
: : if (!strcmp(s,t)) temp=1;
: : ticks=GetTickCount()-ticks0;
: : printf("Time elapsed with strcmp() for %d tests: %u ms\n",max,ticks);
: : ticks0=GetTickCount();
: : for (i=0;i<max;++i)
: : if (*s==*t) temp=1;
: : ticks=GetTickCount()-ticks0;
: : printf("Time elapsed without strcmp() for %d tests: %u ms\n",max,ticks);
: : printf("%d\n",temp);
: : return 0;
: : }
: : 

: :
: : The first character is different in each string, so strcmp() will only compare the first two characters and stops.
: : Here are the results with a Pentium4 at 2.8GHz:
: :
: :
: : Z:\Data\C\Test>test 1000000
: : Time elapsed with strcmp() for 1000000 tests: 16 ms
: : Time elapsed without strcmp() for 1000000 tests: 0 ms
: : 0
: : 
: : Z:\Data\C\Test>test 10000000
: : Time elapsed with strcmp() for 10000000 tests: 78 ms
: : Time elapsed without strcmp() for 10000000 tests: 16 ms
: : 0
: : 
: : Z:\Data\C\Test>test 1000000000
: : Time elapsed with strcmp() for 1000000000 tests: 7078 ms
: : Time elapsed without strcmp() for 1000000000 tests: 1454 ms
: : 0
: : 

: :
: : As you can see, even with one billion comparisons between the two strings, the difference is not so huge: 7s instead of 1.4s.
: :
: : Steph
: :
: 5 times faster! Thats enough for me.
: Think if booting was five times faster.
:
: Thanks for the comparison.
:
: For the post:
: I'm using linux now, but this could easily be ported to windows, or anything I think. I hope my code is ansi, and if it is, it could in fact be ported to all computers.
:
Yes, 5 times faster. But the difference become noticeable only for a huge number of comparisons (it's not so common to have a source file containing 1 billion characters), which all fail. In fact, the gain will be less than 5. Furthermore, source files contain many blanks with which you won't call strcmp(). That's why I think it will be rare for your compiler to make so many string comparisons.
Are you writing a compiler in C? To compile C code? Anyway, I think there will be a part which depends on the OS. It cannot be 100% ANSI, can it?

Steph
Report
Re: strcmp Posted by IDK on 9 Jun 2006 at 9:12 AM
: : 5 times faster! Thats enough for me.
: : Think if booting was five times faster.
: :
: : Thanks for the comparison.
: :
: : For the post:
: : I'm using linux now, but this could easily be ported to windows, or anything I think. I hope my code is ansi, and if it is, it could in fact be ported to all computers.
: :
: Yes, 5 times faster. But the difference become noticeable only for a huge number of comparisons (it's not so common to have a source file containing 1 billion characters), which all fail. In fact, the gain will be less than 5. Furthermore, source files contain many blanks with which you won't call strcmp(). That's why I think it will be rare for your compiler to make so many string comparisons.
: Are you writing a compiler in C? To compile C code? Anyway, I think there will be a part which depends on the OS. It cannot be 100% ANSI, can it?
:
: Steph
:
This is only in the lookup func, and if there is 1000 variables then it will need to search those at least 1000*1000 = 1000000 times, maybe more. I've taken care of the whitespace (and tokinisation).

The compiler will be for a language of my own, opo. The design isn't finnished but I'm working on it.
Why can't I write a compiler in ansi? printf() and getChar() are the io funcs I use (and the appropriate file versions).
Report
Re: strcmp Posted by stephl on 10 Jun 2006 at 12:12 AM
: : : 5 times faster! Thats enough for me.
: : : Think if booting was five times faster.
: : :
: : : Thanks for the comparison.
: : :
: : : For the post:
: : : I'm using linux now, but this could easily be ported to windows, or anything I think. I hope my code is ansi, and if it is, it could in fact be ported to all computers.
: : :
: : Yes, 5 times faster. But the difference become noticeable only for a huge number of comparisons (it's not so common to have a source file containing 1 billion characters), which all fail. In fact, the gain will be less than 5. Furthermore, source files contain many blanks with which you won't call strcmp(). That's why I think it will be rare for your compiler to make so many string comparisons.
: : Are you writing a compiler in C? To compile C code? Anyway, I think there will be a part which depends on the OS. It cannot be 100% ANSI, can it?
: :
: : Steph
: :
: This is only in the lookup func, and if there is 1000 variables then it will need to search those at least 1000*1000 = 1000000 times, maybe more. I've taken care of the whitespace (and tokinisation).
:
: The compiler will be for a language of my own, opo. The design isn't finnished but I'm working on it.
: Why can't I write a compiler in ansi? printf() and getChar() are the io funcs I use (and the appropriate file versions).
:
What ANSI functions allow to create an EXE file? I really cannot see how you can create the EXE file that your compiler has to produce, using ANSI C.

Steph
Report
Re: strcmp Posted by IDK on 10 Jun 2006 at 3:23 AM
: : : : 5 times faster! Thats enough for me.
: : : : Think if booting was five times faster.
: : : :
: : : : Thanks for the comparison.
: : : :
: : : : For the post:
: : : : I'm using linux now, but this could easily be ported to windows, or anything I think. I hope my code is ansi, and if it is, it could in fact be ported to all computers.
: : : :
: : : Yes, 5 times faster. But the difference become noticeable only for a huge number of comparisons (it's not so common to have a source file containing 1 billion characters), which all fail. In fact, the gain will be less than 5. Furthermore, source files contain many blanks with which you won't call strcmp(). That's why I think it will be rare for your compiler to make so many string comparisons.
: : : Are you writing a compiler in C? To compile C code? Anyway, I think there will be a part which depends on the OS. It cannot be 100% ANSI, can it?
: : :
: : : Steph
: : :
: : This is only in the lookup func, and if there is 1000 variables then it will need to search those at least 1000*1000 = 1000000 times, maybe more. I've taken care of the whitespace (and tokinisation).
: :
: : The compiler will be for a language of my own, opo. The design isn't finnished but I'm working on it.
: : Why can't I write a compiler in ansi? printf() and getChar() are the io funcs I use (and the appropriate file versions).
: :
: What ANSI functions allow to create an EXE file? I really cannot see how you can create the EXE file that your compiler has to produce, using ANSI C.
:
: Steph
:
I'm producing the assembly output (wich all compilers do), that is then going to be assembled and linked to an exe, (or in my case, an elf file).

What would be hard to make an exe?
FILE* f = fopen("test.exe","o");
//output some binary data
fclose(f);

This is written for head, so it may not be correct.
Report
Pointers Posted by IDK on 9 Jun 2006 at 5:55 AM
Max thread limit again...

I use gcc
Report
Re: Pointers Posted by stephl on 9 Jun 2006 at 6:26 AM
: Max thread limit again...
:
: I use gcc
:
What do you mean when you write "Max thread limit"? I do not understand.

Steph
Report
Re: Pointers Posted by Lundin on 9 Jun 2006 at 6:29 AM
: : Max thread limit again...
: :
: : I use gcc
: :
: What do you mean when you write "Max thread limit"? I do not understand.
:
: Steph
:

The damned message board only allows 10 messages/threads in a row.
So it has nothing to do with kernel objects
Report
Re: Pointers Posted by stephl on 9 Jun 2006 at 6:35 AM
: : : Max thread limit again...
: : :
: : : I use gcc
: : :
: : What do you mean when you write "Max thread limit"? I do not understand.
: :
: : Steph
: :
:
: The damned message board only allows 10 messages/threads in a row.
: So it has nothing to do with kernel objects
:
OK! Thanks. I must really be tired to have not understood this .
Steph



 

Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic
© Copyright 2011 Programmersheaven.com - All rights reserved.
Reproduction in whole or in part, in any form or medium without express written permission is prohibited.
Violators of this policy may be subject to legal action. Please read our Terms Of Use and Privacy Statement for more information.
Operated by CommunityHeaven, a BootstrapLabs company.