Write a json parser

How to build a parser
If you want an easy way to code parsers, or you are tight on space, you should hand-code a recursive descent parser; these are essentially

LL(1) parsers. This is especially effective for languages which are as “simple” as Basic. (I did several of these back in the 70s!). The good news is these don’t contain any library code; just what you write.

They are pretty easy to code, if you already have a grammar. First, you have to get rid of left recursive rules (e.g., X = X Y ). This is generally pretty easy to do, so I leave it as an exercise. (You don’t have to do this for list-forming rules; see discussion below).

Then if you have BNF rule of the form:

X = A B C ;

create a subroutine for each item in the rule (X, A, B, C) that returns a boolean saying “I saw the corresponding syntax construct”. For X, code:

subroutine X()
     if ~(A()) return false;
     if ~(B()) { error(); return false; }
     if ~(C()) { error(); return false; }
     // insert semantic action here: generate code, do the work, ....
     return true;
end X;

Similarly for A, B, C.

If a token is a terminal, write code that checks the input stream for the string of characters that makes up the terminal. E.g, for a Number, check that input stream contains digits and advance the input stream cursor past the digits. This is especially easy if you are parsing out of a buffer (for BASIC, you tend to get one line at time) by simply advancing or not advancing a buffer scan pointer. This code is essentially the lexer part of the parser.

If your BNF rule is recursive… don’t worry. Just code the recursive call. This handles grammar rules like:

T  =  '('  T  ')' ;

This can be coded as:

subroutine T()
     if ~(left_paren()) return false;
     if ~(T()) { error(); return false; }
     if ~(right_paren()) { error(); return false; }
     // insert semantic action here: generate code, do the work, ....
     return true;
end T;

If you have a BNF rule with an alternative:

P = Q | R ;

then code P with alternative choices:

subroutine P()
    if ~(Q())
        {if ~(R()) return false;
         return true;
        }
    return true;
end P;

Sometimes you’ll encounter list forming rules. These tend to be left recursive, and this case is easily handled. The basic idea is to use iteration rather than recursion, and that avoids the infinite recursion you would get doing this the “obvious” way. Example:

L  =  A |  L A ;

You can code this using iteration as:

subroutine L()
    if ~(A()) then return false;
    while (A()) do { /* loop */ }
    return true;
end L;

You can code several hundred grammar rules in a day or two this way. There’s more details to fill in, but the basics here should be more than enough.

If you are really tight on space, you can build a virtual machine that implements these ideas. That’s what I did back in 70s, when 8K 16 bit words was what you could get.

If you don’t want to code this by hand, you can automate it with a metacompiler (Meta II) that produces essentially the same thing. These are mind-blowing technical fun and really takes all the work out of doing this, even for big grammars.

August 2014:

I get a lot of requests for “how to build an AST with a parser”. For details on this, which essentially elaborates this answer, see my other SO answer https://stackoverflow.com/a/25106688/120163

July 2015:

There are lots of folks what want to write a simple expression evaluator. You can do this by doing the same kinds of things that the “AST builder” link above suggests; just do arithmetic instead of building tree nodes. Here’s an expression evaluator done this way.

Arthmetic Expression Evaluator (Swift)

/*
 sum = product | sum "+" product | sum "-" product
 product = term | product "*" term | product "/" term
 term = "-" term | "(" sum ")" | number
 */

class ExpressionEvaluator {
    var text: String = ""
    var index = 0
    var currentCharacter: Character {
        return text[text.index(text.startIndex, offsetBy: index)]
    }
    
    func parse(str: String) {
        guard str.count != 0 else {
            return
        }

        text = str
        
        if let result = parseSum() {
            print("\(text) = \(result)")
        } else {
            print("Syntax error at \(index)")
        }
    }
    
    func parseSum() -> Int? {
        guard let num = parseProduct() else {
            return nil
        }
        var number = num
        while index < text.count {
            skipBlank()
            if match(char: "+") {
                if let num2 = parseProduct() {
                    number += num2
                } else {
                    return nil
                }
            } else if match(char: "-") {
                if let num2 = parseProduct() {
                    number -= num2
                } else {
                    return nil
                }
            } else {
                return number
            }
        }
        return number
    }

