Revisions:

1. (Jan 22) The description for the ternary conditional expression syntax had a typo, with two terms reversed; should now read R = (X if E else Y).
2. (Jan 23) When returning from a function, the return value expression must be wrapped in parentheses.
3. (Feb 2) Allow for empty scopes (that is, scopes with neither any declarations nor statements).
4. (Feb 17) Permit printing integer or Boolean values.

Notation

• Each rule is named on the left
• Alternatives within a rule are separated by the | (pipe) symbol
• Literal character tokens are denoted in red, and references to other named rules are written in italics
• Single line Comments begin with #, and are not apart of the formal grammar

Grammar

program:	bareScope	# program top-level
bareScope:	declarations	# only declarations
	| declarations statements	# both declarations and statements
	| statements	# only statements
scope:	{ bareScope }	# scope enclosed with braces
	| { }	# empty scope
statements:	variable = expression	# assignment
	| if expression scope	# conditional statement
	| if expression scope elseIfArms
	| if expression scope else scope
	| if expression scope elseIfArms else scope
	| while expression scope	# loop while expression is true
	| repeat scope until expression	# loop until expression is true
	| break	# exit out of enclosing loop
	| break integer	# exit out of multiple enclosing loops
	| return ( expression )	# return from a function
	| return	# return from a procedure
	| print outputs	# print to standard output
	| input inputs	# input from standard input
	| procedureName ( )	# procedure call (no arguments)
	| procedureName ( arguments )	# procedure call (with arguments)
	| scope	# nested scope
	| statements statements	# sequence of statements
elseIfArms:	else if expression scope	# else-if arm
	| elseIfArms elseIfArms	# sequence of else-if arms
declarations:	var variableNames compoundType	# declare variables
	| func procedureName ( ) scope	# declare procedure (no arguments)
	| func procedureName ( parameters ) scope	# declare procedure (with arguments)
	| func functionName ( ) scalarType scope	# declare function (no arguments)
	| func functionName ( parameters ) scalarType scope	# declare function (with arguments)
	| declarations declarations	# sequence of declarations
variableNames:	variableName
	| variableNames , variableNames	# comma separated sequence of variable names
scalarType:	integer	# integer type
	| boolean	# Boolean type
compoundType:	scalarType
	| [ bound ] scalarType	# 1-dimensional array type
	| [ bound ] [ bound ] scalarType	# 2-dimensional array type
bound:	integer	# array of length integer
parameters:	parameterNames scalarType	# declare one or more formal parameters
	| parameters , parameters	# sequence of formal parameters
parameterNames:	parameterName
	| parameterNames , parameterNames	# comma separated sequence of parameter names
arguments:	expression
	| arguments , arguments	# comma separated sequence of arguments
outputs:	expression	# integer or Boolean expression value to be printed
	| text	# string constant to be printed
	| newline	# print newline
	| outputs , outputs	# sequence of output arguments
inputs:	variable	# input to this integer variable
	| inputs , inputs	# input sequence
variable:	variableName	# reference to scalar variable
	| arrayName [ expression ]	# reference to 1-dimensional array element
	| arrayName [ expression ] [ expression ]	# reference to 2-dimensional array element
expression:	integer	# literal integer constant
	| - expression	# unary minus
	| expression + expression	# addition
	| expression - expression	# subtraction
	| expression * expression	# multiplication
	| expression / expression	# integer division
	| true	# Boolean constant true
	| false	# Boolean constant false
	| not expression	# Boolean not
	| expression and expression	# Conditional Boolean and
	| expression or expression	# Conditional Boolean or
	| expression = expression	# equality comparison
	| expression != expression	# inequality comparison
	| expression < expression	# less-than comparison
	| expression <= expression	# less-than-or-equal comparison
	| expression > expression	# greater-than comparison
	| expression >= expression	# greater-than-or-equal comparison
	| ( expression )
	| ( expression if expression else expression )	# Python-style ternary conditional expression
	| variable	# reference to local variable
	| functionName ( )	# function call (no arguments)
	| functionName ( arguments )	# function call (with arguments)
	| parameterName	# reference to a formal parameter
variableName:	identifier
arrayName:	identifier
functionName:	identifier
parameterName:	identifier
procedureName:	identifier

Notes

• The term identifier referenced in the grammar refer to C-style language identifiers: they begin with either an underscore or any upper or lower case alphabetical letter, followed by zero or more underscores, upper/lower alphabetical letters or numeric digits. As a regular expression: [_a-zA-Z][_a-zA-Z0-9]*.

• The term text is a string of ASCII characters (excluding newlines or double quotes) enclosed in double quotes ("). As a regular expression: ["][^"\n\r]*["]. The maximum allowable length of a string is 255 characters.

• The term integer referenced in the grammar refer to non-negative literal constants (i.e. starting from 0) in base 10 decimal notation. Negative constants are treated as expressions built using the unary minus operator. As a regular expression: 0 | [1-9][0-9]*.

• The built-in integer data type is internally represented as a signed 32-bit integer, ranging from −2_147_483_648 to 2_147_483_647. A 32-bit quantity will sometimes be referred to as a word of memory.

• Single line comments begin with // and extend until the end of the line. Multi-line comments begin with /* and end with */. Multi-line comments cannot be nested.

• Lexical tokens may be separated by repeated whitespace: spaces, tabs, newlines or comments. Whitespace is required to separate integers, reserved keywords and identifiers. Otherwise no whitespace is required.

• Every identifier must be declared before it may be used.

• Arrays use C-style indexing, starting from index 0 up to bound - 1 inclusive. Every array access must be checked, that is, the index must be compared at runtime against the bound before every use. Any attempted over or under bounds access must result in a fatal runtime error.

• Arguments to functions/procedures are passed by value.

Expressions

• Operands of mixed Boolean and integer type may not be directly compared.
• Arthimetic, unary minus and greater/less than (or equal to) operators may only be applied to operands of integer type.
• The conditional Boolean operators and the unary not operator may only be applied to operands of Boolean type.
• The true and false keywords are understood to represented Boolean valued expressions.
• The equality = and inequality != comparison operators may be applied to either integer or Boolean typed operands, but the type on the left hand side (LHS) must match the type on the right hand side (RHS).
• The Python-style ternary conditional expression R = (X if E else Y) can be interpreted as if E { R = X } else { R = Y }. The expression E must be Boolean valued, while the types of X and Y may either both be Boolean valued or both integer valued.

Operator precedence

• The order of operator precedence is as follows:
  1. Unary -
  2. * and /
  3. + and binary -
  4. =, !=, <, <=, >, >=
  5. not
  6. and
  7. or
• Operators at levels 2, 3, 6 and 7 associate left to right
  • Example: 3 * 4 / 2 is equivalent to (3 * 4) / 2.
• Operators at level 4 do not associate or chain
  • Example: the expression 1 < 2 <= 3 != false is illegal.
• Both the Boolean conditional and and or operators are conditional or short circuiting, in that evaluating them will not trigger evaluation of their right hand side expression if not strictly necessary.
  • For example, evaluating the expression false and f() will never cause the function f to be called since the false implies that the result of evaluation must always be false regardless of the return value of f.
  • Similarly, evaluating the expression true or g() will never call g since the true implies that the result of the evaluation will always be true regardless of g.

---