# Is building an event-based parser possible/reasonable in Mathematica (WL)?

Too long? Go to Problems section

## Background

I like to learn by doing small, sometimes artificial, projects. Among other things I had 'parsers', and 'stream methods / streams in MMA' on my to learn list.

So I decided to join it and learn that by building a streaming api for JSON files. We will get to what that means.

I did some research and I think I know what I need to do but I don't see how this can be done in reasonable manner in Mathematica.

## What I want to build

Shortly, such api/parser advances step by step (if told to) through a stream and produces events on which user can do something. Events are specific for a parser/format, so in JSON case they can be 'objectBeginning', 'objectEnd', 'keyName', 'stringValue', 'trueValue' etc.

Simple use case, again shortly, 'parse untill you find a keyName "metadata", read value, close stream'.

The point is, all that is done without reading whole JSON into memory.

https://javaee.github.io/jsonp/

http://www.saxproject.org/event.html

## How I want to build that

I decided to start by more or less imitate javax.json mentioned above.

So there should be a next[stream_] method which should succesively return events:

The parser can generate the following events: START_OBJECT, END_OBJECT, START_ARRAY, END_ARRAY, KEY_NAME, VALUE_STRING, VALUE_NUMBER, VALUE_TRUE, VALUE_FALSE, and VALUE_NULL.

The exact form does not matter because I failed to even Read it properly :)

## Problems

After reading about Read, DefineInputStringMethod (tutorial/StreamMethods) and friends, I came to a conclusion that this framework is not suited for this or I just can't grasp it, thus the question, I want to understand :)

• I don't know how to efficiently implement Read e.g. a STRINGValue

which should return content separated by quotes ("string") but we have to keep in mind that it can contain escaped quotes. ("str \" ing")

E.g.:

 Read[StringToStream["\"start \\\"end\""], Word, WordSeparators -> {"\""}]


"start \" (terminated too quickly)

One could go with ReadString

  ReadString[StringToStream["\"start \\\"end\""], Except["\\"] ~~ "\""]


"\"start \\"en"

but we lose the last character, represented by Except, as separators are not part of objects. So we need to go back for it. You can already suspect you are doing something wrong when such basic operation gets so messy.

I don't even proceed with this because we need Skip methods and there is no SkipString to support this type.

Escaped tokens/separators seem to be a core of this problem, otherwise e.g. TRUEValue can be implemented by putting "true" inside TokenWords options.

• Speed

While memory is what we care about, we can't spend 2 minutes on parsing/skipping 10MB of JSON. And you can't Compile, even procedural style, code with While Read etc. So it is too high level to be efficient.

I could solve STRINGValue problem by reading Character by Character, handling escaped quotes and all that but this will take forever.

• DefineInputStreamMethod

I don't really see how this could help, it rather seems to provide an api to 'preprocess' streams. Unless I'm mistaken it does not have tools to add new types, easily emmit events or speed up parsing process but taking it 'deeper'.

Let me know if I am wrong.

## Questions

I guess this boils down to what is a reasonable way to do this?

• If my approach is correct:

• How to add low level types support for Read

