目录

  • 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 实施方案
Covid-19:The porous borders where the virus cannot be controlled

Covid-19:The porous borders where the virus cannot be controlled

From: Saira Asher BBCnews

As nations shut borders, a surge of people pouring unmonitored over international boundaries in a volatile and vulnerable part of the world has sparked warnings about the unchecked spread of the virus there.

In March, more than 150,000 Afghans spontaneously returned from Iran, one of the countries worst hit by the coronavirus - thousands more arrive daily. 

Tens of thousands have also recently returned from Pakistan - among the worst affected countries in South Asia. 

Officials are struggling to control this unprecedented movement across what have always been porous and often lawless borders.

So far, Afghanistan is not among countries severely hit by the virus, reporting 423 cases and 14 deaths, but this influx has raised fears of much higher transmission rates.

"With the numbers of likely infected people who have crossed the border, I expect the numbers of cases and deaths [in Afghanistan] to go up significantly," says Natasha Howard, associate professor of global health and conflict at the National University of Singapore.


If there is an explosion of cases, like we've seen in the US, Spain and Italy, war-ravaged and impoverished Afghanistan's health system would be completely overwhelmed.

Iran crossing: Overwhelmed by numbers

Abdul Maez Mohammadi and his family were in Iran for eight years. But after the boss at the construction company where he worked stopped paying his salary, he gathered his wife, brother and one-year-old son and headed home.

This week they crossed from the Islam Qala border into Herat as undocumented migrants and will head back to their Taliban-controlled village where there are no health facilities.

"The situation in Iran of Covid-19 is very dangerous and I heard there is nowhere to admit cases," says Mr Mohammadi. 

At this border crossing there is no quarantine centre on either side. The provincial authorities are conducting basic health checks, but they are overwhelmed by the number of people.

Herat has a shortage of Covid-19 testing kits and results take four or five days for those who do get tested - and by then it is likely they would have already left for their villages.

Mr Mohammadi says he will have to earn money as soon as he is back in his village, but he knows they will have to take precautions.

"We have to do hand-washing when we wake up from sleep, brush teeth three times a day, avoid mass gatherings, not travel to neighbouring areas and food should be well cooked," he says.

Aziz Ahmad Rahimi, senior regional director for IOM in Herat province, says when they see anyone showing Covid-19 symptoms they transfer them to the local hospitals. Ten to 15 people so far have tested positive he says. 

Pakistan crossing: Forced to abandon controls

A similar situation is playing out on the border with Pakistan.

The Afghan government requested Pakistani authorities to open border crossings to allow Afghans who had become stranded after Pakistan shut its borders to return home.

Authorities said they would allow 1,000 people a day but 20,000 are reported to have crossed at the Chaman border in the last two days prompting authorities to abandon the stipulation that only those with valid documents be allowed to cross.

Afghan authorities had made arrangements to quarantine 4,000 Afghans for 14 days at Torkham but were quickly overwhelmed by the numbers, reports say.

In total 60,000 crossed into Afghanistan in three days, according to IOM. 

An unverified video that has been widely shared by media outlets shows people rushing across the border without showing any documentation.

And these are the people going through official checkpoints. For many years there has been illegal cross-border movement between Afghanistan and Pakistan - those numbers are much harder to track.

All of this has led aid agencies and NGOs working in the region to give a dire warning about the spread of coronavirus across these borders.

And if, as they fear, cases erupt in the next few weeks, how Afghanistan might deal with the numbers given developed countries with top-class health systems are struggling, is leading to some daunting estimates.

How can Afghanistan cope? 

The Afghan ministry of public health forecasts that 16 million out of a population of more than 30 million could get the coronavirus, citing the World Health Organization (WHO).

Waheedullah Mayar, spokesperson for ministry of public health, says in the worst case scenario 700,000 people will require hospitalisation, 220,000 of them may require ICU treatment. From that number 110,000 people may die due to Covid-19.

Afghanistan has 10,400 hospital beds in the entire country. In Herat province, some estimates put the number of ventilators at as little as 12.

"Afghanistan will not have such a number of beds even in 10 years," he says, adding that health authorities are focused on preventative measures.

Kabul is now under completely lockdown and public gatherings have been banned in Herat.

But this is a population where many have pre-existing conditions like tuberculosis, cancer, diabetes and there are approximately 2.5 million malnourished children, according to charity Save the Children.

But if the situation in Afghanistan is so dire why are so many desperate to come back?

Mostly it is driven by by the Covid-19 outbreaks in Iran and Pakistan and the lockdowns that have squeezed out financial opportunities. People are also afraid they just won't get medical attention there.

"The impressions among returnees is, if I'm going to die it's better to die in my home country," says Mr Rahimi.

Some experts believe it's already too late to prevent the virus from spreading widely in Afghanistan. And help is unlikely to come from the international community consumed by the virus itself.

"The situation is likely to get extremely desperate - we could almost consider it a ticking time bomb," says Natasha Howard from the National University of Singapore.