目录

  • 1 Chapter 1 Introduction
    • 1.1 1.0 Course Contents
    • 1.2 1.1 Basic Conception
      • 1.2.1 Lecture 1
      • 1.2.2 Lecture 2
    • 1.3 1.2 Compiler Structure
      • 1.3.1 Lecture 1
      • 1.3.2 Lecture 2
      • 1.3.3 Lecture 3
    • 1.4 1.3 The Technique of Compiler Developing
  • 2 Chapter 2 Conspectus of Formal Language
    • 2.1 2.1 Alphabets and Strings
      • 2.1.1 Lecture 1
      • 2.1.2 Lecture 2
    • 2.2 2.2 Grammars and its Categories
      • 2.2.1 Lecture 1
      • 2.2.2 Lecture 2
    • 2.3 2.3 Languages and Parse Tree
      • 2.3.1 Lecture 1
      • 2.3.2 Lecture 2
    • 2.4 2.4 Notes of Formal Language
    • 2.5 2.5 Basic Parsing Techniques
      • 2.5.1 Lecture 1
      • 2.5.2 Lecture 2
  • 3 Chapter 3 Finite Automata
    • 3.1 3.1 Formal Definition of FA
      • 3.1.1 Lecture 1
      • 3.1.2 Lecture 2
    • 3.2 3.2 Transition from NDFA to DFA
      • 3.2.1 Lecture 1
      • 3.2.2 Lecture 2
      • 3.2.3 Lecture 3
    • 3.3 3.3 RG and FA
    • 3.4 3.4 Regular Expression & Regular Set
      • 3.4.1 Lecture 1
      • 3.4.2 Lecture 2
  • 4 Chapter 4 Scanner(Lexical Analyzer)
    • 4.1 4.1 Lexical Analyzer and Tokens
      • 4.1.1 Lecture 1
      • 4.1.2 Lecture 2
    • 4.2 4.2 Step for developing a lexical analyzer
    • 4.3 4.3  Dealing with Identifier
    • 4.4 4.4  Using Regular Expressions
    • 4.5 4.5 Using Flex
      • 4.5.1 Lecture 1
      • 4.5.2 Lecture 2
  • 5 Chapter 5 Top-Down Parsing
    • 5.1 5.0 Push Down Automata (PDA, Added)
      • 5.1.1 Lecture 1
      • 5.1.2 Lecture 2
      • 5.1.3 Lecture 3
    • 5.2 5.1 Elimination Left-Recursion
    • 5.3 5.2 LL(k) Grammar
      • 5.3.1 Lecture 1
      • 5.3.2 Lecture 2
    • 5.4 5.3 Deterministic LL(1) Analyzer Construction
    • 5.5 5.4 Recursive-descent (Non-backtracking) parsing
    • 5.6 5.5 复习与结课
      • 5.6.1 Lecture1 结课感言
      • 5.6.2 Lecture 2 关于复习
      • 5.6.3 Lecture 3 习题讲解
  • 6 Chapter 6 bottom-up Parsing and precedence analyzer
    • 6.1 6.1 Bottom-Up Parsing
    • 6.2 6.2 Phrase, Simple Phrase and Handle
    • 6.3 6.3 A Shift-Reduce Parser
    • 6.4 6.4 Some Relations on Grammar
    • 6.5 6.5 Simple Precedence Parsing
    • 6.6 6.6 Operator-Precedence Parsing
      • 6.6.1 Lecture 1
      • 6.6.2 Lecture 2
      • 6.6.3 Lecture 3
    • 6.7 6.7 Precedence Functions and Construction
  • 7 Chapter 7  LR Parsing
    • 7.1 7.1 LR Parsers
      • 7.1.1 Lecture 1
      • 7.1.2 Lecture 2
    • 7.2 7.2 Building a LR(0) parse table
      • 7.2.1 Lecture 1
      • 7.2.2 Lecture 2
    • 7.3 7.3 SLR Parse Table Construction
    • 7.4 7.4 Constructing Canonical LR(1) Parsing Tables
    • 7.5 7.5 LALR Parsing Tables Construction
    • 7.6 7.6 Using Ambiguous Grammars
    • 7.7 7.7 Yacc/Bison Overview
  • 8 Chapter 8 Syntax-Directed Translation
    • 8.1 8.1 Syntax-Directed Translation
      • 8.1.1 Lecture1
      • 8.1.2 Lecture 2
      • 8.1.3 Lecture 3
    • 8.2 8.2 Abstract Syntax Tree
    • 8.3 8.3 Intermediate Representation
      • 8.3.1 Lecture 1
      • 8.3.2 Lecture 2
  • 9 Chapter 9 Run-Time Environment
    • 9.1 9.1 Data Area & Attribute
    • 9.2 Section 9.2~9.4 & Section 9.8~9.9
    • 9.3 9.5 Parameter Passing
    • 9.4 9.6 Stack Allocation
    • 9.5 9.7 Heap allocation
  • 10 Chapter 10 Symbol Tables
    • 10.1 10.1 A symbol Table Class
    • 10.2 10.2 Basic Implementation Techniques
    • 10.3 10.3 Block-structured Symbol Table
    • 10.4 10.4 Implicit Declaration
    • 10.5 10.5 Overloading
  • 11 Chapter 11 Code Optimization
    • 11.1 11.1 Control Flow Graph
    • 11.2 11.2 Redundancies
    • 11.3 11.3 Loop Optimizations
    • 11.4 11.4 Instruction Dispatch
      • 11.4.1 Lecture 1
      • 11.4.2 Lecture 2
  • 12 Chapter 12 Code Generation
    • 12.1 12.1 Code generation issues
    • 12.2 12.2 Simple Stack Machine
    • 12.3 12.3 Register Machine
    • 12.4 12.4 A Simple Code Generator
  • 13 13 Extended Reading扩展阅读1 斯坦福大学公开课
    • 13.1 Lecture 1
    • 13.2 Lecture 2
    • 13.3 Lecture 3
    • 13.4 Lecture 4
    • 13.5 Lecture 5
    • 13.6 Lecture 6
    • 13.7 Lecture 7
    • 13.8 Lecture 8
    • 13.9 Lecture 9
    • 13.10 Lecture 10
    • 13.11 Lecture 11
    • 13.12 More sources
  • 14 14 Extended Reading 2 扩展阅读2 illinois.edu lectures
    • 14.1 Lecture 1 Overview
    • 14.2 Lecture 2 Strings, Languages, DFAs
    • 14.3 Lecture 3 More on DFAs
    • 14.4 Lecture 4 Regular Expressions and Product Construction
    • 14.5 Lecture 5 Nondeterministic Automata
    • 14.6 Lecture 6 Closure properties
    • 14.7 Lecture 7 NFAs are equivalent to DFAs
    • 14.8 Lecture 8 From DFAs/NFAs to Regular Expressions
    • 14.9 Lecture 9 Proving non-regularity
    • 14.10 Lecture 10 DFA minimization
    • 14.11 Lecture 11 Context-free grammars
    • 14.12 Lecture 12 Cleaning up CFGs and Chomsky Normal form
    • 14.13 Lecture 13 Even More on Context-Free Grammars
    • 14.14 Lecture 14 Repetition in context free languages
    • 14.15 Lecture 15 CYK Parsing Algorithm
    • 14.16 Lecture 16 Recursive automatas
    • 14.17 Lecture 17 Computability and Turing Machines
    • 14.18 Lecture 18 More on Turing Machines
    • 14.19 Lecture 19 Encoding problems and decidability
    • 14.20 Lecture 20 More decidable problems, and simulating TM and “real” computers
    • 14.21 Lecture 21 Undecidability, halting and diagonalization
    • 14.22 Lecture 22 Reductions
    • 14.23 Lecture 23 Rice Theorem and Turing machine behavior properties
    • 14.24 Lecture 24 Dovetailing and non-deterministic Turing machines
    • 14.25 Lecture 25 Linear Bounded Automata and Undecidability for CFGs
  • 15 15 Extended Reading3 扩展阅读3 Extended  Reference Books
    • 15.1 15.1 English Text Book
    • 15.2 15.2 编译原理(何炎祥,伍春香,王汉飞 2010.04)
    • 15.3 15.3 编译原理(陈光建主编;贾金玲,黎远松,罗玉梅,万新副主编 2013.10)
    • 15.4 15.4 编译原理((美)Alfred V. Aho等著;李建中,姜守旭译 2003.08)
    • 15.5 15.5 编译原理学习与实践指导(金登男主编 2013.11)
    • 15.6 15.6 编译原理及编译程序构造 第2版(薛联凤,秦振松编著 2013.02)
    • 15.7 15.7 编译原理学习指导(莫礼平编 2012.01)
    • 15.8 15.8 JavaScript动态网页开发案例教程
  • 16 16 中文版课件(pdf)辅助学习
    • 16.1 第1章 引论
    • 16.2 第2章 形式语言概论
    • 16.3 第3章 有穷自动机
    • 16.4 第4章 词法分析
    • 16.5 第5章 自上而下分析
    • 16.6 第6章 优先分析方法
    • 16.7 第7章 自下而上的LR(k)分析方法
    • 16.8 第8章 语法制导翻译法
    • 16.9 第9章 运行时的存储组织与管理
    • 16.10 第10章 符号表的组织与查找
    • 16.11 第11章 优化
    • 16.12 第12章 代码生成
  • 17 17 Extended Reading4 扩展阅读4 Static Single Assignment
    • 17.1 17.1 SSA-based Compiler Design
    • 17.2 17.2 A Simple, Fast Dominance Algorithm (Rice Computer Science TR-06-33870)
    • 17.3 17.3 The Development of Static Single Assignment Form(KennethZadeck-Presentation on the History of SSA at the SSA'09 Seminar, Autrans, France, April 2009)
    • 17.4 17.4 SPIR-V Specification(John Kessenich, Google and Boaz Ouriel, Intel Version 1.00, Revision 12 January 16, 2018)
    • 17.5 17.5 Efficiently Computing Static Single Assignment Form and the Control Dependence Graph
    • 17.6 17.6 Global Value Numbers and Redundant Computations
  • 18 18 Extended Reading4 扩展阅读5 Computer Science
    • 18.1 1 实地址模式和保护模式的理解
    • 18.2 2 实模式和保护模式
    • 18.3 3 实模式和保护模式区别及寻址方式
    • 18.4 计算机专业术语
    • 18.5 Bit Math in c Language
    • 18.6 Auto-generating subtitles for any video file
    • 18.7 Autosub
    • 18.8 C语言中的内联函数(inline)与宏定义(#define)
  • 19 19 相关学习
    • 19.1 龙书、鲸书和虎书
    • 19.2 Complexity
    • 19.3 MPC Complexity
    • 19.4 NP-completeness
    • 19.5 Computational complexity theory
  • 20 20 全球战疫-武汉战疫延伸与扩展
    • 20.1 Extraordinary G20 Leaders’ Summit Statement on COVID-19
    • 20.2 Experts urge proactive measures to fight virus
    • 20.3 covid-19病毒下贫穷国家
    • 20.4 正确理解病亡率、压平曲线、疫情高峰术语
    • 20.5 为什么全球经济可能陷入长期衰退
    • 20.6 为何新冠病毒检测会出现“假阴性”
    • 20.7 在纽约,几乎每个人身边都有人感染病毒
    • 20.8 An Address by Her Majesty The Queen
    • 20.9 Boris Johnson admitted to hospital over virus sympto
    • 20.10 Edinburgh festivals cancelled due to coronavirus
    • 20.11 US set to recommend wearing of masks
    • 20.12 Boris Johnson in self-isolation after catching coronavirus
    • 20.13 Covid-19:The porous borders where the virus cannot be controlled
    • 20.14 当欧洲人开始戴上口罩
    • 20.15 Lockdown and ‘Intimate Terrorism’
    • 20.16 Us Election 2020: Bernie Sanders Suspends Presidential Campaign
    • 20.17 The aircraft carrier being infected with the coronavirus
    • 20.18 Spent to the W.H.O.
    • 20.19 Unemployment
    • 20.20 The beat of a heart the glimmer of a soul
    • 20.21 Coronavirus pandemic: EU agrees €500bn rescue package
    • 20.22 the world after coronavirus冠状病毒之后的世界
  • 21 21 课程思政方案
    • 21.1 21.1 课程思政
    • 21.2 21.2 实施方案
2 实模式和保护模式
  • 1 实模式和保护模式
  • 2 实模式和保护模式1

实模式和保护模式

(From https://blog.csdn.net/qq_37653144/article/details/82818191)


       从80386开始,CPU有三种工作模式:实模式、保护模式和虚拟8086模式。80286开始的CPU引入保护模式,实际上,实模式概念是在保护模式推出之后为了区别保护模式之前的8086CPU工作模式才有的,在8086时代CPU工作模式只有一种,自然没有实模式之说。实模式有着先天的缺陷(下文详述),但出于向上兼容的考虑,现代CPU仍然保持着对16位操纵模式的兼容。


       所谓工作模式,是指CPU的寻址方式、寄存器大小、指令用法和内存布局等。


实模式


       实模式的“实”体现在程序中用到的地址都是真实的物理地址,“段基址:段内偏移地址”产生的逻辑地址就是物理地址,即程序员可见的地址完全是真实的内存地址。


        在实模式下,内存寻址方式和8086相同,由16位段寄存器的内容乘以16(左移4位)作为段基址,加上16位段偏移地址形成20位的物理地址,最大寻址空间1MB,最大分段64KB。可以使用32位指令,即32位的x86 CPU也可以兼容实模式,此时的实模式相当于高速的8086(32位CPU的实模式可以使用32位下的资源)。在32位CPU下,系统复位或加电时都是以实模式启动,然后再切换为保护模式。在实模式下,所有的段都是可以读、写和可执行的。


       下图是实模式下的内存访问模型:


       8086CPU的实模式开创性地提出了地址分段的概念,改变了在它之前的CPU只能“硬编码”,程序无法重定位的缺点。然而实模式还是有很多缺陷,其中最主要的是实模式的安全隐患。在实模式下,用户程序和操作系统拥有同等权利,因为实模式下没有特权级。此外,程序可以随意修改自己的段基址,加上实模式下对地址的访问就是实实在在的物理地址,因此程序可以随意修改任意物理地址,甚至包括操作系统所在的内存,这给操作系统带来极大的安全问题。


保护模式


       尽管在Intel 80286手册中已经提出了保护模式,但实际上它只是一个指引。80286虽然有了保护模式但其依然是16位的CPU,其通用寄存器还是16位宽,只不过其地址线由20位变成了24位,即寻址空间扩大到了16MB(但受限于寄存器位宽,单个寄存器的寻址空间仍然为64KB)。80286只是一个“过渡”产品,很快就被淘汰。


       真正的32位地址出现在Intel 80386上,它的地址总线和寄存器都是32位的,因此其单寄存器的寻址空间扩大到了4GB——在当时甚至其后的数年,仅通过段内偏移地址都足以访问内存的任意角落,这也开启了“平坦模型”的时代。


       保护模式本身是80286及以后的x86系列处理器产生的一种操作模式,它具有许多特性设计为提高系统的多道任务和系统的安全性及稳定性——例如内存的保护,分页机制和硬件虚拟存储的支持。现代多数的x86处理器操作系统都运行在保护模式下,包括Linux, Free BSD, 和Windows3.0(它也运行在实模式下,为了和Windows 2.x应用程序兼容)及以后的版本。 


       在保护模式中,内存的管理模式分为两种——段模式和页模式。其中页模式也是基于段模式的。也就是说,保护模式的内存管理模式事实上是:纯段模式和段页式。进一步说,段模式是必不可少的,而页模式则是可选的——如果使用页模式,则是段页式,否则这是纯段模式。


       为了改进实模式下内存访问的不安全性,保护模式给内存段添加了段属性来限制用户程序对内存的操作权限。保护模式引入了全局描述符表(Global Descriptor Table,GDT),GDT的表项是描述段类型属性的数据结构——段描述符。GDT中的每一个段描述符都描述了一个内存段的基本属性,如段基址、段界限、类型、DPL等等。


       正是由于以上概念的提出,使得“段地址:段内偏移地址”的访问策略从实模式下对物理地址的直接映射变成了保护模式下对GDT或LDT的间接映射(如下图所示),进程在访问内存段(无论是数据段还是代码段)前都需要通过特权级检查。段属性的加入让用户程序对内存的访问不再“为所欲为”。