Grammar railroad diagram

[mingodad]

After massaging a bit src/js/base/pyret-grammar.bnf and add tokens from src/js/base/pyret-tokenizer.js and copying the resulting EBNF shown bellow on https://www.bottlecaps.de/rr/ui in the TAB Edit Grammar and then swithcing to the TAB View Diagram we have a full grammar railroad diagram.

/*
  name::= PyretGrammar
*/
program::= prelude block

prelude::= (use_stmt)? (provide_stmt|import_stmt)*

use_stmt::= USE NAME import_source

import_stmt::= INCLUDE import_source
	| INCLUDE FROM module_ref COLON (include_spec (COMMA include_spec)* (COMMA)?)? END
	| IMPORT import_source AS NAME
	| IMPORT comma_names FROM import_source
import_source::= import_special | import_name
import_special::= NAME PARENNOSPACE STRING (COMMA STRING)* RPAREN
import_name::= NAME


include_spec::= include_name_spec
            | include_type_spec
            | include_data_spec
            | include_module_spec

include_name_spec::= name_spec
include_type_spec::= TYPE name_spec
include_data_spec::= DATA data_name_spec (hiding_spec)?
include_module_spec::= MODULE name_spec

provide_stmt::= provide_vals_stmt | provide_types_stmt | provide_block

provide_vals_stmt::=  PROVIDE stmt END | PROVIDE (STAR|TIMES)
provide_types_stmt::= PROVIDE_TYPES record_ann | PROVIDE_TYPES (STAR|TIMES)

provide_block::= PROVIDECOLON (provide_spec (COMMA provide_spec)* (COMMA)?)? END
provide_block::= PROVIDE FROM module_ref COLON (provide_spec (COMMA provide_spec)* (COMMA)?)? END

provide_spec::= provide_name_spec
            | provide_type_spec
            | provide_data_spec
            | provide_module_spec

name_spec::= (STAR|TIMES) (hiding_spec)? | module_ref | module_ref AS NAME
data_name_spec::= (STAR|TIMES) | module_ref

provide_name_spec::= name_spec
provide_type_spec::= TYPE name_spec
provide_data_spec::= DATA data_name_spec (hiding_spec)?
provide_module_spec::= MODULE name_spec

hiding_spec::= HIDING (PARENSPACE | PARENNOSPACE) ((NAME COMMA)* NAME)? RPAREN

module_ref::= (NAME DOT)* NAME



comma_names::= NAME (COMMA NAME)*

block::= stmt*

stmt::= type_expr | newtype_expr | spy_stmt
    | let_expr | fun_expr | data_expr | when_expr
    | var_expr | rec_expr | assign_expr | check_test | check_expr
    | contract_stmt

spy_stmt::= SPY (binop_expr)? COLON (spy_contents)? END
spy_contents::= spy_field (COMMA spy_field)*
spy_field::= id_expr | NAME COLON binop_expr

type_expr::= TYPE NAME ty_params EQUALS ann
newtype_expr::= NEWTYPE NAME AS NAME
let_expr::= toplevel_binding EQUALS binop_expr
binding::= name_binding | tuple_binding

tuple_binding::= LBRACE (binding SEMI)* binding (SEMI)? RBRACE (AS name_binding)?
name_binding::= (SHADOW)? NAME (COLONCOLON ann)?

toplevel_binding::= binding
//# toplevel_binding::= (SHADOW)? NAME COLONCOLON noparen_arrow_ann
multi_let_expr::= LET let_binding (COMMA let_binding)* (BLOCK|COLON) block END
let_binding::= let_expr | var_expr
letrec_expr::= LETREC let_expr (COMMA let_expr)* (BLOCK|COLON) block END

type_bind::= NAME ty_params EQUALS ann
newtype_bind::= NEWTYPE NAME AS NAME

type_let_bind::= type_bind | newtype_bind
type_let_expr::= TYPE_LET type_let_bind (COMMA type_let_bind)* (BLOCK|COLON) block END

contract_stmt::= NAME COLONCOLON ty_params (ann | noparen_arrow_ann)

fun_expr::= FUN NAME fun_header (BLOCK|COLON) doc_string block where_clause END
fun_header::= ty_params args return_ann | ty_params bad_args return_ann
ty_params::= ((LANGLE|LT) comma_names (RANGLE|GT))?
args::= (PARENNOSPACE|PARENAFTERBRACE) (binding (COMMA binding)*)? RPAREN
bad_args::= PARENSPACE (binding (COMMA binding)*)? RPAREN
return_ann::= (THINARROW ann)?
doc_string::= (DOC STRING)?
where_clause::= (WHERE block)?

check_expr::= (CHECK|EXAMPLES) STRING COLON block END
	| (CHECKCOLON|EXAMPLESCOLON) block END
