网络配置

修改配置文件/etc/sysconfig/network-scripts/ifcfg-xxx

Linux内存泄漏工具

简介

详细信息可以查阅官方网站。

Valgrind是一套Linux下，开放源代码（GPL V2）的仿真调试工具的集合。Valgrind由内核（core）以及基于内核的其他调试工具组成。内核类似于一个框架（framework），它模拟了一个CPU环境，并提供服务给其他工具；而其他工具则类似于插件 (plug-in)，利用内核提供的服务完成各种特定的内存调试任务。

安装

ubuntu20.04直接安装，版本为3.15.0

1

apt-get install valgrind

使用

准备程序

需要使用-g将调试信息编译到程序中，以便Memcheck工具输出准确行数。优化参数最好是使用-O0或-O1，使用-O2及以上等级或存在错误上报的可能。

Memcheck运行程序

若程序正常运行为

1

myprog arg1 arg2

则使用valgrind运行时

1

valgrind --leak-check=all myprog arg1 arg2

Memcheck工具是默认项。--leak-check选项指定检查项细节。

程序会比正常运行慢一些，并会占用更多的内存。

常见错误检测

• 内存未释放（definitely/indirectly/possibly lost）
• 内存越界访问（Invalid read/write）
• 内存释放后读写（Invalid read/write）
• 内存错误释放（Mismatched free() / delete / delete []）
• 内存重复释放（Invalid free() / delete / delete[] / realloc()）

流程介绍

基本原则

• 简单。不增加过多学习成本，开发测试快速迭代。

• 可追溯。每个现场环境运行的软件版本号都由主仓发布，主仓关键分支禁用代码强制提交。

简化流程

所有开发人员都从主仓的开发分支克隆(clone)代码。在本地修改代码，本地仓新增(add)提交。待所有代码调试完毕，准备推送(push)到主仓。在推送主仓前先获取(fetch)主仓最新提交记录。

完整流程

私有仓从主仓派生（fork），本地仓从私有仓克隆（clone）。

主仓所有开发人员只能发起合并请求（merge），禁止发起推送请求（push），经仓负责人检视后合入主仓。主仓只有开发（develop）分支接受私有仓代码合并请求，其他分支不接受私有仓代码合并请求。

版本管理

版本号规范

版本号基本结构：v主版本号.子版本号.修订版本号。版本号会以标签（TAG）的方式指向各分支的某次提交记录。

参考：产品中心发布的版本号命名规范

主版本号

1. 大的代码重构导致此版本号变更；
2. 主版本号变更可能导致向下兼容问题；

子版本号

1. 有大的功能变动；
2. 可能影响向下兼容，但是可以通过技术手段进行数据或者业务转换；

修订版本号

1. 修改程序内部 bug，程序功能无变化；
2. 绝对向下兼容；

分支策略

• develop（开发分支）：主仓默认分支，日常开发活跃分支，一般包含未经严格测试的提交记录。
• v主版本号.子版本号.x（发布分支）：是测试或现场环境运行的软件版本对应的代码。

以上两类分支会开启分支保护策略，禁止强制推送。

修订版本号为0的标签会指向开发分支和相应的发布分支，而修订版本号非0的标签只会指向相应的发布分支。

例如：版本号为v1.6.0的标签会同时指向开发分支和v1.6.x的发布分支。而版本号为v1.6.2的标签只会指向v1.6.x的发布分支。

提交记录

提交记录信息基本结构：提交类型[问题单号或任务编号]: 提交信息

提交类型

• feat（功能特性）：主要是核心代码新增或修改功能特性，包括性能优化和代码重构；
• fix（修复问题）：主要是修复核心代码中发现的问题；
• other（其他事务）：主要是新增或修改非核心代码，比如构建脚本、代码版本号、新增环境等等。

提交信息

• 提交信息尽量简短（100字以内）介绍本次提交的目的

• 提交信息尽量携带问题单号或任务编号

• 单次提交实现单个特性或修复单个问题

标准提交示例

1
2
3
4
5
6
7
8
9

# 功能特性提交记录
【推荐】feat1549: 增加登录功能，并对用户权限进行校验
【不推荐】feat: 修改登录功能，忽略对管理员权限进行校验
# 修复问题提交记录
【推荐】fix8317: 修复校验用户权限时，并发访问公共队列造成崩溃的问题
【不推荐】fix: 修复校验管理员权限时，跳过校验普通用户权限的问题
# 其他事务提交记录
【推荐】other1349: 部署脚本打包增加检索服务
【不推荐】other: 部署版本信息修改为v1.8.5

提交策略

• 功能特性和其他事务的提交都只需要合并到开发分支即可；

• 修复问题的提交除了合并到对应的发布分支上，还需要调整后合并到开发分支中；

测试发布流程

对于分支的提测，若没有相应的发布分支，项目负责人需要在新建

