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?
<center>can hold! \$\endgroup\$