I'm looking for a "safe" representation of DAGs. With "safe" representation I mean that it can be described by a context-free grammar. Ideally, this grammar would be suitable for a simple LR parser.
The same problem for trees instead of DAGs is already solved: Just use one of the many well-known tree representations such as s-expressions or JSON, which are all context-free with nice, efficient parsers.
But how to approach that for DAGs instead of trees?
The naive approach is a list of nodes, where each node contains refereces to their parent (head) nodes. Ignoring referential integrity, this would be a regular language. But then I need to check that all references point back to an already-parsed node. How do I ensure this? Is there a clever PDA construction for that?
Or, do I need a totally different representation of DAGs?
Or, is any generic representation of DAGs doomed to be context-sensitive? If so, is there a proof for that?
I'm aware that in natural language processing, there do exist parsers which output a "parse DAG" instead of a parse tree. But I do not see how these may help in this particular problem. Maybe these are of no help here, but their existence gives me a feeling that this problem might have a solution.