http://qs321.pair.com?node_id=678271


in reply to RFC: Parsing with perl - Regexes and beyond

The first two definitions are recursive, so they are not "regular" any more.

You can argue that the first production is "tail recursive" which does not pose a problem with respect to regularity. Like a tail recursive function can be transformed into a loop.

The non-regularity comes with the 2nd production.

term        -> '(' term ')'

The point is that term can grow to arbitrary length and we still should keep the correspondence between the two parentheses, which is not possible with (CS)-Regexes ("pumping lemma").

This last observation is the border where you need a CFL-parser and would be lost with Regexes alone.