From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: tomas@tuxteam.de Newsgroups: gmane.lisp.guile.user Subject: Re: Re parse-result Date: Sun, 20 Jan 2019 09:32:08 +0100 Message-ID: <20190120083208.GA22502@tuxteam.de> 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> NNTP-Posting-Host: ciao.gmane.org Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="yrj/dFKFPuw6o+aM" X-Trace: ciao.gmane.org 1547973155 139457 195.159.176.228 (20 Jan 2019 08:32:35 GMT) X-Complaints-To: usenet@ciao.gmane.org NNTP-Posting-Date: Sun, 20 Jan 2019 08:32:35 +0000 (UTC) User-Agent: Mutt/1.5.21 (2010-09-15) Cc: Guile User To: Zelphir Kaltstahl Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Sun Jan 20 09:32:33 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 1gl8Wu-000aGw-5w for guile-user@m.gmane.org; Sun, 20 Jan 2019 09:32:32 +0100 Original-Received: from localhost ([127.0.0.1]:37058 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gl8X3-00078w-3D for guile-user@m.gmane.org; Sun, 20 Jan 2019 03:32:41 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:50964) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1gl8Wh-00078f-8S for guile-user@gnu.org; Sun, 20 Jan 2019 03:32:20 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1gl8We-0002LE-ND for guile-user@gnu.org; Sun, 20 Jan 2019 03:32:19 -0500 Original-Received: from mail.tuxteam.de ([5.199.139.25]:44994) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1gl8We-0002I8-8K for guile-user@gnu.org; Sun, 20 Jan 2019 03:32:16 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=tuxteam.de; s=mail; h=In-Reply-To:Content-Type:MIME-Version:References:Message-ID:Subject:Cc:To:From:Date; bh=qtlhqq/lrlCtj6JIbcbQqNZp8ezk3AKfCMeghGVWHUY=; b=q2EHOS0gABZ7exCnfK2Ow6TNM3ZVN1QHf2EwN/kJqF+b1ngXDmXBwsnb3d6Xf7xUSy2M119o+oIIfpcBsBtHnaoPsBFwZCewNXdOOSPdzHwWQ522r0i9jJpS0HzOPqAq/aBgtrGJ3+krP/ErkY0Pqk0L9ys9XwznA49Ro/AGdLVWSIgDoH5MCjep4bycQLjBiIIYNXoZyAId8fDhx5P8MD8GZX/OXhLwDQW48BGJFBcIa+m3uLVeQfqBScsfykr6ZEnJMrzarUYbLavBcr7PNyxnALWLS0g8ccv/7NE1BRruAB9yZ+Ahhu1dJdrBAyMu6y9U1ZTNZ+DE7LT3+TqXPA==; Original-Received: from tomas by mail.tuxteam.de with local (Exim 4.80) (envelope-from ) id 1gl8WW-00067h-RP; Sun, 20 Jan 2019 09:32:08 +0100 Content-Disposition: inline In-Reply-To: <41e1f6a3-f849-c823-7f74-a56f68a20feb@gmail.com> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 5.199.139.25 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:15241 Archived-At: --yrj/dFKFPuw6o+aM Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sat, Jan 19, 2019 at 02:23:58PM +0100, Zelphir Kaltstahl wrote: >=20 > On 1/17/19 11:49 AM, tomas@tuxteam.de wrote: [...] > Thanks tom=C3=A1s! >=20 > I know the Chomsky Hierarchy exists for languages and I remember there > was some thing called pumping lemma, which I forgot how to use years ago > anyway and I usually find online proofs difficult to follow, because > they lack the usual "explain for stupid" thoughts, that one has, when > thinking about these things. The one "explain for stupid" I made up for me is that whenever the grammar is too simple, the language becomes boring and starts to "repeat itself". > 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. > 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). 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. 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. OTOH -- all inputs being finite, all languages are regular, given enough time and storage :-) > 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 --yrj/dFKFPuw6o+aM Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iEYEARECAAYFAlxEMggACgkQBcgs9XrR2kbkOQCfb4HVFy265bWZZvF9HVlzwTNz cwkAnR90gDsi+PMyjm2JdN9KRPP+CLZi =dk1Y -----END PGP SIGNATURE----- --yrj/dFKFPuw6o+aM--