Token, SemStack, AST (IR), Spim for Writeln Expressions and Strings

Input Source Code:
%%t
%%ss
%%dmp -- dump the symbol table - empty at first
beta := 2;
%%dmp
alfa := beta *3;
%%dmp -- symtab has 2 variable names now
writeln ("hi ", beta + 10 * alfa , beta);

simple -i -y -o q0_doitnow.s -l q0_doitnow.list q0_doitnow


in     simple.c
grammar: stmtlist -> lambda
 
Symbol table dump:
SymRoot is NULL => symbol table is empty

Token  : Id
grammar: identifier->Id 
After  : PushId Semstack is:
	 IdEntry (beta)	<+ SemTop
	 StLstEntry
grammar: memref   -> identifier
After  : IdToAddr Semstack is:
	 AddrEntry 	<+ SemTop
	 StLstEntry

Token  : Assignop

Token  : Iconst
grammar: integer_const-> Iconst
After  : PushInt Semstack is:
	 IconstEntry	<+ SemTop
	 AddrEntry 
	 StLstEntry
grammar: primary  -> integer_const
After  : IconstReduce Semstack is:
	 ExprEntry 	<+ SemTop
	 AddrEntry 
	 StLstEntry
grammar: fact     -> primary
grammar: term     -> fact

Token  : Termsym
grammar: expr     -> term
grammar: assignstmt->memeref Assignop expr
After  : Assign Semstack is:
	 StmtEntry 	<+ SemTop
	 StLstEntry
grammar: stmt     -> assignstmt Termsym
grammar: stmtlist -> stmtlist stmt
After  : MergeStmts Semstack is:
	 StLstEntry	<+ SemTop
 
Symbol table dump:
  beta

Token  : Id
grammar: identifier->Id 
After  : PushId Semstack is:
	 IdEntry (alfa)	<+ SemTop
	 StLstEntry
grammar: memref   -> identifier
After  : IdToAddr Semstack is:
	 AddrEntry 	<+ SemTop
	 StLstEntry

Token  : Assignop

Token  : Id
grammar: identifier->Id 
After  : PushId Semstack is:
	 IdEntry (beta)	<+ SemTop
	 AddrEntry 
	 StLstEntry
grammar: memref   -> identifier
After  : IdToAddr Semstack is:
	 AddrEntry 	<+ SemTop
	 AddrEntry 
	 StLstEntry
grammar: primary  -> memref
After  : AddrToPrimary Semstack is:
	 ExprEntry 	<+ SemTop
	 AddrEntry 
	 StLstEntry
grammar: fact     -> primary
grammar: term     -> fact

Token  : Mpysym
grammar: multop   -> Mpysym
After  : Operator  Semstack is:
	 OperEntry 	<+ SemTop
	 ExprEntry 
	 AddrEntry 
	 StLstEntry

Token  : Iconst
grammar: integer_const-> Iconst
After  : PushInt Semstack is:
	 IconstEntry	<+ SemTop
	 OperEntry 
	 ExprEntry 
	 AddrEntry 
	 StLstEntry
grammar: primary  -> integer_const
After  : IconstReduce Semstack is:
	 ExprEntry 	<+ SemTop
	 OperEntry 
	 ExprEntry 
	 AddrEntry 
	 StLstEntry
grammar: fact     -> primary
grammar: term     -> term multop fact
After  : DoArithOp Semstack is:
	 ExprEntry 	<+ SemTop
	 AddrEntry 
	 StLstEntry

Token  : Termsym
grammar: expr     -> term
grammar: assignstmt->memeref Assignop expr
After  : Assign Semstack is:
	 StmtEntry 	<+ SemTop
	 StLstEntry
grammar: stmt     -> assignstmt Termsym
grammar: stmtlist -> stmtlist stmt
After  : MergeStmts Semstack is:
	 StLstEntry	<+ SemTop
 
Symbol table dump:
  alfa
  beta

Token  : Writeln

Token  : Lparen

Token  : StrConst
grammar: actparam  -> StrConst
After  : PushString Semstack is:
	 StrEntry (hi )	<+ SemTop
	 StLstEntry
After  : CreateActParam Semstack is:
	 ParmEntry 	<+ SemTop
	 StLstEntry
grammar: actparamlist->actparam

Token  : Commasym

Token  : Id
grammar: identifier->Id 
After  : PushId Semstack is:
	 IdEntry (beta)	<+ SemTop
	 ParmEntry 
	 StLstEntry
grammar: memref   -> identifier
After  : IdToAddr Semstack is:
	 AddrEntry 	<+ SemTop
	 ParmEntry 
	 StLstEntry
grammar: primary  -> memref
After  : AddrToPrimary Semstack is:
	 ExprEntry 	<+ SemTop
	 ParmEntry 
	 StLstEntry
grammar: fact     -> primary
grammar: term     -> fact

Token  : Plussym
grammar: expr     -> term
grammar: addop    -> Plussym
After  : Operator  Semstack is:
	 OperEntry 	<+ SemTop
	 ExprEntry 
	 ParmEntry 
	 StLstEntry

Token  : Iconst
grammar: integer_const-> Iconst
After  : PushInt Semstack is:
	 IconstEntry	<+ SemTop
	 OperEntry 
	 ExprEntry 
	 ParmEntry 
	 StLstEntry
