#APPENDIX A: SUMMARY OF GRAMMAR
#
#This section gives a summary of the grammar for the language used by
#Gofer. The non-terminals <interp> and <module> 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 <angle brackets> 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 = ("-" | "~").
|
