Lang

编译原理一

编译原理

编译

什么是编译原理

编译原理是介绍如何将高级程序设计语言转换成计算机硬件能识别的机器语言，以便计算机进行处理

编译与计算机程序设计语言的关系

日常开发过程中我们使用的语言一般都是高级语法比如 JAVA、Python、PHP、JavaScript等等，但是计算机只能识别0、1这样的机器码。那么这些高级语言是如何翻译成机器能识别的0、1等呢？这就用的了编译，首先我们通过下面这幅图看下编译与计算机程序语言的关系，有助于我们直观的了解编译的作用。

注意：每种机器都对应一种汇编语言

程序设计语言的转换方式

翻译：指把某种语言的源程序，在不改变语义的条件下，转换成另一种语言程序即目标语言程序

真正的实现有两种方式，编译及解释

  • 编译：专指由高级语言转换为低级语言，整个程序翻译。常用的例如： c、c++，delphi,Fortran、Pascal、Ada
  • 解释：接受某种高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这个句子的执行结果，然后再接受下一个语句。类似口译，一句一句进行解释。常用的例如：python 解释以源程序作为输入，不产生目标程序，一边解释一边执行。优点：直观易懂，结构简单，易于实现人机对话。缺点：效率低(不产生目标程序，每次都需要重新执行，速度慢)

编译的转换过程

  • 编译->运行
  • 编译->汇编->运行

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

了解了编译与程序设计语言的关系，那么我们接下来再来看下编译器在语言处理系统中所处位置，如下图

编译系统的结构

那么机器是如何把高级语言翻译为汇编语言程序或机器语言程序的呢？

我们先来看下人工进行英文翻译的例子，这里引用的哈工大编译原理中的图示

图中的中间表示很重要主要起到了一个桥梁的作用，比如图中的中间表示可以使用各种语言表示。

根据上图可以看出要进行语义分析首先需要划分句子成分，那么我们是如何划分句子成分的呢？

  1. 首先通过词法分析分析出句子中各个单词的词性或者词类
  2. 接下来通过语法分析识别出句子中的各类短语从而获得句子的结构
  3. 然后进行语义分析根据句子结构分析出句子中各个短语在句子中充当什么成分，从而确定各个名词性成分同各个核心谓语动词间的关系语意关系
  4. 最后给出中间表示形式 实际上编译器在工作的时候也是经过了以上几个步骤，我们成为阶段(计算机的逻辑组织方式，在实现过程中多个阶段可能会被组合在一起实现)，可以分为两大部分：分析源语言、生成目标代码,在编译器中他们分别对应编译器的前端和后端两个部分。编译器的结构如下图 了解了编译器的结构，让我们从编译器的前端开始讲起，看看词法分析、语法分析、语义分析等各个阶段都做了什么。

词法分析(扫描)

编译的第一个阶段，从左到右逐行扫描源程序的字符，识别出各个单词(是高级语言中有是在意义的最小语法单元，由字符构成)，确定单词的类型。将识别的单词转换成统一的机内表示即词法单元 简称Token

token:<种别码，属性值>token: <种别码，属性值>

单词类型 种别 种别码
1 关键字 program、if、else、then… 一词一码
2 标识符 变量名、数组名、记录名、过程名… 多词一码
3 常量 整型、浮点型、字符型、布尔型… 一型一码
4 运算符 算术（+ - * / ++ –）关系（> < == != >= <=） 逻辑（& | ~） 一词一码或一型一码
5 界限符 ; ( ) = { } 一词一码

名字解释

  • 一词一码：例如，关键字是唯一的且事先可以确定，为每个关键字分配一个种别码

  • 多词一码：例如，所有的标示符统一作为一类单词分配同一个种别码，为了区分不同的标示符，用token的第二个分量“属性值”存放不同标示符具体的字面值

  • 一型一码：不同类型的常量他们的构成方式是不同的，例如，我们为每种类型的常量分配一个种别码，为了区分同一类型下的不同常量，也用token的第二个分量“属性值”存放每个常量具体的值 下面图中是一个词法分析后得到的token序列的例子

    描述词法规则的有效工具是正规式和有限自动机。正规式:用来确定单词是否和程序语言规范。有限自动机：通过有限自动机进行单词和正规式比较

语法分析(parsing)

