Efficiently Parsing Data

[Jasper]

Hi,

I have multiple data files which need parsing in realtime so high
performance is *crucial*.

I dont have a format definition, but from what I can see there is a
hierarchy of data.
Each data field is named thus <"name":(the <are mine).
The data can be quoted text or unquoted text or a composite hierarcy field.
Each name/data pair is terminated by a comma unless it is the last in the
group.

A comma can also appear within a quoted text data field.

The hierarchical tokens are open and close braces <{}and open and
close square brackets <[]>.

Thats all there is to it :)

The data describes, say, a school class, so we have a rigid set of data
groups.
eg we have data describing the teacher, data describing the class taken, and
a repeating group describing each kid and grades.

So it would be nice to be able to parse this data out into appropriate
structures.

Below is a snipped of dummy data (in reality there is much more). I have
added the spacing and carriage returns for clarity. The real data has no
white spaces. There may be a variable number of parameters (I think) so it
would be useful to be able to ID and potentially store the variable name
with its data value.

Anyone got any ideas/code snips/references of the best, most speedy (at run
time), way to go about it? A tight, pure c++ solution (with or without the
stl) would be needed.

Thanks in advance for any help
{

"teacher":{
"name":
"Mr Borat",
"age":
"35",
"Nationalit y":
"Kazakhstan "},
"Class":{
"Semester":
"Summer",
"Room":
null,
"Subject":
"Politics",
"Notes":
"We're happy, you happy?"},

"Students":
[
{
"Smith":
[{"First Name":"Mary","s ex":"Female}],
"Brown":
[{"First Name":"John","s ex":"Male}],
"Jackson":
[{"First Name":"Jackie", "sex":"Fema le}]
}
],
"Grades":
[
{
"Test":
[{"grade":A,"poi nts":68},{"grad e":B,"points":2 5},{"grade":C," points":15}],
"Test":
[{"grade":C,"poi nts":2},{"grade ":B,"points":29 },{"grade":A,"p oints":55}],
"Test":
[{"grade":C,"poi nts":2},{"grade ":A,"points":72 },{"grade":A,"p oints":65}]
}
]

}

[Victor Bazarov]

Jasper wrote:

I have multiple data files which need parsing in realtime so high
performance is *crucial*.

I dont have a format definition, but from what I can see there is a
hierarchy of data.

You better come up with a definition, otherwise you're programming
without a spec. Even if you are reverse-engineering, you need to
begin by writing a specification. A good spec gets you half way
to the solution.

Once you have the definition, you can write a flex/yacc grammar for
it, and then you generate the code that handles that file. Simple
as that.

[..]
Anyone got any ideas/code snips/references of the best, most speedy
(at run time), way to go about it? A tight, pure c++ solution (with
or without the stl) would be needed.

I can only say, good luck with your homework!

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask

[Jasper]

You better come up with a definition, otherwise you're programming
without a spec. Even if you are reverse-engineering, you need to
begin by writing a specification. A good spec gets you half way
to the solution.

The only thing that defines the data as far as I can see is it's
hierarchical structure as given by the bracket and square bracket.
The token names and data values are irrelevant to this.

Once you have the definition, you can write a flex/yacc grammar for
it, and then you generate the code that handles that file. Simple
as that.

I'm not writing a compiler. Maybe flex/yacc can help, I'm not familar with
it, but it seems a bit of overkill for what I want.
I wondered if I could adapt a lightweight XML parser, but all I need is a
sort of DOM based on the "{}" and "[]"

>[..]
Anyone got any ideas/code snips/references of the best, most speedy
(at run time), way to go about it? A tight, pure c++ solution (with
or without the stl) would be needed.

I can only say, good luck with your homework!

Homework? What's that supposed to mean?

[anon]

Jasper wrote:

>Once you have the definition, you can write a flex/yacc grammar for
it, and then you generate the code that handles that file. Simple
as that.

I'm not writing a compiler. Maybe flex/yacc can help, I'm not familar with
it, but it seems a bit of overkill for what I want.
I wondered if I could adapt a lightweight XML parser, but all I need is a
sort of DOM based on the "{}" and "[]"

Maybe this can help you:
http://iridia.ulb.ac.be/~fvandenb/tools/xmlParser.html

>

>>[..]
Anyone got any ideas/code snips/references of the best, most speedy
(at run time), way to go about it? A tight, pure c++ solution (with
or without the stl) would be needed.

I can only say, good luck with your homework!

Homework? What's that supposed to mean?

Here is definition:
http://en.wikipedia.org/wiki/Homework

[Jasper]

"anon" <an**@no.nowrot e in message
news:fj******** **@el-srv04-CHE.srvnet.east link.de...

Jasper wrote:

>>Once you have the definition, you can write a flex/yacc grammar for
it, and then you generate the code that handles that file. Simple
as that.

I'm not writing a compiler. Maybe flex/yacc can help, I'm not familar
with it, but it seems a bit of overkill for what I want.
I wondered if I could adapt a lightweight XML parser, but all I need is
a sort of DOM based on the "{}" and "[]"

Maybe this can help you:
http://iridia.ulb.ac.be/~fvandenb/tools/xmlParser.html

Thanks, I'll take a look. If you kow about the tool and XML (I assume) - I
dont.
Will I have to rewrite the parser to handle the brackets or are they part of
the XML spec (in some way)?
(I'm just asking for a "quickstart ").

>>
Homework? What's that supposed to mean?

Here is definition:
http://en.wikipedia.org/wiki/Homework

Oh thats what it is. Thanls

[anon]

Jasper wrote:

"anon" <an**@no.nowrot e in message
news:fj******** **@el-srv04-CHE.srvnet.east link.de...

>Jasper wrote:

>>>Once you have the definition, you can write a flex/yacc grammar for
it, and then you generate the code that handles that file. Simple
as that.
I'm not writing a compiler. Maybe flex/yacc can help, I'm not familar
with it, but it seems a bit of overkill for what I want.
I wondered if I could adapt a lightweight XML parser, but all I need is
a sort of DOM based on the "{}" and "[]"

Maybe this can help you:
http://iridia.ulb.ac.be/~fvandenb/tools/xmlParser.html

Thanks, I'll take a look. If you kow about the tool and XML (I assume) - I
dont.

There is a tutorial, explaining xml format and the library.

Will I have to rewrite the parser to handle the brackets or are they part of
the XML spec (in some way)?
(I'm just asking for a "quickstart ").

I don't know about brackets. Maybe

[Frank Bergemann]

Hi Jasper,

you might want to have a look at boost::serializ ation:

http://boost.org/libs/serialization/doc/index.html

It is a bit tricky to get in touch with 1st.
But once understood, it is straight forward to use.

rgds!

Frank

[Matthias Buelow]

Jasper wrote:

I wondered if I could adapt a lightweight XML parser, but all I need is a

Wrong turn. I know, today it's XML for any conceivable i/o situation all
hyped up so that people hardly know that software can actually exist
that doesn't use XML, but still. You said you want something fast (and
probably simple).

sort of DOM based on the "{}" and "[]"

You can easily write a simple recursive-descent parser for that. A
recursive descent parser is just another name for the intuitive solution.

[Jasper]

"Matthias Buelow" <mk*@incubus.de wrote in message
news:5s******** *****@mid.dfnci s.de...

Jasper wrote:

>I wondered if I could adapt a lightweight XML parser, but all I need is
a

Wrong turn. I know, today it's XML for any conceivable i/o situation all
hyped up so that people hardly know that software can actually exist
that doesn't use XML, but still. You said you want something fast (and
probably simple).

Actually, I have just discovered that the format of the data is JSON.

[AnonMail2005]

On Dec 14, 6:34 am, "Jasper" <notaro...@dont mail.comwrote:

"Matthias Buelow" <m...@incubus.d ewrote in message

news:5s******** *****@mid.dfnci s.de...

Jasper wrote:

I wondered if I could adapt a lightweight XML parser, but all I need is
a

Wrong turn. I know, today it's XML for any conceivable i/o situation all
hyped up so that people hardly know that software can actually exist
that doesn't use XML, but still. You said you want something fast (and
probably simple).

Actually, I have just discovered that the format of the data is JSON.

As someone already mentioned, figuring out the format gets you well on
your
way to a solution. Google JSON C++ and you will see that there are
existing
solutions written to parse that format. So now the next step is to
determine
whether that work is sufficient for your task.