Parsing Regular Expressions with MGCPGen

mgcadmin 10-08-2026

Parsing regular expressions can be a real chicken-or-the-egg scenario, many algorithms for compiling regular expressions to NFA or DFA involves converting the expression to an AST. This is the job of a parser of course, which as you may know tend to interact with a lexer, whos specification is generally written as... regular expressions. In previous posts I've covered how to circumvent this seemingly meta-issue using both the shunting yard algorithm as well as recursive descent to turn a regex into an AST.

For todays post we're going to turn the volume up to 11 and use MGCPGen, my LALR(1) Parser Generator to generate the parser for us along with MGCLex to generate a lexer for said parser. Lets get meta.

regex.mlex

In order for our parser to make heads or tails of the text being fed to it, the input is first passed through a lexer to perform lexical analysis the string so it can be propely tokenized. Because we are describing regular expression operators by using regular expressions themselves, the operators being described must be escaped.

{"\(",LPAREN}
{"\)",RPAREN}
{"\[",LSQB}
{"\]",RSQB}
{"\-",DASH}
{"\*",KLEENE_STAR}
{"\|",OR}
{"[\]",ESCAPE}
{"\^",NEGATE}
{"[.]",PERIOD}
{"[?]",QMARK}
{"[+]",KLEENE_PLUS}
{".",CHAR}

Because our specification is made up entirely of single-character rule patterns, the resulting DFA is extremely compact. Saving our specification as regex.mlex we are ready to process it with mgclex. I like to use the -c option to produce pair-compressed lex tables.

mgclex regex.mlex lexer_matrix.hpp -c

regex.mgrm

Having been designed to use together, MGCPGen "include"s the lexer specification to use as the source of it's terminal list using the `terminal_list` directive at the top of the file. We also include the typename that the semantic stack will hold and which the parser will ultimately return. In this case, we're returning `astnode`. More specifically our parser will return the root node of the produced AST.

The grammar is arranged by precedence with the 'or' operator ('|') having the lowest, followed by concatenation, and the closure operators having the highest prcedence. Grouping with parentheses will override operator precedence. Characters/digits, character classes, and wildcards will always be leaf nodes in the resulting tree. 

terminal_list regex.mlex
type_returned astnode
sp ::= regex
regex ::= regex OR catexpr   @mkOr
regex ::= catexpr
catexpr ::= catexpr repexpr  @mkConcat
catexpr ::= repexpr 
repexpr ::= val KLEENE_STAR  @mkKleene
repexpr ::= val KLEENE_PLUS  @mkKleene
repexpr ::= val QMARK        @mkOpt
repexpr ::= val
val ::= LPAREN regex RPAREN  @pass
val ::= CHAR                 @mkLeaf
val ::= PERIOD               @mkLeaf
val ::= ESCAPE CHAR          @mkEscaped
val ::= LSQB optneg cclist RSQB     @mkCcl
optneg ::= NEGATE
optneg ::= #
cclist ::= cclist ccent      @mkList
cclist ::= ccent
ccent ::= CHAR DASH CHAR     @mkCCLRange
ccent ::= CHAR

The AST is constructed bottom-up using the action symbols associated with a given rule. Action symbols are referenced by the name of their corresponding procedure, prefixed with an '@' symbol. Action procedures adhere to a simple interface, they are passed a vector of ast nodes and return a single astnode - the result of combining the contents of the vector into the desired tree shape.

Building an AST with Parser Actions

Without action routines our parser is little more than a recognizer in that it can tell us if input is valid or not, but thats about it. Not very useful.  In order to emit an actual usable AST, action routines are triggered during reductions. As mentioned above all action routines have the same interface.  

astnode* pass(vector<astnode*>& r);
astnode* mkLeaf(vector<astnode*>& r) ;
astnode* mkConcat(vector<astnode*>& r);
astnode* mkKleene(vector<astnode*>& r) ;
astnode* mkOpt(vector<astnode*>& r);
astnode* mkOr(vector<astnode*>& r);
// If supporting character classes:
astnode* mkList(vector<astnode*>& r);
astnode* mkCCLRange(vector<astnode*>& r);
astnode* mkCcl(vector<astnode*>& r);
astnode* mkEscaped(vector<astnode*>& r);

