最新公告
  • 欢迎您光临欧资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 编译器内部一探编译器编译器编译器

    源代码:

    编译器实现之旅 – 第 1 章编译器概述

    编译器,近在咫尺,却又遥不可及。当我们写下任何非机器语言代码时,我们需要一个编译器让它可以被计算机运行。然而,它是一个如此高度使用的程序,我们对此知之甚少。什么是编译器?编译器对我们的代码做了什么?它是如何完成的?如果您有这些疑问并想深入了解编译器的内部结构,请加入我的编译器实现之旅。

    1. 什么是编译器

    从广义上讲,编译器是读取语言 A 代码并输出语言 B 代码的程序。如下所示:

    语言代码 -> | 编译器 | -> B语言代码

    根据定义,A、B 可以是同一种语言。也就是说,如果我们编写一个只有“复制粘贴”功能的程序,它也可以称为编译器。但显然,这样的编译器是没有意义的。在实践中,编译器的输入一般是高级语言代码,如C语言、Python语言等,而编译器的输出一般是低级语言代码,如汇编语言、各种字节码、汇编语言代码由汇编语言编译器不断编译,最终产生机器语言供计算机执行;字节码可以由能够执行字节码的虚拟机执行。这样,一个程序从写入到执行的过程就完成了。

    2. 编译器的结构

    编译器内部不是一个整体,而是多个组件共同完成编译功能。这些组件一般可以分为两部分:编译器前端和编译器后端。如下所示:

    语言代码 -> | 编译器前端 | -> 中间代码 -> | 编译器后端 | -> B语言代码

    由于我们编写的高级语言代码不是编译器的首选形式,所以编译器通过编译器前端对源代码进行读取、检查和重组,使其等价转化为编译器的首选形式,即中间码;通常,编译器前端也会检查语法错误。接下来,编译器后端对中间代码进行进一步的检查和优化,最终生成目标代码。

    其实编译器前端和后端还可以进一步细分为多个组件,我们接下来的行程中会一一介绍。

    3. 我们要实现什么

    在此旅程的最后,我们将为一种称为 CMM(即 C Minus Minus)的语言实现一个编译器,该编译器的输出将是一个指令文件,其中包含我们自己设计的一组指令中的指令。因此,我们还要实现一套虚拟机程序来运行编译器输出的指令文件。

    CMM 语言是通过减少 C 语言的语法得到的语言。其主要特点如下:

    接下来,让我们深入编译器的前端一探究竟。见下一章:

    编译器实现之旅——第 2 章编译器前端概述

    在本章的旅程中,我们将深入了解编译器前端。查看编译器前端包含哪些组件以及它们在做什么。

    1. 编译器前端的结构组成

    看起来比我们想象的要简单,编译器前端只包含两个组件,词法分析器和解析器。请看下图:

    +————+ +————+

    源代码 -> | 词法分析器 | -> 令牌流 -> | 语法分析器 | -> 抽象语法树

    +————+ +————+

    2. 什么是词法分析器

    词法分析器(Lexer)是“前端中的前端”。作为整个编译器的第一个组件,词法分析器负责读取和划分源代码,将编译器视为“胡须和辫子”的源代码划分为一个令牌流。同时,词法分析处理器还负责识别和分类每个token。当然,一旦词法分析器发现不应该存在的字符,它就会生成错误消息。词法分析器的工作内容如下图所示:

    +————+

    源代码 -> | 词法分析器| -> (token-category, token-string), (token-category, token-string), …

    +————+

    我们将在有关词法分析器的相关章节中进一步讲述词法分析器的故事。

    3. 什么是解析器

    源代码被词法器无情切割后c语言实现词法分析器,就到了解析器进来的时候了。不难发现,虽然词法分析器所做的工作很强大,但它只完成了类似于数据清洗的工作,而输出只是一个线性的token流,就像一个没有章节甚至标点符号的大段落。, 根本无法阅读。

    语法分析器利用词法分析器的工作,将线性、扁平的记号流按照语法规则重新组织成一棵巨大的三维树,这就是抽象语法树(AST)。抽象语法树在整个编译器中起着举足轻重的作用,它是整个编译器后端喜欢并需要不断访问的数据结构。解析器的工作内容如下图所示:

    +————+

    (token class, token string), (token class, token string), … -> | 解析器| -> 抽象语法树

    +————+

    我们将在解析器的相关章节中进一步讲述解析器的故事。

    接下来,我们来看看这个“前端中的前端”:词法分析器是如何实现的。见下一章:

    编译器实现之旅 – 第 3 章 实现词法分析器之前的准备工作

    在这一章的旅程中,我们将为整个编译器的“前端中的前端”:词法分析器的实现做好充分准备。

    1. 词法分析器概述

    查看编译器的输入:源代码,不难发现,源代码简直就是一个很长的字符串。说到字符串,不难想到字符串的切分功能。这种类型的拆分函数使用空格或任何字符或字符串作为分隔符将字符串拆分为多个小字符串段。这不是词法分析器吗?你可能在想。但是,我们会遇到这个问题:

    “1 + 1” -> (“1”, “+”, “1”)

    “1+1” -> ?

    确实,上面的第一个字符串使用普通的字符串拆分功能可以很方便的拆分出来,但是我们发现无论怎么设置分隔符c语言实现词法分析器,都无法将第二个字符串拆分成相同的结果。也就是说,普通的字符串切分函数及其算法都不能胜任词法分析器的工作,我们必须另辟蹊径。

    对字符串进行拆分,思路是先找到一个拆分点,然后将字符串从当前起点拆分到拆分点,然后在拆分点之后设置当前起点,继续寻找下一个拆分点,不断这样重复该过程,直到到达字符串的末尾。那么为什么字符串拆分函数不能胜任词法分析器的工作呢?稍微思考一下,不难找到原因:字符串拆分函数“寻找下一个拆分点”的逻辑太简单了,只是一个相等的判断。而我们需要的逻辑比较复杂,比如:看到一个空格,拆分;另一个例子:看到一个不是数字的字符,拆分;等等。因此,只要我们扩展字符串拆分函数“寻找下一个拆分点”的逻辑,

    2. 词法分析器的状态

    我们首先需要做什么?我们需要为词法分析器定义许多不同的状态,不同状态下的词法分析器执行不同的行为。显然,词法分析器需要一个开始状态、一个完成状态,可能还有一个或多个中间状态。词法分析器从开始状态开始,读取源代码中的每个字符,并以完成状态结束,当词法分析器处于完成状态时,它会拆分一个标记。词法分析器继续执行此“开始,…,完成”过程,直到到达字符串的末尾。

    为了准确了解词法分析器需要什么状态,我们需要查看 CMM 语言对标记的定义。请注意这里的token是泛化的,它不仅代表一个英文单词,还代表一个符号、一串数字等,也就是说,一个token就是一个需要词法分析器进行分词的字符串。CMM 语言对令牌的定义如下:

    连续的大写或小写字母字符串

    一串连续的数字

    这些符号:+ – * / < >= == != = ; , ( ) [ ] { }

    /* … */ 形成评论

    关键字:void int if else while return

    这里需要说明的是,所谓的关键字只是上面第1条的一个特例。即:当我们对一个词进行分词时,需要额外判断该词是否为关键词。如果是这样,我们需要将单词的类别从“word”更改为“keyword XX”。例如:当我们拆分字符串“abc”时,我们将其归类为“word”;而当我们拆分字符串“if”时,我们需要将其归类为“keyword if”。

    通过 CMM 语言对标记的定义,我们可以开始思考词法分析器需要什么状态。让我们考虑上面的第一条规则,即:词法分析器需要什么状态来分割一个单词?

    首先,词法分析器从“开始”状态开始。如果此时词法分析器读到一个大写或小写字母,我们就知道下一次读到的是一个词;但同时,仅仅通过读到这个字符,我们永远无法知道当前单词是否被读过;当我们看到一个不是大写或小写字母的字符时,我们只能确定刚才的单词已经被读取,我们应该让词法分析器进入“Done”状态。为了处理这种情况,我们引入了中间状态“正在读取单词”。当词法分析器读到一个大写或小写字母时,应该立即从“开始”状态变为“读词”状态;

    那么,如何利用上面的思路让词法分析器跳过注释呢?请参见:

    首先,词法分析器仍然从“开始”状态开始。当它读到一个“/”时,我们不知道这个“/”是一个除号还是一个注释的开始,所以我们把词法分析器关了起来。进入“读分号”的中间状态。在这种状态下,如果词法分析器读取的下一个字符是“”,那么我们可以确定词法分析器现在已经进入了注释,我们会让词法分析器进入“读取注释”状态;相反,如果词法分析器读取的下一个字符不是“”,我们也可以确定词法分析器这次读取的确实是除法符号。这时候,当然,我们让词法分析器进入“Done”状态。

    当词法分析器处于“阅读评论”状态时,我们需要关注两件事:

    词法分析器应该丢弃它读取的任何字符

    词法分析器应该努力避免注释

    如何逃避评论?显然,如果我们想逃避评论,我们需要同时满足两个条件:

    遇到一个“*”

    然后,遇到另一个“/”

    因此,词法分析器在被困在注释中时,会平等地丢弃所有读到的字符,同时还要注意读到的字符是否为“”。如果是,词法分析器看到了希望。此时,词法分析器应该切换到“escape from comment”状态。在这个状态下,如果词法分析器再次读取到“/”,恭喜,词法分析器已经成功脱离注释,回到它已经达到了久违的“开始”状态;如果不是“/”,希望不是完全丢失。这时候词法分析器如果读到“”,应该还是停留在“escape from comments”状态;如果既没有读取“/”也没有读取“*”,那么不幸的是,转义完全失败,词法分析器回退到“

    使用上面的思路来推断其他情况,我们可以得到词法分析器需要的所有状态。请参见:

    显然,我们需要“开始”和“完成”状态

    为了读取单词和数字,我们需要“正在读取单词”和“正在读取数字”状态

    处理评论相关的问题,我们需要“阅读划分”、“阅读评论”和“转义评论”状态

    为了知道词法分析器是在读取“=”、“=”还是“==”,我们需要“读取小于”、“读取大于”和“读取等于”状态

    为了让词法分析器正确读取“!=”(而不是“!”+其他错误符号),我们需要“读取不等式”状态

    至此,我们拥有了词法分析器需要的所有状态。代码如下所示:

    枚举类 LEXER_STAGE

    {

    // 开始

    开始,

    // abc…

    // ^^^^^

    IN_ID,

    // 123…

    // ^^^^^

    IN_NUMBER,

    // /?

    // ^

    IN_DIVIDE,

    // /* …

    // ^^^

    IN_COMMENT,

    // … */

    // ^

    END_COMMENT,

    // // ^

    不到,

    // >?

    // ^

    IN_GREATER,

    // =?

    // ^

    IN_ASSIGN,

    // !?

    // ^

    IN_NOT,

    // 完毕

    完毕,

    };

    3. 令牌类型

    当词法分析器读取一个标记时,我们需要对其进行分类。在词法分析器的各种状态的帮助下,这种分类变得非常容易。比如,当我们从“读号”状态移动到“完成”状态时,当然知道token的当前类别是“号”;而当我们读到一个“(”时,我们当然也知道这个token的类是“左括号”;等等。我们可以从上面给出的token的定义中得到所有token的类。代码看起来像这:

    枚举类 TOKEN_TYPE

    {

    // 单词

    标识,//标识

    NUMBER, // 数字

    //关键词

    无效,//无效

    INT, // 整数

    如果如果

    否则,//否则

    虽然,//同时

    返回, // 返回

    // 操作员

    加号,// +

    减, // –

    相乘,// *

    除法,///

    少,// <

    LESS_EQUAL, //

    GREATER_EQUAL, // >=

    等于,// ==

    NOT_EQUAL, // !=

    分配,// =

    分号, // ;

    逗号, // ,

    LEFT_ROUND_BRACKET, // (

    RIGHT_ROUND_BRACKET, // )

    左方括号,// [

    RIGHT_SQUARE_BRACKET, // ]

    LEFT_CURLY_BRACKET, // {

    RIGHT_CURLY_BRACKET, // }

    // EOF

    END_OF_FILE, // EOF

    // AST

    DECL_LIST, // AST:DeclList

    VAR_DECL, // AST: VarDecl

    FUNC_DECL, // AST: FuncDecl

    PARAM_LIST, // AST:参数列表

    参数,// AST:参数

    COMPOUND_STMT, // AST: CompoundStmt

    LOCAL_DECL, // AST: LocalDecl

    STMT_LIST, // AST: StmtList

    IF_STMT, // AST: IfStmt

    WHILE_STMT, // AST: WhileStmt

    RETURN_STMT, // AST:ReturnStmt

    EXPR, // AST: Expr

    VAR, // AST: Var

    SIMPLE_EXPR, // AST: SimpleExpr

    ADD_EXPR, // AST: AddExpr

    术语,// AST:术语

    呼叫,// AST:呼叫

    ARG_LIST, // AST: ArgList

    };

    需要明确的是,上述代码的最后一部分是 AST 节点类别,与词法分析器无关。我们将在接下来的旅程中介绍该类别的这一部分的作用。

    4. 其他准备

    在实现词法分析器之前,我们还有一些比较简单的准备工作要做,列举如下:

    我们需要定义一个结构来保存标记:

    结构令牌

    {

    // 属性

    TOKEN_TYPE 令牌类型;

    字符串 tokenStr;

    int lineNo;

    };

    在这个结构中,我们存储了令牌的类别、令牌字符串以及令牌所在的源代码中的行数。

    我们需要定义一个哈希表来完成常用词到关键字的识别和转换:

    const unordered_map KEYWORD_MAP

    {

    {“无效”, TOKEN_TYPE::VOID},

    {“int”, TOKEN_TYPE::INT},

    {“如果”, TOKEN_TYPE::IF},

    {“else”, TOKEN_TYPE::ELSE},

    {“while”, TOKEN_TYPE::WHILE},

    {“return”, TOKEN_TYPE::RETURN},

    通过key的存在检测,可以判断一个词是否为关键词;如果是这样,我们也可以得到关键字对应的token的类别。

    我们需要定义一个报错函数,当词法分析器发现语法错误时,报错并退出:

    void InvalidChar(char invalidChar, int lineNo)

    printf(“无效字符: %c in line: %dn”, invalidChar, lineNo);

    退出(1);

    }

    至此,我们已经完成了所有的准备工作,可以开始实现词法分析器了。请参阅下一章:实现词法分析器。

    猫的笔记:《编译器实现之旅》一共有17篇。其余文章请访问小姐姐的博客。博客地址:

    站内大部分资源收集于网络,若侵犯了您的合法权益,请联系我们删除!
    欧资源网 » 编译器内部一探编译器编译器编译器

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    欧资源网
    一个高级程序员模板开发平台

    发表评论