精华内容
参与话题
问答
  • 编译的基本概念

    千次阅读 2019-07-10 14:33:39
    CPU执行程序的原理这篇文章中提到,“程序要想被CPU执行,首先要被编译成CPU可以执行的指令操作”,那编译成CPU可以执行的指令操作是什么意思呢?这篇文章就用来说明编译的实际意义是什么。 2、知识背景——CPU架构...

    1、本文目的

    CPU执行程序的原理这篇文章中提到,“程序要想被CPU执行,首先要被编译成CPU可以执行的指令操作”,那编译成CPU可以执行的指令操作是什么意思呢?这篇文章就用来说明编译的实际意义是什么。

    2、知识背景——CPU架构

    要谈编译,首先要说说CPU架构的概念。CPU架构也就是CPU指令集(指令就是汇编指令或者机器指令,比如Add是汇编指令,而对应的机器指令在MIPS下就是000000)架构,现有CPU架构包括鼎鼎有名的Intel的X86架构、ARM的ARM架构、MIPS的MIPS架构、DEC的Alpha架构。通俗来说,指令集就是指挥CPU如何运算的硬程序,没有这套指令的话,就没有办法指挥CPU运转,而计算机的所有运算都需要CPU参与。

    那编译呢,也就是将一段程序转换为指令集的过程。不同架构的指令集自然是不同的,带来的影响就是同一段代码,编译过后只能运行在对应的指令集上,比如一段C++代码,在X86下编译完了,只能在X86下运行,而不能运行在ARM架构下运行。

    而事实上,编译得到的结果,更是操作系统相关的。假设,一段程序被编译成了X86下的硬程序,但是无法同时运行在Windows上和Linux上(Windows和Linux操作系统都可以装在X86架构的CPU上),如果程序一开始是在Windows操作系统下编译的,那这段程序就无法运行在其他比如Linux操作系统中。

    也就是说,编译与操作系统和CPU这二者都是相关的。

    3、编译过程

    事实上,仅仅将程序通过编译改写成汇编指令或机器指令,在操作系统上还不能直接运行。实际上广义的编译,其实包括预处理、编译、汇编、链接这整个过程。

    1. 预处理,就是把代码里引入的其他代码,插入到这段代码中,形成一个代码文件。
    2. 编译,就是把代码转化为汇编指令的过程,汇编指令只是CPU相关的,也就是说C代码和python代码,代码逻辑如果相同,编译完的结果其实是一样的。
    3. 汇编,就是把汇编指令转为机器码的过程,机器码可以被CPU直接执行。
    4. 链接,就是将一段我们需要的已经编译好的其他库,与我们的汇编结果连起来,这样才是最终程序完整的形式,操作系统才可以运行。不同操作系统编译好的其他库形式不同,而且链接的方式也不同,得到最终程序的形式也不同,所以编译好的程序只能在特定的操作系统下运行。
    展开全文
  • 我们的代码会经过这4个环节,从而形成最终文件,c语言作为编译语言,用来向计算机发出指令。让程序员能够准确地定义计算机所需要使用的数据,并精确地定义在不同情况下所应当采取的行动。 预处理, 展开头文件/宏...

    楔子

    我们在各自的电脑上写下代码,得明白我们代码究竟是如何产生的,不想了解1,0什么的,但这几个环节必须掌握吧。

    我们的代码会经过这4个环节,从而形成最终文件,c语言作为编译语言,用来向计算机发出指令。让程序员能够准确地定义计算机所需要使用的数据,并精确地定义在不同情况下所应当采取的行动。

     

    预处理, 展开头文件/宏替换/去掉注释/条件编译                      (test.i main .i)
    编译,    检查语法,生成汇编                                                      ( test.s  main .s)
    汇编,   汇编代码转换机器码                                                         (test.o main.o)
    链接     链接到一起生成可执行程序                                              a.out
     

    预处理

    预处理如锲子中所言,是一种展开,下表是常用的一些预处理命令

    还有下列几种预处理宏(是双下划线)

    __LINE__ 表示正在编译的文件的行号
    __FILE__表示正在编译的文件的名字__DATE__表示编译时刻的日期字符串,例如: "25 Dec 2007"
    __TIME__ 表示编译时刻的时间字符串,例如: "12:30:55"
    __STDC__ 判断该文件是不是定义成标准 C 程序
    我的vs2013不是定义的标准c语言

     

    宏函数很好用,是直接展开,在这我顺便说一下宏的好处和坏处。

    宏优点1代码复用性2提高性能

    宏缺点1 不可调试(预编译阶段进行了替换),2无类型安全检查3可读性差,容易出错。

    这里附上《c和指针》中的一张表格,总结宏和函数十分到位,我就不多说了

     

    宏函数很皮,#define定义一个比如判断大小,替换常量,很是方便。

    不过我现在也就用下,#define ERROR_POWEROFF -1,#define _CRT_SECURE_NO_WARNINGS 1这样的和编译器有关的东西,不会去写宏函数,宏函数这东西,可读性特别差,在c++中,一般用const/枚举/内联去替代宏。

    但是,define宏在某些方面真的是非常好用,我很推荐。

    1.替代路径

    #define ENG_PATH_1 C:\Program Files (x86)

    2.针对编译器版本不兼容报错

    #define _CRT_SECURE_NO_WARNINGS 1

    3.条件编译

    #ifdef 标识符
    程序段 1
    #else
    程序段 2
    #endif

    4.使用库中的宏

    vc++中有许多有意思的宏,都是大牛们写出来的,真的是充满智慧,十分刁钻,怎么学也学不完,我个人担心出错就很少写宏,用函数代替了。在以后的博客中我会记录一些常用的,充作笔记。

    emmm,当然,还有其他许多重要的预处理。

    比如

    include

    #include <filename>

    尖括号是预处理到系统规定的路径中去获得这个文件(即 C 编译系统所提供的并存放在指定的子目录下的头文件)。找到文件后,用文件内容替换该语句。如stdio.h

    #include“filename”

    “”则是预处理我们自己第三方的文件,如程序员小刘写的Date.h,我们就可以include“Date.h”

    #error 预处理,#line 预处理,#pragma 预处理

    #error 预处理指令的作用是,编译程序时,只要遇到 #error 就会生成一个编译错误提示消息,并停止编译。

    这个我没写过,但碰到过很多次,在编写mfc代码中,拉入控件时我加入密码框控件,OS编译时会自动弹出#error 提示我该编辑框为密码,注意明文问题

    #line 的作用是改变当前行数和文件名称,如#line 28  liu 

    目前我没使其派上用场,但了解为好。

    #pragma 是比较重要且困难的预处理指令。

    #pragma once 

    这个的做用就是防止头文件多次包含

    当然,还有另外一种风格,防止被包含,我同时给出来

    是巧妙地利用了define宏

    #ifndef _SOME_H
    #define _SOME_H
    
    
    ...//(some.h头文件内容)
    
    
    #endif

    变量的防止重复定义则利用extern,在头文件中不初始化只声明。引用该头文件即可,在链接过程中。就可以使用到这个变量。

    (附:extern在c++中经常用于  extern "C"  告诉编译器下面是c语言风格)

    #pragma warning

    #pragma warning( disable : 4507 34; once : 4385; error : 164 )
    等价于:
    #pragma warning(disable:4507 34) // 不显示 4507 和 34 号警告信息
    #pragma warning(once:4385) // 4385 号警告信息仅报告一次
    #pragma warning(error:164) // 把 164 号警告信息作为一个错误。

    另外还有

    #pragma pack

    使用指令#pragma pack (n),编译器将按照 n 个字节对齐。
    使用指令#pragma pack (),编译器将取消自定义字节对齐方式。
    在#pragma pack (n)和#pragma pack ()之间的代码按 n 个字节对齐。

    字节对齐,我将另起炉灶,在另外一篇博客中归纳总结。

     

    #pragma pack(push) //保存当前对其方式到 packing stack
    #pragma pack(push,n) 等效于
    #pragma pack(push)
    #pragma pack(n) //n=1,2,4,8,16 保存当前对齐方式,设置按 n 字节对齐
    #pragma pack(pop) //packing stack 出栈,并将对其方式设置为出栈的对齐

    #运算符和##预算符

    #define SQR(x) printf("The square of "#x" is %d.\n", ((x)*(x)));

    这段代码中#就是帮助x作为一个变量,表现出来,而不是一个简单的字母

    如果有#,SQR(3)运算出来就是

    The square of 3  is 9

    如果没有# SQL(3)运算出来就是

    The square of x  is 9

    ##预算符

    ##把两个语言符号组合成单个语言符号

    编译

    编译阶段是检查语法,生成汇编,这个属于程序员的必备知识,我们学习一门语言第一步就是知晓语法,其中比较生涩的有左值右值,指针的使用,内存的管理,数据结构的使用,这将会是一场持久战 ,贯穿在整个学习生涯。

    在这里我截取优先级问题,这个可能会通过编译但是不一定达到程序员想要的结果。

    在这里,我引用《c语言深度解剖》中的一张表格

    汇编

      汇编代码转换机器码   这个阶段,非底层的程序员不需要考虑, 编译器不会搞错的。也与c/c++开发者无关,但是我们可以利用反汇编来调试代码,学习汇编语言依然是必备的。

    链接

    开头我引用一下百度百科的介绍

    静态链接是由链接器在链接时将库的内容加入到可执行程序中的做法。链接器是一个独立程序,将一个或多个库或目标文件(先前由编译器汇编器生成)链接到一块生成可执行程序。静态链接是指把要调用的函数或者过程链接到可执行文件中,成为可执行文件的一部分。

    动态链接所调用的函数代码并没有被拷贝到应用程序的可执行文件中去,而是仅仅在其中加入了所调用函数的描述信息(往往是一些重定位信息)。仅当应用程序被装入内存开始运行时,在Windows的管理下,才在应用程序与相应的DLL之间建立链接关系。当要执行所调用DLL中的函数时,根据链接产生的重定位信息,Windows才转去执行DLL中相应的函数代码。

    将源文件中用到的库函数与汇编生成的目标文件.o合并生成可执行文件。该可执行文件会变大很多,一般是调用自己电脑上的。

    静态库和应用程序编译在一起,在任何情况下都能运行,而动态库是动态链接,文件生效时才会调用。

    很多代码编译通过,链接失败就极有可能在静态库和动态库这出现了纰漏,要视情况解决。缺少相关所需文件,就会链接报错。这个时候就要检查下本地的链接库是不是缺损。

    展开全文
  • 编译原理:总结

    万次阅读 多人点赞 2019-01-08 09:34:59
    编译器概述 编译器的核心功能 编译器的核心功能是把源代码翻译成目标代码: 翻译!!!目标代码!!! 理解源代码:词法分析、语法...转化为等价的目标代码:中间代码生成、目标代码生成 ...语法分析器:单词流-&am

    编译器概述

    编译器的核心功能

    编译器的核心功能是把源代码翻译目标代码

    翻译!!!目标代码!!!

    • 理解源代码:词法分析、语法分析、语义分析
    • 转化为等价的目标代码:中间代码生成、目标代码生成
    • 更好:优化方法

    编译器的结构

    每个阶段将源程序从一种表示转换成另一种表示。
    随着编译器各个阶段的进展,源程序的内部表示不断地发生变化。

    • 词法分析器:字符流->单词流
    • 语法分析器:单词流->语法树
    • 语义分析器:
      • 收集标识符的属性信息:
        • 类型(Type)
        • 种属(Kind)
        • 存储位置、长度
        • 作用域
        • 参数和返回值信息
      • 语义检查:
        • 变量或过程未经声明就使用
        • 变量或过程名重复声明
        • 运算分量类型不匹配
        • 操作符与操作数之间的类型不匹配
    • 中间代码生成器:抽象语法树->中间表示(与平台无关的抽象程序):
      1. 易于产生
      2. 易于翻译成目标程序
      3. 三地址码:temp1=c*d;temp2=b+temp1;a=temp2
      4. 四元式:(op, arg1, arg2, result);(* , c , d , temp1);(+ , b, temp1 , temp2);(= , temp2 , - , a)
    • 代码优化器:试图改进中间代码,以产生执行速度较快的机器代码:
      • temp1=c*d;temp2=b+temp1;a=temp2
      • change to:temp1=c*d;a=b+temp1
    • 代码生成器:生成可重定位的机器代码或汇编代码:
      • temp1=c*d;a=b+temp1
      • change to:Mov R2,c;Mul R2, d;Mov R1, b;Add R2, R1;Mov a, R2
      • 一个重要任务是为程序中使用的变量合理分配寄存器
    • 符号管理表:
      • 基本功能是记录源程序中使用的标识符,
      • 并收集与每个标识符相关的各种属性信息,
      • 并将它们记载到符号表中。
    • 错误处理器:
      • 处理方式:报告错误,应继续编译
      • 大部分错误在语法分析、语义分析阶段检测出来
      • 词法分析:字符无法构成合法单词
      • 语法分析:单词流违反语法结构规则
      • 语义分析:语法结构正确,但无实际意义

    在这里插入图片描述


    程序设计语言及其文法

    字母表和串上的运算

    串:是字母表中符号的一个有穷序列。
    ∑ 是一个字母表,任意 x∈∑*,x 是 ∑ 上的一个串。

    语言的定义和运算、句子的定义

    设 ∑ 是一个字母表,任意L 属于 ∑*,L 称为字母表 ∑ 上的一个语言
    任意 x∈L,x 叫做 L 的一个句子

    文法的定义

    文法是用于描述语言的语法结构的形式规则。
    任何一种语言都有它自己的文法,不管它是机器语言还是自然语言。

    • 自然语言的文法:主 谓 宾
    • 机器语言也有描述它语言构成的特定文法

    文法可以定义为一个四元组(VT, VN, S, P)

    1. 一个终结符号集合VT
    2. 一个非终结符号集合VN
    3. 一个产生式集合P,定义语法范畴。产生式:A → α,产生式:描述了将终结符和非终结符组合成串的方法
    4. 一个特定的非终结符——开始符号S

    文法的四种类型

    • 0型文法:也称为短语文法
      • ∀α → β∈P,α中至少包含1个非终结符
      • 任何0型语言都是递归可枚举的;反之,递归可枚举集必定是一个0型语言。
    • 1型文法:上下文有关文法context-sensitive
      • ∀ α→β,都有|α| ≤ |β| ,仅 S→ε除外
      • 产生式的形式描述:α1Aα2 → α1βα2 (α1, α2,β∈(VN∪VT ) *,β≠ε,A∈ VN)
      • 即:A只有出现在α1, α2的上下文中,才允许用β替换。
    • 2型文法:上下文无关文法, context-free grammar. CFG
      • ∀ α→β,都有α∈VN,β∈(VN∪VT)*
      • 产生式的形式描述:A →β (A∈VN)
      • 即:β取代A时,与A所处的上下文无关。
    • 3型文法:regular grammar, RG,也称正则文法
      • 每个产生式均为 “A→aB”或“A→a” —— 右线性
      • 或 “A→Ba”或“A→a” —— 左线性
      • (A、B∈VN,a∈VT*)

    推导和归约

    推导:用产生式的右部替换产生式的左部

    句子、句型和语言的定义

    • 如果Sαα(VTVN)S →^* α,α∈(V_T∪V_N)^*,则称α是G的一个句型
    • 如果SwwVTS →^* w,w ∈V_T^*,则称w是G的一个句子
    • 由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言,记为L(G)。即L(G)={w|SwwVTS →^* w,w ∈V_T^*}

    语法生成树

    用图形的方式展示推导过程

    二义性:多个语法分析树生成同一个终结符号串

    程序语言定义

    任何语言实现的基础是语言定义
    语言的定义决定了该语言具有什么样的语言功能、 什么样的程序结构、以及具体的使用形式等细节问题。

    • 词法:是指单词符号的形成规则。(状态转换图、正则表达式和有穷自动机)
    • 语法:是指一组规则,用它可产生一个程序。(下推自动机理论和上下文无关文法是讨论语法分析的理论基础)
    • 规则:词法规则 + 语法规则
    • 语义:定义语言的单词符号和语法单位的意义。(属性方法和基于属性文法的语法制导翻译方法)
    • 形式语言:上述的定义是用文字来描述的,当设计编译程序时,就要把它用形式的方式描述出来,就要用到形式语言。

    参数传递方法:

    1. 传值调用
    2. 引用调用
    3. 复制恢复(传值结果)
    4. 传名调用

    词法分析

    词法分析器的作用

    • 识别源程序中的单词是否有误
    • 读入源程序字符流、组成词素,输出词法单元序列
    • 过滤空白、换行、制表符、注释等
    • 将词素添加到符号表中

    词法分析器的角色

    编译过程的分析部分:词法分析 + 语法分析

    • 简化编译器的设计:词法分析器可以首先完成一些简单的处理工作
    • 提高编译器的效率:相对于语法分析,词法分析过程简单,可高效实现增强编译器的可移植性(输入设备无关)

    输入缓冲

    三种实现方式

    1. 自动生成工具——Lex,生成工具提供读取输入和缓冲的函数
    2. 高级语言手工编码,利用高级语言提供的I/O函数
    3. 汇编语言编程,直接访问磁盘
    • 1 → 3,性能↗ ,实现难度↗
    • 唯一读取文件的阶段,值得优化
    • 方案:
      • 双缓冲方案
      • 哨兵标记

    词法单元的描述:正则表达式定义规则

    若 r, s为正则表达式,表示语言L(r)L(s)L(r)和L(s),则(从1到4优先级递增)

    1. (r)(s)L(r)L(s)(r) | (s)是正则表达式,表示语言L(r)∪L(s)
    2. (r)(s)L(r)L(s)(r)(s)是正则表达式,表示语言L(r)L(s)
    3. (r)(L(r))(r)*是正则表达式,表示语言(L(r))*
    4. (r)L(r)(r) 是正则表达式,表示语言L(r)

    正则表达式等价(equivalent):r = s → 表示的语言相同,L(r)=L(s)L(r) = L(s)

    • 能被5整除的10进制整数:[1-9][0-9]*(0|5)|0|5(!!!
    • C 语言标识符:[_a-zA-Z][_a-zA-Z0-9]*
    • C 语言无符号数的集合:
      • digit → [0-9]
      • digits → digit+
      • number → digits (.digits)? (E(+|-)? digits)?
    • 不包含连续的0的01串:((ε|0)1)*0?

    词法单元的识别

    状态转换图(注意初态和终态)

    不确定有限自动机

    数学模型,表示为五元组 M = {S,Σ,δ,s0,F},其中

    • S:有限状态集
    • Σ:有穷字母表,其元素为输入符号
    • δ:S×Σ到S的子集的映射,即 δ: S×(Σ∪{ε}) → 2S2^S,状态转换函数。
    • s0∈S 是唯一的初态
    • F⊆S 是一个终态集

    正则表达式(描述单词)
    NFA(定义语言):存在缺点,同一符号或ε和其它符号 → 多义性,难以实现
    DFA(适于计算机实现)

    NFA 和 DFA 都可识别正则表达式,时-空折衷
    词法分析器可用一组NFA来描述,每个NFA表示一个单词

    设计自动机(注意初态的 →start 和终态的双圈)

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    词法分析器的构造

    正则表达式 → 构造NFA(Thompson构造法)

    构造规则:注意开始的箭头和结束的双圈

    • N(ε)

    在这里插入图片描述

    • N(a)

    在这里插入图片描述

    • N(s|t)

    在这里插入图片描述

    • N(st)

    在这里插入图片描述

    • N(s*)

    在这里插入图片描述

    NFA → 转换DFA(子集构造法)

    在这里插入图片描述

    1. ε-closure(0)={0,1,2,4,7}=A
    2. ε-closure(δ(A,a)) = ε-closure(δ({0,1,2,4,7},a))
      = ε-closure({3,8})
      = {1,2,3,4,6,7,8} = B
      ∴ Dtran[A,a] = B
      ε-closure(δ(A,b)) = ε-closure(δ({0,1,2,4,7},b))
      = ε-closure({5}) = {1,2,4,5,6,7} = C
      ∴ Dtran[A,b] = C
    3. ε-closure(δ(B,a)) = ε-closure(δ({1,2,3,4,6,7,8},a))
      = ε-closure({3,8})
      = {1,2,3,4,6,7,8} = B
      ∴ Dtran[B,a] = B
      ε-closure(δ(B,b)) = ε-closure(δ({1,2,3,4,6,7,8},b))
      = ε-closure({5,9})
      = {1,2,4,5,6,7,9} = D
      ∴ Dtran[B,b] = D
    4. ε-closure(δ(C,a)) = ε-closure(δ({1,2,4,5,6,7},a))}
      = ε-closure({3,8})
      = {1,2,3,4,6,7,8} = B
      ∴ Dtran[C,a] = B
      ε-closure(δ(C,b)) = ε-closure(δ({1,2,4,5,6,7},b))
      = ε-closure({5})
      = {1,2,4,5,6,7} = C
      ∴ Dtran[C,b] = C
    5. ε-closure(δ(D,a)) = ε-closure(δ({1,2,4,5,6,7,9},a))}
      = {1,2,3,4,6,7,8} = B
      ∴ Dtran[D,a] = B
      ε-closure(δ(D,b)) = ε-closure(δ({1,2,4,5,6,7,9},b))}
      = {1,2,4,5,6,7,10} = E
      ∴ Dtran[D,b] = E
    6. ε-closure(δ(E,a)) = ε-closure(δ({1,2,4,5,6,7,10},a))}
      = {1,2,3,4,6,7,8} = B
      ∴ Dtran[E,a] = B
      ε-closure(δ(E,b)) = ε-closure(δ({1,2,4,5,6,7,10},b))}
      = {1,2,4,5,6,7} = C
      ∴ Dtran[E,b] = C
    7. 最终结果:

    在这里插入图片描述

    最小化DFA状态

    • 初始,两个组:终态与非终态
    • 划分方法,对于状态组A={s1,s2,…,sk}
      • 对符号a,得到其转换状态t1,t2,…,tk
      • 若t1,t2,…,tk属于不同状态组,则需将A对应划分为若干组

    在这里插入图片描述

    在这里插入图片描述


    语法分析

    语法分析器的类型

    在自顶向上的语法分析方法中,分析的关键是:选择候选式
    在自底向上的语法分析方法中,分析的关键是:寻找句柄

    自顶向下分析器:递归下降法,LL(1)
    自底向上分析器:LR()

    LL 和 LR 都不能表示所有 CFG。

    LR分析表种类:

    • LR(0):局限性大,但它是建立其它分析表的基础
    • SLR (1) :易实现,功能比LR(0)稍强些
    • LR(1) :分析能力最强,但实现代价高
    • LALR (1) :功能介于SLR(1)和LR(1)之间,适用于大多数程序设计语言的结构,并且可以比较有效地实现。同心集。

    语法分析器的作用

    • 利用语法检查单词流的语法结构
    • 构造语法分析树
    • 语法错误和修正
    • 识别正确语法
    • 报告错误

    语法错误处理

    不同层次的错误

    • 词法:拼写错误(then → them)
    • 语法:单词漏掉、顺序错误(花括号不配对)
    • 语义:类型错误(声明void f()和调用aa = f())
    • 逻辑:无限循环/递归调用( == → = )

    错误处理目标

    • 清楚、准确地检测、报告错误及其发生位置
    • 快速恢复,继续编译,以便发现后续错误
    • 不能对正确程序的编译速度造成很大影响

    LL,LR,可最快速度发现错误:可行前缀特性,viable-prefix property,当一个输入前缀不是语言中任何符号串前缀——发生错误。

    错误恢复策略

    1. 错误恢复策略
      • 丢弃单词,直到发现 “同步”单词,设计者指定同步单词集,{end, “;”, “}”, …}
      • 缺点:丢弃输入导致遗漏定义,造成更多错误;遗漏错误
      • 优点:简单 → 适合每个语句一个错误的情况
    2. 短语层次的恢复
      • 局部修正,继续分析,同样由设计者指定修正方法。e.g. “,” → “;”,删除“,”,插入“;”
      • 与恐慌模式相结合,避免丢弃过多单词
    3. 错误产生式
      • 理解、描述错误模式,文法添加生成错误语句的产生式,拓广文法 → 语法分析器程序。( 错误检测信息+自动修正)
      • e.g. 对C语言赋值语句,为“:=”添加规则 报告错误,但继续编译
    4. 全局纠正
      • 错误程序 → 正确程序,寻找最少修正步骤,插入、删除、替换
      • 过于复杂,时空效率低

    上下文无关文法

    推导:描述文法定义语言的过程,自顶向下构造语法分析树的精确描述。

    两个CFG生成相同语言,两个CFG等价。

    最左推导,最右推导。

    语法树:推导的图示,但不体现推导过程的顺序。

    一棵语法树对应多个推导,但是有唯一的最左推导和最右推导。

    二义性文法存在某个句子对应多个语法树,多个最左(右)推导。

    证明CFG G生成语言L:(数学归纳法)

    1. G生成的每个符号串都在L中
    2. L中每个符号串都可由G生成

    正则表达式可描述的语言CFG均可描述。
    RG 都可用 NFA 表示,CFG 都是 RG,所以 CFG 都可用 NFA 表示。

    为什么还需要正则表达式?

    • 词法规则很简单,正则表达式描述能力足够
    • 正则表达式更简洁、更容易理解
    • 能更自动构造更高效的词法分析器
    • 使编译器前端更模块化

    设计 CFG

    在这里插入图片描述

    CFG 的修改

    • 消除二义性
    • 消除左递归(间接左递归):见附录
    • 消除空产生式:利用产生式进行代入
    • 消除回路:保证每个产生式都加入终结符(开始符号的空产生式除外)
    • 提取左公因子:预测分析方法要求—— 向前搜索一个单词,即可确定产生式

    在这里插入图片描述

    在这里插入图片描述

    CFG 优点

    • 给出精确的,易于理解的语法说明
    • 自动产生高效的分析器
    • 可以给语言定义出层次结构
    • 以文法为基础的语言的实现便于语言的修改

    问题:CFG 文法只能描述编程语言的大部分语法。(无法表示标识符必须在使用前定义,函数形参和实参数目应匹配)

    递归下降分析法

    缺点

    • 不能处理左递归
    • 复杂的回溯技术
    • 回溯导致语义工作推倒重来
    • 难以报告出错的确切位置
    • 效率低

    产生回溯的原因:进行推导时,若产生式存在多个候选式,选择哪个候选式进行推导存在不确定性。
    消除回溯的基本原则:对文法的任何非终结符,若能根据当前读头下的符号,准确的选择一个候选式进行推导,那么回溯就可以消除。

    LL(1):构造预测分析表

    计算FIRST和FOLLOW函数

    • FIRST

    FIRST(X1 X2 … Xn ) = FIRST (X1) “+”
    FIRST(X2) if ε is in FIRST(X1) “+”
    FIRST(X3) if ε is in FIRST(X2) “+”

    FIRST(Xn) if ε is in FIRST(Xn-1)
    注意:仅当对所有i,e∈FIRST(Xi),才将e加入FIRST(X1 X2 … Xn)

    • FOLLOW

    $加入FOLLOW(S),S为开始符号,$为输入串结束标记
    若A → αBβ,则FIRST(β)中符号除ε外,均加入FOLLOW(B)
    若A → αB 或 A → αBβ 且 β →* ε,FOLLOW(A)中所有符号加入FOLLOW(B)

    在这里插入图片描述

    应用构造算法

    • 对所有的终结符a ∈ FIRST(α),将 A->α 加入M[A,a]
    • 若ε ∈ FIRST(α),对所有的终结符b ∈ FOLLOW(A),将 A->α 加入M[A,b]
    • 所有未定义的表项设置为错误

    在这里插入图片描述

    e.g. id+id*id

    在这里插入图片描述

    LL(1)文法

    若文法G的预测分析表M中不含有多重定义项,则称G为 LL(1)文法。且无二义性,无左递归。

    计算 First 和 Follow 习题

    在这里插入图片描述

    预测分析法的错误恢复

    恐慌模式恢复策略

    考虑非终结符的同步单词集

    • FOLLOW(A)——略过A
    • 将高层结构的开始符号作为低层结构的同步集
    • FIRST(A)——重新开始分析A

    在这里插入图片描述

    • Follow 集为 sync,弹出一个非终结符
    • 其他的空位则跳过输入符号

    在这里插入图片描述

    短语层次错误恢复

    预测分析表空位填入错误处理函数

    自顶向下分析:预测分析法

    预测分析法实现步骤

    • 构造文法
    • 改造文法:消除二义性、消除左递归、消除回溯
    • 求每个变量的FIRST集和FOLLOW集,构造预测分析表
    • 检查是不是LL(1) 文法
    • 对于递归的预测分析,为每一个非终结符编写一个过程;对于非递归的预测分析,实现表驱动的预测分析算法

    缺点:不是所有文法满足LL(1)要求

    自底向上分析方法

    自底向上语法分析,是从输入符号串出发,试图把它归约成识别符号。
    从图形上看,自底向上分析过程是以输入符号串作为末端结点符号串,向着根结点方向往上构造语法树,使识别符号正是该语法树的根结点。

    归约:某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号

    自底向上分析是一个不断进行直接归约的过程。任何自底向上分析方法的关键是要找出这种句柄。

    符号串的句柄是与某个产生式右部匹配的子串,应该归约为产生式左部(最右推导的逆过程)。

    一个句型可有多个不同句柄,但是非多义性文法的最右句型有唯一句柄。

    基本操作:移进、归约、接受、错误。

    若B为非终结符,则 A→a · Bb 为待约项目。

    LR分析方法:当前最广义的无回溯的“移进- 归约”方法。

    优点:适用范围广;分析速度快;报错准确。

    从逻辑上说,一个LR分析器包括两部分:一个总控程序和一张分析表。

    构造 LR(0)分析表

    1. 写出给定文法G的增广文法G’并编号
    2. 构造识别可行前缀的DFA
    3. 根据DFA构造LR(0)分析表

    LR(0)示例

    • 示例文法

    在这里插入图片描述

    • 示例文法的分析表

    在这里插入图片描述

    构造 SLR(1)分析表

    解决同一项目集中的移进-归约冲突。

    对于冲突项目集 Ii ={A→β1·bβ2,B→β·,C→β·},如果集合FOLLOW(B)和FOLLOW(C)不相交,而且不包含b,那么,当状态Ii面临任何输入符号a时,可采用如下“移进—归约”的决策。

    ①当a=b时,则移进,置ACTION[i,a]=Sj
    ②当a∈FOLLOW(B)时,置ACTION [i,a]=rj
    ③当a∈FOLLOW(C)时,置ACTION [i,a]=rm
    ④当a不属于三种情况之一,置ACTION [i,a]=“ERROR”

    一般地,若一个项目集 Ii 含有多个移进项目和归约项目,例如
    Ii={A1→α·a1β1,A2→α·a2β2,…,Am→α·amβm,B1→α·,B2→α·,…,Bn→α·}
    如果集合{a1,a2,…,am},FOLLOW(B1),FOLLOW(B2),… FOLLOW(Bn)两两不相交时,可类似地根据不同的当前符号,对状态为i中的冲突动作进行区分。这种解决“移进—归约”冲突的方法称作SLR方法。

    SLR(1)文法:对于给定的文法G,若按上述方法构造的分析表不含多重定义的元素,则称文法G是SLR(1)文法。

    SLR(1)示例

    设有文法G
    E→E+T|T
    T→T*F|F
    F→(E)|id
    构造该文法SLR(1)分析表。

    ① 将文法G增广为G′,同时对每一产生式进行编号
    (0)S′→E
    (1)E→E+T
    (2)E→T
    (3)T→T*F
    (4)T→F
    (5)F→(E)
    (6)F→id
    ②对G′构造文法LR(0)项目集规范族如下:

    在这里插入图片描述

    ③ 取这些项目集作为各状态,并根据转换函数GO画出识别文法G′的有穷自动机,

    在这里插入图片描述

    ④ 用SLR方法解决“移进—归约”冲突。
    在十二个项目集中, I1、 I2 和 I9 都含有“移进—归约”冲突,其解决办法是:
    对于项目集 I1 ={S′→E·,E →E·+T},由于集合 FOLLOW(S′)={$}与集合{+}不相交,所以当状态为1时,面临着输入符号为+时便移进,而面临着输入符号为$时,则按产生式S′→E归约。对于项目集 I2 ={E→T·,T→T·*F},由于集合 FOLLOW(E)={+,),$}与集合{*}不相交,因此状态2面临输入符号为*时移进,而面临输入符号为+或)或$时,按产生式E→T归约。对于项目集I9 ={E →E+T·,T →T·*F},同样由于 FOLLOW(E) = { +, ), $ }与集合{*}不相交,因此状态9面临着输入符号为*时移进,面临着输入符号为+或)或$ 时,按产生式E→E+T归约。

    ⑤ 构造SLR(1)分析表

    在这里插入图片描述

    • 输入串为id+id*id为例,给出LR分析器的分析过程如下表:
    步骤 状态栈 符号栈 输入串 分析动作 下一状态
    1 0 id+id*id$ S5 5
    2 05 $id +id*id$ r6 GOTO[0,F]=3
    3 03 $F +id*id$ r4 GOTO[0,T]=2
    4 02 $T +id*id$ r2 GOTO[0,E]=1
    5 01 $E +id*id$ S6 6
    6 016 $E+ id*id$ S5 5
    7 0165 $E+id *id$ r6 GOTO[6,F]=3
    8 0163 $E+F *id$ r4 GOTO[6,T]=9
    9 0169 $E+T *id$ S7 7
    10 01697 $E+T* id$ S5 5
    11 016975 $E+T*id r6 GOTO[7,F]=10
    12 0169710 $E+T*F r3 GOTO[6,T]=9
    13 0169 $E+T r1 GOTO[0,E]=1
    14 01 $E acc

    LR(1)

    SLR(1)也存在不足,即如果冲突项目的非终结符FOLLOW集与有关集合相交时,就不能用SLR(1)方法解决。

    SLR(1)是 LR(1)的一种特例,即所有 SLR(1)文法都是 LR(1)文法。

    SLR只是简单地考察下一个输入符号b是否属于与归约项目A→α相关联的FOLLOW(A),但b∈FOLLOW(A)只是归约α的一个必要条件,而非充分条件。

    对于产生式A→α的归约,在不同的使用位置,A会要求不同的后继符号。在特定位置,A的后继符集合是FOLLOW(A)的子集。

    **任何二义性文法都不是LR(k)文法。 **

    LALR

    LALR分析法与SLR相类似,但功能比SLR(1)强,比LR(1)弱。

    首先构造LR(1)项目集,如果它不存在冲突,就把同心集合并在一起,若合并后项目集规范族不存在“归约—归约”冲突,就按照这个集族构造分析表。``

    一个LR(1)文法合并同心集后若不是LALR(1)文法,则可能存在归约/归约冲突,不可能存在移进/归约冲突。


    语法制导翻译

    语法制导翻译概述

    语法制导翻译使用CFG来引导对语言的翻译,是一种面向文法的翻译技术

    在这里插入图片描述

    语义分析器的任务:
    ① 检查各个语法结构的静态语义 (静态语义分析或静态检查 )
    ② 执行所规定的语义动作:如表达式的求值、符号表的填写、中间代码的生成
    将静态检查和中间代码生成结合到语法分析中进行的技术称为语法制导翻译

    语法制导的翻译:一种形式化的语义描述方法,包括两种具体形式:

    • 语法制导定义(Syntax-Directed Definitions, SDD):定义翻译所必须的语义属性和语义规则,一般不涉及计算顺序。
    • 翻译模式(translation schemes): 给出语义规则的计算顺序。

    语法制导定义(SDD)

    • 一个上下文无关文法。
    • 每个属性与文法的一个终结符或非终结符相关联
    • 每一个产生式和一个语义规则集合相关联。描述产生式中各文法符号的属性之间的依赖关系。通常用函数或程序语句的形式表示

    语法制导定义是一种接近形式化的语义描述方法。语法制导定义的表示分两部分:

    • 先针对语义为文法符号设置属性,
    • 然后为每个产生式设置语义规则,来描述各属性间的关系。

    继承属性和综合属性

    属性的特点:

    • 一个结点的综合属性的值通过分析树中它的子结点的属性值和自己的属性值计算的;
    • 继承属性的值由结点的父结点、兄弟结点来计算的;
    • 非终结符号即可有综合属性也可有继承属性,但文法开始符号没有继承属性;
    • 终结符号只有综合属性,由词法分析器提供,即记号的属性;
    • 每个文法符号的综合属性和继承属性的交集为空。

    判断一个属性是继承属性还是综合属性

    综合属性(synthesized attribute):

    • 在分析树结点 N 上的非终结符 A 的综合属性只能通过 N 的子结点N 本身的属性值来定义。
    • 终结符可以具有综合属性。终结符的综合属性值是由词法分析器提供的词法值,因此在SDD中没有计算终结符属性值的语义规则。

    继承属性(inherited attribute)

    • 在分析树结点 N 上的非终结符 A 的继承属性只能通过 N 的父结点、N 的兄弟结点或 N 本身的属性值来定义。
    • 终结符没有继承属性。终结符从词法分析器处获得 的属性值被归为综合属性值。

    继承属性和综合属性的计算在产生式中所在的位置

    • 将计算某个非终结符号A的继承属性的动作插入到产生式右部中紧靠在A的本次出现之前的位置上
    • 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端

    副作用

    副作用:一般属性值计算(基于属性值或常量进行的)之外的功能,如,打印出一个结果;将信息加入符号表。

    注释分析树

    注释分析树:将属性附着在分析树对应文法符号上(属性作为分析树的注释)。

    SDD的求值顺序

    • 对单词符号串进行语法分析,构造语法分析树
    • 根据需要构造属性依赖图;(综合属性在右,继承属性在左)
    • 遍历语法树,并在语法树各结点处按语义规则进行计算

    在这里插入图片描述

    S属性与L属性

    仅仅使用综合属性的 SDD 称为 S 属性的 SDD

    如果一个SDD是S属性的,可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值。

    L-属性定义的直观含义:在一个产生式所关联的各属性之间,依赖图的边可以从左到右,但不能从右到左。即 A->X1X2……Xn 中 Xi 的每个继承属性仅依赖于:

    • A 的继承属性
    • Xi 左边的符号X1,……Xi-1 的属性
    • Xi 本身的属性,但是不能在依赖图中形成环路。

    每个S-属性定义都是L-属性定义
    把L-属性定义变换成翻译模式,在构造翻译程序的过程中前进了一大步。

    语法制导的翻译方案

    示例1:实现桌上计算器的后缀 SDT

    val 为综合属性,计算其值都在产生式的末尾。

    L → En { print (E.val); }
    E → E1 + T { E.val = E1 .val + T.val;}
    E → T { E.val = T.val;}
    T → T1 * F { T.val = T1.val * F.val ;}
    T → F { T.val = F.val; }
    F → (E) { F.val = E.val; }
    F → digit { F.val = digit.lexval; }

    示例2:给出下列文法的 SDT

    为文法
    S → ( L ) | a
    L → L , S | S
    写一个翻译方案,它输出每个a的嵌套深度。例如,对于( a , ( a , a) ),输出的结果是1 2 2。

    depth 为继承属性,计算其值在紧靠非终结符出现之前。

    S’→ {S. depth = 0 } S
    S → {L. depth = S. depth + 1 } ( L )
    S → a {print (S. depth) }
    L → {L1. depth = L. depth }L1 , {S. depth = L. depth }S
    L → {S. depth = L. depth }S

    示例3:根据下列文法的 SDT

    有文法G及其语法制导翻译如下所示:(语义规则中的*和+为运算符乘号和加号)
    E → E1^T{E.val=E1.val * T.val}
    E → T{E.val= T.val}
    T → T1#n{T.val=T1.val +n.val}
    T → n{T.val= n.val}
    采用自底向下分析时,句子3∧3#4其值为:21

    示例4:给出下列文法的 SDT

    为文法
    S → ( L ) | a
    L → L , S | S
    写一个翻译方案,它打印出每个a在句子中是第几个字符。例如,当句子是( a , ( a , ( a , a ) , (a) ) )时,打印的结果是2 5 8 10 14。

    in 为继承属性,out 为综合属性。

    每个非终结符左侧计算其 in 属性,每个产生式最右侧计算其 out 属性。

    S’ → {S. in = 0 } S
    S → {L. in = S. in + 1 } ( L )
    {S. out = L. out + 1 }
    S → a {S. out = S. in + 1; print (S. out) }
    L → {L1. in = L. in }L1 ,
    {S. in = L1. out + 1 } S
    {L. out = S. out }
    L → {S. in = L. in }S {L. out = S. out }

    示例5:给出下列文法的 SDT

    为文法
    S → ( L ) | a
    L → L , S | S
    写一个翻译方案,它输出括号的对数。

    num 为综合属性。

    S’ → S {print (S. num)}
    S → ( L ) { S. num = L.num + 1}
    S → a {S. num = 0}
    L → L1 , S { L. num = L1. num + S. num}
    L → S { L. num = S.num }


    中间代码生成

    中间代码生成概述

    “中间代码生成”程序的任务是:把经过语法分析和语义分析而获得的源程序中间表示翻译为中间代码表示。

    方法:语法制导翻译。

    采用独立于机器的中间代码的好处:

    1. 便于编译系统建立和编译系统的移植;
    2. 便于进行独立于机器的代码优化工作。

    中间表示

    优点: 容易为不同目标机器开发不同后端
    缺点: 编译过程变慢 (因为中间步骤)

    中间表示:

    • 语法树:抽象语法树
      • 反映了抽象的语法结构,而分析树反映的是具体的语法结构。语法树是分析树的抽象形式或压缩形式。
      • 语法规则中包含的某些符号可能起标点符号作用,也可能起解释作用
    • 三地址代码表示
      • 四元式
      • 三元式
      • 间接三元式

    语法分析树,抽象语法树,有向无环图(DAG)

    抽象语法树(或者简称为语法树)反映了抽象的语法结构,而语法分析树(分析树)反映的是具体的语法结构。语法树是分析树的抽象形式或压缩形式。

    • ((a)+(b))的语法分析树和抽象语法树

    在这里插入图片描述

    • 有向无环图

    在这里插入图片描述

    三地址码的实现

    四元式 op, arg1, arg2, result

    在这里插入图片描述

    三元式 op, arg1, arg2

    三元式可以避免引入临时变量,使用获得变量值的位置来引用前面的运算结果。

    在这里插入图片描述

    间接三元式 间接码表+三元式表

    包含一个指向三元式的指针列表,而不是列出三元式序列本身。

    在这里插入图片描述

    类型和声明

    类型检查:利用一组逻辑规则来确定程序在运行时的行为,保证运算分量的类型和运算符的预期类型匹配。

    翻译时的应用:

    • 确定一个名字需要的存储空间
    • 计算一个数组元素引用的地址
    • 插入显式的类型转换
    • 选择算术运算符的正确版本

    类型构造符

    • 数组
    • 笛卡尔积
    • 记录
    • 指针
    • 函数

    类型表达式示例

    int[2][3] array(2,array(3,integer))
    int *f(char a, char b) (char×char) → pointer(integer)
    typedef struct person={
    char name[8];
    int sex;
    int age;
    }
    struct person table[50];
    person record( (name × array(8,char)) × (sex × integer) × (age × integer))
    table array(50,person)

    类型等价

    类型等价:结构等价 + 名等价
    结构等价:满足以下条件之一:(类型名被类型表达式所代替,if 替换所有名字后,两个类型表达式结构上等价即结构等价)

    • 相同的基本类型
    • 将相同类型构造算子应用于等价的类型而构建的
    • 一个类型是另一个类型表达式的名字
      名等价:满足前两个条件(将每个类型名看作是可区分的类型,名字完全相同即名等价)

    在这里插入图片描述

    计算类型及其宽度的语法制导翻译

    T → B { t = B.type; w = B.width;}
    C { T.type = C.type; T.width = C.width;}
    B → int { B.type = integer; B.width = 4;}
    B → float { B.type = float; B.width = 8;}
    C → ε { C.type = t; C.width = w;}
    C → [num] C1 { C.type = array( num.vale, C1.type);
    C.width = num.value × C1.width;}

    习题

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述


    运行存储分配

    运行存储分配概述

    运行时刻环境

    • 为源程序中命名的对象分配安排存储位置
    • 确定目标程序访问变量时使用的机制
    • 过程之间的连接
    • 参数传递

    主题

    • 存储管理:栈分配、堆管理、垃圾回收
    • 对变量、数据的访问

    静态和动态存储

    • 静态分配

      • 编译器在编译时刻就可以做出存储分配决定,不需要考虑程序运行时刻的情形
      • 全局变量
      • 静态分配给语言带来限制
        • 递归过程不被允许
        • 数据对象的长度和它在内存中位置的限制,必须是在编译时可以知道的
        • 数据结构不能动态建立
    • 动态分配

      • 栈式存储:和过程的调用/返回同步进行分配和回收,值的生命期和过程生命期相同
      • 堆存储:数据对象比创建它的过程调用更长寿

    堆空间:存储管理器

    堆空间,用于存放生命周期不确定、或生存到被明确删除为止的数据对象。

    存储管理器基本功能

    • 分配:为每个内存请求分配一段连续的、适当大小的堆空间。
      • 首先从空闲的堆空间分配;
      • 如果不行则从操作系统中获取内存、增加堆空间。
    • 回收:把被回收的空间返回空闲空间缓冲池,以满足其他内存需求。

    评价存储管理器的特性:

    • 空间效率:使程序需要的堆空间最小,即减小碎片
    • 程序效率:充分运用内存系统的层次,提高效率
    • 低开销:使分配/收回内存的操作尽可能高效

    两大问题:

    • 内存泄露:未能删除不可能再被引用的数据
    • 悬空指针引用:引用已被删除的数据

    其他问题

    • 空指针访问/数组越界访问

    代码生成

    代码生成器概述

    • 根据中间表示生成代码
    • 代码生成器之前可能有一个优化组件
    • 代码生成器的三个任务
      • 指令选择:选择适当的指令实现IR语句
      • 寄存器分配和指派:把哪个值放在哪个寄存器中
      • 指令排序:按照什么顺序安排指令执行

    静态/栈式数据区分配

    活动记录静态分配:每个过程静态地分配一个数据区域,开始位置用staticArea表示。

    活动记录栈式分配:

    • 寄存器SP指向栈顶
    • 第一个过程(main)初始化栈区
    • 过程调用指令序列
    • 返回指令序列

    基本块相关的代码生成

    中间代码的流图表示法

    • 中间代码划分成为基本块(basic block),其特点是单入口单出口,即:
      • 控制流只能从第一个指令进入
      • 除了基本块最后一个指令,控制流不会跳转/停机
    • 流图中结点是基本块,边指明了哪些基本块可以跟在一个基本块之后运行

    流图可作为优化的基础

    • 它指出了基本块之间的控制流
    • 可根据流图了解一个值是否会被使用等信息

    划分基本块的算法

    确定首指令(基本块的第一个指令)符合以下任一条:

    • 中间代码的第一个三地址指令
    • 任意一个条件或无条件转移指令的目标指令
    • 紧跟在一个条件/无条件转移指令之后的指令

    确定基本块

    • 每个首指令对应于一个基本块:从首指令(包含)开始到下一个首指令(不含)

    基本块划分示例

    在这里插入图片描述

    窥孔优化

    • 消除冗余指令
    • 消除不可达指令
    • 控制流优化
    • 代数化简/强度消减
    • 机器特有指令的使用

    简单的代码生成算法

    重要子函数:getReg(I)

    • 为三地址指令I选择寄存器;
    • 根据寄存器描述符和地址描述符、以及数据流信息来分配最佳的寄存器;
    • 得到的机器指令的质量依赖于getReg函数选取寄存器的算法

    代码生成时必须更新寄存器描述符和地址描述符。


    代码优化

    代码优化概述

    通过一些相对低层的语义等价转换来优化代码。

    • 公共子表达式消除
    • 复制传播
    • 死代码消除
    • 代码移动
    • 归纳变量和强度消减
    • 常量折叠

    附录

    作业一

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    作业二

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • C/C++程序编译过程详解

    万次阅读 多人点赞 2017-11-13 14:51:06
    C/C++程序编译过程详解 C语言的编译链接过程要把我们编写的一个c程序(源代码)转换成可以在硬件上运行的程序(可执行代码),需要进行编译和链接。编译就是把文本形式源代码翻译为机器语言形式的目标文件...

    C/C++程序编译过程详解

    C语言的编译链接过程要把我们编写的一个c程序(源代码)转换成可以在硬件上运行的程序(可执行代码),需要进行编译和链接。编译就是把文本形式源代码翻译为机器语言形式的目标文件的过程。链接是把目标文件、操作系统的启动代码和用到的库文件进行组织,形成最终生成可执行代码的过程。过程图解如下:

    clip_image002

    从图上可以看到,整个代码的编译过程分为编译和链接两个过程,编译对应图中的大括号括起的部分,其余则为链接过程。

    1. 编译过程

    编译过程又可以分成两个阶段:编译和汇编。

    编译

    编译是读取源程序(字符流),对之进行词法和语法的分析,将高级语言指令转换为功能等效的汇编代码,源文件的编译过程包含两个主要阶段:

    编译预处理

    读取c源程序,对其中的伪指令(以# 开头的指令)和特殊符号进行处理。

    伪指令主要包括以下四个方面:

    1) 宏定义指令,如# define Name TokenString,# undef等。

    对于前一个伪指令,预编译所要做的是将程序中的所有Name用TokenString替换,但作为字符串常量的 Name则不被替换。对于后者,则将取消对某个宏的定义,使以后该串的出现不再被替换。

    2) 条件编译指令,如# ifdef,# ifndef,# else,# elif,# endif等。

    这些伪指令的引入使得程序员可以通过定义不同的宏来决定编译程序对哪些代码进行处理。预编译程序将根据有关的文件,将那些不必要的代码过滤掉。

    3) 头文件包含指令,如# include "FileName" 或者# include < FileName> 等。

    在头文件中一般用伪指令# define定义了大量的宏(最常见的是字符常量),同时包含有各种外部符号的声明。

    采用头文件的目的主要是为了使某些定义可以供多个不同的C源程序使用。因为在需要用到这些定义的C源程序中,只需加上一条# include语句即可,而不必再在此文件中将这些定义重复一遍。预编译程序将把头文件中的定义统统都加入到它所产生的输出文件中,以供编译程序对之进行处理。

    包含到c源程序中的头文件可以是系统提供的,这些头文件一般被放在/ usr/ include目录下。在程序中# include它们要使用尖括号(< >)。另外开发人员也可以定义自己的头文件,这些文件一般与c源程序放在同一目录下,此时在# include中要用双引号("")。

    4) 特殊符号,预编译程序可以识别一些特殊的符号。

    例如在源程序中出现的LINE标识将被解释为当前行号(十进制数),FILE则被解释为当前被编译的C源程序的名称。预编译程序对于在源程序中出现的这些串将用合适的值进行替换。

    预编译程序所完成的基本上是对源程序的“替代”工作。经过此种替代,生成一个没有宏定义、没有条件编译指令、没有特殊符号的输出文件。这个文件的含义同没有经过预处理的源文件是相同的,但内容有所不同。下一步,此输出文件将作为编译程序的输入而被翻译成为机器指令。

    编译、优化阶段

    经过预编译得到的输出文件中,只有常量;如数字、字符串、变量的定义,以及C语言的关键字,如main, if , else , for , while , { , } , + , - , * , \ 等等。

    编译程序所要作得工作就是通过词法分析和语法分析,在确认所有的指令都符合语法规则之后,将其翻译成等价的中间代码表示或汇编代码。

    优化处理是编译系统中一项比较艰深的技术。它涉及到的问题不仅同编译技术本身有关,而且同机器的硬件环境也有很大的关系。优化一部分是对中间代码的优化。这种优化不依赖于具体的计算机。另一种优化则主要针对目标代码的生成而进行的。

    对于前一种优化,主要的工作是删除公共表达式、循环优化(代码外提、强度削弱、变换循环控制条件、已知量的合并等)、复写传播,以及无用赋值的删除,等等。

    后一种类型的优化同机器的硬件结构密切相关,最主要的是考虑是如何充分利用机器的各个硬件寄存器存放有关变量的值,以减少对于内存的访问次数。另外,如何根据机器硬件执行指令的特点(如流水线、RISC、CISC、VLIW等)而对指令进行一些调整使目标代码比较短,执行的效率比较高,也是一个重要的研究课题。

    经过优化得到的汇编代码必须经过汇编程序的汇编转换成相应的机器指令,方可能被机器执行。

    汇编

    汇编过程实际上指把汇编语言代码翻译成目标机器指令的过程。对于被翻译系统处理的每一个C语言源程序,都将最终经过这一处理而得到相应的目标文件。目标文件中所存放的也就是与源程序等效的目标的机器语言代码。

    目标文件由段组成。通常一个目标文件中至少有两个段:

    1) 代码段:该段中所包含的主要是程序的指令。该段一般是可读和可执行的,但一般却不可写。

    2) 数据段:主要存放程序中要用到的各种全局变量或静态的数据。一般数据段都是可读,可写,可执行的。

    UNIX环境下主要有三种类型的目标文件:

    1) 可重定位文件

    其中包含有适合于其它目标文件链接来创建一个可执行的或者共享的目标文件的代码和数据。

    2) 共享的目标文件

    这种文件存放了适合于在两种上下文里链接的代码和数据。

    第一种是链接程序可把它与其它可重定位文件及共享的目标文件一起处理来创建另一个目标文件;

    第二种是动态链接程序将它与另一个可执行文件及其它的共享目标文件结合到一起,创建一个进程映象。

    3) 可执行文件

    它包含了一个可以被操作系统创建一个进程来执行之的文件。

    汇编程序生成的实际上是第一种类型的目标文件。对于后两种还需要其他的一些处理方能得到,这个就是链接程序的工作了。

    2. 链接过程

    由汇编程序生成的目标文件并不能立即就被执行,其中可能还有许多没有解决的问题。

    例如,某个源文件中的函数可能引用了另一个源文件中定义的某个符号(如变量或者函数调用等);在程序中可能调用了某个库文件中的函数,等等。所有的这些问题,都需要经链接程序的处理方能得以解决。

    链接程序的主要工作就是将有关的目标文件彼此相连接,也即将在一个文件中引用的符号同该符号在另外一个文件中的定义连接起来,使得所有的这些目标文件成为一个能够被操作系统装入执行的统一整体。

    根据开发人员指定的同库函数的链接方式的不同,链接处理可分为两种:

    1) 静态链接

    在这种链接方式下,函数的代码将从其所在的静态链接库中被拷贝到最终的可执行程序中。这样该程序在被执行时这些代码将被装入到该进程的虚拟地址空间中。静态链接库实际上是一个目标文件的集合,其中的每个文件含有库中的一个或者一组相关函数的代码。

    2) 动态链接

    在此种方式下,函数的代码被放到称作是动态链接库或共享对象的某个目标文件中。链接程序此时所作的只是在最终的可执行程序中记录下共享对象的名字以及其它少量的登记信息。在此可执行文件被执行时,动态链接库的全部内容将被映射到运行时相应进程的虚地址空间。动态链接程序将根据可执行程序中记录的信息找到相应的函数代码。

    对于可执行文件中的函数调用,可分别采用动态链接或静态链接的方法。使用动态链接能够使最终的可执行文件比较短小,并且当共享对象被多个进程使用时能节约一些内存,因为在内存中只需要保存一份此共享对象的代码。但并不是使用动态链接就一定比使用静态链接要优越。在某些情况下动态链接可能带来一些性能上损害。

    3. GCC的编译链接

    我们在linux使用的gcc编译器便是把以上的几个过程进行捆绑,使用户只使用一次命令就把编译工作完成,这的确方便了编译工作,但对于初学者了解编译过程就很不利了,下图便是gcc代理的编译过程:

    clip_image004

    从上图可以看到:

    1) 预编译

    将.c 文件转化成 .i文件

    使用的gcc命令是:gcc –E

    对应于预处理命令cpp

    2) 编译

    将.c/.h文件转换成.s文件

    使用的gcc命令是:gcc –S

    对应于编译命令 cc –S

    3) 汇编

    将.s 文件转化成 .o文件

    使用的gcc 命令是:gcc –c

    对应于汇编命令是 as

    4) 链接

    将.o文件转化成可执行程序

    使用的gcc 命令是: gcc

    对应于链接命令是 ld

    总结起来编译过程就上面的四个过程:预编译处理(.c) --> 编译、优化程序(.s、.asm)--> 汇编程序(.obj、.o、.a、.ko) --> 链接程序(.exe、.elf、.axf等)。

    4. 总结

    C语言编译的整个过程是非常复杂的,里面涉及到的编译器知识、硬件知识、工具链知识都是非常多的,深入了解整个编译过程对工程师理解应用程序的编写是有很大帮助的,希望大家可以多了解一些,在遇到问题时多思考、多实践。

    一般情况下,我们只需要知道分成编译和链接两个阶段,编译阶段将源程序(*.c) 转换成为目标代码(一般是obj文件,至于具体过程就是上面说的那些阶段),链接阶段是把源程序转换成的目标代码(obj文件)与你程序里面调用的库函数对应的代码连接起来形成对应的可执行文件(exe文件)就可以了,其他的都需要在实践中多多体会才能有更深的理解。

     


    C/C++编译过程

    C/C++编译过程主要分为4个过程 
    1) 编译预处理 
    2) 编译、优化阶段 
    3) 汇编过程 
    4) 链接程序

    一、编译预处理

    (1)宏定义指令,如#define Name TokenString,#undef等。 对于前一个伪指令,预编译所要做的是将程序中的所有Name用TokenString替换,

    但作为字符串常量的 Name则不被替换。对于后者,则将取消对某个宏的定义,使以后该串的出现不再被替换。

    (2)条件编译指令,如#ifdef,#ifndef,#else,#elif,#endif等。 这些伪指令的引入使得程序员可以通过定义不同的宏来决定编译程序对哪些代码进行处理。

    预编译程序将根据有关的文件,将那些不必要的代码过滤掉

    (3) 头文件包含指令,如#include "FileName"或者#include <FileName>等。 在头文件中一般用伪指令#define定义了大量的宏(最常见的是字符常量),

    同时包含有各种外部符号的声明。 包含到c源程序中的头文件可以是系统提供的,这些头文件一般被放在/usr/include目录下。

    在程序中#include它们要使用尖括号(< >)。

    另外开发人员也可以定义自己的头文件,这些文件一般与c源程序放在同一目录下,此时在#include中要用双引号("")。

    (4)特殊符号,预编译程序可以识别一些特殊的符号。 例如在源程序中出现的#line标识将被解释为当前行号(十进制数), 
    上面程序实现了对宏line的运用

    (5)预处理模块 预处理工作由#pragma命令完成,#Pragma命令将设定编译器的状态或者是指示编译器完成一些特定的动作。

    #pragma指令对每个编译器给出了一个方法,在保持与C和C++语言完全兼容的情况下,给出主机或操作系统专有的特征。

    依据定义,编译指示是机器或操作系统专有的,且对于每个编译器都是不同的。 
    打开C标准库函数,如stdio.h,我们总能找到下面这一句指示编译器初始化堆栈

    复制代码
    #include "iostream"
    #line 100
    using namespace std;
    int main(int argc, char* argv[])
    {
    cout<<"__LINE__:"<<__LINE__<<endl;
    return 0;
    }
    复制代码

    /*-------------------- 
    * 输出结果为: 
    * __LINE__:103 
    * 本来输出的结果应该是 7,但是用#line指定行号之后,使下一行的行号变为, 
    * 到输出语句恰为行103 
    ---------------------*/ 
    C/C++编译过程 
    或者程序指示编译器去链接系统动态链接库或用户自定义链接库 
    二、编译、优化阶段 
    经过预编译得到的输出文件中,只有常量;如数字、字符串、变量的定义,以及C语言的关键字,如main,if,else,for,while,{,}, +,-,*,\等等。 
    在《编译原理》中我们可以了解到一个编译器对程序代码的编译主要分为下面几个过程: 
    a) 词法分析 
    b) 语法分析 
    c) 语义分析 
    d) 中间代码生成 
    e) 代码优化 
    f) 代码生成 
    g) 符号表管理 
    h) 将多个步骤组合成趟 
    i) 编译器构造工具
     
    在这里我们主要强调对函数压栈方式(函数调用约定)的编译处理 
    C与C++语言调用方式大体相同,下面是几种常用的调用方式:

    __cdecl 是C DECLaration的缩写(declaration,声明),表示C语言默认的函数调用方法:所有参数从右到左依次入栈,

    这些参数由调用者清除,称为手动清栈。被调用函数不需要求调用者传递多少参数,调用者传递过多或者过少的参数,

    甚至完全不同的参数都不会产生编译阶段的错误。

    _stdcall 是StandardCall的缩写,是C++的标准调用方式:所有参数从右到左依次入栈,如果是调用类成员的话,

    最后一个入栈的是this指针。这些堆栈中的参数由被调用的函数在返回后清除,使用的指令是 retnX,X表示参数占用的字节数,

    CPU在ret之后自动弹出X个字节的堆栈空间。称为自动清栈。函数在编译的时候就必须确定参数个数,

    并且调用者必须严格的控制参数的生成,不能多,不能少,否则返回后会出错。

    PASCAL 是Pascal语言的函数调用方式,在早期的c/c++语言中使用这种调用方式,

    参数压栈顺序与前两者相反,但现在我们在程序中见到的都是它的演化版本,其实 

    复制代码
    #pragma comment(lib,_T("GDI32.lib"))
    #ifdef _MSC_VER
    /*
    * Currently, all MS C compilers for Win32 platforms default to 8 byte
    * alignment.
    */
    #pragma pack(push,_CRT_PACKING)
    #endif /* _MSC_VER */
    复制代码

    C/C++编译过程 
    质是另一种调用方式 
    _fastcall是编译器指定的快速调用方式。由于大多数的函数参数个数很少,使用堆栈传递比较费时。因此_fastcall通常规定将前两个(或若干个)参数由寄存器传递,其余参数还是通过堆栈传递。不同编译器编译的程序规定的寄存器不同。返回方式和_stdcall相当。 
    _thiscall 是为了解决类成员调用中this指针传递而规定的。_thiscall要求把this指针放在特定寄存器中,该寄存器由编译器决定。VC使用ecx,Borland的C++编译器使用eax。返回方式和_stdcall相当。 
    _fastcall 和 _thiscall涉及的寄存器由编译器决定,因此不能用作跨编译器的接口。所以Windows上的COM对象接口都定义为_stdcall调用方式。 
    C中不加说明默认函数为_cdecl方式(C中也只能用这种方式),C++也一样,但是默认的调用方式可以在IDE环境中设置。简单的我们可以从printf函数看出 
    printf使用从从左至右压栈,返回int型并由_CRTIMP指定封在动态链接库中。 
    通过金典的hello world程序我们可以知道编译器对其argc和argv[]这两个参数进行了压栈,并且argc留在了栈顶 
    优化处理是编译系统中一项比较艰深的技术。它涉及到的问题不仅同编译技术本身有关,而且同机器的硬件环境也有很大的关系。优化处理主要分为下面几个过程: 
    1) 局部优化 
    a) 基本块的划分 
    b) 基本块的变换 
    c) 基本块的DAG表示 
    d) DAG的应用 
    e) 构造算法讨论 
    2) 控制流分析和循环优化 
    a) 程序流图与循环 
    复制代码
    /*金典的hello world*/
    #include <stdio.h>
    int main(int argc, char* argv[])
    {
    printf("hello world");
    return 0;
    }
    _Check_return_opt_ _CRTIMP int __cdecl printf(_In_z_ _Printf_format_string_ const char * _Format, ...);
    #define CALLBACK _stdcall /* Windows程序回调函数*/
    #define WINAPI _stdcall
    #define WINAPIV _cdecl
    #define PASCAL _stdcall /*在c++语言中使用了StandardCall调用方式*/
    #define PASCAL _cdecl/*在c语言中使用了C DECLaration调用方式*/
    复制代码

    C/C++编译过程 
    b) 循环 
    c) 循环的查找 
    d) 可归约流图 
    e) 循环优化 
    3) 数据流的分析与全局优化 
    a) 一些主要的概念 
    b) 数据流方程的一般形式 
    c) 到达一定值数据流方程 
    d) 可用表达式及其数据流方程 
    e) 活跃变量数据流方程 
    f) 复写传播
     
    经过优化得到的汇编代码必须经过汇编程序的汇编转换成相应的机器指令,方可能被机器执行。

    三、汇编过程

    汇编过程实际上指把汇编语言代码翻译成目标机器指令的过程。对于被翻译系统处理的每一个C语言源程序,

    都将最终经过这一处理而得到相应的目标文件。目标文件中所存放的也就是与源程序等效的目标的机器语言代码。

    目标文件由段组成。通常一个目标文件中至少有两个段: 代码段:该段中所包含的主要是程序的指令。

    该段一般是可读和可执行的,但一般却不可写。 数据段:主要存放程序中要用到的各种全局变量或静态的数据。一般数据段都是可读,可写,可执行的。

    四、链接程序

    由汇编程序生成的目标文件并不能立即就被执行,其中可能还有许多没有解决的问题。

    例如,某个源文件中的函数可能引用了另一个源文件中定义的某个符号(如变量或者函数调用等);

    在程序中可能调用了某个库文件中的函数,等等。所有的这些问题,都需要经链接程序的处理方能得以解决。

    链接程序的主要工作就是将有关的目标文件彼此相连接,也即将在一个文件中引用的符号同该符号在另外一个文件中的定义连接起来,

    使得所有的这些目标文件成为一个能够诶操作系统装入执行的统一整体。

    根据开发人员指定的同库函数的链接方式的不同,链接处理可分为两种:

    (1)静态链接 在这种链接方式下,函数的代码将从其所在地静态链接库中被拷贝到最终的可执行程序中。

    这样该程序在被执行时这些代码将被装入到该进程的虚拟地址空间中。静态链接库实际上是一个目标文件的集合,

    其中的每个文件含有库中的一个或者一组相关函数的代码。

    (2) 动态链接 
    在此种方式下,函数的代码被放到称作是动态链接库或共享对象的某个目标文件中。链接程序此时所作的只是在最终的可执行程序中记录下共享对象的名字以及其它少量的登记信息。在此可执行文件被执行时,动态链接库的全部内容将被映射到运行时相应进程的虚地址空间。动态链接程序将根据可执行程序中记录的信息找到相应的函数代码。C/C++编译过程对于可执行文件中的函数调用,可分别采用动态链接或静态链接的方法。使用动态链接能够使最终的可执行文件比较短小,并且当共享对象被多个进程使用时能节约一些内存,因为在内存中只需要保存一份此共享对象的代码。但并不是使用动态链接就一定比使用静态链接要优越。在某些情况下动态链接可能带来一些性能上损害。

    ----------------------------------------------------作者  张彦升

    转自:https://www.cnblogs.com/mickole/articles/3659112.html

    展开全文
  • 程序的编译与执行过程

    千次阅读 2018-02-25 23:36:43
    本文以C程序为例。 构建C程序需要4个步骤,分别使用4个工具完成: preprocessor, ...第二步,编译. 将第一步产生的文件连同其他源文件一起编译成汇编代码。 第三步,汇编。将第二步产生的汇编源码转换为 object fi...
  • 看完这篇文章之后,终于明白了编译到底怎么回事。 1 对于同一个语句,有如下三种:高级语言、低级语言、机器语言的表示 C语言  a=b+1; 汇编语言  mov -0xc(%ebp),%eax add $0x1,%eax mov %eax,-...
  • 编译

    2020-06-21 00:51:47
    问题解答 (1): cpu 可以解析运行的程序形式称为什么代码? 1.... C语言中,通过编译.c文件,得到.obj目标文件.目标文件的内容就是本地代码 (4): 把多个文件收录在一起的文件称为什么? 1. 库文件 2.
  • 深入理解程序从编译到运行

    万次阅读 多人点赞 2017-10-17 10:47:18
    From:http://blog.chinaunix.net/uid-22327815-id-3540305.html 从Hello World说程序运行机制:http://www.sohu.com/a/132798003_505868 C/C++中如何在main()函数之前执行一条语句?...(深入理解计算机系统...
  • 编译

    2018-09-02 15:20:16
    之前我们分析过模板到真实 DOM 渲染的过程,中间有⼀个环节是把模板编译成 render 函数,这个 过程我们把它称作编译。 虽然我们可以直接为组件编写 render 函数,但是编写 template 模板更加直观,也更符合...
  • 编译和链接的过程

    万次阅读 多人点赞 2018-07-22 23:08:24
    程序要运行起来,必须要经过四个步骤:预处理、编译、汇编和链接。接下来通过几个简单的例子来详细讲解一下这些过程。 对于上边用到的几个选项需要说明一下。 使用 gcc 命令不跟任何的选项的话,会默认执行...
  • 编译原理学习(一)--编译以及编译过程

    万次阅读 多人点赞 2018-05-22 21:01:00
    【龙书】编译原理(第二版)学习与理解:1.也许我们这辈子都不会去实现一个编译器,但是我们至少要知道编译器是什么?为什么会需要编译器? ①编译器首先也是一种电脑程序。它会将用某种编程语言写成的源代码(原始...
  • 编译执行和解释执行

    千次阅读 多人点赞 2019-07-09 15:19:41
    一、编译和解释 编译:将源代码一次性转换成目标代码的过程 类似英语中的全文翻译。 执行编译过程的程序叫做编译器。 解释:将源代码逐条转换成目标代码同时逐条运行的过程。 类似英语中的同声传译。 ...
  • Android反编译工具包(升级)官方绿色版

    万次下载 热门讨论 2012-10-10 19:18:30
    Android反编译工具包,内含图形和命令两种反编译方式,命令支持windows和linux平台,亲测验证成功!详见博客:Android APK反编译详解(附图) http://blog.csdn.net/sunboy_2050/article/details/6727581
  • apktool 反编译工具 绿色版

    万次下载 热门讨论 2014-03-11 20:18:37
    apktool功能:反编译出apk资源文件。 使用方式: 把apktool 解压到任意位置 执行 在dos 改目录下 执行 apktool d xxx.apk test ,便会把编译后的资源存入test文件夹下。
  • (精华)2020年9月2日 .NET Core 源码编译

    万次阅读 2020-09-01 22:09:08
    if (!(Test-Path -Path $PROFILE)) { New-Item -ItemType File -Path $PROFILE -Force }
  • 2020年支持java8的Java反编译工具汇总

    万次阅读 多人点赞 2018-06-29 10:58:53
    luyten是一款操作简单、功能实用的java反编译工具,软件支持*.JAR、*.zip、*.class等类型文件的反编译操作,还原度非常高,支持更多功能设置,如显式导入、类型、合成组件等等,用户可根据不同的需求选择合适的显示...
  • Android APK反编译详解(附图)

    万次阅读 多人点赞 2011-08-28 22:42:11
    这段时间在学Android应用开发,在想既然是用Java开发的应该很好反编译从而得到源代码吧,google了一下,确实很简单,以下是我的实践过程。在此郑重声明,贴出来的目的不是为了去破解人家的软件,完全是一种学习的...
  • APK反编译

    万次阅读 多人点赞 2017-12-27 17:31:39
    学习和开发Android应用有一段时间了,今天写一篇博客总结一下Android的apk文件反编译。我们知道,Android应用开发完成之后,我们最终都会将应用打包成一个apk文件,然后让用户通过手机或者平板电脑下载下来进行安装...
  • 我们都知道,Android程序打完包之后得到的是一个APK文件,这个文件是可以直接安装到任何Android手机上的,我们反编译其实也就是对这个APK文件进行反编译。Android的反编译主要又分为两个部分,一个是对代码的反编译...
  • Android APK反编译就这么简单 详解(附图)

    万次阅读 多人点赞 2014-03-11 22:06:09
    你往往会去借鉴别人的应用是怎么开发的,那些漂亮的动画和精致的布局可能会让你爱不释手,作为一个开发者,你可能会很想知道这些效果界面是怎么去实现的,这时,你便可以对改应用的APK进行反编译查看。下面是我参考...

空空如也

1 2 3 4 5 ... 20
收藏数 3,346,316
精华内容 1,338,526
关键字:

编译