收集标识符的属性信息
- 种属 (Kind)
  - 简单变量、复合变量(数组、记录、…)、过程、…
- 类型 (Type)
  - 整型、实型、字符型、布尔型、指针型、…
- 存储位置、长度
- 值
- 作用域
- 参数和返回值信息
  - 参数个数、参数类型、参数传递方式、返回值类型、…
语义检查
- 变量或过程未经声明就使用
- 变量或过程名重复声明
- 运算分量类型不匹配
- 操作符与操作数之间的类型不匹配
  - 数组下标不是整数
  - 对非数组变量使用数组访问操作符
  - 对非过程名使用过程调用操作符
  - 过程调用的参数类型或数目不匹配
  - 函数返回类型有误

中间代码生成及编译器后端概述

常用的中间表示形式

三地址码 (Three-address Code)
- 三地址码由类似于汇编语言的指令序列组成，每个指令最多有三个操作数(operand)
语法结构树/语法树 (Syntax Trees)

三地址指令的表示

四元式 (Quadruples)
- (op, y, z, x)
三元式 (Triples)
间接三元式 (Indirect triples)

目标代码生成器

目标代码生成器以源程序的中间表示形式作为输入，并把它映射到目标语言
目标代码生成的一个重要任务是为程序中使用的变量合理分配寄存器

代码优化

为改进代码所进行的等价程序变换，使其运行得更快一些、占用空间更少一些，或者二者兼顾

二、语言及其文法

基本概念

字母表 (Alphabet)

字母表∑是一个有穷符号集合

字母表上的运算

字母表∑1和∑2的乘积( product) ∑1∑2 ={ab|a ∈ ∑1, b ∈ ∑2}
字母表∑的n次幂( power)
- ∑0 ={ ε }
- ∑n =∑n-1 ∑ , n ≥ 1
  
  字母表的n次幂:长度为n的符号串构成的集合
字母表∑的正闭包( positive closure)

∑+ = ∑∪∑2∪∑3∪…

字母表的正闭包:长度正数的符号串构成的集合
字母表∑的克林闭包(Kleene closure)

∑ 克林闭包= ∑0∪∑+ = ∑0∪∑∪∑2∪∑3∪…

字母表的克林闭包:任意符号串(长度可以为零)构成的集合

串 (String)

设∑是一个字母表，任意x∈∑克林闭包，x称为是∑上的一个串

串是字母表中符号的一个有穷序列

串s的长度，通常记作|s|，是指s中符号的个数

空串是长度为0的串，用 ε(epsilon)表示

串上的运算——连接

如果 x和y是串，那么x和y的连接(concatenation)是把y附加到x后面而形成的串，记作xy

空串是连接运算的单位元( identity)，即，对于任何串s都有，εs = sε = s

设x,y,z是三个字符串，如果 x=yz，则称y是x的前缀，z是x的后缀

串上的运算——幂

串s的幂运算

s0= ε
sn = sn-1 s , n ≥1

串s的n次幂:将n个s连接起来

文法的定义

文法的形式化定义

G=(VT ,VN ,P,S)

VT :终结符集合

VN:非终结符集合

P :产生式集合

S :开始符号

符号约定

终结符

字母表中排在前面的小写字母，如a、b、c
运算符，如+、乘等
标点符号，如括号、逗号等
数字0、1、. . . 、9
粗体字符串，如id、if等

非终结符

字母表中排在前面的大写字母，如A、B、C
字母S。通常表示开始符号
小写、斜体的名字，如expr、stmt等
代表程序构造的大写字母。如E(表达式)、T(项) 和F(因子)

在这里插入图片描述

语言的定义

推导 (Derivations)和归约(Reductions)

句子的推导(派生)-从生成语言的角度

句子的归约 - 从识别语言的角度

句型和句子

如果 S ->star α，α∈(VT∪VN)star ，则称α是G的一个句型 (sentential form)

一个句型中既可以包含终结符，又可以包含非终结符，也可能是空串

如果 S ->star w，w ∈VTstar，则称w是G的一个句子(sentence)

句子是不包含非终结符的句型

语言的形式化定义

由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言，记为L(G )。即

L(G )= {w | S ->star w, w∈ VT star }

语言上的运算

在这里插入图片描述

文法的分类

Chomsky 文法分类体系

前提：α →β

0型文法:α中至少包含1个非终结符

1型文法(CSG) :|α|≤|β|

上下文有关文法(Context-Sensitive Grammar , CSG )

2型文法(CFG) :α ∈ VN

上下文无关文法 (Context-Free Grammar, CFG )

3型文法(RG):A→wB 或 A→w (A→Bw 或A→w)

在这里插入图片描述

CFG的分析树

CFG 的分析树

在这里插入图片描述

根节点的标号为文法开始符号
内部结点表示对一个产生式A→β的应用，该结点的标号是此产生式左部A 。该结点的子结点的标号从左到右构成了产生式的右部β
叶结点的标号既可以是非终结符，也可以是终结符。从左到右排列叶节点得到的符号串称为是这棵树的产出( yield )或边缘(f rontier)

分析树是推导的图形化表示

给定一个推导 S -> α1-> α2->…-> αn ，对于推导过程中得到的每一个句型αi，都可以构造出一个边缘为αi的分析树

在这里插入图片描述

(句型的)短语

给定一个句型，其分析树中的每一棵子树的边缘称为该句型的一个短语(phrase)

如果子树只有父子两代结点，那么这棵子树的边缘称为该句型的一个直接短语(immediate phrase)

在这里插入图片描述

二义性文法 (Ambiguous Grammar)

如果一个文法可以为某个句子生成多棵分析树，则称这个文法是二义性的

二义性文法的判定

对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的

满足，肯定无二义性
不满足，也未必就是有二义性的

三、词法分析

正则表达式

正则表达式 (Regular Expression，RE ) 是一种用来描述正则语言的更紧凑的表示方法

正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式 r定义(表示)一个语言，记为L(r )。这个语言也是根据r 的子表达式所表示的语言递归定义的。

正则表达式的定义

ε是一个RE，L(ε) = {ε}
如果 a∈∑，则a是一个RE，L(a) = {a}
假设 r和 s都是 RE，表示的语言分别是 L( r)和L(s)，则
- r|s 是一个RE，L( r|s ) = L (r )∪L(s)
- rs 是一个RE，L( rs ) = L(r ) L(s)
- r star是一个RE，L( r star)= (L(r ))star
- (r ) 是一个RE，L( (r ) ) = L(r )

运算的优先级：*、连接、|

正则语言

可以用RE定义的语言叫做正则语言(regular language)或正则集合(regular set)

正则文法与正则表达式等价

对任何正则文法 G，存在定义同一语言的正则表达式 r

对任何正则表达式 r，存在生成同一语言的正则文法 G

正则定义(Regular Definition)

在这里插入图片描述

有穷自动机 ( Finite Automata，FA )

一类处理系统建立的数学模型
具有一系列离散的输入输出信息和有穷数目的内部状态(状态:概括了对过去输入信息处理的状况)
系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变

FA模型

在这里插入图片描述

FA的表示

转换图 (Transition Graph)

结点:FA的状态
- 初始状态(开始状态):只有一个，由start箭头指向
- 终止状态(接收状态):可以有多个，用双圈表示
带标记的有向边:如果对于输入a，存在一个从状态p到状态q的转换，就在p、q之间画一条有向边，并标记上a

在这里插入图片描述

FA定义(接收)的语言

给定输入串x，如果存在一个对应于串x的从初始状态到某个终止状态的转换序列，则称串x被该FA接收

由一个有穷自动机M接收的所有串构成的集合称为是该FA定义(或接收)的语言，记为L(M )

最长子串匹配原则 (Longest String Matching Principle)

当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配

在到达某个终态之后，只要输入带上还有符号， DFA就继续前进，以便寻找尽可能长的匹配

有穷自动机的分类

确定的FA (Deterministic finite automata, DFA)

在这里插入图片描述

非确定的FA (Nondeterministic finite automata, NFA)

在这里插入图片描述

DFA和NFA的等价性

对任何非确定的有穷自动机N ，存在定义同一语言的确定的有穷自动机D
对任何确定的有穷自动机D ，存在定义同一语言的非确定的有穷自动机N

从正则表达式到有穷自动机

在这里插入图片描述

从NFA到DFA的转换

子集构造法(subset construction)

在这里插入图片描述

计算 ε-closure(T)

屏幕快照 2019-06-05 22.08.45

确定性有限自动机的简化

DFA化简

概念：指寻找一个状态数比DFA Ｍ少的DFA M’,使得L(M)=L(M’)

一个确定有限自动机M是通过①消除多余状态和②合并等价状态而转换成一个最小的与之等价的有限自动机来实现其化简的。

多余状态（无用状态）

概念：从该自动机的初始状态出发，任何输入串也不能到达的那个状态。

对于给定的DFA M，若它含有多余状态，可以非常简单地将多余状态消除，而得到与之等价的有穷自动机。

两个状态S和T等价的条件

如果从S出发能读出某个字w而停于终态，那么从T出发也能读出同样的字而停于终态；
如果从T出发能读出某个字w而停于终态，那么从S出发也能读出同样的字而停于终态。

在DFA M里如果两个状态若不等价，则称这两个状态是可区别的。

DFA的状态最少化算法

