Revisions:

1. (Mar 14) Fixed typos on scope production

This document outlines the processing required to perform a full semantic analysis for a Source language program. The annotated grammar below adds references to additional semantic analysis operators in blue that refer to specific semantic checks that should be performed.

Annotated grammar

program:	SCtopBegin bareScope SCtopEnd	# program top-level
bareScope:	declarations SCdecls	# only declarations
	| declarations SCdecls statements	# both declarations and statements
	| statements	# only statements
scope:	SCminorBegin { bareScope } SCminorEnd	# scope enclosed with braces
	| { }	# empty scope
statements:	variable = expression CTassign	# assignment
	| if expression CTbool scope	# conditional statement
	| if expression CTbool scope elseIfArms
	| if expression CTbool scope else scope
	| if expression CTbool scope elseIfArms else scope
	| while expression CTbool scope	# loop while expression is true
	| repeat scope until expression CTbool	# loop until expression is true
	| break STbreak	# exit out of enclosing loop
	| break integer STbreak STloopDepth	# exit out of multiple enclosing loops
	| return ( expression ) STreturnFunc CTreturn	# return from a function
	| return STreturnProc	# return from a procedure
	| print outputs	# print to standard output
	| input inputs	# input from standard input
	| procedureName ( ) RzeroArgs	# procedure call (no arguments)
	| procedureName ( arguments ) RmatchArgs	# procedure call (with arguments)
	| scope	# nested scope
	| statements statements	# sequence of statements
elseIfArms:	else if expression CTbool scope	# else-if arm
	| elseIfArms elseIfArms	# sequence of else-if arms
declarations:	var variableNames compoundType Dvariables	# declare variables
	| func SCprocBegin procedureName ( ) Dproc scope SCprocEnd DlinkScope
	| func SCprocBegin procedureName ( parameters ) Dproc scope SCprocEnd DlinkScope
	| func SCfuncBegin functionName ( ) scalarType Dfunc scope SCfuncEnd SThasReturn DlinkScope
	| func SCfuncBegin functionName ( parameters ) scalarType Dfunc scope SCfuncEnd SThasReturn DlinkScope
	| declarations declarations	# sequence of declarations
variableNames:	variableName
	| variableNames , variableNames	# comma separated sequence of variable names
scalarType:	integer Tint	# integer type
	| boolean Tbool	# 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 Dparams	# declare one or more formal parameters
	| parameters , parameters	# sequence of formal parameters
parameterNames:	parameterName
	| parameterNames , parameterNames	# comma separated sequence of parameter names
arguments:	expression CTargument
	| 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 CTint	# input to this integer variable
	| inputs , inputs	# input sequence
variable:	variableName Tvar	# reference to scalar variable
	| arrayName [ expression CTint ] Tarr	# reference to 1-dimensional array element
	| arrayName [ expression CTint ] [ expression CTint ] Tarr	# reference to 2-dimensional array element
expression:	integer Tint	# literal integer constant
	| - expression CTint Tint	# unary minus
	| expression CTint + expression CTint Tint	# addition
	| expression CTint - expression CTint Tint	# subtraction
	| expression CTint * expression CTint Tint	# multiplication
	| expression CTint / expression CTint Tint	# integer division
	| true Tbool	# Boolean constant true
	| false Tbool	# Boolean constant false
	| not expression CTbool Tbool	# Boolean not
	| expression CTbool and expression CTbool Tbool	# Conditional Boolean and
	| expression CTbool or expression CTbool Tbool	# Conditional Boolean or
	| expression = expression CTmatch Tbool	# equality comparison
	| expression != expression CTmatch Tbool	# inequality comparison
	| expression CTint < expression CTint Tbool	# less-than comparison
	| expression CTint <= expression CTint Tbool	# less-than-or-equal comparison
	| expression CTint > expression CTint Tbool	# greater-than comparison
	| expression CTint >= expression CTint Tbool	# greater-than-or-equal comparison
	| ( expression ) Texpr
	| ( expression if expression CTbool else expression ) CTvalues Tcond	# Python-style ternary conditional expression
	| variable	# reference to local variable
	| functionName ( ) RzeroArgs Treturn	# function call (no arguments)
	| functionName ( arguments ) RmatchArgs Treturn	# function call (with arguments)
	| parameterName Tparam	# reference to a formal parameter
variableName:	identifier CTscalar
arrayName:	identifier CTarray
functionName:	identifier RfuncId
parameterName:	identifier CTparam
procedureName:	identifier RprocId

Semantic analysis operators

Scopes

• SCtopBegin Start top-level program scope.
• SCtopEnd End top-level program scope.
• SCdecls Associate declaration(s) with immediately enclosing scope.
• SCfuncBegin Start function scope.
• SCfuncEnd End function scope.
• SCminorBegin Start minor scope.
• SCminorEnd End minor scope.
• SCprocBegin Start procedure socpe
• SCprocEnd End procedure scope.

Declarations

• Dproc Declare procedure with given parameters (if any) in outer enclosing scope.
• Dfunc Declare function with given parameters (if any) and return type in outer enclosing scope.
• DlinkScope Link procedure/function body scope with declaration.
• Dparams Declare typed parameters within enclosing procedure/function scope.
• Dvariables Declare typed variables within enclosing scope.

Statements

