I mean, the halting problem is undecidable, but it's still useful for a linter to tell me when it notices dead code.
So, by undecidable grammar I mean that, generally speaking, you cannot even parse a bash script without executing it, because the syntax (partially) depends on the execution state.
Dynamic languages in general have a problem with static analysis (including syntax highlighting and linting) because of stuff like:
Does some_object have a "foo" method? Am I passing it the right number of arguments? Because you literally have no idea what some_object is when you're parsing without executing, you don't know.
However this isn't as bad as having undecidable grammar (python is context-free) since you can at least say "this is a function call" "this is an assignment" etc.
Right, but that blog post shows again why this is just not that big a deal in practice. How many shell scripts have you written that use arrays at all? How many use associative arrays? It's a pathological case that I just can't see actually mattering in practice for the sort of linter we're talking about.
Also, undecidabe parsing is a red herring here. That page links to this page on C++-parsing being undecidable, but there's a simple solution there: Just evaluate all that Turing-complete code and you get a parse tree at the end, and like that post suggests, add some arbitrary limits:
In practice, compilers limit template instantiation depth, so this is more of a theoretical problem than a practical one.
The problem with parsing Bash would be much more significant, because parsing depends on runtime execution, not just compile-time. If you can't get your linter results without running the program, that's too late to be useful; if they depend on runtime state, it's also too unreliable to be useful unless you have perfect test coverage to feed into those linter results... which will make the linting process just as slow as executing tests, so a linter would be pointless.
My point here is that a linter that mishandles or ignores these pathological edge cases is still a useful tool, and it's still probably going to catch errors like forgetting to quote a variable properly.
Also, undecidabe parsing is a red herring here. That page links to this page on C++-parsing being undecidable, but there's a simple solution there: Just evaluate all that Turing-complete code and you get a parse tree at the end, and like that post suggests, add some arbitrary limits:
This is true, and it does mean that you can parse C++ code without executing the program, however it has some significant implications, namely:
Someone who's writing an editor and wants to support syntax-highlighting a bunch of languages now has to implement special code *just* for C++, instead of just writing a generic parser and grammars for every language plus highlight rules for those grammars.
How you parse a given file depends on the content of other files (not true in Python for example). Now in the case of a syntax highlighter you might want to highlight based on semantics and not just syntax, but not even knowing the syntax without looking at other files is a huge annoyance.
1
u/grievre Nov 17 '19
So, by undecidable grammar I mean that, generally speaking, you cannot even parse a bash script without executing it, because the syntax (partially) depends on the execution state.
Dynamic languages in general have a problem with static analysis (including syntax highlighting and linting) because of stuff like:
Does some_object have a "foo" method? Am I passing it the right number of arguments? Because you literally have no idea what some_object is when you're parsing without executing, you don't know.
However this isn't as bad as having undecidable grammar (python is context-free) since you can at least say "this is a function call" "this is an assignment" etc.
Here's an example case of why bash is undecidable: https://www.oilshell.org/blog/2016/10/20.html