H4wk1ns's blog

前言这篇博客分析一下Ubuntu更换内核的步骤 安装依赖执行如下命令，安装编译内核所需要的依赖组件1sudo apt-get install git fakeroot build-essential ncurses-dev xz-utils libssl-dev bc flex libelf-dev bison 下载源码执行如下类似命令，从相关的网站中下载版本的内核源码并解压1wget https://mirrors.edge.kernel.org/pub/linux/kernel/v5.x/linux-5.17.tar.gz && tar -zxvf linux-5.17.tar.gz 编译设置为了使编译的内核可以在当前Ubuntu系统中完美适配，在需要以当前的内核设置，来编译新内核执行如下命令即可以设置相同的选项1cp /boot/config-$(uname -r) .config && make oldconfig 执行过程中，由于存在新特性或新设定，程序会对此进行询问，默认使用回车选择推荐配置即可 编译内核完成设置后，执行如下命令进行编译即可1 ...

前言 语义分析略难…。 这里简单记录一下语义分析相关的知识，并且完成Programming Assignment V Semantic Analysis 语义分析是编译器的第三个阶段。语义分析器从语法分析器处获得一棵AST，并检查该AST的上下文相关的属性 属性文法 为了确定AST中诸如变量节点类型等问题，则自然的，需要指定该节点的数据类型属性，则必须给节点配备一系列属性。 然后，再利用节点的相关属性，从而在AST上进行一系列的语义动作(诸如类型检查等) Syntax-Directed Definition 语法制导定义(SDD)，即为每个文法符号引入一组属性，并且每个文法的产生式都配备一组与之关联的语义计算规则 而这些属性可以简单分为两类 综合属性(synthesized attribute):即产生式头的符号属性由产生式体的属性定义 继承属性(inherited attribute):即产生式体的符号属性由产生式头和该符号左侧的产生式体的属性定义 基于此，可简单将SDD分为两类 S属性如果一个SDD的每个属性都是综合属性 L属性对于SDD的每个属性 要么是 ...

前言 本篇博客记录语法分析部分，并且完成Programming Assignment III Syntax Analysis/Parsing 语法分析是编译器的第二个阶段。语法分析器从词法分析器获得一个由词法单元组成的串，并验证这个串可以由源语言的文法生成 Context-Free Grammars 一个上下文无关文法由以下几个部分构成 一个终结符号集合。在编译器的例子中，就是词法分析器输出的词法单元集合 一个非终结符集合。每个非终结符表示一个终结符号串的集合 一个产生式集合。其中每个产生式由如下元素组成： 一个称为产生式头或左部的非终结符号 一个箭头\rightarrow 一个称为产生式体或右部的，由终结符号和非终结符号组成的序列 指定一个非终结符号为开始符号 上下文无关文法的表达能力比正则表达式更强——每个可以使用正则表达式描述的构造都可以使用上下文无关文法描述，但反过来不成立。诸如括号嵌套匹配等问题，上下文无关文法可以解决，然而正则表达式无法解决虽然如此，其在处理不同问题时有不同优势。在编译器的例子中，正则表达式适合描述诸如标识符、常量、关键字、空白这样的语言构造的结 ...

前言 这里通过学习StanFord CS143课程，学习编译相关的基础和原理 编译器结构 一般来说，目前的编译器包括如下五部分 Lexical Analysis(词法分析) Syntax Analysis/Parsing(语法分析) Semantic Analysis(语义分析) Optimization(代码优化) Code Generation(代码生成) Lexical Analysis 词法分析是编译器的第一个阶段，其读入源程序的输入字符、将它们组成词素，生成并输出一个词法单元序列，每个词法单元对应于一个词素。 目前实现词法分析通过如下几个步骤 将词法模式转换为正则表达式 将正则表达式转换为NFA 将NFA转换为DFA 实现DFA 正则表达式 通过定义一组基础的运算，则可以递归的定义出正则表达式 运算 定义和表示 Union A + B = \{s \vert s \in A \ or \ s \in B\} Concatenation AB = \{ab \vert a \in A \ and \ b \in B\} Itera ...

前言 这个系列终于到最后一篇博客了。 感慨颇深! L3 虚拟文件系统(vfs)实验背景 在这个实验中，我们在多处理器分时多线程的基础上，实现线程安全的虚拟文件系统(virtual file system, VFS)API，并且在VFS这一抽象层上实现若干不同的文件系统： 在存储设备(sda)上支持完整文件和目录操作的文件系统ultra-simple file system(ufs) 虚拟的procfs，提供一系列只读的、反映操作系统内部状态的文件 虚拟的devfs，将操作系统中的设备抽象为可以访问的文件，并为这些文件提供读写操作 实现完成后，系统中的多个线程就可以通过这些文件系统API，进行读写文件操作——至此离现代操作系统就只有一步之遥：只需要为每个线程附属一个独立的地址空间(通过虚拟存储实现)，线程就变成了熟知的进程，操作系统就完整了。 实验描述 实验总览这个实验在pmm和kmt的基础上，在磁盘设备(驱动程序)的基础上实现持久的文件系统，并且在线程级别支持文件描述符和文件/目录操作API——vfs的API和MiniLabs中使用的系统调用几乎完全一样——在Linux中， ...

前言 本篇博客完成M5的实验 M5 File Recovery(frecov)实验背景快速格式化 大家一定用操作系统提供的“格式化”功能对存储介质进行格式化——通常默认的选项是“快速格式化”；MacOS比较贴心的提供了更多的选项，例如更慢但更安全的选项。 实际上，虽然存储设备会比较大，但是格式化起来仍然非常快——如果把存储设备上的文件系统看做是一个数据结构(例如二叉树)，那么只要破坏数据结构的“根节点”，即root->left = root->right = NULL;，数据结构的其他部分也就永久地丢失了。这样，数据结构就完成了一次完美的“内存泄漏”。当然，因为整个数据结构都被摧毁，你也可以重置内存分配器的状态，这样所有磁盘上的空间就变得可以被分配，磁盘也就“焕然一新”(被格式化)了。 格式化磁盘的数据恢复 当然，快速格式化紧接着带来了一个问题：快速格式化(指针赋值)也意味着可以通过遍历存储设备(内存)的方式，将数据结构找回来。在本次试验中，就尝试恢复格式化后的FAT-32文件系统镜像。 实际上，仅是格式化，我们知道文件系统在实现文件/目录的删除操作时，也仅是 ...