Lexical items

We use a vertical bar, |, to indicate alternatives within a production. A vertical bar at the beginning of a line indicates alternative productions within a grammar. We use Kleene star, *, to indicate the concatenation of 0 or more instances, and Kleene plus, +, to indicate the concatenation of 1 or more instances. Square brackets, [ ], indicate a piece of optional syntax.

In general, whitespace consisting of spaces, tabs, and newlines is ignored. In line comments, however, a newline terminates the comment.

• integer ::= ("0x" | "0X") ('0' - '9' | 'A' - 'F' | 'a' - 'f')+ | ('0' - '9')+
• float ::= ('0' - '9')+ ('.' ('0' - '9')*) | ('0' - '9')+ ('.' ('0' - '9')*) | (('e' | 'E') ['+' | '-'] ('0' - '9')+) | ('0' - '9')+ (('e' | 'E') ['+' | '-'] ('0' - '9')+)
• boolean ::= "true" | "false"
• char ::= "'(char - singlequote)'"
• string ::= "doublequote (char-doublequote)* doublequote
• id ::= ('A' - 'Z' | 'a' - 'z') ('A' - 'Z' | 'a' - 'z' | '_' | '0' - '9')*
• comment ::= "(*" char* "*)" | "//" (char - newline)* newline

FISh terms

• datum ::= integer | float | boolean | char
• int_op ::= "+" | "-" | "*" | "div" | "mod" | "<" | "<=" | ">" | ">=" | "="
• float_op ::= "+." | "-." | "*." | "/." | "<." | "<=." | ">." | ">=." | "=."
• bool_op ::= "&&" | "||"
• unop ::= "-" | "-."
• binop ::= int_op | float_op | bool_op
• coercion ::= "#" | "!"
• combinator ::= "abort" | "assign" | "cond" | "equal" | "error" | "fix" | "forall" | "get" | "lendim" | "newexp" | "newvar" | "null" | "numdim" | "output" | "preddim" | "primrec" | "seq" | "shape" | "skip" | "sub" | "succdim" | "undim" | "var2exp" | "whiletrue" | "zerodim"
• prim_constant ::= "acos" | "asin" | "atan" | "atan2" | "ceil" | "cos" | "cosh" | "exp" | "fabs" | "fmod" | "floor" | "int2float" | "log" | "log10" | "pow" | "sin" | "sinh" | "sqrt" | "tan" | "tanh"
• exp_decl ::= id "=" term
• shape_decl ::= "#" id "=" term
• decl ::= exp_decl | shape_decl
• decl_list ::= decl | decl "and" decl_list
• parameter_list = variable | variable parameter_list
• binder ::= id "=" term id parameter_list "=" term
• binder_list ::= binder | binder "and" binder_list
• term_comma_list ::= term | term "," term_comma_list
• datum_shape ::= "int_shape" | "float_shape" | "bool_shape" | "char_shape"
• shape_list ::= term | ":" shape_list | term_comma_list ":" shape_list
• braced_shape_list ::= "{" shape_list "}"
• shape_term ::= datum_shape | braced_shape_list
• fill_term ::= "fill" shape_term "with" "[" comma_term_list "]"
• for_bounds ::= "(" for_bounds ")" | variable "<" term | term "<=" variable "<" term
• term_semicolon_list ::= | term | term ";" term_semicolon_list
• zerodim_term ::= "[" term "]"
• succdim_term ::= "|" term_semicolon_list "|"
• term ::=
  id
  | datum
  | string
  | prim_constant
  | combinator
  | shape_term
  |
  | "(" term ")"
  | term term
  | coercion term
  | unop term
  | term binop term
  | term "." term
  | term ";" term
  | term ":=" term
  | term "[" term "]"
  | zerodim_term
  | succdim_term
  | fill_term
  | "fun" id "->" term
  | "fun" "(" id ":" phrase_type ")" "->" term
  | "if" term "then" term "else" term
  | "new" decl_list "in" term "end"
  | "new" decl_list "in" term "return" id
  | "let" ["rec"] binder_list "in" term
  | term "where" ["rec"] binder_list
  | "for" for_bounds "do" term "done"
  | "while" term "do" term "done"
  | "(" term ":" phrase_type ")"
• array_type ::= id
  | datum
  | "[" array_type "]"
• static_datum ::= size
  | cost
  | fact
  | mark
• shape_type ::= static_datum
  | "#" array_type
• phrase_type ::= id
  | "#" id
  | "exp" array_type
  | "exp" shape_type
  | "var" array_type
  | comm
  | phrase_type "->" phrase_type

Operator precedence

right .
right ;
right :=
left &&
left ||
left = <= > >= < =. <=. >. >=. <
left + - +. -.
left * div mod *. /.
left application
right ! # @ - -.
none []