3
$\begingroup$

I am creating a tool for validating, parsing and interpreting flowchart diagrams on diagrams.net, and it is neccessary to give users an opportunity to define a set of rules for the diagram. So, in the end I want to achieve something like ANTLR for diagrams with the following features:

  • Some kind of DSL for defining parser and lexer rules
  • Building parse tree for given diagram with given set of rules
  • Traversing the parse tree and generating code from it

I failed to find some existing tools or theoretic models for such a task, so currently I am trying to apply context-free grammars for this task, but the problem is that CFGs and all the theory and tooling utilizing them interprets the input as a sequence of tokens, and flowchart diagrams has two major differences from that:

  1. In texts, each token, except EOF, is followed by exactly one token. In flowcharts, after one token may come multiple tokens, for example after the Decision Element.
  2. There can be loops in flowcharts.

Branches support

I managed to resolve first problem – created a top-down parser that can validate and parse a diagram with branching using an extended form of CFG, where production rules can be defined as $\alpha \to \beta$, where $\alpha \in V$, $\beta \in (V\cup V'\cup \Sigma)^*$.

$^*$ - Kleene star operation, $\Sigma$ - set of terminals, $V$ - set of non-terminals, $V' = \{f(v) : v \in V\}$, where $f(v)$ is special non-terminal that represents one or more branches of non-terminal $v$

For example: (capitals are non-terminal charcters, lowercase are terminals)

CONDITION -> decision ACTION'
ACTION -> process
ACTION -> end

There, first rule describes that decision token (rhombus) must be followed by 1 or more branches of ACTION. This grammar could process diagrams like this one:

Diagram example

Specific questions

  1. Maybe I am reinventing the wheel and there is already some parsers or theory that could be applied for this task?
  2. If there is no current solutions, how could I implement loops support? I am currently looking into the idea of keeping a map token -> AST node candidates, and reevaluating the candidates each time lexer visits the same token, but the concept of tying node candidates to tokens seems very unnatural for CFG parsers.
$\endgroup$
2
  • 1
    $\begingroup$ Perhaps you would be interested in context-free graph grammars or regular tree grammars? $\endgroup$
    – D.W.
    May 13 at 20:07
  • $\begingroup$ @D.W. Thanks for pointing out weak points of the question, I edited it to be more specific. Context-free graph grammars from the first glance look like exactly what I need here. $\endgroup$ May 15 at 12:38

0

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.