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.)

  • 1
    $\begingroup$ I don't have a proof right now, but I think that DAGs have no context-free representation. For practical purpose, regular syntax with a static semantics that can be efficiently checked (linear parsing time seems achievable) should be sufficient. It comes down to this: what do you mean resp. want to achieve by "safe"? $\endgroup$ – Raphael Mar 29 '16 at 6:50
  • 1
    $\begingroup$ Context-Free Graph Grammars by J. Engelfriet (1997) may be of interest. $\endgroup$ – Raphael Mar 29 '16 at 6:51
  • $\begingroup$ Minor typo, fixed. $\endgroup$ – Raphael Mar 30 '16 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.