编译原理 | 绪论、语言及其文法

第一章 绪论

1.1 什么是编译

编译的主要任务：翻译 和 优化

优化目标：代码规模小、执行速度快

编译：将高级语言翻译成汇编语言或机器语言的过程

1.2 编译系统的结构

1.3 编译器的生成

T形图的自展与移植：

第二章 语言及其文法

2.1 基本概念

语言的形式化定义：设$\Sigma$ 是一个字母表，$\forall L\subseteq {\Sigma }^{\ast }$，$L$ 称为字母表 $\Sigma$ 上的一个语言（Language），$\forall x\in L$，$x$ 叫做 $L$ 的一个句子。

• 串：有穷符号（symbol） 序列
  • 串的连接：xy
  • 串的n次幂：将n个s连接起来
• 字母表：有穷符号集合
  • 字母表的乘积：笛卡尔积
  • 字母表的n次幂：长度为n的符号串构成的集合
  • 字母表的正闭包：长度正数的符号串构成的集合
  • 字母表的克林闭包：任意符号串（长度可以为零）构成的集合

2.2 文法的定义

语言的有穷描述，$G=(V_T,V_N,P,S)$

• $V_T$ ：终结符集合 ( 字母表 )，终结符（terminal symbol）是文法所定义的语言的基本符号，有时也称为token
• $V_N$：非终结符集合，非终结符(nonterminal) 是用来表示语法成分的符号，有时也称为“语法变量”
• $P$ ：产生式集合。产生式( production)描述了将终结符和非终结符组合成串的方法。
  • 产生式的一般形式： $\alpha \to \beta$ ， 读作：$\alpha$定义为$\beta$
    
  • 产生式( production)描述了将终结符和非终结符组合成串的方法。
• $S$ ：开始符号。$S\in V_N$。开始符号(start symbol)表示的是该文法中最大的语法成分

2.3 语言的定义

推导和规约

句型和句子

文法生成的语言

语言上的计算

2.4 文法的分类

Chomsky 文法分类体系

• 0型文法 (Type-0 Grammar)
  

• 1型文法 (Type-1 Grammar)
  

• 2型文法 (Type-2 Grammar)
  

• 3型文法 (Type-3 Grammar)
  

2.5 CFG的分析树

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

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

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

• 改造文法：描述算术运算的无二义性文法的产生式
• 语法分析时加入消除二义性的规则

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