    func parseProduct() -> Int? {
        guard let num = parseTerm() else {
            return nil
        }
        
        var number = num
        
        while index < text.count {
            skipBlank()
            if match(char: "*") {
                if let num = parseTerm() {
                    number *= num
                } else {
                    return nil
                }
            } else if match(char: "/") {
                if let num = parseTerm() {
                    number /= num
                } else {
                    return nil
                }
            } else {
                return number
            }
        }
        
        return number
    }

    func parseTerm() -> Int? {
        var number: Int? = nil
        skipBlank()
        if match(char: "(") {
            number = parseSum()
            if number != nil {
                skipBlank()
                if !match(char: ")") {
                    return nil
                }
            }
        } else if match(char: "-") {
            if let num = parseTerm() {
                number = -1 * num
            } else {
                return nil
            }
        } else {
            number = parseNumber()
        }
        
        return number
    }
    
    func skipBlank() {
        while match(char: " ") {}
    }

    func parseNumber() -> Int? {
        var number = 0
        if let num = currentCharacter.wholeNumberValue {
            number = num
            
            index += 1
            while index < text.count, let num2 = currentCharacter.wholeNumberValue {
                skipBlank()
                number = number * 10 + num2
                index += 1
            }
            return number
        }
        return nil
    }
    
    func match(char: Character) -> Bool {
        if char == currentCharacter  {
            index += 1
            return true
        }
        return false
    }
}

A json parser with Swift.
Inspired by A JSON Parser、MethodTraceAnalyze and Writing a simple JSON parser

import Foundation

/*
 <json>     ::= <value>
 <value>    ::= <object> | <array> | <bool> | <string> | <number> | <null>
 <array>    ::= "[" [<value>] {"," <value>}* "]"
 <object>   ::= "{" [<property>] {"," <property>}* "}"
 <property> ::= <string> ":" <value>
 */

enum JSONNumberType: Equatable {
    case int(Int)
    case double(Double)
    
    static func == (lhs: JSONNumberType, rhs: JSONNumberType) -> Bool {
        switch (lhs, rhs) {
        case let (.int(left), .int(right)):
            return left == right
        case let (.double(left), .double(right)):
            return left == right
        default:
            return false
        }
    }
}

enum JSONType: Equatable {
    case bool
    case string
    case number(JSONNumberType)
    case null
    case array
    case object
    
    static func == (lhs: JSONType, rhs: JSONType) -> Bool {
        switch (lhs, rhs) {
        case (.bool, .bool),
             (.string, .string),
             (.number(_), .number(_)),
             (.null, .null),
             (.array, .array),
             (.object, .object):
            return true
        default:
            return false
        }
    }
}

struct JSONProperty<V> {
    let key: String
    let value: JSON<V>
}

struct JSON<T> {
    let type: JSONType
    let value: T?
}

struct JSONSyntaxError: Error {
    let line: Int
    let column: Int
}

enum JSONToken: Equatable {
    case string(String, Int, Int)
    case number(JSONNumberType, Int, Int)
    case bool(Bool, Int, Int)
    case null(Int, Int)
    
    case lBrace(Int, Int) // {
    case rBrace(Int, Int) // }
    case lBracket(Int, Int) // [
    case rBracket(Int, Int) // [
    case comma(Int, Int) // ,
    case colon(Int, Int) // :,
    
    static func ==(lhs: JSONToken, rhs: JSONToken) -> Bool {
        switch (lhs, rhs) {
        case let (.string(left, _, _), .string(right,  _, _)):
            return left == right
        case let (.number(.int(left), _, _), .number(.int(right), _, _)):
            return left == right
        case let (.number(.double(left), _, _), .number(.double(right), _, _)):
            return left == right
        case let (.bool(left, _, _), .bool(right, _, _)):
            return left == right
        case (.null(_, _), .null(_, _)),
             (.lBrace(_, _), .lBrace(_, _)),
             (.rBrace(_, _), .rBrace(_, _)),
             (.lBracket(_, _), .lBracket(_, _)),
             (.rBracket(_, _), .rBracket(_, _)),
             (.comma(_, _), .comma(_, _)),
             (.colon(_, _), .colon(_, _)):
            return true
        default:
            return false
        }
    }
    
