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:
- 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.
- 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
- Maybe I am reinventing the wheel and there is already some parsers or theory that could be applied to this task.
- 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.