From mboxrd@z Thu Jan 1 00:00:00 1970 References: <3aaafc130908201052o3c8a6334v13350c18f78120d9@mail.gmail.com> Message-Id: <354A6332-3395-4950-A655-ECBF0EED6C0F@gmail.com> From: "J. R. Mauro" To: Fans of the OS Plan 9 from Bell Labs <9fans@9fans.net> In-Reply-To: Content-Type: text/plain; charset=us-ascii; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit Mime-Version: 1.0 (iPhone Mail 7A341) Date: Fri, 21 Aug 2009 10:57:36 -0400 Cc: Fans of the OS Plan 9 from Bell Labs <9fans@9fans.net> Subject: Re: [9fans] Recursive structural expressions? Topicbox-Message-UUID: 5031d7be-ead5-11e9-9d60-3106f5b1d025 On Aug 21, 2009, at 10:24, Russ Cox wrote: > Regular expressions, in the strict formal sense, have > an important property: they completely express the set > of patterns that can be searched for in a single linear-time > pass through the text. That is, they have an associated > linear-time performance guarantee. > > In your particular case, adding recursion would produce > context-free expressions, and general context-free parsing as > typically implemented is cubic as opposed to linear. > (It turns out to be the same problem as matrix multiplication, > so with a lot more effort you could get it down to n^2.38 or > perhaps even lower, but you can't possibly get sub-quadratic.) > > As Charles pointed out, there is a long, distinguished > history of editors and other tools making regular expressions > more expressive. It is important to remember that this > is always done at the cost of giving up the performance > guarantee, at least in some cases. And unless a general > matcher can distinguish the different cases and implement > separate algorithms for each, it usually gives up the > performance guarantee in all cases. > > Russ > This, and complexity/ambiguity are almost certainly why they didn't carry from qed into ed. Perhaps at least a context-free grep would be a useful thing to have, considering the limitations CF expressions would place on a text editor.