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.(I became inspired to this question by the LANGSEC movement, here are some Slides of them.)
Context-free grammar for DAGs?
graphs;context free;formal grammars;modelling;dag