子集分割法：把一个DFA M的状态分割成一些不相交的子集，使得任何不同的两个子集的状态都是可区别的，而同一子集中的两个状态都是等价的。最后，在每个子集中选出一个代表，同时消去其他等价的状态。如果在从M′中删除所有的无用状态（多余状态），则M′便是最简的（状态最少），从而得到把DFA M状态简化了的DFA M’。

在这里插入图片描述

四、语法分析

自顶向下的分析 (Top-Down Parsing)

每一步推导中，都需要做两个选择

替换当前句型中的哪个非终结符
用该非终结符的哪个候选式进行替换

最左推导 (Left-most Derivation)

在最左推导中，总是选择每个句型的最左非终结符进行替换

如果S->* α，则称α是当前文法的最左句型 (left-sentential form)

自顶向下的语法分析采用最左推导方式

最右推导 (Right-most Derivation)

在最右推导中，总是选择每个句型的最右非终结符进行替换

在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范归约，而最右推导相应地称为规范推导

递归下降分析 (Recursive-Descent Parsing)

由一组过程组成，每个过程对应一个非终结符
从文法开始符号S对应的过程开始，其中递归调用文法中其它非终结符对应的过程。如果S对应的过程体恰好扫描了整个输入串，则成功完成语法分析
可能需要回溯 (backtracking)，导致效率较低

预测分析 (Predictive Parsing)

预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数(通常是一个)符号来选择正确的A-产生式。

可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k) 文法类

预测分析不需要回溯，是一种确定的自顶向下分析方法

文法转换

左递归

含有A→Aα形式产生式的文法称为是直接左递归的 (immediate left recursive)

如果一个文法中有一个非终结符A使得对某个串α存在一个推导A->+Aα ，那么这个文法就是左递归的

经过两步或两步以上推导产生的左递归称为是间接左递归的

消除直接左递归

在这里插入图片描述
事实上，这种消除过程就是把左递归转换成了右递归

消除间接左递归

在这里插入图片描述

提取左公因子 (Left Factoring )

通过改写产生式来推迟决定，等读入了足够多的输入，获得足够信息后再做出正确的选择

在这里插入图片描述

LL(1) 文法

S _ 文法-简单的确定性文法

每个产生式的右部都以终结符开始
同一非终结符的各个候选式的首终结符都不同

S_文法不含ε产生式

预测分析法的工作过程：从文法开始符号出发，在每一步推导过程中根据当前句型的最左非终结符A和当前输入符号a，选择正确的 A- 产生式。为保证分析的确定性，选出的候选式必须是唯一的。

非终结符的后继符号集

可能在某个句型中紧跟在A后边的终结符a的集合，记为FOLLOW(A)，FOLLOW(A)={a| S->αAaβ, a∈VT，α,β∈(VT ∪ VN)*}

如果 A是某个句型的的最右符号，则将结束符 “$” 添加到 FOLLOW(A) 中

产生式的可选集

产生式A→β的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为SELECT( A→β )

SELECT( A→aβ ) = { a }

SELECT( A→ε )=FOLLOW( A )

q_ 文法

每个产生式的右部或为ε ，或以终结符开始
具有相同左部的产生式有不相交的可选集

q_文法不含右部以非终结符打头的产生式

串首终结符集

串首终结符

串首第一个符号，并且是终结符，简称首终结符

给定一个文法符号串α， α的串首终结符集FIRST(α)被定义为可以从α推导出的所有串首终结符构成的集合。

如果α ->* ε，那么ε也在FIRST(α)中
对于任意α∈(VT ∪ V N)+, FIRST(α)={ a | α->* aβ，a∈ VT，β∈(VT ∪ VN)*};

产生式A→α的可选集SELECT

如果ε不属于FIRST(α), 那么SELECT(A→α)=FIRST(α)
如果 ε∈FIRST(α), 那么SELECT(A→α)=( FIRST(α)-{ε} )∪FOLLOW(A)

LL(1) 文法

文法G是LL(1)的，当且仅当G的任意两个具有相同左部的产生式A → α | β 满足下面的条件

不存在终结符a使得α 和β都能够推导出以a开头的串
α 和β至多有一个能推导出ε
如果 β -> ε，则FIRST (α)∩FOLLOW(A) =Φ；如果 α -> ε，则FIRST (β)∩FOLLOW(A) =Φ

sum=同一非终结符的各个产生式的可选集互不相交

第一个“L” 表示从左向右扫描输入
第二个“ L” 表示产生最左推导
“1” 表示在每一步中只需要向前看一个输入符号来决定语法分析动作

FIRST集和 FOLLOW集的计算

在这里插入图片描述

计算文法符号X的FIRST(X )

算法：不断应用下列规则，直到没有新的终结符或ε可以被加入到任何FIRST集合中为止

如果X是一个终结符，那么FIRST ( X ) = { X }
如果X是一个非终结符，且 X→Y1…Yk∈P (k≥1)，那么如果对于某个i，a在FIRST (Yi ) 中且ε 在所有的FIRST(Y1) , … , FIRST(Yi-1)中(即Y1…Yi-1->* ε )，就把a加入到FIRST( X )中。如果对于所有的 j = 1,2, . . . , k，ε在 FIRST(Yj)中，那么将ε加入到FIRST( X )
如果 X→ε∈P，那么将ε加入到FIRST( X ) 中

计算串X1X2 …Xn的FIRST 集合

在这里插入图片描述

计算非终结符A的FOLLOW(A)

算法：不断应用下列规则，直到没有新的终结符可以被加入到任何FOLLOW集合中为止

将$放入FOLLOW( S )中，其中S是开始符号，$ 是输入右端的结束标记
如果存在一个产生式A→αBβ，那么FIRST ( β )中除ε 之外的所有符号都在FOLLOW( B )中
如果存在一个产生式A→αB，或存在产生式A→αBβ且 FIRST ( β ) 包含ε，那么 FOLLOW( A ) 中的所有符号都在 FOLLOW( B ) 中

递归的预测分析法

递归的预测分析法是指:在递归下降分析中，根据预测分析表进行产生式的选择

根据每个非终结符的产生式和LL(1)文法的预测分析表，为每个非终结符编写对应的过程

在这里插入图片描述

非递归的预测分析法

非递归的预测分析不需要为每个非终结符编写递归下降过程，而是根据预测分析表构造一个自动机，也叫表驱动的预测分析

在这里插入图片描述

表驱动的预测分析法

在这里插入图片描述

预测分析法实现步骤

构造文法
改造文法:消除二义性、消除左递归、消除回溯
求每个变量的FIRST集和FOLLOW集，从而求得每个候选式的SELECT集
检查是不是 LL(1) 文法，若是，构造预测分析表
对于递归的预测分析，根据预测分析表为每一个非终结符编写一个过程;对于非递归的预测分析，实现表驱动的预测分析算法

自底向上分析

自底向上分析概述

自底向上的语法分析

自顶向下的语法分析采用最左推导方式
自底向上的语法分析采用最左归约方式(反向构造最右推导)

自底向上语法分析的通用框架：移入 - 归约分析(Shift-Reduce Parsing)

在这里插入图片描述

移入-归约分析器可采取的4种动作

移入:将下一个输入符号移到栈的顶端
归约:被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
接收:宣布语法分析过程成功完成
报错:发现一个语法错误，并调用错误恢复子例程

LR分析法概述

LR 分析法

LR文法是最大的、可以构造出相应移入 - 归约语法分析器的文法类

L: 对输入进行从左到右的扫描
R: 反向构造出一个最右推导序列

LR(k)分析：需要向前查看k个输入符号的LR分析

k = 0和k = 1这两种情况具有实践意义，当省略 (k) 时，表示 k =1

LR 分析法的基本原理

自底向上分析的关键问题是什么? ans：如何正确地识别句柄

句柄是逐步形成的，用“状态”表示句柄识别的进展程度

在这里插入图片描述

LR 分析器(自动机)的总体结构

在这里插入图片描述

LR(0)分析

LR(0) 项目

右部某位置标有圆点的产生式称为相应文法的一个LR(0) 项目(简称为项目)

S → ·bBB 移进项目
S → b·BB 待约项目
S → bB·B 待约项目
S → bBB· 归约项目

项目描述了句柄识别的状态

产生式A→ε 只生成一个项目A→ ·

增广文法 (Augmented Grammar)

如果G 是一个以S为开始符号的文法，则G的增广文法 G’ 就是在G中加上新开始符号S’ 和产生式S’ → S而得到的文法

引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态

文法中的项目

后继项目(Successive Item)

同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目

eg A→α· Xβ的后继项目是A→αX·β

可以把等价的项目组成一个项目集( I ) ，称为项目集闭包 (Closure of Item Sets)，每个项目集闭包对应着自动机的一个状态

在这里插入图片描述

LR(0)分析表构造算法

CLOSURE( ) 函数

计算给定项目集I的闭包 CLOSURE(I) =I ∪{B→·γ|A→α·Bβ∈CLOSURE(I),B→γ∈P}

GOTO ( ) 函数

返回项目集I对应于文法符号X的后继项目集闭包GOTO( I, X )=CLOSURE({A→αX·β | A→α·Xβ∈I })

构造 LR(0) 自动机的状态集

规范LR(0) 项集族(Canonical LR(0) Collection)C={I0}∪{I | 存在J∈C, X∈VN∪ VT , I=GOTO(J , X) }

LR(0) 分析表构造算法