对于发布分支的提测，项目负责人只需在发布分支上打v主版本号.子版本号.x的标签和记录Changelog。

常用命令

以下命令格式常用命令格式，详细可选参数可以查询Git手册获取。

约定

<XX>必填参数

[XX]可选参数

REPO_NAMEGit仓库名称，示例：origin

REPOGit仓库地址，示例：http://ubuntu.alfdxl.top/gitea-admin/git-template.git

BRANCH分支名称，示例：feat_adminuser

TAG标签名称，示例：v1.2.6

MESSAGE提交消息，示例：feat698: 新增创建管理员用户和查询用户信息功能

ID提交记录，示例：3110aa8502d24022cd08ba37d5dacd5160709214

PATH文件夹路径，示例：template

HEADGit保留字段，指向分支当前提交记录

clone

克隆一个Git仓库到本地，可以查看或修改此项目。基本格式：git clone <REPO> [PATH]

Git仓库地址支持HTTP和SSH协议。HTTP协议不会保存用户信息，在拷贝过程中也不会验证用户权限。但在推送本地信息时会要求用户进行验证，常常用于代码查看活动。SSH协议本身已经保存用户信息，推送本地信息时不会要求用户输入信息，常常用于代码开发活动。SSH协议需要提前配置，Gitlab的相关配置可以参考文章。

使用示例：

1
2
3
4
5
6
7
8
9

# 克隆代码到本地
$ git clone http://ubuntu.alfdxl.top/gitea-admin/git-template.git template
Cloning into 'template'...
remote: Enumerating objects: 61, done.
remote: Counting objects: 100% (61/61), done.
remote: Compressing objects: 100% (40/40), done.
remote: Total 61 (delta 9), reused 0 (delta 0), pack-reused 0
Receiving objects: 100% (61/61), 5.07 KiB | 2.53 MiB/s, done.
Resolving deltas: 100% (9/9), done.

remote

管理远程Git仓库，每个仓库都有名称，默认克隆的仓库名称都为origin。

查看远程仓详情：git remote -v

新增远程仓：git remote add <REPO_NAME> <REPO>

删除远程仓：git remote rm <REPO_NAME>

使用示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 查看远程仓
$ git remote -v
origin  http://ubuntu.alfdxl.top/gitea-admin/git-template.git (fetch)
origin  http://ubuntu.alfdxl.top/gitea-admin/git-template.git (push)

# 新增远程仓
$ git remote add ssh_remote ssh://git@ubuntu.alfdxl.top:222/gitea-admin/git-template.git
$ git remote -v                                                                         
origin  http://ubuntu.alfdxl.top/gitea-admin/git-template.git (fetch)
origin  http://ubuntu.alfdxl.top/gitea-admin/git-template.git (push)
ssh_remote      ssh://git@ubuntu.alfdxl.top:222/gitea-admin/git-template.git (fetch)
ssh_remote      ssh://git@ubuntu.alfdxl.top:222/gitea-admin/git-template.git (push)

# 删除远程仓
$ git remote rm ssh_remote 
$ git remote -v           
origin  http://ubuntu.alfdxl.top/gitea-admin/git-template.git (fetch)
origin  http://ubuntu.alfdxl.top/gitea-admin/git-template.git (push)

checkout

分支切换和恢复工作区，基本格式：git checkout <BRANCH>

使用示例：

1
2
3
4
5
6
7
8
9

# 本地拉取远程指定分支代码
$ git checkout -b feat_adminuser origin/feat_adminuser
Branch 'feat_adminuser' set up to track remote branch 'feat_adminuser' from 'origin'.
Switched to a new branch 'feat_adminuser'

# 切换分支
$ git checkout master
Switched to branch 'master'
Your branch is up to date with 'origin/master'.

branch

代码分支管理。

查看所有分支：git branch -a

删除分支：git branch -d <BRANCH>

使用示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 查看所有分支
$ git branch -a
* feat_adminuser
  master
  remotes/origin/HEAD -> origin/master
  remotes/origin/feat_adminuser
  remotes/origin/feat_build
  remotes/origin/master

# 删除分支
$ git branch -d feat_adminuser
warning: deleting branch 'feat_adminuser' that has been merged to
         'refs/remotes/origin/feat_adminuser', but not yet merged to HEAD.
Deleted branch feat_adminuser (was 3110aa8).

log

查看提交记录。基本格式：git log

使用示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 查看提交记录
$ git log
commit 3110aa8502d24022cd08ba37d5dacd5160709214 (HEAD -> feat_adminuser, tag: v1.2.3, origin/feat_adminuser)
Author: 作者姓名 <作者邮箱>
Date:   Tue May 10 11:41:36 2022 +0800

    feat698: 新增创建管理员用户和查询用户信息功能；

