In Pascal For-do loops, there is a rule stating that one cannot modify the counter variable inside the body of the loop.

To exemplify the rule, take the following Pascal for-do, which is not valid, since the counter variable is being modified inside the loop's body:

for i := 0 to 10 do i := i + 1;

My question is: Is possible to express this rule using context-free grammars?

  • 3
    $\begingroup$ You are asking to express semantics using the tools of syntax. $\endgroup$ – Raphael Oct 13 '16 at 20:44
  • 3
    $\begingroup$ This is not conceptually different from the rule "variables must be declared before use", which is well-known to not be context-free. $\endgroup$ – rici Oct 13 '16 at 20:57
  • $\begingroup$ That (i++) is not even valid Pascal. i := i + 1 would be. $\endgroup$ – Rudy Velthuis Jul 23 '17 at 10:35
  • $\begingroup$ Thanks for the remark @RudyVelthuis. Fixed. Long time without working on Pascal $\endgroup$ – El Marce Jul 23 '17 at 21:22

The answer depends on how you represent variables.

  • If there are an infinite number of variable names, the answer is no.
  • If there are a finite number of variable names, the answer is "yes but you never would in practice".

Here's some informal arguments for that:

For the first case, there must be some set of non-terminals which represent valid loop bodies. And for each variable, there must be a non-terminal where you can refer to that variable, and one where you can't. Because of loop nesting, this must be true for any combination of any number of variables i.e. we need a distinct non-terminal for each of an infinite combinations of allowed and not allowed variables.

But, then we have an infinite number of non-terminals, which is not allowed in a context-free grammar.

This is basically because of the "context free" part of CFG. Knowing which variables are allowed and aren't is context, which our grammars are free of.

In the case of a finite number of allowed variables, you basically model it like I said above, with a different non-terminal for each combination of variables. So in terms of computability/expressibility, you you can do it with a context free grammar, in the same way you can model your computer and its 8GB of RAM with a finite automaton. Doing so will explode quickly, and it's not the way you want to do things.

| cite | improve this answer | |

The task of a context free grammar is to generate valid strings that are in a context free language. Context free languages, being 'context free', are generally used in syntax analysis part of compilers. It's just out of their scope to check for semantics.

Consider an analogy with English language, the statement "He is a girl", is completely valid in terms of syntax,(Pronoun-verb-noun is a valid English construct), however it does not make any sense semantically.

Such cases are out of scope or power of context free grammars which is why context sensitive grammars(and even more complex grammars exist).

| cite | improve this answer | |
  • $\begingroup$ All of this is true but I don't think it really answers the question. The restriction that the loop counter can't be modified inside the loop can (at least in principle) be implemented purely syntactically, and the question is whether this can be done in a context-free way. (Similarly, one could forbid "he is a girl" from English by syntactic means by introducing a class of "male-compatible nouns" and only allowing "he is" to be followed by one of those). $\endgroup$ – David Richerby Apr 24 '18 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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