在这里插入图片描述

LR(0) 自动机的形式化定义

在这里插入图片描述

SLR分析

SLR 分析

在这里插入图片描述

SLR 分析表构造算法

在这里插入图片描述

LR(1)分析

LR(1)分析法的提出

SLR分析存在的问题：SLR只是简单地考察下一个输入符号b是否属于与归约项目A→α相关联的FOLLOW(A)，但b∈FOLLOW(A) 只是归约α的一个必要条件，而非充分条件

对于产生式 A→α的归约，在不同的使用位置，A会要求不同的后继符号

在特定位置，A的后继符集合是 FOLLOW(A) 的子集

规范LR(1)项目

将一般形式为 [A→α· β, a]的项称为 LR(1) 项，其中A→αβ 是一个产生式，a 是一个终结符(这里将$视为一个特殊的终结符) 它表示在当前状态下，A后面必须紧跟的终结符，称为该项的展望符

LR(1) 中的1指的是项的第二个分量的长度

在形如[A→α·β, a]且β ≠ ε的项中，展望符a没有任何作用，但是一个形如 [A→α·, a]的项在只有在下一个输入符号等于a时才可以按照A→α 进行归约

这样的a的集合总是FOLLOW(A)的子集，而且它通常是一个真子集

等价LR(1)项目

在这里插入图片描述

b∈FIRST(βa)

LR(1)项目集闭包

CLOSURE( I ) = I ∪ { [B→·γ, b] | [A→α·Bβ,a] ∈ CLOSURE( I ), B→γ∈P, b∈FIRST(βa) }

GOTO 函数

GOTO( I, X ) = CLOSURE({[A→αX·β,a]|[A→α·Xβ, a]∈I })

LR(1)自动机的形式化定义

在这里插入图片描述

LR分析表构造算法

在这里插入图片描述

LALR分析法

LALR ( lookahead-LR )分析的基本思想

寻找具有相同核心的LR (1) 项集，并将这些项集合并为一个项集。所谓项集的核心就是其第一分量的集合。
根据合并后得到的项集族构造语法分析表
如果分析表中没有语法分析动作冲突，给定的文法就称为LALR (1) 文法，就可以根据该分析表进行语法分析

合并同心项集后，虽然不产生冲突，但可能会推迟错误的发现

合并同心项集时会产生归约-归约冲突

在这里插入图片描述

合并同心项集不会产生移进 - 归约冲突

存在的小问题

合并同心项集后，虽然不产生冲突，但可能会推迟错误的发现

在这里插入图片描述

LALR分析法可能会作多余的归约动作，但绝不会作错误的移进操作，因为合并同心项集不会影响移进

LALR(1)的特点

形式上与 LR(1) 相同
大小上与 LR(0)/SLR 相当
分析能力介于SLR 和 LR(1) 二者之间：SLR<LALR(1)<LR(1)
合并后的展望符集合仍为FOLLOW 集的子集

五、语法制导翻译

语法制导翻译概述

什么是语法制导翻译

在这里插入图片描述

语法制导翻译的基本思想

如何表示语义信息?

为CFG中的文法符号设置语义属性，用来表示语法成分对应的语义信息

如何计算语义属性?

文法符号的语义属性值是用与文法符号所在产生式 (语法规则)相关联的语义规则来计算的
对于给定的输入串x ，构建x的语法分析树，并利用与产生式(语法规则)相关联的语义规则来计算分析树中各结点对应的语义属性值

两个概念

将语义规则同语法规则(产生式)联系起来要涉及两个概念

语法制导定义(Syntax-Directed Definitions, SDD)
语法制导翻译方案 (Syntax-Directed Translation Scheme , SDT )

语法制导定义 (SDD)

SDD 是对CFG的推广

将每个文法符号和一个语义属性集合相关联
将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值

在这里插入图片描述

语法制导翻译方案( SDT )

SDT是在产生式右部嵌入了程序片段的CFG，这些程序片段称为语义动作。

在这里插入图片描述

一个语义动作在产生式中的位置决定了这个动作的执行时间

SDD与SDT

SDD

是关于语言翻译的高层次规格说明
隐蔽了许多具体实现细节，使用户不必显式地说明翻译发生的顺序

SDT

可以看作是对SDD的一种补充，是SDD的具体实施方案
显式地指明了语义规则的计算顺序，以便说明某些实现细节

语法制导定义SDD

综合属性(synthesized attribute)

在分析树结点 N上的非终结符A的综合属性只能通过N的子结点或 N本身的属性值来定义

终结符可以具有综合属性：终结符的综合属性值是由词法分析器提供的词法值，因此在SDD中没有计算终结符属性值的语义规则

继承属性(inherited attribute)

在分析树结点 N上的非终结符A的继承属性只能通过N的父结点、N的兄弟结点或 N本身的属性值来定义

终结符没有继承属性：终结符从词法分析器处获得的属性值被归为综合属性值

属性文法 (Attribute Grammar)

一个没有副作用的SDD有时也称为属性文法

属性文法的规则仅仅通过其它属性值和常量来定义一个属性值

SDD的求值顺序

按照什么顺序计算属性值?

语义规则建立了属性之间的依赖关系，在对语法分析树节点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值

依赖图(Dependency Graph)

依赖图是一个描述了分析树中结点属性间依赖关系的有向图
分析树中每个标号为X的结点的每个属性a都对应着依赖图中的一个结点
如果属性X.a的值依赖于属性Y.b的值，则依赖图中有一条从Y.b的结点指向X.a的结点的有向边

属性值的计算顺序

可行的求值顺序是满足下列条件的结点序列N1, N2, … , Nk :如果依赖图中有一条从结点Ni到 Nj 的边(Ni→Nj), 那么i < j(即:在节点序列中，Ni 排在Nj 前面)

这样的排序将一个有向图变成了一个线性排序，这个排序称为这个图的拓扑排序(topological sort)

拓扑排序存在性

对于只具有综合属性的SDD ，可以按照任何自底向上的顺序计算它们的值
对于同时具有继承属性和综合属性的SDD，不能保证存在一个顺序来对各个节点上的属性进行求值
- 如果图中没有环，那么至少存在一个拓扑排序
- 从计算的角度看，给定一个SDD，很难确定是否存在某棵语法分析树，使得SDD的属性之间存在循环依赖关系；幸运的是，存在一个SDD的有用子类，它们能够保证对每棵语法分析树都存在一个求值顺序，因为它们不允许产生带有环的依赖图

S-属性定义与L-属性定义

S-属性定义

仅仅使用综合属性的SDD称为S属性的SDD，或S-属性定义、S-SDD

如果一个SDD是S属性的，可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值
S-属性定义可以在自底向上的语法分析过程中实现

L-属性定义

一个SDD是L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性:假设存在一个产生式A→X1X2…Xn，其右部符号Xi (1<= i <= n)的继承属性仅依赖于下列属性:

A的继承属性(如果是综合属性，可能会形成环)
产生式中Xi左边的符号 X1, X2, … , Xi-1 的属性
Xi本身的属性，但Xi 的全部属性不能在依赖图中形成环路

注：每个S-属性定义都是L-属性定义

语法制导翻译方案SDT

语法制导翻译方案(SDT )是在产生式右部中嵌入了程序片段(称为语义动作)的CFG

SDT可以看作是SDD的具体实施方案

基本文法可以使用LR分析技术，且SDD是S属性的
基本文法可以使用LL分析技术，且SDD是L属性的

将S-SDD转换为SDT

将一个S-SDD转换为SDT的方法:将每个语义动作都放在产生式的最后

S-属性定义的SDT 实现

如果一个S-SDD的基本文法可以使用LR分析技术，那么它的SDT可以在LR语法分析过程中实现

将L-SDD转换为SDT

将L-SDD转换为SDT的规则

将计算某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上
将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端

L-属性定义的SDT 实现

如果一个L-SDD的基本文法可以使用LL分析技术，那么它的SDT可以在LL或LR语法分析过程中实现

在非递归的预测分析过程中进行语义翻译
在递归的预测分析过程中进行语义翻译
在LR分析过程中进行语义翻译

在非递归的预测分析过程中进行翻译

扩展语法分析栈

在这里插入图片描述

分析栈中的每一个记录都对应着一段执行代码

综合记录出栈时，要将综合属性值复制给后面特定的语义动作
变量展开时(即变量本身的记录出栈时)，如果其含有继承属性，则要将继承属性值复制给后面特定的语义动作

在递归的预测分析过程中进行翻译

算法

为每个非终结符A构造一个函数，A的每个继承属性对应该函数的一个形参，函数的返回值是A的综合属性值。对出现在A产生式中的每个文法符号的每个属性都设置一个局部变量
非终结符A的代码根据当前的输入决定使用哪个产生式
与每个产生式有关的代码执行如下动作:从左到右考虑产生式右部的词法单元、非终结符及语义动作
- 对于带有综合属性x的词法单元 X，把x的值保存在局部变量 X.x中;然后产生一个匹配 X的调用，并继续输入
- 对于非终结符B，产生一个右部带有函数调用的赋值语句c := B(b1 , b2 , …, bk)，其中， b1 , b2 , …, bk是代表B的继承属性的变量，c是代表B的综合属性的变量
- 对于每个动作，将其代码复制到语法分析器，并把对属性的引用改为对相应变量的引用

L-属性定义的自底向上翻译

