OO第一单元第二次作业 0.题目需求分析 0.1 概念分析 本次作业在第一次作业的基础上添加了指数函数和自定义函数，其中 需要支持嵌套多层括号 新增指数因子，指数函数括号内部包含任意因子 新增自定义函数因子，自定义函数的表达式会给出且其中不会调用其他自定义函数 本次迭代表达式架构上的改变 支持前导0的十进制带符号整数 因子 变量因子，x 幂函数 一般形式：x^非负整数 省略形式：指数为1，x 指数函数：特指以e为底数的指数函数，表示为exp(<因子>)等 一般形式：exp(<因子>)^指数，注：该指数为exp()整体的指数 exp()的指数为非负整数 **省略形式：**指数为1时，写为exp(<因子>) 自定义函数 自定义函数中不会调用其他自定义函数，定义类似于 f(x,y,z) = 表达式（可能不全部包含x,y,z这三个变量） f,g,h是函数的函数名，本次作业中的自定义函数名只包括f,g,h即最多只有三个自定义函数 x,y,z是函数的形参，形参个数为1~3个，且同一函数定义中不会出现重复使用的形参 函数表达式为关于形参的表达式 函数调用的形式为f(因子，因子，因子)，例如f(x^2),g(exp(x^2),exp(x)),h(1,0,-0)，因子为函数调用中的实参，包含任意一种因子 注意：函数定义中不允许出现自定义函数，但是函数调用中的实参可以是自定义函数 常数因子 表达式因子 项 表达式 ​ 关于去括号要求中的**“必要的括号”** 指数函数调用时必要的一层括号exp() 指数函数对应的嵌套因子为不带指数的表达式因子时，该因子两侧必要的一层括号，例如 exp((x+1)^2)中(x+1)中的括号是不合法的，需要展开为不带指数的形式exp((x^2+2*x+1)) 0.2 表达式架构图 大致保留之前的架构，新增指数函数因子类和自定义函数因子类 1.处理流程分析 1.1 字符串预处理 由于自定义函数的引入，可以新增去除,后不必要的+ 1.2 语义分析 1.2.1 Lexer ​ 本次作业中，新增了EXP,F,G,H,COMMA(逗号)等token，需要增加识别功能。 1.2.2 Parser 1.2.2.1 parseExp ​ 在Parser类中新建一个方法parseExp，当我们读到的token为EXP时调用该方法进行解析。首先对括号内的因子进行解析，再对括号外的指数进行解析。 $$ exp()^n \space | \space exp() $$ public Factor parseExp() { // exp(<factor>)^<num> | exp(<factor>) // lexer : exp -> pos = pos + 4 already into the ( // 读到RP时接着往后读看有没有指数 int pow = 1;//默认指数为1 Factor innerFactor = parseFactor(); if (lexer.getCurTokenType() == TokenType.POW) { // 后面有指数 } return new Exp(innerFactor, pow); } 1.2.2.2 parseFunc 1.2.2.2.1 Definer ​ 为了成功地解析自定义函数，我们首先定义出Definer类，他的主要作用是处理自定义函数的定义以及调用。（相当于parseFunc的slave）其中定义出两个HashMap ...

OS预习题三：MIPS 一.思路分析 ​ 刚开始拿到课程组给出的源文件感觉有点发蒙，我们要补全的代码为start.S，文件结构如下 ​ 和题目有关联的主要文件为需要补全的汇编代码start.S，start.S中调用hello.c以及output.c中的函数。这里我们回忆一下编译的过程，如下图 ​ 这时我刚刚回想起汇编文件是.c文件通过编译得到（这里助教推荐汇编文件的后缀名写为.S而不是.s）。题目的要求是补全汇编代码，具体来说就是为函数分配栈帧。 问题1分析 首先分析为print_str创建栈帧，该函数只传递一个参数。 void print_str(const char *buf) { for (int i = 0; buf[i]; i++) { printcharc(buf[i]); } } ​ 我在做题目时的疑问是：用不用为函数的返回地址$ra创建栈空间呢？这个问题实际上就是要分析$ra寄存器的值在函数调用过程中会不会被覆写掉(jr $ra返回)。我们现在分析这个代码的调用过程，有了上学期的MIPS汇编编写经验，相信会比较轻松.print_str内部调用printcharc，这个调用会改变$ra的值，但是我们并不需要考虑维护，因为这个维护是由编译器进行的，**不要忘记该段代码为C语言，还在汇编语言的上层，我们如果想要建立起“平等”的视角，需要把该段代码转换为汇编代码，这就是编译器的工作。**故我们经过分析可以知道，在printstr每次调用子进程时，编译器都为我们做好了各个寄存器的维护，即最后返回时$ra即为初始值，故该段代码我们只需要为其参数分配空间，结束调用后再返还空间（也可以试着脑补把C代码翻译为MIPS，这样就会发现其实翻译过程中会涉及到对$ra等寄存器的维护，这其实就是模拟了编译器为其分配栈帧的过程，可能这样会理解的更深入一些？） addiu sp,sp,-4 问题二分析 问题二实际上就是考察了如果传递六个参数应当怎样分配栈空间， 前四个参数由寄存器a0-a3传递，栈帧中只需要为其分配栈空间，不需要进行存值 后两个参数需要在分配的空间中保存值 这样六个参数需要24字节 addiu sp,sp,-24 lw $<>, 16(sp) lw $<>, 20(sp) 注：栈是向下生长的，分配栈空间需要将栈指针sp向下移动，填充参数不断向上移动sp 二.补全后代码 #include <asm/asm.h> .data str: .asciiz "Hello World\n" # Null-terminated string "Hello World" stored at label 'str' .align 2 # align to 4-byte boundary (2^2) var: .byte 3 # correctly aligned byte: 3 /* '<x>' in the comments is the part to be replaced. */ /* use '.align <x>' to align the following words to 1-byte boundary (disabling word-alignment) */ /* so that the byte 3 and word 7 is "connected" */ /* Your code here. (1/6) */ .align 0 .word 7, 8, 9 .text /* We define '_start_mips' here as the entry of our program. */ EXPORT(_start_mips) .set at .set reorder mtc0 zero, CP0_STATUS li sp, 0x84000000 /* Load the address of the string 'str' into the first parameter register. */ la a0, str /* use 'addiu sp, sp, <x>' to push a proper-sized frame onto the stack for Nonleaf function 'print_str'. */ /* Your code here. (2/6) */ addiu sp, sp,-4 jal print_str /* use 'addiu sp, sp, <x>' to restore stack pointer. */ /* Your code here. (3/6) */ addiu sp, sp,4 /* Set the first four parameters. */ li a0, 0 li a1, 1 li a2, 2 li a3, 3 /* use 'addiu sp, sp, <x>' to push a proper-sized frame onto the stack for Nonleaf function 'hello'. */ /* Your code here. (4/6) */ addiu sp, sp, -24 lw t1, var li t2, 5 /* use 'sw t1, <x>(sp)' to store t1 at the proper place of the stack */ /* so that t1 is 5th argument of function hello. */ /* Your code here. (5/6) */ sw t1, 16(sp) /* use 'sw t2, <x>(sp)' to store t2 at the proper place of the stack */ /* so that t2 is 6th argument of function hello. */ /* Your code here. (6/6) */ sw t2, 20(sp) /* use 'j' to call the function 'hello', we use 'j' instead of 'jal' because 'hello' is 'noreturn' */ j hello

OS预习题2：Makefile ​ 此题只要观察题目中给出的依赖关系树形图即可解决，我的思路是自底向上逐层构建依赖 ​ 源代码为 .PHONY: clean out: calc case_all ./calc < case_all > out case_all: case_add case_sub case_mul case_div cat case_add case_sub case_mul case_div > case_all case_add: casegen ./casegen "add" 100 > case_add case_sub: casegen ./casegen "sub" 100 > case_sub case_mul: casegen ./casegen "mul" 100 > case_mul case_div: casegen ./casegen "div" 100 > case_div calc: calc.c gcc -o calc calc.c casegen: casegen.c gcc -o casegen casegen.c clean: rm -f out calc casegen case_* *.o TIPS ...

OS预习题1：c-exercise ​ OS预习教程中第一道练习题，要求自行实现函数库中几个对于字符串进行操作的函数，为之后的实验打好基础(恢复已经遗忘的C语言记忆)，在做完之后，我搜索了标准库函数中他们的实现，更加简洁优雅。 1. strlen 我的实现 size_t strlen(const char *s) { size_t i = 0; while(s[i] != '\0') { i++; } return i; } 关于size_t类型：size_t 类型表示C中任何对象所能达到的最大长度，它是无符号整数。它是为了方便系统之间的移植而定义的，不同的系统上，定义size_t 可能不一样。**size_t在32位系统上定义为 unsigned int，也就是32位无符号整型。在64位系统上定义为 unsigned long ，也就是64位无符号整形。**size_t 的目的是提供一种可移植的方法来声明与系统中可寻址的内存区域一致的长度。 标准库中的实现 int strlen(const char *str) { const char *p = str; while(*p != '\0') ++p; return p - str; } 可以看出，标准库中的实现优雅之处在于使用了指针间的减法来计算长度。 C语言中的指针运算 ​ 这里参考绿皮书对C语言中的指针运算进行简单回顾。 ​ 若n是一个整形量，p是一个指针，则p+n和p-n是合法的指针运算表达式，指针类型不变，表达式的值由下式确定 $$ value(p \pm n) \space = value(p) \space \pm n*sizeof(T) $$ ​ 即我们知道指针的移动是以指针变量类型的元素为步长移动的而不是以字节为单位进行移动的（这个bug在后面的strsep中我犯过） ...

QEMU ​ 为了开发和运行我们的MOS操作系统，必须要有配套的支持操作系统运行的硬件系统，我们使用硬件模拟器实现。模拟器能够模拟计算机硬件的行为和特性。我们使用QEMU(quick enulator) 1. QEMU的使用 实验中已经将所有需要用到的QEMU操作写到了Makefile中 我们的实验基于MIPS架构 ​ 使用QEMU提供的MIPS环境编译运行代码的指令 // minimal_hello_world.c void printch(char ch) { *((volatile char *)(0xB80003f8U)) = ch; } void print(char *str) { while (*str != '\0') { printch(*str); str++; } } void __start() { print("Hello, world!\n"); while (1) { } } 编译 编译需要使用交叉编译器mips-linux-gnu-gcc $ mips-linux-gnu-gcc \ -EL \ -nostdlib \ -o hello_world.elf \ minimal_hello_world.c ​ 生成目标文件为hello_world.elf 运行 所有的QEMU指令都是qemu-的形式，对于某一体系架构下的模拟，使用 qemu-system-* 对于小端序的mips架构，对应命令为 qemu-system-mipsel 运行以上示例代码 $ qemu-system-mipsel \ -m 64 \ -nographic \ -M malta \ -no-reboot \ -kernel hello_world.elf Hello, world! qemu-system-mipsel：指定小端序mips架构 -nographic模拟中不使用图形界面，使用串口输出 -M 制定模拟的目标机器，这里模拟的是MIPS melta开发板 -no-reboot虚拟机直接退出而不是重启 -kernel指定要启动的内核 退出QEMU ...

GDB终端调试 1. 编译产生Debug版本 ​ 我们在操作系统实验中使用gdb在终端中进行代码调试。在之前的章节中，我们已经学到可以使用 gcc add.c -o adds ​ 指令来对源代码进行编译。但是采用这种方法编译产生的目标程序是Release版本，并不支持我们使用gdb进行调试，要想产生支持gdb调试的Debug版本，我们需要在原编译指令的基础上加入-g参数，具体指令为 gcc -g add.c -o adds 2. GDB操作 1.进入GDB进行调试 ​ 对编译好的程序运行gdb有两种方式， 一种是直接指定文件进入gdb模式 gdb adds 或者先进入gdb模式，再加载可执行文件 $ gdb (gdb) file <filename> 2.运行程序 (gdb) run 3.退出gdb模式 quit 4. 传入额外参数 // echo.c #include <stdio.h> #include <stdlib.h> void usage() { printf("usage: echo <string>\n"); exit(-1); } int main(int argc, char *argv[]) { if (argc != 2) { usage(); } printf("%s\n", argv[1]); return 0; } ​ 在C语言中，argc和argv是预留的为main函数传参的参数，其中 $$ argc\space is \space short \space for \space argument \space count $$ ...

OSpre——C 1. 源代码到可执行文件 预处理->编译->汇编->链接 1.1 预处理——处理# gcc -E hello.c -o hello.i ## -E选项 预处理的工作内容：处理#开头的预处理指令 删除#define，展开宏定义 处理条件编译指令，#if,ifdef 处理#include预处理指令，将包含的文件内容插入到该预处理指令的位置 1.2 编译——预处理文件生成汇编代码文件 gcc -S hello.i -o hello.s # -S参数 1.3 汇编——汇编代码转换为机器代码 gcc -c hello.s -o hello.o # -c参数 1.4 链接 ​ 把多个目标文件的代码段放在一起、数据段放在一起，以及库函数等形成可执行文件。 2. C语言中变量存储类别 2.1 存储期 2.1.1对象与标识符 ​ C语言中对象是连续的一片内存空间，具有起始地址与大小两个属性。标识符是我们用来访问修改对象的字符串（变量名） 例如 int a = 5; // &a = 0x1000 ​ 我们声明了一个int类型，起始地址为0x1000，占用内存大小为4字节的整型变量，变量的标识符为a。 2.2.2 存储期——变量在内存中的生命周期 静态存储期static： 使用static关键字定义的变量static int a 在函数外定义的变量(全局变量) 若对象具有静态存储期，则在程序运行期间一直存在。并且对象的属性不变，即对象的起始地址和所占用的内存空间大小不会变化，不初始化自动初始化为0 自动存储期auto 不使用static关键字定义的变量（例如局部变量）auto int a 程序执行到该变量声明的时候会创建变量对应的对象，在执行到该变量作用域结束后释放对象，不进行初始化则初始值不确定。 如在函数中生命的局部变量，在他的一次调用中的作用域中具有固定的值和地址属性，不同的调用地址属性可能不同 2.2 作用域——标识符在程序中可以被使用的区域 块作用域：块(block)是用花括号括起来的代码区域。定义在块中的变量具有块作用域。块作用域变量的可见范围是从定义处到包含该定义的块的结尾（右花括号）。(对应着局部变量) ...

OO第一单元第一次作业 0.training 想要通过课程组提供的training获取一点点思路QWQ 0.1 training-1 第一部分通过正则表达式的方法将一个只包含数字和“+”“*”符号的表达式转化为后缀表达式 思路梳理（已经提供好的代码）： Mainclass：对于该类，分析得到其处理的思路为构建出可以描述每一项的正则表达式，而后在表达式中进行匹配，再分别对获得的每一项进行后缀化(toString)，最后整体后缀化(toString)并输出 补充正则表达式如下 private static final String patternTerm = "\\d+(\\*\\d+)*"; (该表达式描述了，一项中至少有一个数字以及>=0个形如*number的部分) 上机tips：关于正则表达式，可以右键之后选择第一项进行检查 Expr：该类的重点为实现toString方法，由后缀化的项得到后缀化的表达式 若表达式中只有一项，则该项即为转换后的表达式 （例如 1 * 2 * 3） 若表达式中大于等于两项，对于前两项需要特殊处理，后面的项补充为项*的后缀化形式 StringBuilder sb = new StringBuilder(); sb.append(terms.get(0)); sb.append(" "); /* TODO */ sb.append(terms.get(1)); sb.append(" "); sb.append("+"); for (int i = 2; i < terms.size(); i++) { sb.append(" "); sb.append(terms.get(i)); sb.append(" "); sb.append("+"); } Term：该类的重点为实现toString方法，将项转化为后缀表达形式 在项的构造方法中对因子factors进行了划分，由于项只可能由数字或数字的乘积构成，使用*划分即可 String[] factorStrs = s.split("\\*"); 同Expr中toString方法，将第0个和第1个因子特判后缀化 0.2 training-2 第二部分通过递归下降的方法对一层括号，只包含“+”“*”运算符的表达式进行处理，输出其后缀表达式 思路梳理 对表达式进行层次化建模（语法树） ...

OSpre——从CO到OS：MIPS补充 1.OS中对CO中CPU的补充 1.访存 在上学期的实验中我们实现了基于MIPS-C指令集的CPU，OS课程中使用基于MIPS32指令集的CPU 在CO中，我们的CPU没有虚拟地址机制，访存指令中的地址均为物理地址，物理地址直接到IM和DM中获取数据 在MIPS32中，汇编指令中的地址为虚拟地址，执行访存操作时，虚拟地址先被送入MMU进行地址翻译、权限检查，检查合法的访存操作，通过MMU得到物理地址 所有的软件（MIPS汇编，C语言编写软件等）均访问虚拟地址 MIPS32的MMU支持基于TLB的页式地址翻译 2.CP0 MIPS32中CP0功能 记录中断及异常信息 特权管理 地址翻译控制 1.中断异常相关 cause寄存器 15-8位：哪些中断等待处理，15-10位来自硬件，9-8位可以由软件写入。中断请求发生，对应位置置为1 6-2位：异常编码 31位：异常指令是否位于延迟槽 EPC寄存器：保存异常发生的指令对应的PC地址，异常处理后返回 BadVAddr寄存器：不合法的访存操作触发异常，该寄存器记录触发异常的访存地址 2.特权管理相关 用户态，内核态 status寄存器 0位(interrupt enable)：全局中断使能位 15-8位：中断使能位，八个中断输入的使能 第4位和第1位：控制处理器的特权模式 UM = 1(usermode),EXL = 0(exception level)运行在用户态 其他均为内核态 (1)代表用户态，(2)代表内核态 2.MIPS调用规范 32个通用寄存器 寄存器编号 助记符 用途 0 zero 值总是为 0 1 at （汇编暂存寄存器）一般由汇编器作为临时寄存器使用。 2-3 v0-v1 用于存放表达式的值或函数的整形、指针类型返回值。 4-7 a0-a3 用于函数传参。其值在函数调用的过程中不会被保存。若函数参数较多，多出来的参数会采用栈进行传递。 8-15 t0-t7 用于存放表达式的值的临时寄存器; 其值在函数调用的过程中不会被保存。 16-23 s0-s7 保存寄存器; 这些寄存器中的值在经过函数调用后不会被改变。 24-25 t8-t9 用于存放表达式的值的临时寄存器; 其值在函数调用的过程中不会被保存。 26-27 k0-k1 仅在内核态下使用。 28 gp 全局指针和内容指针。 29 sp 栈指针。 30 fp或s8 保存寄存器（同 s0-s7）。也可用作帧指针。 31 ra 函数返回地址。 其中加粗的部分，是我们在函数调用中需要保留其值的寄存器。 ...

OSpre——工具介绍 1.vim ​ vim为CLI的文本编辑工具，一些常用的操作如下 vim有Normal模式和Insert模式 启动vim后默认在Normal模式 i进入Insert模式 esc进入Normal模式 在Insert模式下的一些操作 ctrl + p or ctrl + n自动补全 在Normal模式下的一些操作 x删除当前光标所在的一个字符 :wq存盘+退出 :w存盘 :q退出 拷贝\粘贴 v可视化的选择部分文本 dd删除当前行，并把删除的行存在剪贴板里 p粘贴剪贴板 yy拷贝当前行(ddp) 各种插入模式 a在光标后插入（会进入Insert模式） o（小写O）在当前行后插入一个新行 移动光标 方向键移动光标 0移动到行头 $移动到行尾 ^移动到本行第一个不是blank字符的位置 g_移动到本行最后一个不是blank字符的位置 NG移动到第N行 gg到第一行 G到最后一行 搜索 /pattern搜索pattern的字符串，n切换到下一个 *匹配光标所在单词，移动光标到下一个匹配单词 #匹配光标所在单词，移动光标到上一个匹配单词 重复命令 .重复上一次的命令 N<command>重复某个命令N次 Undo/Redo u Undo ctrl + r Redo 2.GCC ​ 使用gcc作为C语言编译器 用法：gcc [选项] 源代码文件 作用：编译源代码文件 默认编译生成文件名为a.out 运行c语言代码 gcc demo.c ./a.out 更改代码内容后需要重新编译 3.make & Makefile make即为“制作”，他是依赖Makefile文件进行构建的指令 Makefile文件的格式 <target> : <dependencies> [tab] <command_1> [tab] <command_2> ... [tab] <command_n> ##意为### 如果要构建target首先要准备好dependencies，接着执行command中的命令 target：构建目标，目标文件、可执行文件 ...