On 1/17/19 11:49 AM, to...@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
