# Does the language of Regular Expressions need a push down automata to parse it?

I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular expresssions?

I assume it must be a push down automaton because the presense of brackets means the need to count and a DFA/NFA cannot perform arbitrary counting. Is this assumption correct? For example, the expression a(bc*)d would require a PDA so that the sub-expression in brackets is handled correctly.

• What do you mean exactly by "parsing"? Do you mean checking if the input is really a regular expression or do you have a more complicated thing in mind, e.g. a machine outputting a description of the corresponding NFA? (if you are not sure if the input is really a regular expression and you need to check it then you need to be able to check that parenthesis are correct and that normally means using a stack.) – Kaveh May 20 '12 at 4:12
• For a practical answer, you could look at the Plan 9 Grep source for grep.y. – Bruce Ediger May 21 '12 at 15:35

You are correct. It is easy to show that the syntax of regular expressions is not regular using standard techniques.

One possibility is to use a homomorphism (which $\mathrm{REG}$ is closed against) to get rid of all symbols but the parentheses, which leaves you with the Dyck language which is well-known to be non-regular. If in doubt, use the Pumping lemma on $(^p)^p$.

That said, you probably do not want to code a PDA by hand. Consider using a parser generator like ANTLR or byacc. If, on the other hand, you want to investigate the parsing of languages by programming parsers yourself, you should continue with other basic parsing algorithms such as CYK, Earley, recursive descent and LR.

• thanks. writing code for these tasks creates a better understanding and is not intended to be as efficient as existing utilities like lex,yacc,bison etc. – Phil Wright May 20 '12 at 10:52
• @PhilWright: I see, nice! I edited in further pointers for this case. – Raphael May 20 '12 at 11:00
• I'd favour a hand-coded recursive descent parser for this one. – Dave Clarke May 20 '12 at 12:00
• If writing a parser by hand for this, either recursive descent (after factoring and massaging) is an option, the LCC parser for C <sites.google.com/site/lccretargetablecompiler> has an interesting take for handling lots of operators. But perhaps easiest for hand-building is precedence parsing. – vonbrand Feb 5 '13 at 13:42

I suggest you to read the Jukka's nice answer to the question "Matching regular expressions using regular expressions" on cstheory, too. An excerpt:

For example, we can modify the standard notation as follows to obtain "compressed" regular expressions:

• You are allowed to remove any prefix that consists of a sequence of ('s
• You are allowed to remove any suffix that consists of a sequence of )'s

That is, ((a|b)*c)de(f|g) can be expressed in the "compressed" notation using, for example, any of the following forms: a|b)*c)de(f|g or ((a|b)*c)de(f|g or (a|b)*c)de(f|g).

[...]

The "compressed" notation (of a regular expression) is a regular language.

This is only a link to an interesting (according to me) "different view" on the regular expression language; as underlined in the comments below, it is not useful for building a syntax tree. If you want to hand code your parser I'll suggest you this simple article on codeproject "Writing-own-regular-expression-parser".

• Jukka essentially removes the requirement that parentheses are balanced. I know of no instance where this is actually done, but it is worth remarking that by changing semantics, you can "simplify" syntax. – Raphael May 20 '12 at 21:46
• You (and Jukka) aren't parsing regexps, only recognizing them. “Yup, that's a (compressed) regexp.” – Gilles 'SO- stop being evil' May 21 '12 at 22:21