World's most popular travel blog for travel bloggers.

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

, , No Comments
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

Answered By : Adi

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]

Start with array -> [element]

  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/

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback