Graph representation of grammars

Anton Antonov
RakuForPrediction-book at GitHub
RakuForPrediction at WordPress
July 2023

Introduction

This notebook is a converted version of the computational Markdown document with the same name [AA1], and it demonstrates the mapping of Extended Backus-Naur Grammars (EBNF) and Raku grammars into graphs.

The graphs are made with Mermaid-JS and Wolfram Language (WL) (aka Mathematica).

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

Examples using Large Language Models (LLMs) are provided. (Via "WWW::OpenAI" and "WWW::PaLM" , [AAp4, AAp5].)

The document has the following structure:

◼

Reflections and observations
I.e. "conclusions first." Those make the anecdotal examples below more scientific, not just conjecture-worthy anecdotes.

◼

Packages and interactions
A list the packages utilized and how they can be used in a coherent way.

◼

Generating Mermaid diagrams for EBNFs
Two simple and similar EBNF grammars with graphs for instructive comparison.

◼

Generating graphs with LLMs
Can LLMs replace Raku programming (of grammar-graphs making)?

◼

Generating Mermaid diagrams for Raku grammars
Same exercise but over Raku grammars, not some EBNFs...

◼

LLMs grammars for sentence collections
An interesting way to derive EBNFs is to "just ask." Well, some questions might get really long (and their answers really expensive.)

◼

Random LLMs grammars
Why ask for EBNFs of sentence collections, if we can just say "Give me a random EBNF grammar (or five.)"

◼

More complicated grammar
A larger grammar example, in order to illustrate the usefulness -- or uselessness -- of grammar-graphs.

———

Reflections and observations

◼

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

◼

Especially, large grammars with recursive dependencies between the production rules.

◼

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

◼

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

◼

Another utility of the examples given below is to show coherent interaction between the packages:

◼

"FunctionalParsers"

◼

"EBNF::Grammar"

◼

"Grammar::TokenProcessing"

◼

This Markdown document is "executed" with the package "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 the packages "FunctionalParsers" and "EBNF::Grammar" was to be able to easily (automatically or semi-automatically) process grammars generated with LLMs.

◼

It is not trivial to parse EBNF hallucinations by LLMs. (More details below.)

◼

Generating Raku grammars with ChatGPT-3.5 or PaLM often produces "non-working" grammars. That is why I focused on EBNF grammars.

◼

My assumption is that EBNF has been around for a longer period of time, hence, LLMs are "better trained for it."

◼

The original Markdown document was converted into this Mathematica notebook using "Markdown::Grammar", [AAp6]. Mathematica notebooks in RakuMode , [AAp7], make much easier the experiments with diagram generation and LLM utilization with Raku. (And more fun!)

◼

Instead of the "MermaidJS" paclet the resource function MermaidInk can be used.

◼

The paclet "MermaidJS" has the function MermaidJS that can be used to produce WL graphics objects, not just images as MermaidInk.

◼

The WL paclet "FunctionalParsers" corresponds to the Raku package "FuncitonalParsers".

Packages and interactions

Here we load the packages used below:

In[]:=

use FunctionalParsers;
use FunctionalParsers::EBNF;
use EBNF::Grammar;
use Grammar::TokenProcessing;
use WWW::OpenAI;
use WWW::PaLM;

Out[]=

(Any)

Here are flowcharts that summarize use cases, execution paths, and interaction between the packages:

Out[]=

———

Generating Mermaid diagrams for EBNFs

The function fp-ebnf-parse can produce Mermaid-JS diagrams corresponding to grammars with the target "MermaidJS::Graph". Here is an example:

In[]:=

my $ebnfCode1 = q:to/END/;
<top> = <a> | <b> ;
<a> = 'a' , { 'A' } , [ '1' ];
<b> = 'b' , ( 'B' | '2' );
END

fp-ebnf-parse($ebnfCode1, target=>'MermaidJS::Graph', dir-spec => 'LR').head.tail

Out[]=

graph LR rep7((*)) NT:top["top"] seq12((and)) NT:a["a"] NT:b["b"] alt1((or)) seq5((and)) opt9((?)) T:b("b") T:B("B") T:1("1") T:2("2") alt14((or)) T:a("a") T:A("A") 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

In[]:=

MermaidJS[%,"PDF",ImageSize->600]

Out[]=

Here is a legend:

◼

The non-terminals are shown with rectangles

◼

The terminals are shown with round rectangles

◼

The "conjunctions" are shown in disks

◼

The order of parsing in sequences is indicated with integer labels

◼

Pick-left and pick-right sequences use the labels "L" and "R" for the corresponding branches

