目录

  • 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 实施方案
3 实模式和保护模式区别及寻址方式

实模式和保护模式区别及寻址方式

(From http://blog.csdn.net/rosetta https://blog.csdn.net/rosetta/article/details/8933200)

64KB-4GB-64TB?


    汇编课程,组成原理课里老师讲过实模式和保护模式的区别,在很多书本上也有谈及,无奈本人理解和感悟能力实在太差,在很长一段时间里都没真正的明白它们的内含,更别说为什么实模式下最大寻址空间为1MB?段的最大长度不超过64KB?而保护模式下为啥最大寻址能力就变成了64TB?每个段最大也达4GB?更甚者分段和分页这两个高深的概念像我这种菜鸟怎么也理解不了啊!


    寻址能力都达64TB了,为啥我的电脑内存只有2GB呢?其实不用纠结于这事,这64TB就是所谓的虚拟地址空间,也叫逻辑地址空间,它能够寻址这么多,只是它有这个能力,并不代表你的内存就要装这么大,你内存比它小再多也不会影响你工作,反过来,要是它的寻址能力只有1MB,而你有2GB的内存,那么那2047MB就没有实际用处了,这就太浪费资源了。而实际上这个64TB也没有什么实际意义,因为32位的地址总线能寻址的线性地址空间和物理地址空间都是2 ^ 32 = 4GB。这个64TB是怎么出来的,稍后揭晓。


实模式与保护模式的来历


    我们先来说一下为什么有实模式和保护模式的区别。最早期的8086 CPU只有一种工作方式,那就是实模式,而且数据总线为16位,地址总线为20位,实模式下所有寄存器都是16位。而从80286开始就有了保护模式,从80386开始CPU数据总线和地址总线均为32位,而且寄存器都是32位。但80386以及现在的奔腾,酷睿等等CPU为了向前兼容都保留了实模式,现代操作系统在刚加电时首先运行在实模式下,然后再切换到保护模式下运行。


再来区别下几个基本概念:逻辑地址,线性地址和物理地址这些概念一时没领会没关系继续往下看。


三种地址


逻辑地址:即逻辑上的地址,实模式下由“段基地址+段内偏移”组成;保护模式下由“段选择符+段内偏移”组成。


线性地址:逻辑地址经分段机制后就成线性地址,它是平坦的;如果不启用分页,那么此线性地址即物理地址。


物理地址:线性地址经分页转换后就成了物理地址。


实模式寻址方式


    刚才说了8086CPU数据总线为16位,也就是一次最多能取2 ^ 16 = 64KB数据,这个数据也解释了实模式下为什么每个段最大只有64KB。但刚才还说了其地址总线为20位,这样它能寻址的能力其实是2 ^ 20 = 1MB,这也就是实模式下CPU的最大寻址能力既然。它有1MB寻址能力,那怎么用16位的段寄存器表示呢?


    这就引出了分段的概念,8086CPU将1MB存储空间分成许多逻辑段,每个段最大限长为64KB(但不一定就是64KB)。这样每个存储单元就可以用“段基地址+段内偏移地址”表示段基地址由16位段寄存器值左移4位表达,段内偏移表示相对于某个段起始位置的偏移量比如。:


SEG = 0x07c0


jmpi offset,#SEG


offset:mov ax,cs 


保护模式寻址方式


    在定义“逻辑地址”时看到保护模式和实模式的区别在于它是用段选择符而非段基地址,这也许就是保护模式的真谛所在,从段选择符入手,全面理解保护模式编程基本概念和寻址方式。


分段机制


    下面来看下保护模式是怎样通过“段选择符+段内偏移”寻址最终的线性地址或物理地址的。


图1逻辑地址到线性地址转换,这里的逻辑地址即指保护模式下的“段选择符+段内偏移地址”,如果不启用分页管理的情况下,那么此线性地址即最终的物理地址。



图1逻辑地址到线性地址转换


    在理解此图时必须要明白段选择符结构,描述符表概念等,下面就一一介绍。


如图2段选择符结构,段选择符为16位,它不直接指向段,而是通过指向的段描述符,段描述符(一会介绍)再定义段的信息。



图2段选择符结构


    其中TI用来指明全局描述符表GDT还是局部描述符表LDT,RPL表示请求特权级,索引值为13位,所以从这里看出,在保护模式下最多可以表示2^13=8192个段描述符,而TI又分GDT和LDT(如图3所示),所以一共可以表示8192*2=16384个段描述符,每个段描述符可以指定一个具体的段信息,所以一共可以表示16384个段。而图1看出,段内偏移地址为32位值,所以一个段最大可达4GB,这样16384*4GB=64TB,这就是所谓的64TB最大寻址能力,也即逻辑地址/虚拟地址。


    在保护模式实际编程中,如下一条语句:jmpi 0, 8。其中的8即段选择符,8的二进制表示为:0000 0000 0000 1000b,所以这条语句的意思是跳转到GDT表(TI=0)中的第2个(段描述符表从0开始编号,所以这里的1指表中的第2个)段描述符定义的段中,其段内偏移为0。



图3


    下面再来看段描述符结构,段描述符表中的每一项为一个段描述符,每一项为8字节,其结构如图4所示。



    从图中可知,段选择符指向的段描述符里有三个部分基地址信息,这三部分组成一个32位地址就决定了段基地址位置,此地址再加上段内偏移最终确定线性地址位置。


    段描述符中的S位和TYPE字段(四位)的不同又分为数据段描述符、代码段描述符(S=1)和系统段描述符(S=0)。数据段和代码段描述符类型如图5所示。



图5


    系统段描述符如图6所示。



图6


分页机制


    到目前为止我们知道了保护模式下是怎样通过段选择符指向一个段描述符,最终由段描述符+段内偏移定位线性地址,在不启用分页情况下,此线性地址就是物理地址,那么在启用分页情况下,又是怎样实现内存的映射转换的呢?这就是伟大的分页机制。


    分页机制如下图所示,它把物理内存分成相同固定大小的页面,2 ^ 12 = 4KB。每个页面的0〜4KB范围由线性地址的低12位表示,线性地址空间的高10位用来指定页目录中的位置,可以选择2 ^ 10 = 1024个目录项,每个目录项为四字节,所以页目录为1024 * 4B = 4KB。每个目录项中的高20位用以查更页表在物理内存中的页面,每个页表含1024个页表项,每个页表项也是四字节,这样一页表也是1024 * 4B = 4KB。所以一个页目录可以查找1024个页表,每个页表为4KB,所以总共可以查找的页面大小为1024 * 4KB = 4MB大。最后每个表表项的高20位用以定位物理地址空间中的某个页基地址,此地址再加上线性地址空间的偏移值就是最后物理内存空间单元。目录项和页表项结构如图8所示。



图7分页机制



图8


    从一个逻辑地址经过分段和分页寻址物理地址的整个过程就如图9所示。总的来说整个过就是逻辑地址经分段机制变成线性地址,如果不启用分页的情况下,此线性地址就是物理地址;如果启用分页,那么线性地址经分页机制变成物理地址。



图9分段和分页


分段和分页的意义


    说了半天分段和分页的原理,它们到底有何用?这里以保护模式下分段和分页讲解。



图10多段模型


    如图10所示。一个多段模型充分发挥了段机制的对代码,数据结构和程序提供硬件保护的能力。每个程序都有自己的段描述符表和自己的段。段可以完全属于程序私有也可以和其它程序之间共享。


访问权限的检查不仅仅用来保护地址越界,也可以保护某一特定段不允许操作。例如代码段是只读段,硬件可以阻击向代码段进行写操作。


分页为需求页,虚拟内存提供实现机制。具体的实现机制可以再深入学习。