4 ms·

A quick Google doesn't turn up any pages stating that parsing Perl and CL is undecidable. Can you provide a reference?

nkurz 16y ago
I don't know about CL, but it is commonly believed that Perl cannot be parsed by anything except Perl. I'm not sure about the nuances between "undecidable" and "cannot be parsed without execution", but this page seems relevant: Perl Cannot Be Parsed: A Formal Proof http://www.perlmonks.org/?node_id=663393 http://www.perlmonks.org/?node_id=663393
- deleted 16y ago
  [deleted]
- swolchok 16y ago
  Oops! I meant that Google didn't turn up anything for TeX, not Perl. The Perl stuff is indeed well known.
dfox 16y ago
There is large difference between "undecidable" and "cannot be parsed without execution". It has to do with the fact that in each of these three cases the syntax can be modified by running code, and that execution is interleaved with parsing. In CL you can essentially add arbitrary right sides to few production rules of it's grammar, and also meaning of many tokens (symbols, numbers and differentiating between symbols and numbers) is dependent on runtime state of implementation which can be modified by code being parsed. In TeX you can partially alter rules of tokenization (by redefining character categories). And in the TeX case it also depends on what you expect as output of parsing, if you want some meaningful AST, it is even more complex (and probably impossible). Because even if you would remove the ability to redefine character categories, you would still be able to only get stream of tokens without clear semantic meaning. But whole this discussion is mostly theoretical, because for reasonable inputs (like LaTeX), parser can effectively guess. Also, in CL cases many of these problems are solved by various conventions (like having most of relevant state consistent for whole file and specified in comment that is readable by said tools).

nkurz 16y ago

I don't know about CL, but it is commonly believed that Perl cannot be parsed by anything except Perl. I'm not sure about the nuances between "undecidable" and "cannot be parsed without execution", but this page seems relevant: Perl Cannot Be Parsed: A Formal Proof http://www.perlmonks.org/?node_id=663393 http://www.perlmonks.org/?node_id=663393

deleted 16y ago
[deleted]
swolchok 16y ago
Oops! I meant that Google didn't turn up anything for TeX, not Perl. The Perl stuff is indeed well known.

dfox 16y ago

There is large difference between "undecidable" and "cannot be parsed without execution". It has to do with the fact that in each of these three cases the syntax can be modified by running code, and that execution is interleaved with parsing. In CL you can essentially add arbitrary right sides to few production rules of it's grammar, and also meaning of many tokens (symbols, numbers and differentiating between symbols and numbers) is dependent on runtime state of implementation which can be modified by code being parsed. In TeX you can partially alter rules of tokenization (by redefining character categories). And in the TeX case it also depends on what you expect as output of parsing, if you want some meaningful AST, it is even more complex (and probably impossible). Because even if you would remove the ability to redefine character categories, you would still be able to only get stream of tokens without clear semantic meaning. But whole this discussion is mostly theoretical, because for reasonable inputs (like LaTeX), parser can effectively guess. Also, in CL cases many of these problems are solved by various conventions (like having most of relevant state consistent for whole file and specified in comment that is readable by said tools).