This document provides an overview of the code generation steps required to complete the backend for your Source language compiler. The annotated grammar below adds references to code generation actions in blue that describe what code should be emitted for the given language construct.

See the lecture slides for details on the Machine architecture and instruction set.

Annotated grammar

program:	CGtopBegin bareScope CGtopEnd	# program top-level
bareScope:	declarations	# only declarations
scope:	{ bareScope }	# scope enclosed with braces
	| declarations statements	# both declarations and statements
	| statements	# only statements
declarations:	var variableNames compoundType	# declare variables
	| func procedureName ( ) CGroutinePrologue scope CGroutineEpilogue CGemitRoutine
	| func procedureName ( parameters ) CGroutinePrologue scope CGroutineEpilogue CGemitRoutine
	| func functionName ( ) scalarType CGroutinePrologue scope CGroutineEpilogue CGemitRoutine
	| func functionName ( parameters ) scalarType CGroutinePrologue scope CGroutineEpilogue CGemitRoutine
	| 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
	| { }	# empty scope
statements:	variable = expression CGassign	# assignment
	| if expression CGifBranch scope CGifEnd	# conditional statement
	| if expression CGifBranch scope CGifEnd elseIfArms
	| if expression CGifBranch scope CGifEnd else scope
	| if expression CGifBranch scope CGifEnd elseIfArms else scope
	| while expression CGwhileBranch scope CGwhileTop	# loop while expression is true
	| repeat scope until expression CGrepeatLoop	# loop until expression is true
	| break CGbreak	# exit out of enclosing loop
	| break integer CGbreak	# exit out of multiple enclosing loops
	| return ( expression ) CGreturnSave CGroutineEnd	# return from a function
	| return CGroutineEnd	# return from a procedure
	| print outputs	# print to standard output
	| input inputs	# input from standard input
	| procedureName ( ) CGprocCall	# procedure call (no arguments)
	| procedureName ( arguments ) CGprocCall	# procedure call (with arguments)
	| scope	# nested scope
	| statements statements	# sequence of statements
elseIfArms:	else if expression CGifBranch scope CGifEnd	# else-if arm
	| elseIfArms elseIfArms	# sequence of else-if arms
arguments:	expression CGsaveArg
	| arguments , arguments	# comma separated sequence of arguments
outputs:	expression CGprintExpr	# integer or Boolean expression value to be printed
	| text CGprintText	# string constant to be printed
	| newline CGprintNewline	# print newline
	| outputs , outputs	# sequence of output arguments
inputs:	variable CGreadInteger CGassign	# input to this integer variable
	| inputs , inputs	# input sequence
variable:	variableName CGnameAddr	# reference to scalar variable
	| arrayName CGnameAddr [ expression CGarrOffset ]	# reference to 1-dimensional array element
	| arrayName CGnameAddr [ expression CGarrOffset ] [ expression CGarrOffset ]	# reference to 2-dimensional array element
expression:	integer CGconst	# literal integer constant
	| - expression CGneg	# unary minus
	| expression + expression CGadd	# addition
	| expression - expression CGsub	# subtraction
	| expression * expression CGmul	# multiplication
	| expression / expression CGdiv	# integer division
	| true CGconst	# Boolean constant true
	| false CGconst	# Boolean constant false
	| not expression CGnot	# Boolean not
	| expression CGshortCircuitFalse and expression	# Conditional Boolean and
	| expression CGshortCircuitTrue or expression	# Conditional Boolean or
	| expression = expression CGeq	# equality comparison
	| expression != expression CGneq	# inequality comparison
	| expression < expression CGlt	# less-than comparison
	| expression <= expression CGlte	# less-than-or-equal comparison
	| expression > expression CGgt	# greater-than comparison
	| expression >= expression CGgte	# greater-than-or-equal comparison
	| ( expression )
	| ( expression1 if expression2 else expression3 ) CGternaryIf	# Python-style ternary conditional expression
	| variable CGretrieve	# reference to local variable
	| functionName ( ) CGfuncCall	# function call (no arguments)
	| functionName ( arguments ) CGfuncCall	# function call (with arguments)
	| parameterName CGnameAddr CGretrieve	# reference to a formal parameter
variableName:	identifier
arrayName:	identifier
functionName:	identifier
parameterName:	identifier
procedureName:	identifier

Code generation actions

Program, Major Scopes & Routines