• How to write fast Read based procedures (ReadList and friends can't be used as we don't see the content in advance

• And if not

• Is there a more idiomatic approach?

• If there is not, why? Isn't that something fundamental for a language?

• Am I right thinking that linking external libraries only make sense if they support all features you need, otherwise building on top will lead to problems outlined in Problems/speed?

Keywords:

event based parser, SAX, SAX2, streaming interface, push parser

Related:

Wrapping a C library with a streaming interface

• My best suggestion would be to build a back-end Association to cache data about, e.g. whether you've got unmatched braces, and use some combination of Read up to various potential tokens, to build a string that can be tested against with a compiled regex and to parse it out like that. Then provide events for when these patterns match. It'd be a bit tedious, but I can see it working with okay performance. – b3m2a1 Oct 17 '17 at 6:54
• @b3m2a1 if I get it right that only makes sense if you plan to parse/work with a specific file more than once, right? For one time data extraction it is not very useful. – Kuba Oct 18 '17 at 8:29
• I wasn't actually necessarily proposing extracting the data. I was picturing parsing some JSON or XML block, where you need to know what part of the block you're in, hence tracking like quantities of open and close brackets. Then I figured read up until you hit any of "{"|"}"|"\""|":" and check to see if you have a complete token or block or whatever, and continue on like that. That's basically the lexing side of things. Then your parser would apply rules to those tokens / blocks. I haven't thought through all of the performance considerations of this strategy though. It might be unworkable. – b3m2a1 Oct 18 '17 at 8:35
• @b3m2a1 So you suggest the logic for the lexer, I think this is not the issue here. Also, notice that all those tokens can be escaped by being in a string so more (not very) sophisticated state tracking is needed and the point of the question is, it seems there are no tools for that. – Kuba Oct 18 '17 at 8:41
• Yeah my backend suggestion was basically to handle all of those escapes and such complications. I agree there are no good tools for it, but I'd argue it's always a bit of a pain to do these kinds of things, based on work I've done in python with DSLs and mini-interpreters. Leonid's streaming work might provide a good backbone for future support of this type of feature, but who knows how far in the future that'd be. – b3m2a1 Oct 18 '17 at 8:46

### Note:

If you want this type of parser added for JSON, I think WRI could do it easily. They already have DeveloperReadRawJSONStream so I think adding some event-based parsing to that wouldn't be too much to ask

This has been kicking around my for the past few days, so here's a quick example of what I discussed in my comment. It is by no means complete, but it's a start.

We'll simply define a bunch of different tokens to look for and handle each of them differently and then layer a reader on top of that. Here's the core code for that:

jStreamReader[stream : _String | _File | _InputStream] :=
Module[{
jStreamData
},
jStreamData~ClearAttributes~Temporary;
jStreamData =
<|
"InString" -> False,
"BlockDepth" -> <|Association -> 0, List -> 0,
CompoundExpression -> 0|>,
"BlockStack" -> {},
"Cache" -> InternalBag[],
"CacheStack" -> {},
"CachePush" ->
Function[
InternalStuffBag[jStreamData["Cache"], #]
],
"CacheRecurse" ->
Function[
jStreamData["CacheStack"] = {jStreamData["CacheStack"],
jStreamData["Cache"]};
jStreamData["Cache"] = InternalBag[];
],
"CacheReset" ->
Function[
With[{c = jStreamData["CacheStack"]},
jStreamData["CacheStack"] = c[[1]];
jStreamData["Cache"] = c[[2]];
]
],
"CachePart" ->
Function[
InternalBagPart[jStreamData["Cache"], #]
],
"CacheClear" ->
Function[
jStreamData["Cache"] = InternalBag[];
],
"CacheDump" ->
Function[
With[{data = InternalBagPart[jStreamData["Cache"], All]},
jStreamData["Cache"] = InternalBag[];
data
]
],
"Stream" ->
Replace[stream, {
_String :> StringToStream[stream]
}]
|>;

jStreamData[p] = v;

StreamPosition@jStreamData["Stream"];

SetStreamPosition[jStreamData["Stream"], p];
(
Close@jStreamData["Stream"];
jStreamData // Remove
);
]
$jStreamBracketTokenIndicators = {"{", "}", "[", "]", "(", ")"};$jStreamChunkTokenIndicators =
{",", ":"};
$jStreamStringTokenIndicators = {"\""};$jStreamInStringTokenIndicators =
{"\\\"", "\""};
$jStreamPossibleTokenIndicators = Alternatives @@ Join[$jStreamStringTokenIndicators,
$jStreamBracketTokenIndicators,$jStreamChunkTokenIndicators
];
$jStreamInStringTokenIndicators = Alternatives @@$jStreamInStringTokenIndicators;
$jStreamBracketTokenIndicators = Alternatives @@$jStreamBracketTokenIndicators;
$jStreamBracketMap = <| "{" -> {Opening, Association}, "}" -> {Closing, Association}, "[" -> {Opening, List}, "]" -> {Closing, List}, "(" -> {Opening, CompoundExpression}, ")" -> {Closing, CompoundExpression} |>; jStreamReadToSep[reader_] := Module[{ sp = StreamPosition@reader, strm = reader["Stream"], ret, sep }, ret = With[{test = Read[strm, Character]}, If[test === EndOfFile, Throw[EndOfFile]]; SetStreamPosition[strm, sp]; If[reader["InString"], If[StringMatchQ[test,$jStreamInStringTokenIndicators] ||

StringMatchQ[
test <> "\"", $jStreamInStringTokenIndicators], "", ReadString[strm,$jStreamInStringTokenIndicators]
],
If[StringMatchQ[test, $jStreamPossibleTokenIndicators], "", ReadString[strm,$jStreamPossibleTokenIndicators]
]
]
];
sep =
],
];
If[StringMatchQ[sep, $jStreamBracketTokenIndicators] && StringLength@StringTrim[ret] > 0, SetStreamPosition[reader, StreamPosition[reader] - 1]; sep = "" ]; {ret, sep, sp} ]; jStreamHandleSepData[reader_, {ret_, sep_, sp_}] := With[{sepData =$jStreamBracketMap[sep]},
Which[
sep === "",
{ret, sep, Value, Expression},
sep === ":",
{ret, sep, Key, None},
sep === ",",
{ret, sep, Value, Expression},
{ret, sep, None, String},
sep === "\"",
{ret, sep, None, Continue},
sep === "\\\"",
{ret, sep, None, Continue},
sepData[[1]] === Closing,
];
{ret, sep, sepData, Expression},
sepData[[1]] === Opening,
{ret, sep, sepData, None},
True,
{ret, sep, sepData, Expression}
]
];
Block[{segs},
segs = {None,
While[segs[[-1, -1]] === Continue,
segs = {segs,
];
Cases[segs, {_String, _String, __}, \[Infinity]]
]
jStreamBuildToken[segs_] :=
{
Switch[segs[[-1, -1]],
None, Null,
String,
{
ToExpression@StringJoin@segs[[All, ;; 2]],
String
},
_,
{
Replace[StringTrim@StringJoin@segs[[-1, 1]], {
"null" -> Null,
e_ :> ToExpression@e
}],
segs[[-1, -1]]
}
],
Replace[segs[[-1, -2]], {
{o_, "{}"} :> {o, Association},
{o_, "[]"} :> {o, List},
{o_, "()"} :> CompoundExpression
}]
}



This generates a reader symbol that tracks the data in a mutable way, allowing it to act like a prettied-up stream in many ways.

Here's support for reading JSON data types:

(*Different types of read processors *)

jStreamRead[reader_, Key] :=
{Null, Key} :>
{a_, String | Expression} :> a
],
EndOfFile :> EndOfFile,
e_ :>
(
)
}];

