ppt链接：点击此处

里面有老师的作业答疑的视频，计算题建议首先看老师的视频

— 删除线标记的不考

复习提纲

1. 编单程序完整组成(7个部分 5个阶段)及各部作用

编译与解释程序的区别 汇编程序与编译程序翻译的对象
高级语言、汇编语言、低级语言特点
中间语言的3种表现形式

(1) 字母表上的运算，乘积，方幂，闭包（自反闭包和正则闭包）
终结符号,非终结符号

(2) 文法所定义的语言：四元组
(给一个文法、写出文法定义的句子)
句子
句型

(3) 推导:最左框导,规范程导
语法树、短语、直接短语、句柄

(4) 文法的分类、特点

5.词法分析
哪些单词?关键词、整数、标识符.界符
正规式(给要求写正规式) 、NFA.DFA, 二者区别(对比时针对某一个点进行)
正规式→ NFA→ DFA→ DFA最小化

6.7 语法分析
自上而下 LL(1)含义 消除左递归，回溯，LL(1)文法判定3个条件

自下而上 LR(0)含义 项目（移进，待约，归约，接受）

第1章 编译的基本概念

一 .为什么学习编译

1.语言的发展过程

2.翻译程序

编译程序和解释程序
编译程序：把高级语言的源程序翻译成目标语言程序，再结合运行子程序执行出结果
解释程序：类似于口译,不生成目标代码，把高级语言源程序的代码中一个语句翻译成机器代码并执行，即边翻译，边执行。

解释程序和编译程序的根本区别：是否生成目标代码

二、编译过程概述

1.词法分析

任务：根据词法规则分析和识别单词
单词：是语言的基本语法单位
<1>保留字（关键字/基本字）（如:if、else、while）
<2>标识符（如:max、min、str）
<3>常数 （如:12、6.8、’a’）
<4>分界符（算符和界符）（如:+、-、*、/、;、（、））

词法分析程序的结果——-二元式

2.语法分析（编译程序的核心）

任务：根据语法规则（即语言的文法），分析并识别出各种语法成分（如表达式、语句、函数等），并进行语法正确性检查。
语法分析的结果——-语法树

y = x + r * 6

3.语义分析及中间代码生成

任务：依据语义规则对识别出的各种语法成分分析其含义，并进行初步翻译，生成中间代码。

生成中间代码的目的：
1、利于代码优化
2、利于目标代码的移植

中间代码的形式：
三元式(op,arg1,arg2)，eg：(+,a,b)
四元式(op,arg1,arg2,result),eg:(+,a,b,T)
逆波兰表示(对语法树的后序遍历) eg：ab的逆波兰表示为 ab

4.代码优化

任务：对中间代码进行加工变换，以得到高质量的目标代码

5.目标代码生成

任务：把中间代码变换成特定机器上的低级语言代码

☆符号表管理

填表：把源程序中的信息和编译过程中所产生的信息登记在表格中 查表：在随后的编译过程中同时又要不断的查找这些表格中的信息

☆错误处理

诊察错误，并能报告用户错误性质和位置 出错处理能力的优劣是衡量编译程序质量好坏的一个重要指标。

知识回顾： 1、编译程序的作用是什么？汇编程序的作用是什么？ 2、逻辑上，编译程序分为哪五个阶段？ 3、一个完整的编译器包括几部分？分别是什么？ 4、编译程序与解释程序最本质的区别是什么？ 5、编译程序的输入是什么？ 6、词法分析程序的输出是什么？

第2章 程序语言

程序设计语言分为高级语言和低级语言

面向机器的语言的特点是：程序的执行效率高，编制效率低，可读性差

第3章 语言分析基础

产生式

产生式的形式为：A→ α, 又称为一条规则
左部符号，非终结符，右部，可以含有非终结符和终结符

3.3 上下文无关文法及其语言

一个上下文无关文法G抽象地表示为四元组
G=（Vn,Vt,P,S）
Vn：表示非终结符号
Vt：表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=Φ
S：是开始符号，
P：是产生式的有限集合，形如：α→β

符号约定：

终结符号：是组成该语言的最基本的符号，是不可再分的基本符号。

