2

You can create a data structure such as a Parsing Expression Grammar (PEG) that will be used to parse:

string -> object

You can then write a function that iterates through the object's properties and serializes back into a string, or will stringify it:

object -> string

I haven't seen any data structures for defining how stringifying would work (similar to a PEG), but I think this would be possible.

What I'm wondering is if you can create one data structure to do both. That is, define a grammar or something that will allow you to both parse and serialize some text. There would still be two functions (parse and stringify), but they would both take the same data structure / grammar thingy to figure out what to do automatically.

I am asking because I feel like I've read before that the whole original purpose of grammars was for language generation rather than parsing, and parsing only came after. I can imagine a data structure to generate strings, but I'm wondering if it can get more finely tailored so you can give it a data structure (say a parsed URL object), and it would generate the URL string from it without having to write the custom serialization code. The data structure / grammar thing would do the stringification for you. Wondering if that's possible.

Or maybe it's just better to have two data structures. Just trying to think in terms of reducing duplication.

Improve this question
9
  • What? This doesn’t make any sense. Types by definition define the legal values a variable can have. Product types allow you to combine multiple variables. Generating the possible strings is simply iterating the possible values (in string form; all possible combinations for product types). That doesn’t require any fancy data structure, and is near useless in any case.
    – Telastyn
    Commented May 24, 2018 at 2:55
  • 1
    If the mapping from strings to tokens, as well as the rules for creating an abstract syntax representation from the sequence of tokens, are both bijective, then an algorithm can revert the lexical and grammatical analysis based on data structures representing the mapping and rules. All other cases require analysis and then usually serialisation code is the best option, because you have to know whether your alternatives can all be represented by a normal form (which no algorithm can guess from your injective rules, although in theory the data can be extended to include such information).
    – unified modeling sandwich
    Commented May 24, 2018 at 3:12
  • Generalized serialization/deserialization of objects (without having to know the type being serialized/deserialized ahead of time) is already a thing in several programming languages. It is accomplished using a variety of techniques, including Reflection.
    – Robert Harvey
    Commented May 24, 2018 at 4:00
  • Please explain more that sounds like what I'm looking for :)
    – Lance Pollard
    Commented May 24, 2018 at 4:05
  • What programming language are you using?
    – Robert Harvey
    Commented May 24, 2018 at 4:06

1 Answer 1

Reset to default
3

... that will be used to parse: string -> object

Em, no. The output of a parser is not an "arbitrary object". It is parse tree (and a boolean indicating if the input string matched the given grammar or not).

I haven't seen any data structures for defining how stringifying would work (similar to a PEG), but I think this would be possible.

That is because there is no datastructure needed to stringify a parse tree (except the tree itself). Just do a depth-first in-order tree traversal and concatenate the string representation of the nodes - that should result in the same string as you started with (assumed your parser did not swallow characters like whitespaces from the tree).

Improve this answer
1
  • 1
    Non-terminal nodes of parse trees contain essential parts of the original input, such as operators. They need to be stringified as well. You're describing a token list, not a parse tree. And most of the time, grammars allow for different inputs to result in the same parse tree, so the grammar itself (plus lexer information) cannot be used to re-stringify without additional information, at that was the original question.
    – unified modeling sandwich
    Commented May 28, 2018 at 19:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.