{_, {Closing, Association}} :>

{Null, Key} :>
(
(
)
];
),
EndOfFile :> EndOfFile,
e_ :>
(
)
}];
{_, {Closing, List}} :>
{{v_, _}, None | Value} :>
(
),
{Null, {Opening, t_}} :>
(
];
),
EndOfFile :> EndOfFile
}];

{_, {Closing, CompoundExpression}} :>
$wrapper @@ reader["CacheDump"], {Null, {Opening, t_}} :> jStreamRead[reader, t], {{v_, _}, None | Value} :> ( reader["CachePush"][v]; jStreamRead[reader, CompoundExpression] ), {Null, {Opening, t_}} :> ( reader["CachePush"][ jStreamRead[reader, t] ]; jStreamRead[reader, CompoundExpression] ), EndOfFile :> EndOfFile }]; jStreamRead[reader_, Value] := Replace[jStreamReadToken[reader], { {{a_, _}, None | Value} :> a, {Null, {Opening, t_}} :> jStreamRead[reader, t], EndOfFile :> EndOfFile, e_ :> ( reader["CacheAdd"][e]; jStreamRead[reader, Value] ) }]; jStreamRead[reader_, KeyValuePattern] := jStreamRead[reader, Key] -> jStreamRead[reader, Value]; jStreamRead[reader_, Automatic] := Replace[jStreamReadToken[reader], { {Null, {Opening, t_}} :> jStreamRead[reader, t], {{a_, _}, None | Value} :> a }]; jStreamRead[reader_, "Token"] := jStreamReadToken[reader];  We'll then layer a more convenient interface on top of that: JSONStream[strm : _String | _File | _InputStream] := JSONStream[jStreamReader[strm]]; JSONStreamRead[JSONStream[s_Symbol], type_: "Token"] := Replace[jStreamRead[s, type], EndOfFile | (_ -> EndOfFile) :> JSONStreamClose[JSONStream[s]] ]; JSONStreamClose[JSONStream[s_Symbol]] := ( Close@s; Remove[s]; EndOfFile ); JSONStream /: Read[JSONStream[s_Symbol], type___] := JSONStreamRead[JSONStream[s], type]; JSONStream /: Close[JSONStream[s_Symbol]] := JSONStreamClose[JSONStream[s]]; Format[JSONStream[ s_Symbol?(MatchQ[#["Data"]["Stream"], _InputStream] &)]] := With[{is = s["Data"]["Stream"]}, RawBoxes@ BoxFormArrangeSummaryBox[ "JSONStream", JSONStream[s], BoxFormGenericIcon[InputStream], { BoxFormSummaryItem[{"Name: ", Replace[is[[1]], f_String :> FileNameTake@f]}], BoxFormSummaryItem[{"Unique ID: ", is[[2]]}] }, { BoxFormSummaryItem[{"Open: ", Dynamic[Options[is] =!= {}, UpdateInterval -> 1 ] }] }, StandardForm ] ]  Finally generate a JSON sample and we can start reading tokens: $jsSample =
"\n" <>
ExportString[
Prepend[ExampleData[{"Dataset", "Planets"}],
"\"EscapedName\"" -> <|"asd" -> "whee", "number" -> 10|>
],
"JSON"
];

