From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Helmut Eller Newsgroups: gmane.emacs.devel Subject: Re: Make peg.el a built-in library? Date: Sun, 10 Oct 2021 07:58:13 +0200 Message-ID: References: <875yvtbbn3.fsf@ericabrahamsen.net> <87a6jjc7c8.fsf@web.de> <87v926w3bs.fsf@ericabrahamsen.net> <87zgrhh4he.fsf@web.de> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="9856"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) To: emacs-devel@gnu.org Cancel-Lock: sha1:mTXRoaPjJgCS7QEg1JdRUPOrS6Y= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sun Oct 10 07:59:19 2021 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1mZRri-0002NB-SU for ged-emacs-devel@m.gmane-mx.org; Sun, 10 Oct 2021 07:59:18 +0200 Original-Received: from localhost ([::1]:58052 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mZRrh-0007O4-VP for ged-emacs-devel@m.gmane-mx.org; Sun, 10 Oct 2021 01:59:17 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:56242) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mZRqq-0006gB-3n for emacs-devel@gnu.org; Sun, 10 Oct 2021 01:58:24 -0400 Original-Received: from ciao.gmane.io ([116.202.254.214]:47706) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mZRqo-0001Kv-L7 for emacs-devel@gnu.org; Sun, 10 Oct 2021 01:58:23 -0400 Original-Received: from list by ciao.gmane.io with local (Exim 4.92) (envelope-from ) id 1mZRqm-0001BT-VZ for emacs-devel@gnu.org; Sun, 10 Oct 2021 07:58:20 +0200 X-Injected-Via-Gmane: http://gmane.org/ Received-SPF: pass client-ip=116.202.254.214; envelope-from=ged-emacs-devel@m.gmane-mx.org; helo=ciao.gmane.io X-Spam_score_int: 5 X-Spam_score: 0.5 X-Spam_bar: / X-Spam_report: (0.5 / 5.0 requ) BAYES_00=-1.9, DKIM_ADSP_CUSTOM_MED=0.001, FORGED_GMAIL_RCVD=1, FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, NML_ADSP_CUSTOM_MED=0.9, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=no autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:276638 Archived-At: On Sun, Oct 10 2021, Michael Heerdegen wrote: > Is it practically possible to transform a regexp into a really > equivalent PEG, or is it too difficult, or would the resulting PEG just > be too large or inefficient? The LPEG people wrote a paper[*] about this problem. But I haven't read it. I think, that regexp without backrefs can be implemented with DFAs, and, hence, shouldn't need any backtracking. The problem probably are backrefs and other extensions. Helmut http://www.lua.inf.puc-rio.br/publications/medeiros11regular.pdf