[Solved]: Pascal FOR loop with context free gramar

Problem Detail: 

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++; 

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

Asked By : El Marce

Answered By : jmite

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/64580

3.2K people like this

 Download Related Notes/Documents