# Notes Notes for lessons I've learned. # CS 110: Computer Architecture I ShanghaiTech University - Spring 2021 ## Intro #### CA 六大思想 1.Abstraction(Layers of Representation/Interpretation) 2.Moore’s Law (Designing through trends) 3.Principle of Locality (Memory Hierarchy) 4.Parallelism 5.Performance Measurement & Improvement 6.Dependability via Redundancy * 其实原版的 **CS61C**在 21 spring 改成了五大思想(逃) ## Numbers ### 整数 * Everything in a computer is a number, in fact only 0 and 1. * Integers are interpreted by adhering to fixed length * Negative numbers are represented with Two’s complement * Overflows can be detected utilizing the carry bit * 整数分为 unsigned 和 signed, 对应原码和补码 * 关于补码的运算和溢出: * ![Nr50nu](https://oss.aaaab3n.moe/uPic/Nr50nu.jpg) * Overflow ERROR: When the result of addition exceeds the range of $$\[-2^{n-1},2^{n-1}-1]$$ * Overflow occurs if and only if two numbers with **the same sign** are added and the result has the opposite sign. * Generally, 负数的二进制值要大于非负数(因为首位二进制为 1) * `Unsigned` 对应 $$2^n-1$$ * A **neat trick** for flipping the sign of a two’s complement number: flip all thebits and add 1. * 2 examples (in 6-bit binary): * ![N9vNwe](https://oss.aaaab3n.moe/uPic/N9vNwe.jpg) * The decoding and encoding system are human-defined, so that it can represent any number as wished. That is, no largest interger represent by n-bit numbers * $$\bar{x} + x + 1 = 0$$ because of `overflow` * **n bit represents $2^n$ numbers in binary** * 2 进制适合计算机, 10进制适合数手指, 16进制表达更方便 * Consider `>>` operations, * for signed int, >> get signed bit; * for neg get -1 (-1 >> 1 = -1) * ref: * [About MSB and Overflow: ](https://stackoverflow.com/questions/29330787/signed-overflow-why-carry-in-and-carry-out-of-msb-should-match) ### IEEE 754 - 计算机数字标准表示 * **Bias**: 偏移, 即在结果加上偏移指, 或者 0b0 代表了偏移值本身. e.g. 0 -> -127, 0xFF = -127 + 0xFF = -127 + 255 = 128 (IEEE 754) * 第一位为符号位S。 接下来八位为指数位E，剩下23位为分数位F (32 位) * $$(-1)^s \times (1+F) \times 2^E$$ * 大小比较： * 首先按照指数排序， 再按照尾数排序 * 64位系统中: 1 位符号位， 11位指数位， 52位小数位 (double) * 当指数位 * Overflow: * 在极大值的情况下会在指数位上溢出 * 在极小值的情况下会在指数位下溢出 * 特殊情况： * 指数位全0： 极小数 * 指数位全1, 小数位全0： Infinity 符号根据符号位确定 * 全0: 0 , 符号位不确定 * $$\infty - \infty , 0-0$$: 可正可负，指数位全1， **小数位不确定** => NaN * ![](https://snz04pap002files.storage.live.com/y4m6TNxePdpVx9OzxurZtXVgs0-3fOLclDH0k7i6GFR3uBJmyk8ExJerz1sM9rEUi2gDGXBNU2NHWYYn7cmpsI04cntU594NFCKadeg1W7veTAX8Nrp8zBbop67NuExwcynOXvvd7VlJ-B1zwI3YedANrzaQK6GW0eWPzGDp22_UNnaiwo4neyy6yF2lyUlivRI?width=1074\&height=354\&cropmode=none) * ![](https://snz04pap002files.storage.live.com/y4m8LUJ7roIO6DfM8Bg74PzkjMI4rDQkW8wQUEOG86Ic1f9Zp3McDQKf7S3H_CwDY-h4dAeEJmNOOTr0QSF8xyLlBBCpB2eq0aawyEuDJ9ELdyJRghZMKfiISI-ozXtr9kkbT1D0rbjuCvGLv5-4ywitiilZbjrblsxFmp3dGvRdm6q2TqhQnoEJZX26KKcVHBk?width=1468\&height=400\&cropmode=none) * 浮点数不精确 * NaN 不可比较 (仅仅在 NaN $$\neq$$ x 时成立) * Smallest Gap: $$2^{-149} = 2^{-23}\*2^{-126}$$ * 运算无交换律 * 最大整数: 0b0 11111110 全1， 因为指数位全1的话会变成 inf * 计算方法: e.g. 53.125 =? 110101.001 =>$$1.10101001 \* 2^5$$ => 127 + 5 = 132 = 10000100 => 0 10000100 10101001 000000.. * 加减法： * ref 1. [IEEE 754 Simulator](https://www.h-schmidt.net/FloatConverter/IEEE754.html) ## C Simple ### Pointers * Dangling references * memory leaks * C 是一个弱类型语言， 也就是说对于每一个类型，结构， 对于其边界没有严格的检查。对于指针也是这样， C将自由和信任交到了程序员手上， 因此会产生很多不安全的内存访问行为。 * 而 Rua st 则添加了诸多限制。 * 函数指针： * char \*foo(args) * `f = &foo` * 能被取地址 * `(*f)("cat", 3)` * 能被调用， 返回 char\* * Tricky: * `int* a[10];` => a is an array of pointers * `int *a, b;` => a is pointer, b is integer ### Memory * 程序一共有四块内存区 * 栈：存放局部变量 * return address, arguments, local variables * Constants * see [编译时你在做什么？有没有空？可以来拯救吗？](https://aaaab3n.moe/technology/2019/11/29/c-cpp-black-magic.html) * 堆：存放动态变量 - difficult to manage * malloc * calloc * free * realloc * * 静态：存放 functions 之外的变量 * Static variables * Global variables * Constants * String Literals * 代码：当程序运行时存储，不可更改 * Machine Instructions * Constants * ![](https://snz04pap002files.storage.live.com/y4ms7978SdKAnRisT2pTi3Dt7K-57msUyxYmihpxd3Op6N3vVU322DnJGUOYX8xrL9gEoZe0CeXa8JK4O1wp3TbenlHKWoIBk1EW_AukWnx-hDhpUcdGxPZ5-mmaqwBGhpx1lV4dsgRKmhXNSuoMKAqnOphlOLlK4T5Yy-Q194wF6J9Nt284s9mLD1bfdaMg6Ek?width=784\&height=858\&cropmode=none) * string: * `a = malloc(sizeof((char))* strlen(b)+1)` * pay attention to **+1s** * `strcpy(a,b)` 不安全， 因为不知道结尾(\0) * `strncpy(a,b, strlen(b)+1)`安全。 if its too short it will not copy the null terminator! * Union * hold different types in **the same location** * 也就是说会存在**内存复写** * size为最大数据结构的大写， 对齐到 4k ， 例如 char 虽然是 1 字节， 但 union 会 size = 4 * Q8 is worth doing Q19 helps understanding * ```c #include #include union a{ char b[6]; char c[9]; } data; int main(){ // char d[7]; union a A = {"abcdef"}; strcpy(A.c, "12345678"); printf("%s", A.b); } ``` ```c #include #include typedef union { unsigned long long num; struct { unsigned short a; unsigned short b; unsigned short c; unsigned short d; } data; } Datatype; int main(){ Datatype y; y.num= 0xABCDDCBADCABAAAA; printf("%d\n", y.data.a); printf("%d\n", y.data.b); printf("%d\n", y.data.c); printf("%d\n", y.data.d); } // result is proved by gcc, clang, msvc on x86 devices [Running] gcc test.c -o test && test 43690 56491 56506 43981 [Done] exited with code=0 in 1.206 seconds >>> 0xABCD 43981 >>> 0xDCBA 56506 >>> 0xDCAB 56491 >>> 0xAAAA 43690 >>> ``` * 由此可见， 结构体中的类型是自上而下的，而小端序是先下后上的。于是产生了 x 反而对应末尾的2字节。 * ```c #include #include typedef union { char d[4]; int e; struct { char a; char b; char c; } data; } Datatype; int main(){ Datatype y; strcpy(y.d, "ABC"); printf("%d\n", y.e); printf("%c\n", y.data.a); printf("%c\n", y.data.b); printf("%c\n", y.data.c); } Result: 4407873 //0x434241 A B C ``` * char\[] 类型或者数组类型也是自上而下的， 因此在内存中从上往下是 'A', 'B', 'C'。 int 按照小端序读是从下往上读，从左往右的拼接数字，所以是 '\0''C''B''A' = 0x00434241 = 4407873(D) * 如果感觉自己被加强了，可以试试 [3(b)](https://robotics.shanghaitech.edu.cn/courses/ca/20s/notes/midterm_sol.pdf) * 你正在往 C语言律师的方向上越走越远 * cppquiz.com ## RISC-V ### Instructions * ![](https://snz04pap002files.storage.live.com/y4mwCiM1SDGRlQ1V0upPdLAAdT0SGq8eQbvbgdNV7RogPurxVjCRvqXCPaoUTJretOunNk8Ty6PlCZR18DdfV_1mi7woJi0WkqK0XVqcwZdCstrBc0UowRJ9Xwo2IMF8vMph-gaUcEXm3B8k1w0VcSYN6AYnVXcLhAXLMBdWy_qzpdM6qs7xJdkxzNk9Tut7SLz?width=1816\&height=534\&cropmode=none) * Techniques: * \*=-1: 取反加一 * 寄存器置零： xor zero * 函数调用 * a0 - a7: arguments * a0, a1: return value * sp: 栈指针 * when jal to functions, a0-a7, t0-t6, ra need to save, since they can be modified during callee * `jr ra`: when some functions is called somewhere, in order to continue running programme, use jr ra to move to ra, and continue programme. 用于返回。 和 `jal`配合使用 * `jal`: jumo and link, 给 `ra`赋值， 这样函数就知道回到哪里了 * `j`: jal x0 offset 不记录返回值 * 伪指令 * ![](https://snz04pap002files.storage.live.com/y4mfcArPm5wbrtiaGxz8iuy9UamZmb45wPwZh9IrUV0iD4f1xZx3jar9u_1Rj64Xh68hYgnQAwjeC31ONDkCGZtvfYJvGS2csyyMCCcdHkPd5LUTfFAvWLPIiOp_lfsDr9sS29iE7_7DH_PS9l37yCp5vpRNFh9dkHq3CFEP9shv1Be1Vo3zMK3Y13EUD05ak4N?width=1920\&height=1440\&cropmode=none) ### Immediates * An I-type instruction can only have 12 bits of immediate * Bits 31:12 get the same value as Bit 11 * RISC-V immediates are "sign extended" * 首位为符号位 ### Little Eddiem * ![](https://snz04pap002files.storage.live.com/y4mT2S6RrFDKQJmTzbD0r-zFNd4ybshNaFhCiNnpCpgDarK_egSY5EirDubpuId2ljjU4s4rSfQ7thLe7LW5FI86KIudWsqymgp_6coO0D4jCGkYnc6cUPBF0DratTKLlZ8UJV2LWBZJgt_QXby0mOCcC65TDrXzgpe1kni14q0dYHvpVDyKzwcXTkF2nRSYnR9?width=2098\&height=1184\&cropmode=none) * 小端序： ![](https://upload.wikimedia.org/wikipedia/commons/thumb/e/ed/Little-Endian.svg/280px-Little-Endian.svg.png) * 自下而上的存储， 前面的在下面。 寄存器从下而上数。 * 0x8f5 为负数(itype 指令只有12位， 因此大于 0x7ff 的都是负数)， 因此扩写成16位(因为寄存器为32位)的补码 * 0xfffff8f5 (两者取反 加一 值相同) ### Types ![](https://snz04pap002files.storage.live.com/y4m6bArYGFBiAHqyJvsp3OGJ_HLK-fgf4EJj5kOFUSGTWKBTkw0aQ6l-rkjdCHTfljQ430peJcBgMHS6i9BcNiWFyAlPFstoe5zNJV2jzYKJyNZH_IeyhxxUiAxyLuTEMgGdDiMYCPJ_Y63azFHjOv9oH_jPIlN9tcu5_b4x1PpZuBBMyXiEqjjdnmft_RCcrMr?width=1466\&height=408\&cropmode=none) * `I type`只能处理12 bit 立即数 * * LI = LUI + ADDI * ![](https://snz04pap002files.storage.live.com/y4muP-145WsnADoJQkCOu408FSE_5yYyr0iryC-6wvNTJ7G3eZ8CthGBhm6IVdGRCuXZZrcKP4mepPgDQnpFnpEzAO8TvrEq6I4toAEjuMv0-tcjy2X7wF_fNKCqq-7togjeBqhZaOn8w6RS8mI_KZqXwKue9dV95mv__AWzFy4vyAt2oSKcT6FttPN-o-gGmhW?width=1770\&height=990\&cropmode=none) * ![](https://snz04pap002files.storage.live.com/y4mUTd2NJ5QIKRlWd0NtMbOYNirRqFBlLUndMQPTIi9_fqaDFlbgM7WiIeSKITRzqE1ecF22d0wQFSDZxhijaq8nfzNr6MRWbQQ_EVMwXt81b1SpQ_glRN6pfgCAdMo0ZQ9nM9_J5urBw7-dHTI7v-3gGKoj591FHQT_EEVcUBZ8H65UMy9wlxqNs3Et6XY-_En?width=1770\&height=1328\&cropmode=none) * **DEADBEEF**: 如图所示，出现了问题。当且仅当32bit的后12bit为负数时，进行addi操作会扩展成补码。例如 `0xEFF`会扩展成`0xFFFFFEFF`。对于前20bit来说， 加上 `0xFFFFF000`无疑等于对第12位取反。 * 解决方法是， 当后三位大于 `0x7FF`的时候，对第12位+1， 或者是对`x10`+1。 因为第12位是对于16进制的剩余类，在这个剩余类中，`0+F=F, F+1=0`, 取反加1为自身。 ## RISC-V Datapath ### Datapath Stage #### Instruction Fetch Send address to the instruction memory （IMEM） and read IMEM at that address. #### Instruction Decode Generate control signals from the instruction bits, generate the immediate, and read registers from the Regfile. #### Execute Perform ALU operations and do branch comparison. #### Memory Read from or write to the data memory （DMEM）. ### Writeback Write back either PC + 4, the result of the ALU operation, or data from memory to the RegFile. ### 不同指令对于不同操作的需求 ![](https://oss.aaaab3n.moe/uPic/klV2Xd.jpg) ### Latency Datapath Stage 需要时间, 下表列出了各个指令对应的 Datapath Stage 以及Total Time 在本表中的延时为: IF:200ps ID: 100ps EX: 200ps MEM: 200ps WB: 100ps ![Clocking](https://oss.aaaab3n.moe/uPic/kvZxTe.jpg) * **critical path**: 电路中最长的 **Delay Path**. 在上表中, 显然 *lw*是 critical path. * 最快: $$\frac {1} {800}$$ picoseconds = $$1.25$$GHz ### All in one ![所有指令都可以根据这张图现推](https://oss.aaaab3n.moe/uPic/123.jpg) 然后根据上表, 把有值的部分画出来就行了 ### Pipeline (管线) ![An Example of Pipeline](https://oss.aaaab3n.moe/uPic/8CEnAS.jpg) * 对单个元件的物理延时无益, 增加整体吞吐率 * 减少电路元件空置,提高复用率 * 在每两个 Control 之间加入 Reg 作为 Cache ### Hizard **Hizard**: prevents starting the next instruction in the next clock cycle (堵马桶) * Structural: A required resource is busy * e.g. ![6kTUGG](https://oss.aaaab3n.moe/uPic/6kTUGG.png) * Solution: Use different memory: **DM** and **IM** * **Duplicate** resources * Data: * Data dependency between instructions * Need to wait for previous instruction to complete its data read/write * e.g. ![kEwv0l](https://oss.aaaab3n.moe/uPic/kEwv0l.jpg) * might save `t0` of wrong value * 先读后写( 在图中以左右分色显示 ) —— 不总是成立 * 当更复杂的情况出现时情况会更糟糕 * Solution1: Stalling (降速) * ![uwnpxI](https://oss.aaaab3n.moe/uPic/uwnpxI.jpg) * Bubble: Do nothing * **Reduce** Performance * Just repeat the second (and subsequent) instructions * And insert a "bubble" (noop) into the pipeline * Solution2: Forwarding / Bypassing (搭桥) * ![SCFW6e](https://oss.aaaab3n.moe/uPic/SCFW6e.png) * 注意在 Time 600 附近的蓝色连线 * Load: * Stall & 交换顺序 * ![k9N2FI](https://oss.aaaab3n.moe/uPic/k9N2FI.jpg) * In RISC-V * Only data hazard which requires a stall are when you use data from a load * And only a single cycle * Control * Flow of execution depends on previous instruction * Killing: ![Killing](https://oss.aaaab3n.moe/uPic/NHPqk5.png) * Every taken branch in simple pipeline costs 2 dead cycles * To improve performance, use “branch prediction (分支预测)” to guess which way branch will go earlier in pipeline * Only flush pipeline if branch prediction was incorrect * 分支预测: ![x4o73r](https://oss.aaaab3n.moe/uPic/x4o73r.jpg) * 如果这个分支之前走过: 计算 `PC + offset` 然后走 * 如果没有, 继续 `PC + 4` * 如果这个分支以前没有见到过: 假设不采用前向分支(forward branches)，采用后向分支(backword branches) * 最终计算时，使用分支结果更新预测变量上的状态 * 减少 Control Hazards 出现的概率 #### Summary: * 流水线通过重叠执行多条指令来提高吞吐量 * 所有流水线阶段具有相同的持续时间 * 选择适合此限制的部分 * Hazards 可能会减少性能 * 加速加速加速 * SuperScalar Processors 将多个执行单元用于额外的指令级并行性 * 性能优势与代码高度相关 * 乱序执行 * CPI = 1 / IPC * IPC yes ## Cache ![Cache Policy](https://oss.aaaab3n.moe/uPic/OxF2cx.jpg) 如果没有缓存: `lw t0 0(t1)` , find `t1 -> 0x12F0` so find `Memory[0x12F0] = 99`, return to `t0` 如果有缓存: `Memory[0x12F0] = 99` 这步会快 我们这么定义: `Memery[Tag] = Data` ## OS ### Boot * 在某个内存位置开始执行指令 * BIOS: 查找一个存储设备并加载第一个扇区（数据块） * 后继者 UEFI : 现代,友好,复杂 * Bootloader: 从磁盘将OS内核加载到内存中的某个位置，然后跳入该位置。 * OS Boot: 初始化服务、驱动程序等 * Init: 启动一个等待输入循环的应用程序 (e.g. Terminal, Desktop ) ### IO **轮询**: * 在到设备的总线上通常有两个寄存器: 控制寄存器(0/1, r/w)和数据寄存器 * 当控制寄存器为 1 时设备可用 * 此时CPU从数据寄存器中读取数据,并复位控制寄存器为0 * 该过程称为轮询(**Polling**), 为了避免IO wait ![pay attention to WaitLoop](https://oss.aaaab3n.moe/uPic/z8sQRj.png) 计算轮询的时间占比: ![SU8NHb](https://oss.aaaab3n.moe/uPic/SU8NHb.png) **Interrupt-driven** 在运行程序时,发现IO就绪,此时中断程序(**Suspend**),将CPU用于IO处理 方法: 插针(**jalr**) **术语** ![TRzAsS](https://oss.aaaab3n.moe/uPic/TRzAsS.png) Interupt - 异步 Exception - try Trap - Except ![QmyYg5](https://oss.aaaab3n.moe/uPic/QmyYg5.png) ![gVEZXq](https://oss.aaaab3n.moe/uPic/gVEZXq.png) 为Pipeline增加了鲁棒性,通过在每一个cache中加入 exception 的方式 ### Precessed * syscall and fork * 通过 sys call 来完成大部分任务和函数,以及资源的调用,这一步由操作系统**代劳** * Supervisor * 访问部分物理内存 * Scheduling * 快速切换上下文, 并为每个程序设置时间,来保证绝大部分程序能分配到差不多的执行用时 * 而快速切换上下文的技术可以快速的转移程序的执行 * Virtual Memory * 虚拟内存空间 通过 操作系统 对 物理内存空间的 映射 ![e0AIsB](https://oss.aaaab3n.moe/uPic/e0AIsB.png) 物理内存为页 (Pages)的集合 页为块(Blocks)的集合 块为一段字节(Word) 所以给每个用户分一个页(或者页表), 页是对内存块的标记 页表保存在MEMORY中 ![GnLL4T](https://oss.aaaab3n.moe/uPic/GnLL4T.jpg) #### 内存管理 * 线性页表 * 1位检查是否页表存在 * PPN: 内存页 * DPN: 磁盘页 * 状态位: 读/写 * 只要活动的用户进程发生更改，操作系统就会设置页面表基本寄存器 * ![RJii47](https://oss.aaaab3n.moe/uPic/RJii47.png) * 错误处理: * 不存在 -> 分配一个新的 * 大小 * ![GVkdkc](https://oss.aaaab3n.moe/uPic/GVkdkc.png) * 分级页表 * ![EByOe0](https://oss.aaaab3n.moe/uPic/EByOe0.png) 虚拟内存便于检查,并且有效率 在页表中有时候会做虚拟地址到物理地址的缓存(**Translation LookasideBuffers** ) ![fuYv5B](https://oss.aaaab3n.moe/uPic/fuYv5B.png) ![DhkaUq](https://oss.aaaab3n.moe/uPic/DhkaUq.png) #### REF * [Risc-V instructions Set](https://1drv.ms/b/s!Au3reWMu7K2ChOZfWdNGg9fNARrDAA?e=QDam4p) # EE 150: Signals and Systems ShanghaiTech University - Spring 2021 {% file src="/files/-MY\_0GAAoIwEXpT9GgRg" %} Summary from UCB {% endfile %} ## Basic concepts ### Signals and Systems * **Signal**: a function of one or more independent variables (e.g., time and spatial variables); typically contains information about the behavior or nature of some physical phenomena * 信号是一系列独立变量 * **System**: responds to a particular signal input by producing another signal(output) * 系统是其一个信号进， 一个信号出 ![A kind of signal](/files/-MYTqI99Eo8gruKK5rPy) ### Transformation * Time reflection: x(t) ←→ x(−t), x\[n] ←→ x\[−n] * Time scaling: x(t) ←→ x(ct) * Time shift: x(t) ←→ x(t − t0), x\[n] ←→ x\[n − n0] * Usually **do shift then scaling** to avoid complex mathematics ### Even and Odd functions Every signal function is $$x(t) = Even(x) + Odd(t)$$ ,then $$x(-t) = Even(-t) + Odd(-t) = Even(t) - Odd(t)$$ $$Even(t) = \frac12 ( x(t) + x(-t) )$$ $$Odd(t) = \frac12 ( x(t) - x(-t) )$$ ### Periodic * Preodic: $$x(t) = x(t+mT)$$ or $$x\[t] = x\[t+mT]$$ * Fundamental period $$T$$: Smallest positive $$T$$ * 如果是合成的 signal, 其 Fundamental Period 是**最小公倍数** * Aperiodic: Non-preodic ### Eular's Formula $$e^{j \omega0 t} = \cos ( \omega0 t ) + j \cdot \sin (\omega\_0 t)$$ * Fundamental period $$T\_0 = 2 \pi / \mid \omega \_0 \mid$$ * $$A \cos (\omega0 t + \phi) = \frac A2 e^{j \phi} e^{j \omega\_0 t} + \frac A2 e^{-j \phi} e^{-j \omega\_0 t}$$ * 只要基础频率 $$\omega\_0$$ 一样， 指数和三角函数可以互相转化 * $$\begin{equation} \mathrm{e}^{-\mathrm{j} \omega t}=\cos (\omega t)-\mathrm{j} \sin (\omega t) \end{equation}$$ * $$\begin{equation} \cos (\omega t)=\frac{1}{2}\left(\mathrm{e}^{\mathrm{j} \omega t}+\mathrm{e}^{-\mathrm{j} \omega t}\right) \end{equation}$$ * $$\begin{equation} \sin (\omega t)=\frac{1}{2 \mathrm{j}}\left(\mathrm{e}^{\mathrm{j} \omega t}-\mathrm{e}^{-\mathrm{j} \omega t}\right) \end{equation}$$ ### Sin $$x(t) = A \cos (\omega \_0 t + \phi )$$ * unit: $$\omega\_0$$ * radians: $$\phi$$ * phase: $$\omega\_0t+\phi$$ ![Fundamantal Frequency， 角频率越大， 振荡越大](/files/-MYU-FwHLlGMB9A4Kyc6) ### Discrete Time Unit Step and Unit Impulse Sequence * $$\delta\[n]$$ * 只有 $$n=0$$有正值 ![](/files/-MYU2muKy-b7wzftzJXV) * $$u\[n]$$ * 只有 $$n \geq 0$$有正值 ![](/files/-MYU2q4iNayA7553bTrz) $$u\[n]$$相当于 $$\delta\[n]$$的积分 ### 常见信号与周期判断 ### 功率与能量 ![](/files/-MYoefiFvkQW4eFuWgDX) ### Other concepts * Energy and Power of Periodic Signals: 积分与积分后的处理 * 谐振: 同一个角频率的集合 * ## Properties of System ### Memory / Memoryless Output only depends on input **at the same time** ### Invertibility and Inverse System Distinct **input** leads to distinct **output** ### **Causality** {% hint style="info" %} **All memoryless are causal** {% endhint %} Output only depends on input **at the same time** or **before** ### **Stability** **Bounded input** gives **Bounded output** ### **T**ime-Invariance A **time-shift** in the input causes a **same time-shift** in the output $$x\[n] \to y\[n]$$ then $$x\[n-n\_0] \to y\[n-n\_0]$$ Example: ![](/files/-MYZz2RX-9hmhluTxAWo) ### Linearity Additivity and Scaling If $$x\[n] \to y\[n]$$ then $$ax\_1\[n] + bx\_2\[n] \to ay\_1\[n] + b y\_2 \[n]$$ {% hint style="info" %} If linear, zero input gives zero output $$x\[ n]=0 \to y\[n] = 2x\[n] = 0$$ {% endhint %} ## Convolution ### Begin We can construct any signal by discrete function $$y\[n] = x\[k]\delta\[n-k]$$, so that $$y\[n]$$can be valued only at $$k$$ and get $$x\[k]$$. By accumulation, the signal can be **piled up**. This is convolution, defined by $$x\[n] =\Sigma \_{k = - \infty} ^ {\infty} x\[k]\delta\[n-k] = x\[n] \* h\[n]$$, which is called **convolution sum**. Example: ![Origin Signal](/files/-MY_49tLDlPK5tMQk-QQ) ![pile up](/files/-MY_4HFDscC2pmJHTI8s) ### Properties of Convolution * Commutative: $$x(t)∗h(t) =h(t)∗x(t)$$ * 交换律 * Bi-linear: $$(ax\_1(t) +bx\_2(t))∗h(t) =a(x\_1∗h) +b(x\_2∗h),x∗(ah\_1+bh\_2) =a(x∗h\_1) +b(x∗h\_2)$$ * Shift: $$x(t−τ)∗h(t) =x(t)∗h(t−τ)$$ * Identity: δ(t) is the identity signal, $$x∗δ=x=δ∗x$$ * Identity is unique: $$i(t) =i(t)∗δ(t) =δ(t)$$ * Associative: $$x\_1∗(x\_2∗x\_3) = (x\_1∗x\_2)∗x\_3$$ * Smooth derivative: $$y(n)' = x(n)'\*h(n) = x(n)\*h(n)'$$ ### Properties of L.T.I System * Memoryless: $$x\[n] \neq 0$$ when $$n = 0$$ * Invertibility: A system is invertible only if an inverse system exists. * Causality: $$h\[n] = 0$$ when $$n < 0$$ * $$y\[n]=\sum\_{k=0}^{\infty} h\[k] \times\[n-k]$$ * $$\begin{equation} y\[n]=\sum\_{k=-\infty}^{n} x\[k] h\[n-k] \end{equation}$$ * Stability: * $$( \sum\_{k=-\infty}^{\infty}|h\[k]|<\infty )$$ * Convolving $$δ(t)$$ with itself * $$( \delta(t) \* \delta(t)) = \delta(t)$$ ### Calculation Sliding window: 1. Reverse the simpler one $$x(t)$$ 2. Record reversed $$x(t)$$ 's jumping points 3. Slide reversed $$x(t)$$, for each $$g(t)$$, is integral of multiplication $$g(t)=\int \frac{d}{d t} x \* h(t) d t=\ldots$$ $$\begin{equation} g(t)=\frac{d}{d t} \int x \* h(t) d t=\ldots \end{equation}$$ ### 逆变换 ![](/files/-MYogUne2CCUeZiDQ_7V) ## Eigen-function of L.T.I ### Eigen-functions * A signal for which the system's output is just a constant (possibly complex) times the input. * **Eigen Basis**: If an input signal can be decomposed to a weighted sum of eigenfunctions (eigen basis), then the output can be easily found. So goal: Getting an **Eigen basis** of an L.T.I system. ### e^{st} as eigenfunction of L.T.I 1. Consider the input to be $$x(t) = e^{st}$$, then the output is $$y(t)=\int h(\tau) e^{s(t-\tau)} d \tau=e^{s t} \int h(\tau) e^{-s \tau} d \tau$$ 2. $$\begin{equation} H(s)=\int h(\tau) e^{-s \tau} d \tau \end{equation}$$ is just a constant, i.e. eigenvalue for function $$e^{st}$$ ### Orthonormal Basis When $$s$$ purely imaginary $$\begin{equation} j k \omega\_{0} \end{equation}$$, $$\begin{equation} e^{j k \omega\_{0} t} \end{equation}$$ is orthonormal and standard among different . * Definition of inner-product of perioidic functions: $$\begin{equation} \=\frac{1}{T\_{0}} \int\_{T\_{0}} x\_{1}(t) x\_{2}^{\*}(t) d t \end{equation}$$ ## Fourier Analysis ### CT & DT * CT: $$e^{j\omega t }$$ * $$\begin{equation} \mathrm{e}^{\mathrm{j} \omega \mathrm{t}} \longrightarrow \mathrm{H}(\mathrm{j} \omega) \mathrm{e}^{\mathrm{j} \omega \mathrm{t}} \end{equation}$$ * 纯虚数 * DT: $$e^{j \omega n }$$ * $$\begin{equation} \mathrm{e}^{j \omega n} \rightarrow H\left(\mathrm{e}^{j \omega}\right) \mathrm{e}^{j \omega n} \end{equation}$$ ### Periodic signals & Fourier Series Expansion $$x(t)$$ may be expressed as a Fourier series: $$\begin{equation} x(t)=\sum\_{k=-\infty}^{\infty} a\_{k} \cdot e^{j k \omega\_{0} t} \end{equation}$$, $$\begin{equation} x(t) \leftarrow{ }^{F . S .} \rightarrow a\_{k} \end{equation}$$ sum of sinusoids whose frequencies are multiple of ω0, the “fundamental frequency”. Where $$a\_k$$ can be obtained by $$\begin{equation} a\_{k}=\frac{1}{T\_{0}} \int\_{T\_{0}} x(\tau) e^{-j k \omega\_{0} \tau} d \tau \end{equation}$$ * Case 0 is often special! * $$a\_0$$ controls a constant And, $$ \begin{aligned} x(t) &=\sum\_{k=-\infty}^{\infty} a\_{k} e^{j k \omega\_{0} t} \ &=\sum\_{k=-\infty}^{\infty}\left(a\_{k} \cos \left(k \omega\_{0} t\right)+j a\_{k} \sin \left(k \omega\_{0} t\right)\right) \ &=a\_{0}+\sum\_{k>0}\left(\left(a\_{k}+a\_{-k}\right) \cos \left(k \omega\_{0} t\right)+j\left(a\_{k}-a\_{-k}\right) \sin \left(k \omega\_{0} t\right)\right) \end{aligned} $$ #### Odd / Even ![奇偶特性](/files/-MYeKhUViQBZ-BXS3APT) #### Approximation ![](/files/-MYeLE5KRbRPJsOXz6TV) #### Linearity $$ z(t)=\alpha x(t)+\beta y(t) \underset{\longleftrightarrow}{\longleftarrow S}{\longrightarrow} \alpha a\_{k}+\beta b\_{k} $$ #### Time-shift $$ x\left(t-t\_{0}\right) \stackrel{F S}{\longleftrightarrow} e^{-j k \omega\_{0} t\_{0}} a\_{k} $$ #### Time-reverse $$ x(-t) \stackrel{F S}{\longleftarrow} a\_{-k} $$ #### Time-scaling $$ x(\alpha t)=\sum\_{k=-\infty}^{\infty} a\_{k} e^{j k\left(\alpha \omega\_{0}\right) t} $$ #### Multiplication $$ x(t) y(t) \underset{\longleftrightarrow}{\longleftrightarrow S}, h\_{k}=\sum\_{l=-\infty}^{\infty} a\_{l} b\_{k-1} $$ which is **Convolution** #### conjugation & conjugate symmetry ![](/files/-MYjnXuW3wVdg8eCt8xg) #### 7 $$ \frac{d x(t)}{d t} \longleftrightarrow F S, j k \omega\_{0} a\_{k} $$ $$ \int\_{-\infty}^{t} x(\tau) d \tau \underset{\longleftrightarrow}{\text { FS }}, \frac{a\_{k}}{j k \omega\_{0}} $$ #### Parseval's identity $$ \frac{1}{T} \int\_{T}|x(t)|^{2} d t=\sum\_{k=-\infty}^{\infty}\left|a\_{k}\right|^{2} $$ Proof: $$ \begin{aligned} \frac{1}{T} \int\_{T}|x(t)|^{2} d t &=\frac{1}{T} \int\_{T} \sum\_{k\_{1}, k\_{2}} a\_{k\_{1}} a\_{k\_{2}}^{*} e^{j\left(k\_{1}-k\_{2}\right) \omega\_{0} t} d t \ &=\sum\_{k\_{1}, k\_{2}} a\_{k\_{1}} a\_{k\_{2}}^{*} \delta\left\[k\_{1}-k\_{2}\right] \ &=\sum\_{k}\left|a\_{k}\right|^{2} \end{aligned} $$ ## Continuous-Time Fourier Transform (CTFT) ### 变换与逆变换 Fourier series: $$\begin{equation} x(t)=\sum\_{k=-\infty}^{\infty} a\_{k} \mathrm{e}^{j k \omega\_{0} t} \end{equation}$$ Inverse fourier transform: $$x(t)=\frac{1}{2 \pi} \int\_{\infty}^{\infty} X(j \omega) \mathrm{e}^{j \omega t} \mathrm{\~d} \omega$$ ### Fourier Transform Pair Fourier Transform: $$\begin{equation} \mathcal{F}: X(j \omega)=\int\_{-\infty}^{\infty} x(t) e^{-j \omega t} d t \end{equation}$$ * For periodic signals, $$\begin{equation} X(j \omega)=2 \pi \sum\_{-\infty}^{\infty} a\_{k} \delta\left(\omega-k \omega\_{0}\right) \end{equation}$$, i.e. the Fourier Series * $$\begin{equation} X(j \omega) \end{equation}$$is called the "Spectrum" of $$x(t)$$ Inverse F.T. $$\begin{equation} \mathcal{F}^{-1}: x(t)=\frac{1}{2 \pi} \int\_{-\infty}^{\infty} X(j \omega) e^{j \omega t} d \omega \end{equation}$$ ### Dual Porperty $$\begin{equation} \mathcal{F}(\mathcal{F}(x(t)))=2 \pi \cdot x(-t) \end{equation}$$ Means that when we put the $$\begin{equation} X(j \omega) \end{equation}$$ in **time** domain, it will produce $$2\pi$$times $$x(-t)$$ waveform in **freq** domain ### Properties ![](/files/-MYjlT8Z0nqLVQiOtJWx) ![](/files/-MYjpd8BxI0HvzK9HkEZ) ### Normal CT Fourier Pairs ![](/files/-MYjlbCCghmS1h27c3IS) ![](/files/-MZSVf6BQJTjFBfO2J2p) ## REF * # CS 131: Programming Languages and Compilers ShanghaiTech University - Spring 2021 ## Introduction ![Compiler](/files/-MZlzscUjQLJTLK8_9W0) ### Definition A **Compiler** is "A program that takes a source-code program and translates it into an equivalent program in target language" ### String A **String** is a sequence of characters. * Alphabet: A finite set of symbols （ASCII characters） * String has words and sentences * $$st$$ is the concatenation of $$s$$and $$t$$ * $$s \epsilon = \epsilon s = s$$ * $$\epsilon$$is the empty string * $$s^0 = \epsilon$$ * $$\mid s \mid$$ is the length of s * Suppose s is banana * **Prefix:**前缀 * ban banana * **Suffix:**后缀 * banana, ana * **Substring:**子字符串 * **Subsequence**:子字符 * bnan, nn A **Language** is a set of Strings over a fixed **Alphabet** $$\Sigma$$, constructed using a specific Grammar. * e.g. $${\varepsilon, 0,01,011,0111, \ldots}$$ * Not all Strings of chars in the Alphabet is in the certain Language, only those who satisfy the Grammar rules. * Alphabet $$={0,1}$$ and using Grammar rule $$\mathrm{RE}=01^{\*}$$ , we can specify the above example Language, while $$01$$ isn't. Below is **Operations** and **Examples**. ![Operations of Languages](/files/-MZmlFc0EYCac_0nCzrW)
Example of Laguage Operations
A **Grammar** $$G$$ is the description of method （*rules*） of how to construct a certain Language over a certain Alphabet * Type 0: Turing Machine Recursive Enumerable Gramma * Type 1: Context-sensitive Grammar （CSG） * Type 2: Context-free Grammar (CFG,上下文无关文法）， *mostly recursive* * Type 3: Right-linear Grammar Regular Expressions (RE,正则表达式）， *non-recursive* {% hint style="info" %} Expressiveness: Type 0 > Type 1 > Type 2 > Type 3 {% endhint %} ### Phases ![](/files/-MZzDtySitutcAp8QaOk) ## Lexical Analyzer （词法分析器） Reads the source program character by character and returns the **tokens** of the source program * 分析并把 identifiers 放入符号表 * 利用正则表达式来分析 tokens * 利用有限自动机来分析 Token 以完成词法分析 * 词法分析器 = 读入（scanning） + 词法分析（lexical analysis） ![Lexical Analyzer](/files/-MZmeSjHtfQ1-ogSHzxx) ### Token Describes a pattern of characters having some meaning in the source program (such as identifiers, operators, keywords, numbers, delimiters and so on) * e.g., identifiers, operators, numbers A **Lexeme （词素）** is an instance of a Token, along with its unique attributes. * e.g. `17` * INT * Token.value = 17 ![Process of determing a Token 通常使用双 buffers 来避免 buffer 区太小的问题](/files/-MZmfxNa9GrrRaFbzRSZ) ### Regular Expression （正则表达式） 我们利用**正则表达式**来 描述 **Tokens** 匹配 **Tokens** * 每个**正则表达式** $$r$$ 描述一个语言 $$L(r)$$ * $$r$$被叫做 **regular set** * **正则表达式**是左结合的，从左向右匹配的 * **正则表达式**是一个 **Type-3 Grammar Rule** #### **Properties** ![Properties](/files/-MZmof_B8q_1S9MeftXx) ![Extended Properties](/files/-MZmojydvefc6fY_VzFT) * e.g. * Integers: * Digit = \[0-9]\* * Integer = Digit Digit\* * Identifier * letter = \[a-zA-Z] * identifier = letter （letter + digit）\* * Whitespace * WS = ('\n' + '\t' + ' ')+ * Examples * Even Binary number * 1\[0+1]\*0 | 0 ### Finite Automata （有限自动机） #### Transition Diagram ![Transition Disgram Examples](/files/-MZpxrkV0bNGzQ5kYj-e) 当一个 Token 被识别： * 如果是关键字，那么会返回 **Token of the keyword** * 如果是符号表里的 ID，那么返回 **entry of symbol table** * 如果符号表没有这个ID，那么加入ID并返回新的 **entry of symbol table** ```c switch (state){ case 0: c = nextchar(); if (c == [something]) state = [state], lexeme_beginning ++; else if (c == [something]) [do something] else if (c == [final state]) // terminal retract(1); //forward lexical_value = install_num(); // install something return (NUM); else state = fail(); ``` #### Finite automata A **recognizer** for a language is a program that takes a string x, and answers “yes” if x is a sentence of that language, and “no” otherwise. We call the recognizer of the tokens as a **finite automaton**. **Example** ![Regular expression: (a+b)\*abb](/files/-MZq0pX6wcH7PWX7wenr) * **Start Arrow** * **State** * **Transition Edge** * **Accepting State**:同心圆，接受并结束，状态3 * **Death State:错误**状态，未定义的 transition 指向该状态 * Transition table: | state | a | b | | ----- | ----- | --- | | 0 | {0,1} | {0} | | 1 | -- | {2} | | 2 | -- | {3} | {% hint style="info" %} 注意 empty string 可以被某些自动机接收 {% endhint %} ### NFA Non-Deterministic Finite Automata （NFAs） **easily** represent regular expression, but are **less precise.** **Accept s:** an Accepting State that spells out **s**. An NFA is a mathematical model that consists of: * S, a **finite** set of **states** * $$\Sigma$$, the symbols of the **input alphabet** * *move*, a **transition function** * move(state, symbol) $$\to$$ sets of states * A state $$s\_0 \in S$$, the **start state** * $$F \subseteq S$$, a set of **final** or **accepting states** * $$\epsilon$$**move: ε- transitions** are allowed in NFAs. In other words, we can move from one state to another one without consuming any symbol {% hint style="info" %} The $$\epsilon$$-Closure of $$S = S \cup {$$ All States that can go to without consuming any input $$}$$ {% endhint %} ### DFA Deterministic Finite Automata （DFAs） require **more complexity** to represent regular expressions but offer **more precision**. **Does not allow** $$\epsilon$$**move,** for every $$s \in S$$, there is ONLY ONE decision for every input *Symbol.* **Accept s:** an Accepting State that spells out **s** *and **ONLY and ONLY ONE** path*. {% hint style="info" %} No $$\epsilon$$-closure !!! {% endhint %} ### Implementation of Lexers One Token, A *Recognizer. There are 4 ways. (r stands for RE)* 1. $$r \to NFA \to Recognizer$$ 2. $$r \to NFA \to DFA \to Recognizer$$ 3. $$r \to DFA \to Recognizer$$ 4. $$r \rightsquigarrow DFA \to Minimized \~ DFA \to Recognizer$$ ### RE to NFA Algorithm is called **Thompson's Construction**. ![](/files/-MZqLle_HFS3AzK_CIg4) There are some requirements on such construction: * $$N(s)$$and $$N(t)$$CANNOT have any intersections * REMEMBER to assign unique names to all states Properties of the resulting NFA: * Exactly 1 Start State & 1 Accepting State * $$#$$ of States in NFA $$\leq 2 \times$$(# of Symbols + # of Operators) in $$r$$ * States do not have multiple outgoing edges with the same input symbol * States have at most 2 outgoing $$\epsilon$$ edges ### RE to DFA **\[Step 1]**: We make Augmented RE: concatenate with symbol # (meaning "finish"). * e.g. (a+b)\*a# * Ensures at least one operator in the RE **\[Step 2]:** Build syntax tree for this Augmented RE:
* $$\epsilon$$, # and $$a \in \Sigma$$ all are at leaves * All other operators are inner nodes * Non-$$\epsilon$$ leaves get its position number, increasing from left $$\to$$ right **\[Step 3]:** Compute `nullable()`, `firstpos()` & `lastpos()` for ALL nodes. 1. `firstpos(n)`: Function returning the set of positions where the *first* Symbol can be at, in the *sub-RE* rooted at `n` 2. `lastpos(n)`: Function returning the set of Positions where the *last* Symbol can be at, in the sub-RE rooted at `n` 3. `nullable(n)`: Function judging whether the *sub-RE* rooted at `n` can generate $$\epsilon$$ ![](/files/-MZqOknizrDpl08vfeyI) **\[Step 4]:** Compute `followpos()` for Leaf positions `followpos(i)`: Function returning the set of positions *which can follow* position i in the generated String Conduct a *Post-order* *Depth First Traversal* on the syntax tree, and do the following oprations when leaving $$\cdot$$ / \* nodes: * $$c{1} \cdot c{2}:$$ For all $$i \in$$ `lastpos(c1)` , `followpos(i)`= `followpo(i)` $$\cup$$ `firstpos(c2)` * $$c^{\*}:$$ For all $$i \in$$ `lastpos(c)`, `followpos(i)`$$=$$ `followpos(i)` $$\cup$$ `firstpos(c)` **\[Step 5]:** Construct the DFA. ```c void construct() { S0=firstpos(root); DStates= {(S0, unmarked)}; while (DStates has an unmarked State U) { Mark State U; for (each possible input char c) { V= {}; for (each position p in U whose symbol is c) V=UnionofVandfollowpos(p); if (V is not empty) { if (V is not in DStates) Include V in DStates, unmarked; Add the Transition U--c->V; } } } } ``` * A State $$S$$in resulting DFA is an Accepting State iff # node $$\in S$$ * Start State of the resulting DFA is $$S\_0$$ #### Calculate \epsilon-Closure ```c set epsClosure(set S) { for (each State s in S) Push s onto stack; closure = S; while (stack is not empty) { Pop State u; for (each State v that u->v is an epsilon Transition) { if (v is not in closure) { Include v in closure; Push v onto stack; } } } return closure; } ``` #### Implement NFA as Recognizer ```c bool recognizer() { S=epsClosure(s0); while ((c=getchar()) !=EOF) S=epsClosure(move(S, c)); if (S and F has intersections) return ACCEPT; return REJECT; } ``` {% hint style="info" %} Performance of NFA-type Recognizers: Space $$O(|r|)$$; Time $$O(|r| \times |s|)$$ {% endhint %} #### Implement DFA as Recognizer ```c bool recognizer() { s=s_0; while ((c=getchar()) !=EOF) s=move(s, c); if (s is in F) return ACCEPT; return REJECT; } ``` {% hint style="info" %} Performance of DFA-type Recognizers: Space $$O(|2^{|r|})$$; Time $$O(|s|)$$ {% endhint %} #### Convert NFA to DFA Algorithm is called **Subset Construction(子集构造法)**, since we make subset of States in original NFA into a single State in resulting DFA ```c void subsetConstruction() { S0=epsClosure({s0}); DStates= {(S0, unmarked)}; while (DStates has any unmarked State U) { MarkState U; for (each possible inputchar c) { V=epsClosure(move(U, c)); if (V is not empty) { if (V is not in DStates) Include V in DStates, unmarked; Add the Transition U--c->V; } } } } ``` * A State $$S$$ in resulting DFA is an Accepting State iff $$\exists s \in S, s$$ is an Accepting State in original NFA * Start State of the resulting DFA is $$S\_0$$ ### Minimize DFA ```c void minimize() { PI = {G_A, G_n}; do { for (every group G in PI){ for (every pair of States (s,t) in G){ if (for every possible input char c, transition s--c -> and t--c-> go to states in the same group) s,t are in the same subgroup; else s,t should split into different subgroups; } Split G according to the above information; } }while (PI changed in this iteration) Every Group in PI is a state in the minimal DFA; } ``` * A State S in the minimal DFA is an Accepting State iff $$\exists s \in S$$, s is an Accepting State in original DFA * Start State of the minimal DFA is the one containing original Starting State ### Other Issues for Lexers #### Look ahead #### Comment Skip #### Symbol Table ## Syntax Analyzer （句法分析） 如果说词法分析这一步提供了可供计算机识别的**词**，那么句法分析是为了理解句子结构。 通常这一步会生成 **parse tree**, **parse tree** 用以描述句法结构。 ### Difference with Lexical Analyzer * The syntax analyzer deals with **recursive** constructs of the language * Both do similar things; But the lexical analyzer deals with simple **non-recursive** constructs of the language. * The lexical analyzer recognizes the smallest meaningful units （**tokens**） in a source program. * The syntax analyzer works on the smallest meaningful units （**tokens**） in a source program to recognize meaningful structures （**sentences**） in our programming language. ### Parse Tree Abstraction A **Parse Tree / Syntax Tree (语法树)** is a graphical representation of the structure of a program, where leaf nodes are Tokens. ### CFG （上下文无关文法） A **Context-free Grammar (CFG)** is a **Type-2** Grammar rule, which serves the construction of a Parse Tree from a streamof Tokens. We use a set of Production Rules to characterize a CFG ![](/files/-MZvRarzF4mg2I3Uq7KL) A **Terminal (终结符号)** is a Token; A **Non-terminal (非终结符号)** is a syntactic variable. * The Start Symbol is the first one of Non-terminals; Usually represents the whole program * A Sentence is a string of Terminals such that Start Symbol $$S \Rightarrow{ }^{+} s$$ A **Production Rule (生成规则)** is a law of production, from a Non-terminal to a sequence of Terminals & Non-terminals. * e.g. $$A \rightarrow \alpha A \mid \beta$$, where $$A$$ is a Non-terminal and $$\alpha, \beta$$ are Terminals * May be *recursive* * The procedure of applying these rules to get a sentence of Terminals is called **Sentential Form** / **Derivation** {% hint style="info" %} $$|$$ Context-free Languages $$|>|$$ Regular Languages $$|$$, e.g. $${(^{i})^{i}: i \geq 0 }$$. {% endhint %} ### Derivation Directions（派生文法）\&Ambiguity（二义性） **Left-most Derivation** **(左递归)**$$\left(\Rightarrow\_{l m}\right)$$ means to replace the leftmost Non-terminal at each step. * If $$\beta A \gamma \Rightarrow \operatorname{lm} \beta \delta \gamma$$, then NO Non-terminals in $$\mathcal{\beta}$$ * Corresponds to *Top Down Parsing* **Right-most Derivation** $$(\Rightarrow r m)$$means Replace the rightmost Non-terminal at each step. * If $$\beta A \gamma \Rightarrow\_{r m} \beta \delta \gamma$$, then NO Non-terminals in $$\gamma$$ * Corresponds to *Bottom Up Parsing*, in reversed manner ![](/files/-MZzG4b-kgANk-Vstyqs) A CFG is **Ambiguous** when it produces more than one Parse Tree for the same sentence. Must remove Ambiguity for apractical CFG, by: * Enforce *Precedence (优先级)* and *Associativity (结合律)* * e.g. $$\* > +$$ , then $$+$$ gets expanded first * Grammar Rewritten ![](/files/-MZzFc923KMiyxDum2ST) ### Top-Down Parsers Construction of the parse tree starts at the root, and proceeds towards the leaves. * Recursive Predictive Parsing * Non-Recursive Predictive Parsing （**LL Parsing**）. （**L**-left to right; **L**-leftmost derivation） * 语法构架能力弱 #### Implement 1. Eliminate Left Recursion $$\to$$ Recursive-descent Parsing 2. Eliminate Left Recursion $$\to$$ Left Factoring $$\to$$Recursive Predictive Parsing 3. Eliminate Left Recursion $$\to$$Left Factoring $$\to$$Construct Parsing Table $$\to$$Non-recursive Predictive Parsing #### Left Recursion Elimination (消除左递归) $$A \Rightarrow^{+} A\_{\alpha}$$: Left Recursion * Top Down Parsing **CANNOT** handle Left-recursive Grammars * Can be eliminated by rewriting For *Immediate* Left Recursions (Left Recursion that may appear in a single step), eliminate by:
立即左递归的消除
```c /* Non-terminals arranged in order: A1, A2, ... An. */ void eliminate() { for (i from 1 to n) { for (j from 1 to i-1) Replace Aj with its products in every Prodcution Rule Ai->Aj ...; Eliminate Immediate Left Recursions Ai->Ai ...; } } ``` ![左递归的消除](/files/-MZzH1KO5UIk5U0j1bRY) #### Implementing Recursive-descent Parsing ```c /* Example: * E -> T | T + E* T -> int | int * T | ( E ) */ bool term(TOKENtok) { return*ptr++==tok; } bool E1() { returnT(); } bool E2() { returnT() &&term(PLUS) &&E(); } bool E() { TOKEN*save=ptr; return (ptr=save, E1()) || (ptr=save, E2()); } bool T1() { returnterm(INT); } bool T2() { returnterm(INT) &&term(TIMES) &&T(); } bool T3() { returnterm (OPEN) &&E() &&term(CLOSE); } bool T() { TOKEN*save=ptr; return (ptr=save, T1()) || (ptr=save, T2()) || (ptr=save, T3()); } ``` #### Left Factoring: Produce LL(1) Grammar LL(1) means Only 1 Token Look-ahead ensures which Pruduction Rule to expand now. To convert LL(1) to a CFG, for each Non-terminal :
{% hint style="info" %} || LL(1) || < || CFG ||, so not all Grammar can be convert to LL(1) * Such Grammar will have an entry with multiple Production Rules to use in the Parsing Table, thusWill be inappropriate for Predictive Parsing {% endhint %} #### Implementing Recursive Predictive Parsing {% hint style="info" %} This part stongly suggest to see for better understanding. {% endhint %} ![](/files/-MZzIAL51Xb-Tx5XjVz8) #### Parsing Table Construction {% hint style="info" %} This part stongly suggest to see for better understanding. {% endhint %} #### Implementing LL(1) Parsing {% hint style="info" %} This part stongly suggest to see for better understanding. {% endhint %} ### Bottom-Up Parsers Construction of the parse tree starts at the leaves, and proceeds towards the root. * Bottom-up parsing is also known as **shift-reduce parsing** * **LR Parsing** – much general form of shift-reduce parsing: **LR**, **SLR**, **LALR** (**L**-left to right; **R**-rightmost derivation) {% hint style="info" %} This part stongly suggest to see for better understanding. {% endhint %} ## IR ## Thanks * \[Guanzhou HU's Notes]\() * TAs: 季杨彪, 杨易为, 尤存翰