Single item productions don't require an action routine unless some specific action is needed. This is because the default behavior for single item reductions is to simply fall through. An example of a "specific action" on single reductions is the @mkLeaf action. In this procedure we take the opportunity to tag the nodes type, with it being a leaf and us working bottom up.

astnode* mkLeaf(vector<astnode*>& r) {
    r[0]->type = CONST_EXPR;
    return r[0];    
}

The size of the vector passed to the procedure will match the number of symbols on the right hand side of the production being reduced. An 'or' expression like a|b will match to the production "regex ::= regex OR catex" so its action routine expects a an astnode for a reduced regex non-terminal, an astnode for an or operator terminal, and an astnode for a reduced catexpr non-terminal. 

astnode* mkOr(vector<astnode*>& r) {
    astnode* nn = r[1];
    nn->type = OR_EXPR;
    nn->children[0] = r[0];
    nn->children[1] = r[2];
    return cc;
}

We then take these three tree's an arrange them so the 'or' operator node becomes the root, with the other two trees as it's children. The resulting tree is the reduced production which is returned and placed on the stack. Just as we constructed the tree for the or expression like we would any in-fix binary operator, we handle closure operators, *,+,? as postfix unary operators.

// r* r+
astnode* mkKleene(vector<astnode*>& r) {
    r[1]->type = KLEENE_EXPR;
    r[1]->children[0] = r[0];
    return r[1];
}

// r?
astnode* mkOpt(vector<astnode*>& r) {
    r[1]->type = OPT_EXPR;
    r[1]->children[0] = r[0];
    return r[1];
}

The concat operator which is only implicitly present requires the creation of a node to glue it's two expression operands together, otherwise it follows much as any other binary operator.

astnode* mkConcat(vector<astnode*>& r) {
    astnode* cc = new astnode(Token(CHAR, "@"));
    cc->type = CONCAT_EXPR;
    cc->children[0] = r[0];
    cc->children[1] = r[1];
    return cc;
}

One quick thing to note however is that action routines are responsible for freeing the memory of any unused symbols from a production - like when we throw away the parentheses during AST constructions as they would be redundant:

astnode* pass(vector<astnode*>& r) {
    swap(r[1],r[2]);
    auto ret = r.back();
    r.pop_back();
    for (auto & m : r) {
        delete m;
    }
    return ret;
}

The full suite of action routines is available on the linked git hub below

Generating The Parser

After saving the above specification as regex.mgrm we can feed it into MGCPGen to generate our parser. Using the -l flag produces an LALR(1) optimized table, while -c would output a CLR(1) table.

mgcpgen -l regex.mgrm parse_table.hpp

The LALR table will of course have far fewer states and entries than its equivelant CLR table and so uses less memory. Regardless of which parser type you choose, we now have everything we need to parse regular expressions into an AST.

astnode* expr2ast(string pattern) {
    Lexer lexer(true);
    Parser parser(true);
    bool running = true;
    string buffer;
    StringBuffer sb;
    sb.init(pattern);
    return parser.parse(lexer.lex(&sb));
}    

mgoren@~/regex/nfa_to_dfa$ ./pmatch "(a|b)*abbd" babbd
 @
  @
   @
    @
     *
      |
       a
       b
     a
    b
   b
  d
New: 1  (0 1 2 4 5 7 8 9 10 )
New: 2  (0 2 3 4 5 7 8 )
New: 3  (0 2 3 4 5 7 8 11 12 )
New: 4  (0 2 3 4 5 7 8 13 14 )
New: 5  (15 )
Marked 5 as accepting for 15
0 b -> 2 a -> 1 b -> 3 b -> 4 d -> Match Found.

So there you have it, a quick little tour of implementing an AST generating parser for regular expressions using MGCPGen & MGCLex. Happy Hacking!

Further Resources:

https://github.com/maxgoren/nfa_to_dfa

---