    var lineColumn: (Int, Int) {
        switch self {
        case let .number(_, line, col):
            return (line, col)
        case let .string(_, line, col):
            return (line, col)
        case let .bool(_, line, col):
            return (line, col)
        case let .null(line, col),
             let .lBrace(line, col),
             let .rBrace(line, col),
             let .lBracket(line, col),
             let .rBracket(line, col),
             let .comma(line, col),
             let .colon(line, col):
            return (line, col)
        }
    }
}

class JSONParser {
    var index: Int
    var currentToken: JSONToken?
    let tokens: [JSONToken]
    
    var error: JSONSyntaxError {
        var (line, col) = (0, 0)
        if let token = currentToken {
            (line, col) = token.lineColumn
        } else if let token = tokens.last {
            (line, col) = token.lineColumn
        }
        return JSONSyntaxError(line: line, column: col)
    }
    
    static func parse(text: String) throws -> JSON<Any> {
        do {
            let tokens = try JSONLexer(text).lex()
            if tokens.count > 0 {
                return try JSONParser(tokens).parse()
            } else {
                return JSON(type: .null, value: JSONType.null)
            }
        } catch let e {
            throw e
        }
    }
    
    private init(_ tokens: [JSONToken]) {
        self.tokens = tokens
        index = 0
    }
    
    private func parse() throws -> JSON<Any> {
        advance()
        do {
            return try parseValue()
        } catch let e {
            throw e
        }
    }
    
    private func parseValue() throws -> JSON<Any> {
        guard let token = currentToken else {
            throw error
        }
        
        switch token {
        case .lBrace(_, _):
            return try parseObject()
        case .lBracket(_, _):
            return try parseArray()
        case let .bool(bool, _, _):
            return JSON(type: .bool, value: bool)
        case .null(_, _):
            return JSON(type: .null, value: JSONType.null)
        case .string(let str, _, _):
            return JSON(type: .string, value: str)
        case .number(let numType, _, _):
            return JSON(type: .number(numType), value: numType)
        default:
            break
        }
        
        throw error
    }
    
    private func parseObject() throws -> JSON<Any> {
        var properties = [JSONProperty<Any>]()
        advance()
        
        repeat {
            guard let token = currentToken else {
                throw error
            }
            
            switch token {
            case .rBrace(_, _):
                return JSON(type: .object, value: properties)
            case .comma(_, _):
                advance()
            default:
                properties.append(try parseProperty())
                advance()
            }
        } while currentToken != nil
        
        throw error
    }
    
    private func parseArray() throws -> JSON<Any> {
        var array = [JSON<Any>]()
        advance()
        
        repeat {
            guard let token = currentToken else {
                break
            }
            
            switch token {
            case .rBracket(_, _):
                return JSON(type: .array, value: array)
            case .comma(_, _):
                advance()
            default:
                array.append(try parseValue())
                advance()
            }
        } while currentToken != nil
        
        throw error
    }
    
    private func parseProperty() throws -> JSONProperty<Any> {
        guard let token = currentToken else {
            throw error
        }
        
        switch token {
        case let .string(str, _, _):
            advance()
            if currentToken == JSONToken.colon(0, 0) {
                do {
                    advance()
                    return JSONProperty(key: str, value: try parseValue())
                } catch let e {
                    throw e
                }
            }
        default:
            break
        }
        
        throw error
    }
    
    private func advance() {
        if index < tokens.count {
            currentToken = tokens[index]
            index += 1
        } else {
            currentToken = nil
        }
    }
}

class JSONLexer {
    var column: Int
    var line: Int
    
