Menu Parser in C

Question

This is a simple program that parses a menu specification and creates a menu tree.

Why?
I want to create a menu application, where the user can select an entry in the menu, and either a submenu can pop up (where the user can select another entry) or a command is run.

But before writing this menu thing (which requires some coding using Xlib), I need to write a parser for the menu configuration file. And I'm not used to write parsers.

Suppose this is a menu configuration file:

_Apps {
    Draw Terminal                           -- exec drawterm
    Open _Terminal at $HOME [^T]            -- exec xterm
    Open Terminal Here [^S-T]               -- exec samedir
    Take _Screenshot                        -- exec scrot select
    _Run                                    -- exec runner
    File _Manager                           -- exec run fm
    _Firefox                                -- exec run www
    _Chrome                                 -- exec chrome
    C_hat                                   -- exec hexchat
    _Games {
        TES III _Morowind               -- exec openmw
        GNU _Backgammon [^S-B]          -- exec gnubg
        _Spider                         -- exec spider
        Super Tux _Kart                 -- exec supertuxkart
    }
}

_Window {
    Stic_k Container                        -- exec shodc state -y
    S_hade Container                        -- exec shodc state -s
    Minimi_ze Container                     -- exec shodc state -m
    _Maximize Container [^W]                -- exec shodc state -M
    Container _FullScreen                   -- exec shodc state -f
    Container _Below                        -- exec shodc state -b
    Container _Above                        -- exec shodc state -a
    Move Container _To {
        Move to Desktop _1              -- exec shodc sendto 1
        Move to Desktop _2              -- exec shodc sendto 2
        Move to Desktop _3              -- exec shodc sendto 3
        Move to Desktop _4              -- exec shodc sendto 4
        Move to Desktop _5              -- exec shodc sendto 5
    }
    _Focus {
        Focus Column on the _Left [^H]  -- exec shodc focus -L
        Focus Column on the _Right [^L] -- exec shodc focus -R
        Focus Row _Above [^K]           -- exec shodc focus -T
        Focus Row _Below [^J]           -- exec shodc focus -B
        Focus Previous Tab [^P]         -- exec shodc focus -cP
        Focus Next Tab [^N]             -- exec shodc focus -cN
    }
    _Close Window [^S-Q]                    -- exec shodc close
}

_Music {
    _Next song                              -- exec mpc next
    _Stop song                              -- exec mpc stop
    _Previous song                          -- exec mpc cdprev
    _Toggle Pause/Play                      -- exec mpc toggle
}

In this hypothetical menu system, when this config file is given, a menu will always be visible for the user. Then, if he clicks the Apps menu, another menu will pop up, where the user can open the Games submenu, popping up another menu, in which the user can select GNU Backgammon, and then the string exec gnubg will be passed to sh -c, effectively opening the GNU Backgammon program.

Another way to open GNU Backgammon is to type the keys Alt then A, then G, then B, in this order, effectively navigating through the menus. This is called the Alt Sequence.

Yet another way to open GNU Backgammon is to press Ctrl + Shift + B. This is called the Accelerator keychord.

But this program is not the menu system, it's just a parser for its configuration file.
I just wanted to give you the background for it.

The parser is split into three .c files and a single .h file. And it just builds a tree of Entry structures, and print them out.

ctrlmenu.c:

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

#include "ctrlmenu.h"

static void
printentries(struct Entry *entry, int lvl)
{
    int i;
    for (; entry != NULL; entry = entry->next) {
        for (i = 0; i < lvl; i++)
            printf("\t");
        printf("%s", entry->name);
        if (entry->alt != NULL)
            printf(" (%s)", entry->alt);
        if (entry->cmd != NULL)
            printf(" : %s", entry->cmd);
        printf("\n");
        if (entry->children != NULL) {
            printentries(entry->children, lvl + 1);
        }
    }
}

static void
printaccelerators(struct Accelerator *acc)
{
    printf("\n");
    for (; acc != NULL; acc = acc->next) {
        if (acc->mods & ControlMask)
            printf("Ctrl + ");
        if (acc->mods & ShiftMask)
            printf("Shift + ");
        printf("%s: %s\n", acc->keyname, acc->entry->name);
    }
}

