Grammar railroad diagram

[mingodad]

I've just added this "src/cowfe/parser.y" to https://mingodad.github.io/parsertl-playground/playground/ an Yacc/Lex compatible online editor/tester (select "Cowgol parser" from "Examples" then click "Parse" to see a parser tree for the content in "Input source").

The playground also generates an EBNF understood by https://www.bottlecaps.de/rr/ui to generate a nice navigable railroad diagram.

//
// EBNF to be viewd at https://www.bottlecaps.de/rr/ui
//
// Copy and paste this at https://www.bottlecaps.de/rr/ui in the 'Edit Grammar' tab
// then click the 'View Diagram' tab.
//

program::=
	  statements

statements::=
	  /*%empty*/
	| statements statement

statement::=
	  SEMICOLON
	| RETURN SEMICOLON
	| VAR newid COLON typeref SEMICOLON
	| VAR newid COLON typeref ASSIGN expression SEMICOLON
	| VAR newid ASSIGN expression SEMICOLON
	| expression ASSIGN expression SEMICOLON
	| startloopstatement statements END LOOP
	| INCLUDE STRING SEMICOLON
	| startwhilestatement statements END LOOP
	| BREAK SEMICOLON
	| CONTINUE SEMICOLON
	| IF if_begin if_conditional THEN statements if_optional_else END IF
	| startcase whens END CASE SEMICOLON
	| CONST newid ASSIGN cvalue SEMICOLON
	| TYPEDEF ID IS typeref SEMICOLON
	| startsubcall inputargs SEMICOLON
	| outputargs ASSIGN startsubcall inputargs SEMICOLON
	| SUB newsubid subparams submodifiers substart statements subend SEMICOLON
	| DECL SUB newsubid subparams submodifiers SEMICOLON
	| subimpldecl substart statements subend SEMICOLON
	| INTERFACE newsubid subparams submodifiers SEMICOLON
	| implementsstart substart statements subend SEMICOLON
	| RECORD recordstart recordinherits IS recordmembers END RECORD
	| initdecl OPENBR initialisers CLOSEBR SEMICOLON
	| asmstart asms SEMICOLON

startloopstatement::=
	  LOOP

initwhilestatement::=
	  WHILE

startwhilestatement::=
	  initwhilestatement conditional LOOP

if_begin::=
	  /*%empty*/

if_conditional::=
	  conditional

if_optional_else::=
	  /*%empty*/
	| if_else statements
	| if_elseif if_conditional THEN statements if_optional_else

if_else::=
	  ELSE

if_elseif::=
	  ELSEIF

startcase::=
	  CASE expression IS

whens::=
	  /*%empty*/
	| whens when

when::=
	  beginwhen statements

beginwhen::=
	  WHEN cvalue COLON
	| WHEN ELSE COLON

conditional::=
	  OPENPAREN conditional CLOSEPAREN
	| NOT conditional
	| conditional AND conditional
	| conditional OR conditional
	| expression EQOP expression
	| expression NEOP expression
	| expression LTOP expression
	| expression GEOP expression
	| expression GTOP expression
	| expression LEOP expression

leafexpression::=
	  NUMBER
	| OPENPAREN expression CLOSEPAREN
	| oldid
	| OPENSQ expression CLOSESQ
	| STRING

expression::=
	  leafexpression
	| MINUS expression
	| TILDE expression
	| expression PLUS expression
	| expression MINUS expression
	| expression STAR expression
	| expression SLASH expression
	| expression PERCENT expression
	| expression CARET expression
	| expression AMPERSAND expression
	| expression PIPE expression
	| expression LSHIFT expression
	| expression RSHIFT expression
	| expression AS typeref
	| AMPERSAND expression
	| ALIAS AMPERSAND expression
	| NEXT expression
	| PREV expression
	| BYTESOF varortypeid
	| SIZEOF varortypeid
	| expression OPENSQ expression CLOSESQ
	| expression DOT ID
	| startsubcall inputargs

cvalue::=
	  expression

typeref::=
	  INT OPENPAREN cvalue COMMA cvalue CLOSEPAREN
	| eitherid
	| OPENSQ typeref CLOSESQ
	| typeref OPENSQ cvalue CLOSESQ
	| typeref OPENSQ CLOSESQ
	| INDEXOF varortypeid

newid::=
	  ID

oldid::=
	  ID

eitherid::=
	  ID

varortypeid::=
	  oldid
	| OPENPAREN typeref CLOSEPAREN

startsubcall::=
	  leafexpression

inputargs::=
	  OPENPAREN inputarglist CLOSEPAREN
	| OPENPAREN CLOSEPAREN

inputarglist::=
	  inputarg
	| inputarglist COMMA inputarg

inputarg::=
	  expression

outputargs::=
	  OPENPAREN outputarglist COMMA outputarg CLOSEPAREN

outputarglist::=
	  outputarg
	| outputarglist COMMA outputarg

outputarg::=
	  expression

implementsstart::=
	  SUB newsubid IMPLEMENTS typeref

submodifiers::=
	  /*%empty*/
	| submodifiers EXTERN OPENPAREN STRING CLOSEPAREN

newsubid::=
	  newid