    var index: Int
    var jsonText: (String)
    var currentCharacter: Character?
    let escape: [Character : String] = ["n" : "\n",
                                        "t" : "\t",
                                        "r" : "\r",
                                        "\\" : "\\",
                                        "\"" : "\""]
    
    var error: JSONSyntaxError {
        return JSONSyntaxError(line: line, column: column)
    }
    
    static func test(jsonText: String, expected: [JSONToken]) {
        do {
            let tokens = try JSONLexer(jsonText).lex()
            if tokens == expected {
                print("Lexer is right.")
            } else {
                print("Error")
            }
        } catch let e as JSONSyntaxError {
            print("Error at line \(e.line) column \(e.column)")
        } catch let e {
            print("Unknown error! \(e.localizedDescription)")
        }
    }
    
    init(_ jsonText: String) {
        self.jsonText = jsonText
        column = 1
        line = 1
        index = 0
    }
    
    func lex() throws -> [JSONToken] {
        guard jsonText.count > 0 else {
            throw error
        }
        
        advance()
        
        var result = [JSONToken]()
        while let char = currentCharacter {
            do {
                if let token = try lexString() {
                    result.append(token)
                    continue
                }
                if let token = try lexNumber() {
                    result.append(token)
                    continue
                }
                if let token = try lexBool() {
                    result.append(token)
                    continue
                }
                if let token = try lexNull() {
                    result.append(token)
                    continue
                }
            } catch let e {
                throw e
            }
            
            //  above use advance(false), check blank.
            if CharacterSet.whitespacesAndNewlines.contains(char.unicodeScalars.first!) {
                advance()
                continue
            }
            
            var token: JSONToken?
            switch char {
            case "{":
                token = .lBrace(line, column)
            case "}":
                token = .rBrace(line, column)
            case "[":
                token = .lBracket(line, column)
            case "]":
                token = .rBracket(line, column)
            case ",":
                token = .comma(line, column)
            case ":":
                token = .colon(line, column)
            default:
                token = nil
            }
            
            if let tk = token {
                result.append(tk)
                advance()
            } else {
                throw error
            }
        }
        return result
    }
    
    private func advance(_ skipWhitespace: Bool = true) {
        repeat {
            if index < jsonText.count {
                currentCharacter = jsonText[jsonText.index(jsonText.startIndex, offsetBy: index)]
                if currentCharacter == "\n" {
                    line += 1
                    // skip newline
                    column = 0
                } else {
                    column += 1
                }
                index += 1
            } else {
                currentCharacter = nil
            }
        } while skipWhitespace &&
            currentCharacter != nil &&
            CharacterSet.whitespacesAndNewlines.contains((currentCharacter?.unicodeScalars.first)!)
    }
    
    private func lexString() throws -> JSONToken? {
        guard currentCharacter == "\"" else {
            return nil
        }
        advance(false)
        var str = ""
        /*
         Not include:
         \f -- Form feed
         \v -- Vertical tab
         \b -- backspace
         */
        while currentCharacter != "\""  {
            if currentCharacter == "\\" {
                advance(false)
                if let char = currentCharacter, let escapedChar = escape[char] {
                    str.append(escapedChar)
                } else {
                    throw error
                }
            } else if let char = currentCharacter {
                str.append(char)
                advance(false)
            } else {
                throw error
            }
        }
        advance()
        return .string(str, line, column)
    }
    
