### ----------------------------------------------------
### -- FunctionalParsers
### -- Licenses: Artistic-2.0
### -- Authors: Anton Antonov
### -- File: doc/Graph-representation-of-grammars.md
### ----------------------------------------------------
# Graph representation of grammars

## Introduction

This computational Markdown document demonstrates the mapping of 
[Extended Backus-Naur Grammars (EBNF)](https://en.wikipedia.org/wiki/Extended_Backus–Naur_form)
and Raku grammars into graphs.

The graphs are made with [Mermaid-JS](https://mermaid.js.org) and 
[Wolfram Language (WL)](https://www.wolfram.com/language/) (aka Mathematica).  

**Remark:** Mermaid-JS specs are automatically rendered in GitHub Markdown files,
and have plug-ing support in Integrated Development Environments (IDEs) like IntelliJ IDEA, VS Code, Emacs, etc.

### Reflections and observations

- I consider the graph representation "neat" and "cool" for small enough grammars, 
but I am not sure how useful it is for large grammars. 

- I made a fair amount of experiments with relatively small grammars, and experiments with a few large grammars.

- The ability to make the grammar graphs, of course, has at least didactic utility.

- Another utility of the experiments shown here is to show coherent interaction between the packages
  - ["FunctionalParsers"](https://raku.land/zef:antononcube/FunctionalParsers)
  - ["EBNF::Grammar"](https://raku.land/zef:antononcube/EBNF::Grammar)
  - ["Grammar::TokenProcessing"](https://raku.land/zef:antononcube/Grammar-TokenProcessing)

- This Markdown document is "executed" with the package 
["Text::CodeProcessing"](https://raku.land/zef:antononcube/Text::CodeProcessing)
which allows generation of Markdown specs that are, say, automatically processed by Web browsers, IDEs, etc.  
  - Like Mermaid-JS charts and graphs.

- Visualizing grammars generated by Large Language Models (LLMs) -- like, ChatGPT and PaLM -- is both didactic and "neat." 
  - One of my primary motivations for making packages "FunctionalParsers" and "EBNF::Grammar" was to be able 
  to easily (automatically or semi-automatically) process grammars generated with LLMs. 

------

## Packages and interactions

Here we load the packages used below:

```perl6
use FunctionalParsers;
use FunctionalParsers::EBNF;
use EBNF::Grammar;
use Grammar::TokenProcessing;
```
```
# (Any)
```

Here use case diagrams that summarize the interaction between the packages:

```mermaid
graph LR
    FPs[["FunctionalParsers"]]
    grEBNF>EBNF<br>grammar]
    mmdGraph>Mermaid JS<br>graph spec]
    grEBNF --> FPs --> mmdGraph
```

```mermaid
graph LR
    FPs[["FunctionalParsers"]]
    EBNFGram[["EBNF::Grammar"]]
    grEBNF>EBNF<br>grammar]
    mmdGraph>Mermaid JS<br>graph spec]
    grEBNF --> EBNFGram --> FPs --> mmdGraph
```

```mermaid
graph LR
    FPs[["FunctionalParsers"]]
    GramTP[["Grammar::TokenProcessing"]]
    grEBNF>EBNF<br>grammar]
    grRaku>Raku<br>grammar]
    mmdGraph>Mermaid JS<br>graph spec]
    grRaku --> GramTP --> grEBNF --> FPs --> mmdGraph 
```

------

## Generating Mermaid diagrams for EBNFs

The function `fp-ebnf-parse` can produce
[Mermaid-JS diagrams](https://mermaid.js.org)
corresponding to grammars with the target "MermaidJS::Graph".
Here is an example:

```perl6, result=asis, output-lang=mermaid, output-prompt=NONE
my $ebnfCode3 = q:to/END/;
<top> = <a> | <b> ;
<a> = 'a' , { 'A' } , [ '1' ];
<b> = 'b' , ( 'B' | '2' );
END

fp-ebnf-parse($ebnfCode3, target=>'MermaidJS::Graph', dir-spec => 'LR').head.tail
```
```mermaid
graph LR
	rep7((*))
	alt14((or))
	T:1("1")
	seq12((and))
	NT:top["top"]
	alt1((or))
	T:a("a")
	T:b("b")
	T:B("B")
	NT:a["a"]
	seq5((and))
	opt9((?))
	T:A("A")
	NT:b["b"]
	T:2("2")
	alt1 --> NT:a
	alt1 --> NT:b
	NT:top --> alt1
	rep7 --> T:A
	opt9 --> T:1
	seq5 --> |1|T:a
	seq5 --> |2|rep7
	seq5 --> |3|opt9
	NT:a --> seq5
	alt14 --> T:B
	alt14 --> T:2
	seq12 --> |1|T:b
	seq12 --> |2|alt14
	NT:b --> seq12
```

Here is a legend:

- The non-terminals are shown with rectangles
- The terminals are shown with round rectangles
- The "conjunctions" are shown in disks

**Remark:** The Markdown cell above has the parameters `result=asis, output-lang=mermaid, output-prompt=NONE`
which allow for direct diagram rendering of the obtained Mermaid code in various Markdown viewers (GitHub, IntelliJ, etc.)

Compare the following EBNF grammar and corresponding diagram with the ones above:

```perl6, result=asis, output-lang=mermaid, output-prompt=NONE
my $ebnfCode4 = q:to/END/;
<top> = <a> | <b> ;
<a> = 'a' , { 'A' } , [ '1' ] ;
<b> = 'b' , 'B' | '2' ;
END

fp-ebnf-parse($ebnfCode4, target=>'MermaidJS::Graph', dir-spec => 'LR').head.tail
```
```mermaid
graph LR
	T:a("a")
	rep7((*))
	alt1((or))
	T:B("B")
	T:A("A")
	alt12((or))
	T:b("b")
	opt9((?))
	NT:a["a"]
	NT:top["top"]
	NT:b["b"]
	seq5((and))
	T:2("2")
	T:1("1")
	seq13((and))
	alt1 --> NT:a
	alt1 --> NT:b
	NT:top --> alt1
	rep7 --> T:A
	opt9 --> T:1
	seq5 --> |1|T:a
	seq5 --> |2|rep7
	seq5 --> |3|opt9
	NT:a --> seq5
	seq13 --> |1|T:b
	seq13 --> |2|T:B
	alt12 --> seq13
	alt12 --> T:2
	NT:b --> alt12
```

------

## Generating Mermaid diagrams for Raku grammars

In order to generate graphs for Raku grammars we use the following steps:

1. Translate Raku-grammar code into EBNF code
2. Translate EBNF code into graph code (Mermaid-JS or WL)

Consider a grammar for parsing integers:

```perl6
grammar LangLove {
    rule TOP  { <workflow-command> }
    rule workflow-command  { <who> 'really'? <love> <lang> }
    token who { 'I' | 'We' }
    token love { 'hate' | 'love' }
    token lang { 'Raku' | 'Perl' | 'Rust' | 'Go' | 'Python' | 'Ruby' }
}
```
```
# (LangLove)
```

Here is an example parsing:

```perl6
LangLove.parse('I hate Perl')
```
```
# ｢I hate Perl｣
#  workflow-command => ｢I hate Perl｣
#   who => ｢I｣
#   love => ｢hate｣
#   lang => ｢Perl｣
```

First we derive the corresponding EBNF grammar:

```perl6
my $ebnfLangLove = to-ebnf-grammar(LangLove)
```
```
# <TOP> = <workflow-command>  ;
# <lang> = 'Raku'  | 'Perl'  | 'Rust'  | 'Go'  | 'Python'  | 'Ruby'  ;
# <love> = 'hate'  | 'love'  ;
# <who> = 'I'  | 'We'  ;
# <workflow-command> = <who> , ['really'] , <love> , <lang>  ;
```

Here is the corresponding Mermaid-JS graph:

```perl6, result=asis, output.lang=mermaid, output.prompt=NONE
fp-grammar-graph($ebnfLangLove)
```
```mermaid
graph TD
	T:Python("Python")
	T:Raku("Raku")
	T:love("love")
	T:We("We")
	T:Perl("Perl")
	NT:TOP["TOP"]
	T:really("really")
	seq19((and))
	alt3((or))
	T:Go("Go")
	T:I("I")
	T:hate("hate")
	NT:workflow-command["workflow-command"]
	alt15((or))
	alt11((or))
	NT:who["who"]
	T:Rust("Rust")
	NT:lang["lang"]
	NT:love["love"]
	opt21((?))
	T:Ruby("Ruby")
	NT:TOP --> NT:workflow-command
	alt3 --> T:Raku
	alt3 --> T:Perl
	alt3 --> T:Rust
	alt3 --> T:Go
	alt3 --> T:Python
	alt3 --> T:Ruby
	NT:lang --> alt3
	alt11 --> T:hate
	alt11 --> T:love
	NT:love --> alt11
	alt15 --> T:I
	alt15 --> T:We
	NT:who --> alt15
	opt21 --> T:really
	seq19 --> |1|NT:who
	seq19 --> |2|opt21
	seq19 --> |3|NT:love
	seq19 --> |4|NT:lang
	NT:workflow-command --> seq19
```

------

## More complicated grammar

Consider this grammar:

```perl6
my $ebnfExpr = q:to/END/;
start   = expr ;
expr    = term '+' expr | term '-' expr | term ;
term    = term '*' factor | term '/' factor | factor ;
factor  = '+' factor | '-' factor | (expr) | integer | integer '.' integer ;
integer = digit integer | digit ;
digit   = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
END
```
```
# start   = expr ;
# expr    = term '+' expr | term '-' expr | term ;
# term    = term '*' factor | term '/' factor | factor ;
# factor  = '+' factor | '-' factor | (expr) | integer | integer '.' integer ;
# integer = digit integer | digit ;
# digit   = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
```

Here we produce the graph using special parsing style:

```perl6, result=asis, output.lang=mermaid, output.prompt=NONE
fp-grammar-graph($ebnfExpr, style => 'Relaxed')
```
```mermaid
graph TD
	seq8((and))
	seq19((and))
	seq34((and))
	T:2("2")
	T:+("+")
	T:1("1")
	T:*("*")
	alt3((or))
	T:.(".")
	T:8("8")
	alt39((or))
	NT:start["start"]
	T:5("5")
	seq4((and))
	T:3("3")
	T:4("4")
	alt14((or))
	alt45((or))
	T:9("9")
	NT:expr["expr"]
	T:6("6")
	T:7("7")
	alt25((or))
	seq15((and))
	NT:factor["factor"]
	seq26((and))
	T:-("-")
	seq40((and))
	T:/("/")
	NT:integer["integer"]
	seq29((and))
	NT:digit["digit"]
	T:0("0")
	NT:term["term"]
	NT:start --> NT:expr
	seq4 --> |1|NT:term
	seq4 --> |2|T:+
	seq4 --> |3|NT:expr
	seq8 --> |1|NT:term
	seq8 --> |2|T:-
	seq8 --> |3|NT:expr
	alt3 --> seq4
	alt3 --> seq8
	alt3 --> NT:term
	NT:expr --> alt3
	seq15 --> |1|NT:term
	seq15 --> |2|T:*
	seq15 --> |3|NT:factor
	seq19 --> |1|NT:term
	seq19 --> |2|T:/
	seq19 --> |3|NT:factor
	alt14 --> seq15
	alt14 --> seq19
	alt14 --> NT:factor
	NT:term --> alt14
	seq26 --> |1|T:+
	seq26 --> |2|NT:factor
	seq29 --> |1|T:-
	seq29 --> |2|NT:factor
	seq34 --> |1|NT:integer
	seq34 --> |2|T:.
	seq34 --> |3|NT:integer
	alt25 --> seq26
	alt25 --> seq29
	alt25 --> NT:expr
	alt25 --> NT:integer
	alt25 --> seq34
	NT:factor --> alt25
	seq40 --> |1|NT:digit
	seq40 --> |2|NT:integer
	alt39 --> seq40
	alt39 --> NT:digit
	NT:integer --> alt39
	alt45 --> T:0
	alt45 --> T:1
	alt45 --> T:2
	alt45 --> T:3
	alt45 --> T:4
	alt45 --> T:5
	alt45 --> T:6
	alt45 --> T:7
	alt45 --> T:8
	alt45 --> T:9
	NT:digit --> alt45
```

------

## References

### Articles

[Wk1] Wikipedia entry, ["Extended Backus–Naur form"](https://en.wikipedia.org/wiki/Extended_Backus–Naur_form).

### Packages, repositories

[AAp1] Anton Antonov,
[FunctionParsers Raku package](https://github.com/antononcube/Raku-FunctionalParsers),
(2023),
[GitHub/antononcube](https://github.com/antononcube).

[AAp2] Anton Antonov,
[EBNF:Grammar Raku package](https://github.com/antononcube/Raku-EBNF-Grammar),
(2023),
[GitHub/antononcube](https://github.com/antononcube).

[AAp3] Anton Antonov,
[Grammar::TokenProcessing Raku package](https://github.com/antononcube/Raku-Grammar-TokenProcessing),
(2022-2023),
[GitHub/antononcube](https://github.com/antononcube).