语法分析的定义

语法分析器从词法分析器输出的token序列中识别出各类短语，并构造语法分析树(parse tree),语法分析树描述了句子的语法结构

语法分析的规则

即语法规则又称文法，规定了单词如何构成短语、句子、过程和程序。

语法规则的标示如下，含义是A定义为B或者C

BNF:A::=B∣CBNF:A::=B|C

<句子>::=<主><谓><宾><句子>::=<主><谓><宾>

<主>::=<定><名><主>::=<定><名>

来看下赋值语句的语法规则：

  • A::=V=E
  • E::=T|E+T
  • T::=F|T*F
  • F::=V|(E)|C
  • V::=标示符
  • C::=常数 即由标示符或者常数的表达式进行加减乘除运算

语法分析的方法

推导(derive)和归约(reduce)

  • 推导：最左推导、最右推导
  • 归约：最右归约、最左归约,推导的逆过程就是归约

最右推导、最左归约：

最左推导、最右归约：

语法树

计算机通过语法树来进行分析，即语法分析过程也可以用一颗倒着的树来标示，这颗树叫语法树。正确的语法树叶子节点数必须是表达式的符号，例如

赋值语句的分析树：

变量声明语句的分析树：

首先看下变量声明语句的文法(文法是由一系列规则构成的)：

<D> -> <T> <IDS>;
<T> -> int | real | char | bool
<IDS> -> id | <IDS>, id

语义分析

语义的任务主要有两个

一. 收集标识符的属性信息

二. 语义检查

  1. 变量或过程未经声明就使用
  2. 变量或过程名重复声明
  3. 运算分量类型不匹配
  4. 操作符与操作数之间的类型不匹配
    • 数组下标不是整数
    • 对非数组变量使用数组访问操作符
    • 对非过程名使用过程调用操作符
    • 过程调用的**参数类型或数目不匹配 **
    • 函数返回类型有误

中间代码生成

通常和语义分析一起实现。对语法分析识别出的各类语法范畴，分析他的含义，进行初步翻译，产生介于源代码和目标代码质检的一种代码

常用的中间代码表示形式

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

三地址指令的表示：

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

下面图中展示了一个中间代码生成的例子

代码优化

对前面生成的中间代码进行加工变换，以便在最后极端产生更为高效的目标代码 ，需要遵循等价变换的原则，优化的方面包括：公共子表达式的提取、合并已知量、删除无用语句、循环优化。

目标代码生成

把经过优化的中间代码转化成特定机器上的低级语言

目标代码的形式：

    • 绝对指令代码：可立即执行的目标代码
  • 汇编指令代码：汇编语言程序，需要经过汇编陈旭汇编后才能运行
  • 可重定位指令代码：先将各目标模块连接起来，确定变量、常数在主存中的位置，装入主存后才能成为可以运行的绝对指令代码

其他

出错处理

如果源程序有错误，编译程序应设法发现错误并报告给用户。由专门的出错处理程序来完成。 错误类型：

  • 语法错误：在词法分析和语法分析阶段检测出来
  • 语义错误：一般在语义分析阶段检测
  • 逻辑错误：不可检测，比如死循环，一般不处理因为没办法在编译阶段检测出来

遍

指对源程序或源程序的中间结果从头到尾扫描一次，并做有关的加工处理，生成新的中间结果或目标代码。遍与阶段的含义毫无关系

多遍扫描： 优点：节省内存空间，提高目标代码的质量，使编译的逻辑结构清晰。缺点：编译时间长。在内存许可的情况下还是遍数尽可能少较好

编译程序生成

  1. 直接用机器语言编写编译程序
  2. 用汇编语言编写编译程序，编译程序核心部分常用汇编语言编写
  3. 用高级语言编写编译程序，这也是普遍采用的方法
  4. 自编译
  5. 编译工具 LEX（语法分析）与YACC(用于自动生成LALR分析表)
  6. 移植(同种语言的编译程序在不同类型的机器之 间移植) 在某机器上为某种语言构造编译程序要掌握以下三方面:
  • 源语言
  • 目标语言
  • 编译方法
Licensed under CC BY-NC-SA 4.0
© 2020 - 2024 Xiaobin's Notes
Built with Hugo
主题 Stack 由 Jimmy 设计