On Mon, Oct 4, 2010 at 7:45 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Yeah. Joseph seems to be confusing copyrights with patents. The idea
> of "parse JSON with bison/flex" is not patentable by any stretch of the
> imagination.
What I meant is, anyone who sets out to write a JSON parser with
bison/flex is probably going to end up with something very similar to
jsonval even without looking at it.
> But having said that, I wonder whether bison/flex are really the best
> tool for the job in the first place. From what I understand of JSON
> (which admittedly ain't much) a bison parser seems like overkill:
> it'd probably be both bloated and slow compared to a simple handwritten
> recursive-descent parser.
I agree, and also because JSON isn't a moving target. However, in my
opinion, the differences in quality between a bison parser and a
handwritten parser are to small to be a big deal right now.
A bison parser is probably slower and bigger than a simple
hand-written one, but I haven't benchmarked it, and it's probably not
worth benchmarking at this point.
In correctness, I suspect a bison parser and a hand-written one to be
about the same. Both pass the same army of testcases I built up while
writing my original JSON patch. Granted, there could be weird
semantics of bison/flex that make the parser wrong in subtle ways (for
instance, the . regex char doesn't match \n and EOF), but there can
also be weird errors in hand-written code. Pick your poison.
In safety, a handwritten recursive descent parser could stack overflow
and crash the server unless the proper guards are in place (e.g if
someone tries to encode '[[[[[[...' as JSON). bison guards against
this (chopping the maximum depth of JSON trees to 9997 levels or so),
but I don't know if the real stack is smaller than bison thinks it is,
or if bison uses its own buffer. A handwritten parser could also
accept trees of any depth using a manually managed stack, but it
wouldn't do much good because code that works with JSON trees (e.g.
json_stringify) is currently recursive and has the same problem. In
any case, I think limiting the depth of JSON, to something generous
like 1000, is the right way to go. The RFC allows us to do that.
In my opinion, the path of least resistance is the best path for now.
If we use the bison parser now, then we can replace it with a
hand-written one that's functionally equivalent later.
Joey Adams