CS 320: Homework2Operational Semantics Required problems: 3,5,6. Optional problems: 1,2,4.
Problem 1. Optional
Consider the following language L0:
constants program commands stack
const::intstring
prog::comcom;prog
com:: adddiv
S::type1v1; type2v2; ; type3vn
Due : Sunday, December 8, 23:59pm
wherev1,v2,,vn areconstantsintorstringandtypei int,string. Consider the following rules for add and div :
ADD
ADDERROR1
add ; p intv2::intv1::S p intv2 v1::S
add ; p p :error :::
ADDEMPTY
add ; p typev::p :error :::typev::
add ; p stringv::S p :error :::stringv::S
ADDERROR2
add ; p intv2::stringv1::S p :error :::intv2::stringv1::S 1
ADDERROR3
v10
div; pintv2::intv1::Spintv2v1::S
DIV
DIV0
DIVERROR1
div ;
p intv2::int0::S p :error :::intv2::int0::S
div ; p p :error :::
DIVEMPTY
div ; p typev::p :error :::typev::
DIVERROR2
DIVERROR3
div ;
where p is a program. We call a configurationp S final if no rule can be applied to it.
GiventhestackSint2; int3; int4; int0;int2; stringhello;,reduce,usingtherules above, the following configurations to final configurations.
add; add; divS
div; add; add; divS
add; add; add; add; addS
Given the stack Sint0; int4; int2; int3; int4; int2, reduce, using the rules above, the following configurations to final configurations.
add; div; add; add; div; addSdiv; add; divS
2
div ; p stringv::S p :error :::stringv::S
p intv2::stringv1::S p :error :::intv2::stringv1::S
Problem 2. Optional
Consider the following language L1, which is an extension of L0 in Problem 1:
constants program commands stack
const::intstring
prog::comcom;prog
com :: push constadddivrem S::type1v1; type2v2; ; type3vn
wherev1,v2,,vn areconstantsintorstringandtypei int,string.
Design new rules for pop , push , rem , swap and neg satisfying the requirements given for the
interpreter assignment.
Given the stack S , reduce using the rules you designed the following configurations to final configurations.
push 7; push 8; neg S
push 7; neg ; swap S
push 2; push 4; rem S
push 0; push 4; rem S
push hello; push world; pop S push 2; push f oo; swap S
push2; push 3; pop; remS
Given the stack S , reduce using the rules you designed the following configurations to final configurations.
push7; push8; push 5; neg; add; add; push 8rem divS
push1; push3; div; neg; push8; push 4add; swap; pop; neg; push2;
rem ; push hello; push 8; add S
3
Problem 3. Consider, L3, a simplified version of the language for arithmetic expressions presented in class:
v1v2v
v1 add v2mvm
ADD
e add xme add fetchx,mm
FETCHR
expressions operations terms memory fetch function
expr::expraddoptermterm addop:: add
term::v Var
m::x1 v1;x2 v2xn vn
fetch : V armZ
where x1,x2,,xn are meta variables ranging over Var, and v1,v2,,vn are integers. Function fetch takes a variable v and a memory m and returning the value of the variable in the memory
Consider the following rules for add :
eme1m
FETCHL EVAL
x add vm fetchx,m add vm
emem emem
e add v2me1 add v2m COMPOSE
emem
where e,e1,e2 are expressions. We call a configuration em final if no rule can be applied.
Given the memory mx3,y9,z8, reduce using the rules the following configurations to final configurations.
4 add 9 add 8m
xadd3addyadd10addzm
4
Problem 4. Optional
Consider the following language L4 which is an extension of L3 in Problem 3:
expressions operations terms memory fetch function
expr::exproptermterm op :: addminusmul term::v Var
m::x1 v1;x2 v2xn vn
fetch : V armZ
wherex1,x2,,xn aremetavariablesrangingoverVar,andv1,v2,,vn areintegers.
Design new rules for minus and mul by analogy to the rules for add .
Then given the memory mx3;y9;z8, reduce, using the rules you designed, the following configurations to final configurations.
9 minus 8m
12 mul 2m
x add 3 minus 8 add y minus 10 minus zmxadd0minusymul3minuszmul5m
5
Problem 5. Consider the following language and the operational semantics:
M,c1M,c1M,c1;c2M,c1 ;c2
M,x nMx n,skip Mx0
M,if x then c1 else c2M,c2 IF2
Commands Memory
c :: skipc;cxnif x then c else c M : V arZ
xV ar
nZ
SEQ
M,skip;cM,c Mx0
SKIP
ASS
IF1
M,if x then c1 else c2M,c1 M,cM,c M,cM,c
M,cM,c
TRANS
Given the Memory: Mx5; y7, reduce using the rules the following programs in the memory M to final configurations, and draw the trees associated to the derivations. By the notation Mx we mean the value associated with the variable x in M, while the notation Mxn represents the memory M updated with the mapping assigning n to x.
x 7;z 4;skip;w 9
ifxthenskipelsez6
ifxthenx4elsey7;z4;w9
x2;ifxthenx4elsey7;ifxthenz3elsew7;z4
6
Problem 6. Consider the following program:
void f1int z,int r
int k4r;
int uf27;
zzk;
printhello; here
int f2int x
int yx1;
return y
void f3int h
int y4h;
f1y,5;
void main
int z0;
f3z;
Draw the activation record stack with the instances active when executing the function main, which is avail able right before the print in f1. The information in the activation record consists of: return address, functional value, dynamic link, static link, parameters and local variables.
7
Reviews
There are no reviews yet.