给定一个以LL文法为基础的L-SDD，可以修改这个文法，并在LR语法分析过程中计算这个新文法之上的SDD

首先构造SDT，在各个非终结符之前放置语义动作来计算它的继承属性，并在产生式后端放置语义动作计算综合属性
对每个内嵌的语义动作，向文法中引入一个标记非终结符来替换它。每个这样的位置都有一个不同的标记，并且对于任意一个标记M都有一个产生式M→ε
如果标记非终结符M在某个产生式A→α{a}β中替换了语义动作a，对a进行修改得到a’ ，并且将a’关联到M→ε 上。动作a’
1. 将动作a需要的A或α中符号的任何属性作为M的继承属性进行复制
2. 按照a中的方法计算各个属性，但是将计算得到的这些属性作为M的综合属性

六、中间代码生成

类型表达式

类型表达式 (Type Expressions)

基本类型是类型表达式
可以为类型表达式命名，类型名也是类型表达式
将类型构造符(type constructor)作用于类型表达式可以构成新的类型表达式
- 数组构造符array
  - 若T是类型表达式，则array ( I, T )是类型表达式( I是一个整数)
- 指针构造符pointer
  - 若T 是类型表达式，则 pointer ( T ) 是类型表达式，它表示一个指针类型
- 笛卡尔乘积构造符
  - 若T1 和T2是类型表达式，则笛卡尔乘积T1 x T2 是类型表达式
- 函数构造符→
  - 若T1、T2、…、Tn 和R是类型表达式，则T1xT2 x…xTn→ R是类型表达式
- 记录构造符record
  - 若有标识符N1 、N2 、…、Nn 与类型表达式T1 、T2 、…、Tn ，则 record((N1 xT1)x(N2xT2)x…x(Nn xTn))是一个类型表达式

声明语句的翻译

局部变量的存储分配

对于声明语句，语义分析的主要任务就是收集标识符的类型等属性信息，并为每一个名字分配一个相对地址
- 从类型表达式可以知道该类型在运行时刻所需的存储单元数量称为类型的宽度(width)
- 在编译时刻，可以使用类型的宽度为每一个名字分配一个相对地址
名字的类型和相对地址信息保存在相应的符号表记录中

在这里插入图片描述

简单赋值语句的翻译

赋值语句翻译的任务

在这里插入图片描述

赋值语句翻译的主要任务：生成对表达式求值的三地址码

在这里插入图片描述

数组引用的翻译

在这里插入图片描述

将数组引用翻译成三地址码时要解决的主要问题是确定数组元素的存放地址，也就是数组元素的寻址

数组元素寻址 (Addressing Array Elements )

在这里插入图片描述

带有数组引用的赋值语句的翻译

在这里插入图片描述

数组引用的SDT

在这里插入图片描述

控制流语句及其SDT

控制流语句的基本文法

在这里插入图片描述

布尔表达式及其SDT

布尔表达式的基本文法

在这里插入图片描述

在跳转代码中，逻辑运算符&&、|| 和 ! 被翻译成跳转指令。运算符本身不出现在代码中，布尔表达式的值是通过代码序列中的位置来表示的

在这里插入图片描述

SDT的通用实现方法

任何SDT都可以通过下面的方法实现：首先建立一棵语法分析树，然后按照从左到右的深度优先顺序来执行这些动作

回填 (Backpatching)

基本思想

生成一个跳转指令时，暂时不指定该跳转指令的目标标号。这样的指令都被放入由跳转指令组成的列表中。同一个列表中的所有跳转指令具有相同的目标标号。等到能够确定正确的目标标号时，才去填充这些指令的目标标号。

七、运行存储分配

运行存储分配概述

运行存储分配策略

编译器在工作过程中，必须为源程序中出现的一些数据对象分配运行时的存储空间

对于那些在编译时刻就可以确定大小的数据对象，可以在编译时刻就为它们分配存储空间，这样的分配策略称为静态存储分配
如果不能在编译时完全确定数据对象的大小，就要采用动态存储分配的策略。即在编译时仅产生各种必要的信息，而在运行时刻，再动态地分配数据对象的存储空间
- 栈式存储分配
- 堆式存储分配

注：静态和动态分别对应编译时刻和运行时刻

运行时内存的划分

在这里插入图片描述

活动记录

使用过程(或函数、方法)作为用户自定义动作的单元的语言，其编译器通常以过程为单位分配存储空间
过程体的每次执行称为该过程的一个活动(activation)
过程每执行一次，就为它分配一块连续存储区，用来管理过程一次执行所需的信息，这块连续存储区称为活动记录( activation record )

活动记录的一般形式

在这里插入图片描述

静态存储分配

在静态存储分配中，编译器为每个过程确定其活动记录在目标程序中的位置，这样，过程中每个名字的存储位置就确定了。因此，这些名字的存储地址可以被编译到目标代码，过程每次执行时，它的名字都绑定到同样的存储单元。

静态存储分配的限制条件

适合静态存储分配的语言必须满足以下条件

数组上下界必须是常数
不允许过程的递归调用
不允许动态建立数据实体

满足这些条件的语言有BASIC和FORTRAN等

常用的静态存储分配方法

顺序分配法
- 按照过程出现的先后顺序逐段分配存储空间
- 各过程的活动记录占用互不相交的存储空间
层次分配法
- 通过对过程间的调用关系进行分析，凡属无相互调用关系的并列过程，尽量使其局部数据共享存储空间
- 层次分配法方向：自底向上

栈式存储分配

有些语言使用过程、函数或方法作为用户自定义动作的单元，几乎所有针对这些语言的编译器都把它们的(至少一部分的)运行时刻存储以栈的形式进行管理，称为栈式存储分配

当一个过程被调用时，该过程的活动记录被压入栈;当过程结束时，该活动记录被弹出栈

这种安排不仅允许活跃时段不交叠的多个过程调用之间共享空间，而且允许以如下方式为一个过程编译代码:它的非局部变量的相对地址总是固定的，和过程调用序列无关

活动树

用来描述程序运行期间控制进入和离开各个活动的情况的树称为活动树

树中的每个结点对应于一个活动。根结点是启动程序执行的main过程的活动
在表示过程p的某个活动的结点上，其子结点对应于被p 的这次活动调用的各个过程的活动。按照这些活动被调用的顺序，自左向右地显示它们，一个子结点必须在其右兄弟结点的活动开始之前结束
每个活跃的活动都有一个位于控制栈中的活动记录
活动树的根的活动记录位于栈底
程序控制所在的活动的记录位于栈顶
栈中全部活动记录的序列对应于在活动树中到达当前控制所在的活动结点的路径

设计活动记录的一些原则

在这里插入图片描述

调用序列和返回序列

过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等

调用序列
- 实现过程调用的代码段。为一个活动记录在栈中分配空间，并在此记录的字段中填写信息
返回序列
- 恢复机器状态，使得调用过程能够在调用结束之后继续执行
一个调用代码序列中的代码通常被分割到调用过程(调用者) 和被调用过程(被调用者)中。返回序列也是如此。

变长数据的存储分配

在现代程序设计语言中，在编译时刻不能确定大小的对象将被分配在堆区。但是，如果它们是过程的局部对象，也可以将它们分配在运行时刻栈中。尽量将对象放置在栈区的原因:可以避免对它们的空间进行垃圾回收，也就减少了相应的开销。
只有一个数据对象局部于某个过程，且当此过程结束时它变得不可访问，才可以使用栈为这个对象分配空间。

非局部数据的访问

一个过程除了可以使用过程自身定义的局部数据以外，还可以使用过程外定义的非局部数据

语言可以分为两种类型

支持过程嵌套声明的语言
- 可以在一个过程中声明另一个过程
- 例: Pascal：一个过程除自身定义的局部数据和全局定义的数据以外，还可以使用外围过程中声明的对象
不支持过程嵌套声明的语言
- 不可以在一个过程中声明另一个过程
- 例:C：过程中使用的数据要么是自身定义的局部数据，要么是在所有过程之外定义的全局数据

无过程嵌套声明时的数据访问

变量的存储分配和访问

全局变量被分配在静态区，使用静态确定的地址访问它们
其它变量一定是栈顶活动的局部变量。可以通过运行时刻栈的top_sp指针访问它们

有过程嵌套声明时的数据访问

嵌套深度

过程的嵌套深度
- 不内嵌在任何其它过程中的过程，设其嵌套深度为1
- 如果一个过程p在一个嵌套深度为i的过程中定义，则设定p的嵌套深度为i +1
变量的嵌套深度
- 将变量声明所在过程的嵌套深度作为该变量的嵌套深度

访问链 (Access Links)

静态作用域规则:只要过程b的声明嵌套在过程a的声明中，过程b就可以访问过程a中声明的对象

可以在相互嵌套的过程的活动记录之间建立一种称为访问链(Access link)的指针，使得内嵌的过程可以访问外层过程中声明的对象
- 如果过程b在源代码中直接嵌套在过程a中(b的嵌套深度比a的嵌套深度多1)，那么b的任何活动中的访问链都指向最近的a的活动

访问链的建立

建立访问链的代码属于调用序列的一部分

假设嵌套深度为nx的过程x调用嵌套深度为ny的过程y (x→y)