int
main(void)
{
    struct Entry *entries = NULL;
    struct Accelerator *accs = NULL;

    /* commented out code for later version */
    //xinit();
    entries = readfile(stdin, "-", &accs);
    printf("\n");
    //runmenu(menu);
    printentries(entries, 0);
    printaccelerators(accs);
    cleanentries(entries);
    cleanaccelerators(accs);
    //xclose();
}

parse.c:

#include <err.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>

#include "ctrlmenu.h"

#define BUFSIZE 1024
#define UTFMAX  4

/* token types */
enum {
    TOK_NONE        = '\0',
    TOK_NEWLINE     = '\n',
    TOK_CMD         = 'C',
    TOK_NAME        = 'N',
    TOK_OPENCURLY   = '{',
    TOK_CLOSECURLY  = '}',
    TOK_OPENSQUARE  = '[',
    TOK_CLOSESQUARE = ']',
    TOK_ASTERISK    = '*',
    TOK_CARET       = '^',
    TOK_COMMA       = ',',
    TOK_ACCEL       = '_',
    TOK_WHITESPACE  = ' ',
    TOK_EOF         = -1,
};

/* parsedata for reentrant parsing */
struct ParseData {
    /* housekeeping data */
    FILE *fp;
    char *filename;
    size_t lineno;
    int eof;

    /* the token buffer */
    char *bufdata;
    int bufsize;
    int bufindex;

    /* the token itself */
    int toktype;
    char *toktext;
    size_t toksize;
};

static struct Entry *parselist(struct ParseData *parse, struct Accelerator **accs);

static int
efgets(struct ParseData *parse)
{
    if (fgets(parse->bufdata, parse->bufsize, parse->fp) == NULL) {
        if (ferror(parse->fp))
            err(1, "fgets");
        parse->eof = 1;
        return EOF;
    }
    return '\0';
}

static void
readtok(struct ParseData *parse, int isname)
{
    size_t nread, i;
    int eot;                        /* whether we reach end of token */
    int inc;                        /* whether to increment bufindex */

    eot = 0;
    i = 0;
    nread = 1;
    while (!eot) {
        while (isblank((unsigned char)parse->bufdata[parse->bufindex]))
            parse->bufindex++;
        nread += strlen(&parse->bufdata[parse->bufindex]);
        if (parse->toksize < nread) {
            if (parse->toksize == 0)
                parse->toksize = parse->bufsize;
            else
                parse->toksize <<= 1;
            parse->toktext = erealloc(parse->toktext, parse->toksize);
        }
        while (parse->bufdata[parse->bufindex] != '\0') {
            inc = 1;
            if (strchr("{}\n", parse->bufdata[parse->bufindex]) != NULL) {
                parse->toktext[i] = '\0';
                eot = 1;
                break;
            } else if (isname && parse->bufdata[parse->bufindex] == '-' && parse->bufdata[parse->bufindex+1] == '-') {
                parse->toktext[i] = '\0';
                eot = 1;
                break;
            } else if (parse->bufdata[parse->bufindex] == '\\') {
                switch (parse->bufdata[++parse->bufindex]) {
                case 'a':
                    parse->toktext[i++] = '\a';
                    break;
                case 'b':
                    parse->toktext[i++] = '\b';
                    break;
                case 'f':
                    parse->toktext[i++] = '\f';
                    break;
                case 'n':
                    parse->toktext[i++] = '\n';
                    break;
                case 'r':
                    parse->toktext[i++] = '\r';
                    break;
                case 't':
                    parse->toktext[i++] = '\t';
                    break;
                case '\n':
                    if (efgets(parse) == EOF) {
                        warnx("%s:%zu: parse error: unexpected end of file", parse->filename, parse->lineno);
                        eot = 1;
                        break;
                    }
                    parse->lineno++;
                    parse->bufindex = 0;
                    inc = 0;
                    break;
                default:
                    parse->toktext[i++] = parse->bufdata[parse->bufindex];
                    break;
                }
            } else {
                parse->toktext[i++] = parse->bufdata[parse->bufindex];
            }
            if (inc) {
                parse->bufindex++;
            }
        }
    }
    if (i > 0) {
        while (isblank((unsigned char)parse->toktext[i-1]))
            i--;
    }
    parse->toktext[i] = '\0';
}

