4
\$\begingroup\$

I don't know whether if this is the right place to ask this.

I am semi-beginner in C. I always wanted to build my own Programming Language. Here I have built a lexical analyser completely myself. The lexer breaks the source code in tokens consisting of strings, characters, identifiers, constants and special symbols. It ignores single and multi-line comments too. And it can lexically analyse it's own code.

lexer.c

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

#define SYMBOL(term) (term>=123&&term<=126)||(term>=33&&term<=47)||(term>=58&&term<=64)||(term>=91&&term<=96)
#define CAPALPHA(term) (term>='A'&&term<='Z')
#define LOWALPHA(term) (term>='a'&&term<='z')
#define ALPHA(term) ((CAPALPHA(term))||(LOWALPHA(term)))
#define WHITESPACE(term) ((term>=0&&term<=32)||term==127||term=='\n')
#define NUMBER(term) (term>='0'&&term<='9')
#define HEXNUMBER(term) ((term>='A'&&term<='f')||(term>='A'||term<='f'))

#define KEYWORD_COUNT 0

enum type {identifier,string,spsymbol,keyword,character,number,hexnumber};
char type2[25][25]={"identifier\0","string\0","symbol\0","keyword\0","character\0","number\0","hexnumber\0"};

enum keywords {regx,regy};
char keywords2[25][25]={"regx\0","regy\0"};

struct Tokens{ //Tokens structure
    char *t; //actual token
    int tlen; //token length
    int ttype; //token type
    int lineno; //token line no
    int keyword;
};

