编译原理笔记1:概述编译相关的基本知识

By | 2020年4月5日

博主的个人课堂学习笔记。水平有限(又是焦虑得睡不着觉的一天),如有谬误还请高人指点,将感激不尽。

编译器的工作步骤

在开始说任何东西之前,我们先来大致看一下编译器是怎么工作的——从代码到程序,大概要经过下面这样的步骤——这里用粗浅的语言进行解释,先有个印象即可,后面还会提到

  • 词法分析:编程语言的语句,由一堆堆的单词组成——比如变量类型名、变量名、函数名、值、符号等。既然我们要让机器来分析源程序然后编译,那么就需要首先让计算机能够明白我们写的语句是什么意思,而理解语句的第一步就是理解每个词。所谓语法分析,进行的工作就是让计算机识别单词;
  • 语法分析:完成词法分析,就要通过语法分析来识别语句的结构;
  • 语义分析:该步骤的目标,就是确定“某一条语句是什么意思”,检查一下说的有没有不合法的地方;
  • 符号表管理:相当于字典。符号表用于各个阶段查找、填写;
  • 出错处理:在出现错误时的处理。种类可分词法错误、语法错误、静态/动态语义错误;
  • 中间代码(可选)可以为优化提供支持。中间代码接近于目标语言,却又与具体硬件对应的机器指令无关,便于优化和代码生成。中间代码优化是对指令进行等价变化,提高运行效率;
  • 中间代码经过优化,就可以生成目标代码了。比如二进制程序的机器码,或者各种 VM 用的字节码。

词法分析器 Lex 和词法分析器 Yacc:

Lex(Lexical Analyzar) 是词法分析器, Yacc(Yet Another Compiler Compiler) 是语法分析器。
虽然从名字上看,这两个东西就已经是“分析器”了,然而实际上并不是,他们是用来生成“分析器”的工具。Lex 是用来生成词法分析器的工具,Yacc 是用来生成语法分析器的工具。
这两个工具可以根据我们输入的词法 / 语法规则,自动生成相应的语法分析器、词法分析器,然后这些分析器就可以帮助我们简单地完成对源代码的词法、语法分析。
因这两样工具的存在,开发编译器、解释器的词语法分析器的难度被极大降低。在现代编译器、解释器的开发中,真正有难度的地方在于语义分析和后期优化。

Lex 正规式示例:

在 Lex 中,我们可以使用一种被称为“正规式”的字符串,来简单地定义“某种符号应该长成什么样子”。
我们先直接体验一下。
比如下面这个实际定义 Number 和 Identifier 的例子:

Yacc 的产生式示例:

Yacc 用如下这种形式来定义“一个表达式应该长成什么样子”:
E : E '+' E | E '*' E | id
这段代码说明,一个表达式 E 可以有三种情况组成:最简单的情况就是 id 。一个变量 x ,他自己就是一个表达式,两个表达式相加是一个表达式,两个表达式相乘还是一个表达式。

对于这个产生式,如果我们写x-y就是不合法的——因为我们并没有定义两个表达式可以被 ‘-‘ 连接

例:对于 Yacc 而言,-x–y也是合法的。对于表达式“-2–3”,这里的减号有一元操作也有二元操作,实际计算的情况是这样的:(-2)-(-3 )

语言之间的翻译


高级语言之间可以实现跨语言的翻译。

预编译的例子:sql、c 混合编程。
sql、c 混合编程,实际上的运行方式是先把 sql 变成 c 语言,再对由 sql 转换来的 c 和本来就是 c 的部分进行整体编译。把 sql 转成 c 的过程就叫“预编译”,Lex、Yacc 就是这样的。

在 UltraGram 中,就可以把我们写的 Lex、Yacc 变成合法的 C 代码。我们就可以把这两份代码和我们自己写的 C 代码一起编译,实现开发自己的解释器/编译器。(所以 lex yacc 就是开发解释器编译器这种东西的工具,将曾需要手工实现的词法语法分析自动化实现)。

对于反汇编,编译器为了防止反汇编会在编译时加入一些无效代码。

编译器与解释器

语言翻译

语言翻译分为两种,分别是先翻译后执行和边翻译边执行。二者基本功能相同。且在翻译的角度来看,两种方式涉及的原理、方法、技术都是类似的

先翻译后执行

比如 C 这种需要编译的语言。特点是效率高、省空间。但交互性、动态性差,可移植性也差。。多数语言都是这种。

边翻译边执行

比如 py、js、java 这种使用解释器工作的语言。跟上面的基本相反。

生成字节码然后运行。从高级语言到字节码实际上是翻译,在运行时再从字节码转化成机器码执行。

编译器的工作原理和基本组成

通用程序设计语言的主要成分

语言都由声明、操作两大部分组成,声明+操作=完整定义。

例:过程式语言:

过程式语言有两种语句:声明性语句和操作性语句。前者提供操作对象的性质(比如数据类型、数据值、对象的作用域)。后者则描述各个操作(比如赋值)的次序,进行实际操作。

