World's most popular travel blog for travel bloggers.

# [Solved]: Context free grammar for nested arrays separated by commas

, ,
Problem Detail:

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?

###### Asked By : Dhruv Ghulati

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/