Remark: The Markdown cell above has the parameters `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:

In[]:=

my $ebnfCode2 = q:to/END/;
<top> = <a> | <b> ;
<a> = 'a' <& { 'A' } , [ '1' ] ;
<b> = 'b' , 'B' | '2' ;
END

fp-ebnf-parse($ebnfCode2, target=>'MermaidJS::Graph', dir-spec => 'LR').head.tail

We can generate WL graphs instead of Mermaid-JS images:

Generating graphs with LLMs

It is interesting to see do LLMs do better at producing (Mermaid-JS) graph representations.

More importantly, we want to answer the question:

Can we generate graph-specs (like, Mermaid-JS) without the need of programming the corresponding interpreters?

Here is a LLM request for a Mermaid-JS spec generation for one of the simple grammars above:

In[]:=

my $request = "Make a Mermaid JS diagram for the EBNF grammar:
$ebnfCode1";
#my $mmdLLM = openai-completion($request, max-tokens => 600, format => 'values', temperature => 1.2);
my $mmdLLM = palm-generate-text($request, max-tokens => 600, format => 'values', temperature => 0.9, :$auth-key);

Here is the corresponding graph:

Remark:: After multiple experiments I can say that the obtained Mermaid-JS code is either:

◼

Simple, somewhat relevant, and wrong

◼

Closer to correct after suitable manual editing

As for the question above -- the answer is "No". But the LLM answers provide (somewhat) good initial versions for manual (human) building of graph specifications.

Generating Mermaid diagrams for Raku grammars

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

Translate Raku-grammar code into EBNF code

Translate EBNF code into graph code (Mermaid-JS or WL)

Consider a grammar for parsing proclaimed feeling toward different programming languages:

In[]:=

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' }
}

Here is an example parsing:

In[]:=

LangLove.parse('I hate Perl')

First we derive the corresponding EBNF grammar:

In[]:=

my $ebnfLangLove = to-ebnf-grammar(LangLove)

Here is the corresponding Mermaid-JS graph:

LLMs grammars for sentence collections

Here is an EBNF grammar generated with ChatGPT, [AAp4], over a list of chemical formulas:

In[]:=

#my @sentences = <BrI BrClH2Si CCl4 CH3I C2H5Br H2O H2O4S AgBr AgBrO AgBrO2 AgBrO3 AgBrO4 AgCL>;
my @sentences = <AgBr AgBrO AgBrO2 AgBrO3 AgBrO4 AgCL>;
my $request = "Generate EBNF grammar for the sentences:
{@sentences.map({ $_.comb.join(' ')}).join("
")}";
#my $ebnfLLM = openai-completion($request, max-tokens => 600, format => 'values');
my $ebnfLLM = palm-generate-text($request, max-tokens => 600, format => 'values', :$auth-key);

Often LLM requests as the ones above return code as Markdown code cells, hence, we try to remove the code cell markings:

In[]:=

$ebnfLLM = $ebnfLLM.subst(/ ^ '`' ** 3 <-[\v]>* | '`' ** 3 \h* $ /,''):g;

Another way for "verify" a grammar is to generate random sentences with it:

In[]:=

.say for fp-random-sentence($ebnfLLM, 12, style => Whatever)

Remark: Random sentences can be also generated with the function fp-random-sentence provided by "FunctionalParsers".

Remark: The function ebnf-random-sentence uses fp-random-sentence , but ebnf-random-sentence (parses and) standardizes the given EBNF grammar first, (then it gives the standardized grammar to fp-random-sentence .)

Remark: It is not trivial to parse EBNF hallucinations by LLMs. For the same EBNF-making request a given LLM can produce different EBNF grammars, each having "its own" EBNF style. Hence, both "FunctionalParsers" and "EBNF::Grammar" have parsers for different EBNF styles. With the spec `style => Whatever` parsing of all of the "anticipated" styles are attempted.

Random LLMs grammars

Why ask for EBNF graphs with sentence collections, if we can just say:

Give me a random EBNF grammar. (Or five.)

Remark: Note, the implications of testing the parsers in that way. We can try to produce extensive parser tests by multiple randomly obtained grammars from different LLMs. (Using different LLM parameters, like, temperatures, etc.)

Here is another example using a random (hopefully small) EBNF grammar:

In[]:=

my $request2 = "Give an example of simple EBNF grammar.";
#my $ebnfLLM2 = openai-completion($request2, max-tokens => 600, format => 'values', temperature => 1.2);
my $ebnfLLM2 = palm-generate-text($request2, max-tokens => 600, format => 'values', temperature => 0.9, :$auth-key);
$ebnfLLM2 = $ebnfLLM2.subst(/ ^ '`' ** 3 <-[\v]>* | '`' ** 3 \h* $ /,''):g;

More complicated grammar

Consider the following grammar for arithmetic expressions:

In[]:=

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

Here we produce the graph using special parsing style:

Here is the WL graph version: