From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Augusto Stoffel Newsgroups: gmane.emacs.devel Subject: Re: Make peg.el a built-in library? Date: Tue, 28 Sep 2021 17:24:18 +0200 Message-ID: <871r58n2ot.fsf@gmail.com> References: <875yvtbbn3.fsf@ericabrahamsen.net> <87bl5k87hq.fsf@alphapapa.net> <87fsuvpod4.fsf@ericabrahamsen.net> <874ka7wqko.fsf@gmail.com> <87sfxp4ard.fsf@ericabrahamsen.net> <20210928080902.GC14380@tuxteam.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="27729"; 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: Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Tue Sep 28 17:25:15 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 1mVEyo-0006yF-S4 for ged-emacs-devel@m.gmane-mx.org; Tue, 28 Sep 2021 17:25:14 +0200 Original-Received: from localhost ([::1]:49886 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mVEyn-0006N9-43 for ged-emacs-devel@m.gmane-mx.org; Tue, 28 Sep 2021 11:25:13 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:49608) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mVExz-0005Nx-VI for emacs-devel@gnu.org; Tue, 28 Sep 2021 11:24:23 -0400 Original-Received: from mail-wr1-x434.google.com ([2a00:1450:4864:20::434]:33498) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1mVExy-0005Ro-3S for emacs-devel@gnu.org; Tue, 28 Sep 2021 11:24:23 -0400 Original-Received: by mail-wr1-x434.google.com with SMTP id t18so58780544wrb.0 for ; Tue, 28 Sep 2021 08:24:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version; bh=s9kA2J4I+mxyQHpR9TBkegb7cPD2Js25Oht2c+JR8NY=; b=P7bWKCLrmT07eWEFJZ0343lEbqEY5E+kKLJv8tEWkoHmy9B7ygSDkbwIypSRK/sDTZ +FbET0c4AuBUzQG2jSW6wiU4/G7JfNsLYAqFsQExjkA2JFe9clUOcWWN7Skd1kADWThM bqkKlx2sQkDlbgtyI/o1wVpgJhTZs50lbwZslRtBuGMU5SRhu754v9drRChAiDIcF2FW yN+8p0qQDZ6ir805K7aqKnJSQ2NlIPpuQsNZn2CXe3/v/oq664W0LDrjo9taz2JtwZq5 LnnhfLm4fYVkYsVeHnritWp/F271R+kzVsKgUs5U9qt6pYmI7C8xOxhtCHolUM9eY9h5 Hslg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:references:date:in-reply-to :message-id:user-agent:mime-version; bh=s9kA2J4I+mxyQHpR9TBkegb7cPD2Js25Oht2c+JR8NY=; b=sWrQq5I1CO26FGTuq9RJ/pPbcXhFHBEWaTFKsQOKey2x3Kdg7V0Bj209XzTyPLmAHq 89u8SfCBE49DVFVO+v1Dl9QGFBCm76cdNXQWt04/m6Lxvf0OOAMek6Iylp3to4htDXST WlYD1729f5yLTOfqj9wRFXaAaMIyZM+kY2u6zJPIVTxyZmkU52JeutUZToN3XXTWqbjk 5Aaw5x9/ogXvejyT7xfApZNQC0ve0l4N2kWkG2dnRABFTHGnTr2kLJpOvXk4lSu9seMZ GF9m3kNeKO/PyNB/DxqrOnSk3KPfEHjypxBJmGSjJ1ejZMutV3s0EHlZD45XhAb7AorP zaFg== X-Gm-Message-State: AOAM5333tSgdx97NXSiTWelUErwgPBNXaF1+6TZlG4TzRyX8EZQd3b9V 2ofls65tuoX+cQYmv74X5UjuPfripHw= X-Google-Smtp-Source: ABdhPJxqqi0lw7zIX8j987nVrE+Auwdoa6D5tdOyoprdl+kYf7+ylY/GxgvpoOeVQDhVf86BGcG/ag== X-Received: by 2002:adf:f583:: with SMTP id f3mr763390wro.116.1632842659813; Tue, 28 Sep 2021 08:24:19 -0700 (PDT) Original-Received: from ars3 (pd95c95b0.dip0.t-ipconnect.de. [217.92.149.176]) by smtp.gmail.com with ESMTPSA id s24sm2868674wmh.34.2021.09.28.08.24.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 28 Sep 2021 08:24:19 -0700 (PDT) In-Reply-To: <20210928080902.GC14380@tuxteam.de> (tomas@tuxteam.de's message of "Tue, 28 Sep 2021 10:09:02 +0200") Received-SPF: pass client-ip=2a00:1450:4864:20::434; envelope-from=arstoffel@gmail.com; helo=mail-wr1-x434.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, 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:275700 Archived-At: On Tue, 28 Sep 2021 at 10:09, wrote: > On Mon, Sep 27, 2021 at 08:52:38PM -0700, Eric Abrahamsen wrote: >> >> On 09/27/21 18:34 PM, Richard Stallman wrote: >> > [[[ To any NSA and FBI agents reading my email: please consider ]]] >> > [[[ whether defending the US Constitution against all enemies, ]]] >> > [[[ foreign or domestic, requires you to follow Snowden's example. ]]] >> > >> > What is a PEG? >> >> A Parsing Expression Grammar: >> https://en.wikipedia.org/wiki/Parsing_expression_grammar >> >> Basically a way of composing a parser out of smaller regexp-like >> expressions. They can be very useful in a wide variety of situations. > > In the Chomsky hierarchy, they live in some funny place between > regular (Type-3) and context free (Type-2). They are strictly > more powerful than regular grammars (but can eat memory for > breakfast [1], but (quoting the Wikipedia ref above: > > "It is an open problem to give a concrete example of a > context-free language which cannot be recognized by a > parsing expression grammar." Perhaps more interesting in practice: a PEG can compute and return a value as it parses the subject string. So one can (easily) write a PEG that recognizes well-formed arithmetic expressions _and_ computes the value of the arithmetic expression along the way. Or a PEG that recognizes email headers and returns those headers as an alist. Regexps usually only produce substrings of the subject string (in Emacs regexps can also call Lisp code, but this is not as general.) [Also note that a PEG defines a parser for a grammar, not just a grammar.] > > I don't know at the moment whether there is a (non-constructive) > proof that CFGs be strictly more expressive than PEGs? > > Cheers > > [1] Memory has become significantly cheaper since Thompson, this > might have a practical significance or not ;-) > > - t