• CGtopBegin Emit code to prepare the top level program environment.
• CGtopEnd Emit code to clean up the top level program environment.
• CGroutinePrologue Emit code that sets up the activation record for the routine, allocates local storage and updates the display for the given lexical level.
• CGroutineEpilogue Emit code that cleans up the activation record, restores the previous value of the display for the given lexical level and unconditionally branches back to the caller.
• CGemitRoutine Gather all code for the body of a routine and emit it sequentially at the top level, saving a reference to the address of the entrypoint to its prologue.

Statements

• CGassign Emit code to store the value of the expression at the address of the variable.
• if statement:
  • CGifBranch Emit code to branch to the next arm of the if statement if the value of the expression is machine false. If there is no next arm, branch to immediately after the if statement itself.
  • CGifEnd Emit code to unconditionally branch to immediately after the if statement.
• Loops:
  • CGwhileBranch Emit code to branch to immediately after the while loop statement if the value of expression is machine false.
  • CGwhileTop Emit code to unconditionally branch to the top of the while loop.
  • CGrepeatLoop Emit code to branch to the top of the repeat loop if expression is machine false.
  • CGbreak Emit code to unconditionally branch to immediately after the enclosing loop referred to by integer (1 if there is no such integer).
• Routines:
  • CGreturnSave Emit code to store the value of expression into the routines' control block.
  • CGroutineEnd Emit code to unconditionally branch to the routines' epilogue.
  • CGprocCall Emit code to call the named procedure with the given arguments (if any) by setting up a return point and unconditionally branching to the procedures' prologue.
  • CGsaveArg Emit code to save the value of expression as an argument for a procedure/function call.
• Output:
  • CGprintExpr Emit code to print the value of expression depending on whether it is integer or Boolean valued.
  • CGprintText Emit code to print the string literal constant text.
  • CGprintNewline Emit code to print the literal newline character (\n or ASCII code 10).
• Input:
  • CGreadInteger Emit code to read an integer valued input from the user.

Variable addressing

You must distinguish between the address and the value of a particular name. The address is a location on the stack (within an activation record) where the name lives, and the value is the machine word that is stored at that address. For arrayName's, the address of the name is also the address where the first element is stored.

• CGnameAddr Emit code that yields the stack storage base address for name given the layout of the activation record and the corresponding major scope where name was declared.
• CGarrOffset Emit code that yields the conversion of the value of expression into a suitable additive offset corresponding to definition of arrayName, and whether expression refers to a 1st or 2nd dimensional index. You may also optionally emit code that checks that expression is within bounds for the corresponding dimension, and prints an error message and halts the machine if it is not.

Expressions

When generating code for an expression, remember that an expression is different from a statement in that it always yields some value.

• CGconst Emit code that yields the corresponding constant value, whether integer or Boolean valued.
• CGneg Emit code that yields the negated the value of expression.
• CGadd Emit code that yields the addition of the values of the two expressions.
• CGsub Emit code that yields the substraction of the values of the two expressions.
• CGmul Emit code that yields the multiplication of the values of the two expressions.
• CGdiv Emit code that yields the division of the values of the two expressions.
• CGnot Emit code that yields the Boolean NOT of the value of expression.
• CGshortCircuitFalse Emit code that evaluates the left expression and yields the value machine false if that expression yields a value of machine false, or otherwise yields the value of the right expression.
• CGshortCircuitTrue Emit code that evaluates the left expression and yields the value machine true if that expression yields a value of machine true, or otherwise yields the value of the right expression.
• CGeq Emit code that yields the value machine true if the value of the two expressions are equal, and machine false otherwise.
• CGneq Emit code that yields the value machine true if the value of the two expressions are unequal, and machine false otherwise.
• CGlt Emit code yields the value machine true if the value of the left expression is less than the value of the right expression, and machine false otherwise.
• CGlte Emit code yields the value machine true if the value of the left expression is less than or equal to the value of the right expression, and machine false otherwise.
• CGgt Emit code yields the value machine true if the value of the left expression is greater than the value of the right expression, and machine false otherwise.
• CGgte Emit code yields the value machine true if the value of the left expression is greater than or equal to the value of the right expression, and machine false otherwise.
• CGternaryIf Emit code that evaluates expression₂, and if it is equal to machine true, yields the value of expression₁, and otherwise yields the value of expression₃.
• CGfuncCall Emit code to call the named function with the given arguments (if any) by setting up a return point and unconditionally branching to the functions' prologue, and finally yielding the return value of that function.
• CGretrieve Emit code that yields the value that is stored at a given address.

---