type
status
date
slug
summary
tags
category
icon
password
简单编译器
本章是上一章编译概论的一个具体实现例子，也就是一个简单的编译器，并且相关知识点在后续章节有详细的说明，所以在这里就不多做说明了
表达式和语句
表达式和语句是不同的，语句是一个表达式加上一个分号
语法规则和词法规则
语法规则就是高级的抽象语法成分，比如while语句的格式是while（布尔表达式）语句，是对非终结符以及非终结符的组合的分析
词法规则就是低级的语法成分，比如标识符（一个单词）的命名规则，所以这个时候语法规则就会降格为词法规则，是对终结符的分析
词法分析器和语法分析器（词法分析与语法分析）
词法分析器就是处理词法规则的（也就是降格的语法规则，更直白的说，就是用来识别终结符的，判断终结符是否合法）
词法分析器的主要方法有以下两个（注意在词法分析时需要跳过空格和注释等无效符号，所以在实验三中的.l文件中如果识别了一个换行符，词法分析器是不需要返回东西的）
- 状态转移图法（也就是自己手搓一个确定有限自动机，还有一种是表驱动法，应该就是搓出来状态转换表）
这个就是一个词法分析器的确定有限自动机
- 正则表达式法（flex）
语法分析器是处理语法规则的（也就是处理文法的，判断程序在语法层面是否正确）
主要方法有以下两个
- 自上而下：从文法推导出程序
- 递归下降分析法：带回溯
- 预测分析法：向前看若干个字符（LL1的1就是代表向前看一个字符）然后确定要将某个非终结符推导为什么，是不带回溯的
就是将每一条文法（语法规则）当成一个函数，也就是说每一个终结符的解析都是一个递归下降分析函数，而非终结符能推导出的东西就是该非终结符对应的递归下降函数的函数体。
说白了就是右侧如果是一个终结符就advance，如果是一个非终结符就调用对应的分析函数，如果一个非终结符有多条推导规则就需要逐个尝试（所以是带回溯的，这个时候需要去存储tok的序列，因为识别了一个单词之后就会将该tok消耗，但是回溯的话又需要恢复到原来的状态，也就是恢复为走错路之前的tok情况）
也就是下图所说的：
上面两张图片是一个具体的递归下降分析程序，其中的终结符就对应着match识别函数，而非终结符就对应其中的分析函数（注意每一条规则的符号识别都是嵌套的，此时if里面的条件是识别了某个符号，而不是像上面那样是判断没有识别哪些符号）。得出结论，在if里面填写识别了某个符号，然后每个非终结符推导出来的可能的表达式的判断是嵌套的，不同的表达式之间是if else并列的
当一个文法对应多条规则的时候就将其翻译为if else语句，然后逐个匹配，只有当进入最后的一个else中时才认为输入串是不合法的，也就是下图说明的情况（这个时候需要存储tok，并为回溯做准备，也就是记录进入某个分支时的tok位置）：
注意递归向下分析法没办法处理左递归和公共左因子
没办法处理左递归是因为会出现死递归的情况
而不能处理公共左因子是因为如果有公共左因子的话就会导致if分支条件是相同的，都是match同一个终结符或非终结符
一个消除左递归的例子：
上面这个例子展示了递归下降分析法是如何处理空串的（就是可以识别，对应着if语句，也可以不识别，没有进入if语句不代表语法错误，因为当前非终结符是可以推导成空的，也是合法的。所以带空的非终结符不进入if是返回1而不是返回0提醒说识别失败）
下面是一个具体的递归下降分析过程
预测分析法的思想——向前看若干个符号（tok）
- 自下而上：从正确的程序规约为文法的开始符号，就是LR一家
创建抽象语法树的时候（此时还在语法分析阶段）就需要进行符号表的填写，这个时候需要将变量的作用域等信息确定以便后续使用（词法分析的时候不可能确定，只有将变量放在文法中的时候才能确定他的作用域到底是什么，之后的语义分析的类型检查也需要这个在语法分析建树阶段创建的符号表）
所以说语法分析阶段，在创建语法树的时候需要去填写符号表（符号表应该在词法分析阶段就开始填写了），然后在语义分析阶段就需要调用这个符号表对语法树进行类型检查（所以经常说语义分析是包含在语法分析的过程中的，因为在创建语法树填符号表的时候就能进行类型检查了）
小知识：c和cpp中可以用整型值来表示布尔值，但是java和c#中就不行（java有专门的true和false），并且布尔类型占一个字节而不是一位是因为计算机通常不能只访问一个位
语义分析
在语义分析阶段主要的任务就是根据符号表进行类型检查
也就是做类型检查，类型是否匹配（比如一个整形数和一个浮点数之间能否进行一些操作），强制类型转换也应该是这个时候做的，就是发现没办法匹配的时候就进行类型转换（某些情况下才能进行类型转换）
小知识：静态语言的类型在编译时确定（这样可以使程序正确有效），或者说类型检查在编译时全部完成；而动态语言的类型在运行时确定（可以使编程方便，但是可靠性降低），也就是编译时没办法检查完所有类型
真是不明白周尔强的逻辑）
上图的小知识：无类型就是没有类型定义，弱类型就是所有类型检查在编译时完成，强类型就是类型检查没有在编译时全部完成
中间代码生成
注意三地址代码每一步只能完成一个操作（=赋值也算是一个操作），并且等号的右边最多只能有两个变量，实际上就是每一个语法树的节点都是一个三地址代码（如二元操作的节点，左右子树为操作数，根节点为操作符，那么这个以操作符为根的子树就对应了一个三地址代码），也就是下图中提到的：约定:该子树的结果保存在当前的临时变量中
这个是三地址代码生成的逻辑，也就是遍历语法树（语法树是在语法分析阶段生成的）然后根据符号表生成三地址代码（实验四llvm应该也是这个逻辑）
具体操作就是根据节点的类型来取值，得到三地址代码所需要的东西
- 作者:Noah
- 链接:https://imnoah.top/article/Compiler/Chapter2
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。