subimpldecl::=
	  IMPL SUB oldid

substart::=
	  IS

subend::=
	  END SUB

subparams::=
	  inparamlist
	| inparamlist COLON paramlist

inparamlist::=
	  paramlist

paramlist::=
	  OPENPAREN CLOSEPAREN
	| OPENPAREN params CLOSEPAREN

params::=
	  param
	| param COMMA params

param::=
	  ID COLON typeref

recordstart::=
	  eitherid

recordinherits::=
	  /*%empty*/
	| COLON typeref

recordmembers::=
	  /*%empty*/
	| recordmember recordmembers

recordmember::=
	  memberid recordat COLON typeref SEMICOLON

recordat::=
	  /*%empty*/
	| AT OPENPAREN cvalue CLOSEPAREN

memberid::=
	  ID

initdecl::=
	  VAR newid COLON typeref ASSIGN

initialisers::=
	  initialiser
	| initialisers COMMA initialiser

initialiser::=
	  /*%empty*/
	| expression
	| startbracedinitialiser initialisers CLOSEBR

startbracedinitialiser::=
	  OPENBR

asmstart::=
	  ASM

asms::=
	  asm
	| asm COMMA asms

asm::=
	  STRING
	| NUMBER
	| oldid

//Tokens

ALIAS ::= "@alias"
AMPERSAND ::= "&"
AND ::= "and"
AS ::= "as"
ASM ::= "@asm"
ASSIGN ::= ":="
AT ::= "@at"
BREAK ::= "break"
BYTESOF ::= "@bytesof"
CARET ::= "^"
CASE ::= "case"
CLOSEBR ::= "}"
CLOSEPAREN ::= ")"
CLOSESQ ::= "]"
COLON ::= ":"
COMMA ::= ","
CONST ::= "const"
CONTINUE ::= "continue"
DECL ::= "@decl"
DOT ::= "."
ELSE ::= "else"
ELSEIF ::= "elseif"
END ::= "end"
EQOP ::= "=="
EXTERN ::= "@extern"
GEOP ::= ">="
GTOP ::= ">"
IF ::= "if"
IMPL ::= "@impl"
IMPLEMENTS ::= "implements"
INCLUDE ::= "include"
INDEXOF ::= "@indexof"
INT ::= "int"
INTERFACE ::= "interface"
IS ::= "is"
LEOP ::= "<="
LOOP ::= "loop"
LSHIFT ::= "<<"
LTOP ::= "<"
MINUS ::= "-"
NEOP ::= "!="
NEXT ::= "@next"
NOT ::= "not"
OPENBR ::= "{"
OPENPAREN ::= "("
OPENSQ ::= "["
OR ::= "or"
PERCENT ::= "%"
PIPE ::= "|"
PLUS ::= "+"
PREV ::= "@prev"
RECORD ::= "record"
RETURN ::= "return"
RSHIFT ::= ">>"
SEMICOLON ::= ";"
SIZEOF ::= "@sizeof"
SLASH ::= "/"
STAR ::= "*"
SUB ::= "sub"
THEN ::= "then"
TILDE ::= "~"
TYPEDEF ::= "typedef"
VAR ::= "var"
WHEN ::= "when"
WHILE ::= "while"

[davidgiven]

That's very cool --- did you generate the yacc-compatible input from the Lemon grammar automatically or by hand? I find railroad diagrams impressively easy to read, although this one is a obfuscated a bit by the way the parser uses a lot of subrules for things like lists.

One of the (many) things on my to-do list, actually, is to rewrite the parser completely, hopefully with something smaller. I've recently had good results with a packrat parser for a BASIC interpreter. See https://github.com/davidgiven/comal65/blob/master/src/_parser.s. The tricky part would be memoisation, but careful design of the parser should avoid most of that...

[mingodad]

I've generated with this extended lemon that has an option to output naked yacc grammar:

lemon-nb -h
Command line syntax error: undefined option.
lemon-nb -h
          ^-- here
Valid command line options for "lemon-nb" are:
  -b           Print only the basis in report.
  -c           Don't compress the action table.
  -d<string>   Output directory.  Default '.'
  -D<string>   Define an %ifdef macro.
  -E           Print input file after preprocessing.
  -f<string>   Ignored.  (Placeholder for -f compiler options.)
  -g           Print grammar without actions.
  -y           Print yacc grammar without actions.
  -Y           Print yacc grammar without actions with full precedences.
  -z           Use yacc rule precedence
  -u           Ignore all precedences
  -I<string>   Ignored.  (Placeholder for '-I' compiler options.)
  -m           Output a makeheaders compatible file.
  -l           Do not print #line statements.
  -O<string>   Ignored.  (Placeholder for '-O' compiler options.)
  -p           Show conflicts resolved by precedence rules
  -q           (Quiet) Don't print the report file.
  -r           Do not sort or renumber states
  -R           Do not use precedence to solve reduce/reduce conflicts
  -s           Print parser stats to standard output.
  -S           Generate the *.sql file describing the parser tables.
  -x           Print the version number.
  -T<string>   Specify a template file.
  -W<string>   Ignored.  (Placeholder for '-W' compiler options.)

That parser in a kind of assembler doesn't seem funny to maintain .