Due: Friday, Sept 23rd by 11:59 PM

Getting Started

Download CS340_Assign03.zip and unzip it.

Import it into Eclipse Using File→Import…→General→Existing projects into workspace→Archive File. You should see a project called CS340_Assign03 in your Eclipse workspace.

Your Task

Your task is to modify the JSONParser class so that it implements a parser for subset of JSON. JSON is a standard format for representing structured data in text format, and is frequently used by web applications to transfer data.

The grammar

Here is the grammar for the JSON subset your parser should handle:

ValueStringLiteral | IntLiteral | Object | Array

Object → “{“ OptFieldList “}”

OptFieldListFieldList | ε

FieldListField | Field “,” FieldList

FieldStringLiteral “:” Value

Array → “[” OptValueList “]”

OptValueListValueList | ε

ValueListValue | Value “,” ValueList

Some explanations:

Approach

Your parser should have one parse function for each nonterminal symbol.

A parseValue function is provided to help you get started. It uses the lexer (lexical analyzer) to “peek” ahead in the input sequence of tokens. Based on the type of token seen, it either directly parses a string literal or integer value, or calls the parseObject or parseArray functions as appropriate.

The main challenge in implementing each parse function is deciding what production to apply. For some parse functions, such as parseObject and parseArray, handle nonterminal symbols for which there is only a single production, so they will be relatively simple. (The parseObject function is also provided for you, since it demonstrates how to consume terminal symbols using the expect method.)

The “interesting” parse functions will be for the OptFieldList, FieldList, OptValueList, and ValueList nonterminal symbols.

Hints and Specifications

For the parseOptFieldList and parseOptValueList methods, the issue is determining whether or not to apply the epsilon production. The OptFieldList and OptValueList nonterminals, which are used in the productions for FieldList and ValueList, generate strings of symbols which will be terminated with the “}” and “]” symbols, respectively. So, these functions can use the lexer’s peek method to find out what the next token will be, and if it is “}” (OptFieldList) or “]” (OptValueList), then the epsilon production should be applied.

For the parseFieldList and parseValueList methods, the issue is whether a single item (Field or Value) will be generated, or whether more than one item will be generated. A good approach is to start by expanding one item (i.e., call parseField or parseValue), then check to see whether then next token is a comma. A comma will indicate that the list continues past the first item, and so a recursive call to parseFieldList/parseValueList should be made.

Important: Your parser must reject inputs that can’t be derived from the grammar by throwing a ParserException. For example, note how the parseValue method raises an exception if the input string is empty. Make sure your parse functions raise an exception if an unexpected token is seen. (Using the expect method may be useful.)

Testing

To test your parser, run the Main class as a Java application.

Here are some example inputs that you can try, along with their expected parse trees:

First example:

"abc"

Parse tree:

VALUE
+--STRING_LITERAL(""abc"")

Second example:

123

Parse tree:

VALUE
+--INT_LITERAL("123")

Third example:

{ "abc" : 123 }

Parse tree:

VALUE
+--OBJECT
   +--LBRACE("{")
   +--OPT_FIELD_LIST
   |  +--FIELD_LIST
   |     +--FIELD
   |        +--STRING_LITERAL(""abc"")
   |        +--COLON(":")
   |        +--VALUE
   |           +--INT_LITERAL("123")
   +--RBRACE("}")

Fourth example:

[ 1, 2, "a", 3, "bcd" ]

Parse tree:

VALUE
+--ARRAY
   +--LBRACKET("[")
   +--OPT_VALUE_LIST
   |  +--VALUE_LIST
   |     +--VALUE
   |     |  +--INT_LITERAL("1")
   |     +--COMMA(",")
   |     +--VALUE_LIST
   |        +--VALUE
   |        |  +--INT_LITERAL("2")
   |        +--COMMA(",")
   |        +--VALUE_LIST
   |           +--VALUE
   |           |  +--STRING_LITERAL(""a"")
   |           +--COMMA(",")
   |           +--VALUE_LIST
   |              +--VALUE
   |              |  +--INT_LITERAL("3")
   |              +--COMMA(",")
   |              +--VALUE_LIST
   |                 +--VALUE
   |                    +--STRING_LITERAL(""bcd"")
   +--RBRACKET("]")

Fifth example:

{ "abc" : [ 1, 2 ], "def" : { "hey" : "yo" } }

Parse tree:

VALUE
+--OBJECT
   +--LBRACE("{")
   +--OPT_FIELD_LIST
   |  +--FIELD_LIST
   |     +--FIELD
   |     |  +--STRING_LITERAL(""abc"")
   |     |  +--COLON(":")
   |     |  +--VALUE
   |     |     +--ARRAY
   |     |        +--LBRACKET("[")
   |     |        +--OPT_VALUE_LIST
   |     |        |  +--VALUE_LIST
   |     |        |     +--VALUE
   |     |        |     |  +--INT_LITERAL("1")
   |     |        |     +--COMMA(",")
   |     |        |     +--VALUE_LIST
   |     |        |        +--VALUE
   |     |        |           +--INT_LITERAL("2")
   |     |        +--RBRACKET("]")
   |     +--COMMA(",")
   |     +--FIELD_LIST
   |        +--FIELD
   |           +--STRING_LITERAL(""def"")
   |           +--COLON(":")
   |           +--VALUE
   |              +--OBJECT
   |                 +--LBRACE("{")
   |                 +--OPT_FIELD_LIST
   |                 |  +--FIELD_LIST
   |                 |     +--FIELD
   |                 |        +--STRING_LITERAL(""hey"")
   |                 |        +--COLON(":")
   |                 |        +--VALUE
   |                 |           +--STRING_LITERAL(""yo"")
   |                 +--RBRACE("}")
   +--RBRACE("}")

Grading

Your parser will be graded according the following criteria:

Submitting

When you are done, submit the lab to the Marmoset server as described below.

Save the project (CS340_Assign03) to a zip file by right-clicking it and choosing

Export…→Archive File

Upload the saved zip file to the Marmoset server as assign03. The server URL is

https://cs.ycp.edu/marmoset/

Important: after you submit, log into the submission server and verify that the correct files were uploaded. You are responsible for ensuring that you upload the correct files. I may assign a grade of 0 for an incorrectly submitted assignment.