From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: John Cowan Newsgroups: gmane.lisp.guile.user Subject: Re: Re parse-result Date: Thu, 17 Jan 2019 14:47:59 -0500 Message-ID: References: <5E629D82-0023-489F-9A0A-63ACF1A520B1@pretty.Easy.privacy> <257748e7-bc56-573d-c691-c1655947be2a@gmail.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" X-Trace: blaine.gmane.org 1547755163 4863 195.159.176.226 (17 Jan 2019 19:59:23 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Thu, 17 Jan 2019 19:59:23 +0000 (UTC) Cc: Guile User To: Zelphir Kaltstahl Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Thu Jan 17 20:59:19 2019 Return-path: Envelope-to: guile-user@m.gmane.org Original-Received: from lists.gnu.org ([209.51.188.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1gkDot-000179-Fe for guile-user@m.gmane.org; Thu, 17 Jan 2019 20:59:19 +0100 Original-Received: from localhost ([127.0.0.1]:54196 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gkDr0-0007o8-M2 for guile-user@m.gmane.org; Thu, 17 Jan 2019 15:01:30 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:38328) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gkDeC-0005VO-1s for guile-user@gnu.org; Thu, 17 Jan 2019 14:48:17 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1gkDeB-0005mb-07 for guile-user@gnu.org; Thu, 17 Jan 2019 14:48:16 -0500 Original-Received: from mail-wm1-x331.google.com ([2a00:1450:4864:20::331]:33950) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1gkDeA-0005js-Eh for guile-user@gnu.org; Thu, 17 Jan 2019 14:48:14 -0500 Original-Received: by mail-wm1-x331.google.com with SMTP id y185so1843704wmd.1 for ; Thu, 17 Jan 2019 11:48:13 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ccil-org.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=FkRHQvwtINj4+0rdMg4ATq1JpIwjPO51A5BhbovIc6U=; b=I2uBvOUWYUKKq/HyW8Y/sPgEt3kRt5DOgPMGOTmc8sX5pSN84wUWma4h+26XEAmtG1 0ElZl9xQc7+1sGNyyO3wMRtiSsq+KDXOalHUDgM6deyUezQo9bEKRcTYEbx7VisjDcG8 pVZ18dexxx3e9KLLSPmpzT8iLw551NN4hQM2aO9da3r+wx4HH+XvdEiqG7EP4N2neWWq Yns6p4GqkGT6Rj6h+y60irrnVwQSxa3m2ueZRvKjwysmtXw81zR9HqaWygR5MpC4FgO2 ijmk4kexR2WKyvAoIrWFVA9aH7UE3+RV/Pjc94GC9eudf09Vz2rGAB8XgAnc4myBIuCo SGwQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=FkRHQvwtINj4+0rdMg4ATq1JpIwjPO51A5BhbovIc6U=; b=f8m69aWNC0uGjUbZRDRpexgiScgl2X1z3F8yFyFEx2RPN5P6d3bfF80XbCvz65fW7k 5fRIJfrC069zGRlOerZc9Wc/fEJHR3ngYi3Hais/1+LituwJk3FRRRUfrfoSm5OJaCG8 iBzNcNaF42zVF1fxhqW1l2DzugbWQmpcpO1wJAfTlND/6BB+OZ2P45B5T0Bgo2MZmzYB sYXHEaUPriRBkOQSPsj8v3iiuqs2onz9HGjF8SXJlxBX07ZVG5CZMaB1+34x6dbsxmvp HJmYZ5CrjinWsyR+f2LpFqEK3o6jqkSADJ+YO/sznyH9shKpsAIQxFo/df2tNx/h8NBK 2fqA== X-Gm-Message-State: AJcUukfjB2w9lRSa5G6fargA7dkS00yXfiFx5puNe41gRVVZPfXz8Pn6 SM/JNQulQNcefBnjD4HU/SAjhvb4KOFzbpZ5C9fcRw== X-Google-Smtp-Source: ALg8bN7FDBHSPlB+3fpcmcoolXpxaUjSEGslA2MmAtEyc9J96WUDQQIcNiLOekmY7+7ivkYz/6WV/sWENb6DbpTYMLI= X-Received: by 2002:a1c:8f41:: with SMTP id r62mr12457435wmd.141.1547754491057; Thu, 17 Jan 2019 11:48:11 -0800 (PST) In-Reply-To: <257748e7-bc56-573d-c691-c1655947be2a@gmail.com> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:1450:4864:20::331 X-Content-Filtered-By: Mailman/MimeDel 2.1.21 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Original-Sender: "guile-user" Xref: news.gmane.org gmane.lisp.guile.user:15231 Archived-At: On Thu, Jan 17, 2019 at 2:56 AM Zelphir Kaltstahl < zelphirkaltstahl@gmail.com> wrote: For example, what is the difference > between PEG parsing and parser combinators? > Both of them do top-down parsing (try to match the top-level grammar rule, which is done by trying to match the lower-level rules which make it up, and so on until we get down to single tokens. They differ in the amount of lookahead that's provided. Parser combinators are a facade over recursive-descent parsing, where you write a procedure corresponding to each rule in the parser, and you can only look ahead one token to guide parsing. This is known as LL(1) parsing. It's very easy to write these procedures, so you don't really need an engine like yacc to do the job. One character of lookahead isn't usually enough, so there is a lower-level lexer that uses (typically) regular expressions to aggregate things like numbers and identifiers into single parsing tokens. PEG parsing allows *infinite* lookahead, all the way to the end of the input. However, it memoizes the results of parsing to avoid reparsing repeatedly. To make this possible, alternatives are ordered: instead of rules like A | B, where the first token has to be enough to tell you if you have an A or a B, you have rules like A / B, which means "assume it's an A, and only if it fails, assume it's a B". If A and B overlap, non-PEG parsing has to treat A | B as a grammar ambiguity and recover, but A / B is never ambiguous. -- John Cowan http://vrici.lojban.org/~cowan cowan@ccil.org You cannot enter here. Go back to the abyss prepared for you! Go back! Fall into the nothingness that awaits you and your Master. Go! --Gandalf