Re: Re parse-result

[tomas]

On Sat, Jan 19, 2019 at 02:23:58PM +0100, Zelphir Kaltstahl wrote:
> 
> On 1/17/19 11:49 AM, address@hidden wrote:

[...]

> 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.

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

signature.asc
Description: Digital signature