0
$\begingroup$

I understand that deserializing data from a string or binary stream into a data structure is effectively the same parsing. When you deserialize the input string, you use a grammar to create a parse tree from that input, and that parse tree is effectively the encoded data structure.

For example, you may have an array of arrays encoded into a JSON string. When you deserialize that input string, you use the JSON grammar to parse the input string. The parse tree you derive from that input has the same structure as the data that was encoded into the string (in this case an array of arrays).

It seems like most data serialization formats (JSON, YAML, Protobuf) use context free grammars. These grammars are capable of encoding data structures like key value pairs, arrays, and trees.

My question: Are there any data structures that cannot serialized using a context free grammar and require a more powerful grammar such as a context sensitive grammar? Or is it possible to serialize any data structure using a context free grammar, but you may need a longer string than if you were to user a more powerful grammar?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ I think that even the serialization/deserialization of a simple matrix requires a more powerful grammar; how do you check with a CF grammar that all rows (or columns) have the same size? $\endgroup$
    – Marzio De Biasi
    Commented Apr 14, 2023 at 10:58
  • $\begingroup$ More generally, the approach falls short once your data structure has integrity constraints. You can use JSON schema then. But this discussion thread about features lacking in JSON schema refers to things you cannot put into a context-free description (partial ordering, unique keys): github.com/json-schema-org/json-schema-vocabularies/issues/22 $\endgroup$
    – Hermann Gruber
    Commented Apr 18, 2023 at 19:06
  • $\begingroup$ ...and for that reason, today we deserialize data into data transfer objects (DTOs), which don't fulfill any integrity constraints. Typically, all fields are nullable and so on. These DTOs are only then mapped to Business Objects, which have integrity constraints aka business invariants. The integrity constraints are thus validated only in the mapping step, not already in the deserialization. We may say that the shortcomings of JSON govern what the deserialized objects look like (they are dumb DTOs, not smart Business Objects). $\endgroup$
    – Hermann Gruber
    Commented Apr 18, 2023 at 19:14
  • $\begingroup$ Ah! I think I understand now (sorry for the slow reply). If I am understanding correctly, an integrity constraint in this case may be something like, an array of tuples that are all of equal width, or something like that. That is inherently not context free. But you could parse the serialized data, and extract all of the tuples while ignoring their length, then verify after parsing that all the tuples are the same length. So, in the language of the comment above, the data structure with the variable length tuples would be the DTO without any integrity constraints. thanks all! $\endgroup$
    – bcarlborg
    Commented Jul 11, 2023 at 14:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.