    // Only support Normal Int or float
    private func lexNumber() throws -> JSONToken? {
        func getDigits() -> Int? {
            guard let char = currentCharacter, char.isWholeNumber else {
                return nil
            }
            
            var num = 0
            while let theNum = currentCharacter?.wholeNumberValue {
                num = num * 10 + theNum
                advance(false)
            }
            return num
        }
        
        func getFraction() -> Double? {
            guard let char = currentCharacter, char.isWholeNumber else {
                return nil
            }
            
            var multiplier = 1.0
            var num = 0.0
            while let theNum = currentCharacter?.wholeNumberValue {
                multiplier *= 0.1
                num = num + multiplier * Double(theNum)
                advance(false)
            }
            return num
        }
        
        guard let char = currentCharacter,
            (char == "-" || CharacterSet.decimalDigits.contains(char.unicodeScalars.first!)) else {
                return nil
        }
        
        let isNegative = char == "-"
        var int: Int?
        var double: Double?
        
        var num: Int = 0
        // -123
        if isNegative {
            advance(false)
        }
        
        if let theNum = getDigits() {
            num = theNum
        } else {
            if (isNegative) {
                throw error
            } else {
                return nil
            }
        }
        
        let sign = isNegative ? -1 : 1
        if currentCharacter == "." {
            advance(false)
            if let fraction = getFraction() {
                double = (Double(num) + fraction) * Double(sign)
            } else {
                throw error
            }
        } else {
            int = num * sign
        }
        
        if int != nil {
            return .number(.int(int!), line, column)
        } else if double != nil {
            return .number(.double(double!), line, column)
        } else {
            return nil
        }
    }
    
    private func lexBool() throws -> JSONToken? {
        guard currentCharacter == "f" || currentCharacter == "t" else {
            return nil
        }
        
        func isBoolString(_ str: String) -> Bool {
            for alphanumeric in str {
                if let char = currentCharacter, char == alphanumeric {
                    advance(false)
                } else {
                    return false
                }
            }
            return true
        }
        
        var token: JSONToken? = nil
        if currentCharacter == "f" {
            if isBoolString("false") {
                token = .bool(false, line, column)
            }
        } else {
            if isBoolString("true") {
                token = .bool(true, line, column)
            }
        }
        
        if token == nil {
            throw error
        }
        return token
    }
    
    private func lexNull() throws -> JSONToken? {
        guard currentCharacter == "n" else {
            return nil
        }
        
        for alphanumeric in "null" {
            if let char = currentCharacter, char == alphanumeric {
                advance(false)
            } else {
                throw error
            }
        }
        
        return .null(line, column)
    }
}

Test for JSONParser.

import Foundation

protocol Test {
    static func cs(current:String, expect:String, des:String)
}

extension Test {
    static func cs<T: Equatable>(current:T, expect: T, des: String) {
        if current == expect {
            print("✅ \(des) ok，符合预期值：\(expect)")
        } else {
            let msg = "❌ \(des) fail，不符合预期值：\(expect)"
            print(msg)
            assertionFailure(msg)
        }
    }
}

let jsonTxt = """
{
    "key1": "value1",
    "key2": 22,
    "key3": {
        "subKey1": "subValue1",
        "subKey2": 40,
        "subKey3":[
            {
                "sub1Key1": 10,
                "sub1Key2":{
                    "sub3Key1" : "sub3Value1",
                    "sub3Key2" : "sub3Value2"
                }
            },
            {
                "sub1Key1": false,
                "sub1Key2": 15
            }
        ],
        "subKey4": [
            "value1",
            23.23,
            "value2",
        ],
        "subKey5": null,
    }
}

"""

