3
\$\begingroup\$

This is a small part of a larger program for implementing a limited syntax regular expression constructor using Ken Thompson's construction algorithm. Converting to postfix before the regular expression is processed makes the processing vastly simpler because everything can be smoothly read and processed left to right. The following algorithm for performing the conversion works in a shunting-yard like manner where an operator stack is used to determine when operators should be sent to the output string.

Conversion Function:

typedef struct _conv_ret {
    char *re;
    int err;
} conv_ret;

conv_ret conv(char *re) {
    /* converts limited regex infix notation with explicit
     * catenation denoted by '.' to postfix in a shunting-yard manner */
    
    conv_ret ret = {NULL, REGEX_TOOLARGE};

    if(strlen(re) > MAX_LINE)
        return ret;

    static char buf[MAX_LINE];
    char *bufp = buf;

    ret.re = buf;
    ret.err = 0;

    /* operator stack */
    int bp[strlen(re)];
    int *sp = bp; 

    #define OP_NUM 6

    /* placeholder for id 0 */
    char id_map[OP_NUM+1] = {' ', '(', '|', '.', '?', '+', '*'};
    int prec_map[OP_NUM+1] = {0, 1, 2, 3, 4, 4, 4};
    
    #define push(id) *++sp = id
    #define pop()    *bufp = id_map[*sp--]; bufp++

    for(; *re; re++) {
        /* loop skips open paren (id 1) because it is only there
         * as a placeholder until the closing paren is pushed */
        for(int id = 2; id < OP_NUM+1; id++) {
            /* pop until incoming op is 
             * highest precedence on stack */
            if(id_map[id] == *re) {
                if(sp > bp) {
                    while(prec_map[id] <= prec_map[*sp]) {
                        pop();
                    }
                }
                push(id);
                goto RELOOP;
            }
        }
        switch(*re) {
        case '(':
            push(1);
            goto RELOOP;
        case ')':
            while(*sp != 1) {
                /* couldn't find matching paren. send error */
                if(sp == bp) {
                    ret.re = NULL;
                    ret.err = PAREN_MISMATCH;
                    return ret; 
                }
                pop();
            }
            /* pop without sending paren to buf */
            --sp;
            goto RELOOP;
        default:
            /* send non op to buf */
            *bufp = *re;
            bufp++;
        }
        RELOOP: ;
    }
    /* pop all leftover values in stack to buf */
    while(sp > bp) {
        /* error if unmatched open paren */ 
        if(*sp == 1) {
            ret.re = NULL;
            ret.err = PAREN_MISMATCH;
            return ret;
        }
        pop();
    }
    
    /* null terminate */
    *bufp = 0;

    return ret;
}

Header:

#include <string.h>

#define MAX_LINE 10000

/* error codes */
#define REGEX_TOOLARGE 1
#define PAREN_MISMATCH 2

Note: Further errors are caught in later stages of parsing within the program, but this post is just about the postfix conversion and the conversion itself is not meant to do a whole lot of syntactic and semantic parsing.

Examples:

a+a -> aa+

a+a* -> aa+*

a.(a+b)*.b -> aab+*.b.

a.(a+b)*.b() -> aab+*.b.

a.(a+b)*.b) -> PAREN_MISMATCH