• 字母表中比较靠前的小写字母，如a,b,c
• 操作符，如+、-等 标点符号，如括号、逗号等 数字0,1，…，9
• 保留字、标识符，如id、if等。

非终结符号：可以推导出其他的语法成分,表示一定符号串的集合。

• 字母表中比较靠前的大写字母，如A、B、C等
• 字母S，常作为开始符号(规则中的一个特殊的非终结符号，语言中的句子都从它开始推导,如程序、句子)
• 小写、斜体的名字，如expr、stmt等
• 代表程序构造的大写字母，如E（表达式）、F（因子）等

元符号，如→、|
候选式，如 α、(A) A→α | (A)

字母表中比较靠后的大写字母，如X、Y、Z等，表示文法符号
（即 既可以代表终结符号，也可以代表非终结符号）
字母表中比较靠后的小写字母，如u、v、…、z等，表示终结符号串
小写希腊字母，如α、β表示文法符号串

二. 上下文无关文法定义的语言

1.句型/句子/语言

• 文法G所产生的语言定义为： L(G)={x|S=>x,其中S为文法的开始符号，x∈Vt*} 。即: 一个文法G可以推导出的所有句子构成的一个集合, 就确定了一个语言。
• 句子：若x仅由终结符号组成，则称x为G(S)的句子。
• 句型：设Ｇ(S)是一文法，如果符号串x是从开始符号推导出来的，即有S=>x,则称x是文法G(S)的一个句型。

即: 任何由开始符号S推导出来的符号串都是句型。

2.推导/最左推导/最右推导

推导: 连续使用产生式右部去替换左部某个非终结符的过程,得到的连续序列称为一个推导。
直接推导：又称一步推导(用 符号=>表示),就是用某条规则的右部去替换该规则的左部
规范推导（最右推导）：在整个推导过程中,任何一步推导α=>β都是对α中最右边的非终结符进行替换
最左推导：在整个推导过程中,任何一步推导α=>β都是对α中最左边的非终结符进行替换

例题：

作业： 1、现有文法 G[E]： E→E+T|T T→TF|F F→(E)|a 写出a+aa的最左推导过程。

输入 “A”查看答案

3.5 上下文无关文法的设计

基本式：A→α
嵌套式：A→αBβ，α，β是终结符，B是非终结符
递归式：A→Aα|α， A→αA|α
成对符号递归： A→αAβ|αβ

乔姆斯基文法分类

• ０型文法(短文文法)： G的每个产生式α→β满足：α∈V+且α中至少含有一个非终结符,β∈V*
• １型文法(上下文有关文法)：如果G的每个产生式α→β均满足|α|<= |β|。1型文法中不能包含空产生式，即α→ ε

例如：αAβ→αγβ

• ２型文法(上下文无关文法)：G的每个产生式为S→β, S是一非终结符，β∈V*

• ３型文法(正规文法)：G的每个产生式的形式都是：A→αB或A→α，其中A,B是非终结符，α是终结符号串。(右线性文法)

  3型文法的优点是很适合描述由字母的字符串组成的词

3.4 语法树和文法的二义性

二、文法的二义性

文法的二义性是指：若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的
判定任给的一个上下文无关文法是否二义，从定义出发，找出一个该文法的句子，它有两个语法分析树
语言的二义性指：一句话有两个意思

三.消除文法二义性

对文法G (E)
P： E →T| E +T
T → F| T F
F → (E)|i
i → 0| 1……9
求句子53+4语法树

五.句型分析：短语/直接短语/句柄

• 令G是一文法，S是文法的开始符号，αβδ是文法G的一个句型。如果有：

1. S *=>αAδ且A+=> β则称β是句型αβδ相对于非终结符A的短语。
2. 如有A=> β则称β是句型αβδ相对于规则A→β的直接短语(也称简单短语)。
3. 一个句型的最左直接短语称为该句型的句柄。

   一般不直接根据上面的定义计算短语/直接短语/句柄，而是利用语法树进行计算

（计算）利用语法树分析句型

如果利用语法树进行推导，则一个句型的语法树与短语、直接短语、句柄的关系如下：
每棵子树的叶子（从左向右排列）组成一短语；
若一棵子树只有一层分支，那这棵子树的叶子（从左向右排列）组成一直接短语；
最左的只有一层分支的子树的叶子（从左向右）组成句柄。

