0
$\begingroup$

I'd read around on the interwebs, and a lot of the text indicated that many programming languages are generated by a context-free grammar, which leads me to 2 questions:

Doesn't variable scoping require a context-sensitive grammer? Particularly, I'm thinking of the following valid C code:

int main(){
    int count=0;
    count++;
    return count;
}

As opposed to the following invalid C code:

int main(){
    count++;
    int count=0;
    return count;
}

There could also be some other stuff involving namespaces and classes for C++, or the '.' operator for C structs, for example. I get the impression that, as a result, C (and various descendents) does (do) have context-sensitive aspects (though this may only be partial context-sensitivity). Thus question 1:

Is it correct to say that C and some derivative languages, as well as some other languages, can only be generated by grammars with a minimum of context-sensitivity?

Secondly is there a relationship between language class and grammar class?

Particularly, I'm thinking of the language BrainF*** when I ask, since its syntax is clearly generated by a context-free grammar, yet its implementation is turing complete (assuming an implementation with an infinite tape). Does this mean that there are languages that have regular grammars, yet are turing complete?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
3
$\begingroup$

The issue is where you want to draw the line for what is considered "syntax". Sure, variable scoping typically requires context-sensitivity, but that doesn't need to be handled by the parser. The parser could just parse the syntax allowing out-of-scope variables, and a follow-on pass could check for out-of-scope errors. In practice, many real implementations of parser for real languages are context-sensitive, but this is handled in an ad-hoc manner by sharing state between productions and allowing "actions" to be attached to context-free productions. In particular, few (no?) languages use general-purpose context-sensitive parsing approaches. In fact, few uses general-purpose context-free parsing approaches. Instead, tooling for potentially limited classes of context-free grammars is used and, as mentioned, ad-hoc "semantic actions" lead to the parser actually being context-sensitive but this done in a way that is not captured by the context-free grammars that putatively describe the language.

In other words, a context-free grammar for a language often describes a larger language than what is actually accepted. But rejecting a program after parsing it for out-of-scope variables, say, is no different than rejecting it for having a type error. Type checking is almost never done while parsing. So what checks are done while parsing or later is usually done as a matter of convenience, and many aren't nicely described by a grammar.

The grammar complexity of the syntax has little to do with the computational complexity. For example, every bit string is a syntactically (and semantically!) valid Jot program, and Jot is Turing-complete.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Doesn't exactly answer 1st question and doesn't make reference to 2nd question, but the 'Jot' link is very interesting to read, and a good answer to that side-question I asked at the end. $\endgroup$
    – Mr. Minty Fresh
    Commented Jan 9, 2018 at 2:09
  • 1
    $\begingroup$ The point of my answer is that your first question is ill-defined. It depends on where you want to draw the line between what is and is not "syntax". If we include, for example, type checking, then probably every statically typed language would require context-sensitivity (and potentially even Turing-completeness) to recognize no matter how simple the "syntax" would be if we didn't include type checking. If you're willing to exclude type checking, then why not scope checking and many other things. $\endgroup$
    – Derek Elkins left SE
    Commented Jan 9, 2018 at 2:22
  • 1
    $\begingroup$ As to your second question, the answer is the first sentence of my last paragraph. Basically, no, there is no connection other than your language isn't Turing-complete (in a reasonable sense) if there are only a finite number of programs. You can clearly make the syntax of a programming language as complex as you'd like no matter how weak the computational strength of the language is. Jot shows that you can have full Turing completeness even when the syntax is completely trivial. $\endgroup$
    – Derek Elkins left SE
    Commented Jan 9, 2018 at 2:22
  • $\begingroup$ Syntax as in, it compiles using the most-widely-used versions of the language (warnings allowed), or interpreted how about. You've indirectly answered that in the comments, so I'll just close the question now. $\endgroup$
    – Mr. Minty Fresh
    Commented Jan 9, 2018 at 3:38
3
$\begingroup$

Does this mean that there are languages that have regular grammars, yet are turing complete?