编译器对上述两种语句使用不同的方式进行处理。对于声明性的,就是给被声明的对象分配一块空间(称为“环境”)。操作则是生成针对环境的可执行代码序列,比如从某个被声明的空间中取值,进行某些运算后将结果放到某个空间中。

因此,“先声明后引用”的规则,能够方便编译器对语言进行处理,也能提升执行效率。

例如,一些语言支持如下操作:

i=10;           // 在没有对 i 进行声明的情况下直接赋整数值
i="abcdefg";    // 直接重新赋字符串值

虽然看起来是两行代码,但是在实际执行中,执行过程是:为整型分配空间->写入整数值10->重新分配空间->写入字符串值。将导致效率的降低。

以阶段划分编译器

编译器的工作过程可以大致划分为四步:词法分析、语法分析、语义分析、目标代码生成。

这个图要背下来。。。。

其中,中间代码生成及其之前的步骤,编译器和解释器可以是一致的。

  • 词法分析:相当于识别每个词代表什么。进行的工作就是识别单词。单词至少分为:关键字、标识符、字面量、特殊符号;
  • 语法分析:识别语句的结构。通常以树的形式表示;
  • 语义分析:前两者正确的情况下,语义未必正确。确保“什么语句是什么意思”——检查结构正确的句子是否语义合法,也可以修改语法树的结构;
  • 符号表管理:相当于字典。符号表用于各个阶段查找、填写;
  • 出错处理:在出现错误时的处理。种类可分词法错误、语法错误、静态/动态语义错误;
  • 中间代码(可选)可以为优化提供支持。中间代码接近于目标语言,却又与具体硬件对应的机器指令无关,便于优化和代码生成。中间代码优化是对指令进行等价变化,提高运行效率。

例:编译器各阶段工作:

  • 词法分析:这里的记号流是一个线性的结构,源代码中的变量名在记号流中被替换为id1、id2这样的标识符。若我们只写一个 real x,在词法分析执行完后仍然是正确的——词法分析只看代码中的单词是否符合规则,而不关心结构。但在语法分析中就过不了了;
  • 语法分析:该步骤,我们将记号流分析为两个语法树。因为句子是有层次关系的,树可以用于描述层次关系。右下角语法树的意思是:对 id3 和 60 使用 * 进行运算,再将结果和 id2 使用 + 进行操作…… 最后赋值给 id1;

  • 语义分析:对语法分析生成的两个语法树进行分析。

语义分析这一步,要看语法结构正确的语法树的含义是否正确——这一步也可以做些附加的操作,比如这里对60的转换,这就是编译器为了简化语言而自动进行的附加工作——对类型进行了自动转换。另又如C语言中,我们可以写 1+2.0 这样的式子,与此同理,也是编译器自动在语义分析时进行了类型转换。

  • 中间代码优化:将4条语句转为了两条;
  • 目标代码生成,解决汇编、可重定位、内存形式(Load-and-Go)问题

编译器的分析/综合模式

编译器可分为前后端,前端进行语言结构和意义的分析,后端进行语言意义的处理。

中间代码是前后端的分界。编译器的基础架构就分为前端、源代码的中间表示和后端。

编译器扫描遍数

“一遍扫描”:每个阶段中,将程序完整分析一遍的工作模式。

比如:

  1. 词法分析阶段,把整个程序转化为记号流,这叫一遍;
  2. 词法分析,对记号流(记号流本身就是一种程序的变体)分析得到语法树,这又叫一遍;
  3. 语义分析,对语法树(语法树是记号流的变体,也就是程序的变体)进行修改,分析得到中间代码,这又叫一遍;

扫描遍数的影响因素:

  1. 软硬件条件:如内存太小或者要做全局优化。想要做比较好的优化就需要全面了解程序,扫描的遍数就要增加;

  2. 语言结构:如果先声明后引用,就只需要扫描一遍;但如果先引用后声明,处理起来就比较复杂,需要多扫描一遍;

  3. 编译技术,比如拉链-回填

    goto lab1;
    ...
    goto lab2;
    ...
    lab1:...
    

    拉链-回填实际上也是先引用后声明,但只需要扫描一遍——当第一次读到引用时,先把后面的目标位置填个问号,读到多次也都填上问号——因为引用了相同的东西,所以这个问号可以“拉成一条链”。当我们确定了lab1的具体标号位置时,就回头把那一串的内容都填上。这并不是第二次扫描,叫做“拉链-回填”

编译器的编写

  1. 直接用语言写;
  2. 使用编译器编写工具:包括语法/词法分析工具、语法制导翻译、代码生成、数据流分析等;
  3. 基于编译器基础架构的编译器构造系统。也就是开放式编译器,比如LLVM、GCC、SUIF等。这样开发,就是自己用工具搞定词法分析、语法分析,再用这玩意做后端,就能开发出来自己的编译器了

写博不易,如果读的开心,可以考虑请我吃包辣条 ~

人间自有真情在,五毛一块也是爱

点击量:332

发表评论

邮箱地址不会被公开。 必填项已用*标注