check_test::= binop_expr check_op (PERCENT (PARENSPACE|PARENNOSPACE) binop_expr RPAREN)? binop_expr (BECAUSE binop_expr)?
          | binop_expr check_op_postfix (BECAUSE binop_expr)?
          | binop_expr


data_expr::= DATA NAME ty_params COLON (first_data_variant)? data_variant* data_sharing where_clause END
variant_constructor::= NAME variant_members
first_data_variant::= variant_constructor data_with | NAME data_with
data_variant::= BAR variant_constructor data_with | BAR NAME data_with
variant_members::= PARENNOSPACE (variant_member (COMMA variant_member)*)? RPAREN
variant_member::= (REF)? binding
data_with::= (WITH fields)?
data_sharing::= (SHARING fields)?

var_expr::= VAR toplevel_binding EQUALS binop_expr
rec_expr::= REC toplevel_binding EQUALS binop_expr
assign_expr::= NAME COLONEQUALS binop_expr

when_expr::= WHEN binop_expr (BLOCK|COLON) block END

binop_expr::= expr (binop expr)*

binop::= PLUS | DASH | TIMES | SLASH | LEQ | GEQ | EQUALEQUAL | SPACESHIP | EQUALTILDE
     | NEQ  | LT  | GT | AND | OR | CARET

check_op::= IS | ISEQUALEQUAL | ISEQUALTILDE | ISSPACESHIP | ISROUGHLY
        | ISNOT | ISNOTEQUALEQUAL | ISNOTEQUALTILDE | ISNOTSPACESHIP
        | RAISES | RAISESOTHER
        | SATISFIES | SATISFIESNOT
        | RAISESSATISFIES | RAISESVIOLATES

check_op_postfix::= RAISESNOT

expr::= paren_expr | id_expr | prim_expr
    | lambda_expr | method_expr | app_expr
    | obj_expr | tuple_expr | tuple_get
    | dot_expr
    | template_expr
    | bracket_expr  //# NOTE(joe)::= experimental for access
    | get_bang_expr | update_expr
    | extend_expr
    | if_expr | if_pipe_expr | cases_expr
    | for_expr
    | user_block_expr | inst_expr
    | multi_let_expr | letrec_expr
    | type_let_expr
    | construct_expr
    | table_select
    | table_extend
    | table_filter
    | table_order
    | table_extract
    | table_update
    | table_expr
    | load_table_expr
    | reactor_expr

template_expr ::= DOTDOTDOT

bad_expr::= UNTERMINATED_STRING | UNTERMINATED_BLOCK_COMMENT | BAD_OPER | BAD_NUMBER | UNKNOWN

//# paren_exprs must be preceded by a space, so as not be be confused with
//# function application
paren_expr::= (PARENSPACE|PARENAFTERBRACE) binop_expr RPAREN

id_expr::= NAME

prim_expr::= num_expr | frac_expr | rfrac_expr | bool_expr | string_expr

num_expr::= NUMBER
frac_expr::= RATIONAL
rfrac_expr::= ROUGHRATIONAL
bool_expr::= TRUE | FALSE
string_expr::= STRING

lambda_expr::= LAM fun_header (BLOCK|COLON) doc_string block where_clause END
	| LBRACE fun_header (BLOCK|COLON) doc_string block where_clause RBRACE

method_expr::= METHOD fun_header (BLOCK|COLON) doc_string block where_clause END

app_expr::= expr app_args
//# These two productions are carefully rigged to *not* parse unary `f (x)`
//# otherwise, we'd admit ambiguous parses.  Instead, parse_pyret detects these
//# two cases and produces a parse error, while well_formedness detects the unary
//# case and produces a well_formedness error with a similar message.
     | expr PARENSPACE RPAREN
     | expr PARENSPACE binop_expr COMMA binop_expr (COMMA binop_expr)* RPAREN

//# application must have the function expression immediately adjacent to
//# the argument list, so as not to be confused with parenthesized exprs
app_args::= PARENNOSPACE opt_comma_binops RPAREN
opt_comma_binops::= (comma_binops)?
comma_binops::= binop_expr (COMMA binop_expr)*
trailing_opt_comma_binops::= (comma_binops (COMMA)? | )
//# app_arg_elt::= binop_expr COMMA

//# at least one annotation must be provided
inst_expr::= expr LANGLE ann (COMMA ann)* (RANGLE|GT)

tuple_expr::= LBRACE tuple_fields RBRACE
tuple_fields::= binop_expr (SEMI binop_expr)* (SEMI)?

tuple_get::= expr DOT LBRACE NUMBER RBRACE


obj_expr::= LBRACE obj_fields RBRACE | LBRACE RBRACE
obj_fields::= obj_field (COMMA obj_field)* (COMMA)?
obj_field::= key COLON binop_expr
     | REF key (COLONCOLON ann)? COLON binop_expr
     | METHOD key fun_header (BLOCK|COLON) doc_string block where_clause END

fields::= field (COMMA field)* (COMMA)?
field::= key COLON binop_expr
     | METHOD key fun_header (BLOCK|COLON) doc_string block where_clause END
key::= NAME

construct_expr::= LBRACK construct_modifier binop_expr COLON trailing_opt_comma_binops RBRACK
construct_modifier::= | LAZY

table_expr::= TABLE table_headers table_rows END
table_headers::= (list_table_header* table_header)?
list_table_header::= table_header COMMA
table_header::= NAME (COLONCOLON ann)?
table_rows::= (table_row* table_row)?
table_row::= ROW table_items
table_items::= (list_table_item* binop_expr)?
list_table_item::= binop_expr COMMA

//# NOTE(joe)::= just parsing as "fields" for now, and handling naming in
//# desugaring/well_formed, so that better error messages can be given
reactor_expr::= REACTOR COLON
  fields
END

dot_expr::= expr DOT NAME
bracket_expr::= expr LBRACK binop_expr RBRACK

get_bang_expr::= expr BANG NAME

extend_expr::= expr DOT LBRACE fields RBRACE
update_expr::= expr BANG LBRACE fields RBRACE

if_expr::= IF binop_expr (BLOCK|COLON) block else_if* (ELSECOLON block)? END
else_if::= ELSEIF binop_expr COLON block
if_pipe_expr::= ASK (BLOCK|COLON) if_pipe_branch* (BAR OTHERWISECOLON block)? END
if_pipe_branch::= BAR binop_expr THENCOLON block

cases_binding::= (REF)? binding
cases_args::= PARENNOSPACE (cases_binding (COMMA cases_binding)*)? RPAREN
cases_expr::= CASES (PARENSPACE|PARENNOSPACE) ann RPAREN binop_expr (BLOCK|COLON) cases_branch* (BAR ELSE THICKARROW block)? END
cases_branch::= BAR NAME (cases_args)? THICKARROW block

for_bind::= binding FROM binop_expr
for_expr::= FOR expr PARENNOSPACE (for_bind (COMMA for_bind)*)? RPAREN return_ann (BLOCK|COLON) block END

column_order ::= NAME (ASCENDING|DESCENDING)
table_select ::= TABLE_SELECT NAME (COMMA NAME)* FROM expr END
table_filter ::= TABLE_FILTER expr (USING binding (COMMA binding)*)? COLON binop_expr END
table_order  ::= TABLE_ORDER  expr COLON column_order (COMMA column_order)* END
table_extract::= TABLE_EXTRACT NAME FROM expr END
table_update ::= TABLE_UPDATE expr (USING binding (COMMA binding)*)? COLON obj_fields END
table_extend ::= TABLE_EXTEND expr (USING binding (COMMA binding)*)? COLON table_extend_fields END
table_extend_fields::= list_table_extend_field* table_extend_field (COMMA)?
list_table_extend_field::= table_extend_field COMMA
table_extend_field::= key (COLONCOLON ann)? COLON binop_expr
//# Commenting this out until we know whether or not it makes sense
//#     | REF key (COLONCOLON ann)? COLON binop_expr
     | key (COLONCOLON ann)? COLON expr OF NAME

//# More informative to allow missing load_table_specs to parse and mark it as a
//# well_formedness error than to reject it at parse_time
load_table_expr::= LOAD_TABLE COLON table_headers (load_table_specs)? END

load_table_specs::= load_table_spec* load_table_spec
load_table_spec::= SOURCECOLON expr
               | SANITIZE NAME USING expr

user_block_expr::= BLOCK block END

ann::= name_ann | record_ann | arrow_ann | app_ann | pred_ann | dot_ann | tuple_ann

name_ann::= NAME
comma_ann_field::= ann_field (COMMA ann_field)*
trailing_opt_comma_ann_field::= (comma_ann_field (COMMA)? | )
record_ann::= LBRACE trailing_opt_comma_ann_field RBRACE
ann_field::= NAME COLONCOLON ann

tuple_ann::= LBRACE ann (SEMI ann)* (SEMI)? RBRACE

noparen_arrow_ann::= (arrow_ann_args)? THINARROW ann
arrow_ann_args::= comma_anns | (PARENSPACE|PARENNOSPACE|PARENAFTERBRACE) comma_ann_field RPAREN
arrow_ann::= (PARENSPACE|PARENNOSPACE|PARENAFTERBRACE) (arrow_ann_args)? THINARROW ann RPAREN

app_ann::= (name_ann|dot_ann) LANGLE comma_anns (RANGLE|GT)

comma_anns::= ann (COMMA ann)*

