11
\$\begingroup\$

I want to write a library to parse any valid or invalid HTML-like things. First of all, I am trying to build a lexer. Here is what I did;

/* A html lexer */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

void *memcpy(void *, const void *, size_t);    

#define TOUPPER ('a' - 'A')

/* This lexer is UTF unaware on purpose, because characters that we
 are interested in are already in <128 range. Moreover, we are not
 removing or adding any bytes, only tagging relevant sections of data
 using pointers.

 Parser, on the other hand, might want to check for encoding.
 */

 /* We will use these token types */
typedef enum {
    DOCTYPE,      // <!DOCTYPE
    TAGOPEN,      // <
    TAGCLOSE,     // >
    TAGSELFCLOSE, // />
    CLOSETAGOPEN, // </
    SINGLEQUOTE,  // '
    DOUBLEQUOTE,  // "
    ESCAPE,       // \x
    COMMENTOPEN,  // <!--
    COMMENTCLOSE, // -->
    CDATAOPEN,    // <![CDATA[
    CDATACLOSE,   // ]]>
    STRING,       // anything else
    WHITESPACE,   // any combination of " ", "\r", "\n", "\t"
    EQUAL         // =
} token_t;

/* Lexer will produce these. */
typedef struct {
    /* begin is included but end is exluded. For example;
    Memory locations: 1 | 2 | 3 | 4 | 5 | 6 |
    Chars:          : t | o | k | e | n |

    Begin will be 1, end will be 6.

    CAUTION! This is not a null terminated string.
    */
    token_t type;
    const char *begin;
    const char *end;
} Token;

/* This is the data used by our lexer. */
typedef struct lexer {
    char *SOF;                          /* Start of file */
    char *END;                          /* End of file */
    char *SOT;                          /* Start of current token */
    char *pos;                          /* Current position of lexer */

    /* Lexer work as a state machine, this function denotes the current 
    state. */
    void (*state_func)(struct lexer *);


    /*  This function gets a pointer to current token.

        This is where lexer communicates with possible parsers. This
        way, multiple parsers can be built upon this lexer.

        Each time a new token is found, this function will be called.
    */
    void (*token_eater)(const Token *);

    /* Tokens that we emit are also kept here, so we don't need to malloc - free
    each token. Parsers can do that if they require. */
    Token token;
} Lexer;

typedef void (*state_func)(struct lexer *);
typedef void (*token_eater)(const Token *);

#define NULLSTATE (state_func)0
#define QUITLEX(LEXER) (LEXER)->state_func = NULLSTATE
#define LEXFUNC(NAME) void lex_##NAME(Lexer *)
#define DATAEND(LEX) (LEX)->pos >= (LEX)->END
#define CHECKEND(LEX) if(DATAEND(LEX))

/* Define possible states */
LEXFUNC(initial);
LEXFUNC(tagopen);
LEXFUNC(comment);
LEXFUNC(whitespace);

static __inline void lex_init(Lexer *lex,
                            char *SOF,
                            char *END,
                            token_eater eater,
                            state_func initial_state) {

    lex->SOF = SOF;
    lex->END = END;
    lex->SOT = SOF;
    lex->pos   = SOF;
    lex->state_func = initial_state;
    lex->token_eater = eater;
}
void token_emit(Lexer *lex, token_t type) {
    assert(lex->pos - lex->SOT);
    lex->token.type = type;
    lex->token.begin = lex->SOT;
    lex->token.end   = lex->pos;
    lex->token_eater(&lex->token);
    lex->SOT = lex->pos;
}

/* If there is something that can be emitted,
   emit it as a string */
static __inline void _flush(Lexer *lex) {
    if (lex->pos - lex->SOT) {
        token_emit(lex, STRING);
    }
}

void lex_initial(Lexer *lex) {
    /* This function pretty much handles most of the job.
    it increments the position until it reaches an interesting
    chracter, and either emits required token if it can, or it
    transfer control to other states.
    */
    char current = lex->pos[0];
    CHECKEND(lex) {
        _flush(lex);
        QUITLEX(lex);
        return;
    }

    switch (current) {
        case '<':
            _flush(lex);
            lex->state_func = lex_tagopen;
            break;
        case '/':
            if(lex->pos[1] == '>') {
                _flush(lex);
                lex->pos+=2;
                token_emit(lex, TAGSELFCLOSE);
            } else {
                lex->pos++;
            }
            break;
        case '>':
            _flush(lex);
            lex->pos++;
            token_emit(lex, TAGCLOSE);
            break;
        case '=':
            _flush(lex);
            lex->pos++;
            token_emit(lex, EQUAL);
            break;
        case '"':
            _flush(lex);
            lex->pos++;
            token_emit(lex, DOUBLEQUOTE);
            break;
        case '\'':
            _flush(lex);
            lex->pos++;
            token_emit(lex, SINGLEQUOTE);
            break;
        case '\\':
            _flush(lex);
            lex->pos+=2;
            token_emit(lex, ESCAPE);
            break;
        case '-':
            if(lex->pos[1] == '-' && lex->pos[2] == '>') {
                _flush(lex);
                lex->pos+=3;
                token_emit(lex, COMMENTCLOSE);
            } else {
                lex->pos++;
            }
            break;
        case ']':
            if(lex->pos[1] == ']' && lex->pos[2] == '>') {
                _flush(lex);
                lex->pos+=3;
                token_emit(lex, CDATACLOSE);
            } else {
                lex->pos++;
            }
            break;
        case ' ':
        case '\t':
        case '\r':
        case '\n':
            _flush(lex);
            lex->state_func = lex_whitespace;
            break;
        default:
            lex->pos++;
    }
}

void lex_whitespace(Lexer *lex) {
    char current = lex->pos[0];

    switch(current) {
        case ' ':
        case '\t':
        case '\r':
        case '\n':
            lex->pos++;
            break;
        default:
            token_emit(lex, WHITESPACE);
            lex->state_func = lex_initial;
    }
}

void lex_tagopen(Lexer *lex) {
    /* If we are here, there must be a < character at lex->pos */
    lex->pos++;
    CHECKEND(lex) {
        /* Tag open character at the end of file
        We might have incomplete file or whatever. We emit
        it, rest is parser's problem.
        */
        token_emit(lex, TAGOPEN);
        QUITLEX(lex);
        return;
    }

    switch (lex->pos[0]) {
    case '!':
        lex->state_func = lex_comment;;
        break;
    case '/':
        lex->pos++;
        token_emit(lex, CLOSETAGOPEN);
        lex->state_func = lex_initial;
        break;
    default:
        token_emit(lex, TAGOPEN);
        lex->state_func = lex_initial;
        break;
    }
}

void lex_comment(Lexer *lex) {
    /* We have <! right now. */

    // Did we get any of <!-- <!DOCTYPE <![CDATA
    char success = 0;

    lex->pos++;
    CHECKEND(lex) {
        /*We have <! at the end of the file, go back and emit 
        < as tag open and count ! as seperate string. */
        lex->pos--;
        token_emit(lex, TAGOPEN);
        lex->pos++;
        token_emit(lex, STRING);
        QUITLEX(lex);
        return;
    }    

    switch (lex->pos[0]) {
        const char *cdata, *doctype;
        char iscdata, isdoctype;

        int i;

        case '-':
            if (lex->pos[1] == '-') {
                lex->pos+=2;
                token_emit(lex, COMMENTOPEN);
                lex->state_func = lex_initial;
                success = 1;
            }
            break;
        case '[': /* empty */;
            cdata = "[CDATA[";
            iscdata = 1;
            for (i = 0; i < 7; i++) {
                if(!(cdata[i] == lex->pos[i])) iscdata = 0;
            }
            if (iscdata) {
                lex->pos+=7;
                token_emit(lex, CDATAOPEN);
                lex->state_func = lex_initial;
                success = 1;
            }
            break;
        case 'D':
        case 'd': /* empty */ ;
            doctype = "doctype";
            isdoctype = 1;
            for (i = 0; i < 7; i++) {
                if(!(lex->pos[i] == doctype[i] ||
                     lex->pos[i] == (doctype[i] - TOUPPER))) isdoctype = 0;
            }
            if (isdoctype) {
                lex->pos+=7;
                token_emit(lex, DOCTYPE);
                lex->state_func = lex_initial;
                success = 1;
            }
            break;  
    }

    /* we couldn't get <!--, <!DOCTYPE or <![CDATA[ */
    if (!success) {
        lex->pos--;
        token_emit(lex, TAGOPEN);
        lex->state_func = lex_initial;
    }
}

/* Normally, a parser will handle tokens, but for now 
    this function will print them.
*/
void token_print(const Token *t) {

    char *tokentype;
    int strlen = t->end - t->begin;
    char *mystring = (char *)malloc(strlen + 1);

    memcpy(mystring, t->begin, strlen);
    mystring[strlen] = '\0';

    switch(t->type) {
    case DOCTYPE:
        tokentype = "doctype";
        break;
    case TAGOPEN:
        tokentype = "tagopen";
        break;
    case TAGCLOSE:
        tokentype = "tagclose";
        break;
    case TAGSELFCLOSE:
        tokentype = "tagselfclose";
        break;
    case SINGLEQUOTE:
        tokentype = "singlequote";
        break;
    case DOUBLEQUOTE:
        tokentype = "double quote";
        break;
    case ESCAPE:
        tokentype = "escape";
        break;
    case COMMENTOPEN:
        tokentype = "comment open";
        break;
    case COMMENTCLOSE:
        tokentype = "comment close";
        break;
    case CDATAOPEN:
        tokentype = "cdata open";
        break;
    case CDATACLOSE:
        tokentype = "cdata close";
        break;
    case STRING:
        tokentype = "string";
        break;
    case WHITESPACE:
        tokentype = "whitespace";
        break;
    case EQUAL:
        tokentype = "equal";
        break;
    case CLOSETAGOPEN:
        tokentype = "closetagopen";
        break;
    default:
        /* This sholdn't happen */
        tokentype = "other";
        break;
    }
    printf("token type: %s, token value: {%s}\n", tokentype, mystring);
}

int main() {
    char data[] = "<a href=\"www.google.com\">google</a>\n<!-- This is a comment -->";
    struct lexer lex;
    lex_init(&lex, data, data + 62, token_print, lex_initial);

    while(lex.state_func) {
        lex.state_func(&lex);
    }
}

This is the lexer part, I will do the parser part later and plug it into Lexer using Lexer->token_eater

How does it look so far?

\$\endgroup\$
  • \$\begingroup\$ Beautiful! The <center> can hold! \$\endgroup\$ – Mathieu Guindon Feb 24 '15 at 19:36
  • \$\begingroup\$ Looks pretty nice! Hope you'll get good reviews! \$\endgroup\$ – Stop ongoing harm to Monica Feb 24 '15 at 19:37
3
\$\begingroup\$

I don't write C, but I can tell this looks pretty neat.

Just a few notes:

  • The STRING token would probably be more accurately named LITERAL
  • The token_print procedure is meant for output; as closetagopen would be more readable as CloseTagOpen, I'd probably prefer to see them output in PascalCase; then you could remove the inconsistent whitespaces in the output values, such as in comment open which would become CommentOpen.
  • The lexer, [mock-up] parser, and the main method should probably be in separate files.
  • The 62 in data + 62 in the main method is a magic number. Not clear what it stands for.
\$\endgroup\$
  • \$\begingroup\$ Ohh, 62 is the length of the data :) data + 62 is pointer to last chracter lexer should process. \$\endgroup\$ – yasar Mar 14 '15 at 11:10
2
\$\begingroup\$

I see some repeated code that can probably be extracted to a separate function:

        _flush(lex);
        lex->pos+= SOMETHING;
        token_emit(lex, SOMETHINGELSE);
        break;

so the function should take lex, pos, SOMETHING (the amount to add to pos), and the token identifier (SOMETHINGELSE).

\$\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.