struct Tokens *token[100000];
int main(){
    char *input=malloc(100000*sizeof(char));
    FILE *fp = fopen("file", "r");
    FILE *of = fopen("lexout","w");
    char symbol;
    if(fp != NULL){
        int j=0;
        while(1)
        {   symbol = fgetc(fp);
            //printf("%c",symbol);
            if (symbol != EOF)
                input[j++]=symbol;
            else {
                input[j++]=symbol;
                break;
            }
        }
        fclose(fp);
    }

    int c=-1;   //file current character
    int current_token=0; //current_token counter
    int line=1; //current line number

    int halt=0;
    while(1){
        if(halt) break;
        token[current_token]=(struct Tokens*)malloc(sizeof(struct Tokens)); //allocate memory for token structure
        token[current_token]->t=(char*)malloc(sizeof(char)*30); //allocate memory for token size

        int tokenTypeSet=0;
        int in=0;   //structure token counter

        while(1){
            c++;
            if(input[c]=='\n') line++;
            /*detect end of file*/
            if(input[c]=='%'&&input[c+1]=='E'&&input[c+2]=='O'&&input[c+3]=='F'&&input[c+4]=='%'){
                halt=1;
                break;
            }
            /*identify singleline comments*/
            if(input[c]=='/'&&input[c+1]=='/'){
                while(input[c+1]!='\n'){
                    c++;
                }
                continue;
            }
            /*identify multiline comments*/
            if(input[c]=='/'&&input[c+1]=='*'){
                c++;
                c++;
                while(input[c]!='*'&&input[c+1]!='/'){
                    if(input[c]=='\n'){
                        line++;
                    }
                    c++;
                }
                c++;
                continue;
            }
            /*identify string*/
            if(input[c]=='"'){
                //identify token type
                if(!tokenTypeSet){
                    token[current_token]->ttype=string;
                    tokenTypeSet=1;
                }
                c++;
                while(1){
                    //newline
                    if(input[c]=='\n'){
                        c++;
                        line++;
                    }
                    //backslash escaped
                    if(input[c]=='\\'&&input[c+1]=='\\'){
                        token[current_token]->t[in++]=input[c];
                        c++;
                        token[current_token]->t[in++]=input[c];
                        c++;
                        continue;
                    }
                    //double-quote escaped
                    if(input[c]=='\\'&&input[c+1]=='"'){
                        token[current_token]->t[in++]=input[c];
                        c++;
                        token[current_token]->t[in++]=input[c];
                        c++;
                        continue;
                    }
                    //contiguous double-quotes
                    if(input[c]=='"'&&input[c+1]=='"'){
                        token[current_token]->t[in++]=input[c];
                        c++;
                        token[current_token]->t[in++]=input[c];
                        c++;
                        continue;
                    }
                    //terminate string
                    if(input[c]=='"'){
                        //c++;
                        break;
                    }
                    token[current_token]->t[in++]=input[c];
                    c++;
                }
                token[current_token]->t[in]='\0';
                break;
            }
            /*identify characters*/
            if(input[c]=='\''){
                //identify token type
                if(!tokenTypeSet){
                    token[current_token]->ttype=character;
                    tokenTypeSet=1;
                }
                c++;
                while(1){
                    //backslash escaped
                    if(input[c]=='\\'&&input[c+1]=='\\'){
                        token[current_token]->t[in++]=input[c];
                        c++;
                        token[current_token]->t[in++]=input[c];
                        c++;
                        continue;
                    }
                    //sigle-quote escaped
                    if(input[c]=='\\'&&input[c+1]=='\''){
                        token[current_token]->t[in++]=input[c];
                        c++;
                        token[current_token]->t[in++]=input[c];
                        c++;
                        continue;
                    }
                    //contiguous single-quotes
                    if(input[c]=='\''&&input[c+1]=='\''){
                        token[current_token]->t[in++]=input[c];
                        c++;
                        token[current_token]->t[in++]=input[c];
                        c++;
                        continue;
                    }
                    //terminate character
                    if(input[c]=='\''){
                        //c++;
                        break;
                    } 
                    token[current_token]->t[in++]=input[c];
                    c++;
                }
                token[current_token]->t[in]='\0';
                break;
            }
            /*mark hexnumbers*/
            if(!tokenTypeSet){
                if(input[c]=='0'&&(input[c+1]=='x'||input[c+1]=='X')){
                    token[current_token]->t[in++]=input[c];
                    c++;
                    token[current_token]->t[in++]=input[c];
                    c++;
                    token[current_token]->ttype=hexnumber;
                    tokenTypeSet=1;
                }
                //continue;
            }
            /*read hex numbers*/
            if(token[current_token]->ttype==hexnumber){
                if(HEXNUMBER(input[c])||NUMBER(input[c])){
                    token[current_token]->t[in++]=input[c];
                }
                if(WHITESPACE(input[c+1])){
                    token[current_token]->t[in]='\0';
                    //c++; //undo
                    break;
                }
                if(SYMBOL(input[c+1])){
                    token[current_token]->t[in]='\0';
                    break;
                }
                if(!(HEXNUMBER(input[c+1])||NUMBER(input[c+1]))){
                    token[current_token]->t[in]='\0';
                    break;
                }
                continue;
            }
            /*read an alphabet or an underscore*/
            if(ALPHA(input[c])||input[c]=='_'){
                //identify token type
                if(!tokenTypeSet){
                    token[current_token]->ttype=identifier;
                    tokenTypeSet=1;
                }
                token[current_token]->t[in++]=input[c];
                //detect end of token
                if(WHITESPACE(input[c+1])){
                    token[current_token]->t[in]='\0';
                    //c++; //undo
                    break;
                }
                if((SYMBOL(input[c+1]))&&(input[c+1]!='_')){
                    token[current_token]->t[in]='\0';
                    break;
                }
                continue;
            }
            /*read a symbol*/
            if(SYMBOL(input[c])){
                if(!tokenTypeSet){
                    token[current_token]->ttype=spsymbol;
                    tokenTypeSet=1;
                }
                token[current_token]->t[in++]=input[c];
                //detect end of token
                if(WHITESPACE(input[c+1])){
                    token[current_token]->t[in]='\0';
                    //c++; //undo
                    break;
                }
                if(SYMBOL(input[c+1])||ALPHA(input[c+1])||NUMBER(input[c+1])){
                    token[current_token]->t[in]='\0';
                    break;
                }
                continue;
            }
            /*read a number*/
            if(NUMBER(input[c])){
                //identify token type
                if(!tokenTypeSet){
                    token[current_token]->ttype=number;
                    tokenTypeSet=1;
                }
                token[current_token]->t[in++]=input[c];
                //detect end of token
                if(WHITESPACE(input[c+1])){
                    token[current_token]->t[in]='\0';
                    //c++; //undo
                    break;
                }
                if(!(NUMBER(input[c+1]))){
                    if(token[current_token]->ttype==identifier&&(ALPHA(input[c+1])||input[c+1]=='_')){
                        continue;
                    }
                    token[current_token]->t[in]='\0';
                    break;
                }
                /*if(SYMBOL(input[c+1])||ALPHA(input[c+1])){
                    token[current_token]->t[in]='\0';
                    break;
                }*/
                continue;
            }
        }
        token[current_token]->lineno=line;
        current_token++;
    }

    //DEBUGGER
    //printf("Total nos of tokens = %d\n\n",current_token-1);
    fprintf(of,"Total nos of tokens = %d\n\n",current_token-1);
    for(int i=0;i<current_token-1;i++){
        //printf("%s:%s\n",type2[token[i]->ttype],token[i]->t);
        if(token[i]->ttype==identifier){
            for(int j=0;j<KEYWORD_COUNT;j++){
                if(strcmp(token[i]->t,keywords2[j])){
                    token[i]->ttype=keyword;
                    break;
                }
            }
        }
        fprintf(of,"lnos:%d,%s:%s\n",token[i]->lineno,type2[token[i]->ttype],token[i]->t);
    }
    printf("%s","***********************\n");
    //END OF LEXING
    return 0;
}

To test the lexer you need to create a source file named simply "file". Inside "file" should be the source code followed by %EOF% string. For example, file:

#include<stdio.h>

int main(){
int a = 5;
int b = a;
return 0;
}

%EOF%

Compile the program:

gcc lexer.c -o lexer.out -Wall

Output:

Total nos of tokens = 26

lnos:1,symbol:#
lnos:1,identifier:include
lnos:1,symbol:<
lnos:1,identifier:stdio
lnos:1,symbol:.
lnos:1,identifier:h
lnos:1,symbol:>
lnos:3,identifier:int
lnos:3,identifier:main
lnos:3,symbol:(
lnos:3,symbol:)
lnos:3,symbol:{
lnos:4,identifier:int
lnos:4,identifier:a
lnos:4,symbol:=
lnos:4,number:5
lnos:4,symbol:;
lnos:5,identifier:int
lnos:5,identifier:b
lnos:5,symbol:=
lnos:5,identifier:a
lnos:5,symbol:;
lnos:6,identifier:return
lnos:6,number:0
lnos:6,symbol:;
lnos:7,symbol:}

Where lnos is the line number the token appears in. The Source code is well commented. Ask if anything is not clear.

Later I would use these tokens in Parsing phase.

All I am seeking is a little guidance.

I need to know

  1. whether this is an efficient way to write a lexer.
  2. Do you see any bad coding practice in the my code.
  3. And if the code could be improved.
\$\endgroup\$
5
\$\begingroup\$

Here are a number of things that may help you improve your program.

Don't use define for function-like macros

There is no advantage and considerable disadvantages to using function-like macros. They lack type-checking and tend to lead to bugs. For example, if we use this:

c = '0';
SYMBOL(++c);
printf("%c\n", c);

We would see that it would print "5" because unlike a real function, the macro increments the value every time it's mentioned in the macro.

Use more whitespace for readability

Lines like this:

if(input[c]=='%'&&input[c+1]=='E'&&input[c+2]=='O'&&input[c+3]=='F'&&input[c+4]=='%'){

are very hard to read because of the lack of whitespace. It's much easier to read for most people when written like this:

if (input[c] == '%' && input[c + 1] == 'E' && input[c + 2] == 'O'
    && input[c + 3] == 'F' && input[c + 4] == '%') {

Eliminate "magic numbers"

One of the macros in the code is this:

#define SYMBOL(term) (term>=123&&term<=126)||(term>=33&&term<=47)||(term>=58&&term<=64)||(term>=91&&term<=96)

However it's difficult to figure out what this means because of all the un-named numerical constants. Better would be to d as you have done for the LOWALPHA macro and use character values directly. Or even better, just use ispunct() as per the next suggestion.

Use standard functions and facilities

Several of the macros attempt to duplicate functions that already exist. Specifically isupper() and many related functions are in <ctype.h>.

Don't leak memory

This code calls malloc several places but never free. This means that the code is leaking memory. It would be much better to get into the habit of using free for each call to malloc and then assuring that you don't leak memory.

Check the return value of malloc

If the program runs out of memory, a call to malloc can fail. The only indication for this is that the call will return a NULL pointer. You should check for this and avoid dereferencing a NULL pointer (which typically causes a program crash). If the program can't proceed without the memory, free any allocated memory and quit the program gracefully.

Decompose your program into functions

All of the logic here is in main in one rather long and dense chunk of code. It would be better to decompose this into separate functions.

Use bool where appropriate

The halt flag is being used as a boolean variable. If you #include <stdbool.h>, you can use a bool type to better signal how this is being used.

Simplify your code

The code currently contains this:

if (fp != NULL) {
    int j = 0;
    while (1) {
        symbol = fgetc(fp);
        //printf("%c",symbol);
        if (symbol != EOF)
            input[j++] = symbol;
        else {
            input[j++] = symbol;
            break;
        }
    }
    fclose(fp);
}

That's much more complex and fragile than it needs to be. It's fragile because there's nothing to prevent it from running beyond the allocated input buffer. It's also more complex than it needs to be with multiple while, if and else. It could be written instead like this:

if (fp == NULL) {
    puts("Cannot open input file");
    exit(1);
}
fgets(input, BUFFLEN, fp);
fclose(fp);

Note also that I'm using BUFFLEN instead of a "magic number" as mentioned above. Similarly, this code is more convoluted than it needs to be:

int halt = 0;
while (1) {
    if (halt)
        break;
    // more code
}

Write it like this instead:

bool halt = false;
while (!halt) {

Don't use uninitialised memory

The code allocates memory for a token, but tests the contents of some of its fields before actually initializing it. If you need it set to specific values, you should set it. If zeroes are sufficient, use calloc.

Don't clutter the code with useless things

In a number of cases we have code like this:

token[current_token]->t = (char *)malloc(sizeof(char) * 30);

However, there's no need to cast the value and sizeof(char) is defined to always be 1. So the code could be written like this instead:

token[current_token]->t = malloc(MAX_TOKEN_LEN);

Again, we're avoiding "magic numbers" as mentioned earlier.

Allow the user to specify input and output files

The file names are currently hardcoded which certainly greatly restricts the usefulness of the program. Consider using argc and argv to allow the user to specify file names on the command line. Also file is certainly a poor choice for a hardcoded file name since it doesn't tell one anything useful about what the file is expected to contain.

Use a state machine

You might find it better to use a state machine to do this parsing. See this answer for an example of how to do this.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.