Yes, there are. Take any Turing-compete language and use the string $1^n$ to represent the $n$th syntactically valid program in the lexicographic order. This gives you a Turing-complete language whose grammar is $1^*$, though it's a little awkward to parse. ;-)

Improve this answer
$\endgroup$
2
$\begingroup$

On top of what Derek Elkins said, C is a bit of a weird case, because its grammar is formally ambiguous. Consider this piece of code:

typedef int T;

void f(void) {
    T * b;
}

This function declares a local variable, b, which is of type pointer-to-T.

Now consider this:

int T, b;

void f(void) {
    T * b;
}

Here, the body of the function doesn't declare any local variables, but does multiply two integers (and throws the result away).

The only difference between the two is the semantic context in which it appears. If was T declared as a type, then the line of code in the body of f is a declaration. If it wasn't, then it is an expression.

It is essentially impossible to write a context-free grammar which parses C without something extra, and there are essentially two ways that C compilers can handle this. They can either feed back information from the parser to the lexical analyser so that lexical analysis can distinguish identifiers that represent type name from identifiers which don't, or parse it as an ambiguous construct and work out which one it really is later.

Actually, it's even more complicated than this, because there are four distinct namespaces of identifier in C which do not interfere. This code is completely valid, if useless:

typedef int T;
struct S { int T; }

void f(void) {
    T: do_something();

    goto T;

    // T is still a typedef name even though
    // it's also the name of a label
    T t = 1;

    // Same here; S is still a typedef name
    // even though it's also the name of a struct
    S s = 1;
    struct S ss = { .T = 1 };
}
Improve this answer
$\endgroup$
3
  • $\begingroup$ This isn't just a case of ambiguity, but of non-contextfreeness. So I think it's clearer to say, in the first sentence, that C's syntax isn't context-free. $\endgroup$
    – reinierpost
    Commented Jan 9, 2018 at 14:24
  • $\begingroup$ This really is an extended comment: it doesn't answer the question. $\endgroup$
    – reinierpost
    Commented Jan 9, 2018 at 15:50
  • $\begingroup$ Yes, it doesn't answer the question and should not be accepted as the best answer. But I think it's relevant context to the question, since it asked about C specifically. $\endgroup$
    – Pseudonym ♦
    Commented Jan 10, 2018 at 3:33
1
$\begingroup$

David Richerby already showed a Turing-complete regular language consisting of numbers only. His technique can be applied to arbitrary programming languages, not just Turing machines: the programs of a programming language are enumerable, so you can number them and write a preprocessor that replaces each number with the program it stands for. Therefore, if the target language is Turing-complete, so is your new language, and it will be the language consisting of all numbers, which is a regular language.

However, this feels like cheating: those numbers don't express the structure of the programs they express. But we can also create Turing-complete regular languages in which programs do faithfully express their structure.

One example is, once again, Turing machines. For instance, we can denote Turing machines like this:

<machine> :== initial <state>; <finals> <transitions>
<finals> :== | final <state>; <finals>
<transitions> :== | <transition>; <transitions>
<transition> :== on <state> reading <symbol> <action>
<action> :== go left | go right | write <symbol>
<symbol> :== a | b | c | ...
<state> := q<number>
<number> := <digit> | <posdigit><number>
<digit> :== 0 | <posdigit>
<posdigit> :== 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

This is a regular language. Each of its members describes a Turing machine. Each Turing machine over the given alphabet is represented by a member of this language. (By multiple members, to be precise.) Therefore, as a notation for Turing machines, this language is Turing-complete.

You'd probably rather look at 'real' programming languages, ones that are used in practice, such as C, or Common Lisp, or PostScript. You'll need one that is Turing-complete (which can be hard to determine; for instance, I'm not entirely convinced that C isn't Turing-complete, because C has dynamic linking and (I think) (with some tinkering) the linked fragments can use different pointer sizes). Then, you need to find a Turing-complete subset of that language that is regular, or can be made regular through some syntactic transformation.

Is this possible?

I think so, but this deserves a discussion on its own, as it's really a separate question.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.