H4wk1ns's blog

前言 语义分析略难…。 这里简单记录一下语义分析相关的知识，并且完成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文件系统镜像。 实际上，仅是格式化，我们知道文件系统在实现文件/目录的删除操作时，也仅是 ...

前言 终于结束了痛苦的L2，虽然感觉确实学到了很多东西。这篇博客完成M4实验 M4 C-Real-Eval-Print-Loop(crepl)实验背景 很多编程语言都提供了交互式的read-eval-print-loop(REPL)，更俗一点的名字就是”交互的shell”。例如在命令行中输入python，就可以和Python shell交互了。现代程序设计语言都提供类似的措施，即便是非解释型的程序设计语言，也提供了类似的措施，例如Scala REPL、go-eval等 实际上，C这种编译型的语言，同样可以实现”交互式”的shell——即支持即使定义函数，并且可以计算C表达式的数值。如果输入一段代码，例如strlen("Hello, World")，这段代码会经历gcc编译、动态加载、调用执行，并最终讲代码执行得到的数值11，打印到屏幕上 在本次实验中，将实现一个非常简单的C交互式shell 实验描述 crepl - 逐行从stdin中输入，根据内容进行处理： 如果输入的一行定义了一个函数，则把函数编译并加载到进程的地址空间中 如果输入是一个表达式，则把 ...