nx < ny 的情况(外层调用内层)
- y一定是直接在x中定义的 (例如:s→q, q→p) ，因此，ny=nx +1
- 在调用代码序列中增加一个步骤:在y的访问链中放置一个指向x的活动记录的指针
n =n的情况(本层调用本层)
- 递归调用(例如: q→q )
- 被调用者的活动记录的访问链与调用者的活动记录的访问链是相同的，可以直接复制
nx > ny的情况(内层调用外层，如: p→e )
- 过程x必定嵌套在某个过程z中，而z中直接定义了过程y
- 从x的活动记录开始，沿着访问链经过nx - ny + 1 步就可以找到离栈顶最近的z的活动记录。y的访问链必须指向z的这个活动记录

堆式存储分配

堆式存储分配是把连续存储区域分成块，当活动记录或其它对象需要时就分配
块的释放可以按任意次序进行，所以经过一段时间后，对可能包含交错的正在使用和已经释放的区域

符号表

符号表的组织：为每个作用域(程序块)建立一个独立的符号表

根据符号表进行数据访问

在这里插入图片描述

实际上，这种为每个过程或作用域建立的符号表与编译时的活动记录是对应的。一个过程的非局部名字的信息可以通过扫描外围过程的符号表而得到

标识符的基本处理方法

当在某一层的声明语句中识别出一个标识符(id的定义性出现)时，以此标识符查相应于本层的符号表
- 如果查到，则报错并发出诊断信息“id重复声明”
- 否则，在符号表中加入新登记项，将标识符及有关信息填入
当在可执行语句部分扫视到标识符时( id的应用性出现)
- 首先在该层符号表中查找该id，如果找不到，则到直接外层符号表中去查，如此等等，一旦找到，则在表中取出有关信息并作相应处理
- 如果查遍所有外层符号表均未找到该id，则报错并发出诊断信息“id未声明”

符号表的建立

在这里插入图片描述

红色箭头在建表的时候完成，蓝色箭头在表建好之后完成。

收起

展开全文

【编译原理】编译原理简单介绍

万次阅读 多人点赞 2017-05-07 13:27:20

编译原理简单介绍编译原理简单介绍什么叫编译程序翻译程序编译程序翻译和编译的区别编译的过程词法分析语法分析语义分析和中间代码的产生优化目标代码生成编译程序的结构编译程序总框表格与表格的管理 ...

编译原理简单介绍

什么叫编译程序

翻译程序

翻译程序（Translator）是一种程序，其输入是某种语言的一系列语句，而其输出则是另一种语言的一系列语句，二者在逻辑上是等价的。就类似生活中的翻译官一样，把英语翻译成汉语，二者在意思上也是等价的。
这里写图片描述

编译程序

编译程序（Compiler）是一种程序。它把用高级语言写的源程序作为数据接收，经过翻译转换，产生面向机器的代码作为输出。
这当中代码还可能要由汇编程序或装配程序作进一步加工，得出目标程序，交给计算机执行。
这里写图片描述

翻译和编译的区别

这里写图片描述

编译的过程

编译程序的工作过程一般可以分为5个阶段：
1. 词法分析
2. 语法分析
3. 语义分析和中间代码的产生
4. 优化
5. 目标代码生成

词法分析

词法分析的任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词（定义符、标识符、运算符、界符、常数）。

在词法分析阶段的工作中所依循的是语言的语法规则（或称构词规则）。
描述语法规则的有效工具是正规式和有限自动机。

语法分析

语法分析的任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单元（语法范畴）（短语、子句、句子、程序段、程序），并确定整个输入串是否构成语法上正确的程序。

语法分析所依循的是语言的语法规则。
语法规则通常用上下文无关文法描述。
词法分析是一种线性分析，而语法分析是一种层次结构分析。

语义分析和中间代码的产生

这一阶段的任务是：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。这一阶段通常包含两个方面的工作。
1. 对每种语法范畴进行静态语义的检查，例如，变量是否定义、类型是否正确等等。
2. 如果语义正确则进行中间代码的翻译。

这一阶段所依循的是语言的语义规则，通常使用属性文法描述语义规则。

优化

对于代码（主要是中间代码）进行加工变换，以期能够产生更为高效（省时间和空间）的目标代码　。
优化的主要方面有：公共子表达式的提取、循环优化、删除无用代码等等。

优化所依循的是程序的等价变换规则。

目标代码生成

这一阶段的任务是：把中间代码（经过优化处理之后的）变换成特定机器上的低级语言代码（绝对指令、可重定位指令、汇编指令
）。

编译程序的结构

编译程序总框

这里写图片描述

表格与表格的管理

编译程序在工作过程中需要保持一系列的表格，以登记源程序的各类信息和编译各阶段的进展状况。
最重要的是符号表，用来等级源程序中出现的每个名字以及名字的各种属性。例如，一个名字是常量名还是变量名，还是过程名；如果是变量名，类型是什么，占多大内存，地址是多少等等。

编译各阶段均须维持表格并进行表格管理，建表的技术支持是数据结构，表格的分类、结构、处理方法决定于语言及机器，还有优化措施。

出错处理

如果源程序有错误，编译程序应设法发现错误，并把有关错误的信息报告给用户。一个好的编译程序：
1. 全
最大限度发现错误
2. 准
准确指出错误的性质和发生地点
3. 局部化
将错误的影响限制在尽可能小的范围内
4. 自动校正
若能自动校正错误则更好，但其代价非常高

源程序中的错误一般分为语法错误和语义错误。
1. 语法错误
指源程序中不符合不符合语法（或词法）规则的错误，例如：单词拼写错误、括号不匹配等等。
2. 语义错误
指源程序中不符合语义规则的错误，例如：说明错误、作用域错误、类型不匹配等等。
一般在语义分析时检出来，有的语义错误要在运行时才能检测出来。

遍

遍是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。遍数多了，整个编译程序的逻辑结构就比较清晰，但是会增加输入和输出所消耗的时间。因此，在主存可能的前提下，一般还是遍数少的好。
分遍的依据：
1. 源程序的结构
2. 选用机型的内存大小
3. 设计目标的技术指标
4. 参加编译程序人员的数量、素质

好的编译程序的指标：
1. 符合语法规则的程序都可执行。
2. 任何非法的错误都有可能识别，并尽量少的产生连锁反应。
3. 错误不至于导致系统崩溃。
4. 可维护和可读性。
5. 模块化和结构化。

编译的前端与后端

概念上我们有时候把编译程序分成编译前端和编译后端。

编译前端

前端主要由源语言有关但与目标机无关的那些部分组成，通常包括词法分析、语法分析、语义分析与中间代码的产生，有的代码优化工作也可以包括在前端。

编译后端

后端包括编译程序中与目标机有关的那些部分，如与目标机有关的代码优化和目标代码生成等。
通常后端不依赖源语言而仅仅依赖于中间语言。

编译程序的生成

编译程序的构造工具

以前人们构造编译程序大多数采用的是机器语言或汇编语言，现在只有为了充分发挥各种不同硬件系统的效率，为了满足各种不同的具体要求，才会采用这种工具来构造编译程序（或编译程序的“核心”部分）。现在越来越多采用高级语言来构造编译程序。

T型图

为了便于说明，我们常采用T型图来表示源语言S、目标语言T、和比编译程序实现语言I之间的关系。
每个T型图相当于一个编译程序。
这里写图片描述

用高级语言L1构造编译程序

如果A机器上有一个使用A机器代码实现的某高级语言L₁的编译程序（黄色），则我们可以使用L1语言编写另外一种高级语言L₂的编译程序（橙色）。把写好的L₂编译程序经过L₁编译程序编译后就可以得到A机器码实习的L₂编译程序（绿色）。
这里写图片描述

编译程序的移植

通过上面用高级语言L1构造编译程序的原理，我们可以实现编译程序的“移植”。首先我们有一个可以在A机器上编译的高级语言L，
这里写图片描述
接下来我们使用L去写一个能够在B机器上运行的编译程序，

然后通过L的编译程序就可以生成在A机器上可以运行的产生B机器代码的编译程序（3）。

使用这个编译程序（3）去编译一遍（2）就可以得到能在B机器上运行的B机器代码的编译程序（4）.
这里写图片描述

自编译方式

先对语言的核心部分构造一个小小的编译程序（可用低级语言实现），再以它为工具构造能编译更多语言成分的较大编译程序，如此不断扩展，最后形成整个编译程序（滚雪球），这种通过一系列自展途径而形成的编译程序的过程叫做自编译过程。

构造工具

现在人们已经建立了多种编制部分编译程序或者整个编译程序的有效工具。构造编译程序的工具称为编译程序-编译程序、编译程序产生器或翻译程序书写系统。
例如：
自动产生扫描器：LEX FLEX
自动产生语法分析器：YACC BISON

收起

展开全文

编译

编译原理试题汇总+编译原理期末试题(8套含答案+大题集)
2019-01-24 09:20:13
编译原理试题汇总+编译原理期末试题(8套含答案+大题集)
收起

编译原理绪论

千次阅读 2020-09-05 21:58:30

之前一直在写程序，了解到运行程序的两个步骤：编译，运行。在Microsoft visual C++中编译和运行是分开的两部分。在DEV C++中集成为一个按键。在之前的印象中，编译就是寻找语法错误的过程...怎么才能实现编译原理

