编译原理1——绪论&语言及其文法

第一章 绪论

语言及特点

• 高级语言：类似于数学定义或自然语言的简洁形式
  • 接近人类表达习惯
  • 不依赖于特定机器
  • 编写效率高
• 汇编语言：引入助记符
  • 依赖于特定机器，非计算机专业人员使用受限制
  • 编写效率比较低
• 机器语言：可以直接被计算机所理解
  • 难以记忆、编写、阅读
  • 容易写错

编译

​ 将高级语言（源语言）翻译成汇编语言或者机器语言（目标语言）的过程。

编译器所处位置

​ 源程序$\rightarrow$[预处理器]$\rightarrow$经过预处理的源程序$\rightarrow$[编译器]$\rightarrow$汇编语言程序$\rightarrow$[汇编器]$\rightarrow$可重定位的机器代码$\rightarrow$[链接器/加载器]$\rightarrow$目标机器代码

编译器的结构

• 分析部分/前端（与源语言相关）

  • 词法分析器：从左向右逐行扫描源程序的字符，识别出各个单词，确定单词的类型。
    • 将识别出的单词转换成统一的机内表示——词法单元（token）格式。\<种别码，属性值>

  • 语法分析器：从词法分析器输出的token序列中识别出各类短语，并构造语法分析树。

  • 语义分析器：

    • 收集标识符的属性信息（种属、类型、存储位置、长度、值、作用域、参数和返回值信息）
      • 符号表：用于存放标识符的属性信息的数据结构
    • 语义检查
      • 变量或过程未声明就使用
      • 变量或过程名重复声明
      • 运算分量类型不匹配
      • 操作符与操作数之间的类型不匹配
        • 数组下标不是整数
        • 对非数组变量使用数组访问操作符
        • 对非过程名使用过程调用操作符
        • 过程调用的参数类型或数目不匹配
        • 函数返回值类型有误
  • 中间代码生成器
    • 三地址码：由类似于汇编语言的指令序列，每个指令最多有三个操作数。
    • 语法结构树/语法树

• 机器无关代码优化器

• 综合部分/后端（与目标语言相关）

  • 目标代码生成器：以源程序的中间表示形式作为输入，把它映射到目标语言。
    • 为程序中使用的变量合理分配寄存器。
  • 机器相关代码优化器

代码优化：等价程序变换、运行更快、占用空间更少

第二章 语言及其文法

串

• 有穷符号序列
• 连接运算、幂运算

字母表

• 有穷符号集合
• 乘积运算、幂运算、正闭包、克林闭包

文法的形式化定义

• $G=(VT,VN,P,S)$
  • VT:终结符集合；VN：非终结符集合；P：产生式集合；S：文法开始符号
• 产生式简写：相同左部，右部竖线隔开，一个部分为一个候选式
• 约定：
  • 终结符：排在前面的小写字母、运算符、标点符号、粗体字符串
  • 非终结符：排在前面的大写字母、S、小写或斜体的名字、代表程序构造的大写字母（E：表达式、T：项、F：因子）
  • 字母表中排在后面的大写字母表示文法符号
  • 字母表中排在后面的小写字母表示终结符号串
  • 小写希腊字母表示文法符号串
  • 第一个产生式左部为开始符号

语言的定义

• 推导和归约

  • 直接推导：用产生式发右部替换左部

  • n步推导

  • 归约：自下而上——识别语言角度

    推导：自上而下——生成语言角度

• 句型和句子

  • 句型：既可以包含终结符，也可以包含非终结符、可以是空串
  • 句子：不包含非终结符的句型

• 语言的形式化定义：由文法G的开始符号S推导出的所有句子构成的集合成为文法G生成的语言，记为$L(G)$

文法的分类（Chomshy文法分类体系）

• 0型文法：无限制文法（UG）/短语结构文法（PSG）
  • $\forall\alpha\rightarrow\beta\in P,\alpha$中至少包含一个非终结符。
• 1型文法：上下文有关文法（CSG）
  • $\forall\alpha\rightarrow\beta\in P,|\alpha|\leq|\beta|$
  • 不包含空产生式
• 2型文法：上下文无关文法（CFG）
  • $\forall\alpha\rightarrow\beta\in P,\alpha\in VN$

• 3型文法：正则文法（RG）

  • 右线性文法：$A\rightarrow wB$ 或 $A\rightarrow w$
  • 左线性文法：$A\rightarrow Bw$ 或 $A\rightarrow w$

• 四种文法逐级限制、逐级包含。

CFG的的分析树

• 根结点、内部结点、叶结点
• 树的产出或边缘：从左到右排列叶结点得到的符号串
• 分析树是推导的图形化表示
• 句型的短语：给定一个句型，其分析树中的每一颗子树的边缘称为该句型的一个短语。
  • 如果子树只有父子两代的结点，则这颗子树的边缘称为该句型的一个直接短语
  • 直接短语一定是某产生式的右部，但是产生式的右部不一定是给定句型的直接短语。
• 二义性文法
  • 如果一个文法可以为某个句子生成多颗分析树
  • 消歧规则
  • 二义性文法的判定：对于任意一个上下文无关文法，不存在一个算法判断它是无二义性的，但是可以给出是无二义性的充分条件