commit 82f2ba7b82fa91335f3d226e3fee61cedea65945
Author: 作者姓名 <作者邮箱>
Date:   Mon May 9 16:33:14 2022 +0800

    fix696: 修复修改用户名都为常量的问题

commit bbb843b97d714df441275c488c8bd2f131efe42c (tag: v1.2.6, origin/master, origin/HEAD, master)
Author: zhangsan <zhangsan1598@gmail.com>
Date:   Mon May 9 16:09:27 2022 +0800

    feat1599: 新增修改用户名称的功能

commit 1ad9bce14ad8548c5b28bdd91398a3e4664909c5
Author: 作者姓名 <作者邮箱>
Date:   Mon May 9 14:59:13 2022 +0800

    feat1598: 新增创建用户的功能

commit 89b4f2cf3cd950686708d390126dec20da330257
Author: 作者姓名 <作者邮箱>
Date:   Mon May 9 14:50:36 2022 +0800

    other1598: 建立代码仓库

tag

标签管理。基本格式：git tag <TAG>

查看本地标签：git tag -l

新增本地标签：git tag <TAG>

删除本地标签：git tag -d <TAG>

使用示例：

1
2
3
4
5
6
7
8
9
10
11

# 查看本地标签
$ git tag -l
v1.2.3
v1.2.6

# 新增本地标签
$ git tag v1.2.3

# 删除本地标签
$ git tag -d v1.2.3
Deleted tag 'v1.2.3' (was 3110aa8)

add/rm

暂存区文件管理。暂存区的代码不会生成提交记录。

暂存区新增文件：git add <FILE>

暂存区删除文件：git rm <FILE>

使用示例：

1
2
3
4
5
6
7
8

