The inspiration for this post came from a project at work. I was building a service that required the comparison of two objects. The catch was that I needed to be able to , , and to specific nodes. Json replace keys filter out paths apply comparison functions Obviously, a standard library comparison function such as would not work. 😧 reflect.DeepEqual() The solution was to build a ( ) modeled off of the objects. Every in the tree represents either a , , , or . AST Abstract Syntax Tree Json Node string integer array object By doing this I would allow for the flexibility to more easily apply onto the data. algorithms To build this we’ll start with the to generate . Then move onto the which will take the tokens and match them to grammar. Finally, we’ll add hooks to generate the tree. Lexer Tokens Parser Json AST The final directory structure: .main.go/lexerlexer.golexer_test.go/tokentoken.go/parserparser.go/astast.go If you want to see and run the final results: cd $GOPATH/src/github.com/Lebonescogit clone go run main.go ./examples/test.json https://github.com/Lebonesco/json_parser.git Lexer The lexer’s job is to take in the data and convert it into a stream of . These tokens include: , , , , , , , , , and . json tokens INVALID EOF COMMA COLON LBRACE RBRACE LBRACKET RBRACKET STRING INTEGER A lexer is also referred to as a scanner. Note: Let’s start down below 👇 cd $GOPATH/src/github.com/Lebonesco/json_parsermkdir tokencd tokentouch token.go You have some freedom in how you want to define your . The more data you add to a the easier it is to debug. tokens token Note: We’ll be using a array, , to store our literals to allow for characters. rune []rune token Unicode Next, let’s jump into our 👍 lexer mkdir lexercd lexertouch lexer.gotouch lexer_test.go The will track where we are in the input and necessary character look aheads. lexer In terms of functionality, it will need to be able to create a new and peak ahead to the next one. token This scanner doesn’t support values, but they could easily be added. Note: Boolean Lexer Test Here we will take in a j string and make sure that it outputs the correct stream of tokens. son To run the test: go test -v=== RUN TestLexer--- PASS: TestLexer (0.00s)PASSok github.com/Lebonesco/json_parser/lexer 0.433s You now have a working 🎉 🎉 🎉 lexer Parser This is the part where we take our stream and match it with to produce nodes. json grammar AST If we were to define in terms of regular expressions it would be represented by the grammar defined below 👇 json JSON : valueValue : Object | Array | String | Integer | Bool | NullArray : '[' [Value] {',' Value}']'Object : '{' [Property] {',' Property} '}'Property : String ':' Value In the above syntax, means the expression occurs one or more times and means that it occurs zero or more times. [expression] {expression} There are tools like that will generate a lexer and/or parser if you provide the regular expressions. That’s the recommended way to go if you’re dealing with something more complicated. gocc But since is fairly simple, we’ll do it by hand! 👐 Json Let’s construct the AST that will represent our final results. nodes mkdir astcd asttouch ast.go The are fairly simple. If we cared more about error handling and tracking hashes, like in my use case, we could store more data. nodes node Because Go uses instead of we need to apply the method to each type in order for each to be interpreted as a node. Note: composition inheritance TokenLiteral() node Json Now onto the Parser! Let’s bring it all together and write our driver, . main.go is a nice substitute to to get prettier outputs. Note: json.MarshalIndent() json.Marshal() json To run: go run main.go ./exampes/test.json All Done 😄 Now that we can generate an it’s easy to add a rolling hash to each node and do all of the other custom operations such as: AST, substitute node values filter out nodes apply special comparison functions to nodes I’ll leave those extensions to the reader. Feel free to drop links to your work in the comments. I’d love to see what you come up with. 👍 Thank you for taking the time to read this article. If you found it helpful or interesting please let me know 👏👏👏.
