build a parser for JSON, the JavaScript Object Notation.

Input

Input will be provided in the form of a file containing a single JSON object or array. The syntax for both structures is defined on the front page of http://www.json.org/ using railroad diagrams.

Processing

Build a recursive-descent parser for JSON. While the specification includes syntax diagrams for tokens, you may wish to build a separate scanner rather than creating procedures for string, number, true, false, and null.

As you parse the JSON object, construct an Abstract Syntax Tree using the following definitions:

Abstract Syntax Tree

ast.h

#ifndef AST_H_

#define AST_H_

class JsonValue

{

public:

virtual void Print() = 0;

};

class JsonObject : public JsonValue

{

private:

map pairs;

public:

virtual void Print();

void Add(string name, JsonValue* value);

};

class JsonArray : public JsonValue

{

private:

list values;

public:

virtual void Print();

void Add(JsonValue *v);

};

class JsonString : public JsonValue

{

private:

string value;

public:

JsonString(string s) : value(s) { };

virtual void Print();

};

class JsonNumber : public JsonValue

{

private:

double value;

public:

JsonNumber(double d) : value(d) { };

virtual void Print();

};

class JsonBoolean : public JsonValue

{

private:

bool value;

public:

JsonBoolean(bool b) : value(b) { };

virtual void Print();

};

class JsonNull : public JsonValue

{

public:

virtual void Print();

};

#endif // AST_H_

Usage

An AST for the following JSON object:

{

"str": "foo",

"num": 123,

"bool": true,

"nul": null,

"arr": [ "bar", 456, false ]

}

might be constructed with the following C++ code:

JsonObject* o = new JsonObject();

o->Add("str", new JsonString("foo"));

o->Add("num", new JsonNumber(123));

o->Add("bool", new JsonBoolean(true));

o->Add("nul", new JsonNull());

JsonArray *a = new JsonArray();

a->Add(new JsonString("bar"));

a->Add(new JsonNumber(456));

a->Add(new JsonBoolean(false));

o->Add("arr", a);

Output

If the file is parsed successfully, call the Print() method to traverse the AST and print the structure of the the tree as a Scheme list with one or more of the following elements:

( string value )

( number value )

( boolean value )

( null )

( array {value} )

( object {name value} )

As in the footnote on p. 49 of the textbook, curly braces ({ }) are used to indicate zero or more instances of the values inside.

Calling o->Print() on the object defined above should produce the following output:

( object arr ( array ( string bar ) ( number 456 ) ( boolean false ) ) bool ( boolean true ) nul ( null ) num ( number 123 ) str ( string foo ) )

Note that the order of the objects name/value pairs has changed since the C++ std::map type sorts its keys.

If the file is not parsed successfully,