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