Re: Re parse-result

[Zelphir Kaltstahl <zelphirkaltstahl@gmail.com>]

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