14
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Kaveh
    Commented May 20, 2012 at 4:12
  • $\begingroup$ For a practical answer, you could look at the Plan 9 Grep source for grep.y. $\endgroup$
    – Bruce Ediger
    Commented May 21, 2012 at 15:35

2 Answers 2

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Phil Wright
    Commented May 20, 2012 at 10:52
  • $\begingroup$ @PhilWright: I see, nice! I edited in further pointers for this case. $\endgroup$
    – Raphael
    Commented May 20, 2012 at 11:00
  • $\begingroup$ I'd favour a hand-coded recursive descent parser for this one. $\endgroup$
    – Dave Clarke
    Commented May 20, 2012 at 12:00
  • $\begingroup$ 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. $\endgroup$
    – vonbrand
    Commented Feb 5, 2013 at 13:42
3
$\begingroup$

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".

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented May 20, 2012 at 21:46
  • 4
    $\begingroup$ You (and Jukka) aren't parsing regexps, only recognizing them. “Yup, that's a (compressed) regexp.” $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented May 21, 2012 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.