Is there an alternative for the formal language theory that could be used for flowchart diagrams?

Question

I am creating a tool for validating, parsing, and interpreting flowchart diagrams on diagrams.net, and it is necessary 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 a parse tree for a given diagram with a 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 have 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 the 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 characters, lowercase are terminals)

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

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

Specific questions

1. Maybe I am reinventing the wheel and there is already some parsers or theory that could be applied to this task.
2. If there are 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 the lexer visits the same token, but the concept of tying node candidates to tokens seems very unnatural for CFG parsers.

Answer 1

Not sure why you would go straight to CFGs to resolve this when most flowcharts can be represented as rational functions, AKA finite-state transducers. These can be expressed as regular patterns: considering your diagram, it would be expressed as

((1, print['1']) | (2, print['2']) | (3, end))

Looping constructs can obviously be modelled as well

((1, print['1']) | (2, print['2']))* (3, end)

CFG constructs would come into the picture if one or more nodes on the flowchart represented an embedded flowchart. This is exactly analogous to a method in an algorithmic programming language like C or Java, where the flow of control (instruction pointer trace) runs a regular pattern as long as the stack pointer is fixed, and embedded flows (called methods) are represented similarly.

If you are interested, see ginr for a robust regular pattern compiler with support for multidimensional patterns (rational functions and relations).