# Context free grammar for nested arrays separated by commas

I have to define a context free grammar for the following rules:

(i) A pair of square bracket tokens [] surrounding zero or more values separated by commas. (ii) A value can be another array or a number.

A number is represented by the token NUMBER. So for example, [NUMBER, [NUMBER, NUMBER], NUMBER]. is valid.

I am stuck as how to approach this.

My intuition is always to look at the question and see that S->LSQ VALUE RSQ, VALUE->VALUE COMMA VALUE | VALUE | ARRAY | e | NUMBER, ARRAY -> LSQ NUMBER RSQ, NUMBER ->NUMBER. But I know this slips up.

What steps can I take to ensure I am always thinking in the right way?

• "But I know this slips up." -- how so? – Raphael Apr 6 '16 at 15:02
• This is almost literally the Motzkin language (Dyck plus non-parenthesis symbols in arbitrary places), one of the most standard CFLs. So I don't know how to help you; you have probably seen something very similar to the solution in class. – Raphael Apr 6 '16 at 15:04
• It'd be easier if you separate it into two steps: (1) generate the inside of the brackets. (2) wrap (1) in brackets. Eg. $Elements \to Element | Element , Elements$, $Array \to [] | [ Elements ]$. – wvxvw Apr 6 '16 at 15:57

your current implementation doesn't enforce the first condition "A pair of square bracket tokens [] surrounding zero or more values separated by commas" as an empty string or a NUMBER on its own would be accepted by the grammar.

You could use the following CFG to maintain the integrity of the constraints

array ::= [ ] | [ element ]

element ::= value | value , element

value ::= array | NUMBER

To derive [NUMBER, [NUMBER, NUMBER], NUMBER]

1. [ element ]
2. [ value, element ]
3. [value, array ]
4. [value, value, element ]
5. [value, array, value]
6. [value, [element], value]
7. [value, [value, element], value]
8. [value, [value, value], value]
9. [NUMBER, [NUMBER, NUMBER], NUMBER]

The grammar rules provided for JSON here might also be a useful reference: http://json.org/

I believe I have a solution but @wvxvw's comment is very helpful.

ARRAY -> LSQ ARRAY RSQ | ARRAY COMMA  ARRAY | e | NUMBER
NUMBER -> NUMBER
LSQ -> [
RSQ-> ]
COMMA-> ,