static void
advance(struct ParseData *parse)
{
    if (parse->bufdata[parse->bufindex] == '\0') {
        /* if there's no data in the buffer, fill it with more data */
        if (efgets(parse) == EOF) {
            parse->toktype = TOK_EOF;
            parse->eof = 1;
            return;
        }
        parse->lineno++;
        parse->bufindex = 0;
    }
    while (isblank((unsigned char)parse->bufdata[parse->bufindex]))
        parse->bufindex++;
    if (strchr("{}\n", parse->bufdata[parse->bufindex]) != NULL) {
        parse->toktype = parse->bufdata[parse->bufindex++];
    } else if (parse->bufdata[parse->bufindex] == '-' && parse->bufdata[parse->bufindex + 1] == '-') {
        /* we got two dashes, read command into toktext */
        parse->bufindex += 2;
        parse->toktype = TOK_CMD;
        readtok(parse, 0);
    } else {
        parse->toktype = TOK_NAME;
        readtok(parse, 1);
    }
}

static int
gettok(struct ParseData *parse)
{
    int rettype;

    if (parse->eof)
        return TOK_EOF;
    else if (parse->toktype == TOK_NONE)
        advance(parse);
    rettype = parse->toktype;
    parse->toktype = TOK_NONE;
    return rettype;
}

static void
ungettok(struct ParseData *parse, int toktype)
{
    parse->toktype = toktype;
}

static int
check(struct ParseData *parse, int expected)
{
    int gottype;

    gottype = gettok(parse);
    ungettok(parse, gottype);
    return gottype == expected;
}

static void
consume(struct ParseData *parse, int expected)
{
    static char *toktab[] = {
        [TOK_NAME]        = "entry name",
        [TOK_OPENCURLY]   = "\"{\"",
        [TOK_CLOSECURLY]  = "\"}\"",
        [TOK_OPENSQUARE]  = "\"[\"",
        [TOK_CLOSESQUARE] = "\"]\"",
        [TOK_ASTERISK]    = "\"*\"",
        [TOK_CARET]       = "\"^\"",
        [TOK_COMMA]       = "\",\"",
        [TOK_ACCEL]       = "key chord",
        [TOK_CMD]         = "command",
        [TOK_WHITESPACE]  = "whitespace",
        [TOK_NEWLINE]     = "newline",
    };
    int gottype;

    if ((gottype = gettok(parse)) != expected) {
        warnx(
            "%s:%zu: parse error: expected %s; got %s",
            parse->filename,
            parse->lineno,
            toktab[expected],
            toktab[gottype]
        );
        parse->bufindex = 0;
        parse->bufdata[0] = '\0';
    }
}

static struct Accelerator *
addaccelerator(char *str, int ctrl, int shift, struct Entry *entry)
{
    struct Accelerator *acc;

    acc = emalloc(sizeof(*acc));
    *acc = (struct Accelerator){
        .next = NULL,
        .mods = 0,
    };
    if (ctrl)
        acc->mods |= ControlMask;
    if (shift)
        acc->mods |= ShiftMask;
    acc->entry = entry;
    acc->keyname = estrdup(str);
    return acc;
}

static void
parsename(struct ParseData *parse, struct Entry *entry, struct Accelerator **accs)
{
    static const unsigned char utfbyte[] = {0x80, 0x00, 0xC0, 0xE0, 0xF0};
    static const unsigned char utfmask[] = {0xC0, 0x80, 0xE0, 0xF0, 0xF8};
    struct Accelerator *acc;
    size_t i, n;
    int ctrl, shift;
    char *s, *p;

    consume(parse, TOK_NAME);
    if ((s = strchr(parse->toktext, '_')) != NULL) {
        /* read alt sequence */
        s++;
        n = 0;
        for (i = 0; i < UTFMAX; i++) {
            if (((unsigned char)*s & utfmask[i]) == utfbyte[i]) {
                n++;
                break;
            }
        }
        if (n > 0 && i < UTFMAX) {
            entry->alt = estrndup(s, n);
            memmove(s - 1, s, strlen(s) + 1);
        }
    }
    if ((s = strchr(parse->toktext, '[')) != NULL) {
        /* read accelerator keychord */
        if (s <= parse->toktext) {
            warnx("%s:%zu: parse error: empty entry name", parse->filename, parse->lineno);
            return;
        }
        *s = '\0';
        for (p = s - 1; p > parse->toktext && isblank(*(unsigned char *)p); p--)
            *p = '\0';
        s++;
        n = strcspn(s, "]");
        if (s[n] != ']' || s[n + 1] != '\0') {
            warnx("%s:%zu: parse error: unmatching square braces", parse->filename, parse->lineno);
            return;
        }
        s[n] = '\0';
        for (p = strtok(s, " \t"); p != NULL; p = strtok(NULL, " \t")) {
            ctrl = *(p++) = '^';
            shift = 0;
            if (p[0] == 'S' && p[1] == '-') {
                shift = 1;
                p += 2;
            }
            acc = addaccelerator(p, ctrl, shift, entry);
            acc->next = *accs;
            *accs = acc;
        }
    }
    entry->name = estrdup(parse->toktext);
}

