awwx.ws

Creating a parser combinator library to parse JSON

seq

The seq combinator takes a list of parsers, and applies them one after another to the input. The whole sequence only succeeds if all of the parsers succeed. And, for the return value, I want to get a list of what each of the parsers returned.

OK, so I’m going to need to loop through the parsers. The parse position is going to change each time, as each parser in turn successfully matches some input. And I’ll need a variable for the accumulated result, which starts off as nil:

(def seq parsers
  (fn (p)
    ((afn (p parsers a)
       ...)
     p parsers nil)))

If I’ve gotten through all the parsers, the parsers list will now be empty, which means all the parsers matched successfully, and so I can return the result. I’ll be cons’ing up the result as I go through the loop, so I’ll use rev to get “(1 2 3)” instead of “(3 2 1)”:

(def seq parsers
  (fn (p)
    ((afn (p parsers a)
       (if parsers
            'do-something-with-the-next-parser
            (return p rev.a)))
     p parsers nil)))

Hey, I’m making progress! I can already call seq on an empty parser list, and have it successfully match no things and return an empty list:

arc> (show-parse (seq) "123")
returning: nil remaining: 123
nil

Impressive, yes? :-)

If there are some more parsers left, I need to call the next one, getting the new parse position and its return value. I’ll use iflet, so if the parser fails to match and returns nil, I’ll fall out of the whole loop returning nil from the parser created by seq, so that if any of the parsers fail then the entire match fails:

(iflet (p2 r) (car.parsers p)
  ...)

If the match succeeds, then I need to loop again with the new parse position, the next parser on the list, and add the return value to the accumulator:

(iflet (p2 r) (car.parsers p)
  (self p2 cdr.parsers (cons r a)))

Putting it all together, I get:

(def seq parsers
  (fn (p)
    ((afn (p parsers a)
       (if parsers
            (iflet (p2 r) (car.parsers p)
              (self p2 cdr.parsers (cons r a)))
            (return p rev.a)))
     p parsers nil)))

Let’s try it out:

arc> (show-parse (seq json-number-char
                      json-number-char
                      json-number-char)
                 "123")
returning: (#\1 #\2 #\3) remaining: 
nil

Questions? Comments? Email me andrew.wilcox [at] gmail.com