# 暂存区新增文件
$ git add .
$ git add gw/*
$ git add gw/cmd/main.go

# 暂存区删除文件
$ git rm gw/internal/info/version.go 
rm 'gw/internal/info/version.go'

commit

将暂存区的文件提交到本地仓。基本格式：git commit -m <MESSAGE>

使用示例：

1
2
3
4
5

# 提交到本地仓
$ git commit -m "fix866: 修复版本不匹配引起服务崩溃问题"
[master 3d4bf3c] fix866: 修复版本不匹配引起服务崩溃问题
 3 files changed, 1 insertion(+), 6 deletions(-)
 delete mode 100644 gw/internal/info/version.go

status

工作区状态查询。基本格式：git status

使用示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# 无任何修改或提交的工作区状态查询
$ git status  
On branch master
Your branch is up to date with 'origin/master'.

nothing to commit, working tree clean

# 有修改为提交的工作区状态查询
$ git status                        
On branch master
Your branch is ahead of 'origin/master' by 2 commits.
  (use "git push" to publish your local commits)

Changes to be committed:
  (use "git restore --staged <file>..." to unstage)
        modified:   gw/cmd/main.go
        deleted:    gw/internal/info/version.go

Changes not staged for commit:
  (use "git add <file>..." to update what will be committed)
  (use "git restore <file>..." to discard changes in working directory)
        modified:   go.mod

Untracked files:
  (use "git add <file>..." to include in what will be committed)
        ReadMe.md

# 有提交未推送的工作区状态查询
$ git status
On branch master
Your branch is ahead of 'origin/master' by 3 commits.
  (use "git push" to publish your local commits)

nothing to commit, working tree clean

reset

重置工作区指向的提交，即可以回退版本也可以撤销回退。

强制重置工作区：git reset --hard <ID>

工作区回退N次提交：git reset --hard HEAD~<N>

撤销工作区提交：git reset --soft <ID>

工作区撤销N次提交：git reset --soft HEAD~<N>

使用示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 强制重置工作区
$ git reset --hard 82f2ba7b82fa91335f3d226e3fee61cedea65945
HEAD is now at 82f2ba7 fix696: 修复修改用户名都为常量的问题
$ git reset --hard v1.2.3                                  
HEAD is now at 3110aa8 feat698: 新增创建管理员用户和查询用户信息功能；
$ git reset --hard origin/master     
HEAD is now at bbb843b feat1599: 新增修改用户名称的功能

# 工作区回退2次提交
$ git reset --hard HEAD~2                                  
HEAD is now at 82f2ba7 fix696: 修复修改用户名都为常量的问题

# 撤销工作区提交
$ git reset --soft 82f2ba7b82fa91335f3d226e3fee61cedea65945

# 工作区撤销2次提交
$ git reset --soft HEAD~2

pull

获取远程仓最新提交记录并与本地记录进行合并。基本格式：git pull [REPO_NAME]

使用示例：

1
2
3
4
5
6
7
8
9
10

# 拉取代码
$ git pull       
remote: Enumerating objects: 9, done.
remote: Counting objects: 100% (9/9), done.
remote: Compressing objects: 100% (4/4), done.
remote: Total 5 (delta 1), reused 0 (delta 0), pack-reused 0
Unpacking objects: 100% (5/5), 435 bytes | 435.00 KiB/s, done.
From http://ubuntu.alfdxl.top/gitea-admin/git-template
   fbd7e0a..01df67e  feat_adminuser -> origin/feat_adminuser
Already up to date.

fetch

获取远程仓提交记录。基本格式：git fetch [REPO_NAME]

使用示例：

1
2
3
4
5
6
7
8
9
10
11
12

# 远程仓无变更
$ git fetch

# 远程仓有变更
$ git fetch
remote: Enumerating objects: 9, done.
remote: Counting objects: 100% (9/9), done.
remote: Compressing objects: 100% (4/4), done.
remote: Total 5 (delta 1), reused 0 (delta 0), pack-reused 0
Unpacking objects: 100% (5/5), 433 bytes | 433.00 KiB/s, done.
From http://ubuntu.alfdxl.top/gitea-admin/git-template
   3110aa8..fbd7e0a  feat_adminuser -> origin/feat_adminuser

rebase

对本地分支进行变基操作。即缓存所有本地提交，将本地的基底与远程仓合并，再依次提交缓存的本地提交。与pull操作最大的不同是rebase操作可以保持提交记录的清晰度，参考文章。基本格式：git rebase [REPO_NAME]

使用示例：

1
2
3
4
5
6
7
8
9
10
11
12

# 变基操作
$ git pull       
remote: Enumerating objects: 9, done.
remote: Counting objects: 100% (9/9), done.
remote: Compressing objects: 100% (4/4), done.
remote: Total 5 (delta 1), reused 0 (delta 0), pack-reused 0
Unpacking objects: 100% (5/5), 435 bytes | 435.00 KiB/s, done.
From http://ubuntu.alfdxl.top/gitea-admin/git-template
   fbd7e0a..01df67e  feat_adminuser -> origin/feat_adminuser
Already up to date.
$ git rebase
Successfully rebased and updated refs/heads/feat_adminuser.

push

推送本地记录到远程仓。

推送提交记录：git push [REPO] [BRANCH]

推送标签记录：git push --tags [REPO] [BRANCH]

使用示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 推送本地提交记录
$ git push                         
Enumerating objects: 9, done.
Counting objects: 100% (9/9), done.
Delta compression using up to 8 threads
Compressing objects: 100% (4/4), done.
Writing objects: 100% (5/5), 453 bytes | 453.00 KiB/s, done.
Total 5 (delta 1), reused 0 (delta 0), pack-reused 0
remote: 
remote: Create a new pull request for 'feat_adminuser':
remote:   http://ubuntu.alfdxl.top/gitea-admin/git-template/compare/master...feat_adminuser
remote: 
remote: . Processing 1 references
remote: Processed 1 references in total
To ssh://ubuntu.alfdxl.top:222/gitea-admin/git-template.git
   3110aa8..fbd7e0a  feat_adminuser -> feat_adminuser

# 推送标签记录
$ git push --tags 
Total 0 (delta 0), reused 0 (delta 0), pack-reused 0
remote: .. Processing 2 references
remote: Processed 2 references in total
To http://ubuntu.alfdxl.top/gitea-admin/git-template.git
 * [new tag]         v1.2.3 -> v1.2.3
 * [new tag]         v1.2.6 -> v1.2.6

配置

参考文章

配置用户名、邮箱

1
2

git config --global user.name "名字"
git config --global user.email "邮箱"

配置编辑器

1

git config --global core.editor vim

配置日志显示格式

1
2
3
4
5
6
7
8
9
10
11
12
13

# 隐藏Merge --no-merges
# 过滤作者 --author='你的名字！自己修改！'

git config --global alias.lm "log --no-merges --color --date=format:'%Y-%m-%d %H:%M:%S' --pretty=format:'%Cred%h%Creset -%C(yellow)%d%Cblue %s %Cgreen(%cd) %C(bold blue)<%an>%Creset' --abbrev-commit"
# 显示效果

git config --global alias.lms  "log --no-merges --color --stat --date=format:'%Y-%m-%d %H:%M:%S' --pretty=format:'%Cred%h%Creset -%C(yellow)%d%Cblue %s %Cgreen(%cd) %C(bold blue)<%an>%Creset' --abbrev-commit"

git config --global alias.ls "log --no-merges --color --graph --date=format:'%Y-%m-%d %H:%M:%S' --pretty=format:'%Cred%h%Creset -%C(yellow)%d%Cblue %s %Cgreen(%cd) %C(bold blue)<%an>%Creset' --abbrev-commit"

git config --global alias.lss "log --no-merges --color --stat --graph --date=format:'%Y-%m-%d %H:%M:%S' --pretty=format:'%Cred%h%Creset -%C(yellow)%d%Cblue %s %Cgreen(%cd) %C(bold blue)<%an>%Creset' --abbrev-commit"

git lm -n 5 | cat

git lm显示效果：

git lms显示效果：

git ls显示效果：

git lss显示效果：

网络配置

网络配置改用netplan，配置方式与以前版本不同。参考Canonical Netplan

其中enp0s3使用的是主机网络（用于主机中局域网络访问），enp0s8使用的是VirtualBox自带的NAT网络（用于访问互联网）。修改配置文件/etc/netplan/00-installer-config.yaml

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# This is the network config written by 'subiquity'
network:
  renderer: networkd # NetworkManager
  ethernets:
    enp0s3:
      dhcp4: no
      dhcp6: no
      addresses: [192.168.56.101/24]
      # gateway4: 192.168.56.1
      # optional: true
      # nameservers:
      #   addresses: [192.168.56.1,8.8.8.8]
      # routes:
      #   - to: default
      #   via: 192.168.56.1
      # routes:
      #   - to: 192.168.56.0/24
      #     via: 192.168.56.1
      #     table: 102
      # routing-policy:
      #   - from: 192.168.56.0/24
      #     table: 102
    enp0s8:
      dhcp4: yes
      dhcp6: no
      # nameservers:
        # addresses: [10.0.3.1,8.8.8.8]
  version: 2

1. 官方语言参考手册：Ada Standard, Rationale and other Documents (ada-europe.org)

2. 提供一个实现编译器简单思路：从零开始实现一个简单编译器 - 知乎 (zhihu.com)

3. 参考各类资料：Commercial software solutions for Ada, C and C++ | AdaCore，BNF表示的Ada-2012语法：Syntax Summary (adacore.com)

考虑到实现所有Ada语法非常多，可以考虑只实现部分。

简介

tokens => lexical analysis词法分析 grammar => syntactic analysis语法分析 typing rules => semantic analysis语义分析 evaluation rules => code generation and optimization代码生成和优化

Operational Semantics

与变量声明类似，这里声明的是运算值

示例说明

变量名和位置map

变量值存储

Cool对象表达方式

特殊场景

其他

Cool Semantics

复杂示例1

复杂示例2

通用表达

示例说明

if条件满足: while条件不满足： while条件满足： 有新申明的变量：

声明对象T通用语法

• 声明内存存放类对象T的所有属性
• 设置所有属性的默认值
• 对象属性初始化
• 返回新对象地址

对象默认值

对象属性初始化

示例说明

e0.f(e1,…,en)的通用语法

• 按照参数顺序e1,…,en处理
• 处理目标对象e0
• 声明X为动态类目标对象
• 获取X的f(有n个参数)定义
• 创建n个新局部变量和一个环境
• 初始化局部变量
• 将self指向目标对象

通用表达式

示例说明

Intermediate Code中间码

简介

在源码与目标码之间的语言； 提供一种抽象的中间层； - 比源码拥有更多细节； - 比目标码少细节； 中间语言等同高级汇编； 每个指令采用三操作数方式；

特点

与汇编代码生成器类似； 可以使用任意个中间寄存器存储结果；

表达式

igen(e,t)表示：在寄存器t中，计算表达式e的值得代码

示例说明

简介

编译流程

L.A. Parsing Semantic A. Opt. Code Gen. 代码优化器是现在编译器中最复杂的，也是耗时最长的。

优化时机

• 对于AST Pro：机器无关 Con：层次太多
• 对于汇编 Pro：暴露优化选项 Con：机器相关 Con：不同目标必须重新实现优化器
• 对于中间码 Pro：机器无关 Pro：暴露优化选项

Basic block基本块

是一个最大指令序列，拥有以下特性： - 没有标签（第一行指令除外） - 没有跳转（最后一行指令除外）

思路

• 不能跳转到基本块内部（第一行指令除外）
• 不能跳出基本块外部（最后一行指令除外）
• 基本块是一个单入口、单出口、单线性代码段

示例说明

一般不能优化。除非能其他地方没有使用t变量。

Control-flow graph控制流图

有以下特点： - 基本块为节点 - 一条边由基本块A指向基本块B，即A的最后一条指令指向B的第一条指令

示例

所有节点都有结束

目的

代码优化主要是提升程序资源利用率，比如： - 执行时间 - 代码大小 - 网络消息 优化不能改变计算结果。 按粒度分有三类优化器： - 局部优化：应用在基本块 - 全局优化：应用在控制流（方法体中） - 函数间优化：应用在跨方法边间 大部分编译器做局部优化，许多会做全局优化，只有少数会做函数间优化。

Local Optimization

最简单的优化器。 主要关注基本块内部。

删除优化

简化优化

常量折叠

在编译时，根据上下文能计算结果的可以优化：

注意

常量优化有时是比较危险的。比如在嵌入式开发中进行交叉编译，浮点数常量会存在精度问题。

不可达优化

代码块没有被其他jump指令跳转即不可达基本块。移除不可达基本块可以减小生成代码大小，有时运行会更快。

单声明

每个寄存器只进行一次声明，减少重复声明。

相同表达式

中间过程寄存器值不变，直接结果赋值。

拷贝传播

代码块中有w:=x的申明，使用x替换w。 一般配合其他优化共同作用，常量折叠、删除优化等。

特点

• 优化器交叉作用
• 编译优化需要不断调用优化器，直到没有提升的可能结束

综合示例

示例1 示例2 初始化代码： 最终形式：

Peephole Optimization

简介

直接应用于汇编代码。 Peephole是一组精简（通常是连续的）的指令序列。 优化器使用等效的代码序列替换它们。

示例说明

示例1

示例2

示例3

特点

与[[#Local Optimization]]相似，要想获得最佳效果必须要不断重复进行优化。

Dataflow Analysis

简介

为使用常量k替换变量x，需要满足条件： - 使用变量x的每条路径均为x:=k

示例说明

X为常量，可以优化： 左边X值改变，不能优化：

特点

• 检测条件是否满足不能太琐碎
• 所有路径包括循环路径和条件分支
• 检测条件依赖全局数据流分析 全局优化任务有几个方法：
• 依靠执行程序已知的属性X
• 依靠整个程序的体系在任意点证明X
• 保守没问题 全局数据流分析是解决这类问题的标准技术。 全局常量传播是一种优化手段，它依赖全局数据流分析。

Constant Propagation

约定

假定需要在每个代码点观测X的值，定义如下符号： 对于每个状态s，可以在s前后迅速得到x的值信息：

规则

Rule 1

前面有声明，则输入为声明

Rule 2

前面存在不同常量，则输入为T

Rule 3

前面所有值为相同常量或未执行，则输入为常量

Rule 4

前面都为未执行，则输入为未执行

Rule 5

输入为未执行，输出为未执行

Rule 6

输入不为未执行，且c为常量，输出为常量

Rule 7

输入不为未执行，且x:=f(…)，输出为声明

Rule 8

输出与输入相同，声明y且y不等于x

通用步骤

1. 程序的每个入口s，初始值为C(s,x,in)=T
2. 除步骤1的每个地方C(s,x,in)=C(s,x,out)=⊥
3. 不断遍历所有状态s，将不满足规则1-8的，进行更新。直到全部s符合规则

示例说明

初始状态 最终状态

Orderings

简化分析表达，可以得到：⊥ < c < T 使用图形表达是 构造函数lub计算最小上边界，例如： lub(⊥,1)=1 lub(T,⊥)=T lub(1,2)=T 任意两点通过图形找到通用的边界 使用lub可以将Rule 1改写为： C(s,x,in)=lub{C(p,x,out)|p是s的前一状态}

特点

• 状态值只能由⊥开始，并持续上升
• ⊥可以变为常数，常数可以变为T
• C(s,x,in/out)最多只能变化两次

Liveness Analysis

简介

如图，第一个X没有被使用，就是dead；第二个X就是live。

基本定义

如何判断变量x在状态s中一直存活： - 存在一个状态s’使用变量x - 有一个路径由s指向s’ - 这个路径中没有重新声明x 若在变量x声明后又遇到x:=…，就说明x存活结束（dead）

规则

Rule 1

Rule 2

Rule 3

Rule 4

通用步骤

1. 初始化所有L(…)=false
2. 重复选择规则1-4中的s，并按照规则更新，直到所有s满足规则1-4

示例说明

特点

• false可以变为true，但不能反向；（即false<true）
• 每个值只能改变一次，因此循环结束有保障
• 使用存活分析，可以消除多余代码很容易 前面介绍的常量传播是正向分析，即信息由输入到输出推出的； 存活分析是后向分析，即信息由输出反向到输入推出的；

Register Allocation

简介

中间码使用大量的临时变量。需要使用与物理寄存器数量匹配的临时变量。 主要方式有： - 为每个寄存器声明多个临时变量 - 不能改变程序行为 简单示例

示例说明

获取每个点存活的变量：

register interference graph

构建一个无向图，这也是寄存器干涉图 - 每个临时变量一个节点 - 边连接的节点不能同时被相同寄存器替代 两个能用相同寄存器存储的节点，不存在边直接连接它们 简单示例

Graph Coloring

简介

边连接的节点有不同的颜色。若图有k种颜色，则它就是k可着色（k-colorable） 其中有多少颜色就需要等量的寄存器。

问题

如何计算图有多少颜色不是很容易的。 - 可以使用heuristics 若需要的寄存器少于颜色 - 可以使用后面讲解spilling

简单方案

步骤： - 在图中选择邻居少于k的节点t - 从图中将节点t和它的边移除 - 若结果图就是k可着色，那这就是原图

泛化步骤： 1. 构造堆栈 - 在图中选择邻居少于k的节点t - 从图中将节点t和它的边移除，并将节点t放入堆栈 - 重复上述步骤直到图为空

2. 为节点涂色

• 从堆栈中获取节点
• 新节点颜色与上色的邻居不一致即可

示例说明

开始的图形： 所有节点少于4邻居： 所有节点入栈： 节点上色： 最终结果：

Spilling

若最终寄存器数量不足，则需要将数据“持久化”。 示例： 使用图中三颜色 可以选择一个节点，比如f将它存入内存。 简化后可以得到满足条件的图 即

具体步骤

• 若颜色优化失败，则声明内存存放f
• 在每处读取f前，增加指令从内存中恢复f再操作
• 在每处写入f后，增加指令将结果写入内存 示例 spilling后的图可以化简为

注意

spilling选定的临时变量有一些要求： - 邻居要尽量多 - 声明少且使用少 - 避免在循环内使用（会增加循环时间复杂度）

缓存管理

简介

编译器擅长管理寄存器，但不擅长管理缓存。编译器可以对缓存进行优化的空间很小。

内存管理

简介

需要对临时对象内存的生命周期进行管理（声明由程序进行）。 如何判断对象是否为不再使用则是内存管理的关键。 示例：

管理方法

标记mark阶段： 清理sweep阶段： 遍历堆中所有对象标记为0的，将其加入到释放列表中

完整过程示例

简介

概述

需要将分解好的Token进行语法匹配，生成抽象语法树(Abstract Syntax Tree , AST）。在此过程中需要检测非法语法，并指出问题所在。 在实现上一般由语法解析器驱动词法分析器进行分析。 实现上一般被称作Parser（解析器）。 语法分析程序产生器YACC，使用根据语法规则生成C语言语法分析器。

Abstract Syntax Tree（抽象语法树）

叶子节点是终止符（[[#定义]]），非叶子结点是非终止符（[[#定义]]）。

原理

Grammars（文法)

定义

文法是用来描述语言的语法成分结构构造的形式规则， 我们通常用G表示。

• 语法成分由句子和构成句子的词素组成
• 语言由句子组成

则将文法G定义为：

其中：

终止符（Terminal）集合为：，也可记为，也可以理解为语言中的字符串，不可分割 非终止符集合为：，也可记为，它需要不断被迭代替换为终止符组成的句子 开始符号为： 产生式为：，它定义了一组符号推导规则

推导

由文法开始符号开始推导， 用产生式的右部取代产生式的左部， 直到推到终结符号为止。 推导分为最左推导和最右推导， 最左推导每次替换式子的最左边， 最右替换每次推导式子的最右边。

示例

假定有文法

对于输入字符串：

可以得到整个推导过程：

规约

规约是句子通过文法规则将产生式的左部取代右部， 直到规约到开始符号为止。 规约也分为最左规约和最右规约。 最左规约和最右推导互为逆过程，同样，最右规约和最左推导互为逆过程。

语言形式

文法具体又可以分为0型文法， 1型文法， 2型文法，3型文法。下面的说明中

0型文法

中的产生式，其中并至少含有一个非终结符，。又叫做短语文法或无限制文法， 识别0型语言的自动机称为图灵机（TM）。

1型文法

中的产生式，除可能有外均有。若有，规定不得出现在产生式的右部。又称为上下文有关文法或者长度增加文法， 通过线性界限自动机（LBA）识别。

2型文法

中的产生式具有形式，其中，。又称为上下文无关文法，记作CFG（Context-Free Grammar）， 通过下推自动机（PDA）识别。

3型文法

中的产生式具有形式，或者，，其中，。又称为正规文法，记作RG（Regular Grammar）， 通过有限状态自动机识别。 Backus-Naur Form（BNF,巴克斯范式）是一种上下文无关文法。 通常研究上下文无关文法和正规文法， 因为程序设计语言的语法和词法规则主要与2型文法和3型文法有关。

Ambiguity（二义性）

一个文法，如果它的一个句子有两棵或两棵以上的语法树，则称此句子具有二义性。如果一个文法含有二义性的句子，则该文法具有二义性。 二义性问题是不可判定问题，即不存在一个算法在有限步骤内，确切判定一个文法是否有二义性。

分析方法

自上而下

从文法的开发符号出发，反复使用各种产生式，寻找“匹配”的推导。 从树的根部开始，构造语法树。 主要方法有：递归下降算法和预测解析器 需要解决的核心问题：回溯问题和文法左递归问题

Recursive Descent Algorithm（递归下降算法）

树的构建过程从上而下，从左往右。

示例 假定有文法

输入字符串为： 第1次解析，推导到，左括号与int不匹配

第2次解析，推导到，左括号与int*T不匹配

第3次解析，推导到，左括号与(E)匹配，继续解析E

第4次解析，推导到，int匹配，继续解析(E)剩余部分

第5次解析，推导到，有括号匹配，解析完毕

实现

定义TOKEN，泛化为tokens类别 定义next为全局指针指向下一个输入的token

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

tokens []TOKEN; // 词法解析的结果
TOKEN next=tokens[0]; // 初始化指向输入点

// 返回输入token类型与指定是否匹配
bool term(TOKEN tok) { return *next++ == tok; }

// 定义E的产生式
// E->T
bool E1() { return T(); }
// E->T+E
bool E2() { return T() && term(PLUS) && E(); }
// E相关产生式
bool E() {
	TOKEN *save = next;
	return (next=save, E1())
		|| (next=save, E2());
}

// 定义T的产生式
// T->int
bool T1() { return term(INT); }
// T->int*T
bool T2() { return term(INT) && term(TIMES) && T(); }
// T->(E)
bool T3() { return term(OPEN) && E() term(CLOSE); }
// T相关产生式
bool T() {
	TOKEN *save = next;
	return (next=save, T1())
		|| (next=save, T2())
		|| (next=save, T3());
}

特点 - 优点 非常容易实现 - 缺点 若部分成功，不会尝试其他推演； 不是适配所有语法 需要单独处理左递归和回溯问题

左递归问题

当存在一种推导路径，算法会陷入无限循环中。根据左递归方式，可以有如下处理方式。

产生式左递归

通用文法记为：，其中不包含起始的 重新改写为：

整体思路：将左递归改为右递归方式，先判断终止符再递归即可防止无限递归。 推导路径左递归

将非终止符按顺序排列，后面的非终止符不应包含前面非终止符的左递归形式，若存在则使用推导方式将其消除。然后就简化为产生式左递归，按照上面方式进行处理即可。

回溯问题

产生式中存在相同终止符开头的选择，算法需要暂时存储上下文，某条分支不匹配又需要重新恢复。消除这种选择即可消除回溯问题。

First Sets（首字符集）

获取字符集（即X = ）的可能包含的第一个终止符（包括），其定义如下：

特性： 若为终止符，则 若，则 若，并且每个都存在，则 若，并且每个都存在，则

Follow Sets（后继字符集）

获取字符集（即X = ）的可能的紧邻的一个终止符（包括文本结尾符），其定义如下：

特性： 若为开始符， 若每个产生式，则 若每个产生式，并且，则

示例

假定有文法

根据产生式(2)，可以得到；再根据产生式(1)，可以得到；综合可得。 同理，可得

得到非终止符的后继字符集：

根据产生式(4)，可得；再加上产生式(3)，可得和；

其他终止符同理，可以得到终止符的后继字符集：

Predictive Parsers（预测解析器）

在递归下降算法基础上，增加预测功能。即向后查看更多的token。 一般使用LL(1)，只预测一个token。

示例

假定有文法

对于产生式(1)要能生效，当前非终止符为，根据产生式(3)输入只能是(和int。 对于，需要根据文法和非终止符逆推非终止符后面可能的输入。比如，右侧有的只有产生式(1)，因，则；再逆推到产生式(3)有，则。具体建表规则间后面。 其他同理，可以得到LL(1)解析表：

步骤

1. 初始化栈为，并初始化next指向下一个输入token；
2. 获取栈顶两个元素；
3. 若为非终止符，则根据和输入token查找解析表。若命中表达式，则将重新入栈；若未命中则直接报错；
4. 若为终止符，则判断是否与输入token匹配，next指向下一个token。若匹配则将重新入栈；若未命中则直接报错；
5. 重复步骤2-4，直到栈为空；

使用表格推演示例解析输入过程：

解析表构建方法

对于文法需要构建LL(1)解析表，则每个产生式进行如下处理： - 每个终止符，都有 - 若存在，则每个终止符都有 - 若存在并且，都有

注意，对于表格项。若为空或多个不同值，则解析异常。

自下而上

从输入字符串开始，逐步进行归约，直到文法的开始符号。 从树的叶节点开始，构造语法树。 主要方法有：算符有限分析法和LR分析法 需要解决的核心问题：识别可规约串

算符优先法

特点

优点：简单，快速 缺点：可能错误接受非法句子 适用范围：用于分析各类表达式

示例

假定有文法

可以得到优先关系表：

优先关系表构建方法

下面小写字母为终结符，大写字母为非终结符。 - 确定满足关系的所有终结符对 ，当文法G中含有形如或的产生式 - 确定满足关系和的所有终结符对 ，当文法G中含有形如的产生式，而或；记为 ，当文法G中含有形如的产生式，而或；记为