static void
parsecmd(struct ParseData *parse, struct Entry *entry)
{
    consume(parse, TOK_CMD);
    entry->cmd = estrdup(parse->toktext);
}

static struct Entry *
parseentry(struct ParseData *parse, struct Accelerator **accs)
{
    struct Entry *entry;

    entry = emalloc(sizeof(*entry));
    *entry = (struct Entry){
        .prev = NULL,
        .next = NULL,
        .children = NULL,
        .name = NULL,
        .cmd = NULL,
        .alt = NULL,
    };
    parsename(parse, entry, accs);
    if (check(parse, TOK_CMD)) {
        parsecmd(parse, entry);
    }
    if (check(parse, TOK_OPENCURLY)) {
        consume(parse, TOK_OPENCURLY);
        entry->children = parselist(parse, accs);
        consume(parse, TOK_CLOSECURLY);
    }
    consume(parse, TOK_NEWLINE);
    return entry;
}

static struct Entry *
parselist(struct ParseData *parse, struct Accelerator **accs)
{
    struct Entry *entry, *entries, *last;
    int toktype;

    entries = last = NULL;
    while((toktype = gettok(parse)) != TOK_EOF && toktype != TOK_CLOSECURLY) {
        if (toktype == TOK_NEWLINE)     /* consume blank lines */
            continue;
        ungettok(parse, toktype);
        if ((entry = parseentry(parse, accs)) == NULL)
            break;
        if (entries == NULL)
            entries = entry;
        if (last != NULL)
            last->next = entry;
        entry->prev = last;
        last = entry;
    }
    ungettok(parse, toktype);
    return entries;
}

void
cleanentries(struct Entry *entry)
{
    struct Entry *tmp;

    while (entry != NULL) {
        tmp = entry;
        entry = entry->next;
        if (tmp->name != NULL)
            free(tmp->name);
        if (tmp->cmd != NULL)
            free(tmp->cmd);
        if (tmp->alt != NULL)
            free(tmp->alt);
        if (tmp->children != NULL) {
            cleanentries(tmp->children);
        }
        free(tmp);
    }
}

void
cleanaccelerators(struct Accelerator *acc)
{
    struct Accelerator *tmp;

    while (acc != NULL) {
        tmp = acc;
        acc = acc->next;
        if (tmp->keyname != NULL)
            free(tmp->keyname);
        free(tmp);
    }
}

struct Entry *
readfile(FILE *fp, char *filename, struct Accelerator **accs)
{
    struct Entry *entries;
    struct ParseData parse;
    char buf[BUFSIZE];

    buf[0] = '\0';
    parse = (struct ParseData){
        .fp = fp,
        .filename = filename,
        .lineno = 0,
        .eof = 0,

        .bufdata = buf,
        .bufsize = BUFSIZE,

        .toktype = TOK_NONE,
        .toktext = NULL,
        .toksize = 0,
    };
    entries = parselist(&parse, accs);
    free(parse.toktext);
    return entries;
}

util.c:

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

int
max(int x, int y)
{
    return x > y ? x : y;
}

int
min(int x, int y)
{
    return x < y ? x : y;
}

void *
emalloc(size_t size)
{
    void *p;

    if ((p = malloc(size)) == NULL)
        err(1, "malloc");
    return p;
}

void *
ecalloc(size_t nmemb, size_t size)
{
    void *p;

    if ((p = calloc(nmemb, size)) == NULL)
        err(1, "calloc");
    return p;
}