public class TestJSON:Test {
    public static func testJSON() {
        do {
            let item = try JSONParser.parse(text: jsonTxt)
            
            let arr = item.value as! Array<JSONProperty<Any>>
            
            cs(current: "\(arr.count)", expect: "3", des: "all dic count")
            cs(current: "\(arr[0].key)", expect: "key1", des: "key1")
            cs(current: "\(arr[0].value.value as! String)", expect: "value1", des: "value1")
            
            cs(current: "\(arr[1].key)", expect: "key2", des: "key2")
            cs(current: arr[1].value.value as! JSONNumberType, expect:JSONNumberType.int(22) , des: "value2")
            
            cs(current: "\(arr[2].key)", expect: "key3", des: "key3")
            let arr2kvs = arr[2].value.value as! Array<JSONProperty<Any>>
            cs(current: "\(arr2kvs.count)", expect: "5", des: "arr2kvs count")
            cs(current: "\(arr2kvs[0].key)", expect: "subKey1", des: "subKey1")
            cs(current: "\(arr2kvs[0].value.value as! String)", expect: "subValue1", des: "subValue1")
            cs(current: "\(arr2kvs[1].key)", expect: "subKey2", des: "subKey2")
            cs(current: arr2kvs[1].value.value as! JSONNumberType, expect: JSONNumberType.int(40), des: "subValue2")
            cs(current: "\(arr2kvs[2].key)", expect: "subKey3", des: "subKey3")
            
            let subValue3 = arr2kvs[2].value.value as! Array<JSON<Any>>
            cs(current: "\(subValue3.count)", expect: "2", des: "subValue3 count")
            
            let subValue30Kvs = subValue3[0].value as! Array<JSONProperty<Any>>
            cs(current: "\(subValue30Kvs.count)", expect: "2", des: "subValue3 kvs count")
            cs(current: "\(subValue30Kvs[0].key)", expect: "sub1Key1", des: "sub1Key1")
            cs(current: subValue30Kvs[0].value.value as! JSONNumberType, expect: JSONNumberType.int(10), des: "sub1Key1 value")
            cs(current: "\(subValue30Kvs[1].key)", expect: "sub1Key2", des: "sub1Key2")
            let subValue30Kvs1ValueKvs = subValue30Kvs[1].value.value as! Array<JSONProperty<Any>>
            cs(current: "\(subValue30Kvs1ValueKvs.count)", expect: "2", des: "sub1Key2 value kvs count")
            cs(current: "\(subValue30Kvs1ValueKvs[0].key)", expect: "sub3Key1", des: "sub3Key1")
            cs(current: "\(subValue30Kvs1ValueKvs[0].value.value as! String)", expect: "sub3Value1", des: "sub3Value1")
            cs(current: "\(subValue30Kvs1ValueKvs[1].key)", expect: "sub3Key2", des: "sub3Key2")
            cs(current: "\(subValue30Kvs1ValueKvs[1].value.value as! String)", expect: "sub3Value2", des: "sub3Value2")

            let subValue31Kvs = subValue3[1].value as! Array<JSONProperty<Any>>
            cs(current: "\(subValue31Kvs[0].key)", expect: "sub1Key1", des: "subValue31Kvs sub1Key1")
            cs(current: subValue31Kvs[0].value.value as! Bool, expect: false, des: "subValue31Kvs sub1Key1 value")
            cs(current: "\(subValue31Kvs[1].key)", expect: "sub1Key2", des: "subValue31Kvs sub1Key2")
            cs(current: subValue31Kvs[1].value.value as! JSONNumberType, expect: JSONNumberType.int(15), des: "subValue31Kvs sub1Key2 value")

            cs(current: "\(arr2kvs[3].key)", expect: "subKey4", des: "subKey4")
            let subValue4 = arr2kvs[3].value.value as! Array<JSON<Any>>
            cs(current: "\(subValue4.count)", expect: "3", des: "subKey4 value array count")
            cs(current: "\(subValue4[0].value as! String)", expect: "value1", des: "subKey4 value array 0 value")
            cs(current: subValue4[1].value as! JSONNumberType, expect: JSONNumberType.double(23.23), des: "subKey4 value array 1 value")
            cs(current: "\(subValue4[2].value as! String)", expect: "value2", des: "subKey4 value array 2 value")

            cs(current: "\(arr2kvs[4].key)", expect: "subKey5", des: "subKey5")
            cs(current: arr2kvs[4].value.value as! JSONType , expect: JSONType.null, des: "subKey5 value")
            
        } catch let e as JSONSyntaxError {
            print("Syntax error at line \(e.line) column \(e.column)!")
        } catch let e {
            print(e.localizedDescription)
        }
    }
    
}

TestJSON.testJSON()


//JSONLexer.test(jsonText: "{\"key1\" \n: false}", expected: [.lBrace(0, 0),
//                                                        .string("key1", 0, 0),
//                                                        .colon(0, 0),
//                                                        .bool(false, 0, 0),
//                                                        .rBrace(0, 0)])