Bitwise JSON Parser

Released December 2014, by Stephen Jackson

TL;DR

The only state that needs to be tracked when parsing JSON fits in one bit per iteration (is last non-terminal an object xor array?).


Download


Introduction

The goal of this C code is to parse a JSON string with a minimal amount of memory (stack or heap). The main file, json.c does not contain any calls to malloc. In order to reduce stack usage while parsing, each iteration of the stack requires a single bit (which is kept track of with a depth counter).

The bit itself specifies if the last encountered non-terminal was an array or object. Terminals (strings, numbers, booleans, commas, colons, and null) are single tokens that are consumed immediately.

If the stack is about to overflow, it is possible for the parsing function to be recursively called (if JSON_RECURSE is defined). Otherwise, a depth error is returned.

WARNING: This code has not been thoroughly tested and thus should not be used in production.


Grammar

The following can be observed in the _procJson(...) function.

start
	→ obj
	| arr

obj
	→ '{' inner_obj
	| '{' '}'

inner_obj → string ':' value obj_end

obj_end
	→ ',' inner_obj
	| '}'

arr
	→ '[' inner_arr
	| '[' ']'

inner_arr → value arr_end

arr_end
	→ ',' inner_arr
	| ']'

value
	→ obj
	| arr
	| string
	| boolean
	| number
	| null

The arr in start is conditionally present if it is the first time start has been encountered.


Functionality

This code uses a common parser for three functions: validator, reducer, and token counter. See src/json.h for more details on these functions.


TODOs

Before reading these, please note that my requirements have changed, and I am moving away from JSON. I do not intend on adding further functionality at this time.


License

This project is MIT Licensed

Copyright (c) 2014 Stephen Jackson

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.