• STbreak Check that break statement is directly inside of a loop.
• STreturnFunc Check that return ( expression ) statement is directly inside of a function.
• STreturnProc Check that return statement is directly inside of a procedure.
• STloopDepth Check that integer is greater than 0 and less than or equal to the number directly enclosing loops.
• SThasReturn Check that function body contains at least one return ( expression ) statement.

Expression types

• Tbool Set result type to boolean.
• Tint Set result type to integer.
• Texpr Set result type to the type of the expression.
• Tcond Set result type to the type of the conditional value expressions.
• Tparam Set result type to the type of parameterName.
• Tvar Set result type to the type of variableName.
• Tarr Set result type to the type of array element.
• Treturn Set result type to the return type of the function.

Expression type checking

• CTbool Check that the type of expression is boolean.
• CTint Check that the type of expression is integer.
• CTmatch Check that the left and right operand expressions are of the same type.
• CTvalues Check that both value expressions in conditional are of the same type.
• CTassign Check that the left-hand side variable reference and right-hand side value expression in assignment are of the same type, and that the assignment is valid.
• CTreturn Check that the expression type matches the return type of the enclosing function.
• CTargument Check that the type of the argument expression matches the type of the corresponding formal parameter declaration.
• CTscalar Check that the identifier has been declared as a scalar variable.
• CTarray Check that the identifier has been declared as an array.
• CTparam Check that the identifier has been declared as a parameter.

Functions and procedures

• RfuncId Check that the identifier has been declared as a function.
• RprocId Check that the identifier has been declared as a procedure.
• RzeroArgs Check that the function or procedure was zero arguments.
• RmatchArgs Check that the number of arguments is equal to the number of formal parameters.

Analysis summary

• Identifiers must be declared in some enclosing scope, and must not be redeclared within the same directly enclosing minor scope:
  • The identifier used in a scalar variable expression must match with a corresponding scalar variable declaration.
  • The identifier used in a array accessor expression must match with a corresponding array variable declaration:
    • The number of dimensions must also match.
  • The identifier used in a procedure call statement must match with a corresponding statement declaration.
  • The identifier used in a function call expression must match with a corresponding function declaration.
• Annotate each expression with its corresponding value type:
  • Constant expressions take on their natural corresponding value type.
  • Scalar variable expressions take on the type of the declaration for that variable or formal parameter.
  • Array variable expressions take on the base type of the declaration for that array.
  • Unary and binary expressions take on the type according to their operator:
    • Arithmetic expressions are integer valued.
    • Boolean conditional expressions are Boolean valued.
    • Ordering comparisons are Boolean valued.
    • Equality/inequality comparisons are Boolean valued.
  • Ternary conditional expressions take on the value of their value expressions (left and right), which must match eachother.
  • A function call expression takes on the return type of the corresponding declared function.
• Check the types of all expressions that appear within other expressions:
  • Unary and binary operators require operands that match with their operator:
    • Arithmetic expressions and ordering comparisons require integer valued operands.
    • Boolean conditional expressions require Boolean valued operands.
    • Equality/inequality expressions require that their operands match value types.
  • Ternary conditional expressions require that their left and right value expressions match value types.
  • Function call arguments must match the type of the corresponding formal parameter declaration.
  • The indices of an array variable expression must be integer valued.
• Check the types of all expressions that appear within statements:
  • The left-hand side of an assignment must be something that can be assigned into, and must match the type of the right-hand side expression.
  • All expressions in if, while, and repeat...until statements must be Boolean valued.
  • The value type of the expression in a return ( expression ) statement must match the return type of the enclosing function declaration.
  • Procedure call argument expressions must match the type of the corresponding formal parameter declaration.
  • The variable inputs to an input statement must be something that can be assigned into, and must be integer valued.
• Check the legality of all statements:
  • A bare return can only appear within a directly enclosing procedure.
  • An return with expression can only appear within a directly enclosing function.
  • An unconditional or multi-level break can only appear within a loop.
  • A multi-level break must break out of at least 1 loop, and cannot break out of more enclosing loops that are present within the enclosing major scope.

Correct operation of a semantic analyzer

• A semantic analyzer should attempt to find all semantic errors in the program that it is analyzing.
• Stopping after the first error is not sufficient behaviour.
• Continue processing past an error where possible, and do not introduce spurious errors as a result of earlier ones.

The meaning of "directly inside"

The definitions of STbreak, STloopDepth, STreturnFunc and STreturnProc refer to being directly inside of, or within a directly enclosing loop, function or procedure. This refers to statements that would otherwise be legal, except for the presence of the loop or procedure/function between the statement and the intended enclosing context. These restrictions should reset at procedure and function boundaries. For example:

func F() integer {
    func P() {
        return (488)    // illegal, violates STreturnFunc
    }
}

func Q() {
    func G() integer {
        return          // illegal, violates STreturnProc
    }
}

while true {
    func R() {
        break           // illegal, violates STbreak
    }

    func H() integer {
        break 1         // still illegal
    }
}

while true {
    func S() {
        while true {
            break 2     // illegal, violates STloopDepth
        }
    }
}

func J() boolean {
    while true {
        func T() {
            repeat {
                if false {
                    break       // legal, within a loop
                } else {
                    return      // legal, also within a procedure
                }
            } until true
        }
    }
}

Do not change the Source language syntax

This document is a companion to the Source language specification, and should not be seen to change that specification in any way. Nor should you, through your implementation of a semantic analyzer, change the syntax of the language in any way. If you find any point on which these two documents disagree, please report this to the instructor and consider this document to be in error.

---