编译原理学习笔记——第一讲 引论

发布时间:2024-02-14 13:30

编译原理学习笔记——第一讲 引论

  • 1. 什么是编译程序?
    • 1.1 Compiler(编译程序)
    • 1.2 Interpreter(解释程序)
  • 2. 为何学习编译原理?
    • 2.1 Computational Thinking(计算思维)
      • 2.1.1 Abstraction(抽象)
      • 2.1.2 Automation(自动化)
      • 2.1.3 Decomposition(分解)
      • 2.1.4 Recursion(递归)
      • 2.1.5 Tradeoff(权衡,折衷)
    • 2.2 学习编译原理的意义
    • 2.3 编译原理和方法的应用
  • 3. 编译过程
    • 3.1 词法分析
    • 3.2 语法分析
    • 3.3 中间代码产生
    • 3.4 优化
    • 3.5 目标代码产生
  • 4. 编译程序的结构
    • 4.1 编译程序总框
    • 4.2 遍(pass)
    • 4.4 编译前端与后端
  • 5. 编译程序的生成

1. 什么是编译程序?

1.1 Compiler(编译程序)

  • 定义:把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序
  • 编译程序的进一步分类:
    诊断编译程序(Diagnostic Compiler)
    优化编译程序(Optimizing Compiler)
    交叉编译程序(Cross Compiler)
    可变目标编译程序(Retargetable Compiler)
  • 运行编译程序的机器:宿主机
    运行目标语言程序的机器:目标机
    编译原理学习笔记——第一讲 引论_第1张图片

1.2 Interpreter(解释程序)

  • 定义:把源语言写的源程序作为输入,但不产生目标程序,而是边解释边执行源程序
    编译原理学习笔记——第一讲 引论_第2张图片

2. 为何学习编译原理?

2.1 Computational Thinking(计算思维)

  • 计算思维:是运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为,它包括了一系列广泛的计算机科学的思维方法。
  • 包括一系列广泛的计算机科学的思维方法:抽象、自动化、问题分解、递归、权衡、保护、冗余、容错、纠错和恢复、利用启发式推理来寻求解答、在不确定情况下的规划、学习和调度。

2.1.1 Abstraction(抽象)

  • 图灵机就是一个抽象的机器。
  • 图灵机有一条无限长的纸带,纸带分成了一个一个的小方格,每个方格有不同的颜色。
  • 有一个机器头在纸带上移来移去。机器头有一组内部状态,还有一些固定的程序。
  • 在每个时刻,机器头都要从当前纸带上读入一个方格信息,然后结合自己的内部状态查找程序表,根据程序输出信息到纸带方格上,并转换自己的内部状态,然后进行移动。
    编译原理学习笔记——第一讲 引论_第3张图片
  • 邱奇-图灵论题(The Church-Turing thesis):所有计算或算法都可以由一台图灵机来执行。
  • 编译原理中的"抽象":
    有限自动机;
    形式文法。

2.1.2 Automation(自动化)

  • 将抽象思维的结果在计算机上实现,是一个将计算思维成果物化的过程,也是将理论成果应用于技术的实践。
  • 自动化的思维方法不仅体现在编译程序本身的工作机制上,更体现在了编译程序的生成工具的研究和设计上。
  • 编译原理中的"自动化“:
    有限自动机;
    预测分析程序;
    算符优先分析;
    LR分析。

2.1.3 Decomposition(分解)

  • 将大规模的复杂问题分解成若干个较小规模的、更简单的问题加以解决。
  • 编译原理中的"问题分解":
    为什么编译程序引入中间语言?
    为什么编译分成多个阶段?
    为什么分析过程分成多遍?

2.1.4 Recursion(递归)

  • 问题的解决依赖于类似问题的解决,只不过后者的复杂程度或规模较原来的问题更小。
  • 一旦将问题的复杂程度和规模化简到足够小时,问题的解法其实非常简单。
  • 编译原理中的"递归":
    递归下降分析;
    基于树遍历的属性计算;
    语法制导翻译。

2.1.5 Tradeoff(权衡,折衷)

  • 理论研究重在探寻问题求解的方法,对于理论成果的研究运用又需要在能力和运用中作出权衡。
  • 编译原理中的"权衡":
    用上下文无关文法来描述和处理高级程序设计语言;
    优化措施的选择。

2.2 学习编译原理的意义

  1. 学习编译程序构造原理,技术:
    提高对计算机系统总体认识、感悟计算思维、更好地理解“计算”
  2. 更好地理解高级语言
  3. 运用编译原理和方法构造实用工具:
    用“计算”的眼光看世界、用计算解决实际问题

2.3 编译原理和方法的应用

  1. Html/XML分析
  2. 语言处理工具(错误拼写检测、自动翻译、搜索引擎)
  • 在计算机技术中也应用了语言的翻译或变换
    1.用户接口:Shell命令解释器, …
    2.查询语言:SQL,XQuery, …
    3.网络协议:HTTP, SOAP, …

3. 编译过程

  • 编译程序是怎样把高级语言(如C++)翻译成低级语言(如机器指令)的?

编译原理学习笔记——第一讲 引论_第4张图片

  • 编译程序工作的五个阶段:
    词法分析、语法分析、中间代码产生、优化、目标代码产生。

3.1 词法分析

  • 任务: 输入源程序,对构成源程序的字符串进行扫描和分解,识别出单词符号
  • 依循的原则:构词规则
  • 描述工具:有限自动机

3.2 语法分析

  • 任务:在词法分析的基础上,根据语法规则把单词符号串分解成各类语法单位(语法范畴)
  • 依循的原则:语法规则
  • 描述工具:上下文无关文法
    编译原理学习笔记——第一讲 引论_第5张图片

3.3 中间代码产生

  • 任务:对各类语法单位按语言的语义进行初步翻译
  • 依循的原则:语义规则
  • 描述工具:属性文法
  • 中间代码:三元式,四元式,树,…

Z:=X + 0.618 * Y 翻译成四元式为
编译原理学习笔记——第一讲 引论_第6张图片

3.4 优化

  • 任务:对前阶段产生的中间代码进行加工变换,以期在最后阶段产生更高效的目标代码
  • 依循的原则:程序的等价变换规则

3.5 目标代码产生

  • 任务: 把中间代码变换成特定机器上的目标代码
  • 依赖于硬件系统结构和机器指令的含义
  • 目标代码三种形式:
    汇编指令代码: 需要进行汇编
    绝对指令代码: 可直接运行
    可重新定位指令代码: 需要连接(重定位)

例: b=a+2
编译原理学习笔记——第一讲 引论_第7张图片

4. 编译程序的结构

4.1 编译程序总框

编译原理学习笔记——第一讲 引论_第8张图片

  • 语法错误:
    源程序中不符合语法(或词法)规则的错误
    非法字符、括号不匹配、缺少 ;、…
  • 语义错误:
    源程序中不符合语义规则的错误
    说明错误、作用域错误、类型不一致、…

4.2 遍(pass)

  • 所谓"遍", 就是对源程序或源程序的中间表示从头到尾扫描一次。
  • 一遍可以由若干段组成
  • 一个阶段也可以分若干遍来完成

4.4 编译前端与后端

在这里插入图片描述

  • 编译前端:
    与源语言有关,如词法分析,语法分析,语义分析与
    中间代码产生,与机器无关的优化
  • 编译后端:
    与目标机有关,与目标机有关的优化,目标代码产生
  • 带来的好处:
    程序逻辑结构清晰
    优化更充分,有利于移植
    编译原理学习笔记——第一讲 引论_第9张图片

5. 编译程序的生成

以汇编语言和机器语言为工具:

  • 优点: 可以针对具体的机器,充分发挥计算机的系统
    功能;生成的程序效率高
  • 缺点: 程序难读、难写、易出错、难维护、生产的效
    率低

高级语言书写

  • 程序易读、易理解、容易维护、生产的效率高
  • 利用已有的某种语言的编译程序实现另一语言的编译程序
    编译原理学习笔记——第一讲 引论_第10张图片
  • 把一种机器上的编译程序移植到另一种机器上编译原理学习笔记——第一讲 引论_第11张图片

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号