From: Zelphir Kaltstahl <zelphirkaltstahl@gmail.com>
To: tomas@tuxteam.de
Cc: Guile User <guile-user@gnu.org>
Subject: Re: Re parse-result
Date: Sat, 19 Jan 2019 14:23:58 +0100 [thread overview]
Message-ID: <41e1f6a3-f849-c823-7f74-a56f68a20feb@gmail.com> (raw)
In-Reply-To: <20190117104910.GB28578@tuxteam.de>
On 1/17/19 11:49 AM, tomas@tuxteam.de wrote:
> On Thu, Jan 17, 2019 at 08:43:01AM +0100, Zelphir Kaltstahl wrote:
>
>>> I am still unsure about the theoretical CS stuff: What kind of parsers
>>> one can possibly write with parser combinators [...]
> [...]
>
>>> Have you looked at the PEG parser recently added to guile? It does
>>> everything the combinators do with an added compressor.
>>> Its quite powerful and seems to work well.
>>> --
>>> Sent from my p≡p for Android.
>> Hi Swedebugia,
>>
>> I did not notice a PEG parser has been added. How did you notice this?
>> Maybe there is another blog for new additions to Guile?
>>
>> Do you know a good text, which explains differences between the
>> different approaches to parsing? For example, what is the difference
>> between PEG parsing and parser combinators? There seems to be a whole
>> jungle of approaches to parsing out there, including parser generators,
>> which I believe take a grammar of certain kind and produce a parser from
>> that. I am never sure what languages I can parse using what approach.
> I repeat myself, but I can only recommend the Wikipedia articles on that
> topic. I'd start with the Chomsky hierarchy, which provides a nice map
> for the terrain:
>
> https://en.wikipedia.org/wiki/Chomsky_hierarchy
>
> At its bottom there is a transcluded template which gives an overview
> of the kinds of languages out there and the types of "machines". You
> can jump directly to that template:
>
> https://en.wikipedia.org/wiki/Template:Formal_languages_and_grammars
>
> which is full of links :-)
>
> PEGs are a bit of a freak within the Chomsky hierarchy, strictly
> superior than regular languages (Type-3, think regexps) but inferior
> to parsers doing fully general context-free (Type-2), like Earley
> and CYK (which are worst-case about n^3 in the input's size).
>
> OTOH, PEGs can be exponential in time (or in space, if you use
> memoizing ("Packrat" parser) in some pathological cases.
>
> Here you can read about thw relationship between PEGs and recursive
> descent parsers (which those combinator thingies are, after all):
>
> https://en.wikipedia.org/wiki/Parsing_expression_grammar#Implementing_parsers_from_parsing_expression_grammars
>
> Enjoy the landscape...
>
> Cheers
> -- tomás
Thanks tomás!
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. My best bet for applying such a thing would
be to search through old documents from university and hope that
somewhere I wrote down all the thoughts in very detailed manner,
including treatment of every little "but what if …?" thought. But this
is also only to prove that a language is not regular, if I recall
correctly. 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.
Is it trial and error in the end?
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.)
Anyway, maybe I can fresh up my knowledge a little through the articles
you linked.
Regards,
Zelphir
next prev parent reply other threads:[~2019-01-19 13:23 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <mailman.109.1547658023.1050.guile-user@gnu.org>
2019-01-16 20:31 ` Re: parse-result (Catonano) Zelphir Kaltstahl
2019-01-16 21:47 ` tomas
2019-01-17 7:16 ` swedebugia
2019-01-17 7:43 ` Re parse-result Zelphir Kaltstahl
2019-01-17 9:56 ` swedebugia
2019-01-17 10:49 ` tomas
2019-01-19 13:23 ` Zelphir Kaltstahl [this message]
2019-01-20 8:32 ` tomas
2019-01-20 11:35 ` Zelphir Kaltstahl
2019-01-17 19:47 ` John Cowan
2019-01-16 20:34 ` Tangerine Edition penultimate report: how I voted, how you're, voting (John Cowan) Zelphir Kaltstahl
2019-01-20 2:24 ` John Cowan
2019-01-20 12:02 ` Arne Babenhauserheide
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/guile/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=41e1f6a3-f849-c823-7f74-a56f68a20feb@gmail.com \
--to=zelphirkaltstahl@gmail.com \
--cc=guile-user@gnu.org \
--cc=tomas@tuxteam.de \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).