#APPENDIX A: SUMMARY OF GRAMMAR # #This section gives a summary of the grammar for the language used by #Gofer. The non-terminals and describe the syntax of #expressions that can be entered into the Gofer interpreter and that of #files of definitions that can be loaded into Gofer respectively. # #The following notational conventions are used in the Grammar which is #specified using a variant of BNF: # # o are used to distinguish names of nonterminals from # keywords. # # o vertical | bars are used to separate alternatives. # # o {braces} enclose items which may be repeated zero or more times. # # o [brackets] are used for optional items. # # o (parentheses) are used for grouping. # # o "quotes" surround characters which might otherwise be confused with # the notations introduced above. # #The following terminal symbols are used but not defined by the grammar: # # varid identifier beginning with lower case letter as described in # section 6. # conid like varid, but beginning with upper case letter. # varsym operator symbol not beginning with a colon, as described in # section 6. # consym constructor function operator, like varsym, but beginning # with a colon character. # integer integer constant, as described in section 7.3. # float floating point constant, as described in section 7.4. # char character constant, as described in section 7.5. # string string constant, as described in section 7.7. # # #Top-level grammar #----------------- # module = ( "{" topdecls "}" # module # ); interp = ( exp [whereClause] # top-level expression # ); topdecls = ( topdecls ";" topdecls # multiple declarations | dataDecl | typeDecl | infixDecl | primDecl | class # class declaration | inst # instance declaration | decls # value declarations # ); dataDecl = ("data" conid {varid} "=" (constr)/"|" # datatype declaration ); typeDecl = ("type" conid {varid} "=" type # synonym declaration ); infixDecl = (( "infixl" | "infixr" | "infix") [digit] (op)/"," # fixity declarations ); # simple = ( conid {varid} # type declaration lhs # ); # constrs = ( constrs "|" constrs # multiple constructors | type consym type # infix constructor | conid {type} # constructor, n>=0 ); constr = type consym type # infix constructor | conid {type} # constructor, n>=0 ; # primDecl = ("primitive" prims "::" type # primitive bindings ); prims = (var string)/"," # primitive binding ; # #Type expressions #---------------- # sigType = ( [context "=>" ] type # [qualified] type # ); context = ( "(" [(pred)/ "," ] ")" # general form | pred # singleton context ); pred = ( conid (type)+ # predicate # ); type = ( ctype [ "->" type ] # function type ); ctype = ( conid {atype} # datatype or synonym | atype ); atype = ( varid # type variable | "(" ")" # unit type | "(" type ")" # parenthesised type | "(" type "," (type)/"," ")"# tuple type | "[" type "]" # list type # #Class and instance declarations #------------------------------- # ); class = ( "class" [context "=>"] pred [cbody] ); cbody = ( "where" "{" cdecls "}" # class body ); cdecls = ( cdecls ";" cdecls # multiple declarations | (var)/ "," "::" type # member functions | fun rhs [whereClause] # default bindings # ); inst = ( "instance" [context "=>"] pred [ibody] ); ibody = ( "where" "{" idecls "}" # instance body ); idecls = ( idecls ";" idecls # multiple declarations | fun rhs [whereClause] # member definition # #Value declarations #------------------ # ); decls = ( decls ";" decls #multiple declarations | (var)/"," "::" sigType #type declaration | fun rhs [whereClause] #function binding | lhsPat rhs [whereClause] #pattern binding, PJT: was pat # ); rhs = ( "=" exp #simple right hand side | (gdRhs)+ #guarded right hand sides # ); gdRhs = ( "|" exp "=" exp #guarded right hand side # ); whereClause = ( "where" "{" decls "}" #local definitions # ); fun = ( var #function of arity 0 | pat varop pat #infix operator | "(" pat varop ")" #section-like notation | "(" varop pat ")" | fun apat #function with argument | "(" fun ")" #parenthesised lhs ); # #Expressions #----------- # exp = ( "\\" (apat)+ "->" exp #lambda expression | "let" "{" decls "}" "in" exp #local definition | "if" exp "then" exp "else" exp #conditional expression | "case" exp "of" "{" alts "}" #case expression | opExp "::" sigType #typed expression | opExp ); opExp = ( opExp op opExp #operator application | pfxExp ); pfxExp = ( "-" appExp #negation | appExp ); appExp = ( appExp atomic #function application | atomic ); atomic = ( var #variable | con #constructor | integer #integer literal | float #floating point literal | char #character literal | string #string literal | "(" ")" #unit element | "(" exp ")" #parenthesised expr. | "(" exp op ")" #sections | "(" op exp ")" | "[" list "]" #list expression | "(" exp "," (exp)/"," ")" #tuple ); # list = ( [ (exp)/"," ] #enumerated list | exp "|" quals #list comprehension | exp ".." #arithmetic sequence | exp "," exp ".." | exp ".." exp | exp "," exp ".." exp ); quals = ( quals "," quals #multiple qualifiers | pat "<-" exp #generator | "let" "{" decls "}" #local definition | exp #boolean guard ); # alts = ( alts ";" alts #multiple alternatives | pat ( "->" exp #single alternative | (gdAlt)+ #guarded alternatives ) [whereClause] #alternative ); # altRhs = ( "->" exp #single alternative # | (gdAlt)+ #guarded alternatives # ); gdAlt = ( "|" exp "->" exp #guarded alternative ); # #Patterns #-------- # pat = ( pat conop pat #operator application | (var | "_") "+" integer #(n+k) pattern | (apat)+ ); lhsPat = ( lhsPat conop lhsPat #PJT: left hand sides of pattern bindings | apat ); apat = ( var #variable | var "@" pat #as pattern | "~" pat #irrefutable pattern | "_" #wildcard | con #constructor | integer #integer literal | char #character literal | string #string literal | "(" ")" #unit element | "(" pat ")" #parenthesised expr. | "(" pat conop ")" #sections | "(" conop pat ")" | "[" [ (pat)/"," ] "]" #list | "(" pat "," (pat)/"," ")" #tuple ); # #Variables and operators #----------------------- # var = ( varid | "(" "-" ")" #variable | "(" varsym ")" #variable identifier ); op = ( varop | conop | "-" #operator ); # varop = ( varsym | "`" varid "`" #variable operator ); # con = ( conid | "(" consym ")" #constructor identifier ); conop = ( consym | "`" conid "`" #constructor operator ); # #Finally, PJT's definitions for literals #--------------------------------------- # integer= (digit)+ ; float = integer "." integer [ ("e" | "E") [ "+"|"-" ] integer ]; varsym = ((symbol | preSymbol) { symbol | ":" }); consym = (":" {symbol | ":"}); varid = (small { letter | digit | "_" | "'" }); conid = (large { letter | digit | "_" | "'" }); string = "\"" { character } "\"" ; char = "'" character "'" ; character = ( letter | digit | symbol | preSymbol | ":" | "\\" ( integer | "n" | "t" | "b" | "\\" | "'" | "\"" ) ); # now this is really trivial... letter = ( small | large); small = ( "a"| "b"| "c"| "d"| "e"| "f"| "g"| "h"| "i"| "j"| "k"| "l"| "m"| "n"| "o" | "p"| "q"| "r"| "s"| "t"| "u"| "v"| "w"| "x"| "y"| "z"); large = ( "A"| "B"| "C"| "D"| "E"| "F"| "G"| "H"| "I"| "J"| "K"| "L"| "M" | "N"| "O"| "P"| "Q"| "R"| "S"| "T"| "U"| "V"| "W"| "X"| "Y"| "Z" ); digit = ( "0"| "1"| "2"| "3"| "4"| "5"| "6"| "7"| "8"| "9" ); octit = ( "0"| "1"| "2"| "3"| "4"| "5"| "6"| "7" ); hexit = ( digit | "A"| "B"| "C"| "D"| "E"| "F"| "a"| "b"| "c"| "d"| "e"| "f" ); cntrl = ( large | "@"| "["| "|"| "]"| "^"| "_" ); charesc = ( "a"| "b"| "f"| "n"| "r"| "t"| "v"| "\\"| "\""| "'"| "&" ); symbol =("!" | "@" | "#" | "$" | "%" | "^" | "&" | "*" | "+" | "." | "/" | "<" | "=" | ">" | "?" | "\\" | "|"); preSymbol = ("-" | "~");