0

I found in a book about regular expression grammars something that said RE's can be used to describe sentences like this ‘the brown tea pot’ by using re like this np = det+"?"+"("+noun+"|"+adj+")*"+noun but that it can't be used to describe recursive structures as in this sentence:

‘the man with a big nose’s wife’

Can anyone explain why is that as I don't see it clearly?

2
  • 1
    The conclusion seems to be that regular expressions cannot handle recursive structures simply by definition, since regular expressions are defined formally as expressing regular languages, which don't have a recursive structure. If your 'regular expression' expresses a language with a recursive structure, it simply isn't a regular expression in the strict, formal sense. See also the responses to this question: stackoverflow.com/questions/2255403/…
    – P Elliott
    Jan 19, 2014 at 18:23
  • Indeed if you're learning compilers then quite early on you learn the difference between lexical analysis, which can be done with regular expressions, and parsing, which cannot specifically due to the need for recursion. The former is a subset of the latter but much easier to handle. Jan 20, 2014 at 16:53

2 Answers 2

3

Regular expressions cannot handle recursive structures simply by definition, since regular expressions are defined formally as expressing regular languages, which don't have a recursive structure. If your 'regular expression' expresses a language with a recursive structure, it simply isn't a regular expression in the strict, formal sense.

See also the responses to these questions on stackoverflow:

(Pasted in from my comment)

0

As P. Eliott already wrote, REs can't describe recursion.

The second link needed is to explain where recursion appears in language: Think of The button on the skirt of the girl on the street, where NPs are nested inside each other. Or think of relative clauses, which are part of a bigger sentence - in that case, VPs are nested. Building NPs from NPs (or VPs from VPs) is what the mathematician calls recursion.

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.