三, SIMULA 67协同程序
1,两个或两个以上程序单元之间交错地
执行,这样的程序称为 协同程序
2,SIMULA 67的协同程序是一个类实例
一般形式为,
class 类名 (参数 );
参数说明 ;
begin
说明 ;
语句表 1;
detach;
语言表 2
end
若设类 x,变量 y1和 y2
是对 x的引用,那么可
写成,
y1:-new x(…);
y2:-new x(…);
当遇到一个 new时,建
立类的一个新实例,并
执行类体
3,玩牌游戏
begin boolean gameover; integer winner;
class player(n,hand); integer n;
integer array hand(1:13);
begin ref(player) next;
detach;
while not gameover do
begin 出牌 ;
if gameover then winner:=n
else resume(next)
end
end
ref(player) array p(1:4);integer i;
integer array cards(1:13);
for i:=1 step 1 until 4 do
begin 第 i家拿牌 ;
p(i):-new player(i,cards)
end;
for i:=1 step 1 until 3 do
p(i).next:-p(i+1);
p(4).next:-p(1);
resume (1);
打印胜利者 (winner)
end
四,并发单元
1,一个例子
, 生产者 -消费者, 问题
单元 producer 单元 consumer
repeat 生产一个元素 ;
存放这个元素到缓冲区 ;
forever
repeat 从缓冲区移出一项 ;
对该项执行某个运算 ;
forever
2,几个基本概念
①并发单元的特点,诸程序单元并行活动
②同步问题
?正确访问缓冲区,不会向已满的缓冲区写数据,
不会从空缓冲区读数据
?动作的, 不可分, 与, 可分,
设 t表示所存项目总数,append是生产者向
缓冲区存数的操作,remove是消费者从缓冲区
取数的操作,这两个操作都要修改 t的值,相应
执行操作 (1)t:=t+1和 (2)t:=t-1来实现。假定
(1)和 (2)是这样实现的,
读 t到一个专用寄存器 ;
更新 专用寄存器的值 ;
将专用寄存器的值写到 t;
?互斥,执行 (1)时不能开始执行 (2),反之亦然。
即,(1)和 (2)必须以 互斥 的方式执行,(1)或 (2)
就像不可分的操作。
③进程的并发性,诸进程的执行概念上是可
重叠的（即正在执行的进程尚未终止，另一个
进程可能开始执行）。
3,信号灯
信号灯是一个数据对象,该数据对象采用一个
整数值,并可用原语 P和 V对它进行操作。信号
灯在说明时,以某个整数值对它初始化。
① P,V操作的定义
P(s),if s>0 then s:=s-1
else 挂起当前进程
V(s),if 信号灯上有挂起的进程
then 唤配进程
else s:=s+1
② 原语 P,V是不可再分的原子操作
③ 信号灯满足的要求
?记录挂起的进程 （ 用队列 ）
?唤醒策略 （ 考虑优先级, 时间等 ）
④ 一个例子
,生产者 -消费者”问题
const n=20
shared var 缓冲区长度 n,缓冲区项目总数 t;
semaphare mutex:=1; {用于保证互斥 }
in:=0; {用于同步，可挂起 consumer}
spaces:=n; {用于同步，可挂起 producer}
process producer;
var i:integer;
repeat
producer(i);
P(spaces);
P(mutex);
添加项目 i到缓冲区 ;
V(mutex);
V(in);
forever
end producer;
process consumer;
var j:integer;
repeat
P(in);
P(mutex);
从缓冲区移出一个项目到 j;
V(mutex);
V(spaces);
forever
end consumer;
⑤ 注意,在访问共享资源前,不能忘记执
行一次 P操作 ;释放资源时不要忽略执行一次
V操作
4,管程
① 管程描述并发环境中的抽象数据类型 。
通过这个工具, 自动保证操纵数据结构的
互斥操作 。
② 在访问共享数据结构的合作操作中, 必
须显式使用管程原语 delay和 continue来进
行编程 。
type fifostorage=
monitor
var contents,array[1..N] of integer；
tot:0..n;
in:1..n;
out:1..n;
sender,receiver,queue;
procedure entry append(var item:integer);
begin if tot=n then delay(sender);
contents[in]:=item;
in:=(in mod n) + 1;
tot:=tot+1;
continue(receiver)
end;
procedure entry remove(var item:integer);
begin if tot=0 then delay(receiver);
item:=content[out];
out:=(out mod n) + 1;
tot:=tot-1;
continue(sender)
end;
begin
tot:=0; in:=1; out:=1
end
const n=20;
type fifostorage=……;
type producer=process(storage:fifostorage);
var element:integer;
begin cycle
…
storage.append(element);
…
end
end;
type consumer=process(storage:fifostorage);
var datum:integer;
begin cycle
…
storage.remove(datum);
…
end
end;
var meproducer:producer;
youconsumer:consumer;
buffer:fifostrage;
begin
init buffer,meproducer(buffer),youconsumer(buffer)
end
5,会合
—— Ada描述并发过程的同步机制
①一个实例
处理对缓冲区的 append和 remove
task BUFFER-HANDLER is
entry APPEND(ITEM:in INTEGER);
entry REMOVE(ITEM:out INTEGER);
end;
task body BUFFER-HANDLER is
N:constant INTEGER:=20;
CONTENTS:array(1..N) of INTEGER;
IN,OUT:INTEGER range 1..N:=1;
TOT:INTEGER range 0..N:=0;
begin loop
select
when TOT<N =>
accept APPEND(ITEM:in INTEGER) do
CONTENTS(IN):=ITEM;
end;
IN:=(IN mod N) +1;
TOT:=TOT+1;
or
when TOT>0 =>
accept REMOVE(ITEM:out INTEGER) do
ITEM:=CONTENTS(OUT);
end;
OUT:=(OUT mod N)+1;
TOT:=TOT-1;
end select
end loop;
end BUFFER-HANDLER;
② accept语句：类似于过程
③ selcet语句 非确定选择
④,会合, 的说明
调用任务
被调用任务
被调用任务
调用任务
挂起
调用
accept
会合
out
会合终点
挂起
调用
accept 会合 out
会合终点
第四章 程序设计语言和编译程序
第一节 上下文无关文法
一, 文法
文法是描述语言的语法结构的形式规
则,必须准确,易于理解,且描述能力强
1,文法的形式定义
G=(VT,VN,S,P)
例 G0=(VT,VN,S,P),
E→E+T/T
T→T*F/F
F→(E)/i
显然 VT ={+,*,(,),I}
VN ={e,t,f}
S=E
P为上述产生式的集合
说明, ① ?→ ?的读法,
其中 ? ?V*VNV*,? ? V*
② ? → ? 1
? → ? 2
,,
,
? → ? n
缩写为 a→ ? 1| ? 2|…| ? n
2,文法的分类
① 0型文法,产生式形如 ?→ ?
② 1 型文法,│α│<=│β│ 或产生式形如
αAβ→α ?β
(上下文有关文法 )
③ 2型文法,产生式形如 A→α
(上下文无关文法 )
④ 3型文法,产生式形如 A→α 或 A→αB
(正则文法,右线性文法 )
3,简化的上下文无关文法
① 不含形如 A→A 的有害规则
② 不含多余规则
即 A?VN,必有 S ?αAβ *
二, 文法产生的语言
1,推导与归约
① 直接推导, αβ? ?α??
即由产生式右边替换产生式左边
② 推导,α1 ? αn,α1 ? αn
③ 归约,推导的逆过程
举例 E→E+E│E*E│(E)│i
i+i*i的推导过程
* +
?E ?E+E ?E+E*E ?E+E*i ?E+i*i ?i+i*i
? E ?E+E ? i+E ?i+E*E ?i+i*E ?i+i*i
? E ?E*E ?E*i ?E+E*i ?E+i*i ?i+i*i
2,句型和句子
?设文法 G=(VT,VN,S,P),若 S ?α,α?V*,则称 α为
文法 G的一个 句型 。
?若上述 α ?VT,则称 α是一个句子，即只含终结
符的句型是一个 句子 。
*
3,文法产生的语言
文法 G=(VT,VN,S,P)的句子的全体,称为由文法
G产生的语言,记为 L(G),即
L(G)={α│S ? α?α ?VT*} +
G2(I),
I→L│LS
S→T│ST
T→L│D
L→a│b│,,,│z
D→ 0│1│2│,,,│9
G3(S),
S→aS│aP
P→bP│bQ
Q→cQ│c
L(G3)={aibjck│i,j,k?1}
G4(S),
S→aSPQ│abQ
QP→PQ
bP→bb
bQ→bc
cQ→cc
L(G4)={ aibici│i ?1}
① 文法的重要特性,用 有限 规则描述
无穷 语言
② 文法的等价,两个文法 G和 G’,如果
有 L(G)=L(G’ ),则称 G和 G’ 等价
4,短语和句柄
① 短语,设 αβ?是上下文无关文法 G的一个句
型,如果有 S ? αA?,并且 A ? β,则称 β是
句型 αβ?关于非终结符 A的一个短语,或称
β是句型 αβ?的一个短语 。
② 直接短语 （ 简单短语 ）, A ? β
③ 句柄：一个句型的最左直接短语 。
* +
④ 素短语：含有终结符的短语，并且它的
真子串不具有这种特性
⑤最右推导（规范推导）
⑥最左推导
5,推导树
—— 以图的方式表示推导过程
① 推导树是一棵有序的标记树
?每个结点的标记是文法 G的非终结符或终结符；
?标记为 A的内部结点从左到右有子结点 X1，
X2,…,Xn,则 A→X 1… Xn是一个产生式 。
?如果有结点标记为 ?,则它必是叶结点, 且它
是该父结点的唯一子结点 。
② 推导树的构造
例 （ i+i*i）
E
（ E ）
E E *
E E +
i i
i
E
（ E ）
E E +
E E i
i i
*
③ 推导树的 边缘,一棵推导树所有叶结点
的从左到右的连接 。
④ 文法的二义性：一个句子有两棵不同的
推导树 。
⑤ 由推导树确定短语等
1,两个或两个以上程序单元之间交错地
执行,这样的程序称为 协同程序
2,SIMULA 67的协同程序是一个类实例
一般形式为,
class 类名 (参数 );
参数说明 ;
begin
说明 ;
语句表 1;
detach;
语言表 2
end
若设类 x,变量 y1和 y2
是对 x的引用,那么可
写成,
y1:-new x(…);
y2:-new x(…);
当遇到一个 new时,建
立类的一个新实例,并
执行类体
3,玩牌游戏
begin boolean gameover; integer winner;
class player(n,hand); integer n;
integer array hand(1:13);
begin ref(player) next;
detach;
while not gameover do
begin 出牌 ;
if gameover then winner:=n
else resume(next)
end
end
ref(player) array p(1:4);integer i;
integer array cards(1:13);
for i:=1 step 1 until 4 do
begin 第 i家拿牌 ;
p(i):-new player(i,cards)
end;
for i:=1 step 1 until 3 do
p(i).next:-p(i+1);
p(4).next:-p(1);
resume (1);
打印胜利者 (winner)
end
四,并发单元
1,一个例子
, 生产者 -消费者, 问题
单元 producer 单元 consumer
repeat 生产一个元素 ;
存放这个元素到缓冲区 ;
forever
repeat 从缓冲区移出一项 ;
对该项执行某个运算 ;
forever
2,几个基本概念
①并发单元的特点,诸程序单元并行活动
②同步问题
?正确访问缓冲区,不会向已满的缓冲区写数据,
不会从空缓冲区读数据
?动作的, 不可分, 与, 可分,
设 t表示所存项目总数,append是生产者向
缓冲区存数的操作,remove是消费者从缓冲区
取数的操作,这两个操作都要修改 t的值,相应
执行操作 (1)t:=t+1和 (2)t:=t-1来实现。假定
(1)和 (2)是这样实现的,
读 t到一个专用寄存器 ;
更新 专用寄存器的值 ;
将专用寄存器的值写到 t;
?互斥,执行 (1)时不能开始执行 (2),反之亦然。
即,(1)和 (2)必须以 互斥 的方式执行,(1)或 (2)
就像不可分的操作。
③进程的并发性,诸进程的执行概念上是可
重叠的（即正在执行的进程尚未终止，另一个
进程可能开始执行）。
3,信号灯
信号灯是一个数据对象,该数据对象采用一个
整数值,并可用原语 P和 V对它进行操作。信号
灯在说明时,以某个整数值对它初始化。
① P,V操作的定义
P(s),if s>0 then s:=s-1
else 挂起当前进程
V(s),if 信号灯上有挂起的进程
then 唤配进程
else s:=s+1
② 原语 P,V是不可再分的原子操作
③ 信号灯满足的要求
?记录挂起的进程 （ 用队列 ）
?唤醒策略 （ 考虑优先级, 时间等 ）
④ 一个例子
,生产者 -消费者”问题
const n=20
shared var 缓冲区长度 n,缓冲区项目总数 t;
semaphare mutex:=1; {用于保证互斥 }
in:=0; {用于同步，可挂起 consumer}
spaces:=n; {用于同步，可挂起 producer}
process producer;
var i:integer;
repeat
producer(i);
P(spaces);
P(mutex);
添加项目 i到缓冲区 ;
V(mutex);
V(in);
forever
end producer;
process consumer;
var j:integer;
repeat
P(in);
P(mutex);
从缓冲区移出一个项目到 j;
V(mutex);
V(spaces);
forever
end consumer;
⑤ 注意,在访问共享资源前,不能忘记执
行一次 P操作 ;释放资源时不要忽略执行一次
V操作
4,管程
① 管程描述并发环境中的抽象数据类型 。
通过这个工具, 自动保证操纵数据结构的
互斥操作 。
② 在访问共享数据结构的合作操作中, 必
须显式使用管程原语 delay和 continue来进
行编程 。
type fifostorage=
monitor
var contents,array[1..N] of integer；
tot:0..n;
in:1..n;
out:1..n;
sender,receiver,queue;
procedure entry append(var item:integer);
begin if tot=n then delay(sender);
contents[in]:=item;
in:=(in mod n) + 1;
tot:=tot+1;
continue(receiver)
end;
procedure entry remove(var item:integer);
begin if tot=0 then delay(receiver);
item:=content[out];
out:=(out mod n) + 1;
tot:=tot-1;
continue(sender)
end;
begin
tot:=0; in:=1; out:=1
end
const n=20;
type fifostorage=……;
type producer=process(storage:fifostorage);
var element:integer;
begin cycle
…
storage.append(element);
…
end
end;
type consumer=process(storage:fifostorage);
var datum:integer;
begin cycle
…
storage.remove(datum);
…
end
end;
var meproducer:producer;
youconsumer:consumer;
buffer:fifostrage;
begin
init buffer,meproducer(buffer),youconsumer(buffer)
end
5,会合
—— Ada描述并发过程的同步机制
①一个实例
处理对缓冲区的 append和 remove
task BUFFER-HANDLER is
entry APPEND(ITEM:in INTEGER);
entry REMOVE(ITEM:out INTEGER);
end;
task body BUFFER-HANDLER is
N:constant INTEGER:=20;
CONTENTS:array(1..N) of INTEGER;
IN,OUT:INTEGER range 1..N:=1;
TOT:INTEGER range 0..N:=0;
begin loop
select
when TOT<N =>
accept APPEND(ITEM:in INTEGER) do
CONTENTS(IN):=ITEM;
end;
IN:=(IN mod N) +1;
TOT:=TOT+1;
or
when TOT>0 =>
accept REMOVE(ITEM:out INTEGER) do
ITEM:=CONTENTS(OUT);
end;
OUT:=(OUT mod N)+1;
TOT:=TOT-1;
end select
end loop;
end BUFFER-HANDLER;
② accept语句：类似于过程
③ selcet语句 非确定选择
④,会合, 的说明
调用任务
被调用任务
被调用任务
调用任务
挂起
调用
accept
会合
out
会合终点
挂起
调用
accept 会合 out
会合终点
第四章 程序设计语言和编译程序
第一节 上下文无关文法
一, 文法
文法是描述语言的语法结构的形式规
则,必须准确,易于理解,且描述能力强
1,文法的形式定义
G=(VT,VN,S,P)
例 G0=(VT,VN,S,P),
E→E+T/T
T→T*F/F
F→(E)/i
显然 VT ={+,*,(,),I}
VN ={e,t,f}
S=E
P为上述产生式的集合
说明, ① ?→ ?的读法,
其中 ? ?V*VNV*,? ? V*
② ? → ? 1
? → ? 2
,,
,
? → ? n
缩写为 a→ ? 1| ? 2|…| ? n
2,文法的分类
① 0型文法,产生式形如 ?→ ?
② 1 型文法,│α│<=│β│ 或产生式形如
αAβ→α ?β
(上下文有关文法 )
③ 2型文法,产生式形如 A→α
(上下文无关文法 )
④ 3型文法,产生式形如 A→α 或 A→αB
(正则文法,右线性文法 )
3,简化的上下文无关文法
① 不含形如 A→A 的有害规则
② 不含多余规则
即 A?VN,必有 S ?αAβ *
二, 文法产生的语言
1,推导与归约
① 直接推导, αβ? ?α??
即由产生式右边替换产生式左边
② 推导,α1 ? αn,α1 ? αn
③ 归约,推导的逆过程
举例 E→E+E│E*E│(E)│i
i+i*i的推导过程
* +
?E ?E+E ?E+E*E ?E+E*i ?E+i*i ?i+i*i
? E ?E+E ? i+E ?i+E*E ?i+i*E ?i+i*i
? E ?E*E ?E*i ?E+E*i ?E+i*i ?i+i*i
2,句型和句子
?设文法 G=(VT,VN,S,P),若 S ?α,α?V*,则称 α为
文法 G的一个 句型 。
?若上述 α ?VT,则称 α是一个句子，即只含终结
符的句型是一个 句子 。
*
3,文法产生的语言
文法 G=(VT,VN,S,P)的句子的全体,称为由文法
G产生的语言,记为 L(G),即
L(G)={α│S ? α?α ?VT*} +
G2(I),
I→L│LS
S→T│ST
T→L│D
L→a│b│,,,│z
D→ 0│1│2│,,,│9
G3(S),
S→aS│aP
P→bP│bQ
Q→cQ│c
L(G3)={aibjck│i,j,k?1}
G4(S),
S→aSPQ│abQ
QP→PQ
bP→bb
bQ→bc
cQ→cc
L(G4)={ aibici│i ?1}
① 文法的重要特性,用 有限 规则描述
无穷 语言
② 文法的等价,两个文法 G和 G’,如果
有 L(G)=L(G’ ),则称 G和 G’ 等价
4,短语和句柄
① 短语,设 αβ?是上下文无关文法 G的一个句
型,如果有 S ? αA?,并且 A ? β,则称 β是
句型 αβ?关于非终结符 A的一个短语,或称
β是句型 αβ?的一个短语 。
② 直接短语 （ 简单短语 ）, A ? β
③ 句柄：一个句型的最左直接短语 。
* +
④ 素短语：含有终结符的短语，并且它的
真子串不具有这种特性
⑤最右推导（规范推导）
⑥最左推导
5,推导树
—— 以图的方式表示推导过程
① 推导树是一棵有序的标记树
?每个结点的标记是文法 G的非终结符或终结符；
?标记为 A的内部结点从左到右有子结点 X1，
X2,…,Xn,则 A→X 1… Xn是一个产生式 。
?如果有结点标记为 ?,则它必是叶结点, 且它
是该父结点的唯一子结点 。
② 推导树的构造
例 （ i+i*i）
E
（ E ）
E E *
E E +
i i
i
E
（ E ）
E E +
E E i
i i
*
③ 推导树的 边缘,一棵推导树所有叶结点
的从左到右的连接 。
④ 文法的二义性：一个句子有两棵不同的
推导树 。
⑤ 由推导树确定短语等
