kalatchev commented 1 year ago

Proposal

Mermaid.js should implement Extended Backus–Naur form (EBNF) for syntax diagrams.

There is an OS project like this - Railroad Diagram Generator

Another code I've found (php).

Use Cases

For me, mainly in documentation and wikis in GitHub.

Screenshots

Code Sample

No response

Yokozuna59 commented 1 year ago

I just want to point out that there is one written in typescript: https://github.com/CJex/regulex. It might be easier to take inspiration from those written in Java or PHP.

@sidharthv96 Can you please add Type: New Diagram label to this issue?

Yokozuna59 commented 12 months ago

I think using railroad keyword is better. Anyway there is an open issue referring to the same thing #2142.

nirname commented 12 months ago

I used to implement something like my own version of bison, but I used graphviz for drawing purposes. There was no other similar tools that would be so easy to use back then. Textual representation occurred to be even more simple than its API.

Basically, what you are asking about is a state diagram, but with special syntax. Based on grammar we can get a FA and then display it. You may need to split it (draw separate graph for NON-TERMINALS) or unite it to get whole graph describing grammar (with NON-TERMINALS as nodes). But that is not limited to this. The main complexity is about NFA/DFA conversion algorithms (you can convert them back and forth). In DFA one transition is marked only by one TERMINAL whereas in NFA it can be marked by many.

What can be confusing a little is that those rectangles are actually transitions (not nodes)

Resulting state machine can be a little different from the grammar, because it can be optimized.

So I would split this task as following:

parsing BNF / EBNF to a table of states and transitions
get the proper structure of it (NFA/DFA or smth that represents grammar exactly as it is written)
display it using one of the existing layout algorithms

I need to research a little bit on that subject to revive something in memory, and probably I'll take it as next type of diagram

nirname commented 12 months ago

Just clarification for anyone who is not really in the subject of all those grammars classification.

Regular expressions in some languages can be recursive, nowadays there are some better techniques that FA for that, but by definition they cannot be recursive and cannot recognize balanced constructions (like open-closed brackets), so to say, regular grammars do not have "memory" or "counting". If you add a quantifier like this

a{3}

it will result in automata like this one

stateDiagram
direction LR

[*] --> s1: a
s1 --> s2: a
s2 --> [*]: a

If I am not mistaken, there are more than one automata for the same grammar.

nirname commented 11 months ago

Which syntax of EBNF should we implement? Is there a standard?

Winterreisender commented 11 months ago

Which syntax of EBNF should we implement? Is there a standard?

There are two standards: ISO/IEC 14977:1996 and W3C。

Most textbooks use ISO standard while programmers (especially compilers) prefer w3c standard. (I guess)

nirname commented 11 months ago

Standards w3c ebnf iso-14977

Examples: regulex with src js-sequence Draw Grammar - written in ml, compiled to js Railroad Diagram Generator with its src Railroad diagrams%2C%0A%20%20ZeroOrMore(%0A%20%20%20%20Choice(0%2C%0A%20%20%20%20%20%20NonTerminal('name%20char')%2C%0A%20%20%20%20%20%20NonTerminal('escape'))))) not bnf but good looking

The most advanced implementation is https://github.com/GuntherRademacher/rr This is the only one which normalizes them

nirname commented 11 months ago

What has been done so far

There are different standards on that, so I decided to support different options simultaneously :

Allow any of ::= := : = -> => as production (assignment) operator

rule ::= term // support for kinda classic bnf
rule := term // golang or pascal like assignments
rule = term // classic equal or assignment
rule : term // bison / jison like
// dragon book derivation operator sample meaning rule derives term
rule -> term
rule => term

() for groups and alternatives
[] and ? for zero or one
```
rule: term?
rule: [term]
```
{} and * for zero or many
```
rule: term*
rule: {term}
```
+ for one or many
```
rule: term+
rule: (term term)+
```
single quoted and double quoted string for termnias
```
rule: "some string"
rule: 'some string'
```

optional angle brackets for <non-terms>

<while-loop>: 'while' '(' ....
<while loop>: 'while' '(' ....

nirname commented 11 months ago

@GuntherRademacher your RR diagrams are really advanced, have you ever considered making a contribution there?

GuntherRademacher commented 11 months ago

@GuntherRademacher your RR diagrams are really advanced, have you ever considered making a contribution there?

Sorry - I have no capacity available to help here. My code comes under the Apache 2 license - feel free to use it if it fits your needs. Grammar transformation and diagram generation is implemented in XQuery, though.

nirname commented 11 months ago

@GuntherRademacher thanks for the response. I am currently at the point where I implemented parser and I am researching on how to optimize AST. I am pretty sure, I am able implement it myself, but before I started writing code, I'd like to verify my ideas against different sources. One of them is your implementation. Another is so called "Dragon Book", but they have very short section about it (left factoring, recursion elimination) and that is pretty much it. Could you provide a piece of advice on where to look at and if there any other detailed descriptions of the subject?

PS: some other diagram tools do not even bother optimizing output, they do it 1:1, but I am not willing to put superficial code into the release, only as a first approach.

nirname commented 11 months ago

I decided to collect all my thoughts into WIKI

nirname commented 10 months ago

My progress on this slowed down, I had to postpone it for some time, but I am going to continue working on that issue ASAP

nirname commented 9 months ago

For those who are watching this issue, I am back to the task

McCache commented 9 months ago

It would be nice to be able to add some documentation to the diagram. Could be under each segment of the railroad and also after the individual diagram for more pointed notes call out.

properties::=

Some documentaiton. Diagram here
- More footnotes call out.

nirname commented 9 months ago

@McCache that depends on the syntax supported. Could you elaborate more on this?

McCache commented 9 months ago

We should stay with EBNF. I am just asking for in your implementation to allow user add optional comments. Sometimes, the diagram may not be clear enough so it would be nice to have some comments to to provide more clarity.

Optionally, allow us to add some comments here. properties ::= The generated fragment railroad diagram

Optionally, allow us add some more detail comments here.

I will let you decide where is the most appropriate placement of the comments.

nirname commented 9 months ago

@McCache EBNF by itself does not imply any comments. That means:

we either must extend it and do something similar to plant uml
stick to some other notations similar to bison / jison or whatever that allows to do some actions for every rule, thus we could think of them as comments
add something in between EBNF production rules like
```
expr ::= expr + expr
> here goes comment
```

As I see it we cannot use standard mermaid comments much alike shebang or doc comments in its current implementation

expr ::= expr + expr
%%! here goes comment that will be in a diagram

Because they are pre-processed.

Could you provide some more examples of possible syntax for that?

McCache commented 9 months ago

Can we use markdown block quote?

expr ::= expr + expr

here goes comment that will be in a diagram

or

expr ::= expr + expr

here goes comment that will be in a diagram

On Fri, Sep 22, 2023 at 5:53 AM Nikolay Rozhkov @.***> wrote:

@McCache https://github.com/McCache EBNF by itself does not imply any comments. That means:

we either must extend it and do something similar to plant uml

stick to some other notations similar to bison / jison or whatever that allows to do some actions for every rule, thus we could think of them as comments

add something in between EBNF production rules like

expr ::= expr + expr

here goes comment

As I see it we cannot use standard mermaid comments much alike shebang or doc comments in its current implementation

expr ::= expr + expr %%! here goes comment that will be in a diagram

Because they are pre-processed.

Could you provide some more examples of possible syntax for that?

— Reply to this email directly, view it on GitHub https://github.com/mermaid-js/mermaid/issues/4252#issuecomment-1731364842, or unsubscribe https://github.com/notifications/unsubscribe-auth/BB252FLKBFXIHL5JN56U6YDX3WC3RANCNFSM6AAAAAAWLOFWU4 . You are receiving this because you were mentioned.Message ID: @.***>

McCache commented 9 months ago

I implement the Git drawing here: https://raw.githubusercontent.com/elau1004/Alembic-Branches-Example/main/README.md

The gitGraph has something at the end for name. Maybe something like:

expr ::= expr + expr "Comment here"

or

expr ::= expr + expr ; Expression comment here.

Use a semicolon as expression delimiter and hash as script comment.

On Mon, Sep 25, 2023 at 7:18 PM Edward Lau @.***> wrote:

Can we use markdown block quote?

expr ::= expr + expr

here goes comment that will be in a diagram

or

expr ::= expr + expr

here goes comment that will be in a diagram

On Fri, Sep 22, 2023 at 5:53 AM Nikolay Rozhkov @.***> wrote:

@McCache https://github.com/McCache EBNF by itself does not imply any comments. That means:

we either must extend it and do something similar to plant uml

stick to some other notations similar to bison / jison or whatever that allows to do some actions for every rule, thus we could think of them as comments

add something in between EBNF production rules like

expr ::= expr + expr

here goes comment

As I see it we cannot use standard mermaid comments much alike shebang or doc comments in its current implementation

expr ::= expr + expr %%! here goes comment that will be in a diagram

Because they are pre-processed.

Could you provide some more examples of possible syntax for that?

— Reply to this email directly, view it on GitHub https://github.com/mermaid-js/mermaid/issues/4252#issuecomment-1731364842, or unsubscribe https://github.com/notifications/unsubscribe-auth/BB252FLKBFXIHL5JN56U6YDX3WC3RANCNFSM6AAAAAAWLOFWU4 . You are receiving this because you were mentioned.Message ID: @.***>

elau1004 commented 7 months ago

Any idea when will this be merged into the main branch?

nirname commented 7 months ago

@elau1004 still in progress, cannot invest a lot of time in this right now. Grammar is more or less ready, rendering is not

elau1004 commented 7 months ago

I am NOT a front end developer. Not sure how involved is this. If there is clear instructions/training on how to set it up and test locally ... maybe I can lean a hand. My IDE is VS Code on Windows.

nirname commented 7 months ago

@elau1004 Neither am I. The best place to start is the development guide. Currently there is a PR I am working on.

IS2511 commented 2 weeks ago

Pretty interested in this feature :eyes:

nirname commented 2 weeks ago

I'm working on this, parser is ready, but needs rewriting to meet our new requirements. Rendering is under development

mermaid-js / mermaid

EBNF (Syntax diagrams / Railroad diagrams / Grammar diagrams) #4252

Proposal

Use Cases

Screenshots

Code Sample

What has been done so far