4 ms·

Justine gets very close to the hairiest parsing issue in any language without encountering it: Perl's syntax is undecidable, because the difference between tre

Justine gets very close to the hairiest parsing issue in any language without encountering it: Perl's syntax is undecidable, because the difference between treating some characters as a comment or as a regex can depend on the type of a variable that is only determined e.g. based on whether a search for a Collatz counterexample terminates, or just, you know, user input. https://perlmonks.org/?node_id=663393 https://perlmonks.org/?node_id=663393 C++ templates have a similar issue, I think.

fanf2 2y ago
I think possibly the most hilariously complicated instance of this is in perl’s tokenizer, toke.c (which starts with a Tolkien quote, 'It all comes from here, the stench and the peril.' — Frodo). There’s a function called intuit_more which works out if $var[stuff] inside a regex is a variable interpolation followed by a character class, or an array element interpolation. Its result can depend on whether something in the stuff has been declared as a variable or not. But even if you ignore the undecidability, the rest is still ridiculously complicated. https://github.com/Perl/perl5/blob/blead/toke.c#L4502 https://github.com/Perl/perl5/blob/blead/toke.c#L4502
- ufo 2y ago
  Wow. I wonder how that function came to be in the first place. Surely it couldn't have started out that complicated?
_cbsz 2y ago
> C++ templates have a similar issue TIL! I went and dug up a citation: https://blog.reverberate.org/2013/08/parsing-c-is-literally-undecidable.html https://blog.reverberate.org/2013/08/parsing-c-is-literally-...
layer8 2y ago
How could a search for a Collatz counterexample possibly terminate? ;)
chubot 2y ago
Yup, bash and GNU Make have the same issue as Perl does, and I mention the C++ issue here too: Parsing Bash is Undecidable - https://www.oilshell.org/blog/2016/10/20.html https://www.oilshell.org/blog/2016/10/20.html I remember a talk from Larry Wall on Perl 6 (now Raku), where he says this type of thing is a mistake. Raku can be statically parsed, as far as I know.
- jwilk 2y ago
  Parsing POSIX shell in undecidable too: https://news.ycombinator.com/item?id=30362718 https://news.ycombinator.com/item?id=30362718
  - chubot 2y ago
    Yes, good point -- aliases makes parse time depend on runtime. That is mentioned in Morbig: A static parser for POSIX shell - https://scholar.google.com/scholar?cluster=15754961728999604986&hl=en&as_sdt=0,39 https://scholar.google.com/scholar?cluster=15754961728999604... (at the time I wrote the post about bash, I hadn't implemented aliases yet) But it's a little different since it is an intentional feature, not an acccident. It's designed to literally reinvoke the parser at runtime. I think it's not that good/useful a feature, and I tend to avoid it, but many people use it.

fanf2 2y ago

I think possibly the most hilariously complicated instance of this is in perl’s tokenizer, toke.c (which starts with a Tolkien quote, 'It all comes from here, the stench and the peril.' — Frodo). There’s a function called intuit_more which works out if $var[stuff] inside a regex is a variable interpolation followed by a character class, or an array element interpolation. Its result can depend on whether something in the stuff has been declared as a variable or not. But even if you ignore the undecidability, the rest is still ridiculously complicated. https://github.com/Perl/perl5/blob/blead/toke.c#L4502 https://github.com/Perl/perl5/blob/blead/toke.c#L4502

ufo 2y ago
Wow. I wonder how that function came to be in the first place. Surely it couldn't have started out that complicated?

_cbsz 2y ago

> C++ templates have a similar issue TIL! I went and dug up a citation: https://blog.reverberate.org/2013/08/parsing-c-is-literally-undecidable.html https://blog.reverberate.org/2013/08/parsing-c-is-literally-...

layer8 2y ago

How could a search for a Collatz counterexample possibly terminate? ;)

chubot 2y ago

Yup, bash and GNU Make have the same issue as Perl does, and I mention the C++ issue here too: Parsing Bash is Undecidable - https://www.oilshell.org/blog/2016/10/20.html https://www.oilshell.org/blog/2016/10/20.html I remember a talk from Larry Wall on Perl 6 (now Raku), where he says this type of thing is a mistake. Raku can be statically parsed, as far as I know.

jwilk 2y ago
Parsing POSIX shell in undecidable too: https://news.ycombinator.com/item?id=30362718 https://news.ycombinator.com/item?id=30362718
- chubot 2y ago
  Yes, good point -- aliases makes parse time depend on runtime. That is mentioned in Morbig: A static parser for POSIX shell - https://scholar.google.com/scholar?cluster=15754961728999604986&hl=en&as_sdt=0,39 https://scholar.google.com/scholar?cluster=15754961728999604... (at the time I wrote the post about bash, I hadn't implemented aliases yet) But it's a little different since it is an intentional feature, not an acccident. It's designed to literally reinvoke the parser at runtime. I think it's not that good/useful a feature, and I tend to avoid it, but many people use it.