pred_ann::= ann PERCENT (PARENSPACE|PARENNOSPACE) id_expr RPAREN

dot_ann ::= NAME DOT NAME

// Tokens

AND ::= "and"
AS ::= "as"
ASCENDING ::= "ascending"
ASK ::= "ask"
BY ::= "by"
CASES ::= "cases"
CHECK ::= "check"
DATA ::= "data"
DESCENDING ::= "descending"
DO ::= "do"
RAISESNOT ::= "does-not-raise"
ELSE ::= "else"
ELSEIF ::= "else if"
END ::= "end"
EXAMPLES ::= "examples"
TABLE_EXTEND ::= "extend"
TABLE_EXTRACT ::= "extract"
FALSE ::= "false"
FOR ::= "for"
FROM ::= "from"
FUN ::= "fun"
HIDING ::= "hiding"
IF ::= "if"
IMPORT ::= "import"
INCLUDE ::= "include"
IS ::= "is"
ISEQUALEQUAL ::= "is=="
ISEQUALTILDE ::= "is=~"
ISNOT ::= "is-not"
ISNOTEQUALEQUAL ::= "is-not=="
ISNOTEQUALTILDE ::= "is-not=~"
ISNOTSPACESHIP ::= "is-not<=>"
ISROUGHLY ::= "is-roughly"
ISSPACESHIP ::= "is<=>"
BECAUSE ::= "because"
LAM ::= "lam"
LAZY ::= "lazy"
LET ::= "let"
LETREC ::= "letrec"
LOAD_TABLE ::= "load-table"
METHOD ::= "method"
MODULE ::= "module"
NEWTYPE ::= "newtype"
OF ::= "of"
OR ::= "or"
PROVIDE ::= "provide"
PROVIDE_TYPES ::= "provide-types"
RAISES ::= "raises"
RAISESOTHER ::= "raises-other-than"
RAISESSATISFIES ::= "raises-satisfies"
RAISESVIOLATES ::= "raises-violates"
REACTOR ::= "reactor"
REC ::= "rec"
REF ::= "ref"
SANITIZE ::= "sanitize"
SATISFIES ::= "satisfies"
TABLE_SELECT ::= "select"
SHADOW ::= "shadow"
TABLE_FILTER ::= "sieve"
SPY ::= "spy"
TABLE_ORDER ::= "order"
TABLE_UPDATE ::= "transform"
TRUE ::= "true"
TYPE ::= "type"
TYPE_LET ::= "type-let"
USING ::= "using"
USE ::= "use"
VAR ::= "var"
SATISFIESNOT ::= "violates"
WHEN ::= "when"

BLOCK ::= "block:"
CHECKCOLON ::= "check:"
DOC ::= "doc:"
ELSECOLON ::= "else:"
EXAMPLESCOLON ::= "examples:"
OTHERWISECOLON ::= "otherwise:"
PROVIDECOLON ::= "provide:"
ROW ::= "row:"
SHARING ::= "sharing:"
SOURCECOLON ::= "source:"
TABLE ::= "table:"
THENCOLON ::= "then:"
WHERE ::= "where:"
WITH ::= "with:"
LBRACK ::= "["
RBRACK ::= "]"
LBRACE ::= "{"
RBRACE ::= "}"
LPAREN ::= "("
RPAREN ::= ")"
SEMI ::= ";"
BACKSLASH ::= "\\"
DOTDOTDOT ::= "..."
DOT ::= "."
BANG ::= "!"
PERCENT ::= "%"
COMMA ::= ","
THINARROW ::= "->"
COLONEQUALS ::= ":="
COLON ::= ":"
BAR ::= "|"
EQUALS ::= "="
LANGLE ::= "<"
STAR ::= "*"
RANGLE ::= ">"
CARET ::= "^"
PLUS ::= "+"
DASH ::= "-"
TIMES ::= "*"
SLASH ::= "/"
SPACESHIP ::= "<=>"
LEQ ::= "<="
GEQ ::= ">="
EQUALEQUAL ::= "=="
EQUALTILDE ::= "=~"
NEQ ::= "<>"
LT ::= "<"
GT ::= ">"
THICKARROW ::= "=>"
COLONCOLON ::= "::"

[blerner]

I'm not sure there's actually a bug here to be fixed? Also, the linked site no longer appears to exist...

[sorawee]

I don't think this is meant to be a bug report. Rather, @mingodad just wanted to inform that this grammar visualization exists, and we could use it if we want to. Maybe we could view it as a feature request to add the grammar visualization to aid the learning.

Re the defunct website: there are other visualization websites that are still functional. E.g.: https://rr.red-dove.com/ui

So I guess the question is, do we find this visualization useful? And if so, do we want to use it somehow?

See also: dafny-lang/dafny#1244. IIUC, @mingodad has been doing this for various other languages as well.