之前一直在写程序，了解到运行程序的两个步骤：编译，运行。在Microsoft visual C++中编译和运行是分开的两部分。在DEV C++中集成为一个按键。在之前的印象中，编译就是寻找语法错误的过程。只要程序语法有错误，程序就无法通过编译。并会提示相应的信息，告诉写程序的人去哪里修改什么类型的错误。这学期开始，开设了编译原理课程。按照之前的习惯，通过写博客，及时梳理自己的思路并希望能在某些方面有所提高。下面开始吧！

学东西先问自己几个问题：什么是编译原理？为什么需要编译原理？怎么才能实现编译原理？

刚开始学习，对编译原理的理解不是那么深刻。简单谈一谈自己的看法。如果后续学习过程中发现自己理解有误，也会及时修改。

为什么需要编译原理？
了解计算机的人都知道对于计算机来说，它所能识别的只是机器代码。就是我们常说的0，1串。但对于编写程序的人来说，如果利用机器语言编写程序，那过程必将是痛苦且低效的。程序员为了让生活对自己好点，慢慢的开发出了高级语言，如C，C++，python等等。抽象来看，输入是高级语言，输出是机器语言，那中间的转化器就是编译器，其原理就是编译原理。现在知道为什么需要编译原理了吧！它是我们和计算机更好沟通的桥梁。

什么是编译器？
由之前的问题了解到，编译器的作用是把高级语言转换成低级语言（机器语言）。其实这简单的解释了编译器的定义。运用编译原理编写的程序，并能起到编译作用的程序叫做编译程序。把编译程序做一个推广：翻译程序。翻译程序的定义是：把某一种语言程序（称为源语言程序）转换成另一种语言程序（称为目标语言程序），而两种程序在逻辑上等价。对翻译程序的源语言（高级语言）和目标语言（机器语言）加以限制就成为了编译程序。

怎么才能实现编译原理？
问题有点抽象。转换的直接一点：编译程序怎么写？编写程序自然有它的步骤，下面会陆续介绍到编译过程的五大步骤。只有了解编译过程，才能对应去写如何实现这些编译过程的代码。

回答完刚才的问题，想必对编译原理和编译程序有了少许的了解。下面开始进入正文：通过本篇文章，想解释明白下面几个问题：

1.编译程序的五大步骤及各步骤的主要工作

2.有关编译程序的几个名词解释，包括：表格管理、出错处理、遍、编译前端/后端

3.编译程序的生成，自展和移植。

注意：因为作者对C语言比较熟悉，所以编译程序的举例都以C语言作为基准。

一、编译程序的五大步骤及各步骤的主要工作

先对五大步骤做一个说明，再详细介绍各个步骤：

1）词法分析

2）语法分析

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

4）优化

5）目标代码生成

它们的顺序其实已经说明其关系，但为了便于理解，这里附上一张关系图：
在这里插入图片描述
下面对各个步骤进行详细说明：

1）词法分析

词法分析就是从头到尾扫描，识别出语法单元，并查看是否存在词法错误。那什么是词法错误呢？举个例子：在部分编程语言中，要求变量名只能由下划线或字母打头而不能使用数字。比如在C语言中的int 3a;就一个不合法的声明，这种错误会在词法分析是被检测出来。再举一个例子，作为编程新手常犯的错误：总是把英文的;写成中文的；这个在编译过程中都会报错，错误的阶段属于词法分析。

在词法分析的过程中不止会寻找错误，也会对正确的词进行一个分类。包括以下几个类别：

1. 基本字（保留字）：主要指语言中已经定义好的那些字符，例如:int double typedef return等等

2. 标识符：主要指在程序中定义的变量名。如int a;/double b;中a，b就属于标识符

3. 界符：界符用于分隔程序，常见的界符有; { } 等

4. 算符：主要指进行运算的字符，运算包括数值运算和逻辑运算。例如：+,-,*,/和&,|;

5. 赋值符：完成的功能就是赋值，例如：=，+=，-=等

举个例子，说明词法分析干的事情：

在这里插入图片描述

2）语法分析

语法分析主要作用是根据语法规则识别语法单位并分析语句中有没有语法错误（这句话听起来很抽象，啥算语法错误？）识别语法错误，就像a=+c其实本来应该是a=b+c，b没有写，对于词法分析过程只认定出是两个连续的算符。对于加号的语法是左右都要有变量，这就是语法错误。另一个作用是识别语法单位，。举个例子：A=B+C*60;是一个赋值语句，可以构建以下语法分析树，说明这是一个正确的赋值语句：

在这里插入图片描述使用语法分析树的好处有什么呢？
好处在于能够表示出语句的层次结构，同时也可以用于辅助对语句的翻译。
从下往上看，经历的算符分别是*到+再到赋值符=。这正好符合我们运算过程中对于优先级的体现（想想在运算中是不是先乘除，再加减，最后把结果赋值给左边）。

对于词法分析和语法分析的总结：词法分析是一种线性分析，语法分析是一种层次结构分析。

3）语义分析与中间代码产生器

语义分析在语法分析之后，所以能到语义分析说明程序中已不存在语法错误。还用之前的a=b+c举例。对于+语义来说，要求左右两个操作数的类型应当相同。对其的检测就属于语义分析的部分。还有一些与具体语言相关的，典型情况包括：变量在使用前先进行声明、每个表达式都有合适的类型、函数的调用和函数的定义相关。（参考博客：https://blog.csdn.net/hit_shaoqi/article/details/83120448link，该博客中列举很多语义分析的错误例子）

中间代码生成的步骤要先理解什么是中间代码？中间代码就是用简单表达式表示你要进行的操作，举个例子就明白：
对于A = B+C60;这个表达式生成的中间代码如下：
temp1 = C60
temp2 = B+temp1
A = temp2

对中间代码常用四元式表示，四元式的结构如下：

在这里插入图片描述
所以对于上面的中间代码转换为四元式如下：

4）优化

优化的意思很明显，就是对代码进行调整使其运行时效率更高（体现在时间/空间上）。优化主要有三个方面：公共子表达式的提取，循环优化（主要优化对象），删除无用代码。

下面对三种优化分别举例：

公共子表达式的提取优化：
优化前
A = B + C;
…
D = B + C;
优化后
T = B + C;
A = T;
…
D = T;

循环优化：
优化前
for k=1 to 100
M=I+10k;
N=J+10k;
优化后
M=I;
N=J;
For k=1 to 100
M=M+10;
N=N+10;

从上面可以看出，循环优化的主要思想是把乘除法优化为加减法。（我们都知道乘除运算所用时间远大于加减法）。

删除无用代码：
无用代码就是对程序的结果没有影响的代码。主要可分为两部分

1. 复制传播
如果存在语句y=x，并且下面有许多语句在使用y。由于x,y在数值上相等，所以可利用x代替所有的y。这样就可以减少y=x这条语句。这种思想就叫做复制传播。

2. 无用代码（死code）
在程序编写过程中，可能出现对一个变量赋值，但后面并没有使用该变量，就认为该赋值无效，将其删除。

5）目标代码生成：

目标代码生成的过程非常复杂，就是把优化好的中间代码转换成指定的低级语言代码（汇编语言或者机器语言等等）。比如上面所举例子最终转换的汇编代码如下图：
在这里插入图片描述
从以上五个步骤可以看出一个明显的分界线，就是第三步中语义分析和中间代码生成之间。在中间代码生成之前，都没有对代码的任何翻译，所做的只是分析，故又称为分析部分。语义分析之后都是对代码的翻译调整，故又称为综合部分。

二、有关编译程序的几个名词解释，包括：表格管理、出错处理、遍、编译前端/后端

表格管理：

在编译程序中的表格主要的指的是符号表。符号表内存储的内容就是标识符（变量）的各种信息。例如：变量类型，存储位置等等。而对符号表的维护是贯彻在整个阶段的。（即每个阶段对符号表都会增添或删改）

出错处理：

在编写程序过程中难免出错，所以对于错误的处理就至关重要。出错可分为两大类：语法错误和语义错误。对于错误处理分几个层次，由坏到好分别为：检测到错误并暂停报错、检测到错误提示报错信息并继续执行程序以发现更多的错误、检测到错误并由对应的办法对错误进行处理校正。

遍（趟）：

平时总说一遍，两遍。但这里的“遍”定义为对源程序或源程序的中间结果从头到尾扫描一次并作有关的加工处理，生成新的中间结果或目标程序。一遍即可以对一个阶段而言（比如把词法分析单独作为一遍），也可以包括多个阶段（比如把词法分析、语法分析、语义分析和中间代码产生和为一遍）。

遍的作用是什么？
“遍”可以使编译程序结构更清晰，每一遍可以集中处理关键问题

编译前端/后端：

在概念上一个编译程序可划分为编译前端和编译后端。

编译前端主要由与源语言有关但与目标机无关的那部分组成的。这些部分通常包括词法分析，语法分析，语义分析与中间代码生成。

编译后端主要由与目标机有关的那部分组成的。这些部分通常包括优化和目标代码生成。

那为什么需要划分编译前端和后端呢？

从上面的概念可以看出，中间代码处于编译前端和编译后端的过渡位置。做这样一个图：
在这里插入图片描述
从这个图看出，高级语言变成中间代码这部分叫前端。前端可以由不同的部分引起。同样也可以产生不同的后端。这样不同的前端可以对应相同的后端，相同的前端可以对应不同的后端。就可以很好的体现代码的移植性。对于移植性的介绍会在后面说明。

