1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ "But I know this slips up." -- how so? $\endgroup$ – Raphael♦ Apr 6 '16 at 15:02
  • $\begingroup$ 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. $\endgroup$ – Raphael♦ Apr 6 '16 at 15:04
  • $\begingroup$ 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 ]$. $\endgroup$ – wvxvw Apr 6 '16 at 15:57
1
$\begingroup$

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/

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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-> ,
|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.