北航 计算理论 第二章 计算模型2课件.ppt

计算理论;2.2 寄存器机;2.2 寄存器机;2.2 寄存器机;2.2.1 RAM机器;2.2.1 RAM机器;指令： 格式：指令 操作数 指令分类： 寄存器取 LOAD 寄存器存 STORE 跳转 JUMP JGTZ JZERO 运算 ADD SUB MULT DIV 输入 输出 READ WRITE 结束 HALT;直接寻址 寄存器中存放的是操作数。 间接寻址 寄存器中存放的是操作数的地址。;操作数： i表示Ri寄存器的内容，记为C(i)； *i表示间接寻址，操作数的地址是Ri 内容， j=C(i)，即其值是C(C(i))，若j 0则停机； =i表示立即数i。;2.2.1 RAM机器;操作数映射V(a): V(a) = C(a) V(*a) = C(C(a)) V(=a) = a;2.2.1 RAM机器;READ a: C(a) /C(C(a))? 输入带上读入一 个符号，读头右移一位 WRITE a: 输出带上当前位置 ? V(a)，写后 写头右移一位 JMP l: 位置计数器 ? l JGTZ l: 若C(0) 0，则位置计数器 ? l JZERO l: 若C(0) = 0，则位置计数器 ? l HALT: 停机;2.2.1 RAM机器;2.2.1 RAM机器;例：输入X1 X2…Xi…Xn0，其中Xi为1或 2，判断1和2出现的个数是否相同？ ? 设计思路：读到1则加一，读到2则减一，若结果为0则个数相等。;R0: 累加器 R1:存放读入字符 R2:存放差值; 初始化： LOAD =0 （累加器清零） STORE 2 （差值寄存器2清零） READ 1 （读入第一个数）; 读入字符1： LOAD 2 (将差值寄存器的数读入 累加器) ADD =1 (读入的数为1，所以差值加1） STORE 2 (将结果传回差值寄存器);读入字符2： LOAD 2 （则将差值寄存器的数读入累加器） SUB =1 （因为是2，所以差值减1） STORE 2 （将结果传回差值寄存器）;程序如下： LOAD =0 （累加器清零） STORE 2 （差值寄存器2清零） READ 1 （读入第一个数） REPEAT: LOAD 1 （将寄存器1中的数读入累加器中） JZERO END （如果为零，说明结束） SUB =1 (将读入的数减1，使得1变为0，2变为1) JZERO ONE （如果是零,则跳到ONE） SUB =1 JZERO TWO HALT ONE: LOAD 2 ADD =1 STORE 2 JMP NEXT ; TWO LOAD 2 SUB =1 STORE 2 JMP NEXT NEXT: READ 1 （读入输入带上的下一个数） JMP REPEAT （跳回REPEAT进行检查） END: LOAD 2 (结束，将差值寄存器的值读入累加器) JZERO EQUAL（如果为零，说明1和2的个数相等， 跳到EQUAL） WRITE =0 （将不相等的结果0写到输出带中） HALT （程序结束，系统停机） EQUAL: WRITE =1 （相等，则输出1到输出带中） HALT （程序结束，系统停机） ;2.2.2