在这里解释下为啥会有机器A,机器B的区分。在不同机器上的架构是不同的，据两个方面的例子。一方面是手机和pc机（一大一小，实现方式肯定不同），另一方面是指令集体系结构的不同，像CISC和RISC的实现结果肯定也不相同。

三、编译程序的生成、自展和移植

编译程序的生成有三大组成部分：源语言、编译程序、目标语言。编译程序的作用就是把源语言变成目标语言。更为具体：如果想让编译程序在目标机上运行，那么编译程序的编写语言需要是目标语言。（是不是很绕？这语言，那语言的）。为了更方便的说明，做了图形的规定（还是拿图说话！）取名为T形图：
在这里插入图片描述 (s代表源语言，T代表目标语言，I代表编译程序)

编译程序的自展

给定一个目标：在机器A（目标机）上，用语言A（编译程序实现语言），构造高级语言L（源语言）的编译程序。T形图表示为：

在这里插入图片描述
Step1:可以考虑使用L的子集S，在机器A上用语言A构造S的编译程序。T形图如下：

Step2:再在机器A上，用语言S构造L的编译程序。T形图如下：

在这里插入图片描述
再将两者结合，step1中s可编译成A，step2中可以利用S对L进行编译并在A机器上执行。我们所希望的是L以A的机器语言在A机器上运行，由step1可将S转换成A机器代码，所以L语言就可以用A的机器代码在A的机器上运行（是不是很绕？你如果第一次学那肯定是一脸懵的）我们用图说话：
在这里插入图片描述
写完以上过程，我有个疑问：为什么需要s是L的子集？上网找到一种说法发现可以接受，也更为贴切于自展的名字。（下图中的L1就是L的子集，从子集出发才能够慢慢扩展为L）

在这里插入图片描述
（节选于博客：https://blog.csdn.net/NameOfBlog/article/details/82857644link

编译程序的移植：

什么叫编译程序的移植呢？就是在A机器上已有的高级语言L编写一个在B机器上运行的高级语言L的编译程序。（简单来说就是L目前已经能使用A机器语言在机器A上运行，想要L能使用B机器语言在机器B上运行）T形图如下:
在这里插入图片描述
过程简记为一次编程两次编译

一次编程：使用L语言编写能够让L语言产生B机器代码的编译程序R

第一次编译：把R在A机器代码下编译使其变为A机器代码的语言，记为编译程序I，作用是把L编译成B

第二次编译：用编译程序I对R进行编译，成功完成L使用B机器语言完成的汇编程序在机器B上运行。

就单单这三段话就能让人找不着北!!!我们还是看图说话：
在这里插入图片描述
文字配图，事半功倍：

第一次编程，我们用L语言实现了编译程序R。注意R的本质是L语言，只不过功能是把L翻译成B。既然是L语言，通过已知L->A，我们可以把L语言变成A语言。这里的变成只是实现方式的改变，并没有改变原有的功能，还是一次编程的图，作用还是变成B语言，区别在于原来是用L语言实现的，现在用了A语言。也可以这样理解：

原来是L1-(L2)->B,又因为L2-(A)->A1。于是L1-(A1)->B。由一次编程知L通过R可变成B，现在只要R变成B就可以了。R的本质是L，第一次编译实现了L变成B，利用第一次的编译程序就可以把L变成B。这样R就变成了B就实现L-(B)->B。

刚学了绪论，对于编译原理的各个部分了解还过于粗浅。用了将近5000字才完成这篇文章。随着后面的学习，会更深层次的剖析每一个部分的。继续加油哈！

致谢：感谢编译原理课程谢老师对文章的耐心修改，同样感谢网上各位博主的优秀博文，为我不懂的地方提供解决办法。

因作者水平有限，如有错误之处，请在下方评论区指正，谢谢！

收起

展开全文

编译原理实验：词法分析

万次阅读 多人点赞 2018-09-29 21:17:16

编译原理实验：词法分析1. 实验题目：词法分析实验目的实验内容实验要求输入输出2. 设计思想3.算法流程4. 源程序5. 调试数据 1. 实验题目：词法分析实验目的根据PL/0语言的文法规范，编写PL/0语言的词法分析...


编译原理实验：词法分析
1. 实验题目：词法分析
实验目的
实验内容
实验要求
输入输出
2. 设计思想
3.算法流程
4. 源程序
5. 调试数据

1. 实验题目：词法分析
实验目的

根据PL/0语言的文法规范，编写PL/0语言的词法分析程序；或者调研词法分析程序的自动生成工具LEX或FLEX，设计并实现一个能够输出单词序列的词法分析器。
通过设计调试词法分析程序，实现从源程序中分出各种单词的方法；加深对课堂教学的理解；提高词法分析方法的实践能力。
掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的法。
掌握词法分析的实现方法。上机调试编出的词法分析程序。

实验内容
 已给PL/0语言文法，输出单词符号（关键字、专用符号以及其它标记）。
实验要求

把词法分析器设计成一个独立一遍的过程。
词法分析器的输出形式采用二元式序列，即：(单词种类,单词的值)

输入输出
输入：

  const a=10;

  var b,c;

  begin

  read(b);

  c:=a+b;

  write( c);

  end.

输出：

  (constsym, const)

  (ident , a)

  (eql, =)

  (number, 10)

  (semicolon, ; )

  (varsym, var)

  (ident,b)

  (comma, ,)

  (ident, c)

  (semicolon, ; )

  (beginsym, begin)

  (readsym, read )

  (lparen,( )

  (ident, b)

  (rparen, ))

  (semicolon, ; )

  (ident, c)

  (becomes, := )

  (ident,  a)

  (plus,  +)

  (ident,b )

  (semicolon, ; )

  (writesym,write)

  (lparen, ( )

  (ident, c)

  (rparen,) )

  (endsym, end )

  (period, .)
2. 设计思想
基本字：




单词（编码）
正规式r




begin(beginsym)
begin


call(callsym)
call


const(constsym)
const


do(dosys)
do


end(endsym)
end


if(ifsym)
if


odd(oddsym)
odd


procedure(proceduresym)
procedure


read(readsym)
read


var(varsym)
var


while(whilesym)
while


write(writesym)
write


then(thensym)
then


标识符：




单词（编码）
正规式r




<标识符>(ident)
（字母)(字母 |数字)*


常数：




单词（编码）
正规式r




<常数>(ident)
（数字)(数字)*


运算符：




单词（编码）
正规式r




+(plus)
+


-(minus)
-


*(times)
*


/(slash)
/


=(eql)
=


<>(neq)
<>


<(lss)
<


<=(leq)
<=


>(gtr)
>


>=(geq)
>=


:=(becomes)
:=


界符：




单词（编码）
正规式r




(  (lparen)
(


)  (rparen)
)


,  (comma)
,


;  (semicolon)
;


.  (period)
.


3.算法流程


词法分析程序打开源文件，读取文件内容，直至遇上文件结束符，然后读取结束。
接下来就要对源文件从头到尾进行扫描了，从头开始扫描，这个时候扫描程序首先要询问当前的字符是不是空格，若是空格，则继续扫描下一个字符，直至不是空格。然后询问这个字符是不是字母，若是则进行标识符和保留字的识别；若这个字符为数字，则进行数字的判断。否则，依次对这个字符可能的情况进行判断（界符和运算符），若将所有可能都走了一遍还是没有知道它是谁，则认定为错误符号，输出该无法识别error，程序结束。每次成功识别了一个单词后，单词都会存在word1[]数组中，然后字符指针往后移，进行下一个单词的识别。
主控程序需要负责对每次识别的种别码进行判断，对于不同的单词种别做出不同的反应，直至文件结束。
本次实验我采用了map这个STL关联容器，主要是考虑到词法分析中的数据映射的关系，因此采用这种结构。map提供一对一的数据处理能力，其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值。这个容器是非常方便使用的，对于查找可以直接使用迭代器进行，利用find（）函数，若一直到末尾都未找到，则是不能识别或为标识符。