a.(a+b)*.b( -> PAREN_MISMATCH

Any criticisms aimed towards improving the efficiency and readability of this code would be greatly appreciated.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ It would be helpful for reviewers to have the missing #define information as well as any header files used for the code. It would also be helpful if you added any test cases (programs and data) you wrote for this code. \$\endgroup\$
    – pacmaninbw
    Sep 4, 2020 at 12:55
  • \$\begingroup\$ @pacmaninbw I added some more information. Hopefully it helps! \$\endgroup\$
    – user228607
    Sep 4, 2020 at 13:28
  • 1
    \$\begingroup\$ Please do not modify the question after an answer has been posted, especially please do not modify the code, everyone has to see the code as reviewed help center. \$\endgroup\$
    – pacmaninbw
    Sep 4, 2020 at 15:45
  • \$\begingroup\$ Please see the rules I pointed at. \$\endgroup\$
    – pacmaninbw
    Sep 4, 2020 at 16:09
  • \$\begingroup\$ You can post a follow up question with your changes and link back to this one. \$\endgroup\$
    – pacmaninbw
    Sep 5, 2020 at 3:14

2 Answers 2

2
\$\begingroup\$

General Observations

It is difficult to accurately define any bottle necks when only one function is presented. The brief moment when main() and match() were visible was very helpful, although it would have been nice if the body of match() was included as well.

It might be better to use a power of 2 (1024, 2048, ...) for MAX_LINE rather than a round number like 10000.

The code is overly complex and should be broken into multiple functions, this is actually proved by the multiple goto RELOOP; statements. These goto statements can be replaced by break; and continue and in one case by the return of a function. Try to avoid writing Spaghetti code.

Implement Stacks using Structs

It is much easier to maintain code when the stack pointer and the stack container (array) can be found in one place. Rather than write push and pop as macros, implement them as functions that take a stack struct, and in the case of push the parameter of what is being pushed on the stack.

Magic Numbers

While there are symbolic constants used rather than number constants in some parts of the code, this could be improved, it is also possible to use enums rather than #define to define symbolic constants in C and I would recommend using enums to represent the error ids because it is expandable.

typedef enum Error_Code
{
    REGEX_TOOLARGE = 1,
    PAREN_MISMATCH = 2
} Error_Code;

Just a quick though here, if the error codes start at 0 rather than 1 than any error messages could be stored as an array of strings.

The place where there are still magic numbers is in this code:

    int prec_map[OP_NUM] = { 1, 2, 3, 4, 4, 4 };

It isn't clear what any of those numbers mean.

It isn't clear that OP_NUM is necessary because the count can be determined by either one of the following:

    char id_map[] = { '(', '|', '.', '?', '+', '*' };
    const size_t OP_NUM = sizeof(id_map)/sizeof(*id_map);

or

    int prec_map[] = { 1, 2, 3, 4, 4, 4 };
    const size_t OP_NUM = sizeof(prec_map)/sizeof(*prec_map);

Numeric constants in code are sometimes referred to as Magic Numbers, because there is no obvious meaning for them.

Posible Optimization

Use strlen() only once and store the value in a variable.

\$\endgroup\$
2
\$\begingroup\$

Avoid function-like macros. They are sooo seventyish, and they may seriously reduce the readability of the code. In this particular case it took me a while to realize that

    while(sp > bp) {
        /* error if unmatched open paren */ 
        if(*sp == 1) {
            ret.re = NULL;
            ret.err = PAREN_MISMATCH;
            return ret;
        }
        pop();
    }

is not an infinite loop. Looking at just this snippet, it is not possible to see that sp does change. The fact that it is decremented is hidden in pop(), and very hidden it is.

Use an inline function, and trust the compiler to produce an identical code. The compilers are very good in optimization these days.


The inner loop over ids does not look pretty. The nesting is too deep. Factor out important functions. First, the real job is done only when id_map[id] == *re. It means

    int id = find_id(*re);
    if (id != INVALID_ID) {
        do_the_job;
    } 

gotos are not called for. Those inside switch are absolutely unnecessary; a normal break would do the same thing. The goto inside the inner loop is more tricky to eliminate. Notice that it naturally belongs to the default case of the switch: it does nothing for ( and ). Also notice that the

    *bufp = *re;
    bufp++;

sequence is only executed if push(id) never happened.

With the previous comment in mind, consider

    default:
        id = find_id(*re);
        if (id == INVALID_ID) {
            *bufp++ = *re;
        } else {
            do_the_job;
        }

See how the gotos disappear. And yet again, don't be shy of functions.

\$\endgroup\$
1
  • \$\begingroup\$ Yeah. I completely refactored the code such that everything is within a switch statement, the id system is totally different, and b/c unary operators are unnecessarily processed in the stack, the only operator ever to go in the stack is the binary union '|'. I wish I could change my code as in the original post because when someone looks up 'regex infix to postfix', this comes up, and I don't want people to see such sloppy and bad/ not even fully functional for some cases code, but it is what it is. \$\endgroup\$
    – user228607
    Sep 5, 2020 at 0:12

Your Answer

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