[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
Misc:
[2001S]
[2002F]
[SamR]
Back to Stack Frames (1). On to A Sample Pascal Parser.
Held: Friday, 9 April 2004
Summary: Today we continue our investigation of stack frames by considering some particular examples.
Related Pages:
Overview:
factorial
,
so we'll try that first.
function factorial(n: integer): integer; var tmp: integer; begin if (n = 0) then factorial := 1 else begin tmp := factorial(n-1); factorial := n * tmp; end end;
| used | +--------------+ FP | old FP | +--------------+ | return value | +--------------+ | ret. address | +--------------+ SP | n | +--------------+ | unused |
| used | +--------------+ FP | old FP | +--------------+ | return value | +--------------+ | ret. address | +--------------+ | n | +--------------+ | tmp | +--------------+ SP | extra | +--------------+ | unused |
| used | +--------------+ FP | old FP | +--------------+ | return value | +--------------+ | ret. address | +--------------+ | n | +--------------+ | tmp | +--------------+ SP | extra | +--------------+ | our FP | +--------------+ | rec. result | +--------------+ | unused |
factorial
look like?
In a generic language with four bytes per word
BEGIN_FACTORIAL: # Do anything appropriate for the beginning of a procedure call ... # if (n = 0) PUSH 8 # Space for temps START_FACTORIAL_CODE: COMPARE MEM[FP+12], CONSTANT[0] JUMP IF EQUAL TO BASE_CASE JUMP RECURSIVE_CASE # factorial := 1 BASE_CASE: STORE INTO MEM[FP+4] FROM CONSTANT[1] JUMP END_FACTORIAL # tmp := factorial(n-1) RECURSIVE_CASE: # Compute n-1 SUBTRACT CONSTANT[1] FROM MEM[FP+12], STORE IN MEM[SP] # Call factorial ... # Copy the value back STORE INTO MEM[SP-4] FROM MEM[SP+8] # factorial := n * tmp MULTIPLY MEM[FP+12] BY MEM[SP-8], STORE IN MEM[FP+4] JUMP END_FACTORIAL # Clean up END_FACTORIAL: ...
# Do anything appropriate for the beginning of a procedure call ADD CONSTANT[8] to SP
END_FACTORIAL: SUBTRACT CONSTANT[8] from SP
SET FP to MEM[FP]
JMP MEM[FP+8]
STORE INTO MEM[?] FROM MEM[?]
STORE INTO MEM[?] FROM FP
SET FP to SP
ADD CONSTANT[16] to SP
STORE INTO MEM[?], RETURN_HERE
JUMP BEGIN_FACTORIAL RETURN_HERE:
SUBTRACT CONSTANT[16] from SP
Back to Stack Frames (1). On to A Sample Pascal Parser.
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[Honesty]
[Instructions]
[Links]
[Search]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Project]
[Readings]
[Reference]
Misc:
[2001S]
[2002F]
[SamR]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Wed May 5 11:47:11 2004.
The source to the document was last modified on Tue Jan 20 23:06:46 2004.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS362/2004S/Outlines/outline.29.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby