From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: =?ISO-8859-1?Q?Andreas_R=F6hler?= Newsgroups: gmane.emacs.devel Subject: Re: Possible problem with looking-back function Date: Thu, 19 Aug 2010 11:32:12 +0200 Message-ID: <4C6CFA1C.7080609@online.de> References: <4C6C85AD.1010500@ig.com.br> <49933.130.55.132.107.1282185810.squirrel@webmail.lanl.gov> <4C6CCA8B.5060106@online.de> <8739ubug9r.fsf@uwakimon.sk.tsukuba.ac.jp> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-Trace: dough.gmane.org 1282210416 6945 80.91.229.12 (19 Aug 2010 09:33:36 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Thu, 19 Aug 2010 09:33:36 +0000 (UTC) Cc: Stefan Monnier , Emacs developers To: "Stephen J. Turnbull" Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu Aug 19 11:33:33 2010 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Om1V5-0002I7-J6 for ged-emacs-devel@m.gmane.org; Thu, 19 Aug 2010 11:33:31 +0200 Original-Received: from localhost ([127.0.0.1]:38199 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Om1V5-00088b-3W for ged-emacs-devel@m.gmane.org; Thu, 19 Aug 2010 05:33:31 -0400 Original-Received: from [140.186.70.92] (port=36332 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Om1Uv-00088S-D9 for emacs-devel@gnu.org; Thu, 19 Aug 2010 05:33:22 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1Om1Ut-0006Dd-TP for emacs-devel@gnu.org; Thu, 19 Aug 2010 05:33:21 -0400 Original-Received: from moutng.kundenserver.de ([212.227.17.10]:56833) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1Om1Ut-0006DE-I1 for emacs-devel@gnu.org; Thu, 19 Aug 2010 05:33:19 -0400 Original-Received: from [192.168.178.27] (brln-4db9cca8.pool.mediaWays.net [77.185.204.168]) by mrelayeu.kundenserver.de (node=mreu0) with ESMTP (Nemesis) id 0MUjgO-1OMbG547pc-00YAdh; Thu, 19 Aug 2010 11:33:10 +0200 User-Agent: Mozilla/5.0 (X11; U; Linux i686; de; rv:1.9.1.11) Gecko/20100711 Thunderbird/3.0.6 In-Reply-To: <8739ubug9r.fsf@uwakimon.sk.tsukuba.ac.jp> X-Provags-ID: V02:K0:wRFPd9FARbA2yqLe48yYQgGO/AeZbjJr6dLptJY/RmV 5urRQ2Zrr2NXvo/qjlCDM0QptAwLk+L3pDOT2QfXMX7HRyKjdk +wPr3XYZST30gIVU8VoYjI87D28cPW6hzhh5TN708/OyVdcUF5 KZ23MGGuZKxBHu3xWJvSVhHgioMCw1MOVPZ7Pt2iJJEKLsf4/Y xJewIuQo+dYarWa7z+z6U92dGIc0PYihfxin2TaO9o= X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:128865 Archived-At: Am 19.08.2010 11:02, schrieb Stephen J. Turnbull: > Andreas Röhler writes: > > > that surprises me. Check must be done against the string already > > found. So workload should grow lineary resp. slightly ascending. > > That's incorrect. In regexp matching abstractly defined, there is no > "string already matched." In general backtracking must be done to get > a correct POSIX match, and it's potentially very expensive. It would > be sometimes possible (as in this case) to identify a non-backtracking > algorithm as you suggest, but that would mean that different regexps > would be treated differently, or that some regexps would be > ridiculously expensive. > > Hi, just for the curious: Coming upon the matter, as in markup languages point may be inside the start tag. Solved it whith function below --begstr is the startup-tag Sometimes begstr is used inside beg-end function quoted: (regexp-quote begstr), therefor the startup tag is delivered in both forms here, making looking-at working - not sure, if its really necessary btw-- (defun ar-leave-begstr-backward (begstr unquoted-beg) (let* ((stringcount (length unquoted-beg)) (collected (char-to-string (char-after))) (indx (string-match (regexp-quote collected) unquoted-beg))) (while (and indx (not (ignore-errors (looking-at begstr)))(< 1 stringcount)) (forward-char -1) (setq collected (concat (char-to-string (char-after)) collected)) (setq indx (string-match (regexp-quote collected) unquoted-beg)) (setq stringcount (1- stringcount))))) See beg-end.el at https://code.launchpad.net/s-x-emacs-werkstatt/