From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Zelphir Kaltstahl Newsgroups: gmane.lisp.guile.user Subject: Re: Re: Re parse-result Date: Sun, 20 Jan 2019 12:35:20 +0100 Message-ID: References: <5E629D82-0023-489F-9A0A-63ACF1A520B1@pretty.Easy.privacy> <257748e7-bc56-573d-c691-c1655947be2a@gmail.com> <20190117104910.GB28578@tuxteam.de> <41e1f6a3-f849-c823-7f74-a56f68a20feb@gmail.com> <20190120083208.GA22502@tuxteam.de> NNTP-Posting-Host: ciao.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: ciao.gmane.org 1547984150 231804 195.159.176.228 (20 Jan 2019 11:35:50 GMT) X-Complaints-To: usenet@ciao.gmane.org NNTP-Posting-Date: Sun, 20 Jan 2019 11:35:50 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.2.1 Cc: Guile User To: tomas@tuxteam.de Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Sun Jan 20 12:35:47 2019 Return-path: Envelope-to: guile-user@m.gmane.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.84_2) (envelope-from ) id 1glBOC-000yHG-2Y for guile-user@m.gmane.org; Sun, 20 Jan 2019 12:35:44 +0100 Original-Received: from localhost ([127.0.0.1]:38598 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1glBOK-0000bW-VC for guile-user@m.gmane.org; Sun, 20 Jan 2019 06:35:52 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:52812) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1glBNz-0000bN-Hf for guile-user@gnu.org; Sun, 20 Jan 2019 06:35:32 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1glBNw-0001UD-AQ for guile-user@gnu.org; Sun, 20 Jan 2019 06:35:30 -0500 Original-Received: from mail-lj1-x22f.google.com ([2a00:1450:4864:20::22f]:33172) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1glBNv-0001PG-OM for guile-user@gnu.org; Sun, 20 Jan 2019 06:35:28 -0500 Original-Received: by mail-lj1-x22f.google.com with SMTP id v1-v6so15211066ljd.0 for ; Sun, 20 Jan 2019 03:35:24 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:to:cc:references:from:message-id:date:user-agent :mime-version:in-reply-to:content-transfer-encoding:content-language; bh=bT1Giq/EiQNHneNTqEvKAvuXphn7QDWV3iEq+oVfPUU=; b=SbjjnIYxwLOyVS2xrsfI8TcVci3hbfOk0vJ4eAz2ZC4IIOs0kY7S2ilt+jw9044LWN eqovw6KoKkddJot8dZbMHfMbMXujjflm8gJ0NMkwBhl4cIXNEBGmo8R0GLnW7OYNWW8p fsOuHiVGn5lz7nICMGdP07bUWBrw0P9cf9vCnBQA16RzO9xYZp7lJna36NXElx92nAIz QJyipI9d/d3ArJz926+M0XpA25MsHJSIx3/09LexO5d0XVM+KAqWvtcWjeN1eLX+cbbe d3somcLIF6xpD55P5uJLsxR4prXjg//oN7wdTBEcgmVNrOiZyyXGtoNxxLQbJU+MZtr3 1WTA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:cc:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-transfer-encoding :content-language; bh=bT1Giq/EiQNHneNTqEvKAvuXphn7QDWV3iEq+oVfPUU=; b=osghistIoAKfRBfGHci32TuU7KyYMbpuIs1dFY6nkpuYzbl1bKN4j36AE599S1T3EF 4PWu+JnoUHC5Wxo5UXcm9YTpVrPTTnwAtqWJXVPh9ARv1nkSmON797T3+SXZ+OBcuvjk 0zduAu7hkfdKhQxImm3kvr0z/Wuh3GtQYYw2RQQGvPK50HhKsw2mR0r5KnAolCBAkv1z +/3lcXTWzWSbH/8f1ifkax1bbAUSsGsvZt+wd3a6W9Xz1yfJ1oce01bVae+YWaDRQQFo CpjzS46REPiDdFj9GZJKL8KqJIq13WfudnOHlVEzUllx+PEtHIYSIz7Q4wMnIPxLCqWg kWHA== X-Gm-Message-State: AJcUukfErsRLWMdoaOJp9FUQXU+J9D1wZ1m8E8DG7xhz8yZH3SqhAnci BJlDORbaRgNrdVuykJNEQ6kezytynBE= X-Google-Smtp-Source: ALg8bN59+UttXWxM906GuLRST6XJcDzboflfa79e5mxg7aOSMdNlYne7+Og5gp9dkgdzSY8U2KurKw== X-Received: by 2002:a2e:8045:: with SMTP id p5-v6mr15310475ljg.87.1547984122445; Sun, 20 Jan 2019 03:35:22 -0800 (PST) Original-Received: from [10.10.0.13] ([185.65.135.173]) by smtp.googlemail.com with ESMTPSA id u65sm1791098lff.54.2019.01.20.03.35.21 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 20 Jan 2019 03:35:21 -0800 (PST) In-Reply-To: <20190120083208.GA22502@tuxteam.de> Content-Language: en-US X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2a00:1450:4864:20::22f 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:15242 Archived-At: Hey tomás, On 1/20/19 9:32 AM, tomas@tuxteam.de wrote: >> My best bet for applying such a thing would >> be to search through old documents from university [...] But this >> is also only to prove that a language is not regular, if I recall >> correctly. > There's one for regular languages and one for context-free. The > "repeating itself" in CFGs is a bit more elaborate (it's pairs > that repeat, think parentheses :-) but the gist is similar. Ah right, I forgot that there was one for CFGs too! I think I never learned that one though. Neither Ogden's (which at least I have heard of) or Parikh's. >> I think in a practical setting (for example: "I want to write >> a parser for ReStructuredText! Can I use parser combinators?") the >> problem is, figuring out whether the real language is in a specific >> class of languages and then understanding, whether or not the parsing >> tool I want to use is able to parse such language. > First you gotta have a grammar. There's a lot of fudging in that > part (you can shift things to or from the "semantic part": e.g. > you might want to express in your grammar that a variable has to > have a "previous" declaration, but nobody in her right mind tries > to do that). Yes, I imagine that to be difficult to express in a grammar. On the other hand, I know that (for example's sake) ReStructuredText has arbitrary document internal references, so the sink or target of the reference needs to be defined somewhere, possibly far away from the reference itself. I think I am beginning to understand, why the reference implementation of RST is more "rolled their own" instead of visibly based on a grammar. > Then you have to look at the grammar and see whether it is > context-free. As above, you can try to fudge things a bit to > "make it so" -- after all, you have a (nearly, the tape and > your patience being limited) Turing-complete beast under your > belt. I was afraid someone would tell me I have to figure out the grammar first, in order to judge the language class. :D > In practice, most libraries and tools cheat, so most regular > expression machines offer things which take them beyond regular > languages (and you pay the price in possibly exponential run > time, but us programming folks love that risk ;-) -- and most > (sub-) CFG machineries cheat in similar ways, but that makes > them interesting. >> Is it trial and error in the end? > That's our trade it seems :-) Have a look at this one: > > https://en.wikipedia.org/wiki/Context-free_language#Decidability > > to get a "feel" on how fractal-y the limits are. I always wonder how people know that their parsing approach will be sufficient. So maybe they do not and simply try it with their favorite parsing tool. > OTOH -- all inputs being finite, all languages are regular, > given enough time and storage :-) I never thought about it like this. This is kind of funny actually. I wonder what a "theoretical CS" teaching person would say to that. Maybe that you still don't know ahead of time (parsing) exactly how long your input is and that it therefore seems infeasible to construct a correct grammar for that regular language, so in practice this does not help you, when looking for a "correct" result. >> Here is an example of such a case from some time ago, when I wanted to >> do some parsing in Rust, because I could not use ReStructuredText in a >> Rust project: https://github.com/flying-sheep/rust-rst/issues/4 (This >> one actually mentions PEG parsing.) > Thanks, and I promise I'll be having a look at this one. I just > Should Be Doing Something Different (TM) at the moment, so it > might take a couple of days. > > It just happens that I am doing some parsing stuff at the moment > (an archeological language, using Python, alas, and their pyparsing > combinator library. I'd rather play with Guile, but perhaps I can > learn things to steal them later ;-) > > Cheers > -- t I did not mean to ask here for anyone to solve that one. Really only an example of where I got stuck because of not knowing things and then losing motivation. Anyway, thank you for your reply! Regards, Zelphir