编译原理

文章目录

  • 绪论
  • 第1章 绪论
    • 1.什么是编译
    • 2.编译系统的结构
    • 3.词法分析
  • 第2章 语言及其文法
    • 字母表 ∑ \sum
    • 概念
      • 终结符
      • 非终结符
      • 产生式
    • 文法
      • Chomsky文法分类体系
        • 0型文法 (Type-0 Grammar)
        • 1型文法(Type-1 Grammar)
        • 2型文法(Type-2 Grammar)
        • 3型文法(Type-3 Grammar)
  • 第3章 词法分析
    • 正则表达式
    • 有穷自动机
      • 确定的有穷自动机 DFA
      • 不确定的有穷自动机 NFA
      • 从正则表达式到有穷自动机
    • 恐慌模式
  • 第4章 语法分析
    • 自顶向下的语法分析
    • 自底向上的语法分析
      • FIRST 串首终结符集
      • FOLLOW
      • SELECT 可选集
    • LL(1)文法
    • LR
      • LR(0) 分析法
      • SLR(1) 分析法
      • LR(1) 分析法
      • LALR 分析法
  • 第5章 语法制导翻译
    • 语法制导翻译的概念
    • 5.1 语法制导定义 SDD
    • 5.2 SDD的求值顺序
    • 5.3 语法制导翻译 SDT
  • 第6章 中间代码生成
    • 6.1 类型表达式
    • 6.2 声明语句的翻译
    • 6.3 简单赋值语句的翻译
      • 赋值语句的SDT
    • 6.4 数组引用的翻译
    • 6.5 控制流语句SDT
      • 控制流语句的SDT
  • 第7章 运行存储分配
    • 7.1 运行存储分配概述
    • 7.2 静态存储分配
      • 1.顺序分配法
      • 2.层次分配法
    • 7.3 栈式存储分配
      • 活动树
    • 7.4 调用序列和返回序列
    • 7.5 非局部数据的访问
      • 访问链的建立
    • 7.6 堆存储分配
    • 7.7 符号表、符号表的建立
  • 第8章 代码优化 (降低资源消耗,加快运行速度)
    • 8.1 流图
      • 基本块
        • 基本块划分算法
      • 流图 (Flow Graphs)
    • 8.2 常用的代码优化方法
    • 8.3 基本块的优化
      • 基本块的DAG图
    • 8.4 数据流分析
      • 语句的数据流模式
      • 基本块的数据流模式
    • 8.5 到达定值
    • 8.6 活跃变量分析
    • 8.7 可用表达式分析
    • 8.8 支配结点和回边
      • 支配结点
      • 回边
    • 8.9 代码移动
  • 第9章 代码生成
    • 9.1 代码生成器的主要任务
    • 9.2 窥孔优化

绪论

推荐视频:哈工大 - 陈鄞
推荐用书:龙书,豆瓣评分9.1


几乎每本编译原理的教材都是分成词法分析,语法分析(LL算法,递归下降算法,LR算法),语义分析,运行时环境,中间代码,代码生成,代码优化这些部分

不过编译原理在讲解词法分析的时候,重点把正则表达式自动机原理加了进来,然后以一种十分标准的方式来讲解词法分析程序的产生。这样的做法道理很明显,就是要让词法分析从程序上升到理论的地步。

语法分析部分就比较麻烦一点了。现在一般有两种语法分析算法,LL自顶向下算法和LR自底向上算法。LL算法还好说,到了LR算法的时候,困难就来了。很多自学编译原理的都是遇到LR算法的理解成问题后就放弃了自学。其实这些东西都是只要大家理解就可以了,又不是像词法分析那样非得自己写出来才算真正的会。像LR算法的语法分析器,一般都是用工具Yacc来生成,实践中完全没有比较自己来实现。对于LL算法中特殊的递归下降算法,因为其实践十分简单,那么就应该要求每个学生都能自己写。当然,现在也有不少好的LL算法的语法分析器,不过要是换在非C平台,比如Java,Delphi,你不能运用YACC工具了,那么你就只有自己来写语法分析器。

《龙书》是计算机相关书籍。本书深入讨论了编译器设计的重要主题,包括词法分析、语法分析、语法制导分析、类型检查、运行环境、中间代码生成、代码生成、代码优化等,并在最后两章中讨论了实现编译器的一些编程问题和几个编译器实例,每章都提供了大量的练习和参考文献。本书从介绍编译的原理性概念开始,然后通过构建一个简单的编译器来逐一解释这些概念。
在这里插入图片描述

参考链接:https://blog.csdn.net/kojhliang/article/details/82881788