void *
erealloc(void *ptr, size_t size)
{
    void *p;

    if ((p = realloc(ptr, size)) == NULL)
        err(1, "realloc");
    return p;
}

char *
estrdup(const char *s)
{
    char *t;

    if ((t = strdup(s)) == NULL)
        err(1, "strdup");
    return t;
}

char *
estrndup(const char *s, size_t maxlen)
{
    char *t;

    if ((t = strndup(s, maxlen)) == NULL)
        err(1, "strndup");
    return t;
}

ctrlmenu.h:

#include <X11/Xlib.h>

/* menu entry structure */
struct Entry {
    struct Entry *prev, *next;
    struct Entry *children;
    char *name;                     /* entry name */
    char *cmd;                      /* command entered */
    char *alt;                      /* alternative key sequence */
};

struct Accelerator {
    struct Accelerator *next;
    struct Entry *entry;
    unsigned int mods;
    char *keyname;                  /* accelerator key */
};

extern Display *dpy;

/* parse.c */
struct Entry *readfile(FILE *fp, char *filename, struct Accelerator **accs);
void cleanentries(struct Entry *entry);
void cleanaccelerators(struct Accelerator *accs);

/* x.c */
// void xinit(void);
// void xclose(void);

/* util.c */
int max(int x, int y);
int min(int x, int y);
void *emalloc(size_t size);
void *ecalloc(size_t nmemb, size_t size);
void *erealloc(void *ptr, size_t size);
char *estrdup(const char *s);
char *estrndup(const char *s, size_t maxlen);

You may need to include some X11/Xlib headers for the ControlMask and ShiftMask constants to be defined (or just define them to 0x1 and 0x2).

Since the program is not complete, there are some code commented out (especially those calling x functions in an innexistant x.o module), and there are some unused functions in util.o.

When that input file is given on its stdin, the program will first print the menu structure, and then print the accelerators:

Apps (A)
    Draw Terminal : exec drawterm
    Open Terminal at $HOME (T) : exec xterm
    Open Terminal Here : exec samedir
    Take Screenshot (S) : exec scrot select
    Run (R) : exec runner
    File Manager (M) : exec run fm
    Firefox (F) : exec run www
    Chrome (C) : exec chrome
    Chat (h) : exec hexchat
    Games (G)
        TES III Morowind (M) : exec openmw
        GNU Backgammon (B) : exec gnubg
        Spider (S) : exec spider
        Super Tux Kart (K) : exec supertuxkart
Window (W)
    Stick Container (k) : exec shodc state -y
    Shade Container (h) : exec shodc state -s
    Minimize Container (z) : exec shodc state -m
    Maximize Container (M) : exec shodc state -M
    Container FullScreen (F) : exec shodc state -f
    Container Below (B) : exec shodc state -b
    Container Above (A) : exec shodc state -a
    Move Container To (T)
        Move to Desktop 1 (1) : exec shodc sendto 1
        Move to Desktop 2 (2) : exec shodc sendto 2
        Move to Desktop 3 (3) : exec shodc sendto 3
        Move to Desktop 4 (4) : exec shodc sendto 4
        Move to Desktop 5 (5) : exec shodc sendto 5
    Focus (F)
        Focus Column on the Left (L) : exec shodc focus -L
        Focus Column on the Right (R) : exec shodc focus -R
        Focus Row Above (A) : exec shodc focus -T
        Focus Row Below (B) : exec shodc focus -B
        Focus Previous Tab : exec shodc focus -cP
        Focus Next Tab : exec shodc focus -cN
    Close Window (C) : exec shodc close
Music (M)
    Next song (N) : exec mpc next
    Stop song (S) : exec mpc stop
    Previous song (P) : exec mpc cdprev
    Toggle Pause/Play (T) : exec mpc toggle

Ctrl + Shift + Q: Close Window
Ctrl + N: Focus Next Tab
Ctrl + P: Focus Previous Tab
Ctrl + J: Focus Row Below
Ctrl + K: Focus Row Above
Ctrl + L: Focus Column on the Right
Ctrl + H: Focus Column on the Left
Ctrl + W: Maximize Container
Ctrl + Shift + B: GNU Backgammon
Ctrl + Shift + T: Open Terminal Here
Ctrl + T: Open Terminal at $HOME

Is this parser good? Should I rewrite it in yacc(1) and/or lex(1)?