From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Make peg.el a built-in library? Date: Sun, 10 Oct 2021 09:56:09 -0400 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="33673"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/28.0.50 (gnu/linux) Cc: emacs-devel@gnu.org To: Helmut Eller Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sun Oct 10 15:57:14 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 1mZZKD-0008VO-LI for ged-emacs-devel@m.gmane-mx.org; Sun, 10 Oct 2021 15:57:13 +0200 Original-Received: from localhost ([::1]:43866 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mZZKB-0008J9-Hn for ged-emacs-devel@m.gmane-mx.org; Sun, 10 Oct 2021 09:57:11 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:52798) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mZZJK-0007bh-WA for emacs-devel@gnu.org; Sun, 10 Oct 2021 09:56:19 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:46394) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mZZJI-0004de-8i for emacs-devel@gnu.org; Sun, 10 Oct 2021 09:56:17 -0400 Original-Received: from pmg2.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 1E5B080620; Sun, 10 Oct 2021 09:56:13 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 2D81A80300; Sun, 10 Oct 2021 09:56:11 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1633874171; bh=DfSSVwTiMuZ1xcI8X252jW438gWYtrzwQgdL/1g6F2E=; h=From:To:Cc:Subject:References:Date:In-Reply-To:From; b=CWi5HTTOTkJtSAcgqtGVW+0o9A5U2Vu0uWYYy5iwdCmGgks4onUehy6xWffFm3N0E lipc6CFfdR5mSoeIHHg/SA9wLuhwLNoNsh5DhLdNFcxCyVAzhXRuYM2XYyBSG7EUrP 7CT56tThaV7ARaFMxe08mpTvFB4XoSSh3PgezApfUKwRCQJQPZhT62/wFNPa5JanSs lOVFx1iRiWLscsR0SsbwwWOxLFNmrZNTc/XKq4EpTOZ5r38qIDEyG7I5rkYDc7apBZ TRMQS4TLGVex/6sQ3WDJ3Z+D1h89XB2tYM0NA/GpbKG4B1c3hDq4HzZkyYLC6FFPFq sH3SF5Ap4dcRw== Original-Received: from pastel (unknown [45.72.241.23]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id C13C5120317; Sun, 10 Oct 2021 09:56:10 -0400 (EDT) In-Reply-To: (Helmut Eller's message of "Sun, 10 Oct 2021 07:58:13 +0200") Received-SPF: pass client-ip=132.204.25.50; envelope-from=monnier@iro.umontreal.ca; helo=mailscanner.iro.umontreal.ca X-Spam_score_int: -42 X-Spam_score: -4.3 X-Spam_bar: ---- X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham 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:276667 Archived-At: >> 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 This is similar to turning the regexp into an NFA and then using the PEG backtracking to run the NFA. Our regexp engine tries to remove some simple forms of backtracking (e.g. for regexps like "\\(.foo\\)*\nbar" because \n and . are mutually exclusive). This significantly reduces the amount of stack use. We could/should perform similar optimizations in `peg.el`. Stefan