第1章 绪论

1.什么是编译

在这里插入图片描述

2.编译系统的结构

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

3.词法分析

1.词法单元(token)

token <种别码,属性值>

在这里插入图片描述



第2章 语言及其文法

字母表 ∑ \sum

∑ + \sum^+ + 正闭包 :长度为n的字符串集合
∑ ∗ \sum^* 克林闭包: 任意长度的字符串集合。即是,正闭包加 空串 ε ε ε

ε ε ε (epsilon) /ˈepsɪlɑːn/

概念

终结符

  • 小写字母:a、b、c
  • 数字:0、1…9
  • +*
  • (
  • id、if
    在这里插入图片描述
    终结符 (token / terminal symbol)
    在这里插入图片描述

非终结符

  • 开始符号S
  • 大写字母:A B C E T F
    在这里插入图片描述

产生式

在这里插入图片描述


在这里插入图片描述


文法

Chomsky文法分类体系

0型文法 (Type-0 Grammar)

无限制文法 / 短语结构文法


1型文法(Type-1 Grammar)

上下文有关文法 (CSG)


2型文法(Type-2 Grammar)

上下文无关文法 (CFG)


3型文法(Type-3 Grammar)

正则文法 (RG)
①右线性文法
②左线性文法


在这里插入图片描述



第3章 词法分析

正则表达式

正则表达式 (Regular Expression,RE)


有穷自动机

1.有穷自动机 (Finite Automat,FA)

2.正则文法 ⇔ ⇔ 正则表达式RE ⇔ ⇔ 有穷自动机FA


确定的有穷自动机 DFA

1.确定的FA(Deterministic finite automata, DFA)
2.DFA更易于计算机计算


不确定的有穷自动机 NFA

1.不确定的FA(Nondeterministic finite automata, NFA)
2.NFA更易于人类阅读


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

RE->NFA->DFA
在这里插入图片描述


恐慌模式

在这里插入图片描述



第4章 语法分析

自顶向下的语法分析

1.最左推导:每次推导都选最左边的

2.最右推导:每次推导都选最右边的

3.自顶向下的缺陷:

②不能解决左递归问题
在这里插入图片描述

4.消除直接左递归
在这里插入图片描述


自底向上的语法分析

FIRST 串首终结符集

α的串首终结符集 FIRST(α):可以从α推导出的所有串首终结符构成的集合。

S->aB(" -> "表示定义为)


FOLLOW

后继符号集 FOLLOW
在这里插入图片描述


SELECT 可选集

产生式的可选集
在这里插入图片描述

LL(1)文法

在这里插入图片描述

LL(1)文法:第一个L表示从左到右扫描输入串,第二个L表示生成的是最左推导


LR

在这里插入图片描述

LR(0) 分析法

LR(0)项目:右部有圆点的产生式
移进项目:点在右部的最左侧
待约项目:点在右部的中间
归约项目:点在右部的最右侧
后继项目:两个产生式,圆点的位置只相差一个符号

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述


项目集闭包:点右边是非终结符,就会出现等价的状态。所有等价状态是一个项目集闭包,对应自动机的一个状态。

等价
在这里插入图片描述


SLR(1) 分析法

LR(0)加强


LR(1) 分析法

SLR加强


LALR 分析法

削弱,目的是减少状态数。代价是推迟了错误的发现。
在这里插入图片描述



第5章 语法制导翻译

语法制导翻译的概念

语法制导翻译使用CFG()来引导对语言的翻译,是一种面向文法的翻译技术。
在这里插入图片描述


5.1 语法制导定义 SDD

注释分析树
属性文法


5.2 SDD的求值顺序

S-属性定义
L-属性定义:S-属性定义一定是L-属性定义


5.3 语法制导翻译 SDT

1.定义:语法制导翻译 SDT(Syntax-directed translation)。是在产生式右部中嵌入了程序片段(称为语义动作)的CFG
基于属性文法的处理过程,对单词符号串进行语法分析,构造语法分析树,然后根据需要构造属性依赖图,遍历语法树并在语法树的各结点处按语义规则进行计算。

语法制导翻译是指一种源语言代码的翻译完全由语法分析器驱动的编译器的实现方法。


第6章 中间代码生成

6.1 类型表达式

类型也有结构,类型的结构用类型表达式来表示。
基本类型是类型表达式。类型名也是类型表达式。将类型构造符(type constructor)作用于类型表达式可以构成新的类型表达式。

6.2 声明语句的翻译

lexeme 语义
在这里插入图片描述
[num] C₁:数组下标表达式序列
在这里插入图片描述
↑T₁:指针类型(↑:指针关键字


6.3 简单赋值语句的翻译

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


赋值语句的SDT

gen(code):生成三地址指令code
在这里插入图片描述


归约状态

6.4 数组引用的翻译


6.5 控制流语句SDT

在这里插入图片描述
S.next:是一个地址,该地址中存放了紧跟在S代码之后的指令(S的后继指令)的标号

控制流语句的SDT

newlabel( ): 生成一个用于存放标号的新的临时变量L,返回变量地址

label(L): 将下一条三地址指令的标号赋给L
在这里插入图片描述


call:过程调用关键字
param指令


第7章 运行存储分配

7.1 运行存储分配概述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述


7.2 静态存储分配

1.顺序分配法

在这里插入图片描述

2.层次分配法

在这里插入图片描述


7.3 栈式存储分配

在这里插入图片描述

活动树

在这里插入图片描述
在这里插入图片描述


7.4 调用序列和返回序列


7.5 非局部数据的访问

访问链 (Access Links)静态作用域原则:第i层可以调用i+1层(外层调用内层)
支持过程(函数)嵌套的语言:Pascal
不支持过程嵌套的语言:C语言、C++

访问链的建立

①外层调用内层
在这里插入图片描述
②本层调用本层:访问链相同,直接复制
在这里插入图片描述
③内层调用外层
在这里插入图片描述


7.6 堆存储分配


7.7 符号表、符号表的建立


第8章 代码优化 (降低资源消耗,加快运行速度)

代码优化:对代码进行等价的程序变换,使之运行的更快,或占用的空间更少,降低时间、空间复杂度。

8.1 流图

基本块

在这里插入图片描述

基本块划分算法

判断首指令:
①一个指令序列的第一条(三地址)指令是首指令
②跳转指令goto的目标指令是首指令
③跳转指令goto的下一条指令是首指令

在这里插入图片描述


流图 (Flow Graphs)

在这里插入图片描述
B→C:
①顺序执行,不存在无条件跳转指令
②跳转指令
在这里插入图片描述


8.2 常用的代码优化方法

1.代码优化的分类
机器无关优化 (针对中间代码)
机器相关优化 (针对目标代码)
局部代码优化 (单个基本块范围内的优化)
全局代码优化 (面向多个基本块的优化)


2.常用代码优化方法
删除公共子表达式
同一个基本块内:局部公共子表达式
不在同一个基本块内:全局公共子表达式
将局部公共子表达式和全局公共子表达式进行删除。
在这里插入图片描述

删除无用代码
在这里插入图片描述

常量合并
在这里插入图片描述

代码移动
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

强度削弱 (Strength Reduction)
用较快的操作代替较慢的操作(运算代价高的指令代替运算代价低的指令),如用加代替乘,用乘代替除

删除归纳变量
归纳变量:对于一个变量x ,如果存在一个正的或负的常数c,使得每次x被赋值时它的值总增加c ,那么x就称为归纳变量(Induction Variable)
在这里插入图片描述


8.3 基本块的优化

有向无环图 (Directed Acyclic Graph,DAG)
定值变量表:为什么变量定值,就把该变量添加到该结点的定值变量表中

基本块的DAG图

1.检测公共子表达式
基本块的DAG图,可以帮助我们自动检测出基本块中的局部公共子表达式。

2.删除无用代码
活跃变量:其值在之后可能被使用
无用代码:其值在之后不会被使用


8.4 数据流分析

语句的数据流模式

IN[s]:语句s之前的数据流值
OUT[S]:语句s之后的数据流值
fs:语句s的传递函数

在这里插入图片描述
在这里插入图片描述

基本块的数据流模式

在这里插入图片描述
在这里插入图片描述


8.5 到达定值

在这里插入图片描述

用途:检测循环计算


在这里插入图片描述
①IN[B]i+1:根据流图,知道IN[B]i+1= OUT[B]i
②OUT[B]i+1:可根据gen{di}使得IN[B]i+1第i位置1;根据kill{di}使得IN[B]i+1第i位置0


8.6 活跃变量分析

引用-定值链(Use-Definition Chains),简称ud链,是一个列表,对于变量的每一 次引
用,到达该引用的所有定值都在该列表中

use:引用
def:定值

定值-引用链(Definition-Use Chains),简称du链,设变量x有一个定值d,该定值所有能够到达的引用u的集合称为x在d处的定值-引用链,简称du链


8.7 可用表达式分析

1.定义
在这里插入图片描述

2.作用
①消除全局公共子表达式
②进行复制传播


e_genB
e_killB


8.8 支配结点和回边

支配结点

①入口结点:支配流图中的所有结点(支配结点树的根结点)
②每个结点都至少支配它自己(支配结点树的叶结点)
在这里插入图片描述
支配结点树(Dominator Tree)
每个结点只支配它和它的后代
在这里插入图片描述
直接支配结点
在这里插入图片描述


回边

在这里插入图片描述
有指向自己的支配结点的边,称为回边。


8.9 代码移动

1.代码移动、前置首结点
在这里插入图片描述



第9章 代码生成

9.1 代码生成器的主要任务


9.2 窥孔优化

在这里插入图片描述
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/732.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

JAVA开发与JAVA(一文学会使用ElasticSearch)

在web网站的架设中特别是数据量大的网站或者APP小程序需要搜索或者全文检索的场景&#xff0c;几乎都需要借助ElasticSearch来作为全文检索引擎&#xff0c;以提高网站的搜索效率和性能。 这一节&#xff0c;我们通过一篇文章介绍&#xff0c;使大家通过一文就学会使用Elastic…

python 函数:定义、调用、参数、返回值、嵌套、变量的作用域(局部变量、全局变量)、global、匿名函数lambda

函数可以将我们的程序分解成最小的模块&#xff0c;避免重复使用。函数内部的代码&#xff0c;只有被调用的时候才会执行。 函数的定义&#xff08;def就是define&#xff09;&#xff1a; 格式&#xff1a;def 函数名(): 函数封装的代码 函数的调用&#xff1a; 格式&…

大学生考研的意义?

当我拿起笔头&#xff0c;准备写这个话题时&#xff0c;心里是非常难受的&#xff0c;因为看到太多的学生在最好的年华&#xff0c;在自由的大学本应该开拓知识&#xff0c;提升认知&#xff0c;动手实践&#xff0c;不断尝试和试错&#xff0c;不断历练自己跳出学生思维圈&…

15000 字的 SQL 语句大全 第一部分

一、基础 1、说明&#xff1a;创建数据库CREATE DATABASE database-name 2、说明&#xff1a;删除数据库drop database dbname 3、说明&#xff1a;备份sql server--- 创建 备份数据的 device USE master EXEC sp_addumpdevice disk, testBack, c:\mssql7backup\MyNwind_1.dat …

数据结构--二叉树

目录1.树概念及结构1.1数的概念1.2数的表示2.二叉树概念及结构2.1二叉树的概念2.2数据结构中的二叉树2.3特殊的二叉树2.4二叉树的存储结构2.4.1顺序存储2.4.2链式存储2.5二叉树的性质3.堆的概念及结构3.1堆的实现3.1.1堆的创建3.1.2堆的插入3.1.3堆顶的删除3.1.4堆的代码实现3.…

蓝桥杯刷题冲刺 | 倒计时26天

作者&#xff1a;指针不指南吗 专栏&#xff1a;蓝桥杯倒计时冲刺 &#x1f43e;马上就要蓝桥杯了&#xff0c;最后的这几天尤为重要&#xff0c;不可懈怠哦&#x1f43e; 文章目录1.路径2.特别数的和3.MP3储存4.求和1.路径 题目 链接&#xff1a; 路径 - 蓝桥云课 (lanqiao.cn…

算法学习之二分查找

&#x1f383;个人主页&#x1f383;&#xff1a;勇敢的小牛儿 &#x1f9e8;推荐专栏&#x1f9e8;&#xff1a;C语言知识点 ✨座右铭✨&#xff1a;敢于尝试才有机会 ⚠️今日鸡汤⚠️&#xff1a;Is the true wisdom fortitude ambition. -- Napoleon 真正的才智是刚毅的志向…

【云原生·Docker】常用命令

目录 &#x1f341;1、管理命令 &#x1f341;2、帮助命令 &#x1f341;3、镜像命令 &#x1f341;4、容器命令 &#x1f342;4.1.查看容器 &#x1f342;4.2.创建容器 &#x1f342;4.3.删除容器 &#x1f342;4.4.拷贝文件 &#x1f342;4.5.查看容器IP &#x1f341;5、部署…

LSTM从入门到精通(形象的图解,详细的代码和注释,完美的数学推导过程)

先附上这篇文章的一个思维导图什么是RNN按照八股文来说&#xff1a;RNN实际上就是一个带有记忆的时间序列的预测模型RNN的细胞结构图如下&#xff1a;softmax激活函数只是我举的一个例子&#xff0c;实际上得到y<t>也可以通过其他的激活函数得到其中a<t-1>代表t-1时…

C语言/动态通讯录

本文使用了malloc、realloc、calloc等和内存开辟有关的函数。 文章目录 前言 二、头文件 三、主界面 四、通讯录功能函数 1.全代码 2.增加联系人 3.删除联系人 4.查找联系人 5.修改联系人 6.展示联系人 7.清空联系人 8.退出通讯录 总结 前言 为了使用通讯录时&#xff0c;可以…

Opencv项目实战:22 物体颜色识别并框选

目录 0、项目介绍 1、效果展示 2、项目搭建 3、项目代码展示与部分讲解 Color_trackbar.py bgr_detector.py test.py 4、项目资源 5、项目总结 0、项目介绍 本次项目要完成的是对物体颜色的识别并框选&#xff0c;有如下功能&#xff1a; &#xff08;1&#xff09;…

线程池的使用:如何写出高效的多线程程序?

目录1.线程池的使用2.编写高效的多线程程序Java提供了Executor框架来支持线程池的实现&#xff0c;通过Executor框架&#xff0c;可以快速地创建和管理线程池&#xff0c;从而更加方便地编写多线程程序。 1.线程池的使用 在使用线程池时&#xff0c;需要注意以下几点&#xff…

GDAL python教程基础篇(7)OGR空间计算

1.空间计算 地理数据处理&#xff08;geoprocessing&#xff09;计算函数&#xff1a; 多边形&#xff08;Polygon&#xff09;&#xff1a; 1、交&#xff1a;poly3.Intersection(poly2) 2、并&#xff1a;poly3.Union(poly2) 3、差&#xff1a;poly3.Difference(poly2) 4、补…

python打包成apk界面设计,python打包成安装文件

大家好&#xff0c;给大家分享一下如何将python程序打包成apk文件&#xff0c;很多人还不知道这一点。下面详细解释一下。现在让我们来看看&#xff01; 1、如何用python制作十分秒加减的apk 如何用python制作十分秒加减的apk&#xff1f;用法:. apk包放入apk文件目录,然后输入…

Linux基础命令大全(下)

♥️作者&#xff1a;小刘在C站 ♥️个人主页&#xff1a;小刘主页 ♥️每天分享云计算网络运维课堂笔记&#xff0c;努力不一定有收获&#xff0c;但一定会有收获加油&#xff01;一起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的绽放&#xff0…

走进哈希心房

目录 哈希的概念 哈希函数 哈希冲突和解决方法 闭散列 插入 查找 删除 开散列 插入 查找 删除 哈希表&#xff08;开散列&#xff09;整体代码 位图 位图模拟实现思路分析&#xff1a; 位图应用 布隆过滤器 本文介绍unordered系列的关联式容器&#xff0c;unor…

安卓手机也可以使用新必应NewBing

没有魔法安卓手机也可以使用新必应NewBing 目前知道的是安卓手机 安卓手机先安装一个猴狐浏览器 打开手机自带浏览器&#xff0c;搜索关键词&#xff1a;猴狐浏览器&#xff0c;找到官网 也可以直接复制这个网址 狐猴浏览器 lemurbrowser CoolAPK 我的手机是荣耀安卓手机…

【正点原子FPGA连载】 第三十三章基于lwip的tftp server实验 摘自【正点原子】DFZU2EG_4EV MPSoC之嵌入式Vitis开发指南

第三十三章基于lwip的tftp server实验 文件传输是网络环境中的一项基本应用&#xff0c;其作用是将一台电子设备中的文件传输到另一台可能相距很远的电子设备中。TFTP作为TCP/IP协议族中的一个用来在客户机与服务器之间进行文件传输的协议&#xff0c;常用于无盘工作站、路由器…

「ML 实践篇」分类系统:图片数字识别

目的&#xff1a;使用 MNIST 数据集&#xff0c;建立数字图像识别模型&#xff0c;识别任意图像中的数字&#xff1b; 文章目录1. 数据准备&#xff08;MNIST&#xff09;2. 二元分类器&#xff08;SGD&#xff09;3. 性能测试1. 交叉验证2. 混淆矩阵3. 查准率与查全率4. P-R 曲…

2023年腾讯云服务器配置价格表(轻量服务器、CVM云服务器、GPU云服务器)

目前腾讯云服务器分为轻量应用服务器、云服务器云服务器云服务器CVM和GPU云服务器&#xff0c;首先介绍一下这三种服务。 1、腾讯云云服务器&#xff08;Cloud Virtual Machine&#xff0c;CVM&#xff09;提供安全可靠的弹性计算服务。 您可以实时扩展或缩减计算资源&#xff…
最新文章