grammar: primary  -> integer_const
After  : IconstReduce Semstack is:
	 ExprEntry 	<+ SemTop
	 OperEntry 
	 ExprEntry 
	 ParmEntry 
	 StLstEntry
grammar: fact     -> primary
grammar: term     -> fact

Token  : Mpysym
grammar: multop   -> Mpysym
After  : Operator  Semstack is:
	 OperEntry 	<+ SemTop
	 ExprEntry 
	 OperEntry 
	 ExprEntry 
	 ParmEntry 
	 StLstEntry

Token  : Id
grammar: identifier->Id 
After  : PushId Semstack is:
	 IdEntry (alfa)	<+ SemTop
	 OperEntry 
	 ExprEntry 
	 OperEntry 
	 ExprEntry 
	 ParmEntry 
	 StLstEntry
grammar: memref   -> identifier
After  : IdToAddr Semstack is:
	 AddrEntry 	<+ SemTop
	 OperEntry 
	 ExprEntry 
	 OperEntry 
	 ExprEntry 
	 ParmEntry 
	 StLstEntry
grammar: primary  -> memref
After  : AddrToPrimary Semstack is:
	 ExprEntry 	<+ SemTop
	 OperEntry 
	 ExprEntry 
	 OperEntry 
	 ExprEntry 
	 ParmEntry 
	 StLstEntry
grammar: fact     -> primary
grammar: term     -> term multop fact
After  : DoArithOp Semstack is:
	 ExprEntry 	<+ SemTop
	 OperEntry 
	 ExprEntry 
	 ParmEntry 
	 StLstEntry

Token  : Commasym
grammar: expr     -> expr addop term
After  : DoArithOp Semstack is:
	 ExprEntry 	<+ SemTop
	 ParmEntry 
	 StLstEntry
grammar: actparam  -> expr
After  : CreateActParam Semstack is:
	 ParmEntry 	<+ SemTop
	 ParmEntry 
	 StLstEntry
grammar: actparamlist->actparamlist Commasym actparam
After  : MergeActParam Semstack is:
	 ParmEntry 	<+ SemTop
	 StLstEntry

Token  : Id
grammar: identifier->Id 
After  : PushId Semstack is:
	 IdEntry (beta)	<+ SemTop
	 ParmEntry 
	 StLstEntry
grammar: memref   -> identifier
After  : IdToAddr Semstack is:
	 AddrEntry 	<+ SemTop
	 ParmEntry 
	 StLstEntry
grammar: primary  -> memref
After  : AddrToPrimary Semstack is:
	 ExprEntry 	<+ SemTop
	 ParmEntry 
	 StLstEntry
grammar: fact     -> primary
grammar: term     -> fact

Token  : Rparen
grammar: expr     -> term
grammar: actparam  -> expr
After  : CreateActParam Semstack is:
	 ParmEntry 	<+ SemTop
	 ParmEntry 
	 StLstEntry
grammar: actparamlist->actparamlist Commasym actparam
After  : MergeActParam Semstack is:
	 ParmEntry 	<+ SemTop
	 StLstEntry
grammar: writestmt-> Writeln Lparen actparamlist Rparen
After  : Call Semstack is:
	 StmtEntry 	<+ SemTop
	 StLstEntry

Token  : Termsym
grammar: stmt     -> writestmt Termsym
grammar: stmtlist -> stmtlist stmt
After  : MergeStmts Semstack is:
	 StLstEntry	<+ SemTop
grammar: program  -> stmtlist
After  : Done Semstack is:
		EMPTY

Intermediate Representation (AST)

Intermediate Representation - the Abstract Syntax Tree Statements Assign beta gets Immediate Value 2 Assign alfa gets beta multiply Immediate Value 3 Writeln parameters hi beta add Immediate Value 10 multiply alfa beta From codegen.c - DisplayRegs() marks used registers Register: 0 1 2 3 4 5 6 7 8 9 - - - - - - - - - - Used = x: COMPILATION COMPLETE out simple.c

Generated SPIM code

# Register Usage: # $s0 for global variables # .text .globl main main: la $t9, CONST la $s0, GVARS # # Start Code # # Generate Assignment Statement li $t0,2 sw $t0,4($s0) # # Generate Assignment Statement lw $t0,4($s0) mul $t0,$t0,3 sw $t0,0($s0) # # Generate Writeln statement la $a0, S1 li $v0, 4 syscall lw $t0,0($s0) mul $t0,$t0,10 lw $t1,4($s0) add $t0,$t0,$t1 li $v0, 1 move $a0,$t0 syscall li $v0, 1 lw $a0,4($s0) syscall la $a0, S0 li $v0, 4 syscall # # Halt execution li $v0 10 syscall # # Finish up by writing out constants .word 0 CONST: #Constant storage area .data S0: .asciiz "\n" .data S1: .asciiz "hi " # # Reserve space for global variables .word 0 GVARS: # space for Global Variables .data _alfa: .word 0 # Offset at 0 .data _beta: .word 0 # Offset at 4 .data Temp_Wr: .word 0 #just for alignment of write(exprtree)

Execute with spim

SPIM Version 6.2 of January 11, 1999 Copyright 1990-1998 by James R. Larus (larus@cs.wisc.edu). All Rights Reserved. See the file README for a full copyright notice. Loaded: /opt/spim/bin/trap.handler hi 622