4. 源程序
#include<bits/stdc++.h>
using namespace std;
map<string,string> word;//应用map数据结构形成一个string->string的对应
std::map<string,string>::iterator it;//用来遍历整个对应关系的迭代器
void map_init(){//对应关系进行初始化
    word["begin"]="beginsym";
    word["call"]="callsym";
    word["const"]="constsym";
    word["do"]="dosym";
    word["end"]="endsym";
    word["if"]="ifsym";
    word["odd"]="oddsym";
    word["procedure"]="proceduresym";
    word["read"]="readsym";
    word["then"]="thensym";
    word["var"]="varsym";
    word["while"]="whilesym";
    word["write"]="writesym";
    word["+"]="plus";
    word["-"]="minus";
    word["*"]="times";
    word["/"]="slash";
    word["="]="eql";
    word["<>"]="neq";
    word["<"]="lss";
    word["<="]="leq";
    word[">"]="gtr";
    word[">="]="geq";
    word[":="]="becomes";
    word["("]="lparen";
    word[")"]="rparen";
    word[","]="comma";
    word[";"]="semicolon";
    word["."]="period";
}
int main(){
    map_init();//初始化
    char ch;
    char a;
    string word1;//string变量识别单词
    string str;//string变量进行字符识别
    ifstream infile("F:\\编译原理\\第一次实验\\analysis.txt");//文件输入流
    ofstream outfile("F:\\编译原理\\第一次实验\\result.txt");//文件输出流
    ostringstream buf;
    while(buf&&infile.get(ch)) buf.put(ch);//将文件中的字符读出来
    str= buf.str();//将得到的字符储存到string类型变量中
    int csize=str.length();
    for(int i=0;i<csize;i++){//对整个字符串进行遍历
        while(str[i]==' '||str[i]=='\n') i++;//若最开始为空格或换行符，则将指针的位置往后移
        if(isalpha(str[i])){//对标识符和基本字进行识别,调用库函数isalpha()
            word1=str[i++];
            while(isalpha(str[i])||isdigit(str[i])){
                word1+=str[i++];
            }
            it=word.find(word1);
            if(it!=word.end()){//判断是不是基本字，若为基本字则进行输出
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }
            else{//否则直接输出
                cout<<"(ident"<<","<<word1<<")"<<endl;
            }
            i--;
        }
        else if(isdigit(str[i])){//判断是不是常数，调用库函数isdigit()
            word1=str[i++];
            while(isdigit(str[i])){
                word1+=str[i++];
            }
            if(isalpha(str[i])){
                cout<<"error!"<<endl;
                break;
            }
            else{
                cout<<"(number"<<","<<word1<<")"<<endl;
            }
            i--;
        }else if(str[i]=='<'){//对<,<=分别进行判断
            word1=str[i++];
            if(str[i]=='>'){
                word1+=str[i];
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }else if(str[i]=='='){
                word1+=str[i];
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }else if(str[i]!=' '||!isdigit(str[i])||!isalpha(str[i])){
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }else{
                cout<<"error!"<<endl;
                break;
            }
            i--;
        }else if(str[i]=='>'){//对>,>=分别进行判断
            word1=str[i++];
            if(str[i]=='='){
                word1+=str[i];
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }else if(str[i]!=' '||!isdigit(str[i])||!isalpha(str[i])){
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }else{
                cout<<"error!"<<endl;
                break;
            }
            i--;
        }else if(str[i]==':'){//对:=进行判断
            word1=str[i++];
            if(str[i]=='='){
                word1+=str[i];
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }else{
                cout<<"error!"<<endl;
                break;
            }
            i--;
        }else{//对其他的基本字依次进行判断
            word1=str[i];
            it=word.find(word1);
            if(it!=word.end()){
                cout<<"("<<word[word1]<<","<<word1<<")"<<endl;
            }else{
                cout<<"error!"<<endl;
                break;
            }
        }
    }
    infile.close();
    return 0;
}

5. 调试数据
待输入的文件流：



输出数据：





说明：如上实验仅符合当时实验要求的相关条件，其他的需求略微进行更改就行，思想是一样的，还是很简单的。输入输出自己按自己需求更改即可。

单词（编码）	正规式r
begin(beginsym)	begin
call(callsym)	call
const(constsym)	const
do(dosys)	do
end(endsym)	end
if(ifsym)	if
odd(oddsym)	odd
procedure(proceduresym)	procedure
read(readsym)	read
var(varsym)	var
while(whilesym)	while
write(writesym)	write
then(thensym)	then

单词（编码）	正规式r
<标识符>(ident)	（字母)(字母 \|数字)*

单词（编码）	正规式r
<常数>(ident)	（数字)(数字)*

单词（编码）	正规式r
+(plus)	+
-(minus)	-
*(times)	*
/(slash)	/
=(eql)	=
<>(neq)	<>
<(lss)	<
<=(leq)	<=
>(gtr)	>
>=(geq)	>=
:=(becomes)	:=

单词（编码）	正规式r
( (lparen)	(
) (rparen)	)
, (comma)	,
; (semicolon)	;
. (period)	.

收起

展开全文

编译原理龙书第四章部分习题（编译原理作业三）
千次阅读 2019-11-28 17:21:40
编译原理作业3 所有题目均为自己所写，觉得有用可以点个赞哟:-) 答案仅供参考，若有问题欢迎评论区讨论~ 文章目录编译原理作业34.2.14.2.24.2.34.2.54.4.14.4.44.6.54.6.64.7.24.7.5 4.2.1 考虑上下文无关...
收起
语法分析
编译原理及交叉编译
2018-04-20 12:51:17
转载： https://blog.csdn.net/testmyieda22/article/details/51444804编译原理及交叉编译编译原理gcc/g++在执行编译的时候，只要分四个阶段：1、预处理阶段，完成宏定义和include文件展开等工作;不生成文件 [预...
收起
编译原理总结
2018-06-11 08:53:39
编译原理是计算机专业的一门重要课程，主要介绍在编译程序构造的一般原理和方法，其中有， 编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法...
收起
【编译原理】引论
千次阅读 2020-02-18 20:59:54
文章目录编译原理引论（一）认识编译程序（二）编译过程概述1、阶段划分2、编译程序的结构3、编译程序的生成 编译原理引论（一）认识编译程序什么是编译程序？这要从翻译程序、解释程序以及编译程序的联系与区别...
收起
编译器
编译原理概述
2016-11-09 20:21:31
编译原理的应用准备系统地整理学习编译原理的相关知识。虽然这部分知识很多时候非常抽象，却能够很高的提高程序员内在的修养。如果每一种程序语言是一套招式，那么编译原理就是内功。不管程序语言如何变，都摆脱...
收起
开发工具编程语言
Cmake编译原理
千次阅读 2019-06-02 17:17:26
CMake编译原理 CMake是一种跨平台编译工具，比make更为高级，使用起来要方便得多。CMake主要是编写CMakeLists.txt文件，然后用cmake命令将CMakeLists.txt文件转化为make所需要的makefile文件，最后用make命令...
收起
编译原理：总结
万次阅读 多人点赞 2019-01-08 09:34:59
编译器概述编译器的核心功能编译器的核心功能是把源代码翻译成目标代码：翻译！！！目标代码！！！理解源代码：词法分析、语法...转化为等价的目标代码：中间代码生成、目标代码生成 ...语法分析器：单词流-&am
收起
了解编译原理
2019-10-09 02:36:27
了解编译原理 1）简述编译程序与翻译程序、汇编程序的联系与区别。编译程序就是将源代码文件以字符流的形式进行处理，进行词法和语法的分析，然后通过汇编器将源代码指令转变成汇编指令（由编译器将c...
收起
编译原理：了解编译原理
千次阅读 2019-09-25 11:59:06
1）简述编译程序与翻译程序、汇编程序的联系与区别。个人理解：编译程序（为高级服务）是将高级语言书写的源程序翻译成与之等价的低级语言的目标程序。　翻译程序是指把高级语言源程序翻译成机器语言源程序...
收起
编译原理书籍推荐
千次阅读 2018-09-28 13:44:20
大学课程为什么要开设编译原理呢？这门课程关注的是编译器方面的产生原理和技术问题，似乎和计算机的基础领域不沾边，可是编译原理却一直作为大学本科的必修课程，同时也成为了研究生入学考试的必考内容。编译原理及...
收起
编译原理序列
千次阅读 2013-09-11 00:01:50
表达式翻译器-1-编译原理 词法分析器-2-编译原理 递归下降法的语法分析器-3-编译原理 递归下降法的语法分析器-3.1-编译原理 用Yacc实现语法分析器-4-编译原理 中间代码生成器-5-编译原理
收起

编译原理

文章目录

一、绪论

什么是编译

计算机程序设计语言及编译

编译器在语言处理系统中的位置

编译系统的结构

词法分析概述

词法分析/扫描(Scanning)

语法分析概述

语义分析概述

中间代码生成及编译器后端概述

常用的中间表示形式

三地址指令的表示

目标代码生成器

代码优化

二、语言及其文法

基本概念

字母表 (Alphabet)

字母表上的运算

串 (String)

串上的运算——连接

串上的运算——幂

文法的定义

文法的形式化定义

符号约定

语言的定义

推导 (Derivations)和归约(Reductions)

句型和句子

语言的形式化定义

语言上的运算

文法的分类

Chomsky 文法分类体系

CFG的分析树

CFG 的分析树

分析树是推导的图形化表示

(句型的)短语

二义性文法 (Ambiguous Grammar)

二义性文法的判定

三、词法分析

正则表达式

正则表达式的定义

正则语言

正则文法与正则表达式等价

正则定义(Regular Definition)

有穷自动机 ( Finite Automata，FA )

FA模型

FA的表示

FA定义(接收)的语言

最长子串匹配原则 (Longest String Matching Principle)

有穷自动机的分类

确定的FA (Deterministic finite automata, DFA)

非确定的FA (Nondeterministic finite automata, NFA)

DFA和NFA的等价性

从正则表达式到有穷自动机

从NFA到DFA的转换

子集构造法(subset construction)

计算 ε-closure(T)

确定性有限自动机的简化

DFA化简

多余状态（无用状态）

两个状态S和T等价的条件

DFA的状态最少化算法

四、语法分析

自顶向下的分析 (Top-Down Parsing)

最左推导 (Left-most Derivation)

最右推导 (Right-most Derivation)

递归下降分析 (Recursive-Descent Parsing)

预测分析 (Predictive Parsing)

文法转换

左递归

消除直接左递归

消除间接左递归

提取左公因子 (Left Factoring )

LL(1) 文法

S _ 文 法-简单的确定性文法

非终结符的后继符号集

产生式的可选集

q_ 文法

串首终结符集

S _ 文法-简单的确定性文法

FIRST集和 FOLLOW集的计算