Re: Re: Re parse-result

[Zelphir Kaltstahl <zelphirkaltstahl@gmail.com>]

Hey tomás,

On 1/20/19 9:32 AM, tomas@tuxteam.de wrote:
>>                              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.

Ah right, I forgot that there was one for CFGs too! I think I never
learned that one though. Neither Ogden's (which at least I have heard
of) or Parikh's.

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

Yes, I imagine that to be difficult to express in a grammar. On the
other hand, I know that (for example's sake) ReStructuredText has
arbitrary document internal references, so the sink or target of the
reference needs to be defined somewhere, possibly far away from the
reference itself. I think I am beginning to understand, why the
reference implementation of RST is more "rolled their own" instead of
visibly based on a grammar.

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

I was afraid someone would tell me I have to figure out the grammar
first, in order to judge the language class. :D

> 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.
I always wonder how people know that their parsing approach will be
sufficient. So maybe they do not and simply try it with their favorite
parsing tool.
> OTOH -- all inputs being finite, all languages are regular,
> given enough time and storage :-)
I never thought about it like this. This is kind of funny actually. I
wonder what a "theoretical CS" teaching person would say to that. Maybe
that you still don't know ahead of time (parsing) exactly how long your
input is and that it therefore seems infeasible to construct a correct
grammar for that regular language, so in practice this does not help
you, when looking for a "correct" result.
>> 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

I did not mean to ask here for anyone to solve that one. Really only an
example of where I got stuck because of not knowing things and then
losing motivation.

Anyway, thank you for your reply!

Regards,

Zelphir