直观地讲，短语就是某一句型中的子串，这个子串是由某个非终结符通过至少一步推导得到的子串； 直接短语就是由某个非终结符通过一步推导得到的子串； 句柄就是最左的直接短语。

对文法G (E)
P： E →T| E +T
T → F| T F
F → (E)|i
求句型ii+i的短语、直接短语和句柄。
为了方便，将句型写作 i1*i2+i3

密码 “A”查看答案

对于文法G(S):
S → (L)|aS|a
L → L，S|S
1) 画出句型(S,(a))的语法树。
2) 写出上述句型的所有短语、直接短语、句柄。

第4章 程序设计语言常用语法与翻译方法

第5章 词法分析

词法分析任务

输出形式为：（单词种类，单词）

词法分析阶段是编译的第一阶段，它的主要任务是从左至右扫描文本格式的源程序，从基于字符理解的源程序中分离出符合源语言词法的单词，最终转换成基于单词理解的源程序。

计算机高级语言一般都有关键字、标识符、常数、运算符和定界符这5类单词。

正规文法与正规式

一.正规文法

多数程序设计语言的单词的语法都能用正规文法或3型文法来描述

３型文法(正规文法)：G的每个产生式的形式都是：A→αB或A→α，其中A,B是非终结符，α是终结符串。

二. 正规式

定义简明直观，就不写了，举个例子吧

正规式应用举例

(1) 描述“标识符”单词的正规式
a(a︱b)
其中，∑＝{a,b}，a —— 字母， b —— 数字 L(a(a︱b))={a}{a,b}*

(2) 描述“整数”单词的正规式
dd︱＋dd︱－dd
其中，∑＝{＋,－,d}， d —— 数字 L(dd︱＋dd︱－dd)={+,－, ε}{d}{d}*

~~三. 正规式和正规文法之间转换 ~~

有穷自动机

有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。

有穷自动机分为两类：
确定的有穷自动机— DFA
不确定的有穷自动机— NFA

确定的有穷自动机DFA

一个确定的有穷自动机DFA M是一个五元组：M=(K,∑,f,S,Z)。其中，

1. K是状态的集合（非空有穷集），每个元素称为状态；
2. ∑是有穷字母表，每个元素称为输入字符；
3. f是K×∑→K映射，称为状态转换函数；
4. S∈K，称为开始状态，唯一开始状态；
5. Z ⊂ K，称为结束状态集，或接受状态集。
   

   不确定的有穷自动机NFA

一个不确定的有穷自动机NFA M是一个五元组：
M=(K,∑,f,S,Z)。其中，
K是非空有穷集，每个元素称为状态；
∑是有穷字母表；
f是K×∑∪{ε}→K的子集映射，
f称为状态转换函数。
S⊂K，称为开始状态集；
Z⊂K，称为可空的结束状态集，或接受状态集。

DFA与NFA的主要区别

（1）DFA任何状态都没有ε转换，即没有任何状态可以不进行输入符号的匹配就直接进入下一个状态；
（2）DFA对任何状态s和任何输入符号a，最多只有一条标记为a的边离开s，即转换函数δ：S×Σ→ S是一个单值函数。
（3）DFA的初态唯一，NFA的初态为一集合。
（4）DFA的终态集合不能为空，NFA的终态可以为空。

正规文法和有穷自动机间的转换

正规式转换为NFA

减少ε闭包技巧

NFA的确定化（NFA转换为DFA）

DFA是NFA的特例.对每个NFA N一定存在一个DFA Ｍ，使得 L(M)=L(N)。也就是说：对每个NFA N存在着与之等价的DFA M。
NFA确定化的基本思路是： DFA的每一个状态对应NFA的一组状态.
NFA确定化方法（子集法）：将NFA转换成接受同样语言的DFA
DFA使用它的一个状态去记录在NFA读入一个输入符号后可能达到的所有状态.

定义对状态集合I的几个有关运算：

1. 状态集合I的ε-闭包
   表示为ε-closure(I)，定义为一状态集，是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。状态集合I的任何状态S都属于ε-closure(I)。
   2. 状态集合I的a弧转换
   表示为move(I,a)定义为状态集合J，其中J是所有那些可从I中的某一状态经过名为a的弧而到达的状态的全体。

计算公式：

去看老师的视频讲解，链接在最上面

包含终态，则也是终态

DFA的最小化

DFA的最小化就是寻求状态数最少的DFA，即：
1.它没有多余状态；（消去）
2.它的状态中没有两个是互相等价的。（合并）

分割法
Steps:
1.所有状态分成两个子集——终态集和非终态集；
2.运用判定状态等价的原则分别对两个子集的状态进行分析和 划分，若发现某个状态与其它状态不等价，则将其作为一个 新的状态子集，如果无法区分，则放在同一子集中；
3.从每个子集中选出一个状态做代表，即可构成简化的DFA；
注意：含有原来初态的子集仍为初态，各终态的子集仍为终态。

Step 1: P0=({1,2,3,4}, {5,6,7})
Step 2: P1=({1,2}, {3,4}, {5,6,7})
Step 3: P2=({1,2}, {3}, {4}, {5,6,7})
Step 4: P3=({1,2}, {3}, {4}, {5}, {6,7})
Step 5: 令1代表{1,2}消去2,令6代表{6,7}消去7. 得到图DFA M’
写步骤给一定分数

第6章 自上而下的语法分析

6.1 自上而下语法分析思想

自上而下分析法也称面向目标的分析方法,也就是从文法的开始符号出发企图推导出与输入的单词串完全匹配的句子,若输入串是文法定义的句子,则必能推出,反之必然出错。
自上而下分析方法，要解决从文法的开始符号出发，如何根据当前的输入符号（单词符号）唯一地确定选用哪个产生式替换相应非终结符往下推导，或构造一棵相应的语法树。

6.2 非LL(1)文法到LL(1)文法的等价变换

• 消除回溯(提取左公共因子)
• 消除左递归

  一.消除回溯(提取左公共因子)

  将产生式A→αβ|αr 等价变换为: A→α(β|r)，
  将括号内用一新引入的非终结符A’表示,得 A→αA’，A’→β|r

  二.消除左递归

  产生式 (1)A->Ab
  (2)A->Bb,B->Aa
  形如(1)产生式文法包含 （简单）直接左递归
  形如(2)产生式文法包含 间接左递归
  改写规则：
  
  还有间接左递归，书本P83

  6.3 LL(1)分析法

LL(1)的含义是：

• 第一个L表示从左到右扫描输入串
• 第二个L表示分析过程用最左推导
• 1表明只需向前看一个符号便可以决定选哪个产生式进行推导 类似地,LL(k)文法需要向前看K个符号才可以确定选用哪个产生式。

  6.4 递归下降分析程序

判断条件 :
第一，文法无左递归
第二，文法无左公共因子
第三， 对每个具有相同左部的产生式A→α与A→β，
满足 SELECT(A→α)∩SELECT(A→β)=Φ。
其中α，β中至多只有一个能推出ε。

1. 首符号集FIRST
2. 后继符号集FOLLOW
3. 选择集合SELECT

产生式A->α的可选集是指可以选用该产生式进行推导时对应的输入符号的集合。

1 .首符号集FIRST(α)

概括说FIRST(α)是由α推导出的第一个终结符组成的（包括ε）集合。

2.后继符号集FOLLOW(B)

概括说FOLLOW(B)是指非终结符直接后继的终结符组成的集合。

3 .选择集合SELECT(A→α)

去看老师的视频讲解，链接在最上面

四.LL(1)分析法

分析步骤：
1.判断是否为LL(1)文法，若是，转向步骤2
2.构造预测分析表
（3）依照SELECT集合把产生式填入分析表

~~3.句子分析过程 ~~

第7章 自下而上的语法分析

7.3 LR分析法

LR分析法是一种十分强大有效的分析方法。
它适用于一大类上下文无关文法的语法分析。
“LR”中的L表示从左向右扫描输入字符串,R表示构造最右推导的逆过程（即规范归约）。

认识这4种项目是什么即可

四种类型的项目：
移进项目:A→α·a 
待约项目: A→α·B 
归约项目: A→α·
接受项目: S’→α·（以开始符号S’定义的归约项目）

第8章 语法制导翻译
第9章 运行时存储空间管理
第10章 优化及目标代码生成