G
Gene
If there is a realistic chance the language will expand in the future
to a branching syntax, then tokenizing now is probably a good idea.
But if the language is such that the parser will always know what to
expect based on what it's already read (essentially the grammar is
LR(0)), then a separate tokenizing step is overkill. It adds error
opportunities and slows things down.
What the OP did is fine, but I'll bet his tests didn't work the first
time. Character-by-character approaches like this are fiddly.
A middle ground is to develop a set of prefix matchers that can be
reused. I've tried many different APIs and idioms and settled on the
following over the years. With this approach the code of the parser
can look just like the spec. With a good inlining compiler, the
result will be as good or better than OP's code for performance.
typedef enum token_e {
OPEN_TOKEN,
CLOSE_TOKEN,
LOCK_TOKEN,
DOOR_TOKEN,
} TOKEN;
/*
* Return true iff the given token is a proper directive.
*/
int is_directive(TOKEN token)
{
return OPEN_TOKEN <= token && token <= LOCK_TOKEN;
}
/* Must be in alpha order, lower case */
KEYWORD_PAIR keywords[] = {
{ "close", CLOSE_TOKEN },
{ "door", DOOR_TOKEN }, // Could handle door specially....
{ "lock", LOCK_TOKEN },
{ "open", OPEN_TOKEN },
};
/*
* Return true iff the given integer is a proper door number.
*/
int door_number_ok(unsigned n)
{
return n <= 10;
}
/*
* Parse a string with the following format:
* - a directive token, case insensitive
* - one or more whitespaces (spaces, tabs, newlines...)
* - the word "door" (without quotes), case insensitive
* - an optional number of whitespaces, even zero
* - a door number in the range 0..10
* - no other characters after the number
* Return the directive as a token and the door number.
* Function return is error code or 0 for success.
*/
int parse(char *s, TOKEN *directive, unsigned *door_number)
{
int index;
// Probably overkill to demand no whitespace.
if (match_whitespace(s, &s))
return -1;
if (!match_keyword(s, &s,
keywords, TABLE_SIZE(keywords),
keyword_cmp_ignoring_case,
&index))
return -2; // Missing token.
*directive = (TOKEN)keywords[index].token;
if (!is_directive(*directive))
return -3; // Token not a directive.
if (!match_token(s, &s,
keywords, TABLE_SIZE(keywords),
keyword_cmp_ignoring_case,
DOOR_TOKEN))
return -4; // Door keyword missing or misspelled
if (!match_unsigned(s, &s, door_number))
return -5; // Door number missing
if (!door_number_ok(*door_number))
return -6; // Door number out of range
if (*s)
return -7; // Junk at end check.
return 0; // 0 is more conventional for success
}
.... and the reusable code looks essentially like this. I've de-
parameterized some of my actual code to shorten it.
/*
* Set *end one char past whitespace prefix of s.
* Return true iff any characters matched.
*/
int match_whitespace(char *s, char **end)
{
char *p = s;
while (isspace(*p))
++p;
*end = p;
return p > s;
}
/*
* Set *end one char past alpha prefix of s.
* Return true iff any characters matched.
*/
int match_alpha(char *s, char **end)
{
char *p = s;
while (isalpha(*p))
++p;
*end = p;
return p > s;
}
/*
* Skip whitespace and then scan as many decimal digits
* as possible. Convert to an unsigned value with no
* overflow check. Return true iff any digits were
* matched. Set *end one past the scanned chars.
* FIXME: Add overflow check.
*/
int match_unsigned(char *s, char **end, unsigned *val_rtn)
{
char *p;
unsigned val;
match_whitespace(s, &s);
for (val = 0, p = s; isdigit(*p); p++)
val = 10 * val + (*p - '0');
*end = p;
*val_rtn = val;
return p > s;
}
/*
* Convert a character to lower case.
*/
char lowercase(char c)
{
return ('A' <= c && c <= 'Z') ? c - 'A' + 'a' : c;
}
/*
* Key comparison function for keyword lookups.
*/
typedef int (*KEYWORD_CMP)(char *s, unsigned n, char *kw);
/*
* Case insensitive keyword comparision. This compares
* a prefix of s of up to n characters with kw.
*/
int keyword_cmp_ignoring_case(char *s, size_t n, char *kw)
{
while (n > 0 && *s && *kw && lowercase(*s) == *kw) {
--n; ++s; ++kw;
}
return (n == 0) ? -*kw : lowercase(*s) - *kw;
}
/*
* Keyword entries and tables. An empty key string in
* a table produces undefined results.
*/
typedef struct keyword_pair_s {
char *key;
int token;
} KEYWORD_PAIR, KEYWORD_TABLE[];
#define TABLE_SIZE(A) (sizeof A / sizeof A[0])
/*
* Match a maximal prefix of alphabetic characters of
* string s to keywords in a table. Binary search is
* used, so the keys must be sorted. The keyword table
* index is returned (not the token value).
* On success return true and set *end one past the keyword.
* If none found, set *end one past any whitespace and return 0
* with index unchanged.
*/
int match_keyword(char *s, char **end,
KEYWORD_TABLE tbl, unsigned tbl_size,
KEYWORD_CMP cmp,
int *index)
{
int diff, lo, hi, mid;
match_whitespace(s, &s);
if (match_alpha(s, end)) {
lo = 0;
hi = tbl_size - 1;
while (lo <= hi) {
mid = (lo + hi) / 2;
diff = cmp(s, *end - s, tbl[mid].key);
if (diff < 0)
hi = mid - 1;
else if (diff > 0)
lo = mid + 1;
else {
*index = mid;
return 1;
}
}
}
*end = s;
return 0;
}
/*
* Match a maximal prefix of string s to keywords in a table.
* If found, verify its token matches the given value.
* On success return true and set *end to character past
* scanned keyword. On any failure, set *end one past any
* leading whitespace.
*/
int match_token(char *s, char **end,
KEYWORD_TABLE tbl, unsigned tbl_size,
KEYWORD_CMP cmp,
int token)
{
int index;
match_whitespace(s, &s);
if (!match_keyword(s, end, tbl, tbl_size, cmp, &index) ||
tbl[index].token != token)
return 0;
return 1;
}