[QUIZ] Parsing JSON (#155)

[James_Edward_Gray_II]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

···

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

There has been a lot of talk recently about parsing with Ruby. We're seeing
some parser generator libraries pop up that make the task that much easier and
they've been stirring up interest.

In honor of that, this week's Ruby Quiz is to write a parser for JSON.

JSON turns out to turns out to be a great little example for writing parsers for
two reasons. First, it's pretty easy stuff. You can hand-roll a JSON parser in
under 100 lines of Ruby. The second advantage is that the data format is
wonderfully documented:

  http://json.org/

Since JSON is just a data format and Ruby supports all of the data types, I vote
we just use Ruby itself as the abstract syntax tree produced by the parse.

Feel free to show off your favorite parser generator, if you don't want to roll
your own. Anything goes.

Here are a few tests to get you started:

  require "test/unit"
  
  class TestJSONParser < Test::Unit::TestCase
    def setup
      @parser = JSONParser.new
    end
    
    def test_keyword_parsing
      assert_equal(true, @parser.parse("true"))
      assert_equal(false, @parser.parse("false"))
      assert_equal(nil, @parser.parse("null"))
    end
    
    def test_number_parsing
      assert_equal(42, @parser.parse("42"))
      assert_equal(-13, @parser.parse("-13"))
      assert_equal(3.1415, @parser.parse("3.1415"))
      assert_equal(-0.01, @parser.parse("-0.01"))
  
      assert_equal(0.2e1, @parser.parse("0.2e1"))
      assert_equal(0.2e+1, @parser.parse("0.2e+1"))
      assert_equal(0.2e-1, @parser.parse("0.2e-1"))
      assert_equal(0.2E1, @parser.parse("0.2e1"))
    end
    
    def test_string_parsing
      assert_equal(String.new, @parser.parse(%Q{""}))
      assert_equal("JSON", @parser.parse(%Q{"JSON"}))
      
      assert_equal( %Q{nested "quotes"},
                    @parser.parse('"nested \"quotes\""') )
      assert_equal("\n", @parser.parse(%Q{"\\n"}))
      assert_equal( "a",
                    @parser.parse(%Q{"\\u#{"%04X" % ?a}"}) )
    end
    
    def test_array_parsing
      assert_equal(Array.new, @parser.parse(%Q{[]}))
      assert_equal( ["JSON", 3.1415, true],
                    @parser.parse(%Q{["JSON", 3.1415, true]}) )
      assert_equal([1, [2, [3]]], @parser.parse(%Q{[1, [2, [3]]]}))
    end
    
    def test_object_parsing
      assert_equal(Hash.new, @parser.parse(%Q{{}}))
      assert_equal( {"JSON" => 3.1415, "data" => true},
                    @parser.parse(%Q{{"JSON": 3.1415, "data": true}}) )
      assert_equal( { "Array" => [1, 2, 3],
                      "Object" => {"nested" => "objects"} },
                    @parser.parse(<<-END_OBJECT) )
      {"Array": [1, 2, 3], "Object": {"nested": "objects"}}
      END_OBJECT
    end
    
    def test_parse_errors
      assert_raise(RuntimeError) { @parser.parse("{") }
      assert_raise(RuntimeError) { @parser.parse(%q{{"key": true false}}) }
  
      assert_raise(RuntimeError) { @parser.parse("[") }
      assert_raise(RuntimeError) { @parser.parse("[1,2]") }
  
      assert_raise(RuntimeError) { @parser.parse(%Q{"}) }
      assert_raise(RuntimeError) { @parser.parse(%Q{"\\i"}) }
  
      assert_raise(RuntimeError) { @parser.parse("$1,000") }
      assert_raise(RuntimeError) { @parser.parse("1_000") }
      assert_raise(RuntimeError) { @parser.parse("1K") }
  
      assert_raise(RuntimeError) { @parser.parse("unknown") }
    end
  end

[Eric_Mahurin]

I definitely want to find time to do this one. What would be nice to have
is performance benchmark to compare parsers. Maybe just have a little ruby
script that generates a stream of repeatable random (but valid) JSON.

Eric

···

On Feb 1, 2008 7:55 AM, Ruby Quiz <james@grayproductions.net> wrote:

In honor of that, this week's Ruby Quiz is to write a parser for JSON.

JSON turns out to turns out to be a great little example for writing
parsers for
two reasons. First, it's pretty easy stuff. You can hand-roll a JSON
parser in
under 100 lines of Ruby. The second advantage is that the data format is
wonderfully documented:

       http://json.org/

[7rans]

A bit aside, but it seems a good place to plug the thought: JSON is so
close to valid Ruby syntax. It would be great if Ruby could support
the syntax 100%. Then a parse would be as simple as,

  data = eval(json)

Or, safety levels withstanding, we could conceive a safe_eval(json).

T.

[steve]

Hey guys

This is my first parser. I used Nathan Sobo's Treetop parsing library (
http://treetop.rubyforge.org/, gem install treetop):

http://pastie.caboo.se/146906

require 'treetop'

File.open("json.treetop", "w") {|f| f.write GRAMMAR }

Treetop.load "json"

parser = JsonParser.new

pp parser.parse(STDIN.read).value if $0 == __FILE__

BEGIN {

GRAMMAR = %q{

grammar Json
  rule json
    space json_value space { def value; json_value.value; end }
  end

  rule json_value
    string / numeric / keyword / object / array
  end

  rule string
    '"' chars:char* '"' {
      def value
        chars.elements.map {|e| e.value }.join

      end
    }
  end

  rule char
    !'"' ('\\\\' ( ( [nbfrt"] / '\\\\' / '/' ) / 'u' hex hex hex hex )
/ !'\\\\' .) {

      def value
        if text_value[0..0] == '\\\\'
          case c = text_value[1..1]
          when /[nbfrt]/

            {'n' => "\n", 'b' => "\b", 'f' => "\f", 'r' => "\r", 't' => "\t"}[c]
          when 'u'

            [text_value[2,4].to_i(16)].pack("L").gsub(/\0*$/,'')
          else
            c
          end

        else
          text_value
        end
      end
    }
  end

  rule hex
    [0-9a-fA-F]
  end

  rule numeric
    exp / float / integer
  end

  rule exp
    (float / integer) ('e' / 'E') ('+' / '-')? integer { def value;
text_value.to_f; end }

  end

  rule float
    integer '.' [0-9]+ { def value; text_value.to_f; end }
  end

  rule integer
    '-'? ('0' / [1-9] [0-9]*) { def value; text_value.to_i; end }
  end

  rule keyword
    ('true' / 'false' / 'null') {
      def value

        { 'true' => true, 'false' => false, 'null' => nil }[text_value]
      end
    }
  end

  rule object
    '{' space pairs:pair* space '}' {
      def value

        pairs.elements.map {|p| p.value }.inject({}) {|h,p| h.merge p }
      end
    }
  end

  rule pair
    space string space ':' space json_value space (',' &pair / !pair) {
      def value
        { string.value => json_value.value }

      end
    }
  end

  rule array

    '[' space array_values:array_value* space ']' {
      def value
        array_values.elements.map {|e| e.value }

      end
    }
  end

  rule array_value
    space json_value space (',' &array_value / !array_value) {

      def value
        json_value.value
      end
    }
  end

  rule space
    [ \t\r\n]*
  end

end

}

}

- steve

···

On Feb 1, 2008 8:55 PM, Ruby Quiz <james@grayproductions.net> wrote:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby Talk follow the discussion. Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

There has been a lot of talk recently about parsing with Ruby. We're
seeing
some parser generator libraries pop up that make the task that much easier
and
they've been stirring up interest.

In honor of that, this week's Ruby Quiz is to write a parser for JSON.

JSON turns out to turns out to be a great little example for writing
parsers for
two reasons. First, it's pretty easy stuff. You can hand-roll a JSON
parser in
under 100 lines of Ruby. The second advantage is that the data format is
wonderfully documented:

       http://json.org/

Since JSON is just a data format and Ruby supports all of the data types,
I vote
we just use Ruby itself as the abstract syntax tree produced by the parse.

Feel free to show off your favorite parser generator, if you don't want to
roll
your own. Anything goes.

Here are a few tests to get you started:

       require "test/unit"

       class TestJSONParser < Test::Unit::TestCase
         def setup
           @parser = JSONParser.new
         end

         def test_keyword_parsing
           assert_equal(true, @parser.parse("true"))
           assert_equal(false, @parser.parse("false"))
           assert_equal(nil, @parser.parse("null"))
         end

         def test_number_parsing
           assert_equal(42, @parser.parse("42"))
           assert_equal(-13, @parser.parse("-13"))
           assert_equal(3.1415, @parser.parse("3.1415"))
           assert_equal(-0.01, @parser.parse("-0.01"))

           assert_equal(0.2e1, @parser.parse("0.2e1"))
           assert_equal(0.2e+1, @parser.parse("0.2e+1"))
           assert_equal(0.2e-1, @parser.parse("0.2e-1"))
           assert_equal(0.2E1, @parser.parse("0.2e1"))
         end

         def test_string_parsing
           assert_equal(String.new, @parser.parse(%Q{""}))
           assert_equal("JSON", @parser.parse(%Q{"JSON"}))

           assert_equal( %Q{nested "quotes"},
                         @parser.parse('"nested \"quotes\""') )
           assert_equal("\n", @parser.parse(%Q{"\\n"}))
           assert_equal( "a",
                         @parser.parse(%Q{"\\u#{"%04X" % ?a}"}) )
         end

         def test_array_parsing
           assert_equal(Array.new, @parser.parse(%Q{}))
           assert_equal( ["JSON", 3.1415, true],
                         @parser.parse(%Q{["JSON", 3.1415, true]}) )
           assert_equal([1, [2, [3]]], @parser.parse(%Q{[1, [2, [3]]]}))
         end

         def test_object_parsing
           assert_equal(Hash.new, @parser.parse(%Q{{}}))
           assert_equal( {"JSON" => 3.1415, "data" => true},
                         @parser.parse(%Q{{"JSON": 3.1415, "data": true}})
)
           assert_equal( { "Array" => [1, 2, 3],
                           "Object" => {"nested" => "objects"} },
                         @parser.parse(<<-END_OBJECT) )
           {"Array": [1, 2, 3], "Object": {"nested": "objects"}}
           END_OBJECT
         end

         def test_parse_errors
           assert_raise(RuntimeError) { @parser.parse("{") }
           assert_raise(RuntimeError) { @parser.parse(%q{{"key": true
false}}) }

           assert_raise(RuntimeError) { @parser.parse("[") }
           assert_raise(RuntimeError) { @parser.parse("[1,2]") }

           assert_raise(RuntimeError) { @parser.parse(%Q{"}) }
           assert_raise(RuntimeError) { @parser.parse(%Q{"\\i"}) }

           assert_raise(RuntimeError) { @parser.parse("$1,000") }
           assert_raise(RuntimeError) { @parser.parse("1_000") }
           assert_raise(RuntimeError) { @parser.parse("1K") }

           assert_raise(RuntimeError) { @parser.parse("unknown") }
         end
       end

[Justin_Ethier]

Here is my solution. I do a first pass to tokenize the input and perform
basic syntax checks. Then the expression is fully converted into ruby syntax
and eval is used to load it into Ruby. It passes each of the test cases,
although some improvements could still be made.

class JSONParser
  # Parse a given JSON expression
  def parse(expr)
    # Tokenize the input
    tokens = lex(expr)

    # Load the expression into ruby
    # Takes advantage of the fact ruby syntax is so close to that of JSON.
    # However, it would be nice to have a safe_eval to prevent against
potential injection attacks
    begin
      eval(ruby_convert(tokens))
    rescue SyntaxError, NameError
      raise RuntimeError
    end
  end

  # Converts tokens into a single ruby expression
  def ruby_convert(tokens)
    expr = ""
    for token in tokens
      token = "=>" if token == ":" # Ruby hash syntax
      token = "nil" if token == "null"
      expr += token
    end
    expr
  end

  # Parses the input expression into a series of tokens
  # Performs some limited forms of conversion where necessary
  def lex(expr)
    tokens = []
    i = -1
    while i < expr.size - 1
      tok ||= ""
      i += 1

      case expr[i].chr
        when '[', ']', '{', '}', ':', ','
          tokens << tok if tok.size > 0
          tokens << expr[i].chr
          tok = ""
        # String processing
        when '"'
          raise "Unexpected quote" if tok.size > 0
          len = 1
          escaped = false
          while (len + i) < expr.size
            break if expr[len + i].chr == '"' and not escaped
            if escaped
              case expr[len + i].chr
                when '"', '/', '\\', 'b', 'f', 'n', 'r', 't', 'u'
                else
                  raise "Unable to escape #{expr[len + i].chr}"
                end
            end
            escaped = expr[len + i].chr == "\\"
            len += 1
          end
          raise "No matching endquote for string" if (len + i) > expr.size
          tokens << convert_unicode(expr.slice(i, len+1))
          i += len
        # Number processing
        when '-', /[0-9]/
          len = 0
          while (len + i) < expr.size and /[0-9eE+-.]/.match(expr[len +
i].chr)!= nil
            len += 1
          end
          num = expr.slice(i, len)

          # Verify syntax of the number using the JSON state machine
          raise "Invalid number #{num}" if
/[-]?([1-9]|(0\.))[0-9]*[eE]?[+-]?[0-9]*/.match(num) == nil

          tokens << num
          i += len - 1
        # Skip whitespace
        when ' ', '\t'
        else
          tok << expr[i].chr
      end
    end
    tokens << tok if tok.size > 0
    tokens
  end

  # Convert unicode characters from hex (currently only handles ASCII set)
  def convert_unicode(str)
    while true
      u_idx = str.index(/\\u[0-9a-fA-F]{4}/)
      break if u_idx == nil

      u_str = str.slice(u_idx, 6)
      str.sub!(u_str, u_str[2..5].hex.chr)
    end
    str
  end
end

Thanks,

Justin

[ThoML]

I liked this quiz because it made me look into treetop, ragel and
some
other libraries I wanted to examine a little bit closer for quite a
while now. Anyway, for my (official) solution I took the easy road
and
rely on ruby to do the actual work.

My solution is ruby19 only, since I used the opportunity to explore
some
of the new regexp features. Since it uses eval(), there is a
possibility
for ruby code injection like the ultimatively relieving "#{`sudo rm -
rf
/`}". I think my solution catches such attacks though.

BTW, what do you all think should be the canonic output of the
following
JSON snippet:

json1 = <<JSON
{"a":2,"b":3.141,"TIME":"2007-03-14T11:52:40","c":"c","d":[1,"b",
3.14],"COUNT":666,"e":{"foo":"bar"},"foo":"B\\u00e4r","g":"\\u677e\
\u672c\\u884c\\u5f18","h":1000.0,"bar":"\\u00a9 \\u2260 \\u20ac!","i":
0.001,"j":"\\ud840\\udc01"}
JSON

I get conflicting results between various versions of my solution and
the official ruby19 parser with respect to these utf characters. This
snippet is taken (IIRC) from the ruby-json parser.

Regards,
Thomas.

#!/usr/bin/env ruby19
# Author:: Thomas Link (micathom AT gmail com)
# Created:: 2008-02-01.

# The string (in JSON format) is tokenized and pre-validated. Minor
# replacements are made in order to transform the JSON into valid
ruby
# input. The transformed string is then evaluated by ruby, which will
# throw an exception on syntactic errors.

···

#
# PROBLEMS:
# - The "parser" doesn't per se detect something like {"foo": 1,} or
# [1,2,] since this is valid in ruby. I'm not sure about JSON. Anyway,
I
# included another "invalid" clause in order to catch these cases of
# which I'm not sure how they are handled properly. If you want the
# parser to be more permissive, remove the first "invalid" clause.
#
# REFERENCES:
# http://json.org
# http://www.ietf.org/rfc/rfc4627.txt
class JSONParser

    RXE = /
        \[|\]|
        \{|\}|
        (?<name_sep>:)|
        (?<invalid>,\s*[}\]])|
        ,|
        (?<string>"([^"\\]++|\\(u[0-9a-fA-F]{4}|[bfnrt"\/\\]))*")|
        -?(0|[1-9]\d*+)(\.\d++)?([Ee][+-]?\d++)?(?=\D|$)|
        true>
        false>
        (?<null>null)|
        [[:space:][:cntrl:]]++|
        (?<invalid>.++)
        /xmu

    def parse(json)
        ruby = json.gsub(RXE) do |t|
            m = $~
            if m['invalid'] then invalid(m['invalid'])
            elsif m['null'] then 'nil'
            elsif m['name_sep'] then '=>'
            elsif m['string'] then m['string'].gsub(/#/, '\\\\#')
            else
                t
            end
        end
        begin
            return eval(ruby)
        rescue Exception => e
            invalid(json)
        end
    end

    def invalid(string)
        raise RuntimeError, 'Invalid JSON: %s' % string
    end

end

if __FILE__ == $0
    a = ARGV.join
    p a
    p JSONParser.new.parse(a)
end

[Eric_Mahurin]

       http://json.org/

This doc is missing two things: 1) exactly what is allowed for the top-level
json, and 2) where can whitespace appear. This is more complete:

http://www.ietf.org/rfc/rfc4627.txt

         def test_keyword_parsing

           assert_equal(true, @parser.parse("true"))
           assert_equal(false, @parser.parse("false"))
           assert_equal(nil, @parser.parse("null"))
         end

         def test_number_parsing
           assert_equal(42, @parser.parse("42"))

...

         end

         def test_string_parsing
           assert_equal(String.new, @parser.parse(%Q{""}))

...

         end

The above isn't legal JSON. An array or object (hash) should be at the
top-level. Surround these by brackets and it will be legal.

···

On Feb 1, 2008 7:55 AM, Ruby Quiz <james@grayproductions.net> wrote:

[Pawel_Radecki]

And here's my solution. It passes all given tests but still there are
some tricky cases not handled well (see: code comments). I used
regular expressions extensively but it may not be the best idea in
terms of performance.

Thanks for the quiz!!

#!/usr/bin/env ruby

# Solution to Ruby Quiz #155 (see http://www.rubyquiz.com/quiz155.html)
# by Paweł Radecki (pawel.j.radecki@gmail.com).

$KCODE='UTF-8'
require 'jcode'

class JSONParser

  def parse(input)
    case input
    # TODO: in every case we need to check if pattern matches the
input thoroughly and nothing is left;
    # ex. "[3, 5] Pablos" still not handled well, it passes through
instead of giving exception

    when '' : raise RuntimeError

    # TODO: There needs to be some smart way of choosing whether we
found an object or an array;
    # now object has priority and it may be found instead of an
array

    #object
    when /\{(".+"):(.+)\s*(,\s*(".+"):(.+))+\}/ then
      h = Hash.new
      $&[1...-1].split(/(.*:.*)?\s*,\s*(.*:.*)?/).each do |e|
        a = e.split(/:\s*(\{.*\}\s*)?/);
        h[parse(a.first)] = parse(a.last) unless (a.first.nil? &&
a.last.nil?)
      end
      h
    when /\{\s*(".+")\s*:\s*(.+)\s*\}/ then { parse($1) => parse($2) }
    when /\{\s*\}/ : Hash.new

    #array
    when /\[.+\]/ then $&[1...-1].split(/(\[.*\])?\s*,\s*(\[.*
\])?/).collect{|e| parse(e)}
    when /\[\s*\]/ then []

    #constants
    when /true/ then
      if ($`.strip.empty? && $'.strip.empty?) then true else raise
RuntimeError end
    when /false/ then
      if ($`.strip.empty? && $'.strip.empty?) then false else raise
RuntimeError end
    when /null/ then nil
      if ($`.strip.empty? && $'.strip.empty?) then nil else raise
RuntimeError end

    #string
    when /"([A-Za-z]|(\s)|(\\")|(\\\\)|(\\\/)|(\\b)|(\\f)|(\\n)|(\\r)|
(\\t)|(\\u[0-9a-fA-F]{4,4}))+"/ : $&[1...-1].gsub(/\\"/, '"').gsub(/\
\n/, "\n").gsub(/\\u([0-9a-fA-F]{4,4})/u){["#$1".hex ].pack('U*')}
    when /""/ then ""

    #number
    when /-?(0|([1-9][0-9]*))(\.[0-9]+)?([e|E][+|-]?[0-9]+)?/ then
      if ($`.strip.empty? && $'.strip.empty?) then eval($&) else raise
RuntimeError end
    else
      raise RuntimeError
    end
  end
end

#puts JSONParser.new.parse(ARGV.first)

···

--
Paweł Radecki
e: pawel.j.radecki@gmail.com
w: http://radeckimarch.blogspot.com/

[Eric_Mahurin]

My first solution uses an parser generator API similar to my rubyforge
"grammar" package. The parser generator is only 89 lines (excluding
comment/blank lines). The API is fairly complete to build a variety of
parsers. The same API can be use to build a parser, lexer, preprocessor,
etc (and you could multi-thread them). The reason this is so simple is that
I'm using Ruby as a DSL to specify the language grammar. The file
specifying the JSONParser class is only 58 lines.

Here is the simple Grammar0 parsing DSL class and the JSONParser class using
it:

http://pastie.caboo.se/147074

http://pastie.caboo.se/147075

grammar0.rb (3.78 KB)

jsonparser.grammar0.rb (2.17 KB)

···

On Feb 1, 2008 7:55 AM, Ruby Quiz <james@grayproductions.net> wrote:

In honor of that, this week's Ruby Quiz is to write a parser for JSON.

[Eric_Mahurin]

Here is another solution that uses my (somewhat) optimized 'grammar' package
directly. The JSON grammar is similar to before. The next release will use
an API closer to the simple Grammar0 package.

http://pastie.caboo.se/147078

Also, I ported this to my development code (which is not checked in to CVS
yet), to see the performance. I grabbed all of the current submissions
along with the fjson and json gems to see how they compare in terms of
performance. I used the previous benchmark that I posted. It also revealed
bugs in these submissions. Here is the performance I found on my machine
with ruby 1.8.6:

ch/s author/gem
---- ----------
- oksteev (TreeTop, couldn't get it to parse a string)
- Pawel Radecki (RE, mismatch)
- Justin Ethier (RE lexer + parser, 71: Invalid number 0)
4054 Eric Mahurin (Grammar0, no lexer, no parser generation)
54586 Eric Mahurin (Grammar, no lexer, v0.5)
166041 Thomas Link (RE, ruby 1.9 results)
220289 json
223486 Eric Mahurin (Grammar, no lexer, unreleased)
224823 fjson (uses C extensions)
553081 Eric Mahurin (Grammar, no lexer, unreleased, w/ ruby2cext)
1522250 json (w/ C extensions)

Note that the Grammar variants don't have the advantage of using RegExp
where you get some C performance. But, in my dev code, I'm using ruby2cext
to get a little more performance. You could integrate a RegExp lexer with a
Grammar parser, also.

···

On Feb 1, 2008 7:55 AM, Ruby Quiz <james@grayproductions.net> wrote:

In honor of that, this week's Ruby Quiz is to write a parser for JSON.

[Clifford_Heath3 (Clifford Heath)]

Here's mine, done with Treetop. It also includes a
Readline-based interpretive checker. The generated
parser from Treetop has a slightly different interface,
so I've included JEG's test program with an adapter at
the top.

The nicest thing about using Treetop is how close the
grammar to the JSON spec :-).

I prefer to convert hash keys to symbols, but the test
cases don't allow that so I stripped out my .to_sym's.

Note that the test cases are rather limited in things
like white-space handling (and in fact the JSON spec is
actually incorrect, in that it doesn't define which rules
constitute tokens that may be separated by whitespace!)
Whitespace in Treetop must be handled explicitly, and it's
easy to miss a spot where it should be skipped, so the
tests should cover that.

I welched on full Unicode support as commented in my code,
but there's another test case you should apply, to parse
the string "\\u1234", which should throw an exception.
You'll see that my code is missing that exception, and
will misbehave instead :-).

It wasn't clear from the quiz or the JSON spec whether an
integer is valid JSON. I elected to accept any value, not
just an object or array.

Treetop now uses Polyglot, which loads the generated .rb
file if you've generated it, or the .treetop file if not.

Clifford Heath.

First, the interactive test program:

require 'treetop'
require 'json' # Note that we can require the Treetop file directly.
require 'readline'

parser = JsonParser.new
while line = Readline::readline("? ", [])
   begin
     tree = parser.parse(line)
     if tree
       p tree.obj
     else
       puts parser.failure_reason
     end
   rescue => e
     puts e
     p e.backtrace
     p tree if tree
   end
end
puts

Now, my test adapter:

class JSONParser
   def parse(text)
     parser = JsonParser.new
     p = parser.parse(text)
     raise parser.failure_reason unless p
     p.obj
   end
end

Finally, the grammar itself:

# Treetop grammar for JSON for Ruby Quiz #155 by Clifford Heath.
grammar Json
  rule json
    value
  end

  rule object
    '{' s pairs:pairs? s '}' s
                        { def obj
                            pairs.empty? ? {} : pairs.obj
                          end
                        }
  end

  rule pairs
    member rest:(s ',' s member)*
                        { def obj
                            rest.elements.inject({eval(member.k.text_value) => member.value.obj}) { |h, e|
                                h[eval(e.member.k.text_value)] = e.member.value.obj
                                h
                              }
                          end
                        }
  end

  rule member # key/value pair of an object
    k:string s ':' s value
  end

  rule array
    '[' s e:elements? s ']'
                        { def obj
                            e.empty? ? [] : e.obj
                          end
                        }
  end

  rule elements # elements of an array
    value rest:(s ',' s value)*
                        { def obj
                            rest.elements.inject([value.obj]) { |a, e|
                                a << e.value.obj
                              }
                          end
                        }
  end

  rule value
    s alt:(string / number / object / array
    / 'true' { def obj; true; end }
    / 'false' { def obj; false; end }
    / 'null' { def obj; nil; end }
    )
                        { def obj; alt.obj; end }
  end

  rule string
    '"' char* '"' { def obj
                            eval(
                              # Strip Unicode characters down to the chr equivalent.
                              # Note that I'm cheating here: '"\\u4321"' should assert,
                              # and there are cases that will succeed but corrupt the data.
                              # This should be handled in the "char" rule.
                              text_value.gsub(/\\u..../) { |unicode|
                                eval("0x"+unicode[2..-1]).chr
                              }
                            )
                          end
                        }
  end

  rule char
    '\\' [\"\\\/bfnrt]
    / '\\u' hex hex hex hex
    / (![\\"] .)
  end

  rule hex
    [0-9A-Fa-f]
  end

  rule number
    int frac? exp? { def obj; eval(text_value); end }
  end

  rule int # Any integer
    '-'? ([1-9] [0-9]* / '0')
      { def obj; eval(text_value); end }
  end

  rule frac # The fractional part of a floating-point number
    '.' [0-9]+
  end

  rule exp # An exponent
    [eE] [-+]? [0-9]+
  end

  rule s # Any amount of whtespace
    [ \t\n\t]*
  end

end

[steve]

Here are some extra unit tests i wrote. Let me know if you think any of
them are incorrect (per the spec):

def test_more_numbers
assert_equal(5, @parser.parse("5"))
assert_equal(-5, @parser.parse("-5"))
assert_equal 45.33, @parser.parse("45.33")
assert_equal 0.33, @parser.parse("0.33")
assert_equal 0.0, @parser.parse("0.0")
assert_equal 0, @parser.parse("0")
assert_raises(RuntimeError) { @parser.parse("-5.-4") }
assert_raises(RuntimeError) { @parser.parse("01234") }
assert_equal(0.2e1, @parser.parse("0.2E1"))
assert_equal(42e10, @parser.parse("42E10"))
end

def test_more_string
  assert_equal("abc\befg", @parser.parse(%Q{"abc\\befg"}))
  assert_equal("abc\nefg", @parser.parse(%Q{"abc\\nefg"}))
  assert_equal("abc\refg", @parser.parse(%Q{"abc\\refg"}))
  assert_equal("abc\fefg", @parser.parse(%Q{"abc\\fefg"}))
  assert_equal("abc\tefg", @parser.parse(%Q{"abc\\tefg"}))
  assert_equal("abc\\efg", @parser.parse(%Q{"abc\\\\efg"}))
  assert_equal("abc/efg", @parser.parse(%Q{"abc\\/efg"}))
end

def test_more_object_parsing
  assert_equal({'a'=>2,'b'=>4}, @parser.parse(%Q{{ "a" : 2 , "b":4 }}))
  assert_raises(RuntimeError) { @parser.parse(%Q{{ "a" : 2, }}) }
  assert_raises(RuntimeError) { @parser.parse(%Q{[ "a" , 2, ]}) }
end

···

On Feb 1, 2008 8:55 PM, Ruby Quiz <james@grayproductions.net> wrote:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz
until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby Talk follow the discussion. Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

There has been a lot of talk recently about parsing with Ruby. We're
seeing
some parser generator libraries pop up that make the task that much easier
and
they've been stirring up interest.

In honor of that, this week's Ruby Quiz is to write a parser for JSON.

JSON turns out to turns out to be a great little example for writing
parsers for
two reasons. First, it's pretty easy stuff. You can hand-roll a JSON
parser in
under 100 lines of Ruby. The second advantage is that the data format is
wonderfully documented:

       http://json.org/

Since JSON is just a data format and Ruby supports all of the data types,
I vote
we just use Ruby itself as the abstract syntax tree produced by the parse.

Feel free to show off your favorite parser generator, if you don't want to
roll
your own. Anything goes.

Here are a few tests to get you started:

       require "test/unit"

       class TestJSONParser < Test::Unit::TestCase
         def setup
           @parser = JSONParser.new
         end

         def test_keyword_parsing
           assert_equal(true, @parser.parse("true"))
           assert_equal(false, @parser.parse("false"))
           assert_equal(nil, @parser.parse("null"))
         end

         def test_number_parsing
           assert_equal(42, @parser.parse("42"))
           assert_equal(-13, @parser.parse("-13"))
           assert_equal(3.1415, @parser.parse("3.1415"))
           assert_equal(-0.01, @parser.parse("-0.01"))

           assert_equal(0.2e1, @parser.parse("0.2e1"))
           assert_equal(0.2e+1, @parser.parse("0.2e+1"))
           assert_equal(0.2e-1, @parser.parse("0.2e-1"))
           assert_equal(0.2E1, @parser.parse("0.2e1"))
         end

         def test_string_parsing
           assert_equal(String.new, @parser.parse(%Q{""}))
           assert_equal("JSON", @parser.parse(%Q{"JSON"}))

           assert_equal( %Q{nested "quotes"},
                         @parser.parse('"nested \"quotes\""') )
           assert_equal("\n", @parser.parse(%Q{"\\n"}))
           assert_equal( "a",
                         @parser.parse(%Q{"\\u#{"%04X" % ?a}"}) )
         end

         def test_array_parsing
           assert_equal(Array.new, @parser.parse(%Q{}))
           assert_equal( ["JSON", 3.1415, true],
                         @parser.parse(%Q{["JSON", 3.1415, true]}) )
           assert_equal([1, [2, [3]]], @parser.parse(%Q{[1, [2, [3]]]}))
         end

         def test_object_parsing
           assert_equal(Hash.new, @parser.parse(%Q{{}}))
           assert_equal( {"JSON" => 3.1415, "data" => true},
                         @parser.parse(%Q{{"JSON": 3.1415, "data": true}})
)
           assert_equal( { "Array" => [1, 2, 3],
                           "Object" => {"nested" => "objects"} },
                         @parser.parse(<<-END_OBJECT) )
           {"Array": [1, 2, 3], "Object": {"nested": "objects"}}
           END_OBJECT
         end

         def test_parse_errors
           assert_raise(RuntimeError) { @parser.parse("{") }
           assert_raise(RuntimeError) { @parser.parse(%q{{"key": true
false}}) }

           assert_raise(RuntimeError) { @parser.parse("[") }
           assert_raise(RuntimeError) { @parser.parse("[1,2]") }

           assert_raise(RuntimeError) { @parser.parse(%Q{"}) }
           assert_raise(RuntimeError) { @parser.parse(%Q{"\\i"}) }

           assert_raise(RuntimeError) { @parser.parse("$1,000") }
           assert_raise(RuntimeError) { @parser.parse("1_000") }
           assert_raise(RuntimeError) { @parser.parse("1K") }

           assert_raise(RuntimeError) { @parser.parse("unknown") }
         end
       end

[Paolo_Bonzini]

Here is my try using regexes. I use the "copy-on-write trick" from
the suffix tree quiz: the regex is always anchored to the beginning of
the string using \A, and the matched text is discarded using
post_match. In some places where I don't want to discard I use (?
=...).

Using Eric's benchmark I get 36kb/sec, but I haven't benchmarked any
other solution.

http://pastie.caboo.se/147201

Paolo

[7rans]

Just an FYI solution, JSON is a subset of YAML. So

  data = YAML.load(json)

T.

[Eric_Mahurin]

Here is another solution of mine:

http://pastie.caboo.se/147505

In this one, I just made a fast hand-built recursive-descent/LL(1) parser.
This is the kind of parser that I'm trying to get my 'grammar' package to
approach (using lots of optimizations). It uses no Regexp or ruby eval
(both of which have compiled C to help speed). And yet, it is the fastest
pure-ruby JSON parser we've seen (see the recursive descent line below):

ch/s author/gem
---- ----------
- Pawel Radecki (RE, mismatch)
3214 Justin Ethier (RE lexer + ruby eval, fixed number parsing)
4054 Eric Mahurin (Grammar0, no lexer, no parser generation)
4078 Eric I (Treetop, unicode broken)
6534 oksteev (Treetop, mismatches in benchmark)
8313 Clifford Heath (Treetop, had to remove handling of "\/")
17320 Alexander Stedile (RE)
54586 Eric Mahurin (Grammar, no lexer, v0.5)
137989 Paolo Bonzini (RE)
166041 Thomas Link (RE lexer + ruby eval, ruby 1.9 results)
220289 json
223486 Eric Mahurin (Grammar, no lexer, unreleased)
224823 fjson (uses C extensions)
333368 Thomas Link & Paolo Bonzini (RE + eval, unicode broken)
388670 Eric Mahurin (hand-built recursive descent)
553081 Eric Mahurin (Grammar, no lexer, unreleased, w/ ruby2cext)
1522250 json (w/ C extensions)

···

On Feb 1, 2008 7:55 AM, Ruby Quiz <james@grayproductions.net> wrote:

In honor of that, this week's Ruby Quiz is to write a parser for JSON.

#
# JSON hand-built recursive descent/LL(1) parser, by Eric Mahurin
#
require 'stringio'

class JSONParser

    def parse(s)
        @next = (@io=StringIO.new(s)).getc
        ws
        value(out=)
        ws
        raise("EOF expected") if @next
        raise(out.inspect) unless out.length==1
        out[0]
    end

    def error(expected, found)
        raise("expected #{expected}, found #{found ? ("'"<<found<<?\') :
'EOF'}")
    end

    def value(out)
        if ?\[.equal?(@next)
            # array
            @next=@io.getc
            ws
            a =
            unless ?\].equal?(@next)
                value(a)
                ws
                until ?\].equal?(@next)
                    ?\,.equal?(@next) ? (@next=@io.getc) : error("','",
@next)
                    ws
                    value(a)
                    ws
                end
            end
            @next = @io.getc
            out << a
        elsif ?\{.equal?(@next)
            # object
            @next=@io.getc
            ws
            h = {}
            unless ?\}.equal?(@next)
                ?\".equal?(@next) ? string(kv=) : error("a string", @next)
                ws
                ?\:.equal?(@next) ? (@next=@io.getc) : error("':'", @next)
                ws
                value(kv)
                ws
                h[kv[0]] = kv[1]
                until ?\}.equal?(@next)
                    ?,.equal?(@next) ? (@next=@io.getc) : error("','",
@next)
                    ws
                    ?\".equal?(@next) ? string(kv.clear) : error("a string",
@next)
                    ws
                    ?\:.equal?(@next) ? (@next=@io.getc) : error("':'",
@next)
                    ws
                    value(kv)
                    ws
                    h[kv[0]] = kv[1]
                end
            end
            @next = @io.getc
            out << h
        elsif (?a..?z)===(@next)
            # boolean
            (s="")<<@next
            @next = @io.getc
            while (?a..?z)===(@next)
                s<<@next;@next=@io.getc
            end
            out << case s
                when "true" then true
                when "false" then false
                when "null" then nil
                else error("'true' or 'false' or 'null'", s)
            end
        elsif ?\".equal?(@next)
            string(out)
        else
            # number
            n = ""
            (n<<@next;@next=@io.getc) if ?-.equal?(@next)
            ?0.equal?(@next) ? (n<<@next;@next=@io.getc) : digits(n)
            (?..equal?(@next) ?
                (n<<@next;@next=@io.getc;digits(n);exp(n);true) :
                exp(n)) ?
            (out << n.to_f) :
            (out << n.to_i)
        end
    end

    # Flattening any of the methods below will improve performance further

    def ws
        @next = @io.getc while (case @next;when ?\s,?\t,?\n,?\r;true;end)
    end

    def digits(out)
        (?0..?9)===@next ? (out<<@next;@next=@io.getc) : error("a digit",
@next)
        while (?0..?9)===@next; (out<<@next;@next=@io.getc); end
        true
    end

    def exp(out)
        (case @next;when ?e,?E;true;end) ? (out<<@next;@next=@io.getc) :
            return
        (out<<@next;@next=@io.getc) if (case @next;when ?-,?+;true;end)
        digits(out)
    end

    def string(out)
        # we've already verified the starting "
        @next=@io.getc
        s = ""
        until ?\".equal?(@next)
            if ?\\.equal?(@next)
                @next = @io.getc
                case @next
                when ?\",?\\,?\/ then (s<<@next;@next=@io.getc)
                when ?b then (s<<?\b;@next=@io.getc)
                when ?f then (s<<?\f;@next=@io.getc)
                when ?n then (s<<?\n;@next=@io.getc)
                when ?r then (s<<?\r;@next=@io.getc)
                when ?t then (s<<?\t;@next=@io.getc)
                when ?u
                    @next = @io.getc
                    u = ""
                    4.times {
                        case @next
                        when ?0..?9, ?a..?f, ?A..?F
                            u<<@next;@next=@io.getc
                        else
                            error("a hex character", @next)
                        end
                    }
                    s << u.to_i(16)
                else
                    error("a valid escape", @next)
                end
            else
                error("a character", @next) unless @next
                s<<@next;@next=@io.getc
            end
        end
        @next = @io.getc
        out << s
    end

end

[James_Edward_Gray_II]

Neat idea.

Just FYI though, I'm probably going to focus more on the parsing in the summary that the speed.

James Edward Gray II

···

On Feb 1, 2008, at 10:09 AM, Eric Mahurin wrote:

On Feb 1, 2008 7:55 AM, Ruby Quiz <james@grayproductions.net> wrote:

In honor of that, this week's Ruby Quiz is to write a parser for JSON.

JSON turns out to turns out to be a great little example for writing
parsers for
two reasons. First, it's pretty easy stuff. You can hand-roll a JSON
parser in
under 100 lines of Ruby. The second advantage is that the data format is
wonderfully documented:

      http://json.org/

I definitely want to find time to do this one. What would be nice to have
is performance benchmark to compare parsers. Maybe just have a little ruby
script that generates a stream of repeatable random (but valid) JSON.

[James_Edward_Gray_II]

Conversion is pretty easy and definitely one way to solve this quiz.

James Edward Gray II

···

On Feb 1, 2008, at 10:23 AM, Trans wrote:

A bit aside, but it seems a good place to plug the thought: JSON is so
close to valid Ruby syntax. It would be great if Ruby could support
the syntax 100%.

[PA1 (PA)]

Brilliant!

But perhaps the other way around: bridge the JSON syntax discrepencies to valid Ruby syntax, e.g:

eval( to_ruby( json ) )

Cheers,

PA.

···

On Feb 1, 2008, at 5:23 PM, Trans wrote:

A bit aside, but it seems a good place to plug the thought: JSON is so
close to valid Ruby syntax. It would be great if Ruby could support
the syntax 100%. Then a parse would be as simple as,

data = eval(json)

[a11 (-a)]

cfp2:~ > cat a.rb
require 'rubygems'
require 'json'

def random_json
   case rand
     when 0 ... 1/3.0
       top = Hash.new
       add = lambda{|obj| top[obj] = obj}
     when 1/3.0 ... 2/3.0
       top = Array.new
       add = lambda{|obj| top.push obj}
     when 2/3.0 .. 1
       top = String.new
       add = lambda{|obj| top += obj}
   end
   10.times{ add[rand.to_s] }
   top.to_json
end

puts random_json

cfp2:~ > for i in `seq 1 3`;do ruby a.rb ;done
"0.3786779826911330.2475380034343990.7052927081471540.2056530009384740.1367079874315110.6433874613518640.5329060341883540.8932613322492760.9233991888762390.561470121133217
"
{"0.758942077040095":"0.758942077040095","0.740998718448961":"0.740998718448961","0.581975309640819":"0.581975309640819","0.471066491788047":"0.471066491788047","0.150752108985123":"0.150752108985123","0.679712508205116":"0.679712508205116","0.265444532310993":"0.265444532310993","0.43229805237576":"0.43229805237576","0.880407977937905":"0.880407977937905","0.91896885679168":"0.91896885679168"}
["0.140526101058637
","0.647296447390116
","0.419874655921874
","0.67320818546074
","0.847043108967541
","0.479385904117001
","0.378678170026127
","0.707315391952609","0.26064520446906","0.460184583302929"]

a @ http://codeforpeople.com/

···

On Feb 1, 2008, at 9:09 AM, Eric Mahurin wrote:

  Maybe just have a little ruby
script that generates a stream of repeatable random (but valid) JSON.

--
we can deny everything, except that we have the possibility of being better. simply reflect on that.
h.h. the 14th dalai lama

[ThoML]

A bit aside, but it seems a good place to plug the thought: JSON is so
close to valid Ruby syntax. It would be great if Ruby could support
the syntax 100%.

I hoped ruby19 would already support this use of colons as in {"key":
"value"} but unfortunately not.