“编译原理”学习笔记
三月 11, 2020
引论
在一个程序可以运行之前,它首先需要被翻译成一种能够被计算机执行的形式。完成这项翻译工作的软件系统称为编译器。
解释器并不通过翻译生成目标程序,解释器直接利用用户提供的输入执行源程序中指定的操作。
一个编译系统包括:
- 源程序经过预处理器生成经过预处理的源程序;
- 再经过编译器生成目标汇编程序;
- 再经过汇编器生成可重定位机器代码;
- 经过链接器/加载器(同时加入库文件、可重定位对象文件)生成机器代码。
编译器的两个主要部分:分析与综合/前端与后端。
编译器内部需要经过:词法分析、语法分析、语义分析、中间代码生成、机器无关代码优化、代码生成、机器相关代码优化后输出目标机器语言。
- 词法分析:将输入代码中的字符流,组织称有意义的词素序列,每个词素用词法单元输出。
- 语法分析:用递归的方式构建语法树,树中每个节点表示一个运算。
- 语义分析:检查源程序是否和语言定义的语义一致,同时也收集类型信息,存在放在语法树或者符号表里。
- 中间代码生成:编译器在经过上面三个步骤以后,可以生成一个明确的低级的或类机器语言的中间过程。该中间表示应该易于生成、且能够被轻松地翻译为目标机器上的语言。
- 代码优化:代码优化器会在中间代码的基础上在时间和空间上优化代码。
- 代码生成:最终翻译成机器能够运行的代码。
- 符号表的管理
- 记录在原代码中使用的标识符和属性信息;
- 提供每一个标识符的类型、参数等。
词法分析
词法分析器是编译器的第一部分,是将输入代码中的字符流,组织称有意义的词素序列,每个词素用词法单元(tokens)输出。
词法单元:
- 分为关键字、标识符、算术符号、多字符符号(>=,<>)
- 识别划分词法单元用规则(pattern)
- 词素有意义的单词
- 因为一个 token 可能有不同的表达意思,所以需要他的属性来表示他所表示的内容,所以需要用词素。
- 可以通过定义一个无意义的 token 来过滤空白的信息。
词法分析工作步骤:
- 扫描输入(源代码)
- 去掉无意义的字符(换行、空格等)
- 找到 tokens
- 创建符号表
- 将 tokens 加入符号表
- 返回错误
- 将词法单元(tokens)输出给语法分析器
如何判断合法的 tokens
- 用正则表达式来判断 tokens 是否合法
- 正则表达式是一个构造符号序列的规则集合
- 空串用 \(\varepsilon \) 表示
- 正则表达式的定义:\(\varepsilon | a | r+r|rr|r^{*}|(r)\)
- 正则表达式是一个构造符号序列的规则集合
- 检验一个表达式是否合法的使用 DFA(确定型自动机)
语法分析
上下文无关法
上下文无关法由终结符号、非终结符号、一个开始符号和一组产生式组成。
- 终结符号一般有:
- 排在前面的小写字母
- 运算符号
- 标点符号
- 数字
- 黑体字符串,例如 id 或 if
- 非终结符号一般有:
- 排在前面的大写字母
- S 一般表示开始符号
- 小写、斜体的名字,比如 expr stmt
推导
- 最左推导:总是选择每个句型的最左非终结符号,记做 \(\Rightarrow _{lm}\)
- 最右推导:总是选择每个句型的最右非终结符号,记做 \(\Rightarrow _{rm}\)
- 语法分析树是推导的图形表示,它过滤掉了推导过程中对非终结符号应用产生式的顺序。
- 语法分析树的叶子结点的标号既可以是非终结符号,也可以是终结符号,从左到右排列这些符号就可以得到一个句型,成为这棵树的结果或边缘
CFG 应该没有二义性、左递归、公共左因子。