Grammar railroad diagram

[mingodad]

Using some online tools like https://www.bottlecaps.de/rr/ui and https://www.bottlecaps.de/convert/ we can have a nice navigable railroad diagram.

Copy and paste the EBNF shown bellow on https://www.bottlecaps.de/rr/ui on the tab Edit Grammar the click on the tab View Diagram to see/download a navigable railroad diagram.

/* converted on Mon Dec 12, 2022, 11:54 (UTC+01) by antlr_4-to-w3c v0.62 which is Copyright (c) 2011-2022 by Gunther Rademacher <[email protected]> */

start    ::= program EOF
program  ::= packageDecl? useDecl* ( decl | clause )*
packageDecl
         ::= 'Package' NAME atoms? '!'
useDecl  ::= 'Use' NAME atoms? '!'
decl     ::= 'Decl' atom descrBlock? boundsBlock* constraintsBlock? '.'
descrBlock
         ::= 'descr' atoms
boundsBlock
         ::= 'bound' '[' term ( ',' term )* ']'
constraintsBlock
         ::= 'inclusion' atoms
clause   ::= atom ( ':-' clauseBody )? '.'
clauseBody
         ::= literalOrFml ( ',' literalOrFml )* ( '|>' transform )?
transform
         ::= ( 'do' term | letStmt ) ( ',' letStmt )*
letStmt  ::= 'let' VARIABLE '=' term
literalOrFml
         ::= ( term ( '=' | '!=' | '<' | '<=' ) | '!' )? term
term     ::= VARIABLE
           | CONSTANT
           | NUMBER
           | STRING
           | NAME '(' ( term ( ',' term )* )? ')'
           | '[' ( ( ( term ',' )* | term ':' ( term ',' term ':' )* ) term )? ']'
           | '{' ( term ':' term ( ',' term ':' term )* )? '}'
atom     ::= term
atoms    ::= '[' ( atom ( ',' atom )* )? ']'
_        ::= WHITESPACE
           | COMMENT
          /* ws: definition */

<?TOKENS?>

WHITESPACE
         ::= [ #x9#xD#xA#xC]+
COMMENT  ::= '#' [^#xA]*
NEWLINE  ::= #xA
LETTER   ::= [A-Za-z]
DIGIT    ::= [0-9]
NUMBER   ::= '-'? DIGIT+
VARIABLE_START
         ::= [A-Z]
VARIABLE_CHAR
         ::= LETTER
           | DIGIT
VARIABLE ::= '_'
           | VARIABLE_START VARIABLE_CHAR*
NAME_CHAR
         ::= LETTER
           | DIGIT
           | ':'
           | '_'
NAME     ::= ':'? [a-z] ( '.'? NAME_CHAR )*
CONSTANT_CHAR
         ::= LETTER
           | DIGIT
           | '.'
           | '-'
           | '_'
           | '~'
           | '%'
CONSTANT ::= ( '/' CONSTANT_CHAR+ )+
STRING   ::= SHORT_STRING
           | LONG_STRING
SHORT_STRING
         ::= "'" ( STRING_ESCAPE_SEQ | [^\'#xd#xa#xc] )* "'"
           | '"' ( STRING_ESCAPE_SEQ | [^\"#xd#xa#xc] )* '"'
LONG_STRING
         ::= '`' LONG_STRING_ITEM* '`'
LONG_STRING_ITEM
         ::= LONG_STRING_CHAR
           | STRING_ESCAPE_SEQ
LONG_STRING_CHAR
         ::= [^-]
STRING_ESCAPE_SEQ
         ::= '\' ( . | NEWLINE )
EOF      ::= $

[burakemir]

Thanks for the suggestion! These will look nice in our documentation. Keeping this issue open as as a reminder.

I do think some parts of the grammar may still change on our way to 1.0 release, but others should be stable.

[rkrishnasanka]

@mingodad @burakemir, there are railroad generation tools for ANTLR. If you can let me know which directory you want them in, I can add a script for generating them / Just insert the railroad diagrams.

[burakemir]

Let's maybe start with an svg for plain Datalog atoms / facts first, with recursion and negation? However the mangle syntax evolves (the syntax in first post is already outdated, since map and struct constants were added), one needs to understand this core first. (edit: formatting)

clause ::= atom (':-' clauseBody)? '.'
clauseBody ::= literal (',' literal)* 
literal ::= atom | '!' atom
atom ::=  predicateName '(' varOrConstant (',' varOrConstant)*  ')' 
varOrConstant  ::= variable | constant

[mingodad]

It's on a matter to pass https://raw.githubusercontent.com/google/mangle/main/parse/gen/Mangle.g4 through https://www.bottlecaps.de/convert/ and then click View Diagram as I just did and updated the EBNF from the first post #3 (comment)

[burakemir]

Just to explain why I am hesitating here: there are still a few minor grammar changes that need to be done, see e.g. #27 and possibly something that lets users define types.

[mingodad]

I've just added a lalr(1) grammar based on this project grammar to https://mingodad.github.io/parsertl-playground/playground/ an Yacc/Lexer compatible online (wasm) interpreter/editor (select Mangle (datalog) parser from Examples then click Parse to see a parser tree for the content in Input source).

The grammar there has some small changes because as it is in this project there is several conflicts mainly due to List/Map accepting an empty [] which doesn't allow to differentiate between then.

[burakemir]

Very cool! I just made a small change to the grammar, to get more readable type syntax. See the new DOT_TYPE variant for non-terminal term.