json = JSONStream[\$jsSample]


Then here's what Read looks like on it:

Read@json

{Null, {Opening, Association}}

{{{"\"EscapedName\"", String}, None}, {Null,
Key}, {Null, {Opening, Association}}, {{"asd", String},
None}, {Null, Key}, {{"whee", String}, None}, {{Null, Expression},
Value}, {{"number", String}, None}, {Null, Key}, {{10, Expression},
Value}}


Here's using the data type support:

Table[Read[json, KeyValuePattern], 3] // AbsoluteTiming

{0.015792, {"Mercury" -> <|"Mass" -> "330104000000000000000000. kg",
"Radius" -> "2439.7 km", "Moons" -> <||>|>,
"Venus" -> <|"Mass" -> "4867320000000000000000000. kg",
"Radius" -> "6051.9 km", "Moons" -> <||>|>,
"Earth" -> <|"Mass" -> "5972198600000000000000000. kg",
"Moons" -> <|"Moon" -> <|"Mass" -> "73459000000000000000000. kg",

Currently we have Key, Value, KeyValuePattern, Association, List, and "Token" as supported types
• Not handling escapes was just a minor bug (it was written to do so). That I can patch quickly. Getting better event handling (e.g. Key` with associated key value) is a bit tougher, but it could be implemented pretty naturally out this, given the OO way the stream data is handled. The hard part, I think, will be finding the appropriate stream position for a given chunk of data, but I think I can manage that. – b3m2a1 Oct 20 '17 at 17:36