Strings that can never be parsed with regular expression

Question

I am teaching regular expression to some good programmers. They are good at programming but hardly use regex. My task is to train them up so they know when to use regex and when not.

After showing most regular expression features, I found they are parsing everything with regex. This is not what I want. I want they know that there are some texts that can never be parsed with regex.

But I am out of luck. I know regular expression can parse regular language. If its a non regular language it can not parse it. So I am looking for non regular language example.

My target is when they fail to parse it, they will come up with some custom parser.

So, could you provide some good example of such non-regular language?

[This answer](http://stackoverflow.com/a/1732454/1864610) might give you a start — , May 04 '14 at 07:13
@MikeW that answer is not really helpful. Yes, its funny and there are some insights. But its not helpful. — Shiplu Mokaddim, May 04 '14 at 08:45
@shiplu.mokadd.im On the contrary. The first sentence gives you exactly what you were looking for: _You can't parse [X]HTML with regex_ — , May 04 '14 at 08:48

score 3 · Answer 1 · edited May 23 '17 at 12:28

3

The best example is the parsing html

Show your students this:

<div>
  <div>some shit</div>
  <div>
    This is some shit again
    <div>
      Really? Is this parsable?  
    </div>
  </div>
</div>

and ask them to match the content of the inner most div, provided the html is dynamic.

In general, ask your students not to parse any other language using regex.

The best way to teach them that is by making them read this answer

In other words:

Use regex only when there is a uniform pattern of something

Also,

You cannot parse palindromes
You cannot parse another regex
You cannot match people's names and emails as they vary.(Email can be matched, but is a overkill)

edited May 23 '17 at 12:28

Community

1
1

answered May 04 '14 at 07:15

Amit Joki

58,320
7
77
95

Should I tell my students "match the inner divs content but dont use back-reference" ? – Shiplu Mokaddim May 04 '14 at 09:01
no. Ask them to get the innermost div's content – Amit Joki May 04 '14 at 09:02
@shiplu.mokadd.im, but if you say them not to use back-reference, then it would be even more diffiocult – Amit Joki May 04 '14 at 09:07

score 2 · Answer 2 · answered May 04 '14 at 07:17

2

A simple and understandable example of a non-regular language would be the language of palindromes, or in other words, strings that are equal to their reverses. It's pretty easy to demonstrate its non-regularity with the pumping lemma (see Wikipedia: http://en.wikipedia.org/wiki/Pumping_lemma)

Mind though, that in practical computing, the distinction isn't quite as clear, as many regular expression engines support features such as back references that allow recognition of certain non-regular languages. A regex engine with back references can match, for example, the language of squares or repetitions ("PonyPony", "123123", "gg" etc): (.*)\1 which isn't possible without back references.

answered May 04 '14 at 07:17

kviiri

3,282
1
21
30

So is backreference making regular expression parse non-regular language? – Shiplu Mokaddim May 04 '14 at 08:48
@shiplu.mokadd.im, yes, you can use back references to parse certain non-regular languages, for example the language of squares (strings that are the same substring repeated twice). Not all of them though - there are some languages that can't be recognized even with a Turing machine. – kviiri May 04 '14 at 08:54

Strings that can never be parsed with regular expression

2 Answers2

The best example is the parsing html

In other words:

Also,