Context free grammar for balanced simultaneous assignment

Question

I know that languages like Python have simultaneous (or "multiway") assignment. Today at an exam I came across a question along the lines of

Write the productions of a grammar for simultaneous assignment, so that if a,b = 1, 1+0; is passed, it would parse fine but a,b,c = 1, 1+0 would return an error (that is to say the number of ids needs to be the same as expressions)? The error should be syntax error.

I understood by this:

You do not need to write the attributes for the grammar (since it was syntax only).

I've tried and looked for all over the place for hints that might help me, but I still see no way of working it out with the way I have been taught how to write grammar. This is what I have so far:

P -> id Id_Tail = exp exp_Tail
Id_Tail -> , id Id_Tail
Id_Tail -> ε
exp_Tail -> , exp exp_Tail
exp_Tail -> ε
exp -> //assume this is is defined well enough to allow for all type of expressions that will generate/have a num (value) that is allowed to be assigned to the respective id

However, this in no way will generate the syntax error that is wanted (it could keep on generating more expressions than ids).

Where there any constraints on what sort of grammars you can use? This is possible with context-free grammars (as I described in an answer), but not with regular grammars. — Joshua Taylor

Joshua Taylor Joshua Taylor · Accepted Answer · 2013-08-27T18:44:47

This is an example of a grammar that a simple regular grammar cannot handle, but that a context-free grammar can. While identifier lists are typically handled by some productions akin to

ids = id
    | id ',' ids

in this case you'll need to take an approach more like that given in balancing punctuation, e.g.,

expr = ... 
     | '(' expr ')'

The proper balancing is accomplished because a left and right parenthesis are added at each expansion of the rule. You can do a similar thing for the multiple assignment expression:

multiway-assignment = lvalue '=' rvalue                         
                    | lvalue ',' multiway-assignment ',' rvalue

Here, the basic multiway-assignment just has an lvalue and rvalue on either side of an assignment operator. The center recursion ensures that every value on the lvalue on the left must be matched by an rvalue on the right, so the number of lvalues is always equal to the number of rvalues.

Context free grammar for balanced simultaneous assignment

1 Answers