From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Alexandr Karbivnichyi Newsgroups: gmane.emacs.devel Subject: Re: Using the wisent parser-generator, as it creates faster parsers Date: Mon, 26 Dec 2022 20:13:27 +0200 Message-ID: <27990365a2b32aaa3f76fe8f0922a8481d953ef6.camel@gmail.com> References: <8075de284038bb4970568bb856656cbc88ded050.camel@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="24587"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Evolution 3.46.2 Cc: Eric Ludlam , emacs-devel To: Lynn Winebarger Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon Dec 26 19:14:11 2022 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 1p9rzG-00068p-NI for ged-emacs-devel@m.gmane-mx.org; Mon, 26 Dec 2022 19:14:10 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1p9ryf-0004Vk-Po; Mon, 26 Dec 2022 13:13:33 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1p9rye-0004Vb-Fd for emacs-devel@gnu.org; Mon, 26 Dec 2022 13:13:32 -0500 Original-Received: from mail-ej1-x630.google.com ([2a00:1450:4864:20::630]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1p9ryc-0003D2-Ld for emacs-devel@gnu.org; Mon, 26 Dec 2022 13:13:32 -0500 Original-Received: by mail-ej1-x630.google.com with SMTP id qk9so27290981ejc.3 for ; Mon, 26 Dec 2022 10:13:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:user-agent:content-transfer-encoding:references :in-reply-to:date:cc:to:from:subject:message-id:from:to:cc:subject :date:message-id:reply-to; bh=l5QMjGSbtOsQRnS6md7jiAcrtn/d7KYk0cnrPOSpP5Q=; b=PdEkK5sh2et9JTn4+CMpGC0LIk50AKmVv/kUe6V9cg/1iZx72rBk7ZNxS1aROBzrDo szWLYSG/LVYRy/FXZuRNvEbsseS80Imy4VvTcixxqljDU5spMxi48EByt5e3k3lcq2Td biircniOZN/vslZYKCwuC3LXuWWJWBImq4n/unCpa2P/E5UkA+Ue63vuKMx7tS+MVaZl OJn8q1FK9InkMFjBMTT0r/tQWIINUrItxoRGXbIGAvN3zsT+uYPLi2oP74EnI/l/NDiH 4YlKGI6sUUnIxKybcwmOposXp5TMtnQh8vamow4C8Vf8AbjGiJHWWPHa7vPbEQeKw+Ih tNaw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=mime-version:user-agent:content-transfer-encoding:references :in-reply-to:date:cc:to:from:subject:message-id:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=l5QMjGSbtOsQRnS6md7jiAcrtn/d7KYk0cnrPOSpP5Q=; b=i0MHD8dXHQUGNoQnHUsLmYysOgOOujTJjrAasJEror1YrcZDvRliTLdFy3TIfD+LP5 C/+Ui+zo4nviY8PVDpuYPhYagh9LryUM9RX9sqjDE+Z92O/X0ncz1PdLC/e99Wj/Y7BT PCh6ncEGYImSsR6AzmM2k3ZItyJIYYYFQcDBk8XUvphGvnvqyMQ13EJzLey1oc0u0yQs 5tNab/KdubNCE3po93cCFcniyu9hI7jxL7ap4+eI/6x9VcJTHk/MPiUOOCl8zb3Joshy gkMZbYbEMm3JA/bfkdwFebttkZUhQbVIz8tX+qBjDH7qoiTnsm/byiwtY3olNLujMLX1 QJvA== X-Gm-Message-State: AFqh2ko8Ua+PUWeNr0EdyumsBxhSn4FVuqszXMbmiW3oYRU98/xnmDGe KWXr6pq2vVgyeTOKkbTAOuE= X-Google-Smtp-Source: AMrXdXsZBj3uAEUAOj8wulsYKmL9O8B4CA5G2LRO/vpPJTXXap1NiPuD03R+Kg4NhyHzcECYi/y+8A== X-Received: by 2002:a17:906:6a1a:b0:7b9:ee36:6153 with SMTP id qw26-20020a1709066a1a00b007b9ee366153mr21204688ejc.2.1672078408966; Mon, 26 Dec 2022 10:13:28 -0800 (PST) Original-Received: from [192.168.0.103] ([89.28.47.80]) by smtp.gmail.com with ESMTPSA id a18-20020a17090682d200b007be301a1d51sm5027362ejy.211.2022.12.26.10.13.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 26 Dec 2022 10:13:28 -0800 (PST) In-Reply-To: Received-SPF: pass client-ip=2a00:1450:4864:20::630; envelope-from=ambulajan@gmail.com; helo=mail-ej1-x630.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.29 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-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.devel:301939 Archived-At: On Mon, 2022-12-26 at 08:54 -0500, Lynn Winebarger wrote: > On Sun, Dec 25, 2022, 11:03 PM wrote: >=20 > I don't agree - conflicts detected by the parser generator indicate > that distinct ASTs map to the same text, at least according to the > reduction method being used.=C2=A0 I like using LR derivations (including > ones produced by LALR) because of the bottom-up recognition of > grammar symbols.=C2=A0 True for LALR parsers. Tried-and-tested system, for industrial compilers built on a formal standard with simple grammar that doesn't change often. I explored parsing from time to time having in mind an idealistic view of a system where given some grammar a lot of automatic features appear almost ready for use. So AST. It's required unambiguous to generate assembler mnemonics. It's unavoidable in LALR to build AST in order to make any sense of the parse. Earley parser creates a state(list of grammar rules) at each scan step(shift). I discovered that it's all what's needed at this stage in the case when I don't intent to create executable. The state contains all current grammar rules with a "dot" inside them(rule's progress at point), from all possible parse trees. It's enough to compute indentation, create smart completion, compose explicative error messages. The beauty of Early's algorithm is in possibility to write some grammar and then keeping in mind the algorithm to write states by hand in a text file for each token. The parser concept prints those states in Message buffer, provides human readable interface. It gives an analogy of 'syntax-ppss' function(elisp reader) but with full grammar contex.=20 After all, the possibility of invoking one parser with different lexers turns out to be an interesting idea. For different purposes. Some tokens can be just blocks of text, either not contributing to the current purpose or put aside to be reparsed recursively when contents of that block-token change while editing. > The above is not to discourage adding Earley parsing to the toolkit.=C2= =A0 > However, just defers the to resolution of ambiguities to your code > rather than by refining your grammar. For specifying a programming > language, this seems like inviting difficult to debug cases to me.=C2=A0= =C2=A0 And reciprocally not to discourage usage of existing tried-and-tested parsers. Semantic allows that a parser may(should) be a separate library. All in all, it's Emacs. GLR algorithm doesn't reject grammar with conflicts and doesn't use defaults to resolve. It's a LALR parser that starts parallel branches for conflicts. Then after subsequent shifts only one branch survives - conflict is resolved. The problem is that all parsing branches invoke actions, all actions must be cached somehow during parsing and only those actions of the survived branch to be included in parser's output. In any case, there are no other tools in existence